BSP Tree

Der Begriff Binary Space Partitioning (BSP, „binäre Raumpartitionierung“) bezeichnet eine Technik zur Partitionierung multidimensionaler Daten durch eine Menge von Hyperebenen. Die so erstellte Datenstruktur ist ein Binärbaum und wird BSP-Baum genannt.

Die wohl verbreitetste Anwendung von BSP-Bäumen ist die räumliche Unterteilung geometrischer Objekte. Vor allem findet BSP bei Game Engines von Computerspielen (insbesondere bei Ego-Shootern) für Objekte oder Teile der „Welt“, die sich während des Spiels geometrisch nicht mehr verändern, Verwendung. Eine weitere Anwendung findet sich beim Raytracing.

Ein Spezialfall der BSP-Bäume sind kd-Bäume, oft auch als axis-aligned BSP-Trees (achsenparallele BSP-Bäume) bezeichnet. Bei kd-Bäumen sind die unterteilenden Hyperebenen immer entlang der Achsen des Koordinatensystems ausgerichtet.

Verfahren

Beim BSP wird der gesamte Raum anfangs durch eine (zunächst beliebig wählbare) Teilungsebene in zwei Teile geteilt. Für beide Halbräume wird dann das gleiche gemacht wie zuerst mit dem gesamten Raum, das heißt, die Welt wird rekursiv immer weiter unterteilt. Jeder innere Knoten des Binärbaumes repräsentiert somit eine Teilungsebene, während die zwei Unterbäume eines inneren Knoten dann jeweils einen Unterraum repräsentieren. Das Ende der Unterteilung ist meist dann erreicht, wenn in einem Teilraum nur mehr ein Datenelement der Ausgangsmenge (z. B. ein geometrisches Grundobjekt wie ein Dreieck oder Polygon) vorhanden ist.

Die Teilungsebenen fallen aus praktischen Gründen oft mit den Polygonen der geometrischen Objekte zusammen. Beim Erstellen des BSP-Baums wird dann ein Polygon aus dem aktuellen Teilraum gewählt, mit dessen Ebene der Teilraum weiter unterteilt wird. Dabei wird einerseits darauf geachtet, dass sich ungefähr gleich viele Polygone auf jeder Seite der gewählten Ebene befinden, andererseits, dass möglichst wenige Polygone des Teilraumes durch die Ebene zerschnitten werden, weil das Zerschneiden zu mehr Polygonen führt, wodurch sich die benötigte Zeit erhöht, um z. B. die Polygone zu zeichnen.

Die Daten der Ausgangsmenge können entweder ausschließlich in den Blättern des Baumes oder sowohl in den Blättern als auch in den inneren Knoten gespeichert sein – beispielsweise, indem das Polygon, das zur Teilung verwendet wurde, einem der beiden entstandenen Teilräumen zugeschlagen wird oder direkt im gleichen Datenelement wie die Ebene gespeichert wird. Man nennt den BSP-Baum dann leaf-based („Blattbasiert“) bzw. node-based („Knotenbasiert“).

Anwendungen und Alternativen

Durch die BSP-Technik können viele Berechnungen, wie Kollisionserkennung oder die Verdeckungsberechnung von Polygonen, wesentlich schneller erfolgen. Beispiele für die Verwendung von Binary Space Partitioning in Computerspielen sind die Game Engines von Doom (dabei handelt es sich um zweidimensionales BSP, d. h. die Teilungsebenen sind eigentlich Teilungsgeraden), der Quake-Serie und von Doom 3.

Beim Raytracing werden BSP-Bäume als Beschleunigungstechnik verwendet, um nur bei möglichst wenigen Primitiven einen Schnittpunkttest durchzuführen.

Weitere Methoden zur hierarchischen Unterteilung des Raumes sind Quadtrees und Octrees.

Beispiel 1

Aufbauen des Baumes

Beispiel für eine Zerlegung mit vier Strecken

Im obigen Bild ist ein Beispiel für die Zerlegung eines Raumes mit vier Strecken zu sehen. In dem rötlichen Kasten sieht man den daraus resultierenden binären Baum.

Zunächst teilt Strecke 1 den Raum in zwei Halbräume (gekennzeichnet durch die blau gestrichelte Linie) und die Strecke 2 in die beiden Teilstrecken 2a und 2b. Die Orientierung der Normalen der Strecken klassifiziert die beiden Halbräume nun als einen Halbraum vor der Strecke und einen Halbraum dahinter. Folglich werden die (Teil)-Strecken, die sich davor befinden in den linken, die, die sich dahinter befinden, in den rechten Teilbaum des Baumes eingefügt und mit den beiden entstehenden Halbräumen fortgefahren.

Betrachtet man zunächst die Strecke 2b, so teilt diese den Raum wieder in zwei Halbräume vor Strecke 1. Jedoch befindet sich keine weitere Strecke im selben Halbraum vor ihr (Strecke 4 wurde durch die Zerlegung von Strecke 1 in den Bereich hinter Strecke 1 „verbannt“). Hinter Strecke 2b befindet sich mit der gleichen Argumentation ebenfalls nichts mehr, das in den Baum eingeordnet werden müsste und das Verfahren terminiert für diesen Teilbaum.

Strecke 2a hingegen teilt den Raum wieder in zwei Teilräume und Strecke 4 wird in den Halbraum davor, Strecke 3 in den Halbraum dahinter eingeordnet.

Die Strecken 3 und 4 zerteilen den Raum zwar erneut in jeweils wieder zwei Halbräume, fügen jedoch nichts weiter in den Baum ein, so dass der Baum im rötlichen Kasten entstanden ist.

Durchlauf des Baumes

Nimmt man nun den Betrachter dort an, wo sich der Kasten mit dem BSP-Baum befindet (die Blickrichtung ist hier nicht weiter wichtig), so ergibt sich die Durchlauf- und damit Zeichenreihenfolge der Strecken wie folgt:

Beginnend von der Wurzel (Knoten 1), werden zunächst die Knoten, die vom Betrachter aus gesehen hinter dieser Strecke liegen, gezeichnet, anschließend die Strecke selbst und danach die Strecken, die sich vor der Strecke - also auf der Seite des Betrachters - befinden.

Im vorliegenden Fall sieht der Durchlauf des Baumes wie folgt aus:

3, 2a, 4, 1, 2b

Zunächst betritt man den Baum über die Wurzel (1). Nun muss man zunächst alle Strecken hinter der Strecke 1 zeichnen und begibt sich also in den rechten Teilbaum und landet dort bei der Wurzel 2a. Nun muss man auch dort erst die Knoten hinter dieser Wurzel zeichnen und steigt wieder in den rechten Teilbaum ab und landet beim Knoten 3. Dieser ist ein Blatt und kann sofort ausgegeben werden. Danach wird Strecke 2a gezeichnet und anschließend die Knoten davor - also 4. Nun ist auch dieser Teilbaum abgearbeitet und man zeichnet schließlich die Knoten 1 und 2b.

Beispiel 2

In der Computergrafik wird der BSP-Baum häufig auch zum Speichern von Informationen über die Geometrie eines Objektes benutzt. Derartige BSP-Bäume werden manchmal als leaf-storing BSP trees bezeichnet, da die Informationen vorrangig in den Blättern abgelegt werden.

Beispiel für eine Zerlegung eines Objektes

Literatur

• Henry Fuchs u. a.: On Visible Surface Generation by A Priori Tree Structures. In SIGGRAPH ’80 Proceedings, S. 124–133. ACM, New York 1980, ISBN 0-89791-021-4
• Christer Ericson: Real-Time Collision Detection (The Morgan Kaufmann Series in Interactive 3-D Technology). Verlag Morgan Kaufmann, S. 349-382, Jahr 2005, ISBN 1-55860-732-3

Weblinks

• BSP FAQ (englisch)
• Java Applet zu BSP