|
Spectrum Expert
#02
31 марта 1998 |
|
Программирование - 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). На самом деле результат никуда сдвигать не надо. Вроде, больше не припоминается ничего. Давно это было ...
Другие статьи номера:
Похожие статьи:
В этот день... 20 апреля