Лекция: BSP-деревья

BSP – бинарное разбиение пространства

BSP деpево — это в сущности некая стpуктуpа данных, котоpая будучи постpоена один pаз для некотоpого 3D обьекта позволяет потом без особых затpат вpемени соpтиpовать по удаленности повеpхности этого 3D обьекта пpи pассмотpении его с pазных точек зpения.

Пример: построим BSP-дерево для данного помещения

Возьмем в качестве корневого элемента сторону F

Для показа BSP-дерева можно воспользоваться алгоритмом:

Например, мы находимся в точке X. Обращаемся в корневой элемент BSP-дерева. Если мы находимся внутри по отношению к F, то мы идем по дереву во внешнюю ветвь. Выписываем элементы ветви в отдельный список D1AB1. Далее поднимаемся в F и выписываем значение F. Идем в правую ветвь в узел E. Если мы находимся внутри по отношению к E, то идем во внешнюю ветвь. Выписываем D2C1EB2C3GC2.

Определение понятия внешней стороны:

Пусть требуется определить расположение полигона 2 и 3 по отношению к полигону 1. Для этого используют тестовую функцию:

T=Ax+By+Cz+D

Если в T полигона 1 подставить узловые точки полигона 2 и все значения будут положительны, то полигон 2 относится к правой ветви BSP-дерева, если отрицательны – то к левой. Если знаки меняются, то полигоны пересекаются.

Алгоритм визуализации BSP-дерева

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