Saya telah memikirkan masalah ini. Apakah mungkin dengan teknologi saat ini untuk membuat replika bumi 1: 1 di game berbasis voxel? Apa struktur data terbaik untuk menyimpan peta raksasa ini? Algoritme mana yang harus digunakan untuk membuat struktur data ini secara waktu nyata?
Pertanyaan-pertanyaan ini membuat asumsi ini:
Setiap voxel memiliki resolusi 1 meter kubik.
Demi kesederhanaan, setiap voxel hanya membutuhkan 1 byte informasi metadata. Informasi ini akan digunakan untuk menyimpan identifikasi "tipe" voxel (tanah, air, batu, dll).
Volume bumi adalah 1 * 10ˆ21 meter kubik.
Dengan "teknologi saat ini" Saya memasukkan apa pun yang tersedia secara komersial, tetapi tidak untuk komputer super.
Hanya topografi dan batimetri Bumi yang akan digunakan untuk menghasilkan peta. Bangunan manusia, tanaman atau gua tidak termasuk. Blok bawah tanah akan dipilih berdasarkan studi geologi misalnya: jika kedalaman lebih besar dari 3000 km membuat voxel 'magma'.
Sama seperti di Minecraft, petanya tidak statis, bisa dimodifikasi dalam gim.
Jarak imbang 'tak terbatas' adalah nilai tambah yang besar, apa gunanya memiliki seluruh bumi di peta jika Anda tidak bisa terbang dan menonton seluruh planet?
Kesimpulan pertama yang saya datang ketika saya memikirkan masalah ini adalah bahwa menyimpan data Bumi secara linear tidak layak, dengan asumsi bahwa setiap voxel hanya menempati 1 byte memori, ini masih memerlukan 1 zettabyte untuk menyimpan peta. Jadi diperlukan semacam kompresi.
Saya berpikir bahwa sebuah voxel octree dapat memampatkan peta, tetapi saya tidak yakin seberapa banyak. Entropi peta voxel ini mungkin sangat rendah, jadi saya kira tingkat kompresi yang sangat tinggi dapat dicapai.
Penolakan
Ini adalah pertanyaan teoretis, saya tidak punya niat untuk menulis bumi voxel
EDIT
ESA GOCE telah memetakan geoid Bumi dengan presisi 1cm-2cm. Saya percaya bahwa informasi ini dapat digunakan untuk menghasilkan peta ketinggian Bumi yang sangat tepat. Ini akan mengecualikan kebutuhan untuk menggunakan algoritma untuk mengisi celah dalam topografi Bumi.
sumber
Jawaban:
Itu tergantung pada metode pembagian ruang yang Anda gunakan, meskipun semua metode pembagian (seperti metode kompresi apa pun) akhirnya berjalan di mana tidak ada kompresi lebih lanjut dapat terjadi, karena overhead struktur data dan faktor logis / matematika lainnya. Contohnya dapat ditemukan di octrees. Untuk setiap node dalam octree, pointer harus disimpan untuk orang tua dan / atau anak-anak (tergantung pada bagaimana Anda pergi tentang arsitektur struktur data Anda), untuk memungkinkan traversal yang bermakna. Setiap struktur pohon dapat berisi n anak-anak. Semakin rendah rasio 1: n, semakin efisien penggunaan ruang yang Anda peroleh, dan akibatnya semakin besar overhead dalam traversal pohon karena Anda harus memiliki lebih banyak node leluhur yang mengandung jumlah voxel daun yang sama (dalam kasus Anda, sekitar 510 triliun ini mewakili area permukaan).
Mempertimbangkan bahwa dalam contoh Anda, masalah utama adalah biaya penyimpanan dan membuat seluruh planet (atau bagiannya) dari jarak yang adil, tidak ada struktur data yang saya sarankan lebih dari satu Oktober. Pemetaan adalah suatu keharusan: diameter 12,8 juta meter pada daya terdekat 2 tertinggi adalah 2 ^ 24 = 16,8 juta. Level 24 octree untuk dilalui akan berjumlah sejumlah besar percabangan - sangat mahal untuk GPU dan CPU. Tetapi jika Anda melakukan hal-hal yang benar, Anda hanya perlu melintasi beberapa level pada satu waktu. Namun, mengingat jumlah ruang yang dibutuhkan, alternatifnya sedikit dan jarang (lihat di bawah).
Kemampuan pemetaan oktaf adalah apa yang membuatnya menjadi alat yang sangat kuat untuk volume besar seperti yang Anda gambarkan. Tidak seperti semua metode pembagian lainnya yang diketahui (dengan pengecualian KD-tree), octree membuat pembagian tetap minimal, artinya perbedaan visual dan fisik antara tingkat mipmap juga dijaga tetap minimal, yang berarti banyak delta yang lebih halus dalam granularitas saat Anda berjalan dan turun pohon.
Jika, di sisi lain, Anda ingin menghasilkan dunia di mana traversal kisi hierarkis dijaga seminimal mungkin, maka Anda perlu menukar ruang untuk menambah kecepatan.
Berbicara tentang rasio 1: n yang ideal, tidak ada struktur yang lebih baik daripada kd-tree dalam hal ini. Di mana octree terbagi menjadi 2 untuk setiap sumbu, menghasilkan 2 ^ 3 = 8 sel anak individual, pohon kd membelah tepat satu kali per tingkat pembagian. Masalahnya adalah Anda harus memilih hyperplane untuk dibelah, dan hyperplane ini dapat dipilih di sekitar salah satu dari 3 sumbu. Meskipun optimal dalam hal ruang, itu membuat traversal 3D (seperti selama raymarch, operasi fundamental ketika menggunakan octrees untuk fisika atau rendering) jauh lebih sulit daripada dalam satu octree, karena struktur tipe portal yang dinamis harus disimpan untuk merekam antarmuka antara masing-masing node kd-tree.
RLE adalah pendekatan lain untuk kompresi, tetapi dalam banyak hal lebih sulit untuk diterapkan pada masalah seperti ini (di mana basis operasi berbentuk bola), karena kompresi RLE adalah satu dimensi, dan Anda harus memilih sumbu tempat operasinya. Untuk planet, seseorang mungkin memilih sumbu kutub, tetapi setiap pilihan sumbu tunggal akan memperkenalkan masalah tertentu dengan traversal untuk rendering dan fisika ketika bertindak dari sudut-sudut tertentu yang tidak optimal. Tentu saja, Anda juga dapat menjalankan RLE dalam 3 sumbu secara bersamaan, tiga kali lipat biaya penyimpanan, atau dalam 6 sumbu (-x, + x, -y, + y, -z, + z) sebagai optimasi lebih lanjut.
Jadi untuk menjawab pertanyaan Anda (atau tidak!)
Saya tidak akan langsung menjawab apa jenis perangkat kerasnya, tetapi saya pikir melihatnya dari sudut pandang oktree mulai memberi Anda gambaran tentang apa yang sebenarnya mungkin terjadi pada perangkat keras jenis apa. Saya akan mendorong Anda untuk turun rute ini, jika Anda benar-benar ingin tahu, mungkin paling mudah untuk benar-benar menerapkan octree jarang sederhana(lihat kertas Laine di referensi) dan letakkan cangkang bulat berisi voxel permukaan ke dalamnya, dan lihat seperti apa penggunaan ruang yang dihasilkan. Melangkah dari sana. Lihat seberapa jauh Anda bisa mendapatkan sebelum memori sistem Anda mulai memberi. Ini tidak mengharuskan Anda untuk menulis renderer kecuali Anda ingin visualisasi. Juga ingat bahwa ini paling baik dilakukan pada CPU - GPU pada umumnya tidak memiliki kapasitas memori untuk menangani masalah skala ini. Ini adalah salah satu alasan Intel melihat bergerak ke arah prosesor paralel masif: manfaat GPGPU, yang lebih baik dalam hal semacam ini, dapat diterapkan pada ruang memori yang jauh lebih luas tanpa hambatan sistem bus untuk bersaing. Mungkin ada orang lain di sini, atau di mathem.stackexchange.com,
Dalam hal persyaratan jarak pandang tak terbatas Anda, tentu saja, tetapi pertanyaannya selalu sampai pada, "berapa banyak detail pada jarak berapa". Memberikan detail tanpa batas akan membutuhkan sumber daya yang tak terbatas. Di situlah pemetaan variabel-per-adegan ikut berperan. Juga ingat bahwa semua struktur data mewujudkan pertukaran kecepatan untuk ruang atau sebaliknya. Itu berarti rendering lebih sedikit / lebih lambat, jika Anda menginginkan dunia yang lebih besar untuk jumlah upaya rekayasa yang sama.
sumber
Karena Anda kemungkinan besar tidak akan pernah mengetahui sifat-sifat setiap meter kubik dunia nyata, Anda akan memerlukan beberapa cara untuk menghasilkan data yang tidak pasti berdasarkan asumsi. Jadi jika Anda sudah menemukan jawabannya, tidak perlu menghitung dan menyimpan semua data itu, tetapi Anda bisa membuatnya dengan cepat.
Pertama dan terpenting Anda dapat membuang semua voxel di dalam bumi, karena ini hanya harus dihitung jika seseorang benar-benar menggali lubang, misalnya. voxels menjadi terlihat.
Untuk permukaan bumi, saya mungkin akan mengambil gambar sebagai titik awal untuk perhitungan saya. Mungkin semacam peta suhu dan kelembaban akan memungkinkan Anda untuk menghitung jenis blok yang akan diterapkan. Misalnya. Air, pasir (gurun), rumput, salju dll. Karena gambar mungkin tidak memiliki satu piksel informasi untuk setiap meter persegi permukaan bumi, Anda harus mencampur ini dengan beberapa suara untuk menghasilkan sedikit variasi pada permukaan. Jika Anda selalu menggunakan benih acak yang sama, hasil Anda harus tetap deterministik.
Selain itu, peta ketinggian akan berguna, sehingga Anda dapat menentukan ketinggian fitur permukaan. Dengan begitu Anda dapat menambahkan gunung dll.
Jadi ini bermuara pada data-volume beberapa gambar 2D yang berisi informasi tentang permukaan bumi. Untuk semua yang ada di dalam, Anda akan kembali ke pendekatan prosedural murni, di mana Anda merender berbagai jenis blok, tergantung pada jarak dari pusat bumi. Tetapi seperti yang dikatakan di atas, ini harus dihitung hanya, ketika seseorang menggali lubang.
Untuk membuat perubahan terus-menerus, saya hanya akan menyimpan modifikasi ke dunia. Jadi, jika seseorang menggali lubang, saya akan menyimpan informasi tentang voxel mana yang telah dihapus, karena saya harus dapat membuat voxels sekitarnya secara prosedural.
Adapun rendering: Anda akan memerlukan beberapa algoritma level-of-detail dan culling canggih untuk membuat ini bekerja. Adalah konyol untuk membuat semua voxel permukaan, ketika kamera berada pada level zoom yang menunjukkan seluruh dunia. Pada level ini, voxel seharusnya jauh lebih besar, bahkan mungkin bola bertekstur sederhana sudah cukup.
Saya kira hal yang paling sulit adalah memiliki generator solid yang memungkinkan Anda menghitung properti voxel, bahkan untuk "resolusi" yang berbeda, sehingga Anda dapat menggunakannya untuk menghasilkan tingkat detail yang berbeda.
sumber
Anda pada dasarnya dapat melakukan hal yang sama seperti yang dilakukan Minecraft. Daripada membuat jumlah data yang demikian, Anda dapat mendefinisikan dunia sebagai rumus matematika, setiap kali sepotong data diperlukan untuk tampilan, Anda menghasilkannya menggunakan rumus.
Formula semacam itu biasanya dibangun dengan menggunakan konsep Perlin noise , ini memungkinkan perincian di semua tingkatan, Anda dapat memiliki rentang gunung sebesar yang ada di dunia nyata, namun memilih untuk hanya menghasilkan sebagian kecil darinya. Anda dapat menghasilkan jumlah detail yang Anda sukai, sehingga dimungkinkan untuk membuat detail yang sangat bagus untuk barang-barang dekat, namun juga menghasilkan pemandangan yang jauh di tingkat detail yang diperlukan.
Minecraft menyimpan semua blok yang telah Anda kunjungi, lengkap dengan perubahan apa pun yang telah dibuat, orang hanya bisa menyimpan perbedaan antara dunia yang dihasilkan dan dunia yang diperbarui, tapi saya kira menyimpan blok besar lebih mudah, dan mereka melakukan kompres yang relatif baik.
Saya tidak berpikir ada permainan yang benar-benar membutuhkan ini, tetapi sangat umum untuk menggunakan generasi formula dari semua detail "tidak penting" dari dunia game besar. Saya tidak yakin seberapa umum menghasilkan ketika diperlukan pendekatan, sebagai lawan hanya menghasilkan banyak dan meletakkannya di disk.
sumber
Anda bisa mencari data vektor dari daratan Bumi, karena data vektor memiliki keuntungan penskalaan ke skala apa pun yang Anda inginkan. Gabungkan dengan peta ketinggian Bumi untuk menghasilkan ketinggian medan. Langkah terakhir adalah beberapa citra satelit terperinci, dari mana Anda dapat memilih jenis blok atas berdasarkan gambar, sehingga Anda mendapatkan batu di mana ada batu, pasir di mana ada pasir, dll. Bagian dalam planet yang sebenarnya mungkin harus dihasilkan seperti Minecraft yang melakukannya, kecuali Anda dapat menemukan data geografis yang detail untuk bekerja. Pada dasarnya, yang ingin Anda lakukan adalah menemukan data geografis, dan memperkirakannya, hanya diberi input koordinat XYZ. Ini berarti Anda memiliki data yang terbatas, dan Anda memperkirakan yang lain setepat mungkin.
sumber