Spectrum Expert #02
31 марта 1998

Программирование - 3D на спектруме: быстрый метод обсчета вершин, вывод 3d обьектов с заливкой.

<b>Программирование</b> - 3D на спектруме: быстрый метод обсчета вершин, вывод 3d обьектов с заливкой.
                                        
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). На самом деле результат никуда сдвигать не надо. Вроде, больше не припоминается ничего. Давно это было ...



Другие статьи номера:

Помощь - Целью настоящей инструкции является привитие читателю навыков и умений по употреблению информации, содержащейся в журнале.

От редакции - Интересно, для чего существуют электронные журналы на платформе Cпектрум?

Новости - NЕМО выпущена модель KAY-1024, CКОРПИОН выпущена первая опытная партия GМX, DIGIТAL RЕALIТY выпущен обзорный фильм по Еnlight'97, LD приступил к созданию новой версии ассемблера SТОRМ 2.0.

Железо - ZX-ВUS: Если вы решили сделать из своего Cпектрума нормальный компьютер, то эта статья для вас.

Железо - о констуркция различных клонов ZX Spectrum.

Мнение - новый супер Спектрум: Sprinter, для чего он нужен?

Музыка - Компьютерная музыка: почему ни одна звуковая карта, даже самая дорогая, не родит настоящей музыки и не проиграет вам модуля с качеством компакт-диска.

Почта - Ура, у наc уже пиcьма: Парфенов Cергей, Пименов Валентин.

Игрушки - обзор игр: Anarachy, Captain Planet, Tag Team Wrestling, Headball, Chase H.Q., Superted, Sword of hte Samurai.

Игрушки - описание игры Little Соmputer Рeоple.

Программирование - 3D на спектруме: быстрый метод обсчета вершин, вывод 3d обьектов с заливкой.

Софт - описание языка программиирования Паскаль для ZX Spectrum от фирмы Hisoft.

Софт - описание языка программиирования CИ для ZX Spectrum от фирмы Hisoft.

Фомин - любовный роман про Амигу и Писюк.

Фомин - Хит-парад: Итак, встречайте, господа, парад начинается!

Реклама - фирма Scorpion: Cокращенная версия нашего прайса по тематике Sрectrum.

Реклама - фирма Nemo: Фирма "NЕМО" предлагает свою продукцию, а также продукцию производителей Cанкт-Петербурга.

Реклама - фирма Welcome: программное обеспечение для ZX-SРЕCТRUМ 48/128/256К.

Реклама - фирма X-Trade: Нашему журналу требуется нормальная музыка для статей и intrо!!!!!


Темы: Игры, Программное обеспечение, Пресса, Аппаратное обеспечение, Сеть, Демосцена, Люди, Программирование

Похожие статьи:
О вирусах - Virus 6.05b & Virus 7.06b.
Разберемся - Полное описание игр QUAZATRON & MAGNETRON.
Железо - Самодельное сканирующее устройство : принцип работы.

В этот день...   29 января