Описание технологий. Binary Space Partitioning (BSP) дерево

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

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

Пример BSP-сортировки (слева) и обычной загрузки (справа) представлен на рисунке 5.9.

Рисунок 5.9 – BSP-сортировка и обычная загрузка

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

Структура BSP-дерева приведена на рисунке 5.10.

Рисунок 5.10 – Структура BSP-дерева

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