Получающиеся деревья сильно зависят от выбора разбивающих граней. На рис. 2.22 приведено дерево для сцены с рис. 2.20 с другим порядком выбора разбивающих граней. Обратите внимание на отсутствие разбиения граней в этом случае.
При разбиении грани плоскостью производится классификация всех вершин грани относительно этой плоскости и разбиение тех ребер, вершины которых лежат в разных полупространствах; сами точки разбиения считаются принадлежащими каждому из получившихся многоугольников.
Естественным образом возникает вопрос о построении дерева, в некотором смысле оптимального. Существует два основных критерия оптималь получение как можно более сбалансированного дерева (когда для любого узла количество граней в правом поддереве минимально отличается от количества граней в левом поддереве); это обеспечивает минимальную высоту дерева (и соответственно наименьшее количество проверок);
минимизация количества разбиений; одним из наиболее неприятных свойств В8Р-деревьев является разбиение граней, приводящее к значительному увеличению их общего числа и, как следствие, к росту затрат (памяти и времени) на изображение сцены.
ности:
Удаление невидимых поверхностей
К сожалению, эти критерии, как правило, являются взаимоисключающими. Поэтому обычно выбирается некоторый компромиссный вариант; например, в качестве критерия выбирается сумма высоты дерева и количества разбиений с заданными весами.
Полный анализ реальной сиены с целью построения оптимального дерева из-за очень большого количества вариантов произвести практически невозможно. Поэтому обычно поступают следующим образом: на каждом шаге разбиения случайным образом выбирается небольшое количество кандидатов на разбиение и выбор наилучшего в соответствии с выбранным критерием производится только среди этих кандидатов.
В случае, когда целью является минимизация числа разбиений, можно воспользоваться следующим приемом: на очередном шаге выбирать ту грань, использование которой приводит к минимальному числу разбиений на данном шаге.