← Модуль 3/Quake: настоящий 3D
EN
Модуль 3 · 3D-революция (1993–1999)

Quake: настоящий 3D — BSP, PVS и запечённый свет

Через три года после Doom id перешла к настоящему 3D: произвольная геометрия, свобода обзора, перспективно-корректные текстуры. Цена честности — её платят заранее: видимость и свет печёт компилятор карты, рантайму остаётся дёшево рисовать.
глубокий~22 мин
Суть за 30 секунд
Doom был 2.5D: 2D-BSP по линиям, сектора с высотами, нельзя ни комнату над комнатой, ни смотреть вверх. Quake (1996) — настоящий 3D: произвольные полигоны, свободный обзор (наклон камеры вверх-вниз), перспективно-корректные текстуры. Чтобы это летало на Pentium, id вынесла дорогое в офлайн-компиляцию карты тремя инструментами: QBSP строит 3D-BSP и порталы, VIS считает PVS (для каждой выпуклой ячейки — битовый список «кого отсюда вообще видно»), LIGHT печёт статический свет в lightmap’ы. В рантайме: из ячейки камеры берём её PVS → рисуем только потенциально видимое; перспективное деление 1/z прячем под целочисленную работу (раз в 16 пикселей). Честный 3D, оплаченный вперёд.

Настоящий 3D против 2.5D Doom

Doom и Quake оба стоят на BSP — но в разном числе измерений, и это меняет всё.

—Doom (1993)Quake (1996)
BSP2D: секущие линии в плане3D: секущие плоскости в объёме
Геометриясектора с высотой пола/потолкапроизвольные выпуклые браши
Комната над комнатойнельзяможно
Обзорнет наклона камеры (автоприцел по вертикали)свободный обзор вверх/вниз + перемещение в 3D
Текстурывертикальный стретч, без перспективной коррекцииперспективно-корректные UV
Светяркость на секторзапечённые lightmap’ы (текстура света)

Структура данных та же — дерево двоичного разбиения пространства — но в 3D она режет объём произвольными плоскостями на выпуклые ячейки (листья дерева). Одна комната обычно дробится на несколько выпуклых ячеек. BSP здесь работает на три фронта: порядок отрисовки, коллизия и хранилище видимости (PVS).

PVS — предвычисленная видимость

Главная идея Quake: видимость не считают в кадре, её компилируют заранее. QBSP между смежными ячейками автоматически расставляет порталы — «окна», через которые из одной ячейки видно другую. Эти порталы живут только во время компиляции. Инструмент VIS по ним прогоняет алгоритм видимости из области (Сет Теллер, 1992; Кармак реализовал в 1996) и для каждой ячейки сохраняет битовый вектор: какие ячейки потенциально видны хоть из какой-то её точки. Это и есть PVS — Potentially Visible Set (плюс аналог PAS для звука).

В рантайме движок берёт лист, где сейчас камера, читает его PVS-битмаску и рисует только отмеченные ячейки. Вместо обхода всей карты — один lookup: из битвектора длиной в число листьев карты (сотни–тысячи) у тесной ячейки взведены единицы–десятки бит. Дальше идёт обычный frustum cull (что в поле зрения) и BSP-порядок.

A · камера B C Dне в PVS стена PVS(A) = {A, B, C}

Запечённый свет: lightmap’ы

Инструмент LIGHT в офлайне кастует лучи от всех источников карты и записывает результат в lightmap — отдельную низкоразрешающую текстуру света (≈ один сэмпл на крупный блок поверхности, lightmap’ы складываются в атласы вроде 128×128 на много поверхностей). В рантайме пиксель = базовая_текстура × lightmap. Это развязывает детализацию и освещение: геометрия и узор — в hi-res текстуре, свет — в lo-res lightmap’е.

Чтобы перемножение не повторять каждый кадр, Quake кэширует результат в surface cache: один раз собрал освещённую поверхность — переиспользуешь, пока она в кадре. Флаг -extra у LIGHT берёт по 4 сэмпла на тексель и усредняет — мягче края теней. Цена запекания — свет статичен: подвинуть лампу или стену нельзя (несколько динамических огней — вспышки выстрелов — накладывались отдельным дешёвым слоем).

Перспективно-корректные текстуры и трюк с делением

Честный 3D требует перспективной коррекции: экранно-линейная интерполяция u,v вдоль уходящего вглубь полигона искривляет текстуру. Корректно — интерполировать u/z и 1/z (они линейны в экранных координатах), а потом делить:

u= интерп(u/z) интерп(1/z)

Проблема: деление на Pentium (FDIV) — до ~39 тактов, на каждый пиксель неподъёмно. Решение Майкла Абраша: точные u,v считать раз в 16 пикселей, между ними — линейная интерполяция (ошибка на таком отрезке незаметна). И главный трюк — перекрытие: FDIV для следующего 16-пиксельного спана запускается в начале текущего; пока FPU 30+ тактов делит, целочисленные конвейеры U/V рисуют текущие 16 пикселей. Деление выходит «бесплатным» — спрятано под рисование, ~7.5 такта на пиксель.

целые U/V: рисуем спан N спан N+1 спан N+2 FPU (FDIV): 1/z для N+1 1/z для N+2 1/z для N+3 Деление для следующего спана крутится параллельно рисованию текущего → латентность FDIV спрятана. Mode 7: одно деление на всю строку (постоянная глубина).

Мост к Mode 7. Помнишь построчную перспективу SNES? Там глубина постоянна вдоль строки → деление 1/z одно на строку. У Quake полигон уходит вглубь, z меняется вдоль спана → деление нужно периодически (раз в 16 пикселей). Mode 7 — это вырожденный случай «N = вся ширина строки».

Хардкор · теория: почему PVS «потенциально» и почему это безопасноможно пропустить

Видимость из области через порталы

VIS решает не «видна ли точка из точки», а «видна ли ячейка из любой точки другой ячейки». Луч зрения должен пройти через последовательность порталов; задача сводится к тому, существует ли прямая, протыкающая все порталы цепочки (через сепарирующие/клиппирующие плоскости между рёбрами порталов). Если хоть одна такая прямая есть — целевая ячейка попадает в PVS.

Консервативность

PVS консервативен: он может пометить лишнее (ячейку, которая из текущей точки/угла на самом деле не видна) — это лишь лишние отрисовки. Но он никогда не пропустит реально видимую ячейку — иначе в мире появились бы дыры. Точная попиксельная видимость зависела бы от позиции и угла камеры и стоила бы попиксельных вычислений в кадре — ровно того, что precompute и устраняет. Поэтому хранят грубое-но-безопасное приближение на область, а не точное на точку.

Перспективная коррекция: откуда берётся кривизна

Экранная координата ∝ x/z. Если интерполировать u линейно по экрану, неявно предполагаешь z постоянным — на уходящем вглубь полигоне это даёт «плавающую» текстуру. Линейны по экрану именно u/z и 1/z; их и тянут, а деление в конце возвращает истинное u. Длина отрезка между точными делениями — компромисс «ошибка vs стоимость»: 16 пикселей у Quake выбраны так, что ошибка невидима, а FDIV как раз успевает за рисованием спана.

Хардкор · инженерия: компилятор карты и рантайм-конвейерможно пропустить
  • Три инструмента, по очереди: QBSP (BSP-дерево + порталы .prt) → VIS (PVS из порталов; на картах 1996-го мог считаться часами) → LIGHT (трассировка света в lightmap’ы). Карта — это «скомпилированный бинарь» уровня.
  • Рантайм-каскад отсечений: PVS (грубо, предвычислено) → frustum cull (по полю зрения, в кадре) → BSP-порядок (back-to-front / front-to-back со списком рёбер). Каждый слой убирает свою долю.
  • Surface cache: освещённая поверхность (texture × lightmap) собирается один раз и кэшируется; перерисовки берут готовое. Память против вычислений.
  • Внутренний цикл текстурирования Абраша: FDIV следующего спана перекрывает целочисленное рисование текущего на сдвоенных пайпах Pentium → ~7.5 такта/пиксель (это для 16-пиксельных спанов ASM-пути; дефолтный C-путь шиппинг-сборки делит каждые 8 пикселей). Это удвоило fps относительно наивной версии.
  • Софт-рендер сначала. Quake вышел с программным растеризатором; GLQuake/VQuake (аппаратное ускорение) — позже. Аппаратный GPU убрал ручной трюк с FDIV, но PVS/BSP/lightmap’ы остались (в GL surface cache уже не нужен — текстура и lightmap комбинируются на лету).
Аналогия
Quake — это музей, подготовленный до открытия. Залы заранее размечены (BSP-ячейки); для каждого зала на табличке записано, какие другие залы из него видно через двери (PVS); свет расставлен и «запечён» в стены (lightmap’ы). Посетитель-рантайм просто идёт и читает готовую табличку «отсюда видно залы 3, 7, 12», не пересчитывая ни видимость, ни свет на ходу. Вся тяжёлая работа сделана до того, как пришёл первый игрок.
Почему это важно
Quake — канонический образец «вынеси дорогое в офлайн». Граница «что предвычислить при компиляции карты, а что считать в кадре» — это тот самый бюджетный выбор, который и сегодня решает, летает движок или нет: baked GI против realtime GI, статические лайтмапы против динамических теней. Понять Quake — значит понять, что precompute это не хак, а архитектурное решение.
🔁 За пределами игр — куда это переносится
Quake — это два мощных приёма: «посчитай заранее, в рантайме только выбирай» (PVS, lightmap’ы) и пространственный индекс (BSP), плюс амортизация дорогой операции (деление раз в 16 пикселей).

Системы / БД: PVS — это материализованное представление / предвычисленный индекс: дорогой ответ считаем офлайн, рантайм = lookup. BSP — пространственный индекс, родня k-d tree, BVH, R-tree: режем пространство, чтобы не сканировать всё. Консервативная видимость = «лучше лишнее, чем пропуск» (как в alias-анализе компилятора).

ML / AI: «запеки офлайн — отдавай дёшево» — это предвычисленные эмбеддинги / feature store (тяжёлые признаки считаем заранее, инференс = выборка) и ANN-индексы (HNSW/IVF) — пространственный индекс над эмбеддингами, тот же BSP-над-миром: дробим пространство, чтобы не делать полный скан. KV-cache = surface cache для трансформера: посчитанное состояние префикса переиспользуем. Деление-раз-в-16-пикселей = чанкинг/градиентное накопление: дорогую операцию амортизируем по оси.

Перф: lightmap = мемоизация дорогого вычисления в текстуру; surface cache = переиспользование между кадрами. «Не считай в горячем цикле то, что не меняется».

Принцип: реши заранее всё, что в рантайме неизменно; рантайм пусть лишь выбирает из предсчитанного и амортизирует то, что обязан считать.

🔧 Запусти и поковыряй — на домашнем компе
Во что поиграть — ниже (🕹). Здесь — залезть в движок через консоль:
🔧 Поковырять (debug) ~30 мин, сорс-порт
Поставь QuakeSpasm/Ironwail, открой консоль (~). r_speeds 1 — счётчики нарисованных поверхностей/рёбер. Теперь r_novis 1 — выключаешь PVS: движок начинает рисовать всё в frustum, счётчики взлетают, fps проседает; r_novis 0 — вернулось. Затем r_fullbright 1 (нужен developer 1/читы) — выключаешь lightmap’ы: атмосферный свет исчезает, мир становится плоским.
🧪 Потестить (глазами QA) ~15 мин
Ищи следствия предвычисления: «комната над комнатой» (невозможная в Doom); куда «протекает» PVS (иногда видно дальше, чем нужно — консервативность); резкие границы запечённых теней; статичность света (стрельба даёт динамический блик поверх статичной картины). Чеклист артефактов precompute-движка.
Чеклист: увидел скачок r_speeds при r_novis 1; выключил свет через r_fullbright; нашёл room-over-room и оценил, где PVS «протекает».

🕹 В какие игры поиграть — и что заметить

От 2.5D-предшественника к настоящему 3D и к тому, что на нём выросло. По каждому: что внутри и во что сыграть/что ввести в консоль.

Doom 1993 · 2.5D, контраст

2D-BSP, сектора с высотами, нет наклона камеры и комнат-над-комнатами. Тот же приём предвычисления, но в плоскости — отличный контраст к Quake.

🎮 Сыграй: в Doom попробуй найти комнату прямо над другой — её нет; стрельба по вертикали идёт автоприцелом. Это потолок 2.5D. Разбор — в уроке Doom и BSP.

Quake — PVS вживую 1996 · r_novis

Из ячейки камеры рисуется только её PVS. Это можно выключить и увидеть цену.

🎮 Сыграй: в QuakeSpasm введи r_speeds 1, затем r_novis 1 — счётчик поверхностей подскакивает в разы, fps падает: движок рисует весь потенциально-кадровый мир без отсечения по видимости. r_novis 0 — PVS снова режет. Ты буквально щёлкаешь предвычисленную видимость.

Quake — свобода 3D полный 3D-обзор + room-over-room

Произвольная геометрия и полный обзор — то, чего Doom не мог.

🎮 Сыграй: в Quake найди балкон над залом (комната над комнатой — невозможна в Doom) и посмотри строго вверх и вниз. Свободный наклон камеры + перспективно-корректные стены под любым углом = настоящий 3D, не псевдо.

Quake — запечённый свет r_fullbright

Вся «атмосфера» уровней — статические lightmap’ы поверх текстур.

🎮 Сыграй: с developer 1 введи r_fullbright 1 — тени и градиенты света исчезают, мир становится равномерно ярким и плоским. Включил-выключил — увидел, сколько настроения несёт один запечённый слой света.

Half-Life / Quake II наследники движка

GoldSrc (Half-Life) и Quake II стоят на том же BSP+PVS+lightmap, добавив цветной свет и больше динамики. Архитектура видимости и запечённого света дожила до конца 90-х почти без изменений.

🎮 Посмотри: в Half-Life то же дерево BSP и PVS; developer 1 и аналог r_speeds покажут ту же механику отсечения. Сравни цветной свет HL с монохромными lightmap’ами Quake.

Связи
основа
Doom и BSP — 2D-BSP, сектора и столбцовый растеризатор; Quake обобщает ту же идею разбиения на полный 3D.
контраст
SNES Mode 7 — псевдо-3D одним слоем: деление 1/z раз на строку (постоянная глубина). Quake делит на пиксель/спан, потому что глубина меняется вдоль полигона.
дальше
Обзор · Модуль 3 — остальные уроки 3D-эпохи: конвейер растеризации, камеры, клиент-предсказание (QuakeWorld).
Вопросы пытливого ума
Если PVS уже говорит, что видно, зачем ещё frustum culling и BSP-обход?
Они режут разное. PVS — грубый, предвычисленный, на область: «что видно хоть из какой-то точки ячейки», и смотрит на 360°. Frustum cull — в кадре, по текущему полю зрения: убирает то, что за спиной и вне угла. BSP даёт порядок отрисовки и работает для коллизий. Это каскад: дешёвый грубый фильтр (PVS) → точный по кадру (frustum) → сортировка (BSP). Каждый снимает свою долю — поэтому их три, а не один.
Почему PVS «потенциально» видимое, а не «точно»?
Точная видимость зависит от конкретной позиции и угла камеры — её пришлось бы пересчитывать в кадре, ровно то, что precompute устраняет. Поэтому хранят видимость из всей ячейки и консервативно: PVS может пометить лишнее (лишние отрисовки — терпимо), но никогда не пропустит реально видимое (пропуск = дыра в мире). Безопасное переприближение на область вместо дорогого точного на точку.
Doom тоже на BSP — в чём принципиальная разница с Quake?
В размерности. У Doom BSP 2D (режет план линиями); «3D» имитируется высотами пола/потолка на сектор → нет комнат над комнатами, нет наклона камеры, текстуры тянутся без перспективы. У Quake BSP 3D (режет объём произвольными плоскостями) → настоящие объёмы, свободный обзор вверх-вниз, перспективно-корректные текстуры. Одна структура данных, но переход от линий к плоскостям меняет класс возможного.
Зачем запекать свет, если Doom уже менял яркость секторов «динамически»?
Яркость-на-сектор у Doom — это один скаляр на плоский регион, почти бесплатно. Quake-овский свет — это градиент по поверхности (мягкие тени, спад от ламп), и считать его на пиксель в рантайме 1996-е железо не могло. Запекание выносит расчёт в офлайн в обмен на статичность: лампу и стену не подвинуть. Несколько динамических огней (вспышки) добавляли дешёвым аддитивным слоем поверх запечённого. Тот же компромисс baked-vs-realtime GI жив и сегодня.
Почему перспективную коррекцию делать раз в 16 пикселей, а не на каждый или раз на спан?
На каждый — деление (FDIV ~39 тактов) убивает скорость. Раз на длинный спан — аффинная ошибка растёт с длиной и перепадом глубины, текстура «плывёт». 16 пикселей — золотая середина: ошибка невидима, цикл хорошо разворачивается, а FDIV для следующих 16 как раз успевает параллельно целочисленному рисованию текущих (сдвоенные пайпы Pentium) → деление эффективно бесплатно. У Mode 7 «раз на строку» прокатывает только потому, что вдоль строки глубина постоянна.
Что почитать