Einsteigerguide: Was ist eine Bounding Volume Hierarchie?

Eine Bounding Volume Hierarchie (BVH) ist eine Baumstruktur auf einer Reihe von geometrischen Objekten.

Alle geometrischen Objekte sind in begrenzende Volumen eingewickelt, die die Blatt-Nodes des Baumes bilden. Diese Nodes werden dann als kleine Mengen gruppiert und in größere Mengen eingeschlossen. Diese wiederum werden ebenfalls rekursiv gruppiert und in andere größere Begrenzungsvolumen eingeschlossen, was schließlich zu einer Baumstruktur mit einem einzigen Begrenzungsvolumen an der Spitze des Baums führt.

Volumenbegrenzungshierarchien werden verwendet, um mehrere Operationen an Mengen von geometrischen Objekten effizient zu unterstützen, wie z.B. bei der Collision Detection und dem Raytracing.

Obwohl das Wrapping von Objekten in Bounding-Volumes und die Durchführung von Collision-Tests vor dem Testen der Objektgeometrie selbst die Tests vereinfacht und zu erheblichen Leistungssteigerungen führen kann, wird immer noch die gleiche Anzahl von paarweisen Tests zwischen Bounding-Volumes durchgeführt. Durch die Anordnung der Bounding Volumes in einer Bounding Volume Hierarchie kann die Zeitkomplexität in der Anzahl der Objekte auf logarithmisch reduziert werden. Wenn eine solche Hierarchie vorhanden ist, müssen beim Collision Testing untergeordnete Volumes nicht untersucht werden, wenn ihre übergeordneten Volumes nicht geschnitten werden.

BVH-Designthemen.

Die Wahl des Begrenzungsvolumen wird durch einen Kompromiss zwischen zwei Zielen bestimmt. Auf der einen Seite möchten wir Begrenzungsbänder verwenden, die eine sehr einfache Form haben. So benötigen wir nur wenige Bytes, um sie zu speichern. Zudem sind Schnittests und Entfernungsberechnungen einfach und schnell. Auf der anderen Seite hätten wir gerne Bounding-Volumes, die sehr eng zu den entsprechenden Datenobjekten passen. Eines der am häufigsten verwendeten Begrenzungsvolumina ist ein achsparalleler Mindestbegrenzungsrahmen. Die achsenorientierte Mindestbegrenzungsbox für einen gegebenen Satz von Datenobjekten ist einfach zu berechnen, benötigt nur wenige Bytes Speicherplatz, robuste Schnitttests sind einfach zu implementieren und extrem schnell.

Es gibt mehrere gewünschte Eigenschaften für einen BVH, die bei der Auslegung für eine bestimmte Anwendung berücksichtigt werden sollten.

• Die Nodes, die in einem bestimmten Teilbaum enthalten sind, sollten nahe beieinander liegen. Je weiter unten im Baum, desto näher sollten die Nodes aneinander liegen.
• Jeder Node im BVH sollte ein Mindestvolumen aufweisen.
• Die Summe aller begrenzenden Volumen sollte minimal sein.
• Den Node in der Nähe der Wurzel des BVH sollte mehr Aufmerksamkeit geschenkt werden.
• Wenn Sie einen Node in der Nähe der Wurzel des Baums beschneiden, werden weitere Objekte aus der weiteren Betrachtung entfernt.
• Das Überlappungsvolumen der Geschwister-Nodes sollte minimal sein.
• Der BVH sollte sowohl in Bezug auf seine Node-Struktur als auch auf seinen Inhalt ausgewogen sein. Beim Balancieren kann so viel wie möglich vom BVH geschnitten werden, wenn ein Ast nicht überquert wird.

Im Hinblick auf die Struktur des BVH ist zu entscheiden, in welchem Umfang (Anzahl der Kinder) und in welcher Größe der Baum, der den BVH repräsentiert, verwendet werden soll. Ein Baum von geringem Grad wird von größerer Höhe sein. Das erhöht die Traversalzeit von Root to Leaf. Andererseits muss an jedem besuchten Node weniger Arbeitsaufwand betrieben werden, um seine Kinder auf Überschneidungen zu überprüfen. Das Gegenteil gilt für einen hochgradigen Baum: Obwohl der Baum eine geringere Höhe hat, wird an jedem Node mehr Arbeit aufgewendet. In der Praxis sind binäre Bäume (Grad = 2) bei weitem am häufigsten. Eine der Hauptgründe ist, dass Binärbäume einfacher zu erstellen sind.

Aufbau.

Es gibt drei Hauptkategorien von Baum-Aufbau-Methoden: Top-Down, Bottom-Up und Einfüge-Methoden.

Top-Down-Methoden gehen so weit, dass sie den Eingabesatz in zwei (oder mehr) Teilmengen partitionieren, sie in dem gewählten Begrenzungsvolumen begrenzen und dann rekursiv partitionieren, bis jede Teilmenge nur noch aus einem einzigen Primitiv besteht (Blatt-Nodes werden erreicht). Top-Down-Methoden sind einfach zu implementieren, schnell zu konstruieren und bei weitem die beliebtesten, führen aber nicht zu den bestmöglichen Bäumen im Allgemeinen.

Bottom-Up-Methoden beginnen mit dem Eingabesatz als Blätter des Baumes und gruppieren dann zwei von ihnen zu einem neuen (internen) Node, gehen auf die gleiche Weise vor, bis alles unter einem einzigen Node gruppiert ist.

Bottom-Up-Methoden sind schwieriger zu implementieren, erzeugen aber im Allgemeinen wahrscheinlich bessere Bäume. Einige neuere Studien deuten darauf hin, dass die Konstruktionsgeschwindigkeit im niedrigdimensionalen Raum erheblich verbessert werden kann (was den Top-Down-Ansätzen entspricht oder diese übertrifft), indem Objekte nach der Raumfüllungskurve sortiert und auf der Grundlage dieser sequentiellen Reihenfolge approximativ gebündelt werden.

Sowohl Top-Down- als auch Bottom-Up-Methoden werden als Offline-Methoden betrachtet, da sie beide voraussetzen, dass alle Primitive vor Baubeginn verfügbar sind. Einfügemethoden bauen den Baum auf, indem sie ein Objekt nach dem anderen einfügen, beginnend mit einem leeren Baum. Die Einfügeposition sollte so gewählt werden, dass der Baum nach einer Kostenkennzahl so wenig wie möglich wächst. Einfügemethoden werden als Online-Methoden betrachtet, da sie nicht erfordern, dass alle Primitive vor Baubeginn verfügbar sind und somit Aktualisierungen zur Laufzeit durchgeführt werden können.

Verwendung.

BVHs werden häufig beim Raytracing verwendet, um potentielle Schnittkandidaten innerhalb einer Szene zu eliminieren, indem geometrische Objekte in begrenzten Volumina weggelassen werden, die nicht vom aktuellen Strahl geschnitten werden.

Ich hoffe, dass wir ihnen einen ersten Einstieg in diese Thematik bieten könnten. Falls Sie noch Anmerkungen oder Fragen zu dieser Thematik haben sollten, hinterlassen Sie uns unten einen Kommentar.

Vielen Dank für ihren Besuch.