Bei Verwendung eines octree sollte der Baum für die Kollisionserkennung in einem Spiel bei jedem Frame neu aufgebaut werden, oder gibt es einen besseren Weg, wenn man davon ausgeht, dass sich die Hälfte der Objekte in einem Frame bewegt?
Antworten
Zu viele Anzeigen?
luke
Punkte
34409
Wenn Sie viele statische Geometrien in Ihren Szenen haben, sollten Sie in Erwägung ziehen, separate Octrees zu erstellen. Sie könnten die gleiche Idee auch durch kompliziertere Blattknoten ausdrücken, die zwischen statischer und nicht-statischer Geometrie unterscheiden.
Fazit: Regenerieren Sie nur, was Sie müssen.
Nicht registrierter Benutzer
Punkte
0
Wenn Sie sehr dynamische Daten haben, die sich in jedem Einzelbild bewegen, und dennoch die Kollisionserkennung beschleunigen müssen, empfehle ich, ein festes 3D-Gitter zu verwenden. 2-dimensionales Äquivalent:
Sie kann auch als freie Liste verwendet werden, um Entfernungen in konstanter Zeit zu ermöglichen, etwa so (unter Verwendung der next Index entweder als Index für das nächste Element in derselben Gitterzelle oder für das nächste freie Element, das vom freien Stapel abgezogen wird, wenn es entfernt wurde):
Ein weiteres Beispiel:
In 3 Dimensionen könnte man meinen, dass dies einen explosiven Speicher erfordert. Der Trick besteht jedoch darin, dass jede Zelle einen 32-Bit-Index in einem Array speichert und im Grunde als einfach verknüpfte Indexliste dient. Dadurch wird die Größe jeder Zelle auf 32 Bit reduziert. Wenn man nun ein 100x100x100-Gitter (1 Million Zellen) speichert, würde das weniger als 4 Megabyte benötigen.
Wenn Elemente verschoben werden, können Sie sie einfach aus den Zellen, in denen sie sich befinden, entfernen, sie verschieben und in die neuen Zellen einfügen. Alles, was Sie dafür tun müssen, ist, einige 32-Bit-Indizes zu manipulieren (keine Speicherallokation/-deallokation, um Elemente von einer Gruppe von Zellen in eine andere zu übertragen). Das alles geschieht in konstanter Zeit und erfordert keine Neuordnung von Bäumen oder Aufteilung von Oktanten, die zu voll werden, oder ähnliches.
Sie können auch eine Hierarchie von Gittern verwenden (das klingt vielleicht wie ein Octree, ist aber anders). Was ich damit meine, ist, dass Sie ein grobes Raster für ganze Mesh-Objekte in Ihrer Szene haben könnten. Dann könnte jedes Mesh-Objekt ein grobes Raster, sagen wir 10x10x10, für jedes seiner Teile speichern. Dann speichert jedes Teil ein feines Gitter oder einen Octree für jedes seiner Polygone. Dies ermöglicht es nicht-organischen Meshes, die z.B. starr sind und deren Teile sich nur drehen, wie z.B. ein Roboter, das Fine Grid/Octree der Polygone nicht aktualisieren zu müssen, sondern nur sein eigenes Grobgitter der Teile und das Grobgitter der Weltobjekte zu aktualisieren, wenn er z.B. seine Beine und Arme zu drehen beginnt.
Die octree würde ich für Ihre völlig statische Elemente/Teile, die nie pro Frame aktualisiert werden müssen, und ich würde eine schöne octree, sparse mit vielleicht einige Post-Processing für Cache-freundlichen Speicherzugriff verwenden. Sie haben ein bisschen mehr Zeit zur Verfügung, um die Suche in diese zu beschleunigen und ihre Speichernutzung zu minimieren, wenn Sie davon ausgehen können, dass der Octree nie aktualisiert werden muss, sobald es gebaut ist.
