Как мне проверить, является ли данное дерево BSP оптимальным?

Question

У меня есть многоугольный суп из треугольников, для которого я хотел бы построить дерево BSP. Моя текущая программа просто создает дерево BSP, вставляя случайный треугольник из модели по одному, пока все треугольники не будут израсходованы, затем проверяет глубину и ширину дерева и запоминает лучший результат, который он достиг (самая низкая глубина, самая низкая ширина ).

По определению, лучшая глубина будет log2 (n) (или меньше, если копланарные треугольники сгруппированы?), Где n - это количество треугольников в моей модели, а наилучшая ширина равна n (что означает, что расщепление не имеет произошло). Но есть определенные конфигурации треугольников, для которых эта вершина никогда не будет достигнута.

Существует ли эффективный тест для проверки качества моего BSP-дерева? В частности, я пытаюсь найти способ, чтобы моя программа перестала искать более оптимальную конструкцию.

Answer 1

Построение оптимального дерева является NP-полной задачей. Определить, является ли данное дерево оптимальным, по сути, та же проблема.

Из этого BSP faq :

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

Answer 2

Случайное построение деревьев BSP, пока вы не наткнетесь на хорошее, будет действительно, очень неэффективно.

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

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

Но, в конце концов, вы не можете надеяться получить абсолютно оптимальное дерево для любых реальных данных, поэтому вам, возможно, придется согласиться на «достаточно хорошее».

Answer 3

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

Вам нужно будет отобрать этот критерий и придумать систему оценки, чтобы решить, какая из них наиболее подходит для плоскости разбиения. Например, чем дальше баланс, тем больше очков он теряет. Если это вызывает 20 сплитов, то штраф составляет -5 * 20 (например). Выберите тот, который набирает больше всего баллов. Вам не нужно выбирать каждый полигон, просто найдите довольно хороший.