Binary Space Partitioning

Grundidee und Aufbau

Binary Space Partitioning (BSP; deutsch binäre Raumpartitionierung) ist eine Technik der Informatik, die multidimensionale Daten mithilfe von Hyperebenen in Teilräume zerlegt. Die daraus entstehende Datenstruktur heißt BSP-Baum und ist ein Binärbaum. Jeder innere Knoten steht für eine Teilungsebene; seine beiden Teilbäume stehen für die beiden durch diese Ebene gebildeten Raumteile.

Der gesamte Raum wird zuerst durch eine zunächst beliebig wählbare Ebene geteilt. Anschließend wird jeder Halbraum nach demselben Prinzip rekursiv, also wiederholt auf seine Teilräume angewendet, weiter zerlegt. Die Unterteilung endet meist, wenn ein Teilraum nur noch ein Datenelement der Ausgangsmenge enthält, etwa ein Dreieck oder Polygon.

Ein Spezialfall sind k-d-Bäume, auch axis-aligned BSP-Trees (achsenparallele BSP-Bäume). Bei ihnen verlaufen die teilenden Hyperebenen immer entlang der Achsen des Koordinatensystems.

Wahl der Teilungsebenen und Speicherformen

Bei geometrischen Objekten werden Teilungsebenen aus praktischen Gründen oft mit Ebenen vorhandener Polygone gleichgesetzt. Für einen aktuellen Teilraum wird ein Polygon ausgewählt; dessen Ebene teilt den Teilraum weiter.

Bei der Auswahl sind zwei Ziele wichtig: Auf beiden Seiten der Ebene sollen ungefähr gleich viele Polygone liegen, und möglichst wenige Polygone sollen von der Ebene geschnitten werden. Geschnittene Polygone müssen nämlich zerlegt werden. Dadurch entstehen mehr Polygone und beispielsweise das Zeichnen benötigt mehr Zeit. Für eine gute Laufzeit bei der späteren Traversierung, also beim Durchlaufen des Baums, wird üblicherweise ein balancierter Baum angestrebt.

Die Ausgangsdaten können nur in Blättern gespeichert werden; dann heißt der Baum leaf-based („blattbasiert“). Sie können aber auch zusätzlich in inneren Knoten liegen, etwa wenn das zur Teilung gewählte Polygon mit der Ebene im selben Datenelement gespeichert wird oder einem der entstandenen Teilräume zugeschlagen wird. Diese Form heißt node-based („knotenbasiert“).

Rekursiver Algorithmus für Polygone

Ein rekursiver Algorithmus für eine Liste ebener Polygone arbeitet so:

• Zuerst wird ein Polygon P ausgewählt. Für P wird ein Knoten N erzeugt, und P wird der Polygonliste von N hinzugefügt.
• Jedes andere Polygon wird im Vergleich zu der Ebene von P eingeordnet: Liegt es vollständig davor, kommt es in die Liste vor P; liegt es vollständig dahinter, kommt es in die Liste hinter P.
• Schneidet die Ebene von P ein Polygon, wird dieses in zwei Polygone geteilt. Die Teilpolygone werden den Listen vor beziehungsweise hinter P zugeordnet.
• Liegt ein Polygon in derselben Ebene wie P, wird es ebenfalls der Polygonliste von Knoten N hinzugefügt.
• Der Algorithmus wird anschließend jeweils auf die Polygonlisten vor und hinter P angewendet.

Die Rekursion endet, wenn die Liste der Polygone vor P oder die Liste der Polygone hinter P leer ist.

Einsatz und Baumdurchlauf

BSP-Bäume werden vor allem zur räumlichen Unterteilung geometrischer Objekte eingesetzt, besonders in Grafik-Engines von Computerspielen für unveränderliche Teile der Spielwelt. Sie können Berechnungen wie Kollisionserkennung und Verdeckungsberechnung von Polygonen wesentlich beschleunigen. Genannt werden die Game Engine der Super-NES-Version von Wolfenstein 3D sowie die Engines von Doom, der Quake-Reihe und Doom 3. Bei Doom handelt es sich um zweidimensionales BSP: Die Teilungsebenen sind dort Teilungsgeraden.

Beim Raytracing dienen BSP-Bäume als Beschleunigungstechnik. Sie sollen bewirken, dass ein Schnittpunkttest nur mit möglichst wenigen Primitiven durchgeführt werden muss. Weitere Methoden der hierarchischen Raumunterteilung sind Quadtrees und Octrees.

Für die Zeichenreihenfolge kann ein BSP-Baum aus Sicht eines Betrachters durchlaufen werden: Von einem Knoten werden zuerst die Elemente hinter dessen Strecke oder Ebene gezeichnet, danach die Strecke beziehungsweise das Polygon des Knotens und anschließend die Elemente davor, also auf der Seite des Betrachters. Im ersten Beispiel mit vier Strecken ergibt sich vom eingezeichneten Betrachter aus die Reihenfolge 3, 2a, 4, 1, 2b. Strecke 1 teilt dabei Strecke 2 in 2a und 2b. Die Orientierung der Normalen klassifiziert die beiden Seiten als vor oder hinter einer Strecke und entscheidet damit über linken beziehungsweise rechten Teilbaum.

Beispiel einer Objektzerlegung

In der Computergrafik kann ein BSP-Baum auch Geometrieinformationen eines Objekts speichern. Solche Bäume werden manchmal leaf-storing BSP trees genannt, weil die Informationen vorrangig in den Blättern abgelegt werden. Im dargestellten Beispiel zeigen alle Normalen der Kanten in das Innere des Objekts; sie dienen dazu, Kanten einer Vorder- oder Rückseite zuzuordnen.

Die Zerlegung beginnt an einer beliebig gewählten Kante, im Beispiel D, die zur Wurzel wird. Die Wahl dieser Startkante beeinflusst die spätere Traversierungsgeschwindigkeit; ein balancierter Baum ist deutlich günstiger. An der ins Unendliche verlängerten Kante D werden die Kanten A und G geschnitten und deshalb jeweils geteilt. So entstehen unter anderem A₁, A₂, G₁ und G₂.

Danach werden die Teilbäume wiederholt nach demselben Schema geteilt: Im einen Teilbaum wird N gewählt, wodurch A₁ erneut und K geteilt werden; anschließend werden beispielsweise I, J und H als Teilungskanten verwendet. Der gezeigte endgültige Baum ist nur eine mögliche Lösung. Weil für Wurzel und weitere Knoten unterschiedliche Kanten gewählt werden können, sind viele korrekte BSP-Bäume für denselben Raum möglich. Ihre Leistungsfähigkeit bei der Traversierung kann je nach Anwendung stark unterschiedlich sein. In den meisten Fällen soll ein entarteter Baum vermieden werden.