Интернет магазин китайских планшетных компьютеров

Компьютеры - Двоичное разбиение пространства - Построение дерева

Пример построения
1. A — корень и набор отрезков на плоскости целиком.
2. A делится на B и C.
3. B делится на D и E.
4. D делится на полностью выпуклые F и G, которые и становятся листьями дерева.

Вышеприведенное определение описывает только свойства BSP-дерева, но не говорит как его построить. Как правило, BSP-дерево строится для набора отрезков на плоскости или полигонов в пространстве, представляющих некоторую фигуру или сцену. Рассмотрим алгоритм построения BSP-дерева для набора полигонов в пространстве:

1. Если заданное множество полигонов пустое, то закончить алгоритм;
2. Для заданного множества полигонов выбрать разбивающую плоскость S;
3. Рассечь все полигоны, пересекающиеся с S;
4. Отнести все полигоны, находящиеся с фронтальной стороны S, к фронтальному поддереву F, а все полигоны, находящиеся с обратной стороны S, к оборотному поддереву B;
5. Выполнить алгоритм рекурсивно для множества полигонов фронтального поддерева F;
6. Выполнить алгоритм рекурсивно для множества полигонов оборотного поддерева B.

Выбор разбивающей плоскости

Разбивающая плоскость выбирается таким образом, чтобы сбалансировать дерево, то есть чтобы число полигонов в фронтальном и оборотном поддереве было приблизительно одинаково:

min — N|)

где N — число полигонов с фронтальной стороны некоторой разбивающей плоскости i, N — число полигонов с оборотной стороны разбивающей плоскости i.