}
prevP = curP; prevF = curF;
* f 1 = new Facet ( p1, countl );
* f2 = new Facet ( p2, count2 );
}

Естественным образом возникает вопрос о построении дерева, в некотором смысле оптимального. Существует два основных критерия оптимальности:

получение как можно более сбалансированного дерева (когда для любого узла количество граней в правом поддереве минимально отличается от количества граней в левом поддереве); это обеспечивает минимальную высоту дерева (и соответственно наименьшее количество проверок);

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

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

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

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

После того, как это дерево построено, построение изображения осуществляется в зависимости от используемого проектирования. Ниже приводится процедура построения изображения для центрального проектирования с центром в точке с.

10. Удаление невидимых линий и поверхностей О void drawBSPTree ( BSPNode * tree ) {

if ((tree -> n & с ) > tree -> d ) {

if (tree -> right != NULL)
drawBSPTree (tree -> right);

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