Spectrum + 3D #2
(c)1998 Dark/X-Trade and -STS-/VolgaSoft
----------------------------------------
Вот и вышел второй номер нашего журнала
и, соответственно, вышла вторая часть из
серии о ЗD-графике на Спектруме.
Предыдущая статья получилась весьма
объемной, и, к превеликому сожалению,
после выхода журнала вылезли на свет бе-
лый злостные неточности и пакостливые
опечатки, также не всё из обещанного бы-
ло реализовано (в силу объективных при-
чин).
Однако, не очень хорошо начинать новую
статью с описания недостатков старой,
поэтому полный список обнаруженных глю-
ков желающие могут найти в самом конце.
----------------------------------------
Итак, из прошлой статьи Вы узнали о
том, как вращать 3D обьекты и выводить
их на экран в виде линий. Но Вы также
убедились, что просчет вершин - это за-
нятие весьма времяёмкое, особенно при
большом количестве оных в объекте. Ну
что тут поделаешь? Казалось бы, надо
как-то ускорить процедуры умножения/де-
ления, да уж вряд ли их ещё возможно
ускорить. Даже используя приблизительное
умножение и деление (8-битные таблицы)
прирост в скорости получается не таким
большим, как хотелось бы.
Вот тут-то и поджидает нас один инте-
ресный метод обработки вершин. В прошлой
статье было заявлено, что "...будет опи-
сан метод, который позволяет с легкостью
обрабатывать объекты, состоящие из сотни
вершин." Строго говоря, не всё так прос-
то, но, в принципе, это чистая правда.
Как и всё в этом мире, этот метод был
придуман разработчиками Спектрумовских
игрушек в 3D. Он избавляет нас от необ-
ходимости делать 12 умножений на точ-
ку (хотя деления делать всё-таки придет-
ся) и, тем самым, позволяет кардинально
повысить производительность расчетов, в
очередной раз доказывая истину: всё ге-
ниальное - просто.
Метод средней точки.
-------------------------------------
Опустим тот факт, что название, как
обычно, придумано нами, так как реальное
название неизвестно, и перейдем непо-
средственно к описанию сего метода.
Вначале обычным способом рассчитывается
куб (хотя в принципе это может быть вов-
се и не куб, а скажем, додекаэдр, не в
этом суть).
Рисунок 1. Вот куб, который
построил ...
Четыре вершины (0-3) куба на рисунке 1
просчитываются как обычно. Оставшиеся
четыре (4-7) получаем зеркальным отраже-
нием относительно центра куба. Готовые
вершины складываем в начало буфера вер-
шин. Заметьте, что вершины всё ещё трёх-
мерны, так как до перспективного преоб-
разования дело ещё не дошло.
Итак, куб готов. Настало время поиметь
с него координаты точек 8,9,10, которые,
как видно из рисунка, составляют вершины
плоскости, нуждающейся в прорисовке.
Сделать это очень просто:
v8=(v4+v5)/2
v9=(v3+v7)/2
v10=(((v3+v2)/2+v3)/2+v9)/2
Пде vN означает вершину с номером N, а
так как вершина задана тремя координата-
ми, то надо выполнить соответствующие
действия над каждой координатой соответ-
ствующей вершины.
В последнем выражении, которое показа-
лось Вам, наверное, немного громозким,
(v3+v2)/2 являются координатами вершины
11, которая показана на рисунке только
в целях иллюстрации.
Формулы формулами, а как же это реали-
зовать на практике? Решение очень прос-
тое - нужно написать программу для каж-
дой точки!
Но не для Z80 (это было бы слишком
жирно), а для виртуального процессора,
который мы будем программно эмулировать!
Пусть наш миниатюрный "процессор" будет
иметь всего один регистр и ОЗУ размером
64 24-битных слова (для хранения 8 бит-
ных XYZ), и будет у него лишь 4 команды
фиксированной длины.
Команды имеют следующий формат:
aabbbbbb
где а = код команды
b = номер точки (N) 6 бит
00 Загрузить в регистр координаты точки
N.
01 Положить содержимое регистра в точку
N.
10 Найти среднее арифметическое между
регистром и точкой N.
11 Закончить выполнение программы.
Можно написать такую программу для вы-
шеприведенного примера с треугольником.
;v8=(v4+v5)/2
;v9=(v3+v7)/2
;v10=(((v3+v2)/2+v3)/2+v9)/2
DB 4,128!5,64!8
DB 3,128!7,64!9
DB 3,128!2,128!3,128!9,64!10
DB -1
После обработки всех точек осталось
только выполнить перспективное преобра-
зование и нарисовать объект.
Вот и всё. Смотрите исходник MIDPNT10
(Middle Point) под Storm1.х (как и в
прошлый раз, в формате текста) и
ищите там процедуру CUBE. На диске также
лежит файлик MIDPNT12, который представ-
ляет собой вышеупонянутую прогу, но в
ней нормальные умножения и деления
заменены на приблизительные, которые в
2-4 раза быстрее нормальных.
Поворя о скорости вообще, несложно за-
метить, что даже вращение четырех точек
весьма времяпоглащающее занятие, так как
на каждую точку требуется 12 умножений,
а всего их надо 48... Путей оптимизации
несколько.
Первый - просчитав только 3 точки, с
помощью несложной арифметики можно доба-
вить и четвёртую.
Второй - вращать куб в полярной системе
координат.
A вот считать матрицу для для четырех
точек неэффективно, так что любителям
матриц придется попробовать указанные
два способа оптимизации, либо придумать
что-либо своё...
Сделаем объекты сплошными
---------------------------------------
Линии сравнительно быстры, но это ещё
не повод, чтобы зацикливаться на них.
Поэтому сейчас мы рассмотрим заливку
полигонов и слегка коснемся проблемы
удаления невидимых поверхностей.
Начнем с последнего. Пока мы будем ри-
совать выпуклые объекты, потому что для
их отображения достаточно лишь опреде-
лить, какие грани рисовать не нужно. В
сложных объектах этого недостаточно, так
как там будут и частично невидимые по-
верхности, для которых нам придется де-
лать сортировку по Z.
Для определения видимости грани (она в
свою очередь должна быть выпуклым много-
угольником) существует простой метод,
основанный на определении направления
вектора нормали поверхности к наблюдате-
лю, точнее, только его Z компоненты.
Взгляните на рисунок 2. Для получения
полного удовлетворения от просмотра ни-
жевыставленного арт-произведения, следу-
ет оперативно принять позу лотоса (в
стойке на голове) и находится в таком
положении на протяжении двух-трёх лет,
стараясь найти истину и оптимизируя за-
ливку полигонов (шутка).
Рисунок 2. Статуя Венеры Мелосской в
свободной интерпретации Малевича.
Вектор нормали находится путем вычис-
ления векторного произведения двух любых
смежных рёбер грани (например 1-2=V,
2-3=W). Обратите внимание, что грань
должна быть задана по часовой стрелке!
Нам нужна только Z компонента, поэтому
ей и ограничимся.
Vz х Wz=VX*WY-VY*WX =
= (X2-X1)*(Y3-Y2)-(X3-X2)*(Y2-Y1)
Если результат будет <=0, значит, грань
невидима.
Как Вы помните, для рисования объекта
из линий достаточно иметь массив, описы-
вающий ребра, который, в свою очередь,
ссылается на конкретные точки, между
которыми должна быть проведена линия.
Объект, составленный из граней, пред-
ставляется в виде описаний плоскостей,
которые ссылаются на конкретные точки,
через которые должна быть проведена
плоскость. Причем, плоскость должна быть
задана по часовой стрелке, дабы пра-
вильно работало отсечение нелицевых гра-
ней (у нас односторонние грани).
Для плоскости на рисунке 2 массивчик
будет выглядеть так:
DB 4,0,1,2,3
Первый элемент массива содержит коли-
чество точек в полигоне.
Выпуклые полигоны (мы будем использо-
вать исключительно их) заливать неслож-
но, однако действо сие весьма и весьма
неторопливо.
Заливка, за исключением особых случаев,
представляет собой процесс заполнения
промежутка между левой (0-3-2) и правой
(0-1-2) стороной многоугольника гори-
зонтальными линиями (линии сканирова-
ния).
Существуют два способа заливки - двух-
проходная и однопроходная.
В двухпроходной заливке сначала трас-
сируется левая сторона, и начальная ко-
ордината X каждой линии сканирования
складывается в буфер левой стороны. По-
том трассируется правая сторона, и ко-
нечная координата X каждой линии скани-
рования складывается в буфер правой сто-
роны. Потом, во втором проходе, коорди-
наты левой и правой сторон извлекаются
из буфера, и между ними прорисовывается
линия.
В однопроходной заливке трассируются
сразу обе стороны, и сразу же между ними
рисуется линия.
C точки зрения оптимизации быстродейст-
вия, двухпроходная заливка вряд ли ока-
жется быстрее однопроходной, так как
приходится проделывать кучу лишних тело-
движений - производить две записи и два
последующих чтения из памяти, также
приходится обрабатывать 3 счетчика - по
одному на каждую сторону, плюс счетчик в
цикле прорисовки. Ко всему прочему, не-
обходимо ещё держать в памяти буфер сто-
рон...
После всех этих доводов не имеет смыс-
ла приводить здесь пример двухпроходной
заливки, а имеет смысл рассказать под-
робнее о заливке однопроходной, хотя
большинство моментов идентичны для обе-
их.
Исходными данными для построения поли-
гона является список координат точек,
образующих полигон. Как уже было сказа-
но, список задан по часовой стрелке. Для
упрощения процедуры заливки мы будем за-
ливать только односторонние полигоны,
так как, если полигон повернут к наблю-
дателю другой стороной, то изменяется
направление движения по списку.
Учитывая данное ограничение, можно быть
уверенным, что, идя вперед по писку, мы
попадаем на правую сторону полигона, идя
же в обратном направлении - попадаем на
левую сторону полигона.
Как видно из рисунка, каждая из двух
сторон состоит, в нашем случае, из двух
секций. Левая сторона из секций A-В и В-
D. Правая - из секций A-C и C-D. Левая и
правая стороны обрабатываются независимо
друг от друга.
Непосрественно перед трассировкой сто-
рон нужно найти точку, с которой надо
начинать трассировку и на которой надо
закончить, т.е. самую верхнюю и самую
нижнюю точки полигона. У нас они соот-
ветствуют точкам 0 и 2 соответственно.
Начиная от самой верхней точки, нам на-
до получить высоту и приращение коорди-
наты X (при перемещении на единицу по Y)
для левой и правой секций. Если высота
секции равна нулю, необходимо взять сле-
дующую из списка. При этом необходимо
следить за тем, чтобы не пропустить ко-
нечную точку и, если она достигнута,
надо выйти из процедуры, сделав как мож-
но меньше лишних движений.
Например, процедура обработки правой
стороны будет делать для секции A-C сле-
дующие вещи:
Вычислять высоту секции...
RsectHgt=Y1-Y0
И приращение X.
RdeltaX=(X1-X0)/RsectHgt
A процедура обработки левой стороны бу-
дет ещё и следить за достижением нижней
точки.
Плавный цикл выглядит примерно так:
1. Рисуем линию между Xleft и Xright.
2. Переходим на следующую строку.
3. Xleft+=LdeltaX, Xright+=RdeltaX.
4. LsectHgt-=1. При достижении нуля вы-
зываем процедуру обработки левой сторо-
ны. Если достигнута конечная точка, вый-
дем из процедуры заливки.
5. RsectHgt-=1. При достижении нуля вы-
зываем процедуру обработки правой сторо-
ны.
6. Перейдем на пункт 1.
Как видите, всё это весьма просто, так
что нет необходимости приводить здесь
какой-либо код. Детали смотрите в файле
3DROT20.
Если надо нарисовать много небольших по
размерам полигонов, имеет смысл рисовать
не прямо на экран (в теневой, естествен-
но), а в буфер, имеющий простую органи-
зацию - изменением младшего байта адреса
мы переходим по Y (0-255), а изменением
старшего байта адреса переходим по X (0-
31).
Таким образом ускоряется расчет адреса
по координатам, переход на следующую
строку и выбор байта заливки. Буфер та-
кого формата выбрасывается на экран
строкой вида (как это сделано в деме
Spirius от Mayhem):
LD В,(HL):DEC Н
LD C,(HL):DEC Н
PUSH ВС
На выброс байта уходит 16.5 тактов (а
на Скорпе - все 18!), так что подумайте
- а не перекроет ли это выигрыш от уско-
рения заливки?
Процедура заливки, приведенная в
3DROT20, не слишком шустрая, но и не
слишком медленная. В любом случае полез-
но бы было написать Ваш собственный ва-
риант. Это относится не только к залив-
ке, но и ко всему остальному коду. Там
имеется огромное поле для всяких оптими-
заций.
----------------------------------------
Все исходники написаны с использованием
специфического синтаксиса STORM turbo
assembler'а. Файлы записаны в текстовом
виде, чтобы посмотреть их можно было бы
вне ассемблера. Для загрузки их в STORM
следует воспользоваться функцией импорта
текстового файла - BREAK+Т.
----------------------------------------
Небольшой список использованных в
примерах синтаксических оборотов.
LD ВС,HL вместо LD C,L:LD В,Н
RL A,В,C,D вместо RL A:RL В:RL C:RL D
.13 PUSH HL тиражирует строку 13 раз,
LD В,A,C,A загружает В и C из
аккумулятора.
ЕХА значит ЕХ AF,AF'.
NUM[ это старший байт числа NUM.
NUM] это младший байт числа NUM.
----------------------------------------
Напоследок о грустном. Плюки предыдущей
статьи.
Плюк 1.
Пде: Алгоритмы/Умножение/метод
2/IXHL=IX*DE
В примере использована несуществующая
команда ADC IX,ВС. Я, как испорченный
Motoroll'ером до мозга костей человек,
часто допускаю эту глупую ошибку.
...
JR NC,$+5
ADD HL,DE
ADC IX,ВС ;Нет такой команды...
...
Плюк 2.
Пде: Алгоритмы/Композиционное умножение
/точный метод, а также в файле
ALGORITM (откуда и вышел глюк)
Допущена и размножена в двух экземпля-
рах небольшая опечатка - беззнаковое де-
ление пополам вместо знакового.
LD L,A
SBC HL,ВС
SBC HL,DE
SRL Н:RR L ; Надо SRA Н:RR L
RET
MULS1 LD A,L:SUB Е
....
ЕХ DE,HL
ADD HL,ВС
SBC HL,DE
SRL Н:RR L ;То же самое
RET
Плюк 3.
Пде: Алгоритмы/Композиционное деление/
вычисление Y=Log X на басике ите-
рационной формулой.
Так как всё дело писалось в редакторе,
идентичный блок был скопирован из друго-
го примера, но, как оказалось, не из
того.
Программа должна быть такой:
LET D=0
FOR X=1 ТО 255
РОКЕ A+X,D-256*INT (D/256)
РОКЕ A+256+X,D/256
LET D=D+1/((х+4606)*LN 2)
NEXT X
Плюк 4.
Пде: Алгоритмы/умножение/Замечание #3
... Действительно, если мы знаем, что,
например, старшие 3 бита множителя нули,
зачем каждый раз проверять это?
Достаточно сдвинуть множитель влево
Плюк 4.
Пде: Алгоритмы/умножение/Замечание #3
... Действительно, если мы знаем, что,
например, старшие 3 бита множителя нули,
зачем каждый раз проверять это?
Достаточно сдвинуть множитель влево
(для второго метода) на эти самые 3 би-
та и сделать лишь 5 итераций умножения.
Очевидно, что результат тоже надо сдви-
нуть на 3 бита влево...
Последнее предложение представляет со-
бой типичный заскок (т.н. thinko). На
самом деле результат никуда сдвигать не
надо.
Вроде, больше не припоминается ничего.
Давно это было ...
Other articles:
Вектор нормали находится путем вычис- ления векторного произведения двух любых смежных рёбер грани (например 1-2=V, 2-3=W). Обратите внимание, что грань должна быть задана по часовой стрелке! Нам нужна только Z компонента, поэтому ей и ограничимся. Vz х Wz=VX*WY-VY*WX = = (X2-X1)*(Y3-Y2)-(X3-X2)*(Y2-Y1) Если результат будет <=0, значит, грань невидима. Как Вы помните, для рисования объекта из линий достаточно иметь массив, описы- вающий ребра, который, в свою очередь, ссылается на конкретные точки, между которыми должна быть проведена линия. Объект, составленный из граней, пред- ставляется в виде описаний плоскостей, которые ссылаются на конкретные точки, через которые должна быть проведена плоскость. Причем, плоскость должна быть задана по часовой стрелке, дабы пра- вильно работало отсечение нелицевых гра- ней (у нас односторонние грани). Для плоскости на рисунке 2 массивчик будет выглядеть так: DB 4,0,1,2,3 Первый элемент массива содержит коли- чество точек в полигоне. Выпуклые полигоны (мы будем использо- вать исключительно их) заливать неслож- но, однако действо сие весьма и весьма неторопливо. Заливка, за исключением особых случаев, представляет собой процесс заполнения промежутка между левой (0-3-2) и правой (0-1-2) стороной многоугольника гори- зонтальными линиями (линии сканирова- ния). Существуют два способа заливки - двух- проходная и однопроходная. В двухпроходной заливке сначала трас- сируется левая сторона, и начальная ко- ордината X каждой линии сканирования складывается в буфер левой стороны. По- том трассируется правая сторона, и ко- нечная координата X каждой линии скани- рования складывается в буфер правой сто- роны. Потом, во втором проходе, коорди- наты левой и правой сторон извлекаются из буфера, и между ними прорисовывается линия. В однопроходной заливке трассируются сразу обе стороны, и сразу же между ними рисуется линия. C точки зрения оптимизации быстродейст- вия, двухпроходная заливка вряд ли ока- жется быстрее однопроходной, так как приходится проделывать кучу лишних тело- движений - производить две записи и два последующих чтения из памяти, также приходится обрабатывать 3 счетчика - по одному на каждую сторону, плюс счетчик в цикле прорисовки. Ко всему прочему, не- обходимо ещё держать в памяти буфер сто- рон... После всех этих доводов не имеет смыс- ла приводить здесь пример двухпроходной заливки, а имеет смысл рассказать под- робнее о заливке однопроходной, хотя большинство моментов идентичны для обе- их. Исходными данными для построения поли- гона является список координат точек, образующих полигон. Как уже было сказа- но, список задан по часовой стрелке. Для упрощения процедуры заливки мы будем за- ливать только односторонние полигоны, так как, если полигон повернут к наблю- дателю другой стороной, то изменяется направление движения по списку. Учитывая данное ограничение, можно быть уверенным, что, идя вперед по писку, мы попадаем на правую сторону полигона, идя же в обратном направлении - попадаем на левую сторону полигона. Как видно из рисунка, каждая из двух сторон состоит, в нашем случае, из двух секций. Левая сторона из секций A-В и В- D. Правая - из секций A-C и C-D. Левая и правая стороны обрабатываются независимо друг от друга. Непосрественно перед трассировкой сто- рон нужно найти точку, с которой надо начинать трассировку и на которой надо закончить, т.е. самую верхнюю и самую нижнюю точки полигона. У нас они соот- ветствуют точкам 0 и 2 соответственно. Начиная от самой верхней точки, нам на- до получить высоту и приращение коорди- наты X (при перемещении на единицу по Y) для левой и правой секций. Если высота секции равна нулю, необходимо взять сле- дующую из списка. При этом необходимо следить за тем, чтобы не пропустить ко- нечную точку и, если она достигнута, надо выйти из процедуры, сделав как мож- но меньше лишних движений. Например, процедура обработки правой стороны будет делать для секции A-C сле- дующие вещи: Вычислять высоту секции... RsectHgt=Y1-Y0 И приращение X. RdeltaX=(X1-X0)/RsectHgt A процедура обработки левой стороны бу- дет ещё и следить за достижением нижней точки. Плавный цикл выглядит примерно так: 1. Рисуем линию между Xleft и Xright. 2. Переходим на следующую строку. 3. Xleft+=LdeltaX, Xright+=RdeltaX. 4. LsectHgt-=1. При достижении нуля вы- зываем процедуру обработки левой сторо- ны. Если достигнута конечная точка, вый- дем из процедуры заливки. 5. RsectHgt-=1. При достижении нуля вы- зываем процедуру обработки правой сторо- ны. 6. Перейдем на пункт 1. Как видите, всё это весьма просто, так что нет необходимости приводить здесь какой-либо код. Детали смотрите в файле 3DROT20. Если надо нарисовать много небольших по размерам полигонов, имеет смысл рисовать не прямо на экран (в теневой, естествен- но), а в буфер, имеющий простую органи- зацию - изменением младшего байта адреса мы переходим по Y (0-255), а изменением старшего байта адреса переходим по X (0- 31). Таким образом ускоряется расчет адреса по координатам, переход на следующую строку и выбор байта заливки. Буфер та- кого формата выбрасывается на экран строкой вида (как это сделано в деме Spirius от Mayhem): LD В,(HL):DEC Н LD C,(HL):DEC Н PUSH ВС На выброс байта уходит 16.5 тактов (а на Скорпе - все 18!), так что подумайте - а не перекроет ли это выигрыш от уско- рения заливки? Процедура заливки, приведенная в 3DROT20, не слишком шустрая, но и не слишком медленная. В любом случае полез- но бы было написать Ваш собственный ва- риант. Это относится не только к залив- ке, но и ко всему остальному коду. Там имеется огромное поле для всяких оптими- заций. ---------------------------------------- Все исходники написаны с использованием специфического синтаксиса STORM turbo assembler'а. Файлы записаны в текстовом виде, чтобы посмотреть их можно было бы вне ассемблера. Для загрузки их в STORM следует воспользоваться функцией импорта текстового файла - BREAK+Т. ---------------------------------------- Небольшой список использованных в примерах синтаксических оборотов. LD ВС,HL вместо LD C,L:LD В,Н RL A,В,C,D вместо RL A:RL В:RL C:RL D .13 PUSH HL тиражирует строку 13 раз, LD В,A,C,A загружает В и C из аккумулятора. ЕХА значит ЕХ AF,AF'. NUM[ это старший байт числа NUM. NUM] это младший байт числа NUM. ---------------------------------------- Напоследок о грустном. Плюки предыдущей статьи. Плюк 1. Пде: Алгоритмы/Умножение/метод 2/IXHL=IX*DE В примере использована несуществующая команда ADC IX,ВС. Я, как испорченный Motoroll'ером до мозга костей человек, часто допускаю эту глупую ошибку. ... JR NC,$+5 ADD HL,DE ADC IX,ВС ;Нет такой команды... ... Плюк 2. Пде: Алгоритмы/Композиционное умножение /точный метод, а также в файле ALGORITM (откуда и вышел глюк) Допущена и размножена в двух экземпля- рах небольшая опечатка - беззнаковое де- ление пополам вместо знакового. LD L,A SBC HL,ВС SBC HL,DE SRL Н:RR L ; Надо SRA Н:RR L RET MULS1 LD A,L:SUB Е .... ЕХ DE,HL ADD HL,ВС SBC HL,DE SRL Н:RR L ;То же самое RET Плюк 3. Пде: Алгоритмы/Композиционное деление/ вычисление Y=Log X на басике ите- рационной формулой. Так как всё дело писалось в редакторе, идентичный блок был скопирован из друго- го примера, но, как оказалось, не из того. Программа должна быть такой: LET D=0 FOR X=1 ТО 255 РОКЕ A+X,D-256*INT (D/256) РОКЕ A+256+X,D/256 LET D=D+1/((х+4606)*LN 2) NEXT X Плюк 4. Пде: Алгоритмы/умножение/Замечание #3 ... Действительно, если мы знаем, что, например, старшие 3 бита множителя нули, зачем каждый раз проверять это? Достаточно сдвинуть множитель влево Плюк 4. Пде: Алгоритмы/умножение/Замечание #3 ... Действительно, если мы знаем, что, например, старшие 3 бита множителя нули, зачем каждый раз проверять это? Достаточно сдвинуть множитель влево (для второго метода) на эти самые 3 би- та и сделать лишь 5 итераций умножения. Очевидно, что результат тоже надо сдви- нуть на 3 бита влево... Последнее предложение представляет со- бой типичный заскок (т.н. thinko). На самом деле результат никуда сдвигать не надо. Вроде, больше не припоминается ничего. Давно это было ...
