Info Guide #09 31 июля 2006

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

Inferno - О воксельном летающем слоне IG #5.

       О летающем слоне
   Воксель - это объёмный пиксель, малень─
кий кубик. На ZX реализуемы не только всем 
известные воксельные пейзажи типа Mars, но 
и воксельные объекты,которые можно крутить 
по  всем осям. В интро к 5-му номеру IG вы 
видели пример такого объекта. Если объект, 
аналогичный по сложности тому, который был 
в IG #5 (а там был как раз летающий слон), 
построить текстурированными полигонами, то 
скорость прорисовки сильно бы упала. 

   В общих  чертах, как  работает  эффект?
Работает он простым brute force'ом. Каждо─
му направлению взгляда соответствует некий
направляющий  вектор определённой длины (у
меня это порядка 8 клеточек); мы двигаемся
шагами  по этому вектору, пока не встретим
непустой воксель. Берём цвет этого вокселя
и кидаем его на экран (точнее,в chunkmap).
   Этот простой алгоритм я использовал ещё
в 1996 году в первых заготовках к Wolf 3d.
Тогда он, правда,не содержал никаких ухищ─
рений для ускорения сканирования и страшно
тормозил...
   Объект описан двумя картами. Первая ка─
рта (по  ней  мы сканируем) в страничке не
помещается  из-за  того, что предусмотрены
пустые края - для исключения зашкаливания.
Эта  карта  для каждой пары координат X, Y
содержит  толщину  объекта (Z-координату).
Вторая  карта  занимает страничку и хранит
цвет вокселя с координатами X, Y (и вышеу─
казанной Z). Y соответствует старшему бай─
ту адреса в карте, X соответствует младше─
му байту этого адреса. Во второй карте все
адреса больше на #2000.
   Ещё  в одной  страничке  лежит стековая
выводилка  чанков  наподобие  той, которую
описал  Monster  в  Born Dead #5. В данном
случае реализовано 16 цветов, коды которых
#c0,#c4,...,#fc.
   Поскольку  слон симметричнен, требуется
только  одна  Z координата для каждой пары
координат  X, Y. Если  нужно посмотреть на
слона с другой стороны,мы просто делаем (в
начале  сканирования конкретного экранного
пикселя)   преобразование:  Z0=-Z0  (Z0  =
z-координата  точки  начала сканирования),
dZ=-dZ (dZ = z-шаг сканирования). 
   Обе  карты  были нарисованы в фотошопе.
Процесс  рисования  происходил  задолго до
написания кода.Поэтому для контроля я сле─
пил маленькую программку на Delphi, позво─
ляющую  смотреть  разрезы  слона. Это дало
возможность  увидеть "заусенцы" в местах с
низким Z (т.е. там, где  полуслон соприка─
сается  со  своим  отражением).  Увиденные
"заусенцы" я, естественно,стирал в фотошо─
пе.
   Цикл сканирования такой:

 LOOPout 
         EXX
         ADD IX,BC
         ADD HL,DE
         LD A,H
         EXX
         LD E,A
         LD D,HX
         LD A,(DE)
         ADD HL,BC
         JR C/NC,LOOPzro
         CP H
         JR C,LOOPQ ;DE=YX
         DEC LY ;делаем не более 14 шагов
        JP NZ,LOOPout
 LOOPzro LD DE,zro  ;ничего не нашли 
        RET

   Вообще  таких циклов в программе 4 шту─
ки, под разные ситуации (учитывается пере─
ход с Z>0 на Z<0 и наоборот). Адрес DE=zro
(там лежит  чёрный  пиксель) отличается от
всех прочих  результатов сканирования тем,
что он меньше #8000.
   Если  бы мы сканировали все направления
(44*44=1936 штук), то  эффект  давал бы не
более одного кадра в секунду. Эту проблему
удалось решить с помощью интерполяции.
   В первую  очередь - мелкая интерполяция
(блур): размазывание полученных при скани─
ровании X,Y координат через 1 пиксель.(Она
в голову приходит в первую очередь, но вы─
полняется-то она в последнюю очередь!)
   Чтобы реализовать интерполяцию, резуль─
таты сканирования (X,Y в координатах объе─
кта) мы  не  используем  сразу, а кладём в
 массив SCANS. Размер этого массива
      ((HEIGHT/2)+1)*(WIDTH+1) слов,
где  WIDTH - ширина  экрана  в знакоместах
(парах  чанков), а  HEIGHT - его  высота в
чанках. Здесь +1 для того,чтобы можно было
проводить  усреднение  на  правом и нижнем
краях картинки.На этих краях массив всегда
содержит  значение zro, мы там не сканиру─
ем.Как можно догадаться из размеров,в этом
массиве лежат пиксели, имеющие только чёт─
ные экранные координаты,а остальные пиксе─
ли вычисляются блуром  в процессе заполне─
ния chunkmap'а (цикл read0).
   Но  реально  сканирование идёт не через
пиксель, а  через  3 пикселя (цикл scan0).
Грубая интерполяция (цикл ish0) интерполи─
рует его результаты.Чтобы получить из этих
результатов  результаты сканирования якобы
через  пиксель, уже  недостаночно простого
размазывания.Для некоторых пикселей произ─
водится  дополнительное сканирование (цикл
fill0). Вот по такой схеме:
 

                    S1S
                    121
                   S1S

где S=SCAN, 1,2=обработка: если все соседи
<>zro или все =zro, то клетка интерполиру─
ется,иначе сканируется. Признак "а ну ска─
нируй  эту  клетку!" передаётся  из  цикла
ish0  циклу  fill0  в  виде значения X=-1.
Если грубая интерполяция выключена,то X=-1
передаётся  во всех случаях (по кнопке "S"
в метки MAYBEJP кладётся команда безуслов─
ного перехода).

   Исходник - как обычно, в приложении.

   Можно  ещё  ускорить, если  удвоить шаг
сканирования. Тогда после пересечения гра─
ницы объекта надо смотреть,не пересекли ли
мы объект на полшага раньше.Если да,то во─
звращаем  в качестве результата сканирова─
ния эту заполшаговую координату. Так рабо─
тает  сканирование  в Wolf2004. Недостаток
такого двойного сканирования в том,что оно
может срезать углы и мелкие детали. Однако
текстуру на крупных деталях оно накладыва─
ет правильно.

Alone Coder