Doom решил задачу порядка отрисовки чужой статьёй 1980 года — и заплатил за это архитектурой уровней

Задача, которую надо было решить к декабрю 1993 года, звучит скучно и определяет всё остальное: в каком порядке рисовать стены, чтобы ближние закрывали дальние.

Очевидный способ — буфер глубины, где для каждой точки экрана хранится расстояние. На машинах того времени это означало лишний мегабайт памяти и сравнение на каждый выведенный пиксель; ни того, ни другого не было. Второй способ — алгоритм художника: сортировать многоугольники по дальности и рисовать от дальних к ближним. Он требует сортировки каждый кадр, а главное — не всегда работает: три стены могут перекрывать друг друга по кругу, и правильного порядка для них просто не существует.

Wolfenstein 3D 1992 года обошёл проблему целиком: мир был сеткой из одинаковых кубов, и движок пускал по лучу на каждый столбец экрана. У сетки порядок тривиален. Но в сетке нельзя поставить стену под углом.

Что взял Кармак

Уровни Doom — произвольные многоугольники под произвольными углами. Для них Кармак применил двоичное разбиение пространства, BSP, описанное в 1980 году в работе Генри Фукса, Цви Кедема и Брюса Нейлора.

Идея объясняется в три предложения. Берём стену и продлеваем её линию до бесконечности — она делит уровень на «спереди» и «сзади». Повторяем это рекурсивно для каждой половины, разрезая пополам те стены, что попали на линию. В листьях дерева остаются выпуклые области, внутри которых ничто не может загородить ничто.

Дальше во время игры сортировка не нужна вовсе. Для любого положения камеры движок спускается по дереву, на каждом узле выбирая сначала ту сторону, где стоит игрок. Порядок получается верным по построению.

Кармак не ускорил сортировку. Он вынес её из времени игры во время компиляции карты.

Чем оплачена скорость

Дерево строится один раз, когда уровень собирают редактором, и это занимает от секунд до минут. Оно намертво описывает геометрию.

Отсюда следует то, за что Doom узнают с одного взгляда. Дверь может подниматься, пол может опускаться, платформа может ехать вверх — всё это меняет высоты, но не план. Ни одна стена в Doom не поворачивается и не сдвигается по горизонтали, потому что от этого дерево стало бы недействительным, а перестроить его на лету нельзя. Архитектурный стиль игры — статичный план с движущимися по вертикали полами и дверями — не художественное решение, а прямое следствие структуры данных.

К этому движок добавляет вторую экономию: он идёт по дереву от ближнего к дальнему и ведёт список уже закрытых столбцов экрана. Как только столбец закрыт, всё, что за ним, пропускается без обработки. Doom почти не перерисовывает одну точку дважды — редкость для того времени.

Общее правило

Doom вышел 10 декабря 1993 года и стал первым массовым примером обмена, который с тех пор определяет графику: перенести работу из времени выполнения во время сборки. Дальше по этой линии идут запечённые карты освещения, предрасчёт видимости в Quake, запечённое глобальное освещение и сегодняшние иерархии ограничивающих объёмов для трассировки лучей — всё это одна и та же сделка.

Поэтому у любого красивого эффекта полезно спрашивать не «сколько это стоит кадру», а «что было посчитано до того, как игрок нажал старт». И следом второй вопрос, ответ на который обычно и есть настоящая цена: что из-за этого теперь нельзя двигать.