Wann ist Binary Space Partitioning, Quadtree, Octree zu verwenden?

75

Ich habe kürzlich etwas über binäre Raumpartitionierungsbäume und deren Anwendung auf 3D-Grafiken und Kollisionserkennung gelernt. Ich habe auch kurz Material zu Quadtrees und Octrees durchgesehen. Wann würden Sie Quadtrees über BSP-Bäumen verwenden oder umgekehrt? Sind sie austauschbar? Ich wäre zufrieden, wenn ich genug Informationen hätte, um eine Tabelle wie diese auszufüllen:

            | BSP | Quadtree | Octree
------------+----------------+-------
Situation A |  X  |          |
Situation B |     |     X    |
Situation C |     |          |   X

Was sind A, B und C?

Martin
quelle

Antworten:

71

Es gibt keine klare Antwort auf Ihre Frage. Es hängt ganz davon ab, wie Ihre Daten organisiert sind.

Beachten Sie Folgendes:

Quadtrees eignen sich am besten für Daten, die meist zweidimensional sind, wie das Rendern von Karten in Navigationssystemen. In diesem Fall ist es schneller als Oktrees, da es sich besser an die Geometrie anpasst und die Knotenstrukturen klein hält.

Octrees und BVHs (Bounding Volume Hierarchies) profitieren davon, wenn die Daten dreidimensional sind. Es funktioniert auch sehr gut, wenn Ihre geometrischen Objekte im 3D-Raum gruppiert sind. (siehe Octree vs BVH ) (archiviert vonOriginal)

Der Vorteil von Oc- und Quadtrees ist, dass Sie jederzeit keine Bäume mehr erzeugen können. Wenn Sie Grafiken mit einem Grafikbeschleuniger rendern möchten, können Sie einfach Bäume auf Objektebene generieren und jedes Objekt in einem einzigen Draw-Aufruf an die Grafik-API senden. Dies funktioniert viel besser als das Senden einzelner Dreiecke (etwas, das Sie tun müssen, wenn Sie BSP-Bäume in vollem Umfang verwenden).

BSP-Bäume sind wirklich ein Sonderfall. Sie funktionieren sehr gut in 2D und 3D, aber gute BSP-Bäume zu erzeugen ist eine Kunstform für sich. BSP-Bäume haben den Nachteil, dass Sie Ihre Geometrie möglicherweise in kleinere Teile aufteilen müssen. Dies kann die Gesamtpolygonzahl Ihres Datensatzes erhöhen. Sie eignen sich gut zum Rendern, sind jedoch viel besser für die Kollisionserkennung und Raytracing-Funktion geeignet.

Eine schöne Eigenschaft der BSP-Bäume ist, dass sie eine Polygonsuppe in eine Struktur zerlegen, die von jeder Kameraposition aus perfekt von hinten nach vorne (und umgekehrt) gerendert werden kann, ohne eine tatsächliche Sortierung durchzuführen. Die Reihenfolge von jedem Standpunkt aus ist Teil der Datenstruktur und erfolgt während der BSP-Tree-Kompilierung.

Das ist übrigens der Grund, warum sie vor 10 Jahren so beliebt waren. Quake verwendete sie, weil es der Grafik-Engine / dem Software-Rasterizer ermöglichte, keinen teuren Z-Puffer zu verwenden.

Alle genannten Bäume sind nur Baumfamilien. Es gibt auch lose Oktrees, kd-Bäume, Hybridbäume und viele andere verwandte Strukturen.

Nils Pipenbrinck
quelle
1
Gute Antwort, obwohl ich nicht sicher bin, was Sie unter "Senden" eines Objekts an die GPU anstatt einzelner Dreiecke verstehen. Beziehen Sie sich auf den VBO-Modus im Vergleich zum Sofortmodus? Weil das mit beiden Ansätzen gemacht werden kann, dachte ich ...
Aktau
@ DavidJeske Diese Antwort ist sechs Jahre alt. Eine lange Zeit in der Informatik. Dies kann sich jetzt geändert haben.
Nils Pipenbrinck
Der Kommentar, dass das Zeichnen mit BSPs langsamer ist, ist falsch. BSPs wurden entwickelt, um große statische Geometrien zu optimieren. Sie wurden ursprünglich zur Optimierung der Okklusion für die Software-Rasterung verwendet und wurden seitdem auch zur Vorberechnung von Zeichnungsstapeln für die Hardware-Rasterisierung verwendet. BSPs passen nicht gut, wenn viele Instanzen vorhanden sind, da die Objekte instanziiert und in die BSP unterteilt werden müssen. BSPs sind auch schlecht für dynamische Objekte, da sie zu langsam zum Erstellen sind.
David Jeske
1
BSPs sind wirklich und ich meine wirklich schlecht für jede moderne Szene. Sie waren damals großartig, als man eine Handvoll Dreiecke sortieren musste. Heutzutage ist ein bisschen Überziehen (selbst mit Hardcore-Fragment-Shadern) viel schneller als das separate Sortieren und Zeichnen jedes Dreiecks in der Szene. Das Zeichnen eines Z-Prepass beseitigt jegliches Überziehen und ist immer noch schneller.
RecursiveExceptionException
14

Der größte praktische Unterschied zwischen BSP-Bäumen und anderen Arten von 3D-Bäumen besteht darin, dass BSP-Bäume optimaler sein können, aber nur mit statischer Geometrie arbeiten. Dies liegt daran, dass BSP-Bäume im Allgemeinen sehr langsam erstellt werden und für ein typisches statisches städtisches Spielniveau oft Stunden oder Tage benötigen.

Die beiden Hauptgründe, warum das Erstellen von BSP-Bäumen länger dauert, sind (a) sie verwenden nicht achsenausgerichtete Aufteilungsebenen, deren optimale Suche länger dauert, und (b) sie unterteilen die Geometrie an den Achsengrenzen, um sicherzustellen, dass keine Objekte die Aufteilungsebenen kreuzen.

Andere Arten von 3D-Bäumen (Octrees, Quadtrees, kd-tree, Bounding-Volume-Hierarchy) verwenden achsenausgerichtete Begrenzungsvolumes, und Volumes dürfen sich (optional) überlappen, sodass enthaltene Objekte nicht auf Volume geschnitten werden müssen Grenzen. Beides macht die Bäume weniger optimal als BSP-Bäume, aber schneller zu erstellen und für dynamische Objekte einfacher zu ändern.

Extrapolation dieser Faktoren in Situationen ...

Außenbereiche verwenden normalerweise höhenfeldbasierte Bodendarstellungen, entweder einfache Höhenkarten oder komplexere Geo-Mip-Kartierungstechniken wie ROAM. Der Boden selbst nimmt nicht an der 3D-Raumaufteilung teil, sondern nur Objekte, die auf dem Boden platziert sind.

In Welten mit vielen einfacheren und ähnlichen Geometrien (Häuser, Bäume, Asteroiden usw.) wird häufig ein Nicht-BSP-Baum (z. B. ein BVH) verwendet, da das Einfügen der Geometrie in einen BSP-Baum das Duplizieren und Aufteilen der Geometrie bedeuten würde Detailgeometrie für jede Instanz.

Umgekehrt verwendet ein großes benutzerdefiniertes statisches Netz ohne Instanzen, wie z. B. eine städtische Szene oder eine komplexe Innenumgebung, normalerweise einen BSP-Baum, um die Laufzeitleistung zu verbessern. Die Tatsache, dass der BSP-Baum die Geometrie an Knotengrenzen aufteilt, ist hilfreich für die Renderleistung, da die BSP-Knoten als vororganisierte Dreieck-Rendering-Stapel verwendet werden können. Der BSP-Baum kann auch für die Okklusion optimiert werden, ohne dass Teile des BSP-Baums gezeichnet werden müssen, von denen bekannt ist, dass sie sich hinter einer anderen Geometrie befinden.

Siehe auch: Octree vs BVH (archiviert vonOriginal), Bounding Volume Hierarchy Tutorial , BSP Tutorial .

David Jeske
quelle
1
@rjdkolb Ich habe es an seinem neuen Standort behoben, wenn Sie noch interessiert sind.
Bart
8

Ein BSP eignet sich am besten für städtische Umgebungen.

Ein Quadtree eignet sich am besten, wenn Sie eine Höhenkarte für Gelände usw. verwenden.

Ein Octree eignet sich am besten für Geometrieklumpen im 3D-Raum, z. B. ein Sonnensystem.

TraumaPony
quelle
3

BSPs sind eine gute Option zur Beschleunigung der Kollisionserkennung, je nachdem, welchen Geschmack Sie verwenden. Sie sind besonders schnell bei Punkt- und Linien- oder Strahlentests, etwas weniger schnell und etwas komplizierter für Dinge mit Volumen.

BSPs sind für ihre Verwendung in Grafiken ziemlich veraltet. Octrees eignen sich gut für Dinge wie das Keulen von Sichtbarkeit, ebenso wie AABB-Bäume.


quelle
1

Ich habe nicht viel Erfahrung mit BSPs, aber ich kann sagen, dass Sie mit Oktrees über Quadtrees gehen sollten, wenn die Szene, die Sie rendern, groß ist. Das heißt, die Höhe ist mehr als die Hälfte der Breite und Tiefe - kleine Faustregel. Im Allgemeinen verursachen Octrees keine großen Kosten gegenüber Quadtrees und haben das Potenzial, die Dinge ein wenig zu beschleunigen. YMMV.

Serafina Brocious
quelle
0

Normalerweise haben diese Dinge keine eindeutige Antwort. Ich würde vorschlagen, dass A, B und C das Ergebnis einer Funktion der Größe Ihres Raums und der Menge an Dingen sind, die Sie unterscheiden.

Jonathan Adelson
quelle
1
Bitte klären Sie, ob BSP für einen großen oder einen kleinen Raum geeignet ist. Mehr oder weniger Objekte?
Martin
0

Ein BSP ist besser für einen kleineren, einfacheren Raum, mit dem Sie nur Okklusion machen möchten. Wenn Sie alle Schnittpunkte für einen bestimmten Strahl möchten, müssen Sie ein Upgrade auf ein Quad / Octree durchführen.

Was Quadtree vs. Octree betrifft - wie viele Dimensionen interessieren Sie sehr? Zwei Dimensionen bedeuten einen Quadtree, vier einen Octree. Wie bereits erwähnt, kann Quadtree im Dreiraum arbeiten. Wenn Sie jedoch möchten, dass jede Dimension richtig behandelt wird, ist ein Octree der richtige Weg.

Hazzen
quelle
0

Wenn Sie nicht wissen, was Sie tun, entscheiden Sie sich immer für die Oktrees, damit Sie sich nicht mehr auf die Überoptimierung konzentrieren und an ernsthafteren Funktionen arbeiten können. Im Ernst, die Engpässe werden immer woanders sein, oder Sie entwerfen Ihren Code um ein optimiertes System herum, das letztendlich bestimmte Arten von Änderungen später verhindert.

Kaffeeentwickler
quelle