Membangun dunia terbuka di browser, bagian 7: Marching cubes dan gua nyata pertama

Oleh Oleg Sidorkin, CTO dan Co-Founder Cinevva

Baru mengikuti seri ini? Gunakan panduan seri. Panduan tersebut menjelaskan apa itu spike dan menyediakan tautan ke semua bagian.

Heightmap sangat bagus sampai Anda membutuhkan struktur yang menjorok.

Begitu ingin membuat terowongan yang dipahat, tepian batu yang menggantung, atau langit-langit gua, pipeline heightfield murni mulai membatasi Anda. Heightmap menyimpan satu nilai Y untuk setiap koordinat XZ. Secara fisik, heightmap tidak mampu merepresentasikan permukaan yang melipat kembali di atas dirinya sendiri. Kami membutuhkan representasi volumetrik.

Spike 12 mengimplementasikan marching cubes di GPU menggunakan compute shader WebGPU. Algoritma ini mengevaluasi signed distance field (SDF) pada grid 3D dan mengekstrak mesh segitiga di permukaan persilangan nol. Setiap sel memiliki 8 sudut, yang masing-masing berada di dalam atau di luar permukaan, sehingga menghasilkan $2^8=256$ kemungkinan pola tanda. Tabel pencarian memetakan setiap pola ke sekumpulan segitiga. Verteks ditempatkan pada rusuk sel, tepat di titik tempat field melintasi nol. Untuk rusuk di antara sudut $a$ dan $b$ dengan nilai field $f_a$ dan $f_b$, interpolasi linear menempatkan verteks pada

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

yang merupakan fraksi sepanjang rusuk tempat nilai field mencapai nol. Karena $f_a$ dan $f_b$ memiliki tanda yang berlawanan pada rusuk yang bersilangan, $t$ selalu berada dalam $[0,1]$. Kami menjalankannya pada empat chunk aktif berukuran 64 kubik secara bersamaan dan menguji pengeditan SDF beranimasi dengan pembuatan ulang mesh pada setiap frame.

Buka Spike 12 di tab baru ↗ · Lihat kode sumber

Keberhasilan pertama memberi kami keyakinan terhadap pipeline komputasi itu sendiri. Satu dispatch dapat mengevaluasi SDF, mengklasifikasikan sel, dan mengeluarkan verteks ke buffer GPU tanpa readback CPU sama sekali. Keberhasilan kedua adalah menyadari betapa cepatnya tahap "sudah berfungsi" berubah menjadi perburuan artefak. Segitiga yang hilang jarang disebabkan oleh masalah dalam teori marching cubes. Penyebabnya adalah ketidakcocokan indeks tabel, rentang draw yang keliru sehingga membaca melewati jumlah verteks aktif, atau interaksi kasus khusus di dekat batas chunk ketika sampel SDF tetangga tidak tersedia.

Spike ini memaksa kami berpikir dalam bentuk zona. Di dekat kamera, Anda menginginkan kebebasan volumetrik agar pemain dapat memahat, menggali, dan melihat gua. Jauh dari kamera, Anda menginginkan efisiensi clipmap karena heightmap datar lebih murah dan sudah sangat memadai. Dualitas tersebut menjadi tulang punggung arsitektur yang terus kami sempurnakan sejak Spike 13 dan seterusnya.

Salah satu momen debugging favorit saya adalah saat menggunakan tombol wireframe ketika pengeditan sedang berjalan. Melihat topologi terbentuk dan melebur secara waktu nyata membuat kompromi kualitas langsung terlihat. Anda dapat melihat bagian yang kepadatan verteksnya sudah cukup tinggi, bagian yang terlalu kasar, dan lokasi persis transisi LOD yang pada akhirnya akan membutuhkan dukungan Transvoxel untuk mencegah retakan.

Di bagian 8, kami membahas tantangan integrasi. Menyatukan mesh mentah yang digerakkan oleh komputasi dan logika scene graph Three.js dalam satu pipeline rendering yang stabil ternyata lebih sulit daripada yang ditunjukkan demo terpisah tersebut.

Teknologi yang dirujuk dalam bab ini

Marching cubes. Algoritma untuk mengekstrak mesh segitiga dari scalar field 3D (Lorensen dan Cline, 1987). Setiap sel dalam grid 3D beraturan diklasifikasikan dengan mengambil sampel field pada 8 sudutnya. Pola tanda menghasilkan indeks kasus (0-255), lalu tabel pencarian memetakan setiap kasus ke sekumpulan segitiga. Verteks ditempatkan pada rusuk grid dengan menginterpolasi antara kedua sudutnya. Algoritma ini sangat mudah diparalelkan karena setiap sel diproses secara independen, sehingga ideal untuk komputasi GPU. Lihat panduan lanskap kami tentang SDF dan marching cubes.

Signed Distance Field (SDF). Representasi volumetrik yang menyimpan jarak bertanda ke permukaan terdekat pada setiap titik dalam ruang 3D. Nilai positif berada di luar, nilai negatif berada di dalam, dan persilangan nol merupakan permukaannya. SDF dapat merepresentasikan bentuk 3D apa pun: gua, lengkungan, struktur yang menjorok, dan geometri mengambang yang tidak dapat diekspresikan oleh heightmap. Pengeditan dilakukan secara alami melalui aljabar himpunan pada field. Penambahan material (gabungan dua bentuk) adalah $d=min(d_1,d_2)$, penghapusan (penggalian) adalah $d=max(d_1,-d_2)$ dengan bentuk pahatan dinegasikan, sedangkan perpaduan halus menggunakan minimum lunak seperti

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

dengan $k$ mengendalikan radius perpaduan. Ketika $k\to 0$, fungsi ini kembali menjadi $min$ yang tegas. Lihat representasi medan SDF.

Compute shader WebGPU. Program GPU yang menjalankan komputasi serbaguna dan tidak terikat pada pipeline rasterisasi. Compute shader menjalankan workgroup berisi thread yang dieksekusi secara paralel. Untuk marching cubes, setiap thread memproses satu sel grid: mengambil sampel SDF, mengklasifikasikan sel, mencari triangulasi, menginterpolasi verteks rusuk, dan menambahkannya ke buffer mesh menggunakan penghitung atomik. Readback CPU tidak diperlukan karena buffer keluaran digunakan langsung sebagai data verteks untuk rendering. webgpu-marching-cubes karya Will Usher mendemonstrasikan pemrosesan grid 256^3 secara waktu nyata di browser. Lihat panduan lanskap kami tentang LOD berbasis WebGPU.

Arsitektur gabungan heightmap + SDF. Pendekatan praktis untuk medan di browser: heightmap mencakup seluruh dunia (murah dan ringkas), sedangkan volume SDF hanya tersedia dalam chunk yang membutuhkan gua, struktur menjorok, atau fitur yang dipahat kreator (5-10% dari seluruh chunk). Di dekat kamera, kebebasan volumetrik memungkinkan pemahatan dan pembuatan gua. Di kejauhan, heightmap menyediakan medan datar yang efisien. Lihat representasi medan gabungan.

---

Bagian 7 dari 12.
Sebelumnya: Bagian 6 - Clipmap mengubah alur pengembangan
Berikutnya: Bagian 8 - Integrasi tanpa kehilangan tolok ukur dasar kami
Panduan seri: /id/blog/2026-02-25-open-world-browser-series-guide