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

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

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

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

3 ответа

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

Из этого BSP faq:

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


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

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

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

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


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

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

licensed under cc by-sa 3.0 with attribution.