Comment tester si un arbre BSP donné est optimal?

Question

J'ai une soupe polygonale de triangles pour laquelle j'aimerais construire un arbre BSP. Mon programme actuel construit simplement un arbre BSP en insérant un triangle aléatoire du modèle un à la fois jusqu'à ce que tous les triangles soient consommés, puis il vérifie la profondeur et la largeur de l'arbre et se souvient du meilleur score obtenu (profondeur la plus basse, largeur la plus faible). Par définition, la meilleure profondeur serait log2 (n) (ou moins si les triangles coplanaires sont groupés?) Où n est le nombre de triangles dans mon modèle, et la meilleure largeur serait n (ce qui signifie ne pas diviser s'est produit). Mais, il y a certaines configurations de triangles pour lesquelles ce pinacle ne serait jamais atteint.

Existe-t-il un test efficace pour vérifier la qualité de mon arbre BSP? Plus précisément, j'essaie de trouver un moyen pour mon programme de savoir qu'il devrait cesser de chercher une construction plus optimale.

Answer 1

La construction d'un arbre optimal est un problème NP-complet. Déterminer si un arbre donné est optimal est essentiellement le même problème.

De cette BSP faq:

Le problème est l'une des division par rapport équilibrage des arbres. Ce sont des exigences exclusives mutuellement . Vous devez choisir votre stratégie pour construire un bon arbre basé sur comment vous l'intention de utiliser l'arbre.

Answer 2

Construire aléatoirement des arbres BSP jusqu'à ce que vous en trouviez un bon sera vraiment, vraiment inefficace. Au lieu de choisir un tri au hasard à utiliser comme un plan split, vous voulez essayer plusieurs (peut-être tous, ou peut-être un échantillonnage aléatoire) et en choisir un selon une heuristique. L'heuristique est typiquement basée sur (a) l'équilibre des nœuds enfants qui en résultent, et (b) le nombre de tris qu'elle diviserait.

Vous pouvez sacrifier la performance et la qualité en considérant un échantillonnage plus petit ou plus grand de tris en tant que plans dédoublés candidats. Mais à la fin, vous ne pouvez pas espérer obtenir un arbre totalement optimal pour n'importe quelles données du monde réel, alors vous devrez peut-être vous contenter d'un "assez bon".

Answer 3

• Essayez de choisir les avions qui (pourraient) se diviser par les la plupart des avions comme des avions de séparation. Les plans de fractionnement ne peuvent pas être divisés. Essayez de choisir un avion ayant le même nombre de plans à l'avant qu'à l'arrière. Essayez de choisir un plan qui ne provoque pas trop de divisions.
• Essayez de choisir un plan qui est coplanaire avec beaucoup d'autres surfaces

Vous aurez à goûter à ces critères et arriver à un système de notation de décider lequel est le plus susceptible d'être un bon choix pour un plan de fractionnement. Par exemple, plus le solde est déséquilibré, plus il perd de points. S'il cause 20 divisions, alors la pénalité est de -5 * 20 (par exemple). Choisissez celui qui marque le mieux. Vous n'avez pas besoin d'échantillonner tous les polygones, cherchez juste un très bon polygone.