Kein Gras hinter dem Hügel rendern: geländebewusstes Occlusion Culling

Von Oleg Sidorkin, CTO und Mitgründer von Cinevva

Teil 28 stellte Spike 57 vor und benchmarkte seine vier Culling-Pfade in ein paar Absätzen. Hier kommt die ausführliche Version: warum gerade diese vier, welche anderen vier es gab und welche Überlegungen hinter dem Ansatz stehen, den wir ausliefern werden.

Zwischen der Kamera und einer Wiese liegt ein Hügel. Die Wiese muss nicht gerendert werden. Jede moderne AAA-Engine weiß das. Die meisten browserbasierten 3D-Engines wissen es nicht – unsere bis letzte Woche eingeschlossen.

Dieser Beitrag ist das Ergebnis gründlicher Recherche, ihrer Übertragung auf unsere tatsächliche Codebasis, der Entwicklung eines funktionierenden Spikes und der Bewertung der Techniken danach, wie sehr sie uns konkret helfen – angesichts dessen, dass wir heute für WebGL und morgen für WebGPU ausliefern.

Du kannst den Live-Spike unten ausprobieren, bevor du weiterliest. Mit T/Y/U/I wechselst du zwischen den Culling-Pfaden, mit C durchläufst du die Kameravoreinstellungen und mit B werden ausgeblendete Chunks als rotes Drahtgitter dargestellt, damit du sehen kannst, was der Test entfernt. Das HUD zeigt an, wie viele Instanzen jede Stufe verwirft.

Spike 57 in einem neuen Tab öffnen ↗ · Quellcode ansehen

Was unsere Engine heute tut (und was nicht)

Unser Streaming-Chunk-Manager lädt rund um den Spieler einen Ring aus 64-m-Chunks in drei LOD-Stufen. Jeder Chunk enthält instanzierte Bäume, die über die Heightmap verteilt sind. Die Culling-Logik in Chunk.updateObjectVisibility ist eine einfache Distanzprüfung: Bäume innerhalb von 60 m werden als vollständiges Mesh gerendert, zwischen 60 m und 140 m als Billboards und jenseits davon gar nicht.

Dieses Culling übersieht zwei riesige Kategorien verschwendeter Arbeit:

1. Alles, was sich innerhalb des 60-m-Radius, aber hinter der Kamera befindet. Wir sortieren den Instanzpuffer jedes Mal neu, wenn sich der Spieler mehr als 4 m bewegt. Den Sichtfrustum prüfen wir jedoch nicht. Dadurch wird durchschnittlich die Hälfte des Kreises an die GPU übergeben, nur um nach der Vertex-Transformation abgeschnitten zu werden.
2. Alles, was sich innerhalb des 60-m-Radius, aber hinter einem Hügel befindet. Unser Gelände hat einen vertikalen Umfang von 80 m und viele Täler. Wenn sich die Kamera in einem Tal befindet, wird der Großteil der Vegetation innerhalb des Culling-Radius geometrisch vom nächstgelegenen Kamm verdeckt. Wir zeichnen sie trotzdem.

Auf die zweite Kategorie konzentriert sich dieser Beitrag. Sie ist zugleich diejenige, die AAA-Engines mit einem ganzen Stapel cleverer Techniken lösen, die sich auf den ersten Blick nicht ohne Weiteres auf den Browser übertragen lassen.

Gilbert Sanders von Guerrilla erklärt, wie Horizon Zero Dawn Vegetation in seiner offenen Welt rendert. Der Culling-Stack nimmt die letzten 20 Minuten ein und ist eine Meisterklasse darin, warum „weniger zeichnen“ besser ist als „schneller zeichnen“.

Acht Techniken, bewertet für unseren Anwendungsfall

Ich habe den modernen Occlusion-Culling-Stack untersucht und jeden Baustein danach bewertet, wie sehr er einer prozeduralen, Heightmap-basierten offenen Browserwelt hilft. Dabei gibt es zwei Achsen: Nutzen (wie viel unnötige Arbeit er in unserer Szene vermeidet) und Kosten (Entwicklungsaufwand sowie der Umfang der nötigen Änderungen an unserem Stack). Die vollständige Begründung steht in der Recherchedatei zu diesem Beitrag; hier ist die Kurzfassung.

1. Frustum Culling pro Instanz. Hoher Nutzen, geringe Kosten. Aktuell prüfen wir den Frustum für unsere instanzierte Vegetation überhaupt nicht. Das Hinzufügen dieser Prüfung halbiert die Arbeit bei praktisch jeder Ansicht, benötigt etwa dreißig Codezeilen und kann schon heute mit WebGL ausgeliefert werden. Dies ist mit Abstand der größte leicht erzielbare Gewinn, und wir hätten ihn schon vor Monaten umsetzen sollen.

2. Horizont-Raycast auf der Heightmap. Hoher Nutzen, geringe bis mittlere Kosten. Wir führen einen Strahl von der Kamera durch jede infrage kommende Instanz und tasten dabei entlang des Weges die Geländehöhe ab. Steigt das Gelände irgendwo über den Strahl, ist die Instanz verdeckt. Das funktioniert gerade deshalb so gut, weil unsere Welt eine Heightmap ist und sich die Sichtbarkeitsprüfung dadurch auf ein eindimensionales Problem entlang der horizontalen Richtung reduziert. Die dichte Variante benötigt O(Schritte) pro Instanz und Frame. Die beschleunigte Variante (der nächste Punkt) reduziert dies auf O(log Schritte).

3. Beschleunigung durch eine Maximalhöhenpyramide. Hoher Nutzen, mittlere Kosten. Eine 2D-Mipmap der Heightmap, in der jedes Texel die maximale Geländehöhe innerhalb seines Bereichs speichert. Dadurch kann der Horizont-Raycast in großen Schritten voranschreiten, wenn die Umgebung flach ist, und nur über Hügeln verfeinern. Diese Datenstruktur macht Punkt 2 günstig genug für den Produktiveinsatz.

4. Hierarchische Z-Verdeckung (Hi-Z/HZB). Hoher Nutzen, hohe Kosten. Eine Mipmap des Tiefenpuffers erstellen, die Begrenzungsvolumen jeder Instanz in den Screen Space projizieren und sie gegen die passende Mipmap-Stufe prüfen. Dies ist der moderne GPU-seitige Standard, den Unreals Nanite, Beavys virtuelle Geometrie und der WebGPU-Port von VTK verwenden. Er funktioniert für alles, nicht nur für Gelände, benötigt aber WebGPU, indirekte Draw Calls und einen Compute-Pass. Er lohnt sich, wenn wir Millionen von Grashalmen statt Tausender Bäume rendern.

5. Zweistufiges Hi-Z (im Nanite-Stil). Geringer Zusatznutzen gegenüber Punkt 4, hohe Kosten. Die Tiefe des aktuellen Frames nach Pass 1 erneut rendern, um das ein Frame lange Disocclusion-Artefakt zu vermeiden. Lohnt sich erst, wenn wir auf dem GPU-gesteuerten Pfad weit genug fortgeschritten sind, dass die zusätzlichen Kosten gering ausfallen.

6. Software-Occlusion-Rasterizer (Frostbite/Intel MOC). Mittlerer Nutzen, hohe Kosten. Einen niedrig aufgelösten Tiefenpuffer großer Occluder auf der CPU rasterisieren. Keine Readback-Latenz. Die Referenzimplementierungen sind AVX/SSE-C++; ihre Portierung auf WASM ist ein eigenes Projekt, während unser Heightmap-Raycast den Großteil derselben Vorteile mit einem Bruchteil des Aufwands erzielt.

7. Vorberechnetes PVS. Geringer Nutzen, hohe Kosten. Hervorragend für statische Maps aus der Quake-Ära. Unser Gelände ist prozedural und unendlich, daher müsste jede Vorverarbeitung beim Chunk-Streaming stattfinden – was ungefähr so viel kostet wie eine Sichtbarkeitsprüfung zur Laufzeit. Überspringen.

8. Horizont-Culling im Cesium-Stil. Kein Nutzen für uns, mittlere Kosten. Für planetare Ellipsoide entwickelt. Unsere Welt ist annähernd flach und begrenzt; die Mathematik ist nicht anwendbar und würde entweder nichts bewirken oder fälschlicherweise Objekte ausblenden. Überspringen.

Also: Punkt 1 sowie Punkt 2+3 jetzt auf der CPU in WebGL umsetzen. Punkt 4 für die WebGPU-Migration einplanen. Den Rest überspringen.

Warum der Heightmap-Raycast für Browsergelände gewinnt

Der übliche Rat in jedem modernen Rendering-Vortrag lautet: „Erstellt einen Hi-Z-Puffer.“ Brian Karis’ ausführlicher Nanite-Vortrag auf der SIGGRAPH 2021 ist die maßgebliche Referenz, und du solltest ihn dir einmal ansehen.

Für eine Engine, die bereits alles über GPU-gesteuerte indirekte Draw Calls ausführt, ist das die richtige Antwort. Die meisten Browser-Engines – unsere eingeschlossen – sind nicht so aufgebaut. Wir haben CPU-seitige Instanzpuffer, WebGL-Draw-Calls und keine Compute-Stufe. Hi-Z an diesen Stack anzubauen hieße, gleichzeitig auf WebGPU zu portieren, die Vegetationspipeline auf indirekte Draw Calls umzustellen und einen Pass zum Aufbau der Tiefenpyramide hinzuzufügen. Das ist ein Vierteljahr Arbeit bis zum ersten Frame, der die Idee bestätigt.

Der Heightmap-Raycast funktioniert auf der CPU, in WebGL und mit den Daten, die wir bereits haben. Er nutzt die eine Eigenschaft unserer Welt, die AAA-Engines nicht voraussetzen können: Unsere Occluder werden durch eine eindimensionale Höhenfunktion beschrieben. Das Abtasten dieser Funktion entlang eines Strahls erfordert zwei Array-Zugriffe und eine Multiplikation. Ein Hi-Z-Puffer müsste dieselbe Tatsache Pixel für Pixel ermitteln.

Die Technik wurde erstmals 2002 auf der IEEE Visualization unter dem Titel „Horizon Occlusion Culling for Hierarchical Terrains“ veröffentlicht (PDF). Sie gehört seit zwei Jahrzehnten zum Werkzeugkasten, weil sie genau die richtigen Eigenschaften besitzt: günstig bei flachem Gelände, teuer nur dort, wo tatsächlich Hügel vorhanden sind, und trivial parallelisierbar.

Die Maximalhöhenpyramide als Darstellung

Der naive Raycast tastet terrainHeight an etwa 24 Punkten entlang jedes Strahls ab und bricht vorzeitig ab, wenn das Gelände ihn kreuzt. Für Tausende Bäume ist das in Ordnung. Bei Hunderttausenden Grashalmen bricht die Performance ein.

Die Lösung ist eine Mipmap der Heightmap, in der jedes Texel die maximale Höhe innerhalb seines Bereichs speichert:

Stufe 0 (256×256, 2,25 m pro Texel): Maximalhöhe von 4×4 versetzten Samples
Stufe 1 (128×128, 4,5 m  pro Texel): max(0,0), max(1,0), max(0,1), max(1,1)
Stufe 2 ( 64×64,  9,0 m pro Texel): dieselbe Reduktion eine Stufe höher
...
Stufe 8 (   1×1,  576 m pro Texel): globales Maximum

Wenn das Strahlsegment lang ist und über flaches Gelände verläuft, wird eine grobe Stufe abgetastet. Ein einziger Zugriff sagt uns: „Kein Geländepunkt in diesem 9-m-Quadrat liegt höher als 12 m, während sich der Strahl dort auf 30 m befindet – also weiter.“ Nur wenn ein grobes Texel signalisiert, dass das Gelände möglicherweise über dem Strahl liegt, steigen wir eine Stufe hinab und verfeinern die Prüfung. Die gesamte Struktur benötigt nur einige Hundert KB und wird in wenigen Dutzend Millisekunden aufgebaut.

Als Diagramm:

                                      Strahl vom Auge
       Auge 1,7 m                   o─────────────────────►
              o───────────────────·─·─·─·─·─·──────────────
              │                    \                       │
              │  Stufe 3             \  Stufe 0            │
              │  (riesiger Schritt)   \  (verfeinern)      │
              │  „kein Gelände über    \ „hier ist ein     │
              │   8 m“                    9-m-Hügel!“       │
        ──────┴────────────/▔▔▔\─────────────/▔▔▔▔▔\─────────────
                               Hügel A (8 m)   Hügel B (12 m)
                                                  ↑
                                           blockiert hier

Für das Strahlsegment, das über die Umgebung von Hügel A verläuft, zeigt uns bereits der Zugriff auf Stufe 3 („Die maximale Höhe in diesem 18 m breiten Bereich beträgt 8 m“), dass der Strahl bei einer Höhe von 1,7 m plus einigen Metern Steigung frei ist. Wir überspringen mit einer einzigen Abfrage 36 m des Ray Marchings. Über Hügel B sagt Stufe 3: „Das Maximum beträgt hier 12 m.“ Wir steigen hinab, und Stufe 0 sagt: „Ja, an genau diesem Texel sind es 12 m.“ Daraufhin verwerfen wir die Instanz.

Der Aufbau der Pyramide befindet sich in height-pyramid.mjs, die Culling-Pfade, die sie verwenden, in cull.mjs. Beide lassen sich im Quellcode-Browser des Spikes gut nachvollziehen.

Was der Spike tatsächlich zeigt

Öffne oben Spike 57 und probiere die vier Pfade aus:

• T0 entspricht dem heutigen Produktionsstand. Nur Distanzprüfung. Bei C1 (Talboden) meldet das HUD etwa 12.000 sichtbare Grashalme.
• T1 ergänzt Frustum Culling pro Instanz. Die sichtbare Anzahl sinkt ungefähr um die Hälfte, weil alles hinter der Kamera oder seitlich außerhalb des Sichtbereichs verworfen wird, bevor es die GPU erreicht.
• T2 ergänzt den Brute-Force-Raycast auf der Heightmap. Bei C1 sinkt die Anzahl um weitere 60–80 %, weil der Großteil des Feldes auf der anderen Seite des nächstgelegenen Kamms liegt. Die Spalte „Cull-ms“ steigt, weil wir terrainHeight etwa 24-mal pro Instanz abtasten.
• T3 ersetzt die Brute-Force-Methode durch die Maximalhöhenpyramide. „Cull-ms“ fällt wieder annähernd auf das Niveau von T1, während der Sichtbarkeitsgewinn erhalten bleibt. Dies ist der Pfad, den man tatsächlich ausliefert.

Das Muster entspricht den Erfahrungen von Produktions-Engines. Acerolas zweiteilige Serie über das Rendern von Gras (Wie rendern Spiele so viel Gras?, Wie ich das Gras meines Spiels optimiert habe) ist die verständlichste Einführung auf YouTube dazu, warum man den Entwicklungsaufwand in die Culling- und nicht in die Shading-Stufe investiert.

Kamera C3 und der Fehlerfall „Hügelkuppe“

Die dritte Kameravoreinstellung des Spikes platziert die Kamera auf einem Hügel mit Blick über das Spielfeld. In diesem Fall bewirkt das Horizont-Culling fast nichts, weil sich zwischen der Kamera und dem Großteil der Welt kein Gelände befindet. Das HUD zeigt, dass T2/T3 die sichtbare Anzahl gegenüber T1 nur um vielleicht 5–10 % reduzieren.

Das ist kein Fehler, sondern eine erwünschte Eigenschaft. Die Technik hört genau dort auf zu wirken, wo sie es sollte: wenn nichts vorhanden ist, das Objekte verdecken könnte. Das Frustum Culling leistet weiterhin echte Arbeit, das Distanz-Culling begrenzt weiterhin das Budget und der Horizonttest wird problemlos zu einer wirkungslosen Prüfung. Bei der Implementierung muss sichergestellt werden, dass auch dieser Fall günstig ist. Deshalb ist die Maximalhöhenpyramide selbst dann wichtig, wenn kein Strahl zu einer Verwerfung führen würde: Oft reicht bereits die gröbste Stufe, um zu bestätigen, dass „nichts verdeckt ist“.

Was wir als Nächstes ausliefern

Es sind drei Dinge in dieser Reihenfolge zu erledigen.

Zuerst portieren wir T1 und T3 in die produktive Methode Chunk.updateObjectVisibility. Die Pyramide sollte eine Ebene höher im Chunk-Manager liegen, weil sie sich über mehr als einen Chunk erstreckt. Das Culling bleibt in Chunk, damit das bestehende Batching pro Chunk weiterhin funktioniert. Geschätzter Aufwand: ein Tag einschließlich Tests. Zweitens machen wir dasselbe für Gras, sobald wir welches haben. Der aktuelle Prototyp verteilt 12.000 Grashalme über ein 576 m großes Spielfeld; die Produktionsdichte sollte ungefähr eine Größenordnung höher liegen. Die CPU-Culling-Pfade verarbeiten 12.000 in weniger als einer Millisekunde, und die Pyramidenbeschleunigung sorgt dafür, dass das auch bei 120.000 so bleibt.

Drittens portieren wir beim Umstieg auf THREE.WebGPURenderer dieselbe Schleife in einen Compute-Shader. Die Metadaten werden zu einem Storage Buffer. Das Culling schreibt die drawIndirect-Argumente. Die Pyramide wird als 2D-Textur hochgeladen, in die die Maximum-Reduktion bereits eingebacken ist. Die Struktur des Codes bleibt nahezu identisch – und genau darum geht es: Wir setzen bei der Migration nicht auf einen neuen Algorithmus, sondern verlagern einen bereits vorhandenen Algorithmus auf eine schnellere Plattform.

Guerrilla hat die GPU-seitige Variante davon für das prozedurale Platzierungssystem von Horizon Zero Dawn vorgestellt. Die Rendering-Pipeline ist weniger entscheidend als die Datenstrukturen, und diese haben dort dieselbe Form:

Hi-Z wird seinen Platz weiterhin verdienen, sobald wir Gebäude und dichte Requisiten veröffentlichen, die in Richtungen verdecken, welche die Heightmap nicht beschreiben kann. Die Heightmap-Pyramide bleibt jedoch in der Pipeline, weil sie für bodennahe Instanzen eindeutig günstiger als Hi-Z ist. Gras, das die Silhouette eines Bergrückens überragt, ist außerdem genau der Fall, den Hi-Z am schlechtesten verarbeitet.

Quellen

Die vollständige, nach Priorität geordnete Begründung und die Architekturentscheidungen stehen oben. Hier folgen die maßgeblichen Quellen für die einzelnen Techniken, ungefähr in der Reihenfolge, in der sie im Stack vorkommen.

• Yalim & Akman, Horizont-Verdeckungsculling für hierarchische Terrains (IEEE Visualization 2002, die ursprüngliche Publikation zum Horizont-Culling von Terrains).
• Turitzin, Hierarchische Tiefenpuffer (die verständlichste Erklärung dazu, wie Hi-Z-Mip-Ketten aufgebaut und abgefragt werden).
• VKGuide, Compute-basiertes Culling (Referenz für eine GPU-gesteuerte Culling-Pipeline; die Portierung auf WebGPU ist reine Fleißarbeit).
• Kruskonja, Zwei-Pass-Verdeckungsculling (die Nanite-ähnliche Architektur außerhalb von Epics Präsentationsfolien erklärt).
• Karis et al., Nanite – ein tiefer Einblick (SIGGRAPH 2021) (die moderne Referenz dafür, wie GPU-gesteuertes Culling im AAA-Maßstab aussieht).
• Karis, HPG-2022-Keynote: Der Weg zu Nanite (umfassenderer Kontext dazu, warum die Culling-Phase wichtig ist).
• Sanders, Zwischen Technik und Kunst: Die Vegetation von Horizon Zero Dawn (der komplette AAA-Culling-Stack für Vegetation).
• Guerrilla, GPU-basierte prozedurale Laufzeitplatzierung in Horizon Zero Dawn (instanziierte Platzierung und Sichtbarkeit pro Instanz).
• Scthe, Nanite WebGPU (eine WebGPU-Referenzimplementierung einschließlich HZB).
• Kitware, WebGPU-Verdeckungsculling in VTK (die erste produktiv eingesetzte HZB-Implementierung im Browser, die mir bekannt ist).
• Acerola, Wie rendern Spiele so viel Gras? und Wie ich das Gras meines Spiels optimiert habe (die zugängliche YouTube-Einführung).
• RasterGrid, Hi-Z-Map-basiertes Verdeckungsculling (die nach wie vor maßgebliche Hi-Z-Einführung).
• Intel, Maskiertes Software-Verdeckungsculling (die Familie der CPU-Rasterizer, falls wir irgendwann entscheiden, dass sich Option Nr. 6 lohnt).