2.5D Renderer

Stage 3: Binary Space Partition

Разбиение на подсекторы

→

Для проблемы размещения сектора внутри сектора есть одно поистине гениальное решение:

Разделим все текущие секторы на секторы меньшего размера — подсекторы в виде выпуклых многоугольников.

Что дает разделение? Ранее мы научили отрисовщик рисовать секторы последовательно один за другим. После разделения всех секторов на подсекторы мы возвращаемся к ситуации, когда у нас нет вложенных подсекторов, а значит можем использовать ранее созданный отрисовщик.

Что дает выпуклость? В выпуклом многоугольнике отрезок, проведенный между любыми двумя точками внутри фигуры, остается внутри этой фигуры и не пересекает внутренние границы. Благодаря этому сегменты внутри одного подсектора можно рисовать без дополнительной сортировки, как мы делали раньше.

Для разделения используем алгоритм Binary Space Partition, или BSP: двоичное разбиение пространства. Простыми словами: пространство постоянно делится линиями на две части, пока не останутся простые отдельные зоны. Это как деление пирога: режем пополам, затем каждую половинку еще пополам, пока не получатся удобные кусочки.

Что дает алгоритм BSP? В результате работы алгоритма все пространство секторов будет разбито на множество подсекторов, связанных в BSP-дерево. Такое дерево позволяет получать последовательность подсекторов от ближних к дальним или наоборот.

Ценность этого подхода в совокупности с другими идеями заключается в будущей экономии ресурсов при отрисовке.

Из чего состоит BSP-дерево

  • Ветвь хранит направленный сегмент-разделитель и два дочерних узла.
  • Лист завершает рекурсию и описывает готовый выпуклый подсектор.

type BSPBranch = {
  kind: 'branch';
  splitter: Seg;
  front: BSPNode;
  back: BSPNode;
};

type BSPLeaf = {
  kind: 'leaf';
  segs: Seg[];
};

type BSPNode = BSPBranch | BSPLeaf;

На самом деле выше описан минимальный набор свойств. В зависимости от реализаций он может отличаться.

Как строится BSP-дерево

  • Один из сегментов уровня выбирается в качестве разделителя.
  • Разделитель достраивается до бесконечной прямой.
  • Эта прямая делит текущую область (или пространство) на переднюю front и заднюю back область:
    • Сегменты, полностью лежащие с одной стороны прямой, отправляются в соответствующую ветвь.
    • Сегменты на линии разделителя сохраняются в обеих соседних областях как часть их границы.
    • Пересекающие прямую сегменты разрезаются в точке пересечения, после чего каждая половина попадает на свою сторону.
    • Получившиеся открытые контуры замыкаются служебными сегментами вдоль линии разделения.
  • Для передней и задней областей операция повторяется рекурсивно, пока получившаяся область не станет связным выпуклым многоугольником.

Выпуклая область становится листом. В листе отдельно хранятся реальные сегменты уровня для рендера и замкнутая граница подсектора для проверки и визуализации разбиения. Невыпуклая область становится ветвью дерева со своим разделителем и дочерними узлами front и back.

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

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

Как выбрать сегмент-разделитель

В алгоритме BSP секторы разбиваются на подсекторы с помощью разделительных линий splitter. Выбор этих линий критически важен для производительности: хорошая эвристика строит более сбалансированное дерево и уменьшает количество разрезов.

  1. Сбалансированность дерева. Каждая разделительная линия должна делить область на две примерно равные части по количеству полигонов. Это помогает удерживать глубину дерева небольшой, а поиск нужного подсектора — быстрым.
  2. Минимизация разрезов. Линия должна проходить так, чтобы разрезать как можно меньше стен на карте. Каждый разрез создает новые сегменты (seg), увеличивает объем данных и может приводить к визуальным артефактам.

Визуализация разбиения пространства

Форма и глубина дерева зависят не только от уровня, но и от выбора разделителей. Удачная стратегия должна сохранять баланс между ветвями и при этом создавать как можно меньше новых фрагментов сегментов.

Исходный уровень

Последовательное BSP-разбиение

Разделение 0 из 4

Ниже BSP-дерево для того же уровня, но представленное в виде JSON:

  • Узел с типом branch содержит разделитель и ссылки на переднее и заднее поддеревья.
  • Узел с типом leaf завершает разбиение и содержит границу готового выпуклого подсектора.
kind:"branch"
splitter:
start:{2 keys}
end:{2 keys}
isTwoSided:true
frontSectorId:2
backSectorId:1
front:
kind:"branch"
splitter:{5 keys}
front:{4 keys}
back:{4 keys}
back:
kind:"leaf"
segCount:4
segs:Array(4)
bounds:{4 keys}

Как использовать BSP-дерево

Положение камеры относительно разделителя определяет порядок обхода дочерних узлов. Сначала посещается сторона с камерой, затем противоположная за камерой — так листья и стены поступают в отрисовщик от ближних к дальним. Это позволит в будущем сразу отмечать уже закрытые участки экрана и не перерисовывать их.

Функция ниже выполняет обход от ближних листьев к дальним. Для листа она вызывает переданную callback-функцию, а для ветви определяет сторону камеры относительно направленного сегмента-разделителя. Потомок на стороне камеры обходится первым. 


function traverseBSPTree(
  node: BSPNode,
  camera: Camera,
  renderLeaf: (leaf: BSPLeaf) => void,
): void {
  if (node.kind === 'leaf') {
    renderLeaf(node);
    return;
  }

  const cameraSide = getPointSide(node.splitter, {
    x: camera.x,
    y: camera.y,
  });

  // Камера находится с back-стороны:
  // сначала рисуем ближнюю ветвь, затем дальнюю
  if (cameraSide <= 0) {
    traverseBSPTree(node.back, camera, renderLeaf);
    traverseBSPTree(node.front, camera, renderLeaf);
  } else {
    traverseBSPTree(node.front, camera, renderLeaf);
    traverseBSPTree(node.back, camera, renderLeaf);
  }
}

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

Пара слов об использовании BSP в DOOM

В DOOM BSP-дерево строилось заранее при подготовке карты, то есть во время отрисовки кадра дерево не перестраивалось, а использовалось ранее сформированное. При построении дерева сложные и вогнутые области разрезались линиями-разделителями до тех пор, пока листьями дерева не становились выпуклыми подсекторами. Если разделитель пересекал стену, исходный linedef не изменялся, но для рендера делился на несколько более коротких seg.

Готовое разбиение сохранялось в WAD в виде трех связанных наборов данных:

  • NODES — ветви дерева с разделителем, границами дочерних областей и ссылками на потомков;
  • SSECTORS — листья дерева, то есть выпуклые подсекторы;
  • SEGS — видимые границы подсекторов, связанные с исходными стенами карты.

Во время отрисовки кадра движок начинал обход с корня дерева. Для каждого узла он определял, с какой стороны от разделителя находится игрок, сначала шел в ближнюю ветвь, а дальнюю мог проверить по границам области и пропустить, если она уже не могла быть видна. Благодаря этому BSP работал не только как способ сортировки стен, но и как пространственный фильтр.

Дополнительный материал: