← Модуль 3/Doom и BSP
EN
Модуль 3 · 3D-революция (1993–1999)

Doom и рендер на BSP

Как Кармак отрисовал «3D» на 486 без GPU и z-буфера: 2D-мир с высотами, предвычисленное BSP-дерево и целочисленный столбцовый растеризатор. Разбор до уровня «прочитал — можешь написать сам».
глубокий~25 мин🏠 лаба
Суть за 30 секунд
Doom рисует «3D» без честной 3D-геометрии и без z-буфера. Мир — двумерный (секторы с высотой пола/потолка), стены вертикальны. Движок не кастует луч на пиксель (это Wolfenstein 3D) — он обходит предвычисленное BSP-дерево спереди-назад, проецирует видимые отрезки стен (segs) в вертикальные столбцы экрана (высота ∝ 1/z) и отсекает перекрытое через клип-массивы столбцов. Вся дорогая работа — порядок и видимость — унесена в build-time дерево; рантайм линеен и целочислен.

Контекст: 1993, бюджет в пару миллионов тактов

Целевое железо — Intel 386/486: нет видеоускорителя, нет аппаратного z-буфера, FPU медленный или отсутствует (на 486SX его нет вовсе). На кадр при 35 FPS — порядка двух-трёх миллионов тактов на весь рендер. «Честный» 3D с попиксельной сортировкой глубины (z-буфер) или с плавающей точкой туда не помещается. Wolfenstein 3D (1992) уже показал «3D» через raycasting, но ценой жёстких ограничений: стены на равномерной сетке, все одной высоты, никаких наклонных стен. Кармаку нужно больше — произвольные углы стен, разные высоты комнат, лестницы, окна. Ответ — не выжать железо, а сменить постановку задачи и перенести тяжёлое в компиляцию уровня.

Мир Doom: 2D-план с высотами

Чтобы понять рендер, надо знать, из чего сделан уровень (это лежит в WAD):

Главное следствие двумерности: точка плана (x, y) принадлежит ровно одному сектору — а значит, в одном месте карты не может быть двух полов друг над другом. Это и есть ограничение 2.5D: мир выглядит объёмным (за счёт высот и проекции), но геометрически он плоский, и поэтому задача видимости сводится к двумерной. «Нельзя комнату над комнатой» — не баг, а то самое «нельзя», которое делает алгоритм дешёвым.

Почему это не raycasting

Частая путаница: «Doom для каждого столбца кастует луч и ищет стену». Это Wolfenstein 3D: один луч на столбец экрана, трассировка по равномерной сетке (DDA) до первой стены → расстояние → высота столбца. Сетка и одна высота — следствие именно raycasting'а.

Doom устроен наоборот: он не спрашивает «что в этом столбце?», а берёт реальные отрезки стен и проецирует их на экран как вертикальные трапеции, попутно отсекая закрытое. Порядок «кого рисовать раньше» даёт BSP, а не луч. Именно это снимает ограничения Wolf3D: стены под любым углом, разные высоты секторов, порталы (проёмы между секторами разной высоты — окна, ступени).

Проекция: откуда берётся 1/z

Камера в начале координат смотрит вдоль оси. Точка стены на перпендикулярном расстоянии z (глубине вдоль взгляда) и мировой высоте h над уровнем глаз. Плоскость проекции (экран) стоит на расстоянии dproj. По подобию треугольников (общий угол у камеры): отношение экранной высоты к dproj равно отношению мировой высоты к z. Сама dproj задаётся горизонтальным полем зрения и шириной экрана W:

dproj=W/2tan(FOV/2)

В Doom FOV по горизонтали 90°, экран 320 пикселей → dproj = 160/tan(45°) = 160. Удобно ввести scale — сколько экранных пикселей приходится на единицу мировой высоты на данной глубине z:

scale=dprojz

Тогда экранная вертикальная координата мировой высоты hworld (относительно высоты глаз viewz), и полная высота стены на экране:

yscreen=centery−(hworld−viewz)·scale hscreen=(zceil−zfloor)·scale=hwall·dprojz

Вот и «1/расстояние»: высота столбца обратно пропорциональна z.

Подставим числа. Стена высотой hwall = zceil − zfloor = 128 ед. на глубине z = 256 → scale = 160/256 = 0.625 → hscreen = 128 · 0.625 = 80 px. Отойди на z = 512 — та же стена вдвое ниже, 40 px. Вся «глубина» — из одного деления на z.

От столбца к целой стене. Один seg — отрезок с двумя концами на разных глубинах z1, z2, значит у него два scale: d_proj/z₁ и d_proj/z₂. Движок шагает scale линейно по экранным столбцам между краями seg (это корректно: scale ∝ 1/z, а 1/z для плоской стены линейна по экрану) — где стена ближе, столбцы выше, где дальше — ниже. Так из вертикальных столбцов складывается трапеция наклонной стены, а перспективная развёртка горизонтальной текстуры — прямое следствие того же 1/z-шага.

И тонкий момент про сами текстуры: внутри одного столбца выборка по вертикали аффинна (весь столбец — одна горизонтальная точка вертикальной стены, то есть один z), поэтому достаточно frac += iscale. А поперёк столбцов z меняется — и горизонталь требует той самой 1/z-коррекции из шага scale выше.

глаз d_proj z (глубина) h_screen h_world экран стена
Подобие треугольников: h_screen / d_proj = h_world / z ⟹ высота на экране падает как 1/z. Никакого 3D-API — только похожие треугольники и деление.

BSP: построение (оффлайн)

BSP (Binary Space Partitioning) строит нодбилдер при компиляции уровня. Рекурсия: выбираем секущую прямую (обычно вдоль одного из segs); segs, лежащие спереди от неё, уходят в одну ветвь, сзади — в другую, а пересекающие прямую разрезаются на два (важно: split реально создаёт новые segs). Рекурсия заканчивается, когда в ветви остаётся выпуклое множество segs — subsector: внутри выпуклой области стены не перекрывают друг друга неоднозначно, поэтому их можно рисовать в любом внутреннем порядке. Внутренний узел дерева хранит секущую прямую (точка p и направление (dx, dy)) и bbox каждого ребёнка.

Не путать sector и subsector. Sector — единица геймплея (своя высота пола/потолка, освещение, тип «лава/телепорт»); subsector — единица рендера (выпуклый лист BSP). Невыпуклый sector дерево режет на несколько subsector'ов, поэтому subsector'ов в уровне обычно больше, чем секторов. Игрок «стоит в секторе», но движок обходит и рисует «по subsector'ам».

Выбор секущей — это компромисс: чем «удачнее» прямая, тем меньше разрезов (меньше новых segs, меньше памяти) и тем ровнее дерево (меньше глубина обхода). Эти две цели конфликтуют, а оптимальный BSP (минимум разрезов / минимум узлов) — NP-трудная задача, поэтому нодбилдеры используют жадные эвристики (например, минимизировать число split'ов, штрафуя дисбаланс).

BSP: обход (рантайм, спереди-назад)

Зная позицию камеры, дерево обходится так, что segs выдаются строго от ближних к дальним:

Обход BSP псевдокод
render_bsp(node):
    if node is subsector:
        draw_segs(node)              # выпуклый лист — внутр. порядок не важен
        return
    side = point_side(view, node.partition)   # по какую сторону камера (знак ниже)
    render_bsp(node.child[side])              # БЛИЖНЯЯ сторона — первой
    if bbox_visible(node.child[1 - side]):    # дальняя — только если ещё не закрыта
        render_bsp(node.child[1 - side])

Тест стороны — это знак двумерного векторного произведения (ориентированная площадь): для секущей с точкой p и направлением (dx, dy) и камеры v

s=(vx−px)·dy−(vy−py)·dx

s > 0 — камера с одной стороны, s < 0 — с другой. Спускаемся сначала в ближнюю ветвь → ближние стены выдаются раньше дальних. Поскольку листья выпуклы, а секущие плоскости согласованы, этот порядок совпадает с истинной глубиной для любой позиции камеры (доказательство — в хардкоре).

Отсечение перекрытого: почему обход линеен

Front-to-back окупается только вместе с дешёвым отсечением уже закрытого. Doom держит две структуры экранного покрытия:

Так каждый экранный пиксель пишется не более одного раза (no overdraw — критично, fill rate был узким местом), а как только solidsegs закрывает весь экран, обход BSP можно оборвать. Итог: O(n) по числу segs, без сортировки и без попиксельной глубины.

План уровня → выпуклые листья BSP 1 2 3 4 игрок обход: 1 → 2 → 3 → 4 (ближние раньше дальних) — — пунктир: секущие прямые (splitting hyperplanes)
Уровень рекурсивно режется прямыми на выпуклые subsector'ы; зная позицию игрока, дерево обходится от ближнего листа к дальнему — точный порядок за один проход.

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

Один вопрос — «как нарисовать 3D на CPU без GPU» — пять разных ответов под разные ограничения, от сетки лучей до настоящего 3D. По каждому: как сделано и во что сыграть, чтобы увидеть руками (порядок — от простого к сложному).

Wolfenstein 3D 1992 · raycasting · предшественник

Один луч на столбец экрана, трассировка по равномерной сетке (DDA) до первой стены → расстояние → высота столбца. Отсюда жёсткие «нельзя»: стены только по сетке, все одной высоты, под прямым углом, без наклонов и перепадов. Рендер прямолинейный, но потолок сложности сцены низкий. Ровно та постановка, от которой Кармак ушёл к BSP.

🎮 Сыграй: запусти ECWolf + бесплатный shareware-эпизод. Заметь: все стены равной высоты, перекрёстки строго по сетке 90°, ни ступенек, ни окон, ни взгляда вверх/вниз. «3D», в котором мир — плоский лабиринт из одинаковых блоков.

Doom 1993 · BSP · 2.5D · сам урок

Геометрия проецируется через предвычисленное BSP-дерево (весь разбор выше): произвольные углы стен, разные высоты секторов, порталы-окна — всё, чего Wolf3D не мог. Но мир по-прежнему 2.5D: точка плана → один сектор, комнаты над комнатой нет, честно смотреть вверх/вниз нельзя.

🎮 Сыграй: поставь DSDA-Doom или GZDoom + бесплатный Freedoom. Попробуй посмотреть вверх/вниз — «mlook» в порт-сорсах есть, но это y-shearing (сдвиг картинки), не настоящий наклон → вот оно, 2.5D. Обойди импа по кругу — он остаётся плоским, меняя кадры спрайта (биллбординг). Жми Tab — увидишь 2D-план, который режет BSP. Счётчик FPS упрётся в 35 (кап ванили, всё на CPU).

Marathon 1994 · портальный рендер · «5D space»

Bungie, Mac-эксклюзив, примерно на год позже Doom (дек 1994 vs дек 1993). Рендер не на BSP, а на порталах — и это позволило непредставимое в Doom: room-over-room и даже наложение областей, когда два и более полигона занимают одну (x, y) («5D space» — им строили невозможную в плане геометрию). Вертикального автоприцела нет: целишься вверх/вниз руками (в Doom наоборот — смотреть вертикально нельзя, зато есть автоаим по высоте).

🎮 Сыграй: запусти Aleph One (открытый движок) + бесплатную трилогию Marathon. Заметь: чтобы попасть по врагу выше/ниже, целишься по вертикали сам — авто-аима нет (в Doom об этом не думаешь). Поищи карты с «5D space», где геометрия физически перекрывается — в Doom так не закодировать.

Build / Duke Nukem 3D 1996 · порталы без BSP · слоупы

Движок Кена Сильвермана: тоже порталы, но без оффлайн-препроцессинга — карта не пекётся в BSP, поэтому стены двигаются в рантайме (разрушаемость, едущие секторы) плюс наклонные полы/потолки. Расплата — нет дешёвого front-to-back BSP-порядка. Room-over-room здесь не родная фича, а трюк: подводные секции телепортируют игрока в другую часть карты, мимикрирующую под «этаж ниже». Настоящий ROR (TROR) появился лишь в EDuke32 (2011), где секторы реально стэкаются в данных.

🎮 Сыграй: запусти EDuke32 + shareware Duke3D. Заметь наклонные поверхности и свободный взгляд вверх/вниз (которых нет в Doom), взорви стену — динамическая геометрия, невозможная с предвычисленным BSP. Нырни под воду — это и есть тот самый телепорт-трюк «комнаты над комнатой».

Quake 1996 · настоящий 3D BSP

Финал арки: id выкидывает 2.5D. Геометрия полигональная в 3D, BSP делит уже 3D-пространство, сверху — PVS (Potentially Visible Set, предвычисленная видимость из каждого листа). Комната над комнатой, честный взгляд во все стороны, наклонные поверхности — бесплатно, потому что мир наконец настоящий 3D. Ограничение «точка → один сектор» снято.

🎮 Сыграй: запусти vkQuake или QuakeSpasm + shareware Quake. Свободно смотри вверх/вниз, найди комнату над комнатой, прыгни в вертикальную шахту — всё то, что в Doom физически непредставимо. Это граница, за которой 2.5D-эпоха кончается.

Хардкор · теория: почему front-to-back корректен и при чём тут циклыможно пропустить

Секущая плоскость задаёт строгий порядок

Плоскость H делит пространство на два открытых полупространства H⁺ и H⁻. Для камеры в H⁺ всё, что в H⁺, не может быть загорожено тем, что в H⁻ (между ними — разделяющая плоскость). Значит «сначала ближняя сторона, потом дальняя» — корректный частичный порядок на этом узле. Рекурсивно по дереву это даёт полный строгий порядок глубины для любой точки обзора. Выпуклость листа гарантирует, что внутри него взаимного загораживания нет, поэтому внутренний порядок segs не важен.

Почему наивный painter ломается

Painter сортирует полигоны по глубине и рисует дальние под ближними. Но отношение «A заслоняет B» не транзитивно: бывают циклические перекрытия — A заслоняет B, B заслоняет C, C заслоняет A (три длинных полигона внахлёст по кругу). Глобальной сортировки тогда не существует — любой порядок даст артефакт. BSP режет цикл физически: секущая плоскость рассекает нарушителей на части, и для частей порядок уже однозначен. Это и есть исходная мотивация BSP (Schumacker 1969; Fuchs, Kedem, Naylor 1980).

Сложность

Разрезы умножают число segs: в патологии — до O(n²) фрагментов. Хорошие нодбилдеры дают дерево размером порядка O(n log n) (Paterson–Yao), но само построение перебором кандидатов-сплиттеров обычно ~O(n²), а оптимальный BSP (минимум разрезов/узлов) NP-труден — отсюда эвристики. Зато обход в рантайме — O(n) по числу segs (плюс дешёвый bbox-reject и solidsegs). Вся асимптотическая тяжесть — в build-time, у игрока её нет.

Хардкор · инженерия: фикспоинт, таблицы и внутренний цикл столбцаможно пропустить

BSP даёт порядок, но «летает на 486» Doom благодаря целочисленной реализации — FPU тут нельзя.

  • Фикспоинт 16.16. Все координаты и шаги — 32-битные целые, где старшие 16 бит — целая часть, младшие 16 — дробная. Деление на z для scale — целочисленное; умножение даёт 64-битный промежуток со сдвигом. Никакого float.
  • Таблицы тригонометрии. угловое разрешение FINEANGLES = 8192; синусы/тангенсы не считаются, а берутся из массива по индексу-углу (BAM, binary angle). Сами таблицы длиннее: finesine — 10240 значений (чтобы finecosine читался из того же массива со сдвигом), finetangent — 4096. Угол к стене → индекс → готовое значение.
  • Внутренний цикл столбца (R_DrawColumn): рисует вертикальную полосу текстуры с целочисленным шагом по тексель-координате —
# столбец текстуры в fixed-point 16.16
frac = texturemid + (y0 - centery) * iscale
for y in y0 .. y1:
    pix[y] = src[ (frac >> 16) & mask ]   # целая часть как индекс
    frac += iscale                          # шаг по текстуре, без float

Это и есть «горячий» цикл движка — простой, предсказуемый, кэш-дружелюбный (последовательная запись столбца). Полы/потолки рисует двойник R_DrawSpan горизонтальными отрезками (visplanes). Паттерн целиком: предвычисленная структура (BSP) + таблицы + фикспоинт + плотный целочисленный цикл = софт-рендер на CPU без единой операции с плавающей точкой и без спецжелеза. Ноль ML, ноль GPU — алгоритмика и аккуратная инженерия.

Хардкор · дизайн: как ограничение 2.5D сформировало язык уровнейможно пропустить

Техническое ограничение не «портило» дизайн — оно задало эстетику. Раз нельзя комнату над комнатой и нельзя честно смотреть вверх/вниз, уровни Doom строятся в особом пространственном языке: лабиринты в плане, перепады высот пола/потолка вместо этажей, секции, читаемые «по карте сверху», порталы-окна между секторами разной высоты. Узнаваемая грамматика — прямое следствие 2.5D.

Второй эффект — скорость. Дешёвый рендер дал высокий, ровный FPS, и это сформировало game feel: стремительное движение, дэши по аренам, уклонение от снарядов. Медленный «честный» 3D дал бы более ватную игру. Ограничение здесь — творческий драйвер: сузило палитру и подарило фирменный темп.

Аналогия
BSP-дерево — это заранее построенное дерево решений «кто кого загораживает». Тяжёлый вопрос видимости решили один раз, при «печати» уровня. В игре под любым углом обзора ты не сортируешь сцену, а просто спускаешься по готовому дереву, на каждой развилке отвечая на дешёвый вопрос «я слева или справа от этой прямой?» — и стены выпадают сразу в правильном порядке.
Почему это важно
Doom — архетип «смени постановку задачи + предвычисли структуру > сырая мощь». Для инженера, делающего AI в играх, мораль прямая и практичная: прежде чем тянуться к модели или GPU, спроси — нет ли ограничения, которое делает задачу дешёвой, и структуры, которую можно построить заранее. Кармак не ускорял 3D — он переопределил, что такое «3D», пока оно не стало помещаться в бюджет. Это и есть инженерное суждение, ради которого ты этот курс и проходишь.
🔁 За пределами игр — куда это переносится
Главный приём Doom — «предвычисли структуру оффлайн → рантайм дёшев и детерминирован» (+ мета-урок Кармака: удачно выбранное ограничение открывает дешёвый алгоритм). Это общеинженерный паттерн:

Бэкенд / БД: индексы (B-tree, инвертированный), материализованные представления, кэш query-плана — тяжёлое строится раз, запрос дёшев.

Инфра / веб: CDN и кэширование (положил ближе / посчитал заранее → мгновенная отдача); статическая генерация сайтов — как этот курс.

ML / AI: KV-cache в LLM-инференсе — это буквально Doom-приём: префикс посчитан раз и переиспользуется (см. LLM-NPC). Сюда же — предвычисленные эмбеддинги/индексы (FAISS) под retrieval; компиляция графа (torch.compile / XLA): дорого на старте, быстрый рантайм.

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

🏠 Лаба — пощупать рендер Doom
Интерактивная лаба без кода: крути ползунки и двигай игрока, смотри, как формулы из урока оживают — проекция 1/z, порядок BSP front-to-back, цена overdraw. Запускается прямо в браузере (и на телефоне). Открыть лабу →
Эталонный разбор движка построчно — Fabien Sanglard, «Game Engine Black Book: DOOM». А во что поиграть и как залезть в движок — секции «🕹» и «🔧» ниже.
🔧 Запусти и поковыряй — на домашнем компе
Во что поиграть и что заметить — выше (🕹). Здесь — для тех, кто хочет залезть в сам движок:
🔧 Поковырять (debug) ~1 ч, нужен C-тулчейн
Склонируй chocolate-doom (точная копия оригинала) или linuxdoom-исходники, собери. Поставь брейкпоинт в R_RenderBSPNode и R_DrawColumn, сделай шаг на один кадр — увидишь обход дерева и заполнение столбцов из урока вживую. Включи noclip, пролети сквозь стены, глядя на автокарту — почувствуешь, как «игрок стоит в секторе».
🧪 Потестить (глазами QA) ~15 мин
Загрузи злую карту-слотермап (например nuts.wad): тысячи монстров и огромные открытые пространства роняют FPS и упираются в лимиты движка — visplane overflow на ванили, тот самый предел из урока. Поищи швы: попин спрайтов при повороте, невозможность прицелиться по вертикали.
Чеклист: в debug-сборке увидел обход R_RenderBSPNode и заполнение столбцов R_DrawColumn; уронил FPS слотермапом (visplane overflow). Эталонный построчный разбор — Fabien Sanglard, «Game Engine Black Book: DOOM».
Связи
дальше
ECS и data-oriented design — та же линия: производительность решается раскладкой данных и плотным циклом (как R_DrawColumn), а не «магией». Doom-рендер кэш-дружелюбен ровно по этим причинам.
пересечение
Классика vs ML — Doom как эталон «классика — правильный ответ»: детерминированный алгоритм с доказуемой корректностью там, где модель была бы и дороже, и хуже.
пересечение
Pathfinding — BSP и navmesh родственны: оба разбивают мир на удобные для обхода области. BSP — под рендер/видимость, navmesh — под поиск пути; тот же приём пространственного разбиения.
Вопросы пытливого ума
Как Doom рисует прозрачные решётки и грязные стёкла (middle textures) — и почему это отдельный проход?
Сплошная стена пишет столбцы и закрывает их (solidsegs). Но «средняя» текстура двустороннего linedef — с дырами: сквозь прутья решётки видно дальше. Значит её нельзя считать solid (она не закрывает столбцы) и нельзя рисовать прямо при обходе — за ней ещё не нарисованы дальние стены. Решение то же, что для спрайтов: при обходе такой seg запоминается как drawseg (masked), а рисуется отдельным поздним проходом (R_DrawMasked) поверх всей плотной геометрии — с проверкой прозрачности по столбцам и клипом по уже записанным границам. Общий принцип движка: всё «дырявое» (прозрачные стены, спрайты) — поздним проходом поверх сплошного.
BSP даёт порядок и так — почему front-to-back, а не back-to-front (классический painter)?
Back-to-front корректен, но рисует всё подряд с overdraw: дальние стены кладутся в кадр, затем затираются ближними. На 486 узким местом был fill rate (запись пикселей), поэтому лишние записи — непозволительная роскошь. Front-to-back + clip-массивы дают early reject: закрытые столбцы не рисуются вовсе, каждый пиксель пишется ≤1 раза, а обход обрывается, когда экран закрыт. Тот же порядок BSP, но инвертированный, экономит самое дорогое.
Сколько segs может стать после построения BSP и почему это не парадокс?
В худшем случае разрезы умножают примитивы до O(n²) segs (каждая секущая может рассечь множество стен). Это кажется проигрышем, но происходит один раз в build-time и платится памятью WAD, а не временем кадра. Нодбилдер жадно минимизирует split'ы (оптимум NP-труден), поэтому на практике рост умеренный. В рантайме важна не общая длина, а O(n) обход с отсечением — игрок платит только за видимое.
Почему выборка текстуры по вертикали столбца аффинна, а по горизонтали — нет?
Вертикальный столбец экрана соответствует одной горизонтальной точке вертикальной стены, то есть одному z; при постоянном z экранная координата линейна по мировой высоте → текстуру можно гнать аффинно (просто frac += iscale). Поперёк столбцов, сканируя стену слева направо, z меняется, и равные шаги по экрану — это неравные шаги по стене (перспективное сжатие у краёв) → нужна 1/z-коррекция. Doom считает горизонтальную тексель-координату через угол и scale (по сути перспективно-корректно), а дешёвую аффинность оставляет только вертикали.
Что именно делает «комнату над комнатой» непредставимой, и как Build (Duke3D) это обошёл?
В Doom точка плана (x, y) → ровно один сектор с единственной парой (пол, потолок). Два пространства, вертикально перекрывающихся в одной (x, y), просто негде закодировать — BSP делит 2D-плоскость, и точка попадает в один subsector. Build-движок (Duke Nukem 3D) обошёл это «room-over-room» хаками на порталах/секторах-телепортах (визуально стэкая секторы), но честная вертикальная топология появилась только с настоящим 3D — Quake (1996), где геометрия полигональная, а BSP делит уже 3D-пространство.
Монстры и двери в BSP не лежат — как их рисуют и сортируют по глубине?
Динамика разведена с геометрией. Спрайты (things: монстры, предметы) собираются во время обхода BSP — для каждого видимого subsector'а в список добавляются его things; затем спрайты сортируются по глубине отдельно и рисуются после стен, обрезаясь по уже записанным drawsegs и clip-массивам. Двери и лифты — это анимация высоты пола/потолка сектора, а план не меняется, поэтому BSP остаётся валидным и не перестраивается. Ключевой трюк: подвижно — только третья координата (высота), а планарная структура разрезов статична.
BSP-рендер устарел — почему идею всё равно надо знать?
Для рендера BSP ушёл: аппаратный z-буфер сделал попиксельную глубину дешёвой, сортировать геометрию деревом не нужно. Но пространственное разбиение живёт везде: BVH/kd-деревья — в трассировке лучей и коллизиях, octree/grid — в culling'е, navmesh — в навигации, PVS (Potentially Visible Set, надстройка над листьями BSP в Quake) — в предвычисленной видимости. Конкретный приём устаревает, паттерн «разбей пространство заранее, чтобы рантайм был дёшев» — фундаментальнее железа.
Что почитать