VoxelSpace: Algoritme Rendering Medan yang Diimplementasikan dengan Kurang dari 20 Baris Kode (2020)

 (github.com/s-macke)
4 poin oleh GN⁺ 2025-01-05 | 1 komentar | Bagikan ke WhatsApp
  • Voxel Space adalah teknik rendering medan 2.5D yang digunakan di Comanche milik NovaLogic pada 1992, yang menampilkan gunung dan lembah bertekstur hanya dengan CPU pada masa ketika akselerasi GPU belum ada atau masih mahal
  • Medan direpresentasikan dengan height map dan color map, dan Comanche menggunakan height map 1024×1024 1-byte serta color map 1024×1024 1-byte
  • Color map sudah berisi shading dan bayangan, sehingga tidak perlu perhitungan pencahayaan saat rendering, tetapi karena setiap posisi di peta hanya bisa memiliki satu ketinggian, struktur geometri kompleks seperti bangunan atau pohon sulit direpresentasikan
  • Rendering dasar bekerja dengan merasterisasi segmen garis peta dari belakang ke depan, lalu membaca tinggi dan warna untuk setiap kolom layar dan menggambar garis vertikal; sudut pandang 90° dan proyeksi perspektif dapat diimplementasikan hanya dengan beberapa baris kode
  • Peningkatan performa dimungkinkan dengan menggambar dari depan ke belakang sambil melewati area yang tertutup menggunakan y-buffer per kolom, serta mengurangi detail pada jarak jauh

Konteks kemunculan Voxel Space

  • Pada 1992, CPU 1000 kali lebih lambat dibanding sekarang, dan akselerasi GPU belum dikenal luas atau terlalu mahal untuk digunakan
  • Game 3D dihitung hanya dengan CPU, dan mesin rendering umumnya menggambar poligon berisi warna solid
  • NovaLogic merilis Comanche pada 1992, dan tekstur, shading, serta bayangan pada gunung dan lembahnya tampak berbeda dari grafis game saat itu
  • README menyediakan Web Demo of the Voxel Space Engine

Representasi medan: height map dan color map

  • Dalam Voxel Space, cara paling sederhana untuk merepresentasikan medan adalah menggunakan height map dan color map
  • Comanche menggunakan dua peta berikut
    • height map 1-byte 1024×1024
    • color map 1-byte 1024×1024
  • Peta-peta ini berulang secara periodik
  • Setiap posisi pada peta hanya bisa memiliki satu ketinggian
    • Struktur geometri kompleks seperti bangunan atau pohon tidak dapat direpresentasikan
    • Sebagai gantinya, shading dan bayangan sudah disertakan di color map sehingga pencahayaan tidak perlu dihitung saat rendering

Algoritme rendering dasar

  • Mesin Voxel Space merender medan dengan merasterisasi height map dan color map lalu menggambar garis vertikal ke layar
  • Prosedur dasarnya adalah sebagai berikut
    • Membersihkan layar
    • Menggambar dari belakang ke depan untuk memastikan occlusion
    • Menemukan garis pada peta yang berada pada jarak optik yang sama dari pengamat
    • Mempertimbangkan sudut pandang dan proyeksi perspektif
    • Membagi garis tersebut sesuai jumlah kolom layar
    • Membaca tinggi dan warna dari peta 2D pada setiap posisi segmen garis
    • Menerapkan proyeksi perspektif pada koordinat ketinggian
    • Menggambar garis vertikal dengan tinggi hasil proyeksi dan warna dari color map
  • Dalam bentuk Python paling sederhana, loop intinya mengurangi z dari jarak jauh ke jarak dekat dan memanggil DrawVerticalLine untuk setiap kolom layar
  • Contoh pemanggilan meneruskan posisi, tinggi kamera, posisi horizon, skala tinggi, jarak maksimum, serta lebar dan tinggi layar

Menambahkan rotasi

  • Algoritme dasar hanya bisa melihat ke arah utara
  • Untuk melihat ke arah lain, ditambahkan kode untuk memutar koordinat
  • Versi dengan rotasi menerima phi sebagai sudut pandang, lalu menghitung sin(phi) dan cos(phi) terlebih dahulu
  • Koordinat hasil rotasi diterapkan saat menghitung titik batas pandang kiri dan kanan, lalu x dan y dinaikkan bersama sepanjang setiap kolom layar
  • Struktur inti rendering tetap sama
    • Menghitung segmen garis berdasarkan jarak
    • Merasterisasi sesuai kolom layar
    • Mengakses height map dan color map
    • Menggambar garis vertikal setelah proyeksi perspektif

Cara peningkatan performa

  • Alih-alih menggambar dari belakang ke depan, menggambar dari depan ke belakang dapat mengurangi area yang tertutup
  • Pendekatan ini membutuhkan y-buffer yang menyimpan posisi y tertinggi untuk setiap kolom layar
    • Nilai awal y-buffer diatur ke tinggi layar
    • Bagian baru hanya digambar jika height_on_screen yang dihitung berada di atas y-buffer yang ada
    • Setelah digambar, y-buffer diperbarui ke posisi yang lebih tinggi
  • Jarak z meningkat dari dekat ke jauh
  • Jika dz diperbesar secara bertahap, jarak jauh bisa di-sampling dengan interval lebih besar sehingga menghasilkan efek Level of Detail
  • Area dekat dirender lebih detail, sedangkan area jauh dirender dengan detail lebih rendah

Materi yang disediakan dan lisensi

  • Repositori ini mencakup beberapa pasangan color map dan height map
  • Bagian perangkat lunaknya menggunakan lisensi MIT
  • Teknologi Voxel Space mungkin masih memiliki paten yang berlaku di beberapa negara
  • Color map dan height map dikecualikan dari lisensi karena merupakan materi hasil rekayasa balik dari game Comanche
  • Sebagai referensi terkait, disediakan tautan Voxel terrain engine - an introduction

Bacaan terkait

1 komentar

 
GN⁺ 2025-01-05
Pendapat Hacker News

  • Sangat keren. Saya merindukan masa ketika algoritme baru dan elegan seperti ini menciptakan pengalaman yang terasa seperti sihir
    Mungkin saya merasa begitu karena sudah menua, tetapi game pada masa sumber daya hardware masih terbatas rasanya punya lebih banyak keajaiban dibanding sekarang. Pada 80-an, 90-an, dan awal 2000-an, hampir setiap tahun, atau setidaknya setiap generasi, game mendorong mediumnya sendiri ke depan, dan para developer memeras kemampuan hardware sampai batasnya dengan teknik baru dan optimasi yang benar-benar terasa seperti sihir
    Belakangan ini, platform fantasi seperti PICO-8 jauh lebih menarik daripada rilis berulang dari studio AAA, dan saya sebenarnya kurang mengerti kenapa game yang pada dasarnya hanya mengganti aset bisa sukses seperti itu setiap tahun

    • Game AAA modern juga masih berisi banyak teknologi yang terasa ajaib. Faktanya, industri game adalah salah satu dari sedikit bidang yang benar-benar serius memedulikan performa, dan kadang bahkan lebih mengutamakan performa daripada keamanan atau akurasi
      Hanya saja sekarang jauh lebih rumit dan tidak terlalu terlihat. Dulu, kita bisa melihat kemajuan dari segitiga datar menuju tekstur berkat trik matematika yang cerdas; sekarang kemajuannya berupa bayangan yang lebih baik di sudut ruangan. Peningkatan tekstur bisa langsung disadari siapa pun, tetapi bayangan di sudut sulit ditunjuk secara spesifik kecuali oleh orang industri. Tetap saja, elemen-elemen seperti ini menumpuk dan membuat grafis keseluruhan lebih baik, walau tidak seimpresif dulu
      Industri game AAA adalah bisnis besar, biaya pembuatan game sangat besar, dan investor menginginkan keuntungan. Jadi biasanya mereka meneliti pasar, melihat apa yang laku, lalu membuat sesuatu ke arah yang mirip. Orisinalitas menurun, tetapi risikonya juga lebih rendah
      Sebaliknya, di industri game indie ada ribuan studio, dan karena mereka tidak bisa mengalahkan AAA dalam jumlah konten atau tingkat penyelesaian, mereka membutuhkan senjata lain seperti ide orisinal agar bisa menonjol dari kerumunan. Namun sekarang, mengatasi keterbatasan teknis sering kali bukan lagi pendorong utama. Karena batasannya tidak sebanyak dulu. Justru karena tidak terjangkau dari sisi biaya, mereka sering kali tidak mendorong teknologi sejauh produksi AAA
      Saya tidak begitu mengenal kancah PICO-8, tetapi saya penasaran seberapa besar bagiannya berupa mengatasi batasan teknis yang dibuat secara artifisial, dan seberapa besar berupa memakai platform sesuai cara yang dimaksudkan sambil berfokus pada gameplay
    • Ini rasanya hampir seperti nostalgia dengan kacamata las seperempat inci berwarna merah jambu. Game AAA modern juga punya momen-momen yang begitu bagus sampai membuat takjub, dan walau ada penyakit sekuel berulang, ada juga karya-karya orisinal, dan teknologi jelas memungkinkan itu
      Saya juga ingat dulu ada sangat, sangat, sangat banyak game yang buruk sekali
    • Saya dulu membuat 3D Mario Kart di kalkulator dengan algoritme ini. Kalkulator itu biasanya bahkan nyaris tidak sanggup menangani grafis 2D, jadi cukup menyenangkan, tetapi akhirnya tidak pernah selesai
      Salah satu prototipenya ini: https://youtu.be/9Z8Bm8ZmWKI
    • Saya dulu membuat 3D Mario Kart di kalkulator dengan algoritme ini. Kalkulator itu biasanya bahkan nyaris tidak sanggup menangani grafis 2D, jadi cukup menyenangkan, tetapi akhirnya tidak pernah selesai
      Salah satu prototipenya ini: https://media.discordapp.net/attachments/953383695908216843/...
    • Di teknologi game masih ada banyak inovasi keren. Lihat saja game seperti Noita, Dreams, Teardown, dan untuk game yang lebih baru ada Tiny Glade
      Presentasi teknis terbaru Tiny Glade penuh dengan hal-hal yang terasa seperti sihir: https://youtu.be/jusWW2pPnA0?si=IE-6W0Z1VCBld0AT
      Teknologi keren juga muncul di engine dan framework pada level yang lebih mendasar. Contohnya Nanite/Lumen/MegaLights di UE5

  • Berikut tautan terkait. Ada yang lain?
    VoxelSpace – Terrain rendering algorithm in less than 20 lines of code - https://news.ycombinator.com/item?id=38051859 - Oktober 2023, 2 komentar
    Voxel Space: Comanche's terrain rendering in less than 20 lines of code (2020) - https://news.ycombinator.com/item?id=26631995 - Maret 2021, 71 komentar
    Terrain rendering algorithm in less than 20 lines of code - https://news.ycombinator.com/item?id=21944573 - Januari 2020, 116 komentar
    Terrain rendering in fewer than 20 lines of code - https://news.ycombinator.com/item?id=15772065 - November 2017, 93 komentar
    Show HN: Voxel Space – terrain rendering in less than 20 lines of code - https://news.ycombinator.com/item?id=15339016 - September 2017, 2 komentar

  • mars.com langsung teringat. Bukan domain, melainkan program. Video: https://www.youtube.com/watch?v=_zSjpIyMt0k
    Tambahan: ada juga di Pouet: https://www.pouet.net/prod.php?which=4662

    • Saya juga menemukan implementasi JavaScript dari demo ini: http://web.archive.org/web/20140107070635/http://ppl-pilot.c...
    • Kenangan masa lalu langsung menyeruak. Saat sampai ke saya sekitar tahun 1998, program ini ada di dalam file Microsoft Word dan dikendalikan dengan mouse
      Waktu itu saya menganggapnya keren, tetapi karena saya masih anak-anak yang sama sekali tidak tahu soal demoscene atau pemrograman, saya kecewa karena itu bukan game utuh. Kalau dipikir lagi, saya hanya menganggapnya semacam demo DirectX murahan yang beredar lewat email, dan tidak tahu bahwa benda itu benar-benar pernah ada
    • Tepatnya, mars.com berjalan mulus bahkan di 286 8MHz
    • Sakit rasanya. Saya ingat pernah menjalankannya di 286 dan terpukau. Di saat yang sama juga kecewa karena Wing Commander 3 tidak bisa berjalan di mesin yang sama

  • Cara rendering-nya rapi, tetapi saya tidak tahu apakah ini bisa disebut voxel. Ia tidak bisa merender volume arbitrer, dan cara penyimpanan datanya juga hanya bisa memiliki satu posisi untuk x,y tertentu
    Bukankah ini sekadar implementasi keren dari renderer heightmap?

    • Saya rasa ini jelas boleh dianggap sebagai mesin voxel. Heightmap memang tidak mendukung overhang seperti octree, tetapi pada akhirnya tinggi adalah tumpukan voxel
      Octree tanpa overhang akan berbentuk persis seperti ini
    • Setahu saya voxel berarti semacam volume element. Mirip seperti pixel berasal dari picture element, dan x menurut saya lebih seperti huruf untuk gaya
      Dalam metode rendering ini, tiap kolom adalah kotak 3D, jadi menurut saya tidak ada masalah menyebutnya matriks voxel 2x2
    • Renderer heightmap seperti ini pada masa itu memang jelas disebut “voxel”
    • Benar, nama yang diberikan pada algoritma ini memang menyesatkan

  • Saya punya kenangan yang sangat menyenangkan saat pada 1990-an, bersamaan dengan belajar trigonometri yang diperlukan di SMA, saya membuat viewer terrain seperti ini. Awalnya dengan Pascal, lalu dengan C dan Assembly
    Saat itu, agar bisa berjalan, diperlukan segala macam optimisasi level rendah
    Menemukan sendiri cara mengimplementasikan dan mengoptimalkannya tanpa buku rujukan atau internet adalah salah satu hal yang paling memuaskan bagi saya pribadi

  • Saya membuat game dengan teknik ini: https://eri0o.itch.io/i-rented-a-boat
    Dibuat dengan Adventure Game Studio, dan dikerjakan di versi engine sebelumnya yang belum saya optimalkan. Saya malas memperbarui halaman itch jadi masih saya biarkan begitu, tetapi suatu saat akan saya lakukan
    Di sana saya menulis bagaimana saya membuatnya, dan ada penjelasan lebih detail di forum AGS

    • Mengesankan bahwa ini bisa dilakukan di AGS

  • Sepertinya boleh juga menambahkan [2020] pada judul, dan melihat komentar lain di tautan diskusi di bawah, [2017] juga tampaknya memungkinkan
    Ada juga diskusi tahun 2021 tentang repositori yang sama: https://news.ycombinator.com/item?id=26631995
    Di thread itu juga ada tautan ke diskusi-diskusi lain
    Tidak sepenuhnya sama, tetapi saya ingat saat pertama kali belajar pemrograman, saya membuat program yang menghasilkan heightmap terrain dan merendernya dengan gaya isometrik memakai teknik serupa. Dibuat dengan QBasic, dijalankan di mesin DOS era 386 di SMP, dan memakai memori grafis sebagai ruang kerja sementara
    Sangat lambat, tetapi saya terpikat oleh hasil keluarannya, dan itu menjadi salah satu pemicu yang membuat saya terus memprogram

  • Saya ingat pernah membaca ini di suatu tempat dulu, dan kali ini saya meninggalkan komentar agar tidak hilang lagi
    Sebagai penggemar simulator penerbangan, saya masih ingat kejutan saat pertama kali memainkan Comanche. Rasanya seperti berasal dari masa depan atau film, dan benar-benar membuat saya merasa hidup di era komputer

    • Novalogic cukup lama memakai teknik ini untuk rendering terrain, dan favorit saya adalah Delta Force pertama
      Sepertinya Comanche 4 dan Black Hawk Down yang asli meninggalkan cara ini dan beralih ke engine poligon: https://en.wikipedia.org/wiki/Comanche_4#Reception
    • Saya ingat Comanche. Itu mengingatkan saya pada saat terpukau oleh generasi prosedural di Rescue on Fractalus[0] di Atari 8-bit, yang sebelum rilis bernama Behind Jaggi Lines
      [0] https://www.youtube.com/watch?v=FbZ-chrOgGg adegan pendaratan di Bumi muncul pada 1:00

  • Benar-benar keren
    Di kebanyakan game modern, karena sudut kamera yang aneh atau masalah clipping, kadang terlihat bahwa gunung adalah struktur berongga
    Namun dengan cara ini, gunungnya padat terisi >:)

  • Saya sangat merekomendasikan mencoba membuat software renderer seperti ini untuk bersenang-senang. Ray tracer memang proyek yang umum, tetapi kode rendering real-time retro seperti ini juga cocok sebagai proyek akhir pekan
    Dulu saya pernah mengimplementasikan algoritma yang hampir sama. Tepatnya, saya mem-port kode SDL sebagai latihan untuk belajar canvas2d: http://namuol.github.io/earf-html5/
    Tentu saja implementasi yang ditautkan jauh lebih cepat dan jauh lebih sederhana daripada milik saya, jadi kalau mencari referensi, saya tidak menyarankan kode CoffeeScript lama saya…