Bounding Volume

Ein Bounding Volume ist ein einfacher geometrischer Körper, der ein komplexeres Objekt umschließt.

Bounding Volumes werden dazu verwendet um bestimmte Tests zu beschleunigen. So kann man z.B. beim Ray Tracing zuerst über den Schnitt mit den Bounding Volumes der Objekte testen, ob sie überhaupt getroffen werden können, bevor man z.B. für ein genaueres Ergebnis die einzelnen Triangel der Objekte testet. Ähnlich funktioniert dies auch für eine Kollisionserkennung, wenn sich die Bounding Volumes zweier Objekte nicht schneiden, dann können auch die Objekte nicht miteinander kollidieren.

Varianten

Bounding Sphere eines Kaktus

• Bounding Sphere: Eine das Objekt umgebende Kugel (oder in 2D ein Kreis). Für Bounding Spheres gibt es in XNA die BoundingSphere Struct (Namespace Microsoft.Xna.Framework). Eine Bounding Sphere wird durch ihren Center-Punkt und ihren Radius definiert. Der Vorteil von Bounding Spheres ist, dass Kollisionen sehr schnell berechnet werden können.

Bounding Box eines Kaktus

• Bounding Box: Ein das Objekt umgebendes Quader (oder in 2D ein Rechteck). Der Vorteil von Bounding Boxen ist, dass sie Objekte meistens genauer umschreiben als Kugeln. Bei Bounding Boxen gibts es eine Unterscheidung zwischen Axis-Aligned Bounding Boxen (AABB) und Object Oriented Bounding Boxen (OOB). AABBs orientieren sich immer an den Axen des Koorinatensystems. Definiert sind sie entsprechend durch zwei Punkte, einen mit dem maximalen x-,y- und z-Wert und einen mit dem minimalen x-,y- und z-Wert. Für AABBs gibt es in XNA die BoundingBox Struct (Namespace Microsoft.Xna.Framework). OOBs orientiren sich wie der Name schon sagt direkt an ihren zugrunde liegenden Objekten. In XNA gibt es für sie standardmäßig keine Implementierung. Der Vorteil von AABBs ist, dass Kollisionen wesentlich einfacher berechnet werden können, ihr Nachteil ist dafür dass sie nicht mit Objekten mitgedreht werden können sondern neu berechnet werden müssen.

Es gibt noch einige weitere Primitive die für Bounding Volumes verwendet werden können, doch diese beiden sind die wichtigsten.

Bounding Volume Hierarchies (BVHs)

Eine BVH ist ein Baum aus Bounding Volumes, z.B. bestehend aus Bounding Spheres und/oder Bounding Boxen. Am Ende der Hierarchie befinden sich Volumes, die gerade groß genug sind um bestimmte Teile des gesamten Objekts zu umfassen. Wenn man der Hierarchie nach oben folgt dann besitzt jeder Knoten ein Volume das gerade groß genug ist um die Volumes der Kindknoten zu enthalten. An der Wurzel des Baums befindet sich letztenendes ein Bounding Volume das groß genug ist um alle anderen Bounding Volumes des Baums zu umfassen.

BVHs sind nützlich um Tests noch weiter zu beschleunigen oder auch um die Ergebnisse zu verbessern. So kann man gerade bei großen Objekten die benötigte Anzahl an Schnitttests für Ray Tracing nochmals reduzieren oder die Genauigkeit der Ergebnisse verbessern, indem man z.B. auf die BVH testet anstatt nur auf ein einzelnes Bounding Volume.

BVH eines Modells aus Bounding Spheres

BVH eines Modells aus Bounding Boxen