BSP-дерево

Общие принципы

BSP (Binary Space Partitioning) — метод двоичного разбиения пространства. Существует очень давно и отлично зарекомендовал себя в трёхмерных играх.

Смысл BSP заключается в том, чтобы представить находящиеся в пространстве полигоны в виде двоичного дерева. Такая структура позволяет установить взаимосвязи "кто за кем" для всех полигонов. Это нужно для эффективной Z-сортировки и корректного отображения пересекающихся 3D-моделей. Также BSP используется для оптимизации расчётов в механизме обнаружения столкновений.

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

Особенности реализации в Alternativa3D

Узлы содержат несколько полигонов

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

Мобильность

Для каждого 3D-объекта существует понятие мобильности. Мобильность определяет как близко к корню будет располагаться объект при построении BSP-дерева. Менее мобильные объекты располагаются ближе к корню, более мобильные – дальше от корня. Это позволяет уменьшить количество перестраиваемых узлов дерева при изменении положения и конфигурации объектов в сцене. У каждого объекта есть собственная и эффективная мобильность. Собственная мобильность определяется природой объекта (например, его размером, массой и т.п.) и может быть изменена разработчиком в любое время. Эффективная мобильность является суммой собственных мобильностей самого объекта и всех его предков по иерархии объектов в сцене. Положение в дереве определяется именно эффективной мобильностью.

Рассмотрим пример: стоящий на земле стол (мобильность 1), а на столе лежит яблоко (мобильность 2). Эффективная мобильность стола в этом случае будет равна единице, яблока – трём. В BSP-дереве ближе к корню будут располагаться полигоны стола, а за ними полигоны яблока. Предположим, что яблоко упало со стола на землю (в иерархии объектов сцены яблоко поменяло родителя со стола на поверхность земли). Эффективная мобильность яблока в таком случае изменится и станет равной двум, всё ещё оставаясь больше, чем эффективная мобильность стола. После перестроения BSP-дерева полигоны яблока всё так же будут более удаленными от корня. Пусть стол после этого погрузили в автомобиль, имеющий мобильность 3. В результате эффективная мобильность стола окажется равной четырём и станет больше, чем у яблока. После перестроения BSP-дерева полигоны стола окажутся дальше от корня дерева, чем полигоны, образующие яблоко.

Анализ сплиттеров

При построении сцены разработчик может преследовать разные цели — минимизировать количество рассечений для минимизации количества полигонов или сделать BSP-дерево более сбалансированным, что может быть полезно для определения столкновений и отсечения невидимых узлов. Для управления видом дерева в движке реализован механизм анализа качества сплиттеров. Управляя параметром качества, разработчик может менять вид дерева от максимально сбалансированного до содержащего минимальное количество полигонов. Однако следует помнить, что при включённом режиме анализа на построение BSP-дерева требуется больше вычислительных ресурсов.

Быстрое удаление веток

При удалении полигонов из BSP-дерева анализируется необходимость удаления построенных на них узлов. Если в узлах ещё остаются полигоны, удаление не происходит. В случае удаления узлов, происходит анализ быстрого отцепления веток (например, если изменение коснулось корневого узла, всё дерево будет пересобрано за один заход). Также учитывается возможность удаления узла без перестроения его дочерних веток (так называемое "переприцепление").

Полигоны хранят свои фрагменты

При рассечении полигонов получившиеся фрагменты сохраняют информацию о родителе и друг о друге. Это позволяет при изменении дерева частично собирать полигоны из фрагментов, вместо их полной перевставки.

Анимация

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

Советы и технические приёмы

Минимизируйте использование BSP для анимации геометрии

Даже с учётом оптимизаций при массовой анимации геометрии движок будет постоянно перестраивать BSP-дерево. Перестройка включает в себя сборку примитивов, анализ сплиттеров и построение новых веток. Это может занимать много процессорного времени (в зависимости от количества полигонов и структуры дерева) и привести к ощутимому замедлению проигрывания. Для ускорения анимации планируется внедрение простой Z-сортировки (по средней удалённости от камеры) и локальные BSP-деревья.

Назначайте мобильность

Использование уровня мобильности объектов повышает контроль над построением BSP-дерева.

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

Используйте вспомогательную геометрию

• Для дополнительного контроля за BSP-деревом может пригодиться построение невидимой геометрии (без материалов) с низкой мобильностью. Например, моделируя сложную конструкцию, можно принудительно разделить её части, чтобы фрагментирование было в их пределах.
• При частом изменении определённой части модели имеет смысл ограничить область невидимой геометрией (полигонами без материалов), что позволит разделить в разные ветки внешнее и внутреннее пространство. В итоге анимация внутри области будет иметь небольшую фрагментацию и не будет влиять на остальное окружение. Например, внутри помещения можно сделать невидимые грани, чтобы архитектура стен не влияла на фрагментацию мебели.