Spectrum Expert #02 31 марта 1998

Программирование

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