Binary Space Partitioning

Binary Space Partitioning

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. BSP findet vor allem Verwendung 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. Eine weitere Anwendung findet sich beim Raytracing.

Ein Spezialfall der BSP-Bäume sind k-d-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.

Inhaltsverzeichnis

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


Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Binary space partitioning — (BSP) is a method for recursively subdividing a space into convex sets by hyperplanes. This subdivision gives rise to a representation of the scene by means of a tree data structure known as a BSP tree.In simpler words, it is a method of breaking …   Wikipedia

  • Binary Space Partitioning — Partition binaire de l espace Pour les articles homonymes, voir BSP. La partition binaire de l espace (binary space partitioning ou BSP) est un système utilisé par un moteur de jeu pour calculer des espaces pleins (bloquant) et vides (ou le… …   Wikipédia en Français

  • Binary space partitioning — Partition binaire de l espace Pour les articles homonymes, voir BSP. La partition binaire de l espace (binary space partitioning ou BSP) est un système utilisé par un moteur de jeu pour calculer des espaces pleins (bloquant) et vides (ou le… …   Wikipédia en Français

  • Binary Space Partitioning — …   Википедия

  • Binary Space Partition — 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… …   Deutsch Wikipedia

  • Binary tree — Not to be confused with B tree. A simple binary tree of size 9 and height 3, with a root node whose value is 2. The above tree is unbalanced and not sorted. In computer science, a binary tree is a tree data structure in which each node has at… …   Wikipedia

  • Partición binaria del espacio — Binary space partitioning o Partición Binaria del Espacio (BSP) es un método para subdividir recursivamente un espacio en elementos convexos empleando hiperplanos. Esta subdivisión da lugar a una representación de la escena por medio de una… …   Wikipedia Español

  • BSP (file format) — BSP is a map file extension used in games such as the Doom , Quake , and games that use Quake derived engines, such as the Half Life series. .BSP files use binary space partitioning to generate levels that can be rendered quickly while minimizing …   Wikipedia

  • Collision detection — For collision detection on networks see CSMA/CD Collision detection typically refers to the computational problem of detecting the intersection of two or more objects. While the topic is most often associated with its use in video games and other …   Wikipedia

  • Trie — A trie for keys A , to , tea , ted , ten , i , in , and inn . In computer science, a trie, or prefix tree, is an ordered tree data structure that is used to store an associative array where the keys are usually strings. Unlike a binary search… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”