Как мне проверить, оптимально ли данное дерево BSP?
У меня есть многоугольный суп из треугольников, для которого я хотел бы построить BSP-дерево. Моя текущая программа просто строит BSP-дерево, вставляя случайный треугольник из модели по одному до тех пор, пока все треугольники не будут поглощены, затем она проверяет глубину и ширину дерева и запоминает лучший результат, полученный им (наименьшая глубина, наименьшая ширина ).
По определению, наилучшая глубина будет log2 (n) (или меньше, если сгруппированы копланарные треугольники?), Где n - количество треугольников в моей модели, а наилучшая ширина - n (то есть разделения не произошло). Но есть определенные конфигурации треугольников, для которых эта вершина никогда не будет достигнута.
Есть ли эффективный тест для проверки качества моего дерева BSP? В частности, я пытаюсь найти способ, чтобы моя программа знала, что ей следует перестать искать более оптимальную конструкцию.
Ответы 3
Построение BSP-деревьев случайным образом до тех пор, пока вы не найдете хорошее, будет действительно неэффективно.
Вместо того, чтобы выбирать три наугад для использования в качестве разделенной плоскости, вы хотите попробовать несколько (может быть, все из них, или, может быть, случайную выборку) и выбрать одно в соответствии с некоторой эвристикой. Эвристика обычно основана на (а) том, насколько сбалансированными будут результирующие дочерние узлы, и (б) сколько трис он разделит.
Вы можете найти компромисс между производительностью и качеством, рассматривая меньшую или большую выборку трисов в качестве кандидатов на разделение плоскостей.
Но, в конце концов, вы не можете надеяться получить полностью оптимальное дерево для любых реальных данных, поэтому вам, возможно, придется довольствоваться «достаточно хорошим».
Построение оптимального дерева - это NP-полная задача. Определение того, является ли данное дерево оптимальным, по сути, та же проблема.
Из этого BSP часто задаваемые вопросы:
The problem is one of splitting versus tree balancing. These are mutually exclusive requirements. You should choose your strategy for building a good tree based on how you intend to use the tree.
В общем, проверка того, является ли решение оптимальным, и поиск оптимального решения не обязательно должны принадлежать к одному классу сложности. Знаете ли вы, что проверка оптимальности BSP-дерева является NP-полной?
- Попробуйте выбрать самолеты, которые (потенциально) могут быть разделены наибольшим количеством плоскостей, как разделяющие плоскости. Плоскости разделения нельзя разделить.
- Попробуйте выбрать самолет, у которого примерно такое же количество самолетов спереди, как и сзади.
- Попробуйте выбрать самолет, который не вызывает слишком много расколов.
- Попробуйте выбрать плоскость, которая копланарна множеству других поверхностей.
Вам нужно будет выбрать эти критерии и придумать систему баллов, чтобы решить, какой из них, скорее всего, будет хорошим выбором для плоскости разделения. Например, чем дальше он теряет баланс, тем больше очков он теряет. Если это вызывает 20 разбиений, то штраф составляет -5 * 20 (например). Выберите тот, который набирает больше всего очков. Вам не нужно пробовать каждый многоугольник, просто найдите довольно хороший.
Построение оптимального BSP-дерева завершено на NP. Но вы можете построить очень хорошую с помощью эвристики и частичного поиска "достаточно хороших" плоскостей разбиения.
Фактически, даже одно случайное BSP-дерево имеет асимптотически оптимальную сложность в случае точечных множеств.