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

Question

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

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

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

Answer 1

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

Из этого часто задаваемого вопроса BSP :

  

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

Answer 2

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

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

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

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

Answer 3

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

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