Scene Rendering

[Jonathan]

Ich möchte demnächst das Grafikgrundgerüst meines Spiels umstellen, da mir der bisherige Ansatz zu langsam vorkommt. Gedacht ist das ganze erstmal für einen Egoshooter, aber auch Spiele aus der TopDown Ansicht könnten in nächster Zeit interessant werden.



Aktuell besteht meine Szene prinzipiell aus einem Haufen Objekten, die sich auf einem Gelände (bzw. Boden) befinden. Dieses Entitysystem finde ich ansich ganz nett, man kann einfache statische Objekte durch verschiedene Komponenten erweitern, die dann jeweils auf Ereignisse in der Spielwelt (oder auch Nutzereingaben) reagieren können, wodurch man eigentlich die Spiellogik ganz gut umsetzen kann.
Jedes dieser Entitys hat jetzt ein Modell-Objekt. Das kann ein 3D Modell mit zugehörigem Material laden und rendern. Im Hintergrund sind dabei ein paar Manager die sich darum kümmern, dass Ressourcen nur einmal geladen werden müssen, aber prinzipiell kann sich jedes Modell eigenständig rendern. Die nötigen Shader werden dazu aus den materialeigenschaften generiert, was hässlich wird, sobald mal 'globale' Effekte, wie Lichtquellen oder Schatten hat. Dafür hat im Moment jedes Material eine Referenz auf ein 'LightSetup' um die entsprechenden Lichtquellen in den Shader berücksichtigen zu können.

Nun, der Ansatz funktioniert und war auch nicht sonderlich komplex umzusetzen, aber es ist langsam. Da jedes Modell eigenständig ist, wird für jedes Entity quasi alles neu gesetzt. Ein paar Test in gDebugger ergaben, dass das ganze die CPU scheinbar echt zum schwitzen bringt. ShadowMapping scheint die Sache weder durch die hohe Füllrate noch durch den komplexen Shader auszubremsen, sondern schlicht deshalb, weil alle Objekte zweimal gezeichnet werden müssen. Viele Statechanges halt.

Ein paar Optimierungen sind natürlich schon drin: Ich habe ein ViewFrustum Culling für die Objekte, die in einem Quadtree (da das Spielfeld sehr flach ist) eingebaut, was die Sache auch deutlich beschleunigt. Dieser Quadtree wird derzeit auch für Kollisionsabfrage benutzt.



Jetzt will ich das ganze dahingehend umbauen, dass ich eine Art Scenengraph (ob es wirklich ein Graph sein wird, weiß ich noch nicht) programmieren will, indem sich die Entitys einfach mit ihrem Modell registrieren und der dann sämtliche Renderarbeiten übernimmt. Das sollte eine ganze Reihe an Optimierungen zulassen und das Rendern deutlich beschleunigen. Jetzt ist meine Frage, wie würde ich das ganze aufbauen?
Man möchte ja vermutlich Objekte mit dem selben Material irgendwie gruppieren um diese dann hintereinander Zeichnen zu können, um StateChanges zu sparen. Wonach sortiert man da so? Spontan würde ich sagen, dass Shader neu setzen aufwändiger ist, als eine Textur zu ändern. Wie geht man das Problem an, dass der Shader nicht nur die Materialeigenschaften sondern auch die Beleuchtungsinformationen (Lichtquellen, Schatten, usw.) berücksichtigen muss? Irgendwie muss man den doch generieren, oder legt man sich da auf 1-5 hardkodierte Shader fest? Wie gesagt, bislang hab ich die Shader im Code generiert, aber das ist ziemlich fummelig zu programmieren, vielleicht gibt es da ja bessere Möglichkeiten.
Und wie sieht es mit verbessertem Culling aus? Ich denke, für Outdoorszenen ist ein Baum schon ganz cool, aber was ist mit Objekten, die genau auf der Grenze liegen (bisher hatte ich die dann einfach in einem höheren Node liegen). Macht es vielleicht sogar Sinn, erst den Baum zu durchlaufen und alle Objekte in eine Temporäre Liste zu speichern, die dann nochmal nach Material oder was auch immer sortiert wird?
Früher oder später hätte ich auch gerne Indoor Szenen. Da sieht man ja meistens nur einen winzigen Teil des Levels, wie cullt man da am besten? Man hört ja von Portalen, wo das Level in mehrere Bereiche aufgeteilt, und man zeichnet nur den Bereich, in dem sich die Kamera befindet und die, die man durch Portale sehen kann. Da man das Frustum auf diese Portale beschneiden kann, wird man so wohl recht effektiv Dinge wegschneiden können. Aber was passiert, wenn man den selben Knoten durch unterschiedliche Portale sehen kann? Wenn 2 Fenster nebeneinander liegen und man nach draußen guckt, wird die komplette Außenwelt dann doppelt gerendert, oder wird gespeichert, welche Bereiche schonmal gerendert wurden (was natürlich das Beschneiden des ViewFrustums schwierig macht).


Hier sollten ja eigentlich einige rumspringen, die sich mit derlei Fragen schon beschäftigt haben, aber vielleicht hat ja auch jemand ein paar ganz gute Artikel zu dem Thema. Ich habe zwar immer mal wieder etwas in die Richtung gelesen, aber Texte von vor 5 Jahren müssen ja heute nicht mehr unbedingt empfehlenswert sein.

[Schrompf]

Puh, das sind gleich ne Menge Themen.

a) Der Scene Graph
Die Splitterwelten-Engine rendert nicht direkt jedes Objekt sofort aus, sondern erstellt beim Abklappern der zeichenbaren Objekte nur eine Liste von Zeichenaufgaben. Die werden dann sortiert (nach Reihenfolge Vertex-Deklaration, Shader, Textur, Mesh, Parameter) und erst danach ausgerendert. Hat uns (vor langer Zeit) eine Verdopplung der Framerate eingebracht. Und das war noch zu Zeiten, als wir einen Gelegenheitsgrafiker und demzufolge etwa 10 verschiedene Texturen und Shader hatten. Heutzutage sind es eher tausend.

Du kannst es wie ich machen und bei jedem Renderpass neu die Liste zusammenstellen und sortieren. Theoretisch gilt die Sortierung ja aber auch, wenn Du alle potentiellen Zeichenaufgaben zusammenstellst, sortierst und dann pro Pass nur die sichtbaren Renderjobs ausführst. Damit musst Du nur noch bei Szene-Änderungen neu sortieren. Damit ist dann allerdings die Renderjob-Reihe auf festgenagelt - jede Änderung am Licht-Setup oder bei den Splitterwelten die Render-Alternativmodi würden eine zusätzliche separate Liste von Renderjobs erfordern. Hat beides seine Vor- und Nachteile. Randbemerkung: Das Sortieren der Renderjobs ist hier so im Bereich einiger Zehntel Millisekunden. Wenig, aber nicht null.

b) Objekte in Sichtbarkeit-Beschleunigungsstrukturen

Ein Octtree oder Quadtree ist ne feine Sache. Für Objekte auf der Kante gibt es mehrere klassische Lösungen. Das Objekte in der Hierachie nach oben zu schieben ist eine Idee. Eine andere wäre es, die lokalen Grenzen des Tree-Nodes um den Objektbereich zu erweitern, so dass Du die Objekte nur noch nach Mittelpunkt an Tree-Nodes zuordnen kannst und trotzdem kein Objekt aus Versehen beim Rendern auslässt. Das macht die Splitterwelten-Engine.

Randbemerkung: nicht übertreiben mit dem Culling. Zum Einen lassen auch viele aktuelle Engines gern mal was durchrutschen, was zu verschwindenen Objekten oder springenden Schatten führt. Das ist hässlich, scheint aber außer mir niemanden zu stören. Zum Anderen sind zu viele kleinteilige Sichtbarkeitsprüfungen für die aktuellen Prozessoren auch problematisch. Die Battlefield3-Variante, alle potentiellen Renderjobs mit ihren Bounding Spheres in einer Liste zu sammeln und linear durchzurattern, hat mich auch etwas beeindruckt. Und sie ist perfekt parallelisierbar.

c) Zusätzliche Sichtbarkeitseingrenzungen

Mach Dir die grundsätzliche Herangehensweise klar. Ein Standard-Kamera-Frustum z.b. beschreibt eine Methode, um erstmal von "sichtbar" auszugehen und dann zu bestimmen, welche Objekte komplett jenseits einer Grenzebene liegen und demzufolge unsichtbar sind. Die Gegen-Herangehensweise sind Portale: Du gehst erstmal grundsätzlich von "unsichtbar" aus und bestimmst dann über die aktuelle Zone und die mittels Portalen erreichbaren benachbarten Zonen, welche Objekte sichtbar sind. Beides sind valide Herangehensweisen.

Bei den Splitterwelten nehme ich Methode a) - alles ist grundsätzlich sichtbar und ich lasse nur weg, was ich zuverlässig ausschließen kann. Ich habe aber meine Frustum-Klasse so gestaltet, dass ich zusätzliche Unsichtbar- und Sichtbar-Volumen hinzufügen kann. Ersteres wird von Blockern umgesetzt, die anhand ihrer Silhouette aus der aktuellen Kamera-Perspektive Unsichtbar-Volumen zum aktuellen Frustum hinzufügen. Objekte, die vollständig in diesem Volumen liegen, kann ich auch vom Rendern ausschließen, obwohl sie eigentlich innerhalb des Kamera-Frustums liegen. Der Gegenentwurf dazu sind Portale, die quasi genauso funktionieren, nur halt "Sichtbar"-Volumen generieren. Ich sortiere pro Zeichenprozess die Volumen so, dass sie einander ergänzen. Und pro Objekt gehe ich dann die Liste durch und ermittle die Auswirkung: Ausgehend von "sichtbar" kommt zuerst das Kamera-Frustum dran, bei Sichtbarkeit dann die Blocker, bis einer das Objekt auf "unsichtbar" schaltet, und alle Portale zwischendurch kann ich auslassen, weil die eh nur auf "sichtbar" schalten würden. Wenn ein Blocker zugeschlagen hat, mach ich einfach weiter in der Liste, kann aber jetzt die Blocker auslassen und nur die Portale prüfen, weil das Objekt ja eh unsichtbar ist. Wenn ich durch die Liste durchbin, habe ich definitiv raus, ob ein Objekt sichtbar oder unsichtbar ist.

Der Ansatz ist übrigens auch gut parallelisierbar.

[Jonathan]

Ok, das klingt doch schonmal ganz net. Irgendwelche Richtlinien, wonach man zuerst sortieren sollte? Rein intuitiv würde ich sagen, es ist teurer den Shader neu zu setzen, als eine Textur, oder kostet alles prinzipeill gleich viel, weil das eigentliche Warten durch Synchronisierungen auf der Grafikkarte entsteht?

Das mit der festen Liste: Jedesmal wenn sich die Szene ändert, würde man diese Liste neu aufbauen. Beim Cullen fügt man nicht Objekte in eine temporäre (später zu sortierende) Liste ein, sondern würde in der vorsortierten nur ein Flag setzen, ob sie dieses mal gerendert werden sollen, oder nicht?


Zu den Portalen: Was genau meinst du mit "einander ergänzen"? Und welche Objekte gehts du jeweils durch, alle, die momentan in der Spielwelt existieren?
Ich stelle mir das momentan so vor, dass man die Spielwelt in Räume aufgeteilt hat und man muss zunächst nur die Objekte betrachten, die im selben Raum, wie die Kamera sind. Diese können dann am Kamera Frustum gecullt werden, wodurch sich die Anzahl nochmal verringert. Sieht die Kamera jetzt ein Portal, wird dieser Raum dann auch gezeichnet, mit einem entsprechend kleineren Frustum, usw. Nur bei deinem Ansatz hört sich das irgendwie überhaupt nicht an, als hättest du Objekte irgendwelchen Räumen zugeordnet.
Also schön wäre ja, wenn ich nicht keine komplexe Raum-Verwaltungs-Logik bräuchte, sondern das irgendwie hübsch in meinen Scenetree integrieren könnte. Nur sehe ich da derzeit noch einige Probleme, es scheint zum Beispiel, als würde aus dem Baum einfach ein Graph, was ich mir nciht gut vorstelle.

Achja, wie werden Portale und Blocker verwaltet? Muss man die alle im Leveleditor erstellen, oder kann im Objektmodell ein Blocker bzw. Portal integriert werden? Oder werden die irgendwie geschickt automatisch generiert?

Achja, irgendwelche Artikelempfehlungen zu diesem Thema?

[glassbear]

Das mit der festen Liste: Jedesmal wenn sich die Szene ändert, würde man diese Liste neu aufbauen. Beim Cullen fügt man nicht Objekte in eine temporäre (später zu sortierende) Liste ein, sondern würde in der vorsortierten nur ein Flag setzen, ob sie dieses mal gerendert werden sollen, oder nicht?

In eine neue (andere) Liste statt des Flags. Die Liste mit den gesetzten Flags bringt dir nur den Cache durcheinander.

Achja, irgendwelche Artikelempfehlungen zu diesem Thema?

Real Time Rendering.

[Schrompf]

Ok, das klingt doch schonmal ganz net. Irgendwelche Richtlinien, wonach man zuerst sortieren sollte? Rein intuitiv würde ich sagen, es ist teurer den Shader neu zu setzen, als eine Textur, oder kostet alles prinzipeill gleich viel, weil das eigentliche Warten durch Synchronisierungen auf der Grafikkarte entsteht?

Die Richtlinien stehen schon in meiner ersten Antwort. Du kannst ganz an den Anfang der Sortierkriterien noch "Rendertarget" schreiben, dann ist sie meiner Meinung nach komplett.

Das mit der festen Liste: Jedesmal wenn sich die Szene ändert, würde man diese Liste neu aufbauen. Beim Cullen fügt man nicht Objekte in eine temporäre (später zu sortierende) Liste ein, sondern würde in der vorsortierten nur ein Flag setzen, ob sie dieses mal gerendert werden sollen, oder nicht?

Ja. Die Flags in den jeweiligen Listenobjekten vermasseln Dir zwar die Cache-Kohärenz ein wenig, aber nicht mehr, als die Liste komplett neu aufzubauen. Die Renderjobs werden im Speicher eine gewisse Größe haben, da passen definitiv nicht alle Jobs in den Cache, egal wie Du es drehst. Ausprobieren, würde ich sagen. Die Splitterwelten-Engine erstellt diese Liste ja wie gesagt in jedem Scene Pass live und sortiert sie auch live. Auch das geht. Das Sortieren kostet zwar Rechenzeit, aber dafür ist die Liste nur ein paar tausend Elemente lang.

Randbemerkung: "Liste" ist hier ein Wort für einen beliebigen Container - in der Realität ist eine Liste in praktisch allen Fällen eine schlechte Wahl. Ich nehme einen banalen std::vector<RenderJob> und einen std::vector<RenderJob*> zum Sortieren.

Zu den Portalen: Was genau meinst du mit "einander ergänzen"? Und welche Objekte gehts du jeweils durch, alle, die momentan in der Spielwelt existieren?
Ich stelle mir das momentan so vor, dass man die Spielwelt in Räume aufgeteilt hat und man muss zunächst nur die Objekte betrachten, die im selben Raum, wie die Kamera sind. Diese können dann am Kamera Frustum gecullt werden, wodurch sich die Anzahl nochmal verringert. Sieht die Kamera jetzt ein Portal, wird dieser Raum dann auch gezeichnet, mit einem entsprechend kleineren Frustum, usw. Nur bei deinem Ansatz hört sich das irgendwie überhaupt nicht an, als hättest du Objekte irgendwelchen Räumen zugeordnet.

Stimmt. Ich halte Vorsortierung und feste Zuordnungen für schlecht. Die Portale und Blocker bei mir sind auch nur Nodes im SceneGraph, die anhand der Kamera ihre eigene Sichtbarkeit bestimmen und im Fall der Sichtbarkeit ihr jeweiliges Ausschluss- oder Einschluss-Volumen zum Kamera-Frustum hinzufügen. Die sind dazu bei der Welt separat gemeldet, damit ich so schon vor dem Rendern in einer Liste habe, aber mehr auch nicht.

Achja, wie werden Portale und Blocker verwaltet? Muss man die alle im Leveleditor erstellen, oder kann im Objektmodell ein Blocker bzw. Portal integriert werden? Oder werden die irgendwie geschickt automatisch generiert?

Aktuell platziert man die im Leveleditor. Die sollten ja extrem schlicht sein, damit die daraus berechneten Silhouetten eine niedrige Anzahl Grenzebenen erzeugen. Ich habe aber mal mit dem Gedanken gespielt, unter größeren Bergen automatisch Blocker zu platzieren, bin nur bisher nicht dazu gekommen.