[Große Aussenwelt] Algorithmen u. Datenstrukturen

[mnemonix]

Hallo,

immer mehr Spiele nutzen große Aussenwelten um dem Spieler eine gewisse Freiheit (Openworlds) innerhalb des Spiels vorzutäuschen. Man kennt das z.B. von Spielen wie Fallout 3, Crytek-Spielen, World of Warcraft und anderen MMOGs, Gothic, Risen und viele mehr. Deshalb frage ich mich oft, welche Algorithmen u. Datenstrukturen hier oft Anwendung finden und dahinterstecken. Ich habe auch schon hier und da gegooglet und auch ein paar Infos darüber einfangen können. Zum Beispiel LoD Algorithmen (ROAM, Geomipmapping, Geoclipmaps, ...), Paging/Streaming, Visibility mit Quadtrees oder Octrees, etc. (http://vterrain.org/ ist z.B. eine schöne Webseite darüber). Das ist ja schön und gut, das betrifft aber alles nur im engeren Sinne Terrains. Was ich mich jedoch anderweitig Frage ist, wie die Spieleentwickler es handhaben, wenn der Spieler Höhlen (die z.B. tief unter dem Terrain verlaufen) oder Gebäude _seamless_ betritt. Welche Datenstrukturen/Algorithmen werden hier verwendet (in Bezug auf Visibility hauptsächlich)? Geht man hier z.B. bei Gebäuden über auf BSP/Portal-based Algorithmen wie man sie von Indoor-Spielen wie Half-Life 1, Doom, Quake, etc. kennt? Und was würde man bei Höhlen in Betracht ziehen? Octrees? Auch würde es mich interessieren, wie man Überhänge in Terrains darstellen könnte? Mit Heightmaps ja theoretisch unmöglich. Geht man da den Weg über indirektes Voxel-based Terrain?

So die paar Fragen reichen erstmal. Ich finde es halt sehr spannend, was es momentan alles so gibt und was derzeit State-of-the-Art ist. Ich bin gespannt auf eure Antworten. Ich weiss ja, dass sich hier sehr viele kluge Köpfe aufhalten nach langem Verfolgen eurer spannenden Posts über C++, Rendering und dergleichen (manche Dinge sind mir sogar fast zu hoch). Haut rein. ;)

EDIT: Links zu Blogs/Artikeln/Papers zum Nachlesen speziell zu diesen Themen sind auch sehr willkommen.

[Krishty]

Creating Vast Game Worlds geht auf Probleme und Lösungen der Entwicklung von Just Cause 2 ein; etwa, wie man eine so große Welt trotz Gleitkomma-Unzulänglichkeiten durch Direct3D geschoben kriegt.

[mnemonix]

Vielen Dank für den Link, Krishty. Das sind doch schonmal nützliche Informationen. Aber mein Hauptpunkt sind mehr die Visibility Datenstukturen/Algorithmen. Ich habe jetzt z.B. herausgefunden, dass WoW scheinbar ein BSP-System nutzt, denn innerhalb der Ingame-Konsole gibt es eine Einstellung, die die Größe eines BSP-Caches bestimmt. Ich vermute mal, dass dieser sich auf große Gebäude und Höhlensysteme bezieht. Wie sieht es mit anderen Spielen aus? Was ist hier State-of-the-Art?

@Schrompf: Welche Techniken benutzt du bei Splitterwelten in Bezug auf Visibility (Indoor/Outdoor)? Und wie realisierst du Überhänge (z.B. indirektes Voxel-basiertes Terrain)? Entwickelst du eigentlich noch an Splitterwelten weiter?

Btw gibt es eine Option oder ein Tool in WoW, wie ich mir das Wireframe anzeigen kann? Habe mir spaßeshalber mal die Starter-Edition gezogen, um das mal in Augenschein zu nehmen.

[waigie]

Als Datenstruktur zur Überprüfung der Sichtbarkeit eignet sich rein theoretisch jede beliebige Baumstruktur. BSP-Bäume werden mittlerweile jedoch seltener eingesetzt. Alternativen sind KD-Trees, Quadtrees oder Octtrees. Was du da nutzt hängt auch stark von der Anwendung ab. KD-Trees eignen sich nach meiner Erfahrung besser wenn du hauptsächlich statische Geometrie hast, da sie sich etwas schwerer Updaten lassen als Quad- und Octtrees.
Occlusion Culling Techniken gibt es einige. Einer der modernsten Ansätze ist in Next Generation Occlusion Culling beschrieben. Die Technik verwendet unter anderem auch in Unity3D. Ich hab den Artikel nur überflogen, aber es sieht nach einer Mischung aus Room/Portal und DepthBuffer Tests aus. Es sieht aber danach aus, das große Datenmengen vorberechnet werden müssen, was bei manchen Anwendungen nicht möglich ist.
Eine weitere recht moderne Arbeit ist Rendering with Conviction. Diese Lösung kommt ohne große Vorberechnungen aus.
Und nochmal 2 Jahre älter CHC++. Das von den dreien wohl einfachste Verfahren. Jedoch mit dem Nachteil, das es nötig ist Rendering und Occlusion Culling abwechselnd ausgeführt werden müssen um die Latenz der Occlusion Queries zu reduzieren.

[Schrompf]

So, da mein Rechner endlich wieder sicher funktioniert, hier noch mein Senf zum Thema:

Die Splitterwelten benutzen im Kern einen banalen locker strukturierten Tree aus Axis Aligned Bounding Boxes. Das reicht natürlich nicht für die Objektmassen, die auf einem Splitter herumstehen, daher gibt es unter anderem folgende weitere Basteleien.

- Frühzeitiges Abschalten von Objekten. Die einfachste Methode, aber auch die wichtigste. Niemand will zwanzig Paar Besteck rendern, wenn die Hütte drumrum >50m entfernt ist.
- Hierarchisches Zusammenfassen. Es gibt für verschiedene Gruppen von Objekten Sammelobjekte, die ab einer bestimmten Entfernung tätig werden und alle Unterobjekte in einem Mesh gemeinsam rendern. Gilt für Terrain-Segmente genauso wie für Wald-Segmente.
- Alles, was nicht interaktiv ist und auch nicht kollidiert, wird per Instancing in großen Gruppen gerendert. Z.B. Gras, Farne, Bachsteine.
- Blocker - konvexe Volumen, deren Silhouetten-Kanten von der Kameraposition aus extrudiert werden. Das sich zusammen mit den Vorderseiten des Blockers ergebende konvexe Volumen wird genutzt, um Objekte als unsichtbar zu markieren.
- Die Blocker werden benutzt, um das Innere eines Hauses vom Äußeren zu trennen.
- Die Blocker als große Flächen in die Berge gesetzt, um grob alles hinter dem Berg unsichtbar zu machen.
- Randnotiz: Irgendwann stell ich mal auf Bounding Spheres um, das würde einiges an Culling-Rechenzeit sparen.
- Randnotiz II: siehe CodingCats Notizen zur Datenorientierung. Es könnte sich lohnen, den ganzen hierarchischen Scheiß zu knicken und linear durch eine Liste von Bounding Volumes zu testen. Hab ich aber noch nicht ausprobiert.
- Weiter im Text: Portale. Ebenso konvexe Volumen oder planare Polygone, deren Silhouettenkanten ein wiederum konvexes Sichtvolumen ergeben, das Objekte nach Blockern wieder sichtbar macht.
- Die Portale werden an Türen und Fenstern eingesetzt, um selektiv Objekte wieder sichtbar zu machen, die durch diese Tür oder Fenster sichtbar wären.
- Portale werden mit begrenzter Reichweite auch an den Grenzflächen zwischen zwei Blockern eingesetzt.
- Mein Leveldesigner beackert mich seit Ewigkeiten, den Dungeon doch einfach als separate Spielwelt mit Ladebildschirm zu gestalten. Bisher habe ich mich dem verweigert.

Schlussendlich: das nützt alles nix, wir haben immernoch bis zu 7000 DrawCalls pro Frame. Dem will ich wie folgt abhelfen, sobald ich mal ordentlich Zeit am Stück habe:

a) Umbau auf einen Deferred Renderer, um die Anzahl Shaderwechsel gesenkt zu bekommen
b) Dadurch wird dann auch das automatische Instancing effektiver, dass aktuell deaktiviert ist, weil das Umschalten der Vertex Deklaration mehr kostet als ein Dutzend gleichartiger DrawCalls durchzujagen.
c) Multicore-Renderer: Culling und Sammeln der Zeichenaktionen parallel in mehreren Threads, Ausführung leider immernoch sequentiell im Hauptthread.
d) Umbau auf DX10 oder besser - damit werden DrawCalls angeblich deutlich billiger.
e) Lichtquellen dynamisch pro Frame sammeln, anstatt wie jetzt pro Objekt Listen wirksamer Lichtquellen zu verwalten und bei jeder Bewegung aktuell zu halten. Hat mit Render-Performance jetzt nicht so viel zu tun, ist aber lästig und verhindert effektiv den Einsatz kleiner Lichtquellen an Gegenständen und sowas.
f) Parallele Haltung der Szene als Sparse Voxel Tree - für Global Illumination, aber auch für grobe Schatten für kleine Lichtquellen. Von den oben genannten 7000 DrawCalls finden etwa 5000 nur in Schatten-Passes statt - die könnte man alle knicken, wenn man Cone Tracing durch einen SVT macht, und bekäme trotzdem grobe weiche Schatten.

Mir fällt mir dazu erstmal nicht ein.

[Jonathan]

Wo wir gerade bei Portalen und Sichtblockern sind: Ich habe mir mal darüber Gedanken gemacht und bin mir gar nicht so sicher, wie viel die wirklich bringen.
Ich meine, verwinkelte Indoor-Levels kann man mit Portalen echt super gut rendern. Aber heutzutage will man doch eher offene Spielwelten haben. Nehmen wir jetzt mal an, ein großer Stein dient als Sichtblocker, alles was dahinter ist, wird dann nicht mehr gerendert. Nun, man könnte genausogut neben dem Stein stehen, dann müsste auch alles gerendert werden, und der Stein im Vordergrund ist irgendwie auch schnell gerendert, man sollte also in der Regel kaum merken, ob man vor dem Stein steht, oder daneben, wenn man eh immer alles rendert.
Wozu dann also noch die Mühe und ihn als Sichtblocker deklarieren? Wird dadurch das rendern nicht nur komplizierter und damit generell langsamer, nur damit man in seltenen Situationen unnütz hohe Frameraten hat, im Allgemeinen aber wenig gewinnt?

Wenn ich mich irgendwann nochmal daran setze, bei mir alles zu optimieren, würde ich glaube ich so vorgehen: Über das Level wird ein grobes Gitter gelegt. Da wo die Kamera ist und vielleicht noch in den anliegenden Zellen, mach ich einfach schön bruteforce einen BoundingSphere-Test für jedes Objekt (wenn die Daten schön nebeneinander liegen, sollte das alleine aus Cache-Gründen locker mit einem Octree mithalten können). Zellen die weiter weg liegen werden mit reduzierten Details gerendert, d.h. evtl. andere Modelle und kleine Objekte gar nicht mehr. Für jede LOD-Stufe gibt es eine separate Modell-List, die wieder brute-force gecullt wird.
Evtl. Sammel ich auch alle Render-Jobs und sortiere die noch nach Material. Da die Liste evtl. schon grob vorsortiert ist und auch das sortieren irgendwie parallelisierbar sein müsste, sollte das sehr schnell gehen.

Was ich mir davon Verspreche, ist, dass es leicht und übersichtlich zu implementieren ist und es nicht irgendwelche Spezialfälle optimiert, die vielleicht viel zu selten auftreten. Stattdessen kann man damit jede Art von Szene ungefähr gleich gut rendern, was genügen sollte.

[Schrompf]

So sah meine Engine am Anfang auch aus. Besonders die Material-Sortierung bzw. Sortierung nach Vertex-Deklaration, Shader und TexturSet hat einiges gebracht. LOD genauso - ein Standardmanöver, in wenigen Minuten eingebaut. Die Blocker und Portale aber sind kein so einfaches Pflaster. Wir reden hier ja nicht von einem Findling - da lohnt sich das Blocken nicht, da hast Du Recht. Ich setze es zum Trennen von Innen- und Außenräumen ein. "Außen" ist der Standardfall, "Drinnen" ist der Spezielfall. Und bei einem dreistöckigen Haus gibt es eine Menge "drin". Charaktere, Möbel, Einrichtung, Deko-Kleinkram - selbst die Frustums von ShadowMap Passes werden zuerst gegen Blocker gecullt. Da kann es vorkommen, dass Du bei der Lampe an der Haus-Rückseite 4 von 6 Shadow-CubeMap-Seiten gar nicht aktualisieren musst, weil Du weißt, dass sie komplett vom Haus verdeckt werden. Portale in Fenstern und Türen kannst Du erst ab 20m aktivieren, vorher pinselst Du das Portal mit einem schwarzen Material nach und ersparst Dir das Hausinnere vollständig. Es braucht Augenmaß, klar, aber meiner Meinung nach ist es das wert.

Prominentestes Beispiel bei uns: der Dungeon. 200m lang und besteht aus anderthalb tausend Einzelobjekten. Wenn Du drin bist, ist alles außerhalb unsichtbar, von außen ist alles darin unsichtbar. Und da ich bei mir alle Objekte immer als Unterobjekte des Blockers anlege und der Blocker, solange er inaktiv ist, alle Unterobjekte versteckt, kostet der Dungeon zur Laufzeit genau null Rechenzeit.