Sunting: Ini hanya untuk pengalaman belajar saya sendiri, BUKAN untuk alasan kinerja saya mengajukan pertanyaan ini.
Ini terkait dengan mesin medan mirip Minecraft. Saya menyimpan blok dalam potongan (16x256x16 blok dalam satu potongan). Ketika saya menghasilkan bongkahan, saya menggunakan beberapa teknik prosedural untuk mengatur medan dan menempatkan objek. Saat menghasilkan, saya menyimpan satu array 1D untuk potongan penuh (solid atau tidak) dan array 1D yang terpisah dari blok padat.
Setelah generasi, saya beralih melalui blok padat memeriksa tetangga mereka jadi saya hanya menghasilkan wajah blok yang tidak memiliki tetangga yang solid. Saya menyimpan wajah mana yang akan dibuat dalam daftar mereka sendiri (itu adalah 6 daftar, satu wajah yang mungkin / normal). Saat merender sepotong, saya merender semua daftar dalam potongan kamera saat ini dan hanya daftar yang menghadap kamera dalam semua potongan lainnya. Saya melakukan ini dengan menyimpan semua 6 daftar dalam satu buffer, maka saya cukup mengubah rentang yang saya gambar.
Menggunakan 2D atlas dengan ini trik shader sedikit Andrew Russell menyarankan, saya ingin menggabungkan wajah yang mirip sekali. Yaitu, jika mereka berada dalam daftar yang sama (normal sama), berdekatan satu sama lain, memiliki tingkat cahaya yang sama, dll. Saya tahu saya masih akan berakhir dengan persegi panjang, tetapi harus dengan mudah mengurangi jumlah simpul saya hingga 50% atau lebih baik jika perkiraan saya benar.
Asumsi saya adalah membuat masing-masing dari 6 daftar diurutkan berdasarkan sumbu tempat mereka bersandar, kemudian oleh dua sumbu lainnya (daftar untuk bagian atas blok akan diurutkan berdasarkan nilai Y-nya, kemudian X, kemudian Z).
Dengan ini saja, saya bisa dengan mudah menggabungkan strip wajah, tapi saya mencari untuk menggabungkan lebih dari strip hanya bersama jika memungkinkan. Saya telah membaca tentang algoritma serakah yang serakah ini , tetapi saya mengalami banyak kesulitan untuk memahaminya.
Jadi, pertanyaan saya: Untuk melakukan penggabungan wajah seperti yang dijelaskan (mengabaikan apakah itu ide buruk untuk medan / pencahayaan yang dinamis), apakah mungkin ada algoritma yang lebih mudah diterapkan? Saya juga akan dengan senang hati menerima jawaban yang menuntun saya melalui algoritma serakah dengan cara yang lebih sederhana (tautan atau penjelasan).
Saya tidak keberatan sedikit penurunan kinerja jika lebih mudah diimplementasikan atau bahkan jika itu hanya sedikit lebih baik daripada hanya melakukan strip. Saya khawatir bahwa sebagian besar algoritma berfokus pada segitiga daripada paha depan dan menggunakan atlas 2D seperti saya, saya tidak tahu bahwa saya bisa mengimplementasikan sesuatu segitiga berdasarkan keterampilan saya saat ini.
PS: Saya sudah frustum memetik per potong dan seperti yang dijelaskan, saya juga menyisihkan wajah di antara blok padat. Saya belum menutup sumbatan dan mungkin tidak pernah.
* Sunting: Saya telah menerapkan teknik kecil saya sendiri, yang mungkin memiliki nama, tetapi saya cukup memeriksa 6 daftar saya yang diurutkan berdasarkan sumbu yang digunakannya, diikuti oleh jenis blok, dan kemudian oleh tingkat pencahayaan. Saya beralih melalui mereka, menciptakan persegi panjang baru saat saya pergi dan menumbuhkannya secara bersamaan (dengan bias berat terhadap sumbu tertentu). Jelas tidak optimal, tetapi memang cukup cepat dan itu menurunkan jumlah vertex saya rata-rata hampir 50%. Komentar Byte56 adalah lemari saya pikir untuk jawaban yang nyata, tetapi saya tidak bisa memilih itu untuk jawaban / karunia.
Ini adalah cara saya yang cepat dan sederhana saya menangani masalah ini SETELAH menghasilkan medan awal penuh tanpa banyak optimasi. Dengan asumsi semua kotak yang diberikan adalah gambar yang sama, level cahaya, normal, dll. Setiap warna adalah quad yang berbeda yang akan saya render. Dengan daftar saya yang diurutkan apa adanya, ini adalah pendekatan yang sangat mudah / cepat.
sumber
Jawaban:
Anda hanya ingin membuat strip, atau yang terbaik, persegi panjang. Tidak ada bentuk lain yang dapat dipecahkan atau berguna bagi Anda.
Saya juga ingin menunjukkan bahwa dengan menyimpan 6 daftar per bongkahan, bahwa pada titik mana pun Anda akan menggunakan 5 daftar dari bongkahan dalam arah mata angin, dan setidaknya 3 dalam setiap bidak lainnya. Anda membuang-buang waktu di sini, ketika kartu video tidak hanya dapat melakukan optimasi ini untuk Anda, tetapi bahkan jika Anda melakukannya sendiri, Anda akan lebih baik menyimpan semua wajah di satu tempat, dan membandingkan yang normal dengan arah ke arah ke kamera (Penelitian produk DOT vektor).
Tautan CaptainRedMuff pada penyatuan Greedy yang telah Anda lihat adalah jawaban untuk masalah Anda. Seharusnya juga jelas dari bahwa Anda akan berakhir dengan jerat "Stripy", tetapi mereka sangat efektif, dan datang dengan sesuatu yang lebih optimal akan lebih rumit, dan Anda telah menyatakan bahwa serakah rakus sudah terlalu rumit.
Jika Anda mengalami masalah kinerja dengan satu chunk, itu membuat saya berpikir ada hal lain yang sangat salah.
Dugaan pertama saya adalah Anda terlalu sering memanggil operasi undian. Anda hanya dapat memberi tahu kartu grafis untuk menggambar antara 50 dan 400 ~ kali per detik, tergantung pada perangkat kerasnya. Berapa banyak panggilan ke .setData atau .draw ____ Primitif yang Anda lakukan?
sumber
Artikel yang Anda tautkan sebenarnya tidak memberikan algoritme untuk menghasilkan mesh; itu menyatakan cara untuk mengevaluasi solusi yang mungkin.
Namun, secara umum, artikel tersebut memberikan ringkasan yang baik: 1) solusi naif buruk, 2) ada solusi optimal, tetapi akan memakan waktu untuk menulis dan menjalankan, 3) pemusnahan cepat memberikan hasil yang jauh lebih baik ( dan inilah yang dilakukan oleh Minecraft sendiri), dan akhirnya 4) mungkin ada solusi yang lebih cerdas (algoritma serakah).
"Solusi" yang Anda maksudkan dalam gambar dalam pertanyaan Anda adalah algoritma serakah. Tampaknya pertanyaan Anda adalah "apakah saya menerapkan solusinya dengan benar?" yang harus saya jawab, "dia tidak memberikan solusi; Anda sendiri yang memecahkannya."
Bisakah solusi Anda menjadi lebih baik? Ah. Tentu. Mungkin tidak sepadan. Saya pikir penyumbatan oklusi atau LOD akan menjadi langkah selanjutnya yang lebih baik. Minecraft membuang banyak siklus untuk menggambar permukaan bahkan ketika Anda berada di bawah tanah, serta menggambar jaringan besar sistem gua dan tambang saat Anda berada di permukaan. Setelah Anda mendapatkan pemecahan mesh yang baik, ya, menyingkirkan permukaan yang tidak jelas bisa menjadi hal yang baik - tetapi (mis.) Umumnya lebih cepat untuk membiarkan kartu video Anda melakukan culling backface daripada melakukannya pada CPU.
sumber