¿Cómo puedo probar si un árbol BSP dado es óptimo?

Question

Tengo una sopa poligonal de triángulos para la que me gustaría construir un árbol BSP. Mi programa actual simplemente construye un árbol BSP insertando un triángulo aleatorio del modelo uno a la vez hasta que se consumen todos los triángulos, luego verifica la profundidad y la anchura del árbol y recuerda la mejor puntuación que obtuvo (profundidad más baja, anchura más baja). ).

Por definición, la mejor profundidad sería log2 (n) (¿o menor si los triángulos coplanares se agrupan?) donde n es el número de triángulos en mi modelo, y la mejor amplitud sería n (lo que significa que no hay división) ocurrió). Pero, hay ciertas configuraciones de triángulos para los cuales nunca se alcanzaría este pináculo.

¿Existe una prueba eficiente para verificar la calidad de mi árbol BSP? Específicamente, estoy tratando de encontrar una manera para que mi programa sepa que debería dejar de buscar una construcción más óptima.

Answer 1

La construcción de un árbol óptimo es un problema NP-completo. Determinar si un árbol dado es óptimo es esencialmente el mismo problema.

De esta Preguntas frecuentes sobre BSP :

  

El problema es uno de división contra   balanceo de árboles. Estos son mutuamente   Requisitos exclusivos. Debieras   elige tu estrategia para construir un   buen árbol basado en cómo pretendes   usa el árbol.

Answer 2

La construcción aleatoria de árboles BSP hasta que te encuentres con uno bueno será muy, muy ineficiente.

En lugar de elegir un tri al azar para usarlo como un plano dividido, desea probar varios (quizás todos ellos, o tal vez un muestreo aleatorio) y elegir uno de acuerdo con alguna heurística. La heurística generalmente se basa en (a) qué tan equilibrados serían los nodos secundarios resultantes y (b) cuántos tris se dividiría.

Puede intercambiar rendimiento y calidad considerando una muestra mayor o menor de tris como planos divididos candidatos.

Pero al final, no puedes esperar obtener un árbol totalmente óptimo para cualquier información del mundo real, por lo que es posible que tengas que conformarte con "lo suficientemente bueno".

Answer 3

• Trate de elegir planos que (potencialmente) puedan dividirse por la mayoría de los planos como planos divididos. La división de planos no se puede dividir.
• Trate de elegir un avión que tenga el mismo número de aviones en la parte delantera que en la parte trasera.
• Intenta elegir un avión que no cause demasiadas divisiones.
• Intente elegir un plano que sea coplanar con muchas otras superficies

Tendrá que probar estos criterios y crear un sistema de puntuación para decidir cuál es el más adecuado para un plano de división. Por ejemplo, cuanto más fuera de balance, más puntuación pierde. Si causa 20 divisiones, la penalización es de -5 * 20 (por ejemplo). Elige el que mejor puntúe. No tienes que muestrear todos los polígonos, solo busca uno bastante bueno.