BSP-Baum

Geschichte

Früher (als der Tiefenpuffer noch nicht so verbreitet war) wurden BSP-Bäume beim Rendering verwendet um die Polygone von hinten nach vorne zu zeichnen. Ironischerweise könnte man auch heutzutage noch BSP-Bäume verwenden um den Rendering-Prozess zu beschleunigen, indem man die Polygone von vorne nach hinten zeichnet, da der Tiefenpuffer-Test heutzutage sehr schnell ist. Da BSP-Bäume jedoch immer Polygon für Polygon gezeichnet werden müssten, verzichtet man üblicherweise auf diese Aufbereitung der Daten für einen schnellen Tiefenpuffer-Test.

Eigenschaften eines BSP-Baumes

Ein BSP-Baum ist ein Binärbaum, bei dem jeder Knoten eine Ebenengleichung besitzt. Diese Ebene teilt den Raum in 2 Hälften. Die Ebene des linken Knoten teilt wiederum den Halbraum vor der ersten Ebene in 2 Hälften, die Ebene des rechten Knoten teilt den Halbraum hinter der ersten Ebene. "Vor" bzw. "Hinter" wird hierbei durch die Ebenengleichung definiert, welche für die Punkte auf der einen Seite der Ebene ein positives, für alle Punkte auf der anderen Seite der Ebene jedoch ein negatives Ergebnis liefert.

Alle Polygone die eine der Ebenen eines höher gelegenen Knoten schneiden, werden an dieser Ebene in 2 Teile geschnitten. Dadurch ist die eine Hälfte des Polygons im vorderen und die andere Hälfte im hinteren Ast dieses Knoten zu finden. Da das teilen von Polygonen natürlich mehr Aufwand beim Zeichenvorgang dar stellt, ist die Anzahl der Polygone die geschnitten wurden natürlich ein wesentliches Qualitätskriterium bei der Erstellung eines BSP-Baumes.

Konvexe Bereiche an den Astenden würden im BSP-Baum zu einer Liste degeneriert, deshalb werden diese konvexen Bereiche häufig gesondert gespeichert um Performance und auch Speicherplatz zu gewinnen.

Verwendung von BSP-Bäumen

Polygone von vorne nach hinten sortieren

Wenn ein Raum durch eine Ebene geteilt wird, so können wir sagen: Wenn sich die Kamera vor der Ebene befindet, so ist es unmöglich, dass ein Objekt welches sich hinter der Ebene befindet ein anderes Objekt vor dieser Ebene verdeckt. "Vor" und "Hinter" ist hierbei durch die Normale der Ebene definiert. Der umgekehrte Schluss: Wir befinden uns hinter der Ebene => kein Objekt vor der Ebene kann ein Objekt hinter der Ebene verdecken, ist natürlich auch gültig. Beim Sortieren der Polygone eines BSP-Baumes wird diese Eigenschaft für jede Ebene des Baumes verwendet. Dies führt zu einer rekursiven Funktion:

SortiereBSPTree( BSPKnoten aktuell )
 if KameraPosition vor aktuell.Ebene
  SortiereBSPTree( aktuell.vorne )
  Verwende Polygone des aktuellen Knoten nach belieben
  SortiereBSPTree( aktuell.hinten )
 else
  SortiereBSPTree( aktuell.hinten )
  Verwende Polygone des aktuellen Knoten nach belieben
  SortiereBSPTree( aktuell.vorne )

Die Verwendung der Polygone kann beispielsweise eine Kollisionsabfrage oder das zeichnen der Polygone sein. Dieser Pseudocode sortiert die Polygone des BSP-Baumes von vorne nach hinten. Die Sortierung von hinten nach vorne geht sehr ähnlich:

SortiereBSPTree( BSPKnoten aktuell )
 if KameraPosition vor aktuell.Ebene
  SortiereBSPTree( aktuell.hinten )
  Verwende Polygone des aktuellen Knoten nach belieben
  SortiereBSPTree( aktuell.vorne )
 else
  SortiereBSPTree( aktuell.vorne )
  Verwende Polygone des aktuellen Knoten nach belieben
  SortiereBSPTree( aktuell.hinten )

Wie bereits erwähnt hat die Sortierung der Polygone primär geschichtliche Bedeutung und findet heutzutage kaum noch Anwendung.

Zu beachten ist das bei einer derartigen Sortierung nichts über die Entfernung eines Polygons zum Betrachter gesagt werden kann. Die einzige Aussage die beim sortieren von hinten nach vorne getroffen wird ist die, dass Polygone die in diesem Prozess später gezeichnet werden niemals von früheren verdeckt wurden. Beim sortieren von vorne nach hinten werden später gezeichnete Polygone entweder von frühere verdeckt, oder es findet keine Überlappung statt.

In welchem Bereich befindet sich ein Punkt

BSP Bäume werden beispielsweise in Quake 1 bis 3 verwendet um den Bereich in dem sich die Kamera innerhalb des Levels befindet zu ermitteln. Jeder Bereich hat hierbei eine eindeutige Identifikation und eine Tabelle aller sichtbaren Bereiche welche als PVS gespeichert sind. Der BSP-Baum dient also zur Ermittlung dieses Bereiches. Hierfür wird der Baum folgendermaßen durchlaufen:

FindeBereich( BSPKnoten aktuell, Position pos )
 if aktuell.isBlattknoten
  return aktuell.BereichID else
 if pos vor aktuell.Ebene
  return FindeBereich( aktuell.vorne, pos )
 else
  return FindeBereich( aktuell.hinten, pos )

Zu beachten ist, dass nur die Blattknoten eine Bereichs-ID besitzen. Bei gewissen Implementierungen kann ein Blattknoten noch weitere konvexe Hüllen besitzen, bei denen zusätzlich überprüft werden muss ob der Punkt innerhalb oder ausserhalb dieser Hüllen ist.

Kollisionsabfragen

Kollisionsabfragen verlaufen recht ähnlich zur Suche eines Bereiches zu einem Punkt, jedoch wird hier kein Punkt sondern ein Volumen überprüft. Bei einem Volume kann es passieren, dass beide Seiten der Ebene überprüft werden müssen. Dies könnte nun beispielsweise so aussehen:

PrüfeKollisionen( BSPKnoten aktuell, Volumen vol )
 if vol schneidet aktuell.Ebene
  Prüfe auf Kollisionen mit Polygonen dieses Knoten
  PrüfeKollisionen( aktuell.vorne, vol )
  PrüfeKollisionen( aktuell.hinten, vol )
 else
  if vol vor aktuell.Ebene
   PrüfeKollisionen( aktuell.vorne, vol )
  else
   PrüfeKollisionen( aktuell.hinten, vol )

Abbruchkriterium ist das Erreichen eines Blattknoten. Ein Blattknoten kann wiederum konvexe Hüllen beinhalten die ebenfalls auf Kollisionen getestet werden müssen.

Weitere Anwendungsmöglichkeiten

Ein BSP-Baum ist in der 3D-Grafik wahrscheinlich die Datenstruktur welche am meisten Anwendungsmöglichkeiten bietet. Einige Beispiele sind:

• Raytracing, indem eine Art Kollisionsabfrage mit dem Strahl durchgeführt wird.
• Viewfrustum culling, indem eine Art Kollisionsabfrage mit der Viewfrustum durchgeführt wird, oder aber jeder Knoten zusätzlich noch ein Bounding Volume erhält.
• Szenen Hierarchie, indem die Objekte so lange am BSP-Baum hinter geschoben werden bis sie eine Ebene schneiden.