31 декабря 2017

   3D скролл: реализация
               Терминология

   Небольшой словарик  используемых в ста─
тье терминов.

  Текстураилислой текстуры- некий бит─
мап, который отображается на экран как на─ 
клонная плоскость с использованием перспе─ 
ктивно-корректного  алгоритма накладывания 
текстуры. 

  Байт текстуры- какой-либо байт,состав─
ляющий текстуры.Обычно в этих байтах испо─ 
льзуются  не более 4-5 текстурных пикселей 
(или битов).Такой трюк необходим для того, 
чтобы  ограничить на разумном уровне испо─ 
льзование памяти таблицами (см. ниже). 
   Для примера рассмотрим слой текстуры из
демы New Wave(рис. 8).Слева то,как он на 
самом  деле  хранится в памяти, справа - с 
вычтенной  константой. Можно заметить, что 
каждый  символ  имеет  ширину  5 или менее 
пикселей и располагается в битах 4..0 каж─ 
дого текстурного байта. 



  Экран,экранный байт- всё,что относится
к ZX-экрану 6912 байт. 

  Маппинг- отображение  текстуры  на эк─
ран. 

  Горизонтальная, вертикальная  таблица-
способ  расположения таблиц в памяти. Если 
в регистре H - номер (указатель) таблицы,а 
в  L - индекс  в таблице, то такую таблицу 
назовём горизонтальной. Наоборот, если L - 
номер таблицы, а H - индекс в ней, то таб─ 
лица вертикальная. 
   Аналогично   можно  классифицировать  и
буферы  с графическими  данными: если  для 
сдвига вправо на 1 байт мы делаем INC L, а 
для  сдвига вниз INC H или прибавляем кон─ 
станту  к HL - это  горизонтальный  буфер. 
Если  INC L сдвигает  HL на байт вниз (или 
вверх) а  INC H - на  байт  вправо, то это 
вертикальный буфер. 

              Основные идеи

   Основная  идея, в  общем-то, очевидна -
далеко  не каждая строчка экрана перерисо─
вывается каждый кадр.В верхней части можно
видеть  некий  шум  и альясинг (как в игре
Doom, если  отойти подальше от стены). Там 
обычно все строчки перерисовываются каждый
кадр.  Снизу, однако, ситуация  совершенно
другая, и для скролла на 1 текстурный пик─
сель  необходимо  провести  несколько  фаз
обновления  экрана (рис. 9). Весь процесс
скролла состоит в последовательном рендере
каждой фазы и сдвиге текстурного буфера на
1 пиксель  после того, как все фазы выпол─
нены.Обычно этот сдвиг производится просто
изменением указателя в текстурном буфере.



   Так  как  на каждом шаге в нижней части
экрана обновляются  далеко не все строчки,
а  в верхней  части - строчки относительно
узки,обычно получается весь эффект пускать
в 50 FPS  без двойной буферизации (т.е. на
одном экране!),успевая выполнить всю пере─
рисовку  вперёд  луча. Более того, попытка
использовать два экрана приведёт,очевидно,
к тому, что в нижней части экранов удвоит─
ся число линий, требующих обновления!
   Следующая  по важности идея заключается
в самом процессе маппинга:как именно байты
текстуры отображаются в байты экрана. Оче─
видно, этот  процесс происходит при помощи
множества таблиц - для каждого обновляюще─
гося экранного байта требуется столько та─
блиц, сколько текстурных байт в него попа─
дают (полностью или частично),при этом со─
ответствие  между экранными байтами и таб─
лицами фиксированно.В верхней части экрана
несколько текстурных байт отображаются в 1
экранный  байт, в  нижней - наоборот, один
текстурный  байт  отображается в несколько
экранных(рис.10).



   Все эти разнообразные таблицы генериру─
ются  в процессе прекалка, при этом обычно
оказывается (либо этого специально добива─
ются), что  количество различных таблиц не
превышает  256. Текстурные байты, как ука─
зывалось выше, обычно имеют 4 или 5 знача─
щих бит,следовательно,все таблицы маппинга
удобно  размещаются  в вертикальном виде в
блоке памяти размером соответственно 4 или
8  килобайт. Индексом (загружаемым в стар─
шую часть регистровой пары) в таких табли─
цах служит текстурный байт, к которому за─
ранее  (при отрисовке в слой текстуры, на─
пример), можно  прибавить смещение к блоку
таблиц. Номер  таблицы загружается в млад─
шую часть регистровой пары.
   Итак, всего  вышесказанного достаточно,
чтобы понять суть эффекта.

                Реализация

   Я, конечно  же, не  стану  загромождать
эту статью бесконечными портянками полного
Z80-кода эффекта, равно как и сорцами пре─
калка - оставлю  это в качестве упражнения
для достаточно заинтересованного читателя.
Тем не менее,ниже приведены ключевые фраг─
менты Z80-кода.
   Если  памяти в избытке (например, у вас
128-килобайтовый ZX), то можно просто сге─
нерить одну большую портянку кода для каж─
дой фазы, которая каждый экранный байт об─
рабатывает соответствующим образом: загру─
жает нужные номера таблиц, шагает по текс─
туре, объединяет значения из таблиц и т.д.
Суммарный объём такого кода (для всех фаз)
оказывается  в районе  нескольких десятков
килобайт.
   Пусть текстурный буфер горизонтален, мы
его  читаем  при  помощи POP , а на экран
указывает DE . Тогда код  может выглядеть
следующим образом:

;Шаг на следующую текстурную линию 
   LD HL,const
   ADD HL,SP
   RES 4,H;не допускаем выход за
            ;пределы буфера
   LD SP,HL

;один байт текстуры распределяем на 
;несколько экранных байтов 
   POP BC;берём сразу 2 текстурных байта
   LD L,table_number1
   LD H,C;текстурный байт - индекс
           ;в таблице
   LDI;из таблицы прямо в экран
   LD L,table_number2
   LDI
   LD H,B;следующий текстурный байт

;несколько текстурных байтов попадают в 
;один экранный 
   POP BC
   LD L,table_numberЗ
   LD H,C
   LD A,(HL);кусочек - из одной таблицы
   LD L,table_numberЧ
   LD H,B
   OR (HL);кусочек - из другой
            ;и объединяем
   LD (DE),A;результат на экран
   INC E;следующий экранный байт

   Скорее всего,такой код почти оптимален.
Однако, если  поставить перед собой задачу
реализовать  такой  же  эффект  в пределах
48 килобайт, то основной  проблемой станет
неприемлемый размер этого кода.Для радика─
льного сокращения кода  я использовал сле─
дующий  трюк, подсказанныйAlone Coder'ом.
   Вместо  того, чтобы в прекалке генерить
целиковую простыню, которая целиком ренде─
рит одну фазу, можно поискать закономерно─
сти  и похожие  кусочки в коде - например,
можно выделить кусочек, который продвигает
текстурный указатель, кусочек,который мап─
пит несколько текстурных байтов в один эк─
ранный и т.д.
   Всего таких кусков получается несколько
килобайт. Для управления последовательнос─
тью  вызова  таких  кусков  и снабжения их
данными (например,номерами таблиц) исполь─
зуется,очевидно,стек. Переход на следующий
кусок -RET , чтение  необходимых данных -
POP .
   Далее идёт пример из48К демы New Wave.
В этом  примереHL указывает на вертикаль─
ный текстурный буфер,BC на экран.

   POP BC;загружаем новую позицию
           ;в экране
   LD A,L
   POP HL
   ADD A,L
   LD L,A;пропускаем 1 или более строк L
           ;в текстурном буфере
           ;(всего в нём 256 строк)
           ;заодно грузим новую
           ;горизонтальную позицию H в нём
   RET;идём на следующий кусок

   POP DE;берём номер таблицы в E
   LD D,(HL);подставляем индекс в этой
            ;таблице из текстурного буфера
   LD A,(DE);лукап в этой таблице
   LD (BC),A;и на экран
   INC C;следующий байт на экране
   INC H;след. байт в текстурном буфере
   RET;следующий кусок кода

   POP DE;всё то же самое,но комбинируем
   LD D,(HL);в одном экранном байте
   INC H    ;несколько текстурных,
   LD A,(DE);пропущенных через несколько
   POP DE   ;разных таблиц
   LD D,(HL)
   INC H
   EX DE,HL
   OR (HL)
   EX DE,HL
   LD (BC),A
   INC C
   RET

   Такой  код, конечно, не  так быстр и не
так элегантен (например,EX DE,HL два раза
- это же звиздец!), но зато сносно помеща─
ется и работает в 48K .

                 Прекалк

   Прекалк  уже был упомянут несколько раз
и не зря:ведь это именно то,что превращает
некий  рандомный  Z80-код с лукапами через
непонятные  таблицы  в  рабочий визуальный
эффект.
   Данная  процедура  довольно затратна по
меркам  Z80: предположительно  она длилась
бы  многие  десятки секунд (если не минут)
на ZX. Мой прекалк  был  написан и работал
на пц.
   Примерный  план  того, что происходит в
прекалке:
   Задаёмся  исходными  данными:  наклоном
текстурной плоскости, положением, шириной,
количеством фаз и т.д.
   При  помощи рейкастинга определяем мап─
пинг текстурных пикселей в экранные.Тут же
можно проверить, например,что видимых тек─
стурных линий меньше, чем 256 минус высота
шрифта - чтобы  не  видеть  процесс печати
новых символов где-то далеко на экране.
   Объединяем пиксели в байты и составляем
таблицы маппинга,выкидываем повторяющиеся.
Проверяем,что всего таблиц не более 256.
   Наконец, генерируем код вывода фаз, или
(для случая48K ) блоки кода и управляющую
таблицу.

                Заключение

   Я полагаю, что  всей вышеизложенной ин─
формации вполне достаточно для того, чтобы 
воспроизвести описанный эффект. Также воз─ 
можны следующие улучшения: 
  - текстурная поверхность может быть вол─
нистой,изогнутой по вертикали и горизонта─ 
ли. Изогнутость может привести к необходи─ 
мости удаления невидимых частей этой пове─ 
рхности. 
  - весь прекалк  можно  выполнить на Z80,
например, упихав весь эффект в 1 кБ. 
  - можно  раскрасить каждую строку текста
в свой цвет. 
  - ну, и  всё  остальное, что  взбредёт в
голову :) 

   Наконец, спасибки:
  -Alone Coderза трюк с фрагментами кода
и управлением при помощи  данных на стеке. 
Ну, и за бессменную работу над Info Guide. 
  -Bolek,ещё разAlone CoderиEllvisза
ценную историческую инфу, касающуюся похо─ 
жих 3D скроллов. 
  -Stein(автору  star wars scroll  в C64
демах Trick and Treat и RGB C64 demo )- за 
вдохновение. 

  Автор :lvd^mhm, lvd.mhm@gmail.com