31 декабря 2017

   3D движок: оптимизация
Alone Coder

   В2016 году я забросил все дела и напи─
сал  новый  ЗD-движок, который я показывал
на осеннем слёте NedoPC , а теперь предла─
гаю вашему вниманию.
   Его  идея - реализовать  подобие  Total
Eclipse , используя  в  основном  8-битные 
вычисления. То  есть, в  частности, делать
глобальные грубые усечения по целым объек─
там, а вершины  клипировать уже на экране.
Идея, как обычно, вертелась у меня в голо─
ве  с1997 года, но понадобилось  написать
два  ЗD-движка  в  обычном  демомейкерском
(бесполезном для практических задач) стиле
"object shower", чтобы постепенно прийти к
реализации.

                  * * *

   Итак, поскольку у нас есть очень крутой
прообраз - 3D Construction Kit,  нашим ос─
новным  козырем  должна  быть  скорость (а
через неё - например, площадь экрана).

   Важно отметить, что уже в начале разра─
ботки  быстрой программы надо обладать ин─
формацией, сколько  примерно проходов каж─
дого  цикла в среднем требуется. Иначе оп─
тимизировать   можно  только  локально,  а
здесь речь о комплексной оптимизации - не─
большой проигрыш где-то оборачивается зна─
чительным  выигрышем в другом месте. Когда
программа  уже готова, определить важность
каждой  процедуры проще. Когда я оптимизи─
ровал  ZXUnRar и JPEG Viewer (а я их опти─
мизировал в несколько раз каждый), я выра─
ботал такой метод: во все интересующие ме─
ста  вставляю  счётчики проходов и смотрю,
сколько  раз  оно  выполнилось. У  Screw'а
есть версия Unreal Speccy, позволяющая ав─
томатизировать такие вещи,но я пользовался
простыми  вставками кода. Или другой метод
- добавляю  в каком-нибудь месте известные
паузы и смотрю, насколько подскочило число
тактов...
   Когда  я  писал  новый  3D  движок, я в
общем  уже  знал, например, что заполнение
пикселей  занимает  меньше  половины всего
времени для сложных сцен. Поэтому основное
ускорение  коснулось расчётов и обвязок. И
разумеется, сначала был сделан минимальный
работающий  скелет (по модели наDelphi ),
на котором постепенно заменялись куски.

   Ещё  раз  обращаю ваше внимание: это не
обычный ЗD-движок для дем, где перед носом
крутится какой-то объект. Это движок, реа─
лизующий  "погружение"  в  сцену. То, чего
почти  не  было в спектрумовских демах. То
есть  встают  вопросы  повышенной точности
расчётов,клипирования,хранения и обработки
сцены из многих объектов и нескольких сис─
тем координат.
   Изначальные требования к движку такие:
  - объект  в сцене  не  один, их десятки.
И более половины из них не видно. 
  - некоторые  объекты одинаковые (и копии
не должны отнимать много ресурсов),а неко─ 
торые - уникальные. 
  - каждый объект имеет свой угол поворота
как минимум вокруг вертикальной оси (важно 
для врагов и оружия). 
  - размеры рабочей зоны  должны позволить
реализовать  игровую  комнату. Больше пока 
не надо. 
  - объекты  могут быть проволочные, зали─
тые, текстурные, смешанные - в  будущем  с 
текстурами и шейдерами, и это должно наст─ 
раиваться. 
  - движок  должен работать в том числе на
оригинальном  48K, при  этом  должна  быть 
возможность подключать дополнительные фичи 
для 128K и ATM Turbo 2+. 
  - работать всё должно в разы быстрее,чем
движок в Total Eclipse. 

   Общий  дизайн  движка предполагался та─
кой:
  - с  полной  точностью  вращаются только
объекты целиком.Вершины объектов вращаются 
уже в восьми битах. Проблема только в пер─ 
спективной коррекции. 
  - имеется   линейка  масштабов  проекций
объектов, где соседние масштабы отличаются 
в2раза. Это позволяет крутить вершины во 
всех  масштабах  быстрым 8-битным кодом, а 
заодно  и реализовать быстрый 8-битный код 
проверки видимости полигона. 
  - в пространстве клипируются только объ─
екты целиком.Полигоны усекаются уже в пло─ 
скости экрана.Существует максимальный раз─ 
мер  объекта - "единичный куб"(бЗxбЗxбЗ).
Если объект будет больше, то встанет сразу 
несколько проблем: он будет резко исчезать 
на краях экрана; не получится крутить вер─ 
шины  в диапазоне +-31(если  не  вводить 
дополнительное  масштабирование уже не то─ 
лько для проекций объектов, но и для самих 
объектов); появятся  полигоны размером бо─ 
льше экрана, которые не поддерживает отри─ 
совщик  из  NedoDemo  (потомок знаменитого 
отрисовщика из Spectrum Expert #2 ). 
  - плоскость  расчётов для вершин ограни─
чена  двумя экранами в ширину (256точек) 
и столько же в высоту. Всё,что не попало в 
два экрана, "сплющивается" к границам этой 
области.Видно,что разрешение геометрии при 
этом составляет2пикселя, но при отрисов─ 
ке  это не должно быть видно - линии и по─ 
лигоны между этими точками рисуются с пол─ 
ной  точностью. В чанках  это тем более не 
увидеть. Но  надо  следить за погрешностью 
вычислений, иначе  точки  будут прыгать во 
все  стороны  на 2пикселя и более. Из-за 
этого  пришлось  отказаться  от нескольких 
оригинальных методов перспективной коррек─ 
ции - пара вариантов через поправочную та─ 
блицу и пара вариантов через логарифм. 
  - все параметры экрана настраиваются.Вы─
вод на экран - отдельный модуль. 

                  * * *

   Начнём  с  метода  оптимизации  сложных
расчётов, который я отработал за последнюю
пару лет. Возьмём  какой-то  один  расчёт,
роль которого в общей программе мы знаем.

   Сначала пишем схему расчётов. Например:
;# посчитать то-то 
;# посчитать сё-то 
;# отрисовка такая-то 
   Это  будут  заголовки  этапов, играющие
роль комментариев.
   Там,  где  написаны  формулы, указываем
необходимую  точность  расчётов. Например:
dX12=(X2-X1)/H12 (+-6.0 / 6.0 = +-6.8).
   Это  значит, что  мы 6  бит  со знаком
делим на6 бит без знака,получаем знаковый
результат  с  фиксированной запятой, где6
бит до запятой и8 бит после. От необходи─
мой  точности  зависят применяемые методы.
Широкие  умножения-деления, которые в изо─
билии разбросаны в прессе, обычно не нужны
- достаточно  грубых  расчётов  по таблице
или  за 5-6 проходов цикла. Бывает и так,
что  вместо  умножения выгоднее сложение в
цикле - настолько  малые множители реально
используются (так было  в обвязке полигона
в The Link ). К сожалению, нужная точность
часто выясняется по результатам экспериме─
нтов, когда  уже всё написано. Например, в
Wolf 48 сначала была 16-битная математика, 
потом она заменена на 8-битную. Лучше сде─
лать запас по точности, но иметь под рукой
и  радикально  быстрый метод, под точность
которого  можно  будет подогнать эффект (и
так бывает).

   Когда  выбраны методы расчёта, смотрим,
сколько в каком этапе используется регист─
ров  и сколько надо  в это время проносить
регистров для следующих этапов. Например:
;# генератор стека нижних сканлайнов 
;(8 регистров), проносим 7 (U1[1],V1[1], 
;dU13[2],dV13[2],Y) + 2 (dX12[2]) 
;=9 регистров - хватает впритык (17) 
   У  меня  за  многие годы заготовлено до
десятка  вариантов кода под типовые задачи
(сканлайн, иннерлуп tmap, умножение, деле─
ние и т.п.), поэтому я знаю,сколько регис─
тров мне надо на ключевых этапах.
   Если  регистров  на  каком-то  этапе не
хватает,меняем схему расчётов или заменяем
проносимые регистры на память или стек.

   Только  после  этого  пишем между этими
комментариями  код. Код будет с вопросите─
льными знаками вместо регистров: например,
с командами  типаld a,?1 . Не обязательно
реализовывать  все  этапы сразу, главное -
последние этапы.
   Каждый  вставленный фрагмент содержит в
конце  комментарий с числом тактов. Обычно
я беру фрагменты из накопленной коллекции,
там  уже есть это число. Если даже код но─
вый, то  счёт  четвёрками и семёрками (или
четвёрками с последующим вычитанием едини─
чек) занимает недолго.

   Потом  с конца программы начинаем опре─
делять,какие конкретно регистры требуются:
  - проставляем регистры в последнем этапе
  - далее  перед  этим  этапом расписываем
требуемое состояние регистров на входе:
;c=параметр такой-то 
;hl'=параметр сякой-то 
;lx=параметр этакий-то 
и т.п.
  - в этапе, который стоит перед ним,заме─
няем  имеющиеся вопросительные знаки наld
a,c?1 и т.п. и по необходимости пишем свя─
зку  для  переброски регистров между этими
двумя  этапами. Иногда  хвост одного этапа
отрезается  вместе  с  головой следующего,
так  что  получается отрицательный оверхед
на связку между этапами!
  - если  появляются проблематичные затыки
или неоптимальности (для этого даже не на─
до заменять все вопросительные знаки, обы─
чно  видно раньше), то пытаемся переписать
последний этап с другими регистрами. Иначе
продолжаем снизу вверх в той же последова─
тельности:проставляем регистры,расписываем
состояние регистров, заменяем вопроситель─
ные знаки в предыдущем этапе и пишем связ─
ку.
   Неоптимальности - это, например, бесто─
лковое  перекладывание чисел из регистра в
регистр, локальные PUSH-POP или локальные
патчи, команда NEG (обычно её можно заме─
нить  другим  порядком  сложений-вычитаний
или сменой таблицы), повторное использова─
ние числовых констант и др.
   Я их выделяю в исходнике сдвигом строки
вправо, чтобы  можно  было быстро находить
глазами и оценить, насколько код неоптима─
лен.

                  * * *

   К сожалению, при отладке иногда выясня─
ется, что  на  этапе планирования допущена
ошибка. Тогда приходится городить костыли,
которые  нарушают  оптимальность.  Но  при
следующей реализации той же задачи уже мо─
жно будет учесть эту ошибку.
   В  этом  движке учтено несколько ошибок
предшественников. Кроме  самого  подхода к
клипированию, посмотрите, например:
  - как  хранится  экран (его расположение
заточено под удобное клипирование); 
  - как  идёт  вращение объектов и их вер─
шин с компенсацией  перспективного искаже─ 
ния (раньше  для этого приходилось вращать 
каждую вершину с полной точностью!); 
  - как  реализована  сортировка (линейная
pigeon-hole sort с минимальной переброской 
данных и компромиссным количеством уровней 
Z); 
  - как  повторяющиеся  объекты  прописаны
прямо кодом... 
   ...но  понадобится новая итерация пере─
писывания, чтобы  разрешить объекты разме─
ром  больше единичного куба. Впрочем, игры
уже  делать  можно. Надо  только привязать
движок к NedoLang'у :)

   Демонстрационная программа лежит в при─
ложении, а её исходники в архиве. Управле─
ние  простое - стрелки5678 двигают камеру
по координатам,а мышь вращает её.КнопкойF
можно  выключить пол и потолок.0 - пауза.
Проверки  за выход из активной зоны нет, а
на работу вне её движок совершенно не рас─
считан.
   Да, это пока не Total Eclipse :)

 А
 Б
 В
 Г
 Д
 Е
 Ж
 З
 И
 Й
 К
 Л
 М
 Н
 О
 П
 Р
 С
 Т
 У
 Ф
 Х
 Ц
 Ч

   Размер активной зоны #280(x) * #280(y)
* #100 (z). Такой  размер  сейчас  задан в
floor.asm для  отображения пола и потолка.
Но дело не только в поле и потолке - глав─
ное, что при таких размерах не будет пере─
полнения  расчётов. Можно только чуть уве─
личить  высоту (z). Активная  зона  может
располагаться  в любом  месте пространства
XYZ, потому что мы работаем с координатами
относительно камеры.
   Для сравнения, в  движке  Total Eclipse
размер  зоны -8192 * 4096 * 8192, но  при
этом  объекты можно размещать только с ша─
гом в128 единиц (по оси y - с шагом 64 ):
https://en.wikipedia.org/wiki/Freescape
   Максимальный  размер  объекта #3f  (от
края  до края), причём на больших объектах
уже  возникают  искажения, если  подойти к
ним близко. Точность расчётов вершин соот─
ветствует+-1 единице, но полигон размером
в 2  единицы  вы  рискуете не увидеть при
8-битном контроле видимости(VISIBILITY16=
=0).

   Объекты описаны вЗdmodel.asm . Объекты
могут  содержать  полигоны и линии. Каждый
объект  привязан  к  процедуре  вращения -
проверки    видимости - рисования   (через
drawedges.asm и/илиdrawfaces.asm ), зато─ 
ченной именно на объекты его класса. Кроме
процедур   с  уже  готовыми  объектами  (в
rotmodel.asm ), имеется  и "универсальная"
ROTVB  (вrotate.asm ), которой достаточно
передать списки вершин, рёбер и полигонов.
Только  координаты вершин у неё могут быть
только0 или +-31... Впрочем, можно соста─
вить и  совсем  универсальную. Она будет в
разы  медленнее, чем процедура под готовый
объект. Предполагалось генерировать проце─
дуры под объекты.

   Вrotate.asm  есть и процедура перспек─
тивной  коррекции вершин объектаdiv8x. На
входе она имеет повёрнутые координаты вер─
шин, координаты  объекта  на  экране и его
зум (инлайн патч), а возвращает уже экран─
ные координаты.

  sortobj.asm - вы думаете, это процедура
сортировки  по  глубине?  :) На самом деле
отдельной  сортировки в движке вообще нет.
Она  интегрирована наполовину в добавлялку
объекта в список на вывод(DOOBJ), наполо─
вину в вывод списка объектов(sortobjpop).
И обе  эти процедуры  лежат в этом модуле,
вместе с проверкой попадания объекта в эк─
ран  и  выбором  нужного зума. Разумеется,
выводятся  объекты не в том порядке, в ко─
тором  добавляются :) Причём все процедуры
обработки объектов (см. выше) заканчивают─
ся  командойjp sortobjnext, чтобы не тра─
тить стек. Используется самый быстрый воз─
можный  метод сортировки для ограниченного
диапазона глубин. Он называется Pigeonhole
sort (вырожденный случай  Radix sort ). Он 
работает  линейно  от  числа  объектов, то
естьO(n), причём с совсем маленьким коэф─
фициентом. Да, так бывает! :) Объекты, со─
ответствующие  каждой  глубине (сейчас128
глубин:SORTLEVELS=128) попадают в отдель─
ный список. Списки пока чистятся небольшим
куском  кода  в  начале mainloop. В конце
концов код очистки тоже будет переброшен в
этот модуль.

   Сама  сцена  сейчас описана непосредст─
венно кодом вmain.asm . Этот код сгенери─
ровать  несложно, перевести в таблицы тоже
нет проблем.

  rotobj.asm - процедура  вращения с пол─
ной точностью, нужна для определения поло─
жения  объекта  на  экране. Вызывается для
всех объектов, причём для половины невиди─
мых объектов предусмотрен выход из середи─
ны. Точнее, это  даже не процедура, а мак─
росADDCAM_ROT.

  rotmatrix.asm  -  процедура составления
матрицы  вращения  вершин объекта и таблиц
"засечек"  для  быстрого пересчёта вершин.
Для каждой комбинации осей строится31 за─
сечка, не считая нуля, что с учётом знаков
как раз соответствует максимальному разме─
ру объекта#3f (см. выше).
   Это реально очень быстрая вращалка, со─
ставленная  по мотивам вращалки LVD в "во─
лосатом   бублике"  (демо  Mission  Highly
Improbable ). Можно  даже отключить  крен, 
чтобы  было  вращение только по двум осям.
Но вызывается  эта вращалка  только тогда,
когда  встречается  объект, повёрнутый  не
так, как предыдущие.

   Экранный  буфер  хранится  по столбцам.
Сейчас  он для скорости выводится чересст─
рочно, но  можно  допилить до полноценного
полноэкранного  вывода.  Процедура  вывода
буфера на экран лежит вdisplay.asm. Можно
её  настроить,  например, на  motion  blur
(NOISECLS=0; 0=очистка, 1=шум, 2=пропуск
байтов ). 
   Движок можно легко переделать на другой
формат  экрана  (чанки  или цвет на точку)
заменой  модулей drawedges,  drawfaces  и
display. Предполагалось добавить как мини─
мум  чанковый движок из New View 48K с не─
которым   допиливанием.  Смотрите  каталог
mars с разными настройками этого чанкового
движка - цвет/чб, разные текстуры, размеры
экрана, размеры чанка и пара фильтров.
   Все нужные таблицы  считаются на Бейси─
ке. Исходники тоже прилагаются.

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

   Если кто-то заинтересуется практическим
использованием  движка, пишите! Допилим... 
Можно  будет параллельно публиковать серию 
статей про новости в начинке движка, как в 
коммодоровской  газете C Hacking. А пока в 
следующей  части  обрисуем некоторые куски 
кода, которые есть сейчас... но предупреж─ 
даю - текст будет не для слабонервных :)