VoxelSpace: 20 satırdan az kodla uygulanmış arazi render algoritması (2020)

 (github.com/s-macke)
4 puan yazan GN⁺ 2025-01-05 | 1 yorum | WhatsApp'ta paylaş
  • Voxel Space, 1992'de NovaLogic'in Comanche oyununda kullanılan bir 2.5D arazi render tekniğidir; GPU hızlandırmasının olmadığı ya da pahalı olduğu bir dönemde yalnızca CPU ile dokulu dağlar ve vadiler göstermeyi sağlıyordu
  • Arazi, height map ve color map ile temsil edilir; Comanche 1024×1024 1 baytlık bir height map ve 1024×1024 1 baytlık bir color map kullanıyordu
  • Color map içinde gölgelendirme ve gölgeler zaten bulunduğundan render sırasında ışık hesaplaması gerekmez, ancak haritadaki her konum yalnızca tek bir yükseklik değerine sahip olabildiği için bina veya ağaç gibi karmaşık geometrik yapıları ifade etmek zordur
  • Temel render işlemi, haritadaki çizgi segmentlerini arkadan öne doğru rasterize edip her ekran sütunu için yükseklik ve rengi okuyarak dikey çizgiler çizme yöntemine dayanır; 90° görüş açısı ve perspektif projeksiyon birkaç satır kodla uygulanır
  • Performans iyileştirmesi, önden arkaya çizim yapıp sütun başına bir y-buffer ile gizlenen bölümleri atlayarak ve uzak mesafelerde ayrıntı seviyesini düşürerek mümkündür

Voxel Space'in ortaya çıktığı bağlam

  • 1992'de CPU'lar bugüne göre 1000 kat daha yavaştı ve GPU hızlandırması ya bilinmiyordu ya da karşılanamayacak kadar pahalıydı
  • 3D oyunlar yalnızca CPU ile hesaplanıyor, render motorları ise genelde tek renk doldurulmuş poligonlar çiziyordu
  • NovaLogic, 1992'de Comanche'yi yayımladı ve oyundaki dağ-vadi dokuları, gölgelendirme ve gölge kullanımı döneminin oyun grafiklerinden ayrışıyordu
  • README, Web Demo of the Voxel Space Engine bağlantısını sunuyor

Arazi gösterimi: height map ve color map

  • Voxel Space'te araziyi göstermenin en kolay yolu height map ve color map kullanmaktır
  • Comanche şu iki haritayı kullanıyordu
    • 1024×1024 1 baytlık height map
    • 1024×1024 1 baytlık color map
  • Bu haritalar periyodik olarak tekrar eden yapıdadır
  • Her harita konumu yalnızca tek bir yükseklik değerine sahip olabilir
    • Bina ve ağaç gibi karmaşık geometrik yapılar gösterilemez
    • Buna karşılık color map içinde gölgelendirme ve gölgeler zaten bulunduğundan render sürecinde ışık hesaplaması yapmaya gerek kalmaz

Temel render algoritması

  • Voxel Space motoru, height map ile color map'i rasterize edip ekranda dikey çizgiler çizerek araziyi render eder
  • Temel süreç şöyledir
    • Ekranı temizler
    • Gizleme işlemini garanti etmek için arkadan öne çizer
    • Gözlemciden aynı optik uzaklığa karşılık gelen harita üzerindeki çizgiyi bulur
    • Görüş açısını ve perspektif projeksiyonu hesaba katar
    • İlgili çizgiyi ekran sütunu sayısına göre böler
    • Her çizgi parçası konumunda yükseklik ve rengi 2D haritadan okur
    • Yükseklik koordinatına perspektif projeksiyonu uygular
    • Yansıtılan yükseklik ve color map'teki renk ile dikey çizgi çizer
  • En basit Python biçimindeki çekirdek döngü, z değerini uzak mesafeden yakına doğru azaltırken her ekran sütunu için DrawVerticalLine çağırır
  • Örnek çağrı; konum, kamera yüksekliği, ufuk çizgisi konumu, yükseklik ölçeği, maksimum mesafe, ekran genişliği ve yüksekliğini geçirir

Dönüş ekleme

  • Temel algoritma yalnızca kuzeye bakabilir
  • Başka yönlere bakmak için koordinatları döndüren kod eklenir
  • Dönüşlü sürüm, görüş açısı olarak phi alır ve sin(phi) ile cos(phi) değerlerini önceden hesaplar
  • Sol ve sağ görüş sınırı noktalarının hesabında döndürülmüş koordinatlar uygulanır ve her ekran sütunu boyunca x ile y birlikte artırılır
  • Render'ın temel yapısı aynı kalır
    • Mesafeye göre çizgi segmenti hesabı
    • Ekran sütunlarına göre rasterizasyon
    • Height map ve color map sorgulaması
    • Perspektif projeksiyon sonrası dikey çizgi çizimi

Performans iyileştirme yöntemleri

  • Arkadan öne çizmek yerine önden arkaya çizmek, gizlenen alanları azaltabilir
  • Bu yöntem, her ekran sütunu için en yüksek y konumunu tutan bir y-buffer gerektirir
    • Başlangıç y-buffer değeri ekran yüksekliğine ayarlanır
    • Yeni hesaplanan height_on_screen yalnızca mevcut y-buffer değerinden daha yukarıdaysa görünen kısmı çizer
    • Çizimden sonra y-buffer daha yüksek konuma güncellenir
  • z mesafesi yakından uzağa doğru artar
  • dz değerini kademeli olarak büyütmek, uzak mesafelerde daha geniş aralıklarla örnekleme yapmayı sağlayarak Level of Detail etkisi verir
  • Bu yaklaşım yakındaki alanları daha ayrıntılı, uzaktakileri ise daha az ayrıntılı render eder

Sunulan materyaller ve lisans

  • Depoda birden çok color map ve height map çifti yer alır
  • Yazılım kısmı MIT lisansı altındadır
  • Voxel Space tekniğinin bazı ülkelerde hâlâ geçerli patentleri olabilir
  • Color map ve height map'ler, Comanche oyunundan reverse engineering ile elde edilen materyaller olduğundan lisansa dahil değildir
  • İlgili kaynak olarak Voxel terrain engine - an introduction bağlantısı verilir

İlgili okumalar

1 yorum

 
GN⁺ 2025-01-05
Hacker News yorumları

  • Çok havalı. Böyle yeni ve zarif algoritmaların sihir gibi deneyimler yarattığı zamanları özlüyorum.
    Yaşlandığım için böyle hissediyor da olabilirim ama donanım kaynaklarının kısıtlı olduğu dönemin oyunlarında bugünkünden daha büyük bir sihir vardı sanki. 80’lerde, 90’larda ve 2000’lerin başında neredeyse her yıl, en azından her nesilde, oyunlar mecranın kendisini ileri taşıyordu; geliştiriciler yeni tekniklerle ve saf büyü gibi optimizasyonlarla donanımın performansını sonuna kadar sıkıştırıyordu.
    Bugünlerde PICO-8 gibi fantasy platformlar, AAA stüdyolarının yinelemeli çıkışlarından çok daha ilginç geliyor; açıkçası pratikte sadece varlıkları değiştirilmiş oyunların her yıl nasıl bu kadar başarılı olduğunu pek anlamıyorum.

    • Modern AAA oyunlarda hâlâ çok sayıda sihirli teknoloji var. Aslında oyun sektörü performansı ciddiye alan az sayıdaki alandan biri; bazen güvenlikten ya da doğruluktan bile daha fazla performansa önem veriyor.
      Sadece artık çok daha karmaşık ve göze daha az çarpıyor. Eskiden akıllı bir matematik hilesiyle düz üçgenlerden dokulara geçiş gibi bir ilerleme görülebiliyordu; bugün ise odanın köşesindeki gölgelendirmeyi daha iyi hâle getirmek gibi ilerlemeler var. Doku iyileştirmesini herkes hemen fark eder, ama köşedeki gölgeyi sektörden olmayan biri kolay kolay işaret edip söyleyemez. Yine de bu unsurlar birikerek genel grafikleri daha iyi yapıyor; sadece eskisi kadar etkileyici görünmüyor.
      AAA oyun sektörü büyük bir iş alanı; oyunların yapım maliyetleri devasa ve yatırımcılar getiri istiyor. Bu yüzden genelde pazarı araştırıp neyin iyi sattığına bakıyor, sonra ona benzer bir yönde üretim yapıyorlar. Özgünlük azalıyor ama risk de düşüyor.
      Buna karşılık indie oyun sektöründe binlerce stüdyo var; içerik miktarı ya da cilalanmışlık açısından AAA’yı yenemeyecekleri için kalabalıktan sıyrılmak adına özgün fikirler gibi başka silahlara ihtiyaçları var. Ancak artık çoğu zaman ana itici güç teknik sınırları aşmak değil; çünkü kısıtlar eskisi kadar fazla değil. Hatta maliyet açısından altından kalkılamadığı için AAA yapımlara göre teknik olarak daha az zorladıkları sık görülüyor.
      PICO-8 sahnesini iyi bilmiyorum ama bunun ne kadarının yapay teknik kısıtları aşmakla, ne kadarının da platformu amaçlandığı şekilde kullanıp oynanışa odaklanmakla ilgili olduğunu merak ediyorum.
    • Bu bana neredeyse pembe renkli 1/4 inç kaynak gözlüğüyle yapılan bir nostalji gibi geliyor. Modern AAA oyunlarda da aklı baştan alacak kadar iyi anlar var; tekrar devam oyunu hastalığı da var ama özgün işler de var ve teknoloji bunu açıkça mümkün kılıyor.
      Eskiden de gerçekten, gerçekten, gerçekten berbat oyunların çok olduğunu hatırlamak lazım.
    • Bu algoritmayla hesap makinesinde 3D Mario Kart yapıyordum. O hesap makinesi normalde 2D grafikleri bile zar zor kaldıran bir seviyedeydi, bu yüzden epey eğlenceliydi ama sonunda tamamlayamadım.
      Prototiplerden biri şu: https://youtu.be/9Z8Bm8ZmWKI
    • Bu algoritmayla hesap makinesinde 3D Mario Kart yapıyordum. O hesap makinesi normalde 2D grafikleri bile zar zor kaldıran bir seviyedeydi, bu yüzden epey eğlenceliydi ama sonunda tamamlayamadım.
      Prototiplerden biri şu: https://media.discordapp.net/attachments/953383695908216843/...
    • Oyun teknolojisinde hâlâ çok sayıda harika yenilik var. Noita, Dreams, Teardown gibi oyunlara bakmak yeterli; daha yeni oyunlardan Tiny Glade de var.
      Tiny Glade’in yakın tarihli teknik sunumu sihir gibi şeylerle dolu: https://youtu.be/jusWW2pPnA0?si=IE-6W0Z1VCBld0AT
      Daha temel seviyedeki motor ve framework’lerde de harika teknolojiler çıkıyor. Örneğin UE5’in Nanite/Lumen/MegaLights özellikleri var.

  • İlgili bağlantılar bunlar. Başka var mı?
    VoxelSpace – Terrain rendering algorithm in less than 20 lines of code - https://news.ycombinator.com/item?id=38051859 - Ekim 2023, 2 yorum
    Voxel Space: Comanche's terrain rendering in less than 20 lines of code (2020) - https://news.ycombinator.com/item?id=26631995 - Mart 2021, 71 yorum
    Terrain rendering algorithm in less than 20 lines of code - https://news.ycombinator.com/item?id=21944573 - Ocak 2020, 116 yorum
    Terrain rendering in fewer than 20 lines of code - https://news.ycombinator.com/item?id=15772065 - Kasım 2017, 93 yorum
    Show HN: Voxel Space – terrain rendering in less than 20 lines of code - https://news.ycombinator.com/item?id=15339016 - Eylül 2017, 2 yorum

  • mars.com hemen aklıma geldi. Alan adı değil, program. Video: https://www.youtube.com/watch?v=_zSjpIyMt0k
    Ek: Pouet’te de var: https://www.pouet.net/prod.php?which=4662

    • Bu demonun JavaScript uygulamasını da buldum: http://web.archive.org/web/20140107070635/http://ppl-pilot.c...
    • Eski anılar birden canlandı. 1998 civarında bana ulaştığında bir Microsoft Word dosyasının içindeydi ve fareyle kontrol ediliyordu.
      O zamanlar havalı olduğunu düşünmüştüm ama demoscene ya da programlama hakkında hiçbir şey bilmeyen bir çocuk olduğum için tam bir oyun olmamasına hayal kırıklığına uğramıştım. Geriye dönüp bakınca, e-postayla dolaşan dandik bir DirectX demosu gibi düşünmüşüm; gerçekten var olan bir şey olduğunu bilmiyordum.
    • Daha doğrusu mars.com, 8MHz 286 üzerinde bile akıcı çalışıyordu.
    • Acı veriyor. 286’da çalıştırıp büyülendiğimi hatırlıyorum. Aynı zamanda aynı makinede Wing Commander 3 çalışmadığı için hayal kırıklığına uğramıştım.

  • Render yöntemi temiz, ama buna voxel denebilir mi emin değilim. Rastgele bir hacmi render edemiyor ve veri saklama biçimi de verilen x,y için yalnızca tek bir konuma izin veriyor.
    Sadece bir heightmap renderer’ın şık bir uygulaması değil mi?

    • Kesinlikle voxel engine olarak görülebileceğini düşünüyorum. Heightmap, octree gibi çıkıntıları desteklemez ama sonuçta yükseklik bir voxel yığınıdır.
      Çıkıntısı olmayan bir octree bununla tam olarak aynı şekle sahip olurdu.
    • Bildiğim kadarıyla voxel, volume element gibi bir anlama geliyor. Pixel’in picture element’ten gelmesine benziyor; x de daha çok havalı görünsün diye konmuş bir harf gibi.
      Bu render yönteminde her sütun bir 3D kutu olduğundan, buna 2x2 voxel matrisi demekte bence pek sorun yok.
    • Bu tür heightmap renderer’lar o dönemde kesinlikle “voxel” diye adlandırılıyordu.
    • Evet, bu algoritmaya verilen ad kafa karıştırıcı.

  • 1990’larda lisede gerekli trigonometriyi öğrenirken aynı zamanda böyle arazi görüntüleyicileri yaptığımı hatırlamak gerçekten güzel. Önce Pascal’da, sonra C ve Assembly’de yaptım.
    O zamanlar çalışır hale getirmek için türlü düşük seviye optimizasyonlar gerekiyordu.
    Başvuracak kitap ya da internet olmadan nasıl uygulanacağını çözüp optimize etmek, kişisel olarak en tatmin edici işlerimden biriydi.

  • Bu teknikle bir oyun yaptım: https://eri0o.itch.io/i-rented-a-boat
    Adventure Game Studio ile yaptım ve henüz optimize etmediğim eski bir motor sürümünde üretildi. itch sayfasını güncellemekle uğraşmaya üşendiğim için öyle bıraktım ama bir gün yapacağım.
    Orada nasıl yaptığımı yazdım; AGS forumunda daha ayrıntılı bilgiler var.

    • AGS’de bunun mümkün olması etkileyici.

  • Başlığa [2020] koymak uygun olabilir; aşağıdaki tartışma bağlantısındaki diğer yorumlara bakınca [2017] de mümkün görünüyor.
    Aynı depo hakkında 2021’de de bir tartışma olmuş: https://news.ycombinator.com/item?id=26631995
    O başlıkta da başka tartışmalara bağlantılar var.
    Tam olarak aynı değil ama programlamayı ilk öğrendiğim zamanlarda arazi heightmap’i üreten ve benzer bir teknikle izometrik tarzda render yapan bir program yazdığımı hatırlıyorum. QBasic ile yapmıştım, ortaokuldaki 386 dönemi DOS makinelerinde çalıştırmıştım ve grafik belleğini geçici çalışma alanı olarak kullanmıştım.
    İnanılmaz yavaştı ama çıktısı beni büyülemişti; programlamaya devam etmemi sağlayan şeylerden biri oldu.

  • Bunu daha önce bir yerlerde okuduğumu hatırlıyorum; bu kez kaybetmemek için yorum bırakıyorum.
    Bir uçuş simülatörü hayranı olarak Comanche’i ilk oynadığımda yaşadığım şoku hâlâ hatırlıyorum. Gelecekten ya da bir filmden gelmiş gibiydi; gerçekten bilgisayar çağında yaşadığımı hissettirmişti.

    • Novalogic bu tekniği arazi render’ında epey uzun süre kullandı; benim favorim ilk Delta Force oyunu.
      Comanche 4 ve orijinal Black Hawk Down’da bu yöntemi bırakıp poligon motoruna geçmiş gibi görünüyorlar: https://en.wikipedia.org/wiki/Comanche_4#Reception
    • Comanche’i hatırlıyorum. 8-bit Atari’de Rescue on Fractalus[0], çıkış öncesi adıyla Behind Jaggi Lines’ın prosedürel üretimine hayran kaldığım zamanı anımsattı.
      [0] https://www.youtube.com/watch?v=FbZ-chrOgGg Dünya’ya iniş sahnesi 1:00’da.

  • Gerçekten harika.
    Modern oyunların çoğunda garip kamera açıları ya da clipping sorunları yüzünden dağların içi boş yapılar olduğunu bazen görebiliyorsunuz.
    Ama bu yöntemde dağlar sağlam şekilde dolu >:)

  • Eğlence için böyle software renderer’lar yapmayı şiddetle tavsiye ederim. Ray tracer yaygın bir proje ama bu tür retro gerçek zamanlı rendering kodları da hafta sonu projesi için iyi.
    Uzun zaman önce neredeyse aynı algoritmayı uygulamıştım. Daha doğrusu canvas2d öğrenmek için bir alıştırma olarak SDL kodunu port etmiştim: http://namuol.github.io/earf-html5/
    Elbette bağlantıdaki uygulama benimkinden çok daha hızlı ve çok daha basit; yani referans arıyorsanız eski CoffeeScript kodumu önermem…