Sind Octrees, Kd-Trees, BSP nur für statische Geometrie sinnvoll?

7

Ich implementiere immer noch mein Szenendiagramm (siehe diese Frage ). Nun frage ich mich, ob eine räumliche Darstellung wie ein Kd-Tree oder Octree für View Frustum Culling (VFC) nur bei statischer Geometrie sinnvoll ist. Der Grund für meine Zweifel ist, dass dynamische Geometrie normalerweise ein kleiner Teil der Szene ist, während statische Geometrie sehr groß sein kann und dynamische Geometrie die Aktualisierung der räumlichen Darstellung in jedem Frame erfordert.

Deine meinungen?

Tunnuz

performance scene-graph tunnuz
quelle

Antworten:

9

Im Allgemeinen habe ich einen separaten Partitionsbaum für statische und dynamische Objekte verwendet oder ihn für dynamische Objekte einfach ganz ignoriert. Dies bietet die Vorteile beider Welten:

  • Statische Objekte erfordern keine Neuberechnung des Baums in jedem Frame
  • Dynamische Objekte erfordern nur die Neuberechnung eines minimalen Baums

Wenn das ständige Zeichnen Ihrer dynamischen Objekte nicht zu viel Leistung bringt, kann es manchmal besser sein, auf die Neuberechnung eines Baums für sie in jedem Frame zu verzichten.

Eine weitere Optimierung besteht darin, den Baum nur dann neu zu berechnen, wenn sich Objekte um eine bestimmte Strecke bewegt haben oder sich mit ausreichend hoher Geschwindigkeit fortbewegen. Andernfalls erhalten Sie wahrscheinlich ohnehin in jedem Frame denselben Baum.

Sean James
quelle
Tolle Antwort, ich habe so etwas erwartet. Verwenden Sie normalerweise unterschiedliche Datenstrukturen für dynamische und statische Geometrie? Gibt es ein Ad-hoc-Verfahren, um die beiden Strukturen bei der Kollisionserkennung zwischen statischen und dynamischen Objekten "zu treffen"?
Tunnuz
2
Die Verwendung derselben Datenstruktur ist normalerweise am einfachsten, da die Implementierung bereits geschrieben wurde und daher auch weniger Möglichkeiten für das Auftreten von Fehlern bestehen. Manchmal reichen jedoch die Überprüfung der Begrenzungskugeln für dynamische Objekte aus, verglichen mit dem Aufwand für das Erstellen eines gesamten Baums, insbesondere wenn sich die Objekte stark bewegen. In diesem Sinne kann es vorteilhaft sein, ein weniger aggressives Partitionierungssystem für dynamische Objekte zu schreiben, um die Berechnungszeiten niedrig zu halten und einen aggressiveren, aber rechenintensiven Algorithmus für statische Objekte zu verwenden.
Sean James
2
Ich fand, dass Gitter für dynamische Objekte besonders gut funktionieren. Sie sind einfach und schnell.
Kröte