Apa solusi struktur data yang baik untuk manajer adegan di XNA?

8

Saya bermain dengan XNA untuk proyek game saya sendiri, saya sebelumnya pernah melihat OpenGL dan bekerja sedikit dengan Ogre, jadi saya mencoba untuk mendapatkan konsep yang sama bekerja pada XNA.

Secara khusus saya mencoba untuk menambahkan ke XNA seorang manajer adegan untuk menangani transformasi hierarkis, frustum (mungkin bahkan oklusi) pemusnahan dan penyortiran objek transparansi.

Rencana saya adalah membangun pengelola adegan pohon untuk menangani transformasi dan pencahayaan hierarkis, dan kemudian menggunakan Oktree untuk pemusnahan dan pemilahan objek. Masalahnya adalah bagaimana melakukan penyortiran geometri untuk mendukung transparansi dengan benar. Saya tahu bahwa penyortiran sangat mahal jika dilakukan berdasarkan per-poligon, sangat mahal sehingga bahkan tidak dikelola oleh Ogre. Tapi gambar dari Ogre masih terlihat benar.

Adakah ide tentang bagaimana melakukannya dan struktur data mana yang digunakan dan kemampuan mereka? Saya tahu orang-orang di sekitarnya menggunakan:

  • Oktaf
  • Kd-tree (seseorang di forum GameDev mengatakan bahwa ini jauh lebih baik daripada Octrees)
  • BSP (yang seharusnya menangani pemesanan per-poligon tetapi sangat mahal)
  • BVH (tetapi hanya untuk pemusnahan frustum dan oklusi)

Terima kasih

Tunnuz

performance graphics-programming tunnuz
sumber

Jawaban:

6

Octtrees (atau bahkan hanya quadtrees) dan Kd-tree adalah skema partisi spasial untuk keperluan umum yang baik, dan jika pipa saluran dan / atau mesin Anda menghasilkannya, maka Anda akan menemukan mereka berguna dalam segala macam cara untuk mengoptimalkan kueri / iterasi. Mereka bekerja dengan membagi volume tetap dengan cara hierarkis, yang membuat kueri seperti raycasting ke ruang objek Anda sangat murah untuk dicari (bagus untuk pemeriksaan tabrakan).

Bounding Volume Hierarchies bekerja dengan cara yang sedikit berbeda (mereka mengagregasi volume objek di pohon daripada membagi ruang), dan merupakan cara sederhana untuk memotong hal-hal yang tidak perlu agar tidak diulangi. Tetapi karena BVH tidak membatasi bagaimana dua node saudara terkait, itu bukan skema yang baik untuk mencari tahu urutan rendering, atau untuk pertanyaan tabrakan sewenang-wenang.

Sistem BSP bagus ketika Anda membagi dunia berdasarkan poligon individu, tetapi untuk objek yang lebih besar pendekatan berbasis volume lebih masuk akal.

Di atas semua itu, perlu dicatat bahwa tidak satu pun dari sistem ini yang sempurna untuk menentukan urutan render untuk transparansi, bahkan pendekatan BSP. Akan selalu memungkinkan untuk membuat geometri yang merusak algoritma Anda, kecuali jika Anda dapat membagi poligon dengan cepat. Apa yang kemungkinan besar Anda cari adalah solusi 'usaha terbaik', di mana geometri dapat dipesan dengan benar di sebagian besar kasus; dan tim seni dapat membagi model untuk kasus-kasus yang tidak berfungsi (karena model / poligon berukuran besar, panjang, atau berpotongan sendiri). Model / node yang lebih kecil selalu jauh lebih mudah untuk mengurutkan 'dengan benar', tetapi Anda membayar untuk itu dalam hal iterasi.

Kd-tree dan Oct / quad-tree keduanya merupakan solusi tujuan umum yang baik, untuk itu implementasi platform yang ramah dapat ditulis, tetapi pada akhirnya Anda harus menyeimbangkan kedalaman / kompleksitas pohon partisi spasial Anda dengan biaya iterasi, dan overhead per model (yaitu biaya panggilan draw). Jika Anda menargetkan XNA, saya sarankan Anda tetap sederhana dan tingkat tinggi, dan jika ada masalah pengurutan dengan beberapa konten, maka sangat mempertimbangkan untuk mengubah konten sebelum mencoba meningkatkan mesin Anda sampai dapat mengatasinya; pengembalian berkurang dengan sangat cepat setelah penyortiran render paling dasar diimplementasikan.

MrCranky
sumber
Saya telah membaca bahwa bahkan teknik Mengupas Kedalaman untuk menangani penyortiran per-fragmen sering mendapatkan hasil yang baik. Apakah Anda pikir ini layak untuk mesin game kecil? Apakah game AAA menggunakan teknik ini?
tunnuz
Menurut Anda apa yang lebih baik / lebih mudah untuk diterapkan antara Kd-tree dan Octrees?
tunnuz
Saya akan sangat terkejut jika tidak ada implementasi C # untuk mereka berdua yang sudah ada di luar sana: itu adalah jenis dagingnya (pembagian dan permintaan) yang sama untuk semua implementasi, tetapi bit yang menarik (bagaimana Anda mengulangi / meminta / mengaitkan item dengan node) dapat bervariasi. Okt / quad-tree, menurut saya, secara konsep lebih sederhana, tetapi seperti yang telah ditunjukkan, pohon kd lebih efisien dalam berbagai cara. Saya mungkin pergi kd-tree hanya karena jika Anda bisa melakukan itu, Anda dapat melakukan oct-tree (tetapi sebaliknya tidak selalu benar).
MrCranky
1
Adapun penyortiran per-fragmen: tanpa mengetahui apa-apa tentang mesin Anda sulit untuk mengatakan, tapi rasanya seperti sedikit optimasi prematur. Ya, game AAA mungkin menggunakan teknik-teknik itu, tetapi mereka juga akan mengocok lebih banyak objek daripada yang bisa dikelola oleh mesin XNA, sehingga membutuhkan teknik pengoptimalan yang lebih ekstrem untuk memaksimalkannya. Saran saya akan selalu menyelesaikan dasar-dasar (penyortiran transparansi) dengan solid, dan jika Anda menemukan bahwa kinerja tidak sesuai dengan yang diinginkan, maka pergilah seluruh babi dan lakukan penyortiran berbutir halus. Peluang adalah hal lain yang akan mengikat kinerja terlebih dahulu.
MrCranky
1
Sebenarnya ada AAA-pengembang di luar sana yang melompat menggunakan BV-tree's sejak melakukannya dengan kasar sambil memastikan bahwa Anda benar-benar menggunakan sebagian besar sepeda motor secara efisien (No LHS / L2 + L1 Cache misses dll) memberikan kinerja yang cukup baik. Sungguh menakjubkan berapa banyak tes yang dapat Anda lakukan dengan sistem yang dirancang dengan baik.
Simon
3

McCranky membahas dengan luar biasa semua struktur data yang Anda sebutkan, namun saya melihat Anda belum mempertimbangkan R-Trees. Tubuh pengetahuan tentang struktur itu sangat besar, dan mereka sangat cocok untuk pertanyaan rentang spasial (sebagian besar pekerjaan telah dilakukan oleh para ahli teori dan praktisi basis data) dalam 30 tahun terakhir. Baru-baru ini Sebastian Sylvain dari Rare telah memberikan kursus tentang GDC tentang mengapa mereka bekerja untuk gim juga (khususnya pada konsol dengan prosesor berurutan). Anda dapat mempelajari lebih lanjut dari pdf-nya: http://www.gdcvault.com/play/1012452/R-Trees-Adapting-out-of

Implementasi yang naif dan sederhana cukup mudah, dan struktur dasar memberi Anda banyak ruang untuk perbaikan (manajemen heuristik pemisahan yang lebih baik, pengambilan peluang awal, pencarian paralel, dll).

Ksatria Merah
sumber
2

Jawabannya sangat tergantung pada jumlah model yang Anda rencanakan untuk digunakan. Saya belum benar-benar bekerja dengan hal-hal semacam ini untuk XNA, tetapi jika Anda menggunakan AABB untuk tes dan tidak memiliki terlalu banyak model Anda mungkin cukup baik dengan uji brute force. Mungkin bahkan membuangnya di utas. Saya tidak yakin bagaimana / jika ada optimasi SSE / VMX yang dapat digunakan untuk C # tetapi jika Anda berhasil mendapatkan AABB secara linear dalam memori (sehingga Anda tidak mendapatkan cache-misses untuk CPU), Anda harus dapat untuk mendorong melalui sejumlah besar tes dalam waktu yang sangat sedikit.

Simon
sumber