Wie teste ich, ob ein bestimmtes BSP Baum optimal ist?

Question

Ich habe eine Polygon-Suppe von Dreiecken, die Ich mag würde für einen BSP-Baum zu konstruieren. Mein aktuelles Programm einfach ein BSP-Tree-Konstrukte durch ein zufälliges Dreieck aus dem Modell einen nach dem anderen ein, bis alles Dreiecken verbraucht werden, dann überprüft er die Tiefe und Breite des Baumes und erinnert mich an die beste Punktzahl erreicht (niedrigste Tiefe, niedrigste Breite ).

Nach Definition wäre die beste Tiefe log2 (n) (oder weniger, wenn koplanare Dreiecken gruppiert sind?), Wobei n die Anzahl der Dreiecken in meinem Modell ist und die beste Breite wäre n (dh keine Aufspaltung hat aufgetreten). Aber es gibt bestimmte Konfigurationen von Dreiecken, für die dieser Zinne würde nie erreicht werden.

Gibt es einen effizienten Test, um die Qualität meines BSP-Tree für die Überprüfung? Insbesondere bin ich versucht, einen Weg für mein Programm zu finden, zu wissen, dass es für eine optimale Konstruktion der Suche aufhören sollte.

Answer 1

Aufbau eines optimalen Baum ist ein NP-vollständiges Problem. Feststellen, ob ein bestimmte Baum optimal ist, ist im Wesentlichen das gleiche Problem.

Von diesem BSP FAQ :

  

Das Problem ist einer der Spaltung im Vergleich   Baum Balancing. Diese sind für beide Seiten   exklusive Anforderungen. Du solltest   Wählen Sie Ihre Strategie ein für den Bau   guter Baum auf, wie Sie wollen   verwenden Sie den Baum.

Answer 2

Randomly Bau BSP Bäume, bis Sie auf eine gute Chance wirklich sein werden, wirklich ineffizient.

Statt einen tri zufällig bei der Wahl als Split-Ebene zu verwenden, mögen Sie mehr ausprobieren (vielleicht alle von ihnen, oder vielleicht eine Zufallsstichprobe) und eine auswählen, nach einiger Heuristik. Die Heuristik wird in der Regel auf Basis von (a), wie ausgewogen die entstehenden Tochterknoten wären, und (b) wie viele Tris es wäre geteilt.

Sie können durch Betrachtung eine kleinere oder größere Probenahme von Tris als Kandidaten Split-Flugzeuge Leistung und Qualität abwägen.

Aber am Ende, man kann nicht einen ganz optimal Baum für alle Daten der realen Welt zu bekommen hoffen, so dass Sie zu begleichen haben könnten ‚gut genug‘.

Answer 3

• Versuchen Ebene zu holen, dass (könnte möglicherweise) von den meisten Ebenen als Spaltebene aufgeteilt bekommen. Spaltebene können nicht geteilt werden.
• Versuchen eine Ebene auszuwählen, die auf die gleiche Anzahl von Ebenen vor, wie in close hat.
• Versuchen Sie, ein Flugzeug zu holen, die nicht zu viele verursacht Splits.
• Versuchen eine Ebene zu wählen, die mit vielen anderen Oberflächen koplanar

Sie werden diese Kriterien probieren haben und mit einem Punktesystem, kommen bis zu entscheiden, welche man am ehesten eine gute Wahl für eine Teilungsebene sein. Zum Beispiel verliert das weiter aus dem Gleichgewicht, desto mehr Punkte es. Wenn es 20 Splits verursacht, dann Strafe ist -5 * 20 (zum Beispiel). Wählen Sie das, dass am besten abschneidet. Sie müssen nicht jedes Polygon probieren, nur die Suche nach einem ziemlich gut.