Jangan render rumput di balik bukit: occlusion culling yang memahami medan

Oleh Oleg Sidorkin, CTO dan Co-Founder Cinevva

Bagian 28 memperkenalkan Spike 57 dan menguji performa empat jalur culling-nya dalam beberapa paragraf. Ini versi panjangnya: mengapa kami memilih keempat jalur tersebut, apa saja empat teknik lainnya, dan alasan di balik teknik yang akan kami rilis.

Ada sebuah bukit di antara kamera dan padang rumput. Anda tidak perlu merender padang rumput itu. Semua engine AAA modern memahami hal ini. Sebagian besar engine 3D berbasis browser tidak, termasuk engine kami sampai minggu lalu.

Tulisan ini adalah hasil dari riset yang dilakukan dengan benar, disesuaikan dengan codebase kami yang sebenarnya, diwujudkan sebagai spike yang berfungsi, serta penilaian berbagai teknik berdasarkan seberapa besar manfaatnya secara khusus bagi kami, mengingat saat ini kami merilis untuk WebGL dan besok untuk WebGPU.

Anda dapat mencoba spike interaktif di bawah ini sebelum melanjutkan membaca. T/Y/U/I beralih di antara jalur culling, C menggilir preset kamera, dan B mewarnai chunk yang disembunyikan dengan wireframe merah agar Anda dapat melihat apa saja yang dihapus oleh pengujian tersebut. HUD melaporkan berapa banyak instance yang ditolak oleh setiap tahap.

Buka Spike 57 di tab baru ↗ · Lihat kode sumber

Apa yang dilakukan engine kami saat ini (dan yang tidak dilakukannya)

Pengelola streaming chunk kami memuat lingkaran chunk berukuran 64 m di sekitar pemain pada tiga tingkat LOD. Setiap chunk memiliki pohon-pohon instanced yang disebarkan di atas heightmap. Logika culling-nya, yang berada di Chunk.updateObjectVisibility, hanya berupa pemeriksaan jarak: pohon dalam radius 60 m dirender sebagai mesh penuh, pohon antara 60 m dan 140 m dirender sebagai billboard, dan di luar itu tidak dirender sama sekali.

Culling tersebut melewatkan dua kategori pemborosan yang sangat besar:

1. Apa pun yang berada di dalam lingkaran 60 m tetapi di belakang kamera. Kami mengurutkan ulang buffer instance setiap kali pemain bergerak lebih dari 4 m, tetapi kami tidak menguji view frustum, sehingga rata-rata separuh lingkaran dikirim ke GPU hanya untuk di-clip setelah transformasi vertex.
2. Apa pun yang berada di dalam lingkaran 60 m tetapi di balik bukit. Medan kami memiliki rentang vertikal 80 m dan banyak lembah. Saat kamera berada di lembah, sebagian besar vegetasi di dalam radius culling tersembunyi secara geometris oleh punggung bukit terdekat. Kami tetap menggambarnya.

Kategori kedua menjadi fokus tulisan ini. Ini juga kategori yang diatasi oleh engine AAA dengan serangkaian trik cerdas yang, sekilas, tidak mudah diterapkan di browser.

Gilbert Sanders dari Guerrilla menjelaskan cara Horizon Zero Dawn merender vegetasi dunia terbuka. Pembahasan rangkaian culling ada di 20 menit terakhir dan merupakan pelajaran luar biasa tentang mengapa "menggambar lebih sedikit" mengalahkan "menggambar lebih cepat".

Delapan teknik, dinilai untuk kasus kami

Saya mempelajari rangkaian occlusion culling modern dan menilai setiap bagiannya berdasarkan seberapa besar manfaatnya bagi dunia terbuka prosedural berbasis heightmap yang berjalan di browser. Ada dua sumbu: nilai (seberapa banyak pemborosan yang dihilangkan dalam scene kami) dan biaya (upaya engineering, ditambah seberapa banyak bagian stack kami yang harus diubah). Alasan lengkapnya ada di berkas riset yang mendasari tulisan ini; berikut versi singkatnya.

1. Frustum culling per instance. Nilai tinggi, biaya rendah. Saat ini kami sama sekali tidak menguji frustum untuk vegetasi instanced. Menambahkannya memangkas kira-kira separuh pekerjaan pada tampilan apa pun, hanya membutuhkan sekitar tiga puluh baris kode, dan dapat dirilis di WebGL sekarang. Ini adalah peningkatan murah terbesar dan seharusnya sudah kami lakukan berbulan-bulan lalu.

2. Raycast horizon heightmap. Nilai tinggi, biaya rendah–menengah. Lakukan ray marching dari kamera melalui setiap instance kandidat, sambil mengambil sampel ketinggian medan sepanjang jalurnya. Jika medan pernah naik melampaui ray, instance tersebut terhalang. Teknik ini bekerja secara presisi karena dunia kami merupakan heightmap, yang menyederhanakan visibilitas menjadi persoalan 1D di sepanjang arah horizontal. Versi padatnya memiliki kompleksitas O(langkah) per instance per frame. Versi yang dipercepat (poin berikutnya) menurunkannya menjadi O(log langkah).

3. Akselerasi piramida ketinggian maksimum. Nilai tinggi, biaya menengah. Mipmap 2D dari heightmap, dengan setiap texel menyimpan ketinggian medan maksimum di dalam area cakupannya. Ini memungkinkan raycast horizon melompat dengan langkah-langkah besar saat area sekitarnya datar dan hanya memperhalus pengujian di atas bukit. Struktur inilah yang membuat teknik nomor 2 cukup murah untuk produksi.

4. Occlusion Hierarchical-Z (Hi-Z / HZB). Nilai tinggi, biaya tinggi. Bangun mipmap depth buffer, proyeksikan bounds setiap instance ke screen space, lalu uji terhadap tingkat mip yang tepat. Ini adalah standar modern di sisi GPU, digunakan oleh Nanite milik Unreal, virtual geometry milik Bevy, dan port WebGPU VTK. Teknik ini bekerja untuk semuanya, bukan hanya medan, tetapi memerlukan WebGPU, indirect draw, dan compute pass. Investasinya baru sepadan saat kami merender jutaan helai rumput, bukan ribuan pohon.

5. Hi-Z dua pass (gaya Nanite). Manfaat tambahan kecil dibandingkan nomor 4, biaya tinggi. Render ulang depth frame ini setelah pass 1 untuk menghindari artefak disocclusion satu frame. Hanya layak setelah jalur berbasis GPU kami cukup matang sehingga biayanya bersifat inkremental.

6. Rasterizer occlusion perangkat lunak (Frostbite/Intel MOC). Nilai menengah, biaya tinggi. Rasterisasi depth buffer beresolusi rendah dari occluder besar di CPU. Tanpa latensi readback. Implementasi referensinya berupa C++ AVX/SSE; mem-porting-nya ke WASM merupakan proyek tersendiri, sementara raycast heightmap kami memperoleh sebagian besar manfaat yang sama dengan upaya yang jauh lebih kecil.

7. PVS yang diprakomputasi. Nilai rendah, biaya tinggi. Sangat bagus untuk peta statis era Quake. Medan kami prosedural dan tak terbatas, sehingga semua prapemrosesan harus dilakukan saat streaming chunk, yang biayanya kurang lebih sama dengan menghitung visibilitas saat runtime. Lewati.

8. Horizon culling gaya Cesium. Tidak bernilai bagi kami, biaya menengah. Dirancang untuk elipsoid planet. Dunia kami relatif datar dan berbatas; perhitungannya tidak berlaku dan hanya akan menjadi no-op atau salah melakukan culling. Lewati.

Jadi: lakukan nomor 1 serta nomor 2+3 sekarang, di CPU, dalam WebGL. Rencanakan nomor 4 untuk migrasi WebGPU. Lewati sisanya.

Mengapa raycast heightmap unggul untuk medan di browser

Saran standar dalam presentasi rendering modern mana pun adalah "bangun buffer Hi-Z". Pembahasan mendalam Nanite di SIGGRAPH 2021 oleh Brian Karis adalah rujukan utamanya dan patut Anda tonton setidaknya sekali.

Itu jawaban yang tepat untuk engine yang sudah menjalankan semuanya melalui indirect draw berbasis GPU. Sebagian besar engine browser, termasuk engine kami, belum seperti itu. Kami memiliki buffer instance di sisi CPU, draw call WebGL, dan tidak memiliki tahap compute. Menambahkan Hi-Z ke stack tersebut berarti sekaligus mem-porting ke WebGPU, menulis ulang pipeline vegetasi menjadi indirect draw, serta menambahkan pass untuk membangun depth pyramid. Itu berarti kerja selama seperempat tahun hanya untuk menghasilkan frame pertama yang membuktikan gagasannya.

Raycast heightmap berjalan di CPU, dalam WebGL, menggunakan data yang sudah kami miliki. Teknik ini memanfaatkan satu fakta tentang dunia kami yang tidak dapat dimanfaatkan engine AAA: occluder kami dideskripsikan oleh fungsi ketinggian 1D. Mengambil sampel fungsi tersebut di sepanjang ray hanya memerlukan dua lookup array dan satu perkalian. Buffer Hi-Z harus menemukan fakta yang sama piksel demi piksel.

Teknik ini pertama kali diterbitkan dengan judul "Horizon Occlusion Culling for Hierarchical Terrains" di IEEE Visualization 2002 (PDF). Teknik ini tetap digunakan selama dua dekade karena memiliki karakteristik yang tepat: murah saat medan datar, mahal hanya ketika benar-benar ada bukit, dan sangat mudah diparalelkan.

Piramida ketinggian maksimum, dalam gambar

Raycast naif mengambil sampel terrainHeight pada sekitar 24 titik di sepanjang setiap ray dan berhenti lebih awal jika medan memotongnya. Itu cukup baik untuk ribuan pohon. Namun, performanya runtuh saat menangani ratusan ribu helai rumput.

Solusinya adalah mipmap heightmap dengan setiap texel menyimpan ketinggian maksimum di dalam area cakupannya:

level 0 (256×256, 2,25 m per texel):  h maks dari 4×4 sampel dengan jitter
level 1 (128×128, 4,5 m  per texel):  maks(0,0), maks(1,0), maks(0,1), maks(1,1)
level 2 ( 64×64,  9,0 m per texel):  reduksi yang sama satu level ke atas
...
level 8 (   1×1,  576 m per texel):  maksimum global

Saat segmen ray panjang dan datar, ambil sampel dari level kasar: satu lookup memberi tahu Anda bahwa "tidak ada medan dalam persegi 9 m ini yang pernah melebihi elevasi 12 m, sedangkan ray berada pada ketinggian 30 m di sana, jadi lanjutkan." Hanya ketika texel kasar mengatakan "medan mungkin berada di atas ray", Anda turun satu level dan memperhalus pengujian. Seluruh struktur hanya berukuran beberapa ratus KB dan dapat dibangun dalam puluhan milidetik.

Dalam bentuk diagram:

                                            ray dari mata
        mata 1,7 m                        o─────────────────────►
              o─────────────────────────·─·─·─·─·─·──────────────
              │                          \                       │
              │   level 3 (langkah besar) \   level 0 (perhalus) │
              │   "tak ada medan > 8 m"    \   "bukit 9 m!"      │
              │                              \                   │
        ──────┴────────────/▔▔▔\─────────────/▔▔▔▔▔\─────────────
                                 bukit A (8 m) bukit B (12 m)
                                                ↑
                                           terhalang di sini

Untuk segmen ray yang melewati sekitar bukit A, lookup level 3 ("ketinggian maksimum dalam kotak selebar 18 m ini adalah 8 m") sudah memberi tahu kita bahwa ray pada elevasi 1,7 m ditambah beberapa meter pendakian tidak terhalang. Kita melewati 36 m ray marching hanya dengan satu kueri. Di atas bukit B, level 3 mengatakan "maksimum di sini adalah 12 m", kita turun ke level berikutnya, lalu level 0 mengatakan "ya, 12 m tepat di texel ini", dan kita menolak instance tersebut.

Pembangunan piramida berada di height-pyramid.mjs, sedangkan jalur culling yang menggunakannya berada di cull.mjs. Keduanya dapat dibaca di penjelajah kode sumber spike.

Apa yang sebenarnya ditunjukkan spike ini

Buka Spike 57 di atas dan coba keempat jalurnya:

• T0 adalah yang dilakukan produksi saat ini. Hanya jarak. Dari C1 (dasar lembah), HUD melaporkan sekitar 12.000 helai rumput terlihat.
• T1 menambahkan frustum culling per instance. Jumlah yang terlihat berkurang kira-kira separuh karena apa pun yang berada di belakang kamera atau di luar sisi tampilan dibuang sebelum mencapai GPU.
• T2 menambahkan raycast heightmap brute-force. Di C1, jumlahnya turun lagi sebesar 60–80%, karena sebagian besar lapangan berada di balik punggung bukit terdekat. Kolom Cull-ms naik karena kami mengambil sampel terrainHeight sekitar 24 kali per instance.
• T3 mengganti brute force dengan piramida ketinggian maksimum. Cull-ms kembali mendekati T1 sambil mempertahankan pengurangan jumlah objek terlihat. Inilah jalur yang benar-benar layak Anda rilis.

Polanya sesuai dengan yang ditemukan engine produksi. Seri dua bagian Acerola tentang rendering rumput (Bagaimana Game Merender Begitu Banyak Rumput?, Apa yang Saya Lakukan untuk Mengoptimalkan Rumput dalam Game Saya) adalah penjelasan YouTube yang paling mudah dipahami tentang mengapa upaya engineering sebaiknya dicurahkan pada tahap culling, bukan tahap shading.

Kamera C3 dan kasus kegagalan "puncak bukit"

Preset kamera ketiga pada spike menempatkan kamera di puncak bukit, menghadap ke seluruh area permainan. Dalam kasus ini, horizon culling hampir tidak melakukan apa-apa karena tidak ada medan di antara kamera dan sebagian besar dunia. HUD menunjukkan T2/T3 hanya mengurangi jumlah objek terlihat sekitar 5–10% dibandingkan T1.

Itu adalah fitur, bukan bug. Teknik ini berhenti bekerja tepat ketika seharusnya: saat tidak ada apa pun yang menghalangi. Frustum culling masih melakukan pekerjaan nyata, distance culling masih membatasi anggaran, dan pengujian horizon dengan mulus berubah menjadi no-op. Jika Anda mengimplementasikannya, Anda harus memastikan bahwa kasus no-op juga murah. Inilah alasan piramida ketinggian maksimum tetap penting meskipun tidak ada ray yang akan ditolak: level paling kasar sering kali sudah cukup untuk mengonfirmasi bahwa "tidak ada yang terhalang".

Apa yang akan kami rilis berikutnya

Ada tiga hal yang perlu dilakukan, secara berurutan.

Pertama, porting T1 dan T3 ke Chunk.updateObjectVisibility di produksi. Piramida sebaiknya ditempatkan satu tingkat lebih tinggi, pada pengelola chunk, karena cakupannya melintasi lebih dari satu chunk. Proses culling tetap berada di Chunk agar batching per chunk yang ada terus berfungsi. Perkiraan upaya: satu hari, termasuk pengujian. Kedua, lakukan hal yang sama untuk rumput setelah kita memilikinya. Eksperimen saat ini menyebarkan 12.000 helai rumput di area permainan seluas 576 m; kepadatan produksi seharusnya kira-kira sepuluh kali lebih tinggi. Jalur culling CPU menangani 12.000 helai dalam waktu kurang dari satu milidetik, dan akselerasi piramida membuat hal itu tetap berlaku pada 120.000 helai.

Ketiga, saat kita bermigrasi ke THREE.WebGPURenderer, porting loop yang sama ke compute shader. Metadata menjadi storage buffer. Proses culling menulis argumen drawIndirect. Piramida diunggah sebagai tekstur 2D dengan max-reduction yang sudah diproses sebelumnya. Bentuk kodenya tetap nyaris identik, dan memang itulah intinya: kita tidak mempertaruhkan migrasi pada algoritma baru, tetapi memindahkan algoritma yang sudah kita miliki ke landasan yang lebih cepat.

Guerrilla membahas versi GPU dari pendekatan ini untuk sistem penempatan prosedural Horizon Zero Dawn; pipeline rendering tidak sepenting struktur datanya, dan struktur mereka memiliki bentuk yang sama:

Hi-Z tetap akan berguna setelah kita merilis bangunan dan prop padat yang menutupi objek dari arah yang tidak dapat digambarkan oleh heightmap. Namun, piramida heightmap tetap berada dalam pipeline karena jauh lebih murah daripada Hi-Z untuk instance yang dekat dengan permukaan tanah, sedangkan rumput yang melintasi siluet punggung bukit adalah kasus yang paling sulit ditangani Hi-Z.

Referensi

Alasan lengkap yang telah diprioritaskan dan keputusan arsitekturnya ada di atas; berikut adalah sumber utama untuk setiap teknik, kurang lebih sesuai urutan kemunculannya dalam stack.

• Yalim & Akman, Culling Oklusi Horizon untuk Medan Hierarkis (IEEE Visualization 2002, makalah awal tentang culling horizon medan).
• Turitzin, Buffer Kedalaman Hierarkis (penjelasan paling jelas tentang cara membangun dan melakukan kueri pada rantai mip Hi-Z).
• VKGuide, Culling Berbasis Compute (referensi pipeline culling berbasis GPU; porting ke WebGPU bersifat mekanis).
• Kruskonja, Culling Oklusi Dua Tahap (arsitektur bergaya Nanite yang dijelaskan di luar slide Epic).
• Karis dkk., Nanite — Pembahasan Mendalam (SIGGRAPH 2021) (referensi modern tentang bentuk culling berbasis GPU pada skala AAA).
• Karis, Keynote HPG 2022: Perjalanan Menuju Nanite (konteks yang lebih luas tentang alasan tahap culling penting).
• Sanders, Antara Teknologi dan Seni: Vegetasi Horizon Zero Dawn (stack culling vegetasi AAA secara menyeluruh).
• Guerrilla, Penempatan Prosedural Saat Runtime Berbasis GPU di Horizon Zero Dawn (penempatan berbasis instance dan visibilitas per instance).
• Scthe, Nanite WebGPU (implementasi referensi WebGPU, lengkap dengan HZB).
• Kitware, Culling Oklusi WebGPU di VTK (HZB produksi pertama di sisi browser yang saya ketahui).
• Acerola, Bagaimana Gim Merender Begitu Banyak Rumput? dan Yang Saya Lakukan untuk Mengoptimalkan Rumput di Gim Saya (tur YouTube yang mudah dipahami).
• RasterGrid, Culling Oklusi Berbasis Peta Hi-Z (pengantar Hi-Z yang masih menjadi rujukan utama).
• Intel, Culling Oklusi Perangkat Lunak Bermask (keluarga rasterizer CPU, jika Anda suatu saat memutuskan bahwa #6 layak diterapkan).