Введение
Двоичное разбиение пространства (Binary Space Partitioning, BSP) – метод рекурсивного разбиения евклидова пространства в выпуклые множества и гиперплоскости. Принцип его работы можно описать следующей последовательностью действий: начинаем с разделения пространства на плоскости, затем разделяем вновь сформированные подпространства с каждой стороны по другим плоскостям и продолжаем до тех пор, пока не закончатся подпространства, которые мы хотим разделить. Эти конечные подпространства становятся листьями нашего дерева. В результате объекты получают представление в виде структуры данных, называемой BSP-деревом. Эта техника может быть использована для значительного ускорения расчетов видимости в 3D-рендеринге.
Использование BSP в видеоиграх
Технология BSP широко распространена в разработке видеоигр. Прежде всего двоичное разбиение пространства используется для визуализации 3D пространства. Данная технология, к примеру, была использована в таких играх как Doom и Quake.
Прежде чем можно будет визуализировать 3D пространство в игре, мы должны выполнить ряд вычислений. Однако после того, как эти вычисления выполнены, их результаты можно использовать много раз. Это одно из преимуществ BSP – после того, как вычисления выполнены, их не нужно делать снова, если только карта не будет изменена.
Главный недостаток BSP-деревьев заключается в том, что вся карта должна быть статичной (неподвижной) – если часть ее сдвинется, все дерево придется перестраивать. Один из способов обойти эту проблему – хранить и визуализировать статические и подвижные части отдельно друг от друга.
Предварительные расчеты
Для начала нужно разбить или разделить игровую карту на выпуклые многоугольники. Выпуклый многоугольник – это многоугольник, все внутренние углы которого меньше или равны 180 градусам. Например, следующие фигуры являются выпуклыми многоугольниками (рис. 1).
Рис. 1. Выпуклые многоугольники
Однако следующие фигуры не являются выпуклыми (рис. 2).
Рис. 2. Невыпуклые многоугольники
Если карта рассматривается как невыпуклый многоугольник, мы можем разделить его на два «подполигона», проведя через него разделительную линию. Например, рассмотрим следующую карту (рис. 3).
Рис. 3. Разделение карты на два «подполигона»
Разделив этот полигон на два, мы создали два «подполигона». Это деление можно представить в виде простого дерева (рис. 4).
Рис. 4. Простое дерево
Теперь можно рекурсивно разделить каждый из двух «подполигонов». Каждое деление создает новую «ветвь» дерева. Рекурсия продолжается до тех пор, пока карта не будет разделена на выпуклые полигоны, которые являются «листьями» дерева (рис. 5).
Рис. 5. Рекурсивное разделение карты
В итоге мы получили BSP дерево, которое можно использовать для рендеринга.
Рендеринг
Рендеринг с использованием деревьев BSP также выполняется с использованием рекурсивного алгоритма. Наиболее распространенный подход – начать с корневого узла (вершины дерева) и рекурсивно двигаться вниз. Нужно сохранять дерево сбалансированным: это уменьшает объем рекурсии. Рекурсия на большую глубину может значительно замедлить рендеринг.
Для любого конкретного узла существует разделительная линия, где он разделяется на два подузла. Если эту линию продлить до бесконечности, то точка обзора, с которой мы выполняем рендеринг, может считаться находящейся либо на левой, либо на правой стороне. Сторона, на которой находится точка обзора, определяет, какой из подузлов рендерится первым (рис. 6).
Рис. 6. Рендеринг в зависимости от точки обзора
Обратите внимание, что на самом деле существует два способа выполнения рендеринга: «Back-to-front» и «Front-to-back». В «Back-to-front» рендерере дальние стены визуализируются первыми и закрываются более близкими стенами. Недостатком «Back-to-front» рендеринга является перерисовка – прорисовываются части стен, которые закрываются более близкими и не видны. Этот метод требует больше времени для отрисовки кадра. Рендерер «Front-to-back» работает наоборот: более близкие стены рендерятся первыми, а более отдаленные стены обрезаются по уже нарисованным. Поскольку он не имеет перерисовки, почти все практические рендереры BSP используют метод «Front-to-back», так как этот метод требует меньше времени для отрисовки кадра в сравнении с методом «Back-to-front».
Пример псевдокода для простого рендерера «Back-to-front» будет выглядеть следующим образом:
function render(узел)
{
if узел является листом
{
вывести узел на экран
}
else
{
определить с какой стороны разделительной линии находится точка обзора
if если точка обзора находится на левой стороне
{
render (правый подузел)
render (левый подузел)
}
else
{
render (левый подузел)
render (правый подузел)
}
}
}
Другие применения BSP-деревьев
Помимо упорядочивания видимости, деревья BSP также имеют ряд других применений. Одно из них заключается в том, что иерархическое разделение карты, позволяет исключить большие части карты из процесса рендеринга – если весь конкретный узел находится вне поля зрения точки обзора, то он может быть исключен из рендеринга. Это быстрый и эффективный способ ускорения движка рендеринга. Дерево также можно использовать для создания ряда других эффектов, например теней.
Заключение
Двоичное разбиение пространства является чрезвычайно полезным представлением информации о пространстве в 3D движках. Метод значительно упрощает задачу расчёта видимости геометрии, что сокращает время расчета кадра. Данный факт особенно важен для видеоигр и других систем реального времени. К минусам двоичного разбиения пространства можно отнести то, что необходим предварительный расчёт для преобразования карты в BSP дерево и то, что карта должна быть статичная.
