Welche Bibliothek für Octrees oder KD-Bäume? [geschlossen]

8

Gibt es robuste performante Bibliotheken zum Indizieren von Objekten?

Objekte hätten selbst Grenzen, anstatt durch Punkte dargestellt zu werden. und ein Objekt könnte sich daher in mehr als einem Fach befinden, wenn der Index Dinge in Partitionen fester Größe unterteilt.

Es würde das Ausmerzen von Kegelstumpf und das Besuchen von Objekten, die von einem Strahl getroffen wurden, sowie die Suche nach Nachbarschaften erfordern.

Ich kann viele Artikel finden, die die Mathematik für die Bestandteile zeigen, oft als Algebra und nicht als einfaches C, aber nichts, was alles zusammenfügt (außer vielleicht Ogre, obwohl PyOrge anscheinend den Octree nicht verfügbar macht ). Sicherlich müssen Hobby-Spielehersteller nicht alle ihre eigenen spartialen Indizes erstellen?

(Ich setze mich hin und schreibe meine eigene Kugel-Kugel, Kugel-Strahl, Strahl-Aabb, Kegel-Aabb, Kegel-Fustrum, Aabb-Fustrum und Octree-Implementierung; sicherlich gibt es einen besseren Weg, dh jemand hat dies bereits getan und a nettes Paket?!?!)

(Python oder C / C ++ mit Bindungen bevorzugt)

python octree frustum Wille
quelle

Antworten:

10

Sicherlich müssen Hobby-Spielehersteller nicht alle ihre eigenen Oktrees machen?

Wenn sie nicht etwas Größeres verwenden (wie Ogre oder eine andere Physik- / Rendering-Engine), tun dies viele. Ein Octree ist eine ziemlich einfach zu implementierende Struktur, und es gibt viele Kompromisse:

  • Ist das Octree aufdringlich oder nicht? Wenn es aufdringlich ist, erhalten Sie eine bessere Cache-Leistung, aber größere Strukturen.
  • Wenn es nicht aufdringlich ist, speichert es Zeiger oder eine Art sicheren Griff?
  • Wird es flach oder mit untergeordneten Zeigern gespeichert?
  • Wie typsicher ist es? Wenn Vorlagen verwendet werden, ist dies bei minimalem Laufzeitaufwand viel sicherer, aber viel schwieriger an Python zu binden.
  • Jeder Octree mit räumlicher Abfrage muss eine Art Vektor- / Punkt- / Strahlentyp enthalten, und jeder mit Kegelstumpf-Keulung wird eine Kegelstumpf- und Matrix-Mathematikroutine enthalten. Ist das Schreiben des Codes für die Schnittstelle zu dem Dutzend Matrix- / Vektorklassen, die Sie bereits aus allen anderen Bibliotheken gezogen haben, die Sie verwenden, tatsächlich weniger Arbeit als nur das Schreiben des gewünschten Basis-Octrees?
  • Ist es threadsicher?

That being said, es Online viele Octree - Implementierungen sind . Gehen Sie einfach nicht davon aus, dass Sie durch das Ergreifen eines dieser Elemente viel Arbeit sparen, und gehen Sie nicht davon aus, dass es einen wahren Weg gibt, eine andere Datenstruktur als ein Array zu erstellen.


quelle
Schöner Einblick! Ich frage mich, wie es für KD-Bäume ist. Was ich von ihnen gesehen habe, ist, dass sie hübsch zu implementieren sind (es gibt viele knifflige Details, die berücksichtigt werden müssen). Vielleicht weiß jemand mehr darüber?
Nef
Sind kd-Bäume tatsächlich schwieriger zu implementieren? Ich denke, es ist schwieriger, darüber nachzudenken, insbesondere ohne Bilder zu zeichnen, da sie die Geometrie weniger intuitiv aufteilen. Die grundlegenden Algorithmen zum Erstellen / Abfragen sind jedoch nicht länger oder weniger erforscht als der Octree.
2
Ein Octree ist eigentlich nur ein Sonderfall-KD-Baum. Mit festen Positionsaufteilungsebenen. Wenn Sie KD-Bäume implementieren, benötigen Sie eine Möglichkeit, Ihren "besten" Achsenaufteilungsversatz pro Knoten zu finden.
nichtig
2

Um fair zu sein, wurde der verknüpfte Python Octree im Jahr 2006 veröffentlicht, sodass Python-Ogre die Octree-Klasse möglicherweise bereits verfügbar gemacht hat.

Wenn ich jedoch die Ogre-Quellen durchschaue, sehe ich zwei Octree-Implementierungen: eine in Plugins/OctreeSceneManager/OgreOctree.hund eine in Plugins/OctreeZone/OgreOctreeZoneOctree.h.

Wenn Sie mich auf den zeigen, den Sie benötigen, werde ich ihn auf meine Aufgabenliste für meinen eigenen handgeschriebenen Python-Wrapper setzen (er ist auf bitbucket verfügbar und in meinem Profil verlinkt).

Wie auch immer - Viel Glück. : D.

jsandell
quelle
das ist ein sehr freundliches Angebot; Ich habe aber schon meine eigenen geschrieben.
Will
1

Ich habe hier Code für eine Python-Octree-Implementierung gefunden , indem ich einfach 'Octree-Python' gegoogelt habe. ; D.

Es ist nicht bibliotheksabhängig (obwohl ursprünglich für PyOgre geschrieben) und wird gut kommentiert.

Die kommunistische Ente
quelle
Eine Sache, die ich in Pure-Python-Octrees gefunden habe, ist, dass der zusätzliche Overhead für Funktionsaufrufe für das Durchlaufen von Bäumen Ihre Laufzeit schnell dominiert und sie schlechter macht als einfache Suchen in Listen, für jede Menge von Objekten, die Sie in Pure-Python sowieso verarbeiten könnten. Dieses spezielle Beispiel sieht auch sehr unoptimiert aus.
Das ist zwar ein gutes Stück Code, das Sie verdauen sollten, wenn Sie Ihren eigenen Octree erstellen möchten, aber in diesem Octree fehlen sofort alle Funktionen - zum Beispiel Ray- und Fustrum-Schnittpunkte -, die ich in der Frage zitiert habe. Tatsächlich gibt es nicht einmal eine Suche nach dem nächsten Nachbarn. Ich frage mich, wofür sie diesen Octtree verwenden, wenn sie Daten eingeben, aber nicht anders als nach genauem Punkt abfragen können. Und es speichert eher Punkte als Dinge mit Grenzen. Ich liste all diese Mängel auf, da dies auf alle Python-Octrees hinweist, die ich im Web gefunden habe. Vielleicht finden andere einen volleren Octree bei Google? Ich kann nicht :(
Will
1

Nachdem ich einige der oben genannten Pakete erfolglos ausprobiert hatte, fand ich RTree , einen Wrapper um libspatialindex .

glennr
quelle