Struktur data mana yang harus digunakan untuk mewakili medan voxel?

18

Menurut halaman Wikipedia tentang voxels, "[...] posisi voxel disimpulkan berdasarkan posisinya relatif terhadap voxel lain (yaitu posisinya dalam struktur data yang membentuk satu gambar volumetrik tunggal)."

Bagaimana seharusnya seseorang menerapkan struktur data seperti itu? Saya sedang berpikir tentang sebuah octree tetapi saya bertanya-tanya apakah ada hal lain yang tidak pernah saya dengar.

pwny
sumber
1
Ini adalah pertanyaan yang agak sulit untuk ditanyakan karena sangat tergantung pada data apa yang akan dibutuhkan oleh data voxel Anda. Hal-hal seperti seberapa penuh voxel itu, seperti apa bentuknya, dll akan sangat tergantung pada apa yang Anda lakukan. Kedua, struktur data harus memberikan akses kecepatan tinggi untuk manipulasi data real-time dan pembaruan selanjutnya. Bagaimana menjaga agar struktur memori tetap rendah per voxel dan akses cepat / manipulasi data cukup banyak merupakan tantangan teknis utama yang niat cukup spesifik saat bekerja dengan mesin voxel. Bukan jawaban, begitu komentar.
James

Jawaban:

14

Pertama. Mari kita menulis apa yang kita ketahui tentang setiap voxel:

voxel = (x, y, z, color) // or some other information

Penyimpanan umum

Secara umum adalah ini:

set of voxels = set of (x,y,z, color)

Perhatikan, triplet itu (x, y, z) mengidentifikasi masing-masing voxel secara unik, karena voxel adalah titik dalam ruang dan tidak ada cara dua titik menempati satu tempat (saya percaya kita berbicara tentang data voxel statis).

Itu harus baik untuk data sederhana. Tetapi ini bukan struktur data yang cepat.

Rendering adalah AFAIK yang dilakukan oleh algoritma scanline. Artikel Hardware Tom tentang voxels memiliki gambar algoritma scanline .

Pencarian cepat

Jika pencarian cepat diperlukan, maka struktur data tercepat untuk pencarian adalah hash (alias array, map ...). Jadi, Anda harus membuat hash dari itu. Jadi, secara naif kami hanya menginginkan cara tercepat untuk mendapatkan elemen arbitrer:

array [x][y][z] of (color)
  • Ini memiliki O (1) untuk mencari voxel dengan koordinat x, y, z.

  • Masalahnya adalah, bahwa persyaratan ruangnya adalah O (D ^ 3), di mana D adalah kisaran dari masing-masing angka x, y dan z (lupakan bilangan real, karena jika mereka Chars, yang memiliki kisaran nilai 256, akan ada 256 ^ 3 = 2 ^ 24 == 16 777 216 elemen dalam array).

Tapi itu tergantung pada apa yang ingin Anda lakukan dengan voxels. Jika rendering adalah apa yang Anda inginkan, mungkin array inilah yang Anda inginkan. Namun masalah penyimpanan masih tetap ...

Jika penyimpanan adalah masalahnya

Salah satu metode adalah dengan menggunakan kompresi RLE dalam array. Bayangkan sepotong voxels (himpunan voxels, di mana voxel memiliki satu nilai konstan koordinat .... seperti bidang di mana z = 13 misalnya). Seperti sepotong voxels akan tampak seperti beberapa gambar sederhana di MSPaint . Model Voxel, saya katakan, biasanya menempati sebagian kecil dari semua tempat yang memungkinkan (ruang D ^ 3 dari semua voxel yang mungkin). Saya percaya, bahwa "mengambil sepasang dari triplet koordinat dan mengompresi sumbu yang tersisa" akan melakukan trik (misalnya, ambil [x] [y] dan untuk setiap elemen kompres semua voxels pada sumbu z pada x yang diberikan, y .. harus ada 0 hingga beberapa elemen, RLE akan baik-baik saja di sini):

array [x][y] of RLE compressed z "lines" of voxel; each uncompressed voxel has color 

Metode lain untuk memecahkan masalah penyimpanan adalah alih-alih array menggunakan struktur data tree:

tree data structure  = recursively classified voxels
for octrees: recursively classified by which octant does voxel at (x,y,z) belong to
  • Oktree, seperti yang disebutkan oleh Nick. Seharusnya mengompres voxel. Octree bahkan memiliki kecepatan yang layak untuk pencarian, saya kira itu adalah beberapa O (log N), di mana N adalah jumlah voxels.
  • Oktree harus dapat menyimpan data voxel yang sewenang-wenang.

Jika voxel adalah beberapa peta ketinggian sederhana, Anda mungkin menyimpannya. Atau Anda dapat menyimpan parameter berfungsi yang menghasilkan peta ketinggian, alias secara prosedural menghasilkannya ...

Dan tentu saja Anda dapat menggabungkan semua pendekatan yang mungkin. Tapi jangan berlebihan, kecuali Anda menguji bahwa kode Anda berfungsi dan mengukur bahwa itu BENAR-BENAR lebih cepat (jadi itu layak optimasi).

TL; DR

Selain dari Octrees adalah kompresi RLE dengan voxels, google "voxlap", "ken silverman" ...

Sumber daya

Ada daftar sumber daya dan diskusi tentang cara membuat roxer voxel cepat, termasuk makalah dan kode sumber .

pengguna712092
sumber
1
"Jika penyimpanan adalah masalahnya": Anda juga dapat menggunakan VTC ( oss.sgi.com/projects/ogl-sample/registry/NV/… ) atau kompresi
DXT
@Inddragon terima kasih atas informasi ini. :) Itu ide yang sangat bagus.
user712092
Tautan sumber daya sedang rusak.
Ezequiel
4

Ada dua aspek struktur data yang berbeda yang mungkin mereka bicarakan.

Struktur susunan

Ketika Anda mereferensikan elemen array dari sejumlah dimensi, pertimbangkan bahwa array itu sendiri, setelah Anda melewati indeks (mis. myArray[4][6][15]) Tahu apa yang ada di lokasi itu. Jika apa yang ada di lokasi itu adalah voxel, voxel itu tidak perlu merekam koordinat x, y, dan z miliknya - array yang memegang voxel menentukan lokasi dunia itu secara implisit berdasarkan lokasi yang diindeks array.

Alasan ini baik adalah karena aritmatika pointer yang digunakan untuk akses array semacam ini secara inheren cepat dan secara umum, menyediakan fondasi untuk sebagian besar array cepat (sering disebut "asli") yang ditemukan dalam berbagai bahasa. Kelemahan dari array ini adalah bahwa mereka harus memiliki elemen dengan ukuran yang sama dalam byte, agar aritmatika pointer tersebut berlaku.

Oktaf

(Saya perhatikan detik ini, karena ini lebih kecil kemungkinannya untuk apa yang dimaksud wikipedia, dan implementasi voxel tidak memerlukan penggunaan oktri walaupun hampir semua yang modern menggunakan oktober.)

Simpul root octree adalah kubus tunggal yang tidak terbagi. Mari kita berikan contoh. Katakanlah akar octree Anda, pusat kubus, berada di {0, 0, 0}dalam ruang 3D. Setelah Anda mulai menempatkan objek di dalam ruang tersebut (baca: lebih dari satu objek), sekarang saatnya untuk membagi lebih lanjut octree. Di sinilah Anda membaginya menjadi 8 ( Oktober- ), dengan mengirisnya menggunakan 3 pesawat, pesawat ini menjadi pesawat xy, xz dan yz. Kubus asli Anda sekarang persis mengandung 8 kubus yang lebih kecil. Setiap sub-node ini diposisikan sebagai offset dari cube induk . Yaitu, bahwa misalnya, kubus yang terletak di oktan xyz positif akan memiliki offset dari induk / pusat kubus yang mengandung persis{root.width / 4, root.height / 4, root.depth / 4}. Daripada menentukan posisi absolut untuk setiap subnode, lebih masuk akal untuk mempertimbangkan simpul induk sebagai asal dari ruang anak-anaknya. Ini adalah cara kerja grafik adegan yang sama.

Cukup sederhana untuk melihat ini dalam gambar 2D, di mana Anda menggambar kotak, dan membaginya menjadi 4 wilayah yang sama. Jika, seperti simpul akar octree kami, pusat dari kuadrat induk dianggap {0, 0}, maka 4 pusat dari kotak anak akan

{root.width / 4, root.height / 4}, {-root.width / 4, root.height / 4}, {root.width / 4, -root.height / 4}, {-root.width / 4, -root.height / 4}

... Sebagai relatif terhadap orang tua mereka - prinsip yang sama seperti dalam 3D.

Insinyur
sumber
Terima kasih atas jawaban Anda. Dalam kasus saya, beberapa bagian besar dari medan akan dibuat dari jenis voxel yang sama, itulah sebabnya saya berpikir tentang octrees (sepotong besar tidak harus dibagi lagi). Namun, saya akan memberikan bidikan 3D array karena terlihat lebih mudah diimplementasikan. Saya yakin saya dapat mengatur untuk mengabstraksi detail implementasi dari kelas terrain saya sehingga tidak terlalu sulit untuk beralih implementasi jika diperlukan.
pwny
Sama-sama. Saya pasti akan menyarankan melihat ke oktober, benar-benar mereka tidak sulit untuk dipahami. Tapi ya, pendekatan Anda masuk akal untuk saat ini, tentu ada baiknya melakukan prototipe awal menggunakan array 3D.
Insinyur
Sebagai bacaan lebih lanjut, diskusi yang baik tentang implementasi oktri termasuk beberapa referensi yang berguna dapat ditemukan di artikel Intel Memperluas STL untuk Game .
Martin Foot
1

Anda bisa menggunakan RLE. Tetapi Anda dapat menggunakan SVO (Sparse Voxel Octree), id Tech 6 menggunakan SVO. SVO adalah teknik rendering grafik komputer 3D menggunakan raycasting atau kadang-kadang pendekatan ray tracing ke representasi data octree.

Tekniknya agak bervariasi, tetapi umumnya bergantung pada menghasilkan dan memproses lambung titik (voksel jarang) yang terlihat atau mungkin terlihat, mengingat resolusi dan ukuran layar.

Gunakan raycasting, karena lebih cepat.

RealTimeGraph9999
sumber
0

Secara umum Anda dapat menghindari struktur data 3D untuk medan. Anda dapat menggunakan peta ketinggian sebagai gantinya. Ini bisa sangat murah dan efisien dioksidasi saat runtime. Biasanya membayar (dalam pengalaman saya) untuk melacak ketinggian minimum yang Anda perlu render di setiap kolom dan juga kadang-kadang mulai-stop-top sudut sehingga Anda dapat menyisihkan kolom backface juga.

Inilah yang saya buat sejak lama: http://sites.google.com/site/williamedwardscoder/spinning-voxels-in-flash

Jika medan Anda memiliki sedikit overhang atau gua atau fitur lain yang tidak dapat diwakili oleh peta ketinggian, maka Anda dapat memiliki lubang di peta tinggi Anda dan memiliki representasi alternatif misalnya objek voxel 3D sejati yang mengisi hanya tempat-tempat yang dilokalkan di mana biaya runtime dijamin.

Representasi voxel yang jarang sangat berguna saat Anda memiliki dunia voxel sejati yang besar. John Carmack telah berbicara dengan mereka selama beberapa tahun terakhir sekarang ...

Akan
sumber
Saya juga memikirkan ketinggian, tetapi beberapa hal membuat saya menjauh darinya. Masalahnya adalah bahwa dalam kasus saya, medannya tidak benar-benar besar dengan cara apa pun atau sangat rumit (bayangkan medan jenis labirin, sangat cartesian). Saya juga ingin bagian medan dapat dirusak atau memungkinkan pengguna memengaruhi medan melalui konstruksi. Hal ini dapat mengakibatkan pemain membuat "terowongan" di medan yang tampaknya lebih rumit untuk diwakili dengan peta ketinggian.
pwny