BSP-Baum - Versionsgeschichte

Glawesome: /* Eigenschaften eines BSP-Baumes */ Zeichensetzung, Ebene verlinkt, Rechtschreibung

2013-10-12T17:45:21Z

‎Eigenschaften eines BSP-Baumes: Zeichensetzung, Ebene verlinkt, Rechtschreibung

Glawesome: /* Geschichte */ Kommasetzung

2013-10-12T17:40:06Z

‎Geschichte: Kommasetzung

Flash: BSP-Bäume wurde nach BSP-Baum verschoben

2006-02-26T16:41:28Z

BSP-Bäume wurde nach BSP-Baum verschoben

Dj3hut1: /* Link Bounding_Volume */

2005-12-30T19:14:46Z

‎Link Bounding_Volume

Flo: Der Kategorie Anleitung zugeordnet

2005-09-23T08:17:34Z

Der Kategorie Anleitung zugeordnet

Flo: Der Kateogrie Technik oder Algorithmus zugeordnet

2005-09-23T08:17:10Z

Der Kateogrie Technik oder Algorithmus zugeordnet

2005-04-17T11:39:20Z

2005-03-01T12:48:37Z

Lyr: /* In welchem Bereich befindet sich ein Punkt */ Wenn so, dann gleich gscheit :-)

2005-03-01T12:43:37Z

‎In welchem Bereich befindet sich ein Punkt: Wenn so, dann gleich gscheit :-)

134.109.4.201: /* In welchem Bereich befindet sich ein Punkt */

2005-03-01T11:53:58Z

‎In welchem Bereich befindet sich ein Punkt

@@ Zeile 3: / Zeile 3: @@
 =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.
+Ein BSP-Baum ist ein Binärbaum, bei dem jeder Knoten eine [[Ebene#Hesseform|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.
+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=

@@ Zeile 1: / Zeile 1: @@
 =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.
+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=

@@ Zeile 70: / Zeile 70: @@
 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.
+*Viewfrustum culling, indem eine Art Kollisionsabfrage mit der Viewfrustum durchgeführt wird, oder aber jeder Knoten zusätzlich noch ein [[Bounding_Volume|Bounding Volume]] erhält.
 *Szenen Hierarchie, indem die Objekte so lange am BSP-Baum hinunter geschoben werden bis sie eine Ebene schneiden.
 [[Kategorie:Anleitung]] [[Kategorie:Technik_oder_Algorithmus]]

← Nächstältere Version		Version vom 23. September 2005, 08:17 Uhr
Zeile 73:		Zeile 73:
	*Szenen Hierarchie, indem die Objekte so lange am BSP-Baum hinunter geschoben werden bis sie eine Ebene schneiden.		*Szenen Hierarchie, indem die Objekte so lange am BSP-Baum hinunter geschoben werden bis sie eine Ebene schneiden.

−	[[Kategorie:Technik_oder_Algorithmus]]	+	[[Kategorie:Anleitung]] [[Kategorie:Technik_oder_Algorithmus]]

← Nächstältere Version		Version vom 23. September 2005, 08:17 Uhr
Zeile 72:		Zeile 72:
	*Viewfrustum culling, indem eine Art Kollisionsabfrage mit der Viewfrustum durchgeführt wird, oder aber jeder Knoten zusätzlich noch ein Bounding Volume erhält.		*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 hinunter geschoben werden bis sie eine Ebene schneiden.		*Szenen Hierarchie, indem die Objekte so lange am BSP-Baum hinunter geschoben werden bis sie eine Ebene schneiden.
		+
		+	[[Kategorie:Technik_oder_Algorithmus]]

← Nächstältere Version	Version vom 26. Februar 2006, 16:41 Uhr
(kein Unterschied)

@@ Zeile 44: / Zeile 44: @@
   FindeBereich( BSPKnoten aktuell, Position pos )
    if aktuell.isBlattknoten
-    return aktuell.BereichID else
+    return aktuell.BereichID
    else
-    return FindeBereich( aktuell.hinten, pos )
+    if pos vor aktuell.Ebene
 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.