Ich möchte in der Lage sein, eine große Population kleiner, sich unabhängig bewegender Objekte in Echtzeit zu rendern. Sie können sich schwarmartig bewegen, aber Ihre relativen Positionen sind nicht kohärent – ihre Position kann sich innerhalb eines Schwarms willkürlich ändern und Schwärme können sich zu jedem Zeitpunkt auflösen und reformieren.
Welcher Ansatz zum Aufbau einer begrenzten Volumenhierarchie passt am besten zu dieser Situation? eine Möglichkeit, eine Hierarchie beizubehalten, die nicht optimal, aber gut genug ist und nur eine teilweise Aktualisierung jedes Frames erfordert? Oder gibt es eine Möglichkeit, eine Hierarchie von Grund auf neu zu erstellen, die für eine reibungslose Animation schnell genug ist?
Die Anzahl der Objekte ist zu groß, um ohne Hierarchie gerendert zu werden. Aus dem gleichen Grund erwarte ich, dass das Erstellen der Hierarchie zeitaufwändig ist.
Nach dem Kommentar von John Calsbeek, falls meine Der Fokus auf das Begrenzen von Volumenhierarchien ist falsch, und es gibt bitte einen besseren Ansatz für die Speicherpartitionierung in dieser Situation antworte entsprechend. Ich bin auf der Suche nach etwas, das mit dem, was ich beschreibe, umgehen kann, einschließlich allem, woran ich nicht gedacht habe.
Kommentare
- Beschränken Sie absichtlich die Frage nach begrenzten Volumenhierarchien oder sind Sie offen für andere Formen der räumlichen Partitionierung?
- @JohnCalsbeek Ich ‚ habe zur Klärung bearbeitet – danke für den Hinweis auf meine versehentliche Einschränkung.
- Erwägen Sie, einen “ Schwarm “ als eine Einheit zu behandeln, wenn Schwärme zusammengeführt werden. Füge sie zu einem einzigen Schwarm zusammen. Wenn ein Einzelgänger zu weit wegwandert, wird er zu einem “ Schwarm “ von einem. Dies funktioniert am besten, wenn die Schwärme eher zusammenhängend sind und die Einzelgänger eher selten sind. Es gibt viele nette Möglichkeiten, mit dem “ -Schwarm zu spielen. “ ermöglicht es Mitgliedern, Schwärme nur dann zu wechseln, wenn sie es sind In Kontakt miteinander geht die Liste weiter und weiter.
Antwort
Erwägen Sie insbesondere die Verwendung von räumlichem Hashing Wenn Ihre Objekte ähnlich groß sind.
Teilen Sie Ihre Welt grundsätzlich in Rasterzellen mit einheitlicher Größe auf (2D und 3D sind je nach Umfang der vertikalen Bewegung gültige Möglichkeiten). Weisen Sie bei jeder Aktualisierung Ihr Objekt jedem überlappenden Fach zu. Wenn die Zellen im Verhältnis zu den Objekten eine angemessene Größe haben, sollten die meisten Objekte in einem einzelnen Fach landen.
Jedes Fach wird in eine Hash-Tabelle eingefügt. Der Schlüssel sind die Koordinaten des Behälters. (Sie können es sich auch als Hash-Tabelle mit mehreren Werten für denselben Schlüssel vorstellen und für jede überlappende Zelle einmal ein Objekt einfügen.)
In diesem Schema gibt es keine Hierarchie, die neu erstellt werden muss. Dies macht es gut für dynamische Szenen geeignet. Sie können die Abmessungen der Zelle dennoch grob gegen den Kegelstumpf oder gegen Okkluder testen und viele Objekte gleichzeitig verwerfen. Außerdem ist es einfacher, diese Struktur schrittweise zu verwalten. Sie können die Hash-Tabelle von Frame zu Frame beibehalten und Objekte nur dann von einem Bin in einen anderen verschieben, wenn sie die Grenze einer Zelle überschreiten.
Antwort
Sie könnten versuchen, die Begrenzungsvolumina einfach etwas größer als nötig zu machen, damit die Objekte nicht bei jeder Bewegung ihre Grenzen überschreiten, sondern andererseits. Sie müssten die Struktur ohnehin ab und zu neu erstellen.
Oder es gibt Grenzintervallhierarchie , die versucht, genau dies zu beheben Szenario.
Oder das Papier von Ingo Wald, Solomon Boulos und Peter Shirley mit dem Titel Raytracing deformierbarer Szenen unter Verwendung dynamischer Begrenzungsvolumenhierarchien könnte sein von Interesse.
Antwort
Ich möchte dem eine praktische Perspektive hinzufügen.
Lassen Sie Ich Vorwort, dass ich hier mit begrenzten Informationen arbeite:
- Ich weiß nicht, wie m Objekte, mit denen Sie es zu tun haben.
- Ich weiß nicht, wofür genau Ihre Beschleunigungsstruktur verwendet wird. Kegelstumpf Keulen? Ray Tracing? Kollisionserkennung zwischen Objekten in der BVH?
In Zukunft gehe ich davon aus, dass es sich um Kegelstumpf handelt, der einige tausend Objekte auswählt.
Die Anzahl der Objekte ist zu groß, um ohne Hierarchie gerendert zu werden. Aus dem gleichen Grund erwarte ich, dass das Erstellen der Hierarchie zeitaufwändig ist.
Ich würde argumentieren, dass, wenn Sie jedes Objekt in jedem Frame besuchen müssen, um eine BVH zu berechnen, das direkte Auslesen und ohne BVH tatsächlich schneller ist. Dies hängt natürlich von Ihrer Implementierung des Kegelstumpfes ab. Die Begrenzungsvolumina aller Objekte sollten zusammenhängend im Speicher gespeichert werden. Dies führt zu einer effizienteren CPU-Cache-Auslastung und ermöglicht eine weitere Optimierung mithilfe von SIMD-Anweisungen. DICE bietet eine vollständige Präsentation zu diesem Thema: Ausmerzen des Schlachtfelds: Datenorientiertes Design in der Praxis
In der Präsentation wird auch erwähnt, dass das Ausmerzen mithilfe eines einfachen Rasters noch schneller beschleunigt wird.
Da ich davon ausgehe, dass die meisten 3D- / Simulations- / Spielcode-Basen bereits eine Art von haben Die BVH-Klasse und ich wissen nicht, wie wichtig es für Sie ist, die BESTE Keulungsleistung zu erzielen. Ich möchte einige Argumente für das Festhalten an einer BVH vorstellen:
Je nachdem, welche Methode Sie verwenden, konstruieren Eine BVH kann schnell und einfach sein.
Meine aktuelle Implementierung einer binären BVH (jeder Knoten kann nur null oder zwei untergeordnete Elemente haben und jeder Blattknoten speichert nur ein Element), die für eine schnelle dauert für 1137 Objekte in einem einzelnen Thread eines i7-5960X bei 3,89 GHz ca. 0,18 ms. Ich bin mir sicher, dass es schneller gehen kann. Die Konstruktion wird durchgeführt, ohne dabei Speicher neu zuzuweisen (dies hat die Konstruktionsleistung verdoppelt).
Während SAH möglicherweise die beste BVH generiert, dauert es lange. SAH ist gut Für Dinge, die Sie vorberechnen können, wie z. B. Kollisionsnetze. Zur Laufzeit können Sie die Kollisionsnetze dann in eine BVH einfügen, die für die Echtzeitkonstruktion besser geeignet ist.
Ein schneller und einfacher BVH-Konstruktionsansatz (der I. „Ich verwende derzeit) dient zum Sortieren aller Objekte auf einer Achse (z. B. der längsten Achse des übergeordneten AABB) und zum Aufteilen der Sammlung in der Mitte.
Um die Geschwindigkeit noch weiter zu erhöhen, berechnen Sie die Knoten-AABBs NACH dem Erstellen des Baums durch Kombinieren der beiden untergeordneten Knoten-AABBs eines übergeordneten Knotens. Dadurch wird vermieden, dass alle Objekte durchlaufen werden (weitere zweifache Beschleunigung). Dies ist jedoch nur möglich, wenn Ihr Aufteilungskriterium nicht vom AABB des übergeordneten Knotens abhängt.