Wenn ein octree zur Kollisionserkennung in einem Spiel verwendet wird, sollte der Baum für jeden Frame neu erstellt werden oder gibt es einen besseren Weg, wenn man davon ausgeht, dass sich die Hälfte der Objekte in einem Frame bewegt?Sollte ein Octree in jedem Frame neu aufgebaut werden?
Wenn sich die Szene mit jedem Bild ändert, müssen Sie den Baum erneut erstellen.
Wenn Sie in Ihren Szenen viel statische Geometrie haben, sollten Sie separate Octrees erstellen. Sie können die gleiche Idee auch durch komplexere Blattknoten ausdrücken, die zwischen statischer und nichtstatischer Geometrie unterscheiden.
Fazit: nur regenerieren, was Sie müssen.
Wenn Sie sehr dynamische Daten haben, die jeden einzelnen Frame verschieben und trotzdem die Kollisionserkennung beschleunigen müssen, empfehle ich Ihnen, ein festes 3D-Raster dafür zu verwenden. 2-dimensional äquivalent:
Es kann auch als eine freie Liste verdoppeln über konstante Zeit Umzug zu ermöglichen, wie so (unter Verwendung des next Index entweder als ein Index zu dem nächsten Element in der gleichen Rasterzelle oder das nächste freie Element von dem freien Stapel abspringt, wenn er entfernt wurde):
Ein weiteres Beispiel:
Jetzt in 3 Dimensionen, könnte es scheinen, als würde es explosiven Speicher erfordern. Der Trick besteht jedoch darin, jede Zelle einen 32-Bit-Index in ein Array speichern zu lassen und im Grunde als einfach verknüpfte Indexliste zu dienen. Das reduziert die Größe jeder Zelle auf 32 Bit. Wenn Sie jetzt ein 100x100x100-Raster (1 Million Zellen) speichern, würde das weniger als 4 Megabyte benötigen.
Wenn Elemente sich bewegen, können Sie sie einfach aus den Zellen entfernen, die sie belegen, verschieben und in die neuen Zellen einfügen. Alles, was Sie tun müssen, um dies zu tun, ist, einige 32-Bit-Indizes zu manipulieren (keine Speicherzuweisung/-freigabe, um Elemente von einem Zellensatz auf andere zu übertragen). Dies ist alles konstante Zeit und erfordert keine Neubalancierung von Bäumen oder das Aufspalten von Oktanten, die zu voll werden oder ähnliches.
Sie können auch eine Rasterhierarchie verwenden (dies klingt vielleicht wie ein Octree, aber anders). Was ich damit meine, ist, dass Sie ein grobes Raster für ganze Mesh-Objekte in Ihrer Szene haben. Dann kann jedes Gitterobjekt ein grobes Gitter, beispielsweise 10 × 10 × 10, für jeden seiner Teile speichern. Dann speichert jeder Teil ein feines Gitter oder Octree für jedes seiner Polygone. Dies ermöglicht nicht-organische Netze, die beispielsweise starr mit Teilen sind, die sich nur wie ein Roboter drehen, um zu vermeiden, das feine Gitter/Octree von Polygonen aktualisieren zu müssen und nur sein eigenes grobes Gitter von Teilen und das grobe Gitter von Weltobjekten zu aktualisieren es beginnt, seine Beine und Arme zu drehen, z Nur organische Modelle müssen ihre feinen Gitter aktualisieren, wenn sie durch Knochen deformiert werden, z. Der Octree, den ich für Ihre komplett statischen Elemente/Teile behalten würde, die nie per-Frame aktualisiert werden müssen, würde ich mit einem schönen Octree verwenden, spärlich mit vielleicht einer Nachbearbeitung für Cache-freundlichen Speicherzugriff. Sie haben etwas mehr Zeit zur Verfügung, um Suchvorgänge in diese zu beschleunigen und ihren Speicherverbrauch zu minimieren, wenn Sie davon ausgehen können, dass der Octree nach dem Aufbau nie aktualisiert werden muss.
Wenn sich die Szene mit jedem Bild ändert, müssen Sie den Baum aktualisieren. Es ist nicht immer notwendig, den gesamten Baum "wiederherzustellen". Meine eigene Implementierung kann nach Bedarf aktualisiert werden, wenn Objekte verschoben werden.Ob du das kannst oder nicht, hängt davon ab, wie du es implementierst. – phkahler
Redo == Aktualisierung; Ich betrachte sie als Synonyme. Aber dein Standpunkt ist richtig - es ist fast so, als würdest du eine schmutzige Flagge brauchen, um Teile zu markieren, die sich verändert haben. – duffymo