Warum sollte man jemals einen Octree über einem KD-Baum verwenden?

32

Ich habe einige Erfahrung im wissenschaftlichen Rechnen und habe kd-trees ausgiebig für BSP-Anwendungen (Binary Space Partitioning) verwendet. Ich habe mich in letzter Zeit mit Octrees, einer ähnlichen Datenstruktur für die Partitionierung von euklidischen 3D-Räumen, vertraut gemacht, die jedoch nach meinen Erkenntnissen in regelmäßigen Abständen funktioniert.

Ein bisschen Unabhängigkeitsforschung scheint darauf hinzudeuten, dass kd-trees für die meisten Datensätze in der Regel eine überlegene Leistung aufweisen - schneller zu konstruieren und abzufragen. Meine Frage ist, was sind die Vorteile von Octrees in räumlicher / zeitlicher Leistung oder auf andere Weise, und in welchen Situationen sind sie am besten anwendbar (ich habe 3D-Grafikprogrammierung gehört)? Eine Zusammenfassung der Vorteile und Probleme beider Typen würde mich am meisten freuen.

Wenn jemand die Verwendung der R-Tree-Datenstruktur und ihre Vorteile näher erläutern könnte, wäre ich auch dafür dankbar. R-Bäume (mehr als Octrees) scheinen bei der Suche nach k nächsten Nachbarn oder Entfernungen ziemlich ähnlich auf kd-Bäume angewendet zu werden.

Noldorin
quelle
Ich sollte beachten, dass sowohl kd-Bäume als auch R-Bäume (aber keine Oktobäume) speziell dafür ausgelegt sind, die Suche nach k nächsten Nachbarn zu erleichtern - wie vergleichen sie in diesem Sinne?
Noldorin
Eine Anmerkung ist, dass kd-Bäume geringe Tiefe garantiert haben. Komprimierte Quad-Bäume können Sie dorthin bringen, sind aber weniger praktisch.
Suresh Venkat
@ Suresh Venkat: Danke dafür. Ich kenne komprimierte Quadtrees nicht, aber wären sie wirklich für räumliche 3D-Wiederholungen geeignet? Vielleicht gibt es ein "komprimiertes Octree" -Analog.
Noldorin
Ich habe auch gehört, dass Octrees geeigneter sind, wenn man eine bekannte Z-Ordnungskurve (Raumfüllungskurve) hat, aber ich bin mir nicht ganz sicher, was die Gründe hier sind.
Noldorin

Antworten:

23

Die Zellen in einem kann -Baum mit hohem Aspektverhältnis aufweisen, während Octree Zellen kubisch sein garantiert. Da es sich um eine Theorietafel handelt, gebe ich Ihnen den theoretischen Grund, warum ein hohes Seitenverhältnis ein Problem ist: Es ist unmöglich, die Anzahl der Zellen, die Sie bei der Lösung von Abfragen zum nächsten Nachbarn untersuchen müssen, mithilfe von Volumengrenzen zu steuern.kD

Genauer gesagt: Wenn Sie nach einem ungefähren nächsten Nachbarn zu einem Abfragepunkt q fragen und der tatsächliche nächste Nachbar sich in der Entfernung d befindet , erhalten Sie in der Regel eine Suche, die jede Datenstrukturzelle untersucht, die von innen nach außen reicht außerhalb eines Kreisrings oder einer Ringschale mit Innenradius d und Außenradius ( 1 + ϵ ) d . Wenn die Zellen ein begrenztes Seitenverhältnis haben, wie es in einem Quadtree der Fall ist, können höchstens 1 / ϵ d - 1 solcher Zellen vorhanden sein, und Sie können nachweisen, dass die Zeit für die Abfrage gut begrenzt ist. Wenn das Seitenverhältnis nicht begrenzt ist, wie in a kϵqdd(1+ϵ)d1/ϵd1 Baum, diese Grenzen gelten nicht.kD

-Bäume hat einen anderen Vorteil gegenüber Quadtrees, dass sie garantiert höchstens logarithmisch Tiefe haben, die auch für eine nächste Nachbarn Abfrage der Zeit beiträgt. Die Tiefe eines Quadtree ist jedoch höchstens die Anzahl der Bits der Genauigkeit der Eingabe, die im Allgemeinen nicht groß ist, und es gibt theoretische Methoden zum Steuern der Tiefe, um im Wesentlichen logarithmisch zu sein (siehe die Quadtree-Datenstruktur zum Überspringen).kD

David Eppstein
quelle
4
Eine moderne Zusammenfassung komprimierter Quadtrees finden Sie in Sariel Har-Peleds neuestem Lehrbuch.
Jeffs
Vielen Dank für eine gute quantitative Zusammenfassung, David. Nur zur Bestätigung: Stimmt die Verwendung von "Seitenverhältnis" mit "Verzweigungsverhältnis" überein? Ich muss auf jeden Fall Quadrees / Octrees überspringen und Quadtrees / Octrees komprimieren.
Noldorin
1
Das Seitenverhältnis eines rechteckigen Kastens kann als das Verhältnis seiner längsten Kantenlänge zu seiner kürzesten Kantenlänge definiert werden. Ich weiß nicht, was Verzweigungsverhältnis in diesem Zusammenhang bedeuten soll, aber das Seitenverhältnis steht in keinem Zusammenhang mit dem Verzweigungsfaktor der Bäume (der für beide Datenstrukturen konstant ist).
David Eppstein
Ich habe die "Zellen in" verpasst. Macht jetzt Sinn.
Noldorin,
15

Eine Gruppe von Freunden und ich arbeiten an einem Weltraum-RTS-Spiel als lustiges Nebenprojekt. Wir verwenden eine Menge der Dinge, die wir in der Informatik gelernt haben, um sie hocheffizient zu machen und um später massive Armeen zu bilden.

Zu diesem Zweck haben wir über die Verwendung von KD-Bäumen nachgedacht, diese jedoch schnell verworfen: Einfügungen und Löschungen sind in unserem Programm äußerst häufig (betrachten Sie ein Schiff, das durch den Weltraum fliegt), und dies ist ein unheiliges Durcheinander mit KD-Bäumen. Wir haben uns deshalb Octrees für unser Spiel ausgesucht.

Alex ten Brink
quelle
Ah ja, das habe ich auch schon gehört. Das Einfügen / Löschen mit kd-trees ist eine kostenintensive Operation (aufgrund eines Neuausgleichs). Ich glaube jedoch, dass die Zeitkomplexitäten im besten Fall immer noch dieselben sind ...
Noldorin,
2
Es hängt davon ab, wie Sie den kd-Baum reparieren. Eine gute Best-Case-Zeitkomplexität ist nicht das, was ich allgemein anstrebe: Zum Beispiel hat Bogosort eine O (1) -Best-Case-Komplexität, aber ich hoffe, dass niemand sie verwendet.
Alex ten Brink
Leider kann ich keine guten Zusammenfassungen der Zeitkomplexität für allgemeine Operationen an diesen Datenstrukturen finden, aber das ist mir egal. Die Komplexität der Durchschnittszeit ist oft aufschlussreich ...
Noldorin
1
Ich denke wirklich, dass Sie es immer noch besser machen würden, wenn Sie nur einen KD-Baum verwenden würden, der Achsen durchläuft und einfach den Raum in der Mitte aufteilt. Überspringen Sie die umfangreichen SAH- und anderen teuren Medianschnitte und Sie erhalten etwas, das nicht nur schneller als ein Octree sucht, sondern auch schneller baut. Da Sie den Raum gleichmäßig aufteilen, wie Sie es mit einem Octree tun würden, aber mit einem binären Baum anstelle eines achtjährigen Baums, sollte das, was Sie zuvor für das Entfernen getan haben, mit dem KD-Baum nicht komplexer sein in ähnlicher Weise gleichmäßig verteilt sein. Beispiel: Sie können leere Knoten einfach über eine Tiefe von N entfernen.
Dragon Energy
8

Was sind die Vorteile von Octrees in Bezug auf räumliche / zeitliche Leistung oder auf andere Weise und in welchen Situationen sind sie am besten anwendbar (ich habe 3D-Grafikprogrammierung gehört)?

kD-Bäume sind ausgeglichene Binärbäume und Octrees sind Versuche, so dass die Vor- und Nachteile wahrscheinlich von diesen allgemeineren Datenstrukturen geerbt werden. Speziell:

  • Das Nachwuchten kann teuer sein (Octrees müssen nicht nachgewuchtet werden).
  • Das Auswuchten handhabt die Heterogenität besser, weil es anpassungsfähig ist.
  • Ein höherer Verzweigungsfaktor in Oktaven bedeutet flachere Bäume (weniger Indirektionen und Zuweisungen) für homogene Verteilungen.

Außerdem bietet sich eine Halbierung (wie in Oktaven) für eine triviale Implementierung in Bezug auf Bit-Twiddling an. Ebenso stelle ich mir vor, dass Octrees bei der Suche nach Reichweiten von vorberechneten Entfernungen in hohem Maße profitieren können.

BEARBEITEN

Offensichtlich müssen meine Hinweise auf Versuche und Homogenität geklärt werden.

Versuche sind eine Familie von Datenstrukturen, die durch Verzeichnisbäume dargestellt werden und als Wörterbücher für Schlüssel verwendet werden, die Sequenzen sind (insbesondere Zeichenfolgen, aber auch DNA-Sequenzen und die Bits in einem Hash-Wert für Hash-Versuche). Wenn jedes Wörterbuch jeweils ein Bit der x-, y- und z-Koordinaten abbildet (höchstwertiges Bit in der ersten Ebene des Versuchs, nächstwertiges Bit in der zweiten Ebene usw.), ist der Versuch ein Oktree, das den 3D-Raum gleichmäßig unterteilt. Octrees erben daher die Eigenschaften von Versuchen, die im Allgemeinen sind:

  • Ein hoher Verzweigungsfaktor kann flache Bäume bedeuten, für die nur wenige Indirektionen auftreten, sodass die Suche schnell vonstatten geht. Beispielsweise können 20 Ebenen eines Binärbaums in 4 Ebenen eines Baums mit einem Verzweigungsfaktor von 256 gespeichert werden.
  • Versuche werden während des Einfügens und Löschens nicht neu ausgeglichen, was eine teure Operation erspart, die für ausgeglichene Binärbäume erforderlich ist.

Der Nachteil ist, dass Heterogenität zu unausgeglichenen Versuchen / Octrees führen kann, sodass die Suche viele Indirektionen erfordern kann. Das äquivalente Problem bei Versuchen wird durch die Verwendung von Kantenkomprimierung gelöst, um mehrere Indirektionsebenen in einer einzigen Ebene zusammenzufassen. Octrees tun dies nicht, aber es gibt nichts, was Sie daran hindert, ein Octree zu komprimieren (aber ich glaube nicht, dass Sie das Ergebnis als Octree bezeichnen könnten!).

Betrachten Sie zum Vergleich ein spezialisiertes Wörterbuch für Zeichenfolgenschlüssel, das als Trie dargestellt wird. Die erste Stufe des Versuchs verzweigt sich auf das erste Zeichen im Schlüssel. Die zweite Ebene des zweiten Zeichens und so weiter. Nach einer beliebigen Zeichenfolge kann gesucht werden, indem nach dem ersten Zeichen aus dem Schlüssel im Wörterbuch gesucht wird, um ein zweites Wörterbuch zu erhalten, das zum Nachschlagen des zweiten Zeichens aus dem Schlüssel usw. verwendet wird. Ein Satz zufälliger Schlüsselfolgen wäre eine homogene Verteilung. Ein Satz von Schlüsselzeichenfolgen, die alle ein Präfix haben (z. B. alle Wörter, die mit "anti" beginnen), sind a heterogenVerteilung. Im letzteren Fall enthält das erste Wörterbuch nur eine Bindung für "a", das zweite nur eine für "n" und so weiter. Suchen Sie nach einer Zuordnung in der Liste, indem Sie immer dieselben vier Wörterbücher mit denselben vier Schlüsseln durchsuchen. Dies ist ineffizient und genau das tun Octrees, wenn sie zum Beispiel zum Speichern heterogener Partikelverteilungen verwendet werden, bei denen der größte Teil der Partikel in einem winzigen Volumen im Vektorraum liegt.

Jon Harrop
quelle
"Octrees sind Versuche"? Was meinen Sie mit "besser mit Heterogenität umgehen"? Homogen ist kein Wort, das mir in Bezug auf Bäume begegnet ist.
Noldorin
2
"Octtrees müssen nicht neu ausbalanciert werden"? Dies gilt absolut nicht für Octtrees, in denen heterogene Punktverteilungen gespeichert sind. Alternativ, je nachdem, wie allgemein Sie "Octtree" definieren: Das Neuausgleichen eines Octtree ist einfach unmöglich , egal wie wünschenswert es auch sein mag.
Jeffs
@Noldorin "Octrees sind Versuche". Ja. Weißt du was ein Trie ist? en.wikipedia.org/wiki/Trie
Jon Harrop
@Noldorin "Homogen ist kein Wort, das mir in Bezug auf Bäume begegnet ist". Ich beziehe mich auf die Homogenität der Distribution, die partitioniert wird. Wenn Sie beispielsweise Partikel in einem 3D-Raum aufteilen, sind die Atome in einem Festkörper homogen verteilt, während die Sterne im Universum heterogen verteilt sind. kD-Bäume sind für heterogene Verteilungen eher zu bevorzugen, da ihre Raumunterteilung adaptiv ist.
Jon Harrop
@ Jɛ ɛ E "Es ist einfach unmöglich, einen Octtree neu abzugleichen". Genau darauf bezog ich mich. Entschuldigung, wenn mein Wortlaut verwirrend war.
Jon Harrop
2

Octrees sind nützlich als Basisdatentyp für Kontinuumsmodelle, siehe zum Beispiel den Gerris Flow Solver. In der Strömungsmechanik ist das Leben schwierig genug, daher ist es ein vereinfachender Faktor, zu wissen, dass die Größe aller Ihrer Subcubes nur von ihrer Tiefe abhängt.

Einschränkung: Ich bin kein flüssiger Dynamiker!

jjg
quelle
Interessant. Ich kann definitiv zu schätzen wissen, dass es einfacher ist, mit Octrees in Kontinuumsmodellen zu arbeiten ... Ich frage mich, was der Grund für die Grafikprogrammierung ist.
Noldorin