Eine offene Welt im Browser erschaffen, Teil 7: Marching Cubes und die ersten echten Höhlen

Von Oleg Sidorkin, CTO und Mitgründer von Cinevva

Neu hier? Nutze den Serienleitfaden. Dort wird erklärt, was ein Spike ist, und alle Teile sind verlinkt.

Heightmaps sind großartig – bis man Überhänge braucht.

Sobald man ausgehöhlte Tunnel, vorspringende Felsformationen oder Höhlendecken umsetzen möchte, wird eine reine Heightfield-Pipeline zum Hindernis. Eine Heightmap speichert für jede XZ-Koordinate genau einen Y-Wert. Sie ist physikalisch nicht in der Lage, Oberflächen darzustellen, die sich über sich selbst zurückfalten. Wir brauchten eine volumetrische Repräsentation.

Spike 12 implementierte Marching Cubes auf der GPU mithilfe von WebGPU-Compute-Shadern. Der Algorithmus wertet ein Signed Distance Field (SDF) auf einem 3D-Raster aus und extrahiert an der Nulldurchgangsfläche ein Dreiecksnetz. Jede Zelle besitzt 8 Ecken, die sich jeweils entweder innerhalb oder außerhalb der Oberfläche befinden. Daraus ergeben sich $2^8=256$ mögliche Vorzeichenmuster. Eine Lookup-Tabelle ordnet jedem Muster eine Reihe von Dreiecken zu. Die Vertices liegen an den Zellkanten genau dort, wo das Feld den Nullwert durchquert. Für eine Kante zwischen den Ecken $a$ und $b$ mit den Feldwerten $f_a$ und $f_b$ wird der Vertex durch lineare Interpolation an folgender Position platziert:

$$\mathbf{v}={\mathbf{p}}_a+t({\mathbf{p}}_b-{\mathbf{p}}_a),t=\frac{-f_a}{f_b-f_a}$$

Das ist der Anteil entlang der Kante, an dem das Feld den Nullwert erreicht. Da $f_a$ und $f_b$ an einer durchquerten Kante unterschiedliche Vorzeichen haben, liegt $t$ immer in $[0,1]$. Wir führten dies gleichzeitig auf vier aktiven Chunks mit jeweils ${64}^3$ Zellen aus und testeten animierte SDF-Bearbeitungen mit einer erneuten Mesh-Generierung in jedem Frame.

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

Der erste Erfolg war das Vertrauen in die Compute-Pipeline selbst. Ein einziger Dispatch konnte das SDF auswerten, Zellen klassifizieren und Vertices in einen GPU-Puffer schreiben – ganz ohne Rückübertragung zur CPU. Der zweite Erfolg war die Erkenntnis, wie schnell aus „Es funktioniert“ die Jagd nach Artefakten wird. Fehlende Dreiecke waren nur selten ein theoretisches Problem von Marching Cubes. Meist waren die Ursachen nicht übereinstimmende Tabellenindizes, fehlerhafte Zeichenbereiche, die über die Anzahl aktiver Vertices hinauslasen, oder Sonderfälle an Chunk-Grenzen, an denen benachbarte SDF-Samples nicht verfügbar waren.

Dieser Spike zwang uns dazu, in Zonen zu denken. In der Nähe der Kamera braucht man volumetrische Freiheit, damit Spieler Terrain formen und graben sowie Höhlen sehen können. Weit entfernt von der Kamera braucht man die Effizienz von Clipmaps, wo eine flache Heightmap günstiger und vollkommen ausreichend ist. Diese Dualität wurde zum Rückgrat der Architektur, die wir ab Spike 13 kontinuierlich weiterentwickelten.

Einer meiner liebsten Debugging-Momente war das Umschalten auf die Drahtgitteransicht, während die Bearbeitungen liefen. In Echtzeit zu beobachten, wie sich die Topologie bildete und wieder auflöste, machte Kompromisse bei der Qualität sofort sichtbar. Man konnte erkennen, wo die Vertex-Dichte hoch genug war, wo sie zu grob wurde und an welchen Stellen die LOD-Übergänge später Transvoxel-Unterstützung benötigen würden, um Risse zu vermeiden.

In Teil 8 behandeln wir die Herausforderung der Integration. Rohe, Compute-gesteuerte Meshes und die Szenengraph-Logik von Three.js in einer stabilen Rendering-Pipeline zu vereinen, war schwieriger, als die isolierte Demo vermuten ließ.

In diesem Kapitel erwähnte Technologien

Marching Cubes. Ein Algorithmus zum Extrahieren eines Dreiecksnetzes aus einem dreidimensionalen Skalarfeld (Lorensen und Cline, 1987). Jede Zelle eines regelmäßigen 3D-Rasters wird klassifiziert, indem das Feld an ihren 8 Ecken abgetastet wird. Das Vorzeichenmuster ergibt einen Fallindex (0–255), und eine Lookup-Tabelle ordnet jedem Fall eine Reihe von Dreiecken zu. Vertices werden durch Interpolation zwischen den beiden Ecken auf den Rasterkanten platziert. Der Algorithmus lässt sich hervorragend parallelisieren, da jede Zelle unabhängig verarbeitet wird, und eignet sich deshalb ideal für GPU-Compute. Siehe unseren Terrain-Leitfaden zu SDFs und Marching Cubes.

Signed Distance Fields (SDFs). Eine volumetrische Repräsentation, die für jeden Punkt im dreidimensionalen Raum den vorzeichenbehafteten Abstand zur nächsten Oberfläche speichert. Positive Werte liegen außerhalb, negative innerhalb, und der Nulldurchgang bildet die Oberfläche. SDFs können beliebige 3D-Formen darstellen: Höhlen, Bögen, Überhänge und schwebende Geometrie, die sich mit Heightmaps nicht ausdrücken lassen. Bearbeitungen entsprechen natürlichen Mengenoperationen auf dem Feld. Das Hinzufügen von Material (Vereinigung zweier Formen) ist $d=min(d_1,d_2)$, das Entfernen (Graben) ist $d=max(d_1,-d_2)$ mit negierter Aushöhlungsform, und eine weiche Überblendung verwendet ein glattes Minimum wie etwa

$$\mathrm{smin}(d_1,d_2,k)=min(d_1,d_2)-\frac{h^2}{4k},h=max(k-|d_1-d_2|,0)$$

wobei $k$ den Überblendungsradius steuert. Für $k\to 0$ fällt dies wieder auf ein hartes $min$ zurück. Siehe SDF-Repräsentation von Terrain.

WebGPU-Compute-Shader. GPU-Programme, die allgemeine Berechnungen ausführen und nicht an die Rasterisierungs-Pipeline gebunden sind. Ein Compute-Shader startet Arbeitsgruppen aus Threads, die parallel ausgeführt werden. Bei Marching Cubes verarbeitet jeder Thread eine Rasterzelle: Er tastet das SDF ab, klassifiziert die Zelle, schlägt die Triangulierung nach, interpoliert die Kanten-Vertices und hängt diese mithilfe atomarer Zähler an einen Mesh-Puffer an. Eine Rückübertragung zur CPU ist nicht erforderlich, da der Ausgabepuffer direkt als Vertex-Daten für das Rendering verwendet wird. Will Ushers webgpu-marching-cubes demonstriert die Echtzeitverarbeitung eines ${256}^3$-Rasters im Browser. Siehe unseren Terrain-Leitfaden zu GPU-gesteuertem LOD mit WebGPU.

Hybride Heightmap- und SDF-Architektur. Der praktische Ansatz für Browser-Terrain: Heightmaps decken die gesamte Welt ab und sind dabei günstig und kompakt, während SDF-Volumen nur in Chunks vorhanden sind, die Höhlen, Überhänge oder von Creatorn geformte Strukturen benötigen (5–10 % der Chunks). In der Nähe der Kamera ermöglicht die volumetrische Freiheit das Graben und die Darstellung von Höhlen. In der Ferne sorgen Heightmaps effizient für flaches Terrain. Siehe hybride Terrain-Repräsentation.

---

Teil 7 von 12.
Zurück: Teil 6 – Clipmaps veränderten die Handlung
Weiter: Teil 8 – Integration, ohne unsere Ausgangsbasis zu verlieren
Serienleitfaden: /blog/2026-02-25-open-world-browser-series-guide