}
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);