Was ist ein BSP Baum?

Ein “Binary Space Partitioning” Baum (oder BSP Baum) ist eine Datenstruktur, die benutzt wird, um Objekte in einem Raum zu organisieren. Auf dem Gebiet der Computergrafik gibt es verschiedene Applikationen fuer das “hidden surface removal” Problem und fuer Ray Tracing. Ein BSP Baum ist ein rekursive Zerlegung des Raumes, die jedes Liniensegment ( bzw. jedes Polygon in 3D) wie eine Zerlegungsebene ansieht, die benutzt wird, um alle uebrigen Objekte des Raumes als vor oder hinter dieser Ebene liegend zu kategorisieren. Mit anderen Worten, wenn ein neues Objekt in den Baum eingefuegt wird, wird es zunaechst in Relation zur Wurzel zugeordnet und dann rekursiv unter Betrachtung jedes folgenden Knoten eingeordnet. Fuer weitere Informationen ueber BSP Baeume lesen sie die BSP Baum FAQ.

'tschuldigung, dein Browser unterstuetzt keine Java applets.

Wie benutze ich dieses Applet

Man kann Liniensegmente in dem ersten Feld zeichnen (die erste gezeichnete Linie veranlasst Java dazu einige Initialisierungen durchzufuehren, so dass es viel laenger dauert, als bei den folgenden). Die Segmente werden durchnumeriert in aufsteigender Reihenfolge, und der Baum wird dadurch aufgebaut, dass jedes Segment in numerischer Folge eingefuegt wird. Wenn ein Segment zerlegt werden muss, dann der vordere Teil mit “f” in seinem Namen markiert und der hintere mit “b”. Falls Segment 1 die Zerlegungsebene schneidet, die von Segment 0 gebildet wird, dann wird der Teil von Segment 1, der vor Segment 0 liegt mit “1f” bezeichnet und der hintere Teil mit “1b”.

Man kann den roten Blickwinkel (Pfeil) durch anklicken und ziehen bewegen, und wenn man den Pfeilkopf anklickt und zieht, dann kann die Blickrichtung gedreht werden.

Wenn die Zeichnung des Baumes zu gross fuer den Darstellungsbereich ist, kann durch Anklicken und Ziehen des Baumes dieses verschoben werden.

BSP-Baum-Demo technische Anmerkungen

Der BSP-Baum Algorithmus

Der BSP-Baum wird erstellt, indem jedes Segment in numerierter Reihenfolge in den Baum eingefuegt wird. Damit der Benutzer die Demonstration leichter versteht, wir hier darauf verzichtet den Baum zu finden mit den weingsten Zerlegungen. Dies wird normalerweise gemacht, weil es die Groesse des Baumes verringert und ihn effektiver macht. Es wird auch nicht versucht einen ausbalancierten Baum zu erstellen, was eigentlich immer erstrebenswert ist, weil es degenerierte Faelle, wie zum Beispiel Baeume, bei denen die Hoehe des Baumes gleich der Anzahl der Zerlegungen ist, vermeidet. Weil jede Partition gegen O(lg(n)) andere Partitionen klassifiziert werden muss, erhaelt man fuer die Konstruktion eines BSP-Baumes eine Laufzeit von O(n*lg(n)).

Der Algorithmus zur Darstellung

Der Graph wird unter Verwendung des “Reingold and Tilford Rooted Tree Drawing” Algorithmuses gezeichnet. Naehere Informationen zu diesem Algorithmus koennen auf Seite 6 dieses PostScript Dokumentes gefunden werden. Sollte das Dokument nicht verfuegbar sein, sind hier die relevanten Auszuege des Algorithmuses.

Nachdem der linke und rechte Zweig gezeichnet wurden, plaziert man die Zeichnungen der Zweige mit einem horizontalem Abstand von 2. Danach plaziert man die Wurzel eine Stufe hoeher und auf halbem Weg zwischen den Zweigen. Wenn es nur einen Zweig gibt, dann plaziert man die Wurzel mit einem horizontalen Abstand von 1 vom Zweig entfernt.

Der Renderalgorithmus

Diese Pseudo 3D-Szene wird gerendert, indem alle Objekte relativ zur Betrachtung klassifiziert werden, d.h zunaechst werden alle Segmente auf der anderen Seite des Wurzel-Segmentes dargestellt, dann das Wurzelsegment und anschliessend alle Segemnte, die auf derselben Seite wie das Wurzelsegment liegen. Wenn der Blickwinkel so faellt, das seitlich auf ein Segement geschaut wird, dann wird das betreffende Segment nicht gezeichnet. Da jedes Segment waehrend des Zeichnens genau einmal berechnet wird, kann eine Szene mit einer Zeitkomplexitaet von O(n) berechnet werden. Hier ist der Pseudocode fuer eine entsprechende Methode, der diesen Algorithmus implementiert:

draw3DScene()
  if location(eye.point) == frontSide
    back.draw3DScene()
    drawPolygon()
    front.draw3DScene()
  else if location(eye.point) == backSide
    front.draw3DScene()
    drawPolygon()
    back.draw3DScene()
  else
    front.draw3DScene()
    back.draw3DScene()

Wenn man bereit ist die Szene zu zeichnen, werden der Blickpunkt und der Richtungsvektor benutzt, um das Koordinatensystem fuer die Kamereaperspektive zu bestimmen. Dann wird jedes Polygon nach dem folgenden Algorithmus berechnet:

drawPolygon()
  transform segment endpoints to camera space
  clip segment to view frustrum
  convert segment to polygon:
    set the width to the x values scaled down by the y values
    set the height to a constant value scaled down by the y values

Weiter Informationen zu BSP Baeumen

Der womoeglich beste Platz fuer Informationen ueber BSP Baeume ist die BSP Baum FAQ.

Dieses Dokument wurde von Carsten Rene Tschoep und Carsten Rene Tschoep ins Deutche ubersetzt.