Wann binäre Raumpartitionierung, Quadtree, Octree?

Question

Ich habe kürzlich über Binärraum Partitionierung Bäume und ihre Anwendung auf 3D-Grafik und Kollisionserkennung gelernt. Ich habe auch kurz Material über Quadtrees und Octrees gelesen. Wann würden Sie Quadtrees über BSP-Bäume verwenden oder umgekehrt? Sind sie austauschbar? Ich wäre zufrieden, wenn ich genug Informationen hätte, um eine Tabelle wie folgt auszufüllen:

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

Was sind A, B und C?

Answer 1

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

Etwas im Auge zu behalten:

Quadtrees für Daten am besten arbeiten, die meist zweidimensionale wie map-Rendering in Navigationssystemen ist. In diesem Fall ist es schneller als Octrees, weil es sich besser an die Geometrie anpasst und die Knotenstrukturen klein hält.

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

Der Vorteil von Oc- und Quadtrees ist, dass Sie jederzeit aufhören können, Bäume zu erzeugen. Wenn Sie Grafiken mit einem Grafikbeschleuniger rendern möchten, können Sie nur Bäume auf Objektebene generieren und jedes Objekt in einem einzigen Zeichenaufruf an die Grafik-API senden. Dies führt 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-Trees haben den Nachteil, dass Sie Ihre Geometrie in kleinere Teile teilen müssen. Dies kann die Gesamtpolygonzahl Ihres Datensatzes erhöhen. Sie sind gut für das Rendern, aber sie sind viel besser für Kollisionserkennung und Ray-Tracing.

Eine nette Eigenschaft der BSP-Bäume ist, dass sie eine Polygonsuppe in eine Struktur zerlegen, die von jeder Kameraposition aus perfekt gerendert werden kann (und umgekehrt), ohne eine tatsächliche Sortierung vorzunehmen. Die Reihenfolge von jedem Standpunkt aus ist Teil der Datenstruktur und erfolgt während der BSP-Baumkompilierung.

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

Alle genannten Bäume sind nur Familien von Bäumen. Es gibt lose Octrees, kd-Bäume Hybrid-Bäume und viele andere verwandte Strukturen.

Answer 2

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

Answer 3

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

Answer 4

Ein BSP ist besser für einen kleineren, einfacheren Platz, den Sie nur mit Okklusion machen wollen. Wenn Sie alle Schnittpunkte für einen bestimmten Strahl wünschen, müssen Sie ein Upgrade auf Quad/Octree durchführen.

Wie für Quadtree vs. Octree - für wie viele Dimensionen interessieren Sie sich? Zwei Dimensionen bedeuten einen Quadtree, vier einen Octree. Wie bereits erwähnt, kann Quadtree in drei Räumen arbeiten, aber wenn Sie möchten, dass jede Dimension eine angemessene Behandlung erhält, ist ein Octree der richtige Weg.

Answer 5

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

Ein Quadtree ist am besten, wenn Sie eine Höhenkarte für Gelände, etc. verwenden

Ein Octree ist am besten, wenn Sie Klumpen von Geometrie in 3D-Raum, wie zum Beispiel eine Solaranlage.

Answer 6

BSPs sind eine gute Option, um die Kollisionserkennung zu beschleunigen, 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.

Für ihre Verwendung in der Grafik sind BSPs ziemlich veraltet. Octrees funktionieren gut für Dinge wie grobe Sichtbarmachung, ebenso wie AABB-Bäume.

Answer 7

Der größte praktische Unterschied zwischen BSP-Bäumen und anderen Arten von 3D-Bäumen ist, dass BSP-Bäume optimaler sein können, aber nur unter statische Geometrie funktionieren. Dies liegt daran, dass BSP-Bäume im Allgemeinen sehr langsam aufzubauen sind und oft Stunden oder Tage für ein typisches statisches städtisches Spielniveau benötigen. Die zwei Hauptgründe, aus denen BSP-Bäume länger bauen, sind (a) sie verwenden nicht achsabgestimmte Teilungsebenen, die länger brauchen, um optimal zu finden, und (b) sie unterteilen Geometrie auf Achsengrenzen, wodurch keine Objekte gesichert werden Split-Ebenen überqueren.

Andere Arten von 3D-Bäumen (Octrees, Quadtrees, kd-tree, Bounding-Volume-Hierarchy) verwenden achsausgerichtete Bounding-Volumes, und Volumes (optional) dürfen sich überlappen, so dass enthaltene Objekte nicht müssen an Volumengrenzen geschnitten werden. Beide machen die Bäume weniger optimal als BSP-Bäume, aber schneller zu bauen und einfacher für dynamische Objekte zu ändern.

diese Faktoren in Situationen ...

Außenbereiche typischerweise Extrapolation verwenden Höhenfeld-basierten Darstellungen Boden, entweder einfache oder komplexere Height geo-Mip-Mapping-Techniken wie ROAM. Der Boden selbst nimmt nicht an der 3D-Raumaufteilung teil, sondern nur Objekte, die auf dem Boden liegen.

Welten mit vielen Instanzen einfacherer und ähnlicher Geometrie (Häuser, Bäume, Asteroiden usw.) verwenden oft einen Nicht-BSP-Baum (z. B. BVH), weil das Einfügen der Geometrie in einen BSP-Baum bedeuten würde Duplizieren und Teilen der Detailgeometrie für jede Instanz.

Umgekehrt wird ein großes statisches Netz ohne Instanziierung, z. B. eine städtische Umgebung oder eine komplexe Innenraumumgebung, in der Regel einen BSP-Baum verwenden, um die Laufzeit zu verbessern. Die Tatsache, dass der BSP-Tree Geometrie auf Knotengrenzen aufteilt, ist für die Rendering-Performance hilfreich, da die BSP-Knoten als vordefinierte Dreieck-Rendering-Stapel verwendet werden können. Der BSP-Tree kann auch für die Okklusion optimiert werden, so dass keine Teile des BSP-Baumes gezeichnet werden müssen, die bekanntermaßen hinter anderen Geometrien liegen.

Siehe auch: Octree vs BVH, Bounding Volume Hierarchy Tutorial, BSP Tutorial.