Для построения правильного изображения сцены необходимо сначала выводить грани из дальнего кластера, а затем из ближнего.

Применим предложенный подход для упорядочения граней внутри каждого кластера. Для этого выберем две плоскости, разбивающие каждый из кластеров на два подкластера.

Повторяя описанный процесс до тех пор, пока в каждом получившемся кластере останется не более одной грани (рис. 10.33).

Получаем в результате двоичное дерево (Binary Space Partitioning Tree). Узлами этого дерева являются плоскости, производящие разбиение.Пусть плоскость, производящая разбиение, задается уравнением

(р. п) = d.

Каждый узел дерева можно представить в виде следующей структуры

struct BSPNode
{
Facet * facet; // corresponding facet Vector3D n; .// normal to facet ( plane ) float d; // plane parameter
BSPNode* left; //left subtree BSPNode* right; //right subtree
};

left указывает на вершину поддерева, содержащуюся в положительном полупространстве (р, п) > d. right - на поддерево, содержащееся в отрицательном полупространстве (р, п) < d

Обычно в качестве разбивающей плоскости выбирается плоскость, проходящая через одну из граней. Все грани, пересекаемые этой плоскостью, разбиваются вдоль

Удаление невидимых линий и поверхностей

10. Удаление невидимых линий и поверхностей нее. а получившиеся при разбиении части помешаются в соответствующие поддеревья.

Рассмотрим сцену, представленную на рис. 10.34. Плоскость, проходящая через грань 5, разбивает грани 2 и 8 на части 2', 2й, 8' и 8", и все множество граней (с учетом разбиения граней 2 и 8) распадается на два кластера (1,8\2') и (2м, 3, 4, 6, 7, 8"). Выбрав для первого кластера в качестве разбивающей плоскости плоскость, проходящую через грань 6, разбиваем его на два подкластера (7,8м) и (2",3,4). Каждое следующее разбиение будет лишь выделять по одной грани из оставшихся кластеров. В результате получим следующее дерево (рис. 10.35).

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


⇐ Предыдущая| |Следующая ⇒