От экрана дизайнера к экрану игрока
Карты разрабатывались дизайнером уровней в 2D с помощью редактора Doom Editor (DoomED). LINEDEFS описывали замкнутые секторы (SECTORS в исходном коде), а третье измерение (высота) указывалась посекторно. Первый уровень Doom E1M1 выглядит так:
После завершения работы над картой она нарезается методом двоичного разбиения пространства (Binary Space Partitioning, BSP). LINEDEF рекурсивно выбирались и их плоскости превращались в секущие плоскости. То есть LINEDEF разрезались на сегменты (SEGS) до тех пор, пока не оставались только выпуклые подсектора (SSECTOR в коде).
Интересный факт: И DoomED, и iBSP писались на… Objective-C на рабочих станциях NextStep. Пятнадцать лет спустя тот же язык почти в той же операционной системе выполняет игру на мобильном устройстве! [прим. пер.: в 2010 году Doom вышел на iPhone] Я немного поработал веб-археологом и мне удалось найти исходный код idbsp. На него стоит посмотреть.
Ниже представлен пример рекурсивного разделения карты первого уровня.
Уровень рекурсии 1
Синим отмечена выбранная стена, превращённая в секущую плоскость (красная). Секущая плоскость выбиралась таким образом, чтобы сбалансировать BSP-дерево, а также для ограничения количества создаваемых SEGS. Зелёные ограничивающие прямоугольники использовались позже для отбрасывания целых фрагментов карты.
Уровень рекурсии 2 (только для правого подпространства)
В результате секторы SECTORS разделялись на выпуклые подсекторы (обозначаемые как SSECTORS), а LINEDEFS разрезались на сегменты (обозначаемые как SEGS):
Процесс работы в целом
Вот как выглядит главный метод рендеринга (R_RenderPlayerView):
void R_RenderPlayerView (player_t* player)
{
[..]
R_RenderBSPNode (numnodes-1);
R_DrawPlanes ();
R_DrawMasked ();
}Здесь выполняется четыре операции:
R_RenderBSPNode: все подсекторы на карте сортируются с помощью BSP-дерева. Большие фрагменты отбрасываются с помощью ограничивающих прямоугольников (показаны на предыдущем изображении зелёным).R_RenderBSPNode: видимые сегменты SEGS проецируются на экран через таблицу поиска и обрезаются с помощью массива отсечения. Стены рисуются как столбцы пикселей. Размер столбца определяется по расстоянию от точки обзора игрока, позиция Y столбца через высоту связана с игроком. Основания и вершины стен создают плоскости visplanes. Эти структуры используются для рендеринга пола и потолка (они называются в коде flats).R_DrawPlanes: Плоскости visplanes преобразуются из столбцов пикселей в строки пикселей и рендерятся на экране.R_DrawMasked: Выполняется рендеринг «предметов» (врагов, объектов и прозрачных стен).
Сортировка двоичного разбиения пространства
Два примера с E1M1 (первой картой Doom) и BSP выглядят следующим образом:
//Начало системы координат находится в левом нижнем углу
// Уравнение плоскости ax + by + c = 0 с
// единичным вектором нормали = (a,b)
// Корневая плоскость (разделяющая карту на зоны A и B):
normal = (-1,0) c = 3500
// Плоскость A (разделяющая зону A на зоны A1 и A2):
normal = (1,0) c = -2500
// Плоскость B (разделяющая зону B на зоны B1 и B2):
normal = (-0.24,0.94) c = -650
// Подстановка координаты любой точки (x,y) в
// уравнение плоскости даёт нам расстояние от этой плоскости.
Обход BSP-дерева всегда начинается с корневого узла с сортировкой обоих подпространств. Рекурсия выполняется для обоих дочерних узлов.
Пример 1: Игрок (зелёная точка) смотрит сквозь окно из точки p=(2300,1900):
// Позиция игрока = ( 2300, 1900 )
// R_RenderBSPNode выполняется для секущей плоскости AB (-x + 3500 = 0):
-2300 + 3500 = 1200
Результат положителен, значит, ближайшее подпространство находится ПЕРЕД секущей плоскостью. (A ближе, чем B).
// Затем R_RenderBSPNode рекурсивно выполняется для двух дочерних узлов корневого узла: секущих плоскостей A1/A2 и B1/B2.
// R_RenderBSPNode выполняется для A1/A2 (x - 2500 = 0):
2300 - 2500 = -200
Результат отрицателен, поэтому ближайшее подпространство находится СЗАДИ от секущей плоскости. (A1 ближе, чем A2).
// R_RenderBSPNode выполняется для B1/B2 (-0.24x +0.97y - 650 = 0):
-0.24 * 2300 + 0.97 * 1900- 650 = 641
Результат положителен, поэтому ближайшее подпространство находится ПЕРЕД секущей плоскостью. (B1 ближе, чем B2).
Результат: зоны отсортированы от самой близкой до самой далёкой:
{ A1, A2, B1, B2 }Пример 2: Игрок (зелёная точка) смотрит с секретного балкона в точке p=(5040, 2400):
// Позиция игрока = ( 5040, 2400 )
// R_RenderBSPNode выполняется для секущей плоскости AB (-x + 3500 = 0):
-5040 + 3500 = -1540
Результат отрицателен, поэтому ближайшее подпространство находится СЗАДИ от секущей плоскости. (B ближе, чем A).
// Затем R_RenderBSPNode рекурсивно выполняется для двух дочерних узлов корневого узла: секущих плоскостей A1/A2 и B1/B2.
// R_RenderBSPNode выполняется для B1/B2 (-0.24x +0.97y - 650 = 0):
-0.24 * 5040 + 0.97 * 2400 - 650 = 468
Результат положителен, поэтому ближайшее подпространство находится ПЕРЕД секущей плоскостью. (B1 ближе, чем B2).
// R_RenderBSPNode выполняется для A1/A2 (x - 2500 = 0):
5040 - 2500 = 2540
Результат положителен, поэтому ближайшее подпространство находится ПЕРЕД секущей плоскостью. (A2 ближе, чем A1).
Результат: зоны отсортированы от самой близкой до самой далёкой:
{ B1, B2, A2, A1 }BSP-деревья позволили сортировать SEGS из любой точки карты с постоянной скоростью, вне зависимости от позиции игрока. Ценой за это стали одна операция умножения и одна операция суммирования для каждой плоскости. Кроме того, благодаря тестированию ограничивающими прямоугольниками отбрасываются крупные части карты.
Примечание: Не сразу очевидно, но BSP сортирует все сегменты SEGS вокруг игрока, даже те, на которые он не смотрит. При использовании BSP необходимо применение отсечения по пирамиде видимости.
Стены
При сортировке BSP стен (SEGS) с ближней до дальней, рендерятся только ближайшие 256 стен. Две вершины каждого SEGS преобразуются в два угла (относительно позиции игрока).
Примечание: В 1993 году только самые мощные машины 486DX имели FPU (сопроцессор для чисел с плавающей точкой), поэтому движок Doom вычислял все углы с помощью двоичного измерения углов (Binary Angular Measurement, BAM), работавшего только с числами int, формат float использовался редко. По той же причине точность, превышающая точность целых чисел, достигалась с помощью fixed_t, двоичного формата 16.16 с фиксированной запятой (подробнее об этом можно почитать здесь и здесь).
После преобразования в углы координаты X экранного пространства получались с помощью таблиц поиска (viewangletox). Поскольку BAM выполнялись в int, углы сначала масштабировались с 32 до 13 бит с помощью 19-битного смещения вправо, чтобы уместиться в таблицу поиска размером 8 КБ.
Затем стены обрезались согласно массиву отсечения (solidsegs. В некоторых статьях о движке Doom упоминается связный список, но не похоже на то, что он использовался). После обрезки оставшееся пространство интерполировалось и отрисовывалось как столбцы пикселей: высота и координата Y столбца пикселей были основаны на высоте сектора SEGS и расстоянии от точки обзора игрока, соответственно.
Примечание об отсечении поверхностей: Отсечение невидимых поверхностей выполнялось с помощью angle2-angle1 > 180 . Рендерились только стены, находящиеся в области видимости.
Примечание: Не все стены состояли из единых текстур. У стен могла быть нижняя текстура, верхняя текстура и средняя текстура (которая могла быть прозрачной или полупрозрачной). Как заметно на видео ниже, это было удобно для симулирования окон: «окно» на самом деле является сектором с высоким полом и отсутствующей средней текстурой.
Интересный факт: Поскольку стены рендерились как вертикальные колонны, текстуры стен хранились в памяти повёрнутыми на 90 градусов влево. Этот трюк позволял полностью использовать функцию предварительного кэширования центрального процессора: процесс считывания тексела стены из ОЗУ также предварительно заполнял кэш ЦП восемью соседними текселами с каждой стороны. Поскольку последующие данные чтения уже находились в кэше ОЗУ, достигалось значительное снижение латентности считывания. Подробнее о предварительном кэшировании и выравнивании данных в памяти можно почитать в книге «The Art of Assembly Language programming» (раздел 3.2.4 Cache Memory).
Плоские поверхности (пол и потолок), или печально известные visplanes
При отрисовке столбцов стен верхние и нижние координаты экранного пространства использовались для генерирования «visplanes», областей в экранном пространстве (не обязательно непрерывных горизонтально). Вот как объявляется visplane_t в движке Doom.
//
// Что же такое visplane?
//
typedef struct
{
fixed_t height;
int picnum;
int lightlevel;
int minx;
int maxx;
byte top[SCREENWIDTH];
byte bottom[SCREENWIDTH];
} visplane_t;
Первая часть структуры хранит информацию о «материале», (height, picnum, lightlevel). Четыре последних члена определяют покрываемую зону экранного пространства.
Если два подсектора имеют одинаковый материал (высоту, текстуру и уровень освещённости), то движок Doom пытался слить их вместе, но из-за ограничений структуры visplante_t это было не всегда возможно.
Для всей ширины экрана visplane может хранить местоположение столбца пикселей (поскольку visplanes получаются проецированием стен на экран, они создаются как столбцы пикселей).
Вот три основные visplanes начального экрана:
Зелёная плоскость особенно интересна: она демонстрирует, что visplane_t может хранить прерывистые (но только в горизонтальном направлении) области. Поскольку столбец непрерывен, visplane может хранить его. Это ограничение проявляется в движке: некоторые подсекторы можно слить и рендерить с помощью одной visplane, но если между ними есть что-нибудь по вертикали, то слияние невозможно.
Вот скриншот и соответствующее видео, показывающие фрагментацию visplane.
Интересный факт: Жёстко заданный предел visplanes (MAXVISPLANES 128) был большой головной болью для моддеров, потому что игра вываливалась и возвращалась в DOS. Могут возникнуть две проблемы:
"R_FindPlane: no more visplanes": Общее количество различных материалов visplanes (высота, текстура и уровень освещённости) больше 128.R_DrawPlanes: visplane overflow (%i): при фрагментации visplanes их количество превысило 128.
Зачем ограничиваться числом 128? Два этапа конвейера рендеринга требовали выполнения поиска по списку visplanes (с помощью R_FindPlane). Поиск был линейным, и, возможно, для чисел больше 128 оказался слишком затратным. Ли Киллоу (Lee Killough) позже расширил этот предел, заменив линейный поиск реализацией хеш-таблицы с цепочками.
Предметы и прозрачные стены
После того, как все сплошные стены и стены с «прозрачной средней текстурой», а также поверхности потолков и полов будут отрендерены, остаются только «предметы»: враги, бочки, боеприпасы и полупрозрачные стены. Они рендерятся от самых дальних к самым ближним, но не проецируются в экранное пространство с помощью таблицы поиска стен. Процесс рендеринга выполняется вычислениями двоичных чисел 16.16 с фиксированной запятой.
Примечание: В этом видео показан один из наихудших сценариев, когда некоторые пиксели приходится перерисовывать три раза.
Профайлинг
Загрузка Chocolate Doom в Instruments под Mac OS X позволила выполнить кое-какой профайлинг:
Похоже, что порт [на iPhone] довольно точно соответствует «ванильному» Doom: бóльшую часть времени выполняется отрисовка стен (R_DrawColumn), потолка/пола (R_DrawSpan) и предметов (R_DrawMaskedColumn ). Кроме отрисовки я заметил высокие затраты ресурсов на интерполяцию стен (R_RenderSegLoop) и преобразование visplane из столбцов в строки пикселей (R_MakeSpans). Затем, наконец, дело доходит до AI (R_MobjThinker) и обход BSP-дерева (R_RenderBSPNode).
С помощью инвертированного дерева вызовов можно увидеть, что бóльшая часть работы и в самом деле заключается в обходе BSP-дерева, рендеринге стен и генерировании visplanes: R_RenderBSPNode (второй столбец — процент потраченного времени).
Всё вместе
И вот, наконец, видео генерирования легендарного первого экрана, в котором можно увидеть по порядку:
- Стены как строки пикселей, с ближних до дальних
- Плоские поверхности как строки пикселей, с ближних до дальних
- Предметы с дальних до ближних.
Интересные факты
- Поскольку Doom разрабатывался на системе NeXTSTEP с линейной моделью виртуальной памяти, id Software решила отказаться от EMS и XMS, которые использовались в большинстве игр того времени. Вместо этого разработчики использовали DOS/4G, расширитель памяти, позволявший ПО получать доступ к ОЗУ в защищенном режиме в операционной системе с реальным режимом (DOS).
- Рабочая станция NexT была настолько мощной, что оказалась способна выполнять редактор, игру и отладчик одновременно. Когда игра стала достаточно стабильной, код отправили по сети в PC, где он был скомпилирован под DOS/x86 компилятором Watcom. Благодаря DOS/4G код выполнялся в одинаковой модели памяти и на PC, и на NeXT.
- Интересное видео, дополняющее книгу «Masters of Doom»:
- Многие подробности можно изучить на сайтах Джона Ромеро (John Romero) rome.ro и planetromero.com.
Рекомендуемое чтение
- Оригинальный исходный код, выпущенный в 1997 году, удобен для чтения, но в нём нет или почти нет комментариев, он не компилируется, в нём отсутствует исходный код звуковой подсистемы (из-за проблем с лицензированием).
- Chocolate Doom: О, ДА! Это просто потрясающий порт, он основан на SDL и с brio скомпилируется практически на любой платформе. Именно этот порт я хакнул, чтобы генерировать видео для статьи.
- Книга «Graphics Programming Black Book» Майкла Абраша. Помогает понять BSP-деревья и является отличным источником вдохновения. Этот парень может даже заставить вас полюбить ассемблер.
- Masters of Doom: история id Software со множеством подробностей о создании Doom
Автор: PatientZero
