Bagaimana saya bisa menerapkan pencahayaan berbasis voxel dengan penyumbatan dalam gim bergaya Minecraft?

13

Saya menggunakan C # dan XNA. Algoritma saya saat ini untuk pencahayaan adalah metode rekursif. Namun, itu mahal , ke titik di mana satu potongan 8x128x8 dihitung setiap 5 detik.

  • Apakah ada metode pencahayaan lain yang akan membuat bayangan kegelapan variabel?
  • Atau apakah metode rekursif itu baik, dan mungkin saya salah melakukannya?

Sepertinya hal-hal rekursif pada dasarnya mahal (dipaksa untuk melewati sekitar 25k blok per bongkahan). Saya sedang berpikir tentang menggunakan metode yang mirip dengan ray tracing, tetapi saya tidak tahu bagaimana ini akan berhasil. Hal lain yang saya coba adalah menyimpan sumber cahaya dalam Daftar, dan untuk setiap blok mendapatkan jarak ke setiap sumber cahaya, dan menggunakannya untuk menyalakannya ke tingkat yang benar, tetapi kemudian pencahayaan akan menembus dinding.

Kode rekursi saya saat ini ada di bawah. Ini disebut dari sembarang tempat di chunk yang tidak memiliki tingkat cahaya nol, setelah membersihkan dan menambahkan kembali sinar matahari dan cahaya obor.

world.get___atadalah fungsi yang bisa mendapatkan blok di luar chunk ini (ini ada di dalam class chunk). Locationadalah struktur saya sendiri yang seperti Vector3, tetapi menggunakan bilangan bulat bukan nilai floating point. light[,,]adalah lightmap untuk chunk.

    private void recursiveLight(int x, int y, int z, byte lightLevel)
    {
        Location loc = new Location(x + chunkx * 8, y, z + chunky * 8);
        if (world.getBlockAt(loc).BlockData.isSolid)
            return;
        lightLevel--;
        if (world.getLightAt(loc) >= lightLevel || lightLevel <= 0)
            return;
        if (y < 0 || y > 127 || x < -8 || x > 16 || z < -8 || z > 16)
            return;
        if (x >= 0 && x < 8 && z >= 0 && z < 8)
            light[x, y, z] = lightLevel;

        recursiveLight(x + 1, y, z, lightLevel);
        recursiveLight(x - 1, y, z, lightLevel);
        recursiveLight(x, y + 1, z, lightLevel);
        recursiveLight(x, y - 1, z, lightLevel);
        recursiveLight(x, y, z + 1, lightLevel);
        recursiveLight(x, y, z - 1, lightLevel);
    }

sumber
1
Ada sesuatu yang sangat salah jika Anda melakukan 2 juta blok per potongan - terutama karena hanya ada 8.192 blok sebenarnya dalam potongan 8 * 128 * 8. Apa yang bisa Anda lakukan sehingga Anda melewati setiap blok ~ 244 kali? (mungkinkah itu 255?)
doppelgreener
1
Matematika saya salah. Maaf: P. Berubah Tetapi alasan mengapa Anda harus pergi meskipun begitu banyak adalah Anda harus "keluar" dari setiap blok sampai Anda mencapai level cahaya yang lebih besar daripada yang Anda setting. Itu berarti setiap blok dapat ditimpa 5-10 kali sebelum mencapai tingkat cahaya aktual. 8x8x128x5 = banyak
2
Bagaimana Anda menyimpan Voxel Anda? Itu penting untuk mengurangi waktu traversal.
Samaursa
1
Bisakah Anda memposting algoritma pencahayaan Anda? (Anda bertanya apakah Anda melakukannya dengan buruk, kami tidak tahu)
doppelgreener
Saya menyimpannya dalam array "Blok", dan satu Blok terdiri dari enum untuk materi, ditambah byte metadata untuk penggunaan di masa mendatang.

Jawaban:

6
  1. Setiap cahaya memiliki posisi yang tepat (titik mengambang), dan bola pembatas didefinisikan oleh nilai radius cahaya skalar LR,.
  2. Setiap voxel memiliki posisi tepat (titik mengambang) di tengahnya, yang dapat Anda hitung dengan mudah dari posisinya di kisi.
  3. Jalankan melalui masing-masing dari 8192 voxels sekali saja, dan untuk masing-masing, lihat apakah itu termasuk dalam masing-masing volume pembatas bola lampu N dengan memeriksa |VP - LP| < LR, di mana VP adalah vektor posisi voxel relatif terhadap asal dan LPmerupakan vektor posisi cahaya relatif terhadap asal. Untuk setiap cahaya yang radius voxel saat ini ditemukan berada, naikkan faktor cahayanya dengan jarak dari pusat cahaya |VP - LP|,. Jika Anda menormalkan vektor itu dan kemudian mendapatkan besarnya, ini akan berada dalam kisaran 0,0-> 1,0. Level cahaya maksimum yang dapat dicapai voxel adalah 1.0.

Runtime adalah O(s^3 * n), di manas panjang sisi (128) dari wilayah voxel Anda dan nsejumlah sumber cahaya. Jika sumber cahaya Anda statis, ini tidak masalah. Jika sumber cahaya Anda bergerak secara real time, Anda dapat bekerja hanya pada delta daripada menghitung ulang seluruh shebang setiap pembaruan.

Anda bahkan bisa menyimpan voxels yang mempengaruhi setiap cahaya, sebagai referensi di dalam cahaya itu. Dengan cara ini, ketika lampu bergerak atau dihancurkan, Anda dapat melewati daftar itu, menyesuaikan nilai cahaya yang sesuai, daripada harus melintasi seluruh kotak kubik lagi.

Insinyur
sumber
Jika saya memahami algoritmanya dengan benar, ia mencoba melakukan semacam pseudo-radiosity, dengan membiarkan cahaya mencapai tempat-tempat yang jauh sekalipun itu berarti ia harus "berputar" ke beberapa sudut. Atau, dengan kata lain, algoritma pengisian banjir pada ruang "kosong" (non-padat) dengan jarak maks terbatas dari titik asal (sumber cahaya) dan jarak (dan darinya, redaman cahaya) dihitung sesuai dengan jalur terpendek ke titik asal. Jadi - tidak cukup apa yang Anda usulkan saat ini.
Martin Sojka
Terima kasih atas detailnya @MartinSojka. Yap terdengar lebih seperti isi banjir yang cerdas. Dengan segala upaya iluminasi global, biaya cenderung tinggi bahkan dengan optimisasi yang cerdas. Oleh karena itu, baik untuk mencoba masalah ini dalam 2D ​​terlebih dahulu, dan jika harganya mahal, ketahuilah bahwa Anda akan menghadapi tantangan yang pasti dalam 3D.
Insinyur
4

Minecraft sendiri tidak melakukan sinar matahari dengan cara ini.

Anda cukup mengisi sinar matahari dari atas ke bawah, setiap lapisan mengumpulkan cahaya dari tetangga voxels di lapisan sebelumnya dengan atenuasi. Sangat cepat - lintasan tunggal, tidak ada daftar, tidak ada struktur data, tidak ada rekursi.

Anda harus menambahkan obor dan lampu non-flooding lainnya di masa depan.

Ada begitu banyak cara lain untuk melakukan ini, termasuk propagasi cahaya directional mewah dll, tetapi mereka jelas lebih lambat dan Anda harus mencari tahu apakah Anda ingin berinvestasi dalam realisme tambahan mengingat hukuman tersebut.

Bjorn Wesen
sumber
Tunggu, jadi bagaimana tepatnya Minecraft melakukannya? Saya tidak bisa mendapatkan apa yang Anda katakan ... Apa artinya "setiap lapisan mengumpulkan cahaya dari voxels tetangga di lapisan sebelumnya dengan pelemahan" artinya?
2
Mulailah dengan lapisan paling atas (irisan dengan ketinggian konstan). Isi dengan sinar matahari. Lalu pergi ke layer di bawah ini, dan setiap voxel mendapatkan iluminasi dari voxel terdekat di layer sebelumnya (di atasnya). Masukkan nol cahaya dalam voxels padat. Anda memiliki beberapa cara untuk memutuskan "kernel", bobot kontribusi dari voxels di atas, Minecraft menggunakan nilai maksimum yang ditemukan, tetapi menguranginya dengan 1 jika propagasi tidak lurus ke bawah. Ini adalah pelemahan lateral, sehingga kolom vertikal voxel yang tidak diblokir akan mendapatkan perambatan sinar matahari penuh dan tikungan cahaya di sekitar sudut.
Bjorn Wesen
1
Harap dicatat bahwa metode ini sama sekali tidak didasarkan pada fisika nyata apa pun :) Masalah utama adalah bahwa Anda pada dasarnya mencoba memperkirakan cahaya non-directional (hamburan atmosfer) DAN memantulkan radiositas dengan heuristik sederhana. Terlihat bagus.
Bjorn Wesen
3
Bagaimana dengan "bibir" yang menggantung, bagaimana cahaya naik ke sana? Bagaimana cahaya bergerak ke arah atas? Ketika Anda hanya melakukan top-down, maka Anda tidak dapat kembali ke atas untuk mengisi overhang. Juga obor / sumber cahaya lainnya. Bagaimana Anda melakukan ini? (mereka hanya bisa turun!)
1
@Felheart: beberapa saat sekarang saya melihat ini, tetapi pada dasarnya ada tingkat cahaya sekitar minimum yang biasanya cukup untuk bagian bawah overhang sehingga mereka tidak sepenuhnya hitam. Ketika saya menerapkan ini sendiri, saya menambahkan pass kedua dari bawah, tetapi saya tidak benar-benar melihat peningkatan estetika yang besar dibandingkan dengan metode ambient. Obor / lampu sorot harus ditangani secara terpisah - saya pikir Anda dapat melihat pola propagasi yang digunakan dalam MC jika Anda meletakkan obor di tengah dinding dan bereksperimen sedikit. Dalam pengujian saya, saya menyebarkannya di bidang cahaya terpisah lalu menambahkan.
Bjorn Wesen
3

Seseorang berkata untuk menjawab pertanyaan Anda sendiri jika Anda menemukan jawabannya, jadi ya. Menemukan metode.

Apa yang saya lakukan adalah ini: Pertama, buat array boolean 3d dari "blok yang sudah diubah" overlay di atas chunk. Kemudian, isi sinar matahari, obor, dll (hanya menyalakan blok yang menyala, belum mengisi banjir). Jika Anda mengubah sesuatu, tekan "blok yang diubah" di lokasi itu menjadi true. Juga pergi dan mengubah setiap blok padat (dan karena itu tidak perlu menghitung pencahayaan untuk) menjadi "sudah berubah".

Sekarang untuk hal-hal yang berat: Pergilah ke seluruh bagian dengan 16 lintasan (untuk setiap level cahaya), dan jika 'sudah berubah' terus saja. Kemudian dapatkan level cahaya untuk blok di sekitar itu sendiri. Dapatkan level cahaya tertinggi dari mereka. Jika level lampu itu sama dengan level lampu yang dilewati saat ini, setel blok tempat Anda berada pada level saat ini, dan atur "sudah diubah" untuk lokasi tersebut menjadi true. Terus.

Saya tahu jenisnya rumit, saya mencoba menjelaskan yang terbaik. Tetapi fakta penting adalah, ia bekerja dan cepat.


sumber
2

Saya menyarankan algoritma yang menggabungkan solusi multi-pass Anda dengan metode rekursif asli, dan kemungkinan besar sedikit lebih cepat daripada salah satunya.

Anda akan membutuhkan 16 daftar (atau segala jenis koleksi) blok, satu untuk setiap level cahaya. (Sebenarnya, ada beberapa cara untuk mengoptimalkan algoritma ini untuk menggunakan daftar yang lebih sedikit, tetapi cara ini paling mudah untuk dijelaskan.)

Pertama, kosongkan daftar dan atur level cahaya semua blok ke nol, dan kemudian inisialisasi sumber cahaya seperti yang Anda lakukan dalam solusi Anda saat ini. Setelah (atau selama) itu, tambahkan blok dengan level cahaya yang tidak nol ke daftar yang sesuai.

Sekarang, buka daftar blok dengan level cahaya 16. Jika ada blok yang berdekatan dengan level lampu kurang dari 15, atur level cahayanya menjadi 15 dan tambahkan ke daftar yang sesuai. (Jika mereka sudah ada di daftar lain, Anda dapat menghapusnya dari daftar itu, tetapi tidak ada salahnya meskipun Anda tidak.)

Kemudian ulangi hal yang sama untuk semua daftar lainnya, dalam urutan kecerahan yang menurun. Jika Anda menemukan bahwa sebuah blok dalam daftar sudah memiliki tingkat cahaya yang lebih tinggi daripada seharusnya karena berada di daftar itu, Anda dapat mengasumsikan itu sudah diproses dan bahkan tidak perlu repot memeriksa tetangganya. (Kemudian lagi, mungkin lebih cepat hanya memeriksa tetangga - itu tergantung pada seberapa sering itu terjadi. Anda mungkin harus mencoba keduanya dan melihat mana yang lebih cepat.)

Anda mungkin mencatat bahwa saya belum menentukan bagaimana daftar harus disimpan; benar-benar hampir semua implementasi yang masuk akal harus melakukannya, selama memasukkan blok yang diberikan dan mengekstraksi blok yang sewenang-wenang keduanya operasi cepat. Daftar tertaut harus berfungsi, tetapi demikian juga implementasi setengah jalan array variabel yang layak juga. Cukup gunakan apa pun yang terbaik untuk Anda.


Tambahan: Jika sebagian besar lampu Anda tidak terlalu sering bergerak (dan tidak juga dinding), mungkin lebih cepat untuk menyimpan, untuk setiap blok yang menyala, sebuah penunjuk ke sumber cahaya yang menentukan tingkat cahayanya (atau ke salah satu dari mereka, jika beberapa diikat). Dengan begitu, Anda dapat menghindari pembaruan pencahayaan global hampir seluruhnya: jika sumber cahaya baru ditambahkan (atau yang sudah terang), Anda hanya perlu melakukan satu pas pencahayaan rekursif tunggal untuk blok di sekitarnya, sementara jika ada yang dihapus (atau redup), Anda hanya perlu memperbarui blok yang mengarah ke sana.

Anda bahkan dapat menangani perubahan dinding dengan cara ini: ketika sebuah dinding dilepas, cukup mulai lintasan penerangan rekursif baru di blok itu; ketika ditambahkan, lakukan recalc pencahayaan untuk semua blok yang mengarah ke sumber cahaya yang sama dengan blok yang baru saja di dinding.

(Jika beberapa perubahan pencahayaan terjadi sekaligus - mis. Jika lampu dipindahkan, yang dianggap sebagai penghapusan dan tambahan - Anda harus menggabungkan pembaruan menjadi satu, menggunakan algoritma di atas. Pada dasarnya, Anda nol tingkat cahaya semua blok yang menunjuk ke sumber cahaya yang dihapus, tambahkan blok yang menyala di sekelilingnya serta sumber cahaya baru (atau sumber cahaya yang ada di area yang dihilangkan) ke daftar yang sesuai, dan jalankan pembaruan seperti di atas.)

Ilmari Karonen
sumber