Einsteigerguide: Was ist ein Binary Space Partitioning Tree (BSP Tree)?
Ein Binary Space Partitioning Tree (BSP Tree) ist eine Datenstruktur, die verwendet wird, um Objekte innerhalb eines Raumes zu organisieren. Im Bereich der Computergrafik gibt es Anwendungen zur Entfernung versteckter Oberflächen (Hidden Surface Removal) und für das Raytracing. Ein BSP-Baum ist eine rekursive Unterteilung des Raumes, die jedes Linsensegment (oder Polygon) als Schnittebene behandelt, mit der alle verbleibenden Objekte im Raum entweder als „front“ oder „back“ dieser Ebene kategorisiert werden. Mit anderen Worten, wenn eine Partition in den Baum eingefügt wird, wird sie zunächst in Bezug auf den Root Node und anschließend rekursiv in Bezug auf jedes geeignete Child kategorisiert. Weitere Informationen zu BSP-Trees finden Sie im BSP-Tree.
So verwenden Sie dieses Applet.
Sie können Linsensegmente im ersten Canvas-Bereich zeichnen (die erste Linie bewirkt, dass Java eine gewisse Initialisierung durchgeführt, so dass es viel länger dauert, als nachfolgende zu zeichnen). Die Segmente werden in der Reihenfolge Ihrer Nummerierung erstellt und der Baum wird erstellt, indem jedes Segment in der Reihenfolge seiner Nummerierung eingefügt wird. Wenn eine Partition geteilt werden muss, haben der vordere und hintere Teil der Partition ein „f“ und ein „b“ an ihren jeweiligen Namen angehängt. Wenn beispielsweise die Partition 1 die Schnittebene der Partition 0 durchquert, dann wird der Teil der Partition 1, der sich von der Partition 0 befindet, „1f“ genannt, und der Teil auf der Rückseite wird „1b“ genannt.
Sie können den magentafarbenen Eyepoint bewegen, indem Sie ihn anklicken, ziehen und wenn Sie auf die Pfeilspitze in der Nähe des Endes des Blickvektors des Augenpunktes klicken und ziehen, können Sie die Kamera drehen, die die Pseudo-3D-Szene darstellt. Im Fahrmodus zeigt der Look-Vektor in die Richtung, in die Sie den Eyepoint bewegen. Die BSP-Baumklassifizierung des Eyepoints wird im BSP-Baumdiagramm als magentafarbener Punkt dargestellt.
Wenn der „Drive Mode“ aktiviert ist, zeigt der Look-Vektor beim Bewegen des Eyepoints automatisch in Bewegungsrichtung, um den Eindruck zu erwecken, durch die 3D-Szene zu fahren.
Wenn die Zeichnung des Baumes zu groß für sein Canvas wird, klicken und ziehen Sie dieses Canvas hinein, um den Baum zu verschieben.
Technische Hinweise.
Der BSP Tree Algorithmus.
Der BSP-Tree wird erstellt, indem jedes Segment in nummerierter Reihenfolge in den Baum eingefügt wird. Um dem Benutzer ein besseres Verständnis der Demo zu ermöglichen, wird nicht versucht, den BSP-Baum auszuwählen, der die minimale Aufteilung der Segmente bewirkt. Dies geschieht normalerweise, weil es die Größe des Baumes minimiert und diesen effizienter macht. Darüber hinaus wird nicht versucht, einen ausgewogenen Baum zu erzeugen, was normalerweise auch wünschenswert wäre, da es degenerative Fälle wie solche verhindert, in denen die Tiefe des Baumes ungefähr der Anzahl der Partitionen entspricht. Da jede Partition in Bezug auf 0 (lg(n)) andere Partitionen klassifiziert werden muss, ist die erwartete Laufzeit für den Aufbau dieses BSP-Baums O (n*lg(n)).
Der Grafik-Algorithmus.
Das Diagramm wird mit dem Reingold und Tilford Rooted Tree Drawing Algorithmus erstellt.
„Nachdem Sie die linken und rechten Teilbäume gezeichnet haben, platzieren Sie die Zeichnungen der Teilbäume im horizontalen Abstand 2. Platzieren Sie die Wurzel eine Ebene über und auf halbem Weg zwischen den Childs. Wenn es jedoch nur ein Child gibt, legen Sie die Wurzel in einem horizontalen Abstand 1 vom Child.“
Der Rendering-Algorithmus.
Die Pseudo-3D-Szene wird gerendert, indem der Eyepoint in Bezug auf das Wurzelsegment klassifiziert, alle Segmente auf der anderen Seite dieses Segments rekursiv, dieses Segment und anschließend alle Segmente auf der gleichen Seite dieses Segments rekursiv gezeichnet. Wenn der Eyepoint ein Segment schneidet, sehen wir es kantengerade, so dass es nicht gezeichnet wird. Da jedes Segment genau einmal beim Zeichnen der Szene besucht wird, kann die Szene in 0(n)-Zeit gerendert werden. Hier ist der Pseudocode für eine Methode auf einer BSP-Baum-Tree-Klasse, die diesen Algorithmus implementiert.
Wenn wir bereit sind, die Szene zu zeichnen, werden Eyepoint und Look-Vektor verwendet, um das Koordinatensystem für den Kameraraum zu bestimmen. Anschließend wird jedes Polygon mit Hilfe des folgenden Algorithmus gezeichnet:
Das war unser Beitrag zum Binary Space Partitioning. Wenn Sie noch Fragen oder Anregungen haben sollten, hinterlassen Sie uns unten einen Kommentar.
Vielen Dank für Ihren Besuch.