Wie ist der Stand der Technik bei der Raumteilung für Spiele? [geschlossen]

Ich kenne BSP-Bäume, Octrees und Portal, die lange Zeit verwendet wurden. Aber moderne Spiele benutzen immer noch diese Systeme oder sie benutzen neue Dinge?

Wenn es mit Vor- und Nachteilen möglich ist, unter Berücksichtigung von Rendering und Kollisionserkennung.

Ja, die Unreal Engine 3 verwendet zum Beispiel immer noch ein BSP - hauptsächlich, weil es während des CSG-Prozesses verwendet wird. Doom3 / id Tech 4 verwendet Portale und ich glaube, ich habe etwas gelesen, dass id Tech 5 zurück zu BSP-Bäumen ist. Es gibt auch Spiele, die Octrees verwenden. Ich verstehe im Spiel, dass UE3 mit Okklusionsabfragen zu einem dynamischeren Ansatz übergegangen ist, aber ich wäre überrascht, wenn sie das BSP nicht verwenden, um zumindest zu bestimmen, welche statischen Netze in Sicht sind. In anderen Spielen wird möglicherweise nur das Auswerfen von Ansichten (z. B. Civilization) verwendet. Es hängt wirklich davon ab, welche Art von Spiel Sie sehen.

Der Grund, warum es BSPs und ähnliches immer noch gibt, ist, dass man es nicht viel besser machen kann. Wenn Sie statische Geometrie haben, ist ein BSP großartig, wenn Sie es richtig konstruieren. Sie müssen jedoch einen BSP-Builder schreiben, was schwierig ist (was jedoch kostenlos passieren kann, wenn Ihre CSG-Lösung einen verwendet!). Octrees und dynamischere Lösungen (wie das Verlassen auf Okklusionsabfragen für alles) sind einfacher zu implementieren und haben eine höhere Laufzeit kosten aber nicht erfordern (teure) vorverarbeitung der ebenen. Dies ist ein Kompromiss, den einige Spiele eingehen möchten (Crytek möchte zum Beispiel, dass alles in Echtzeit ausgeführt wird, sodass sie keine Verarbeitungszeit für den Aufbau einer statischen Beschleunigungsstruktur aufwenden.) Andere Laufzeitansätze sind zum Beispiel Software-Rasterisierung der CPU und Ausführen von Okklusionsabfragen auf der CPU (dies wird von der Frostbite-Engine verwendet.)

Schauen Sie sich für einen wirklich modernen Ansatz Umbra an , eine Middleware für Sichtbarkeitsabfragen. Wenn Sie ein wenig im Internet suchen, sollten Sie einige der Masterarbeiten finden, die die frühen Anfänge von Umbra beschreiben.

Fazit: Ob Sie ein BSP / Octree / no AS verwenden möchten, hängt stark von der Art des Spiels ab, das Sie erstellen möchten. Wenn Ihre Ebenen meist statisch sind, sollten Sie dies ausnutzen und eine statische Beschleunigungsstruktur aufbauen. Wenn alles dynamisch ist, brauchen Sie natürlich einen anderen Ansatz.

Für die Kollisionserkennung würde ich mir Bullet und PhysX und ihre Kollisionserkennungsalgorithmen ansehen. Ich bin jedoch der Meinung, dass die Physiklösungen weniger an die Sichtbarkeit gebunden sind als früher - eine Physiklösung möchte möglicherweise einen auf einer GPU basierenden BVH verwenden. In diesem Fall ist es nicht sinnvoll, dies für Sichtbarkeitsabfragen zu verwenden.

Ich weiß ehrlich gesagt nicht, welche Motoren der nächsten Generation derzeit verwendet werden, aber ich werde Ihnen sagen, was ich weiß. Es ist leicht, eine Optimierung mit der Datenstruktur zu verwechseln, die für diese Optimierung verwendet wird. Alle unten genannten Punkte dienen der Optimierung, aber ich werde darauf hinweisen, welche Datenstrukturen spezifisch sind.

BSP : Datenstruktur - Zur Erkennung von Schnittpunkten zwischen sich dynamisch bewegenden Objekten und statischer Weltgeometrie. Wurde verwendet, um Kollisionen zu erkennen und Geometrie korrekt ohne Z-Puffer zu rendern, wird jedoch nicht mehr für das Rendern verwendet, da wir seit Tagen über genügend Speicher für Z-Puffer verfügen. Sie werden technisch etwas anders generiert, aber immer noch als derselbe Baumtyp betrachtet. Benötigt Vorverarbeitung.

Octree oder Kd-Tree : Datenstruktur - wird verwendet, um zu bestimmen, welche Objekte sich in derselben "Zelle" oder in demselben Bereich befinden, um zu vermeiden, dass alle dynamischen Objekte einer n ^ 2-Prüfung unterzogen werden.

Dies sind nicht die einzigen, aber wahrscheinlich die häufigsten. Es gibt auch viele Optimierungen, mit denen die Engine das Rendern von Geometrie im Allgemeinen vermeiden kann. Aber das Folgende beschreibt nur die Geometrie und das ist normalerweise alles, wofür es verwendet wird:

Portale : Technisch gesehen keine Datenstruktur, aber für das Culling ist eine spezielle erforderlich. Wird für die Sichtbarkeitsauslese von Weltgeometrie und dynamischer Objektgeometrie aus der Ansicht verwendet. Benötigt Vorverarbeitung, um die Welt in Bereiche zu unterteilen, die ich denke. Aber ich habe das noch nicht implementiert, also weiß ich es nicht.

Occlusion Culling : Optimierung - wird für die Sichtbarkeitsanalyse beliebiger, wahrscheinlich dynamischer Objekte verwendet.

Normale Ansichtsfenster-Auswahl : Optimierung - Auswahl von Objekten, die sich nicht in der Ansicht der Kamera befinden.

Mehr Auslese von Ansichtsfenstern : Optimierung - Das regelmäßige Auslesen von Ansichtsfenstern kann mithilfe eines Octrees noch weiter optimiert werden. Sie können ganze Zellen des Octrees entfernen, die sich hinter der Kamera befinden oder nicht in ihrer Ansicht sind. Dies schließt Geländefelder ein (wenn Sie draußen sind). Was auch immer nicht durch das Octree ausgesondert wird, Sie würden "reguläres Viewport-Culling" durchführen. Dann würden Sie, was auch immer übrig bleibt, rendern.

Backface Culling : Optimierung - Entfernt die Geometrie von der Kamera, um ein Rastern zu verhindern. Wird normalerweise in Hardware ausgeführt, wenn der Render-Status richtig eingestellt ist.

Sonderfalldatenstrukturen:

AABB-Bäume oder Kugelbäume : Hierbei handelt es sich um spezielle Falldatenstrukturen. Sie verwandeln eine konkave Form in eine konvexe. Zum Beispiel ist ein Charakter mit Knochen technisch konkav. Es zerlegt es in kleinere konvexe Stücke. Kann als Optimierung für die Kollisionserkennung und Sichtbarkeitsanalyse dynamischer Objekte (normalerweise) verwendet werden und erleichtert die Durchführung von Kreuzungstests, da diese konvex sind. Dies würde in einem Octree liegen, da es sich in der Regel um dynamische Objekte handelt. Diese können auch verwendet werden, um die Optimierung der Okklusionsentfernung zu unterstützen.

Es gibt keinen Grund, warum Sie eine einzige Struktur verwenden müssen, um alles darzustellen (z. B. ein Szenendiagramm). Meiner Meinung nach ist es besser, unterschiedliche Datenstrukturen für unterschiedliche Aufgaben zu verwenden, als zu versuchen, eine Art Allzweckbaum zu verwenden. Zum Beispiel plane ich für die Engine, an der ich gerade arbeite, eine BSP / Octree / AABB-Baumkombination mit den folgenden Optimierungen zu implementieren: Okklusions-Culling, Ansichtsfenster und natürlich Backface-Culling. Dies bedeutet, dass ich einen BSP-Baum, einen Octree und wahrscheinlich mehrere AABB-Bäume in diesem Octree haben werde.

Die Auswahl der besten Datenstrukturen und Algorithmen / Optimierungen ist wahrscheinlich die größte und vorteilhafteste Maßnahme, die Sie für Ihren Motor ergreifen können.