Bagaimana saya bisa menghasilkan bidang jarak yang ditandatangani (2D) secara real time, cepat?

21

Dalam pertanyaan sebelumnya , disarankan bahwa bidang jarak yang ditandatangani dapat dihitung sebelumnya, dimuat saat runtime dan kemudian digunakan dari sana.

Untuk alasan yang akan saya jelaskan di akhir pertanyaan ini (untuk orang-orang yang tertarik), saya perlu membuat bidang jarak secara real time.

Ada beberapa makalah di luar sana untuk metode yang berbeda yang seharusnya dapat bertahan dalam lingkungan waktu nyata, seperti metode untuk transformasi jarak Chamfer dan transformasi berbasis diagram-pendekatan Voronoi (seperti yang disarankan dalam presentasi ini oleh pria pengembang Pixeljunk Shooter dev ), tetapi Saya (dan dengan demikian dapat diasumsikan banyak orang lain) memiliki waktu yang sangat sulit untuk menggunakannya, karena biasanya panjang, sebagian besar penuh dengan matematika dan tidak terlalu algoritmik dalam penjelasannya.

Algoritma apa yang akan Anda sarankan untuk membuat bidang jarak secara real-time (lebih baik pada GPU) terutama mengingat kualitas yang dihasilkan dari bidang jarak?

Karena saya sedang mencari penjelasan / tutorial yang sebenarnya dan bukan tautan ke kertas atau slide lain, pertanyaan ini akan menerima hadiah setelah memenuhi syarat untuk satu :-).

Inilah mengapa saya perlu melakukannya secara real time:

Jika Anda harus melakukan precompute SDFs ini untuk lingkungan 2D yang besar (pikirkan peta seperti Terraria yang besar), ini berarti Anda menerima overhead yang agak besar di ruang penyimpanan (dan waktu pembuatan peta) demi menerapkan lebih banyak algoritma rumit yang cukup cepat untuk pembuatan SDF waktu nyata.

Misalnya, peta yang relatif kecil dengan 1000 * 256 (lebar * tinggi) dengan ukuran ubin 10 * 10 piksel dan dengan demikian total dimensi 10.000 * 2560 piksel akan dikenakan biaya sekitar 2 megabita ukuran, jika Anda memilih yang relatif kecil Resolusi SDF 128x128, dengan asumsi bahwa Anda hanya menyimpan nilai jarak dari 0 hingga 255.

Jelas, ini bisa dengan cepat menjadi terlalu banyak dan merupakan overhead yang tidak ingin saya miliki.

Ada sesuatu yang lain:

SDF dapat digunakan untuk banyak hal (seperti deteksi tabrakan), dan beberapa aplikasi yang berguna bahkan belum ditemukan. Saya pikir banyak orang akan mencari hal-hal ini di masa depan, dan jika kita mendapatkan jawaban yang komprehensif di sini, saya pikir kita akan membantu banyak orang.

2d signed-distance-field TravisG
sumber
Saya googled "apa itu bidang jarak yang ditandatangani" dan hit pertama adalah versi GPU: http.developer.nvidia.com/GPUGems3/gpugems3_ch34.html Ini agak lama tetapi mungkin membantu pencarian Anda lebih jauh.
Patrick Hughes
1
Mungkin saya kehilangan sesuatu, tapi saya agak bingung dengan pernyataan mengapa Anda perlu melakukannya secara real time (paling tidak, mengapa itu ditandai dengan spoiler); pertama, di mana Anda mendapatkan angka 2MB untuk SDF 128x128? Kedua, mengapa Anda menganggap 2MB sebagai penggunaan memori yang sangat berat? Saya setuju ini tidak penting, tetapi tampaknya sebagian kecil dari keseluruhan penggunaan memori peta Anda. Dan ketiga, bagaimana cara menghasilkan bidang dalam waktu nyata menghemat memori itu? Anda masih perlu menyimpan data yang persis sama apakah itu dihasilkan dengan cepat atau dihitung, bukan?
Steven Stadnicki
Secara lebih luas, bisa jadi SDF bukanlah teknik yang Anda butuhkan. Informasi lebih lanjut tentang situasi spesifik Anda - penghitungan hambatan statis, penghalang kendala dinamis, dll. - dan efek apa yang ingin Anda capai akan sangat membantu dalam mencoba menjabarkan apa yang paling mungkin berguna bagi Anda.
Steven Stadnicki
1
Jika saya membuat field jarak secara real time, saya hanya akan membuat 2MB itu satu kali per frame (total overhead memori akan selalu menjadi memori yang diperlukan untuk satu field jarak, karena saya hanya membutuhkan satu untuk layar). Jika saya memiliki peta yang lebih besar dari contoh 1000x128 saya (saya pikir peta Terraria besar melampaui 10.000 itu) Saya membutuhkan salah satu dari 2mb untuk setiap submap 1000x128 peta itu. Mengapa saya membutuhkan SDF di tempat pertama dijelaskan dalam pertanyaan pertama yang saya tautkan di awal pertanyaan ini (ini untuk GPU 2D shadow casting).
TravisG
1
@heishe apakah Anda mencoba menghasilkan 2 MB data sekali per frame? Serius?
kaoD

Jawaban:

9

Catalin Zima menjelaskan cara mencapai bayangan 2D dinamis di artikelnya - dan dia memang menggunakan bidang jarak yang telah ditandatangani (dari apa yang bisa saya katakan itu hanyalah nama mewah untuk buffer bayangan dalam konteks ini). Metodenya memang membutuhkan GPU, dan implementasinya apa adanya adalah bukan yang terbaik (turun di bawah 60Hz pada sekitar 20 lampu pada mesin saya, saya punya sekitar 500 lampu); yang diharapkan karena dia lebih menyukai kejelasan kode daripada kecepatan.

Pelaksanaan

Persis seperti yang diterapkan olehnya:

  1. Jadikan semua kastor bayangan menjadi tekstur.
  2. Hitung jarak ke pusat cahaya untuk setiap piksel, dan tetapkan nilai itu ke RGB piksel buram.
  3. Distorsi gambar sehingga mewakili bagaimana kamera 3D akan melihat piksel tersebut.
  4. Squash gambar menjadi gambar berukuran 2xN menggunakan ukuran yang tidak biasa yang dijelaskan dalam artikelnya (ukuran polos tidak akan berfungsi).
  5. Gambar 2xN sekarang menjadi bidang jarak yang Anda tandatangani untuk keempat kuadran cahaya (ingat bahwa satu kuadran pada dasarnya adalah satu frustrasi kamera pada 90 derajat).
  6. Render peta cahaya.
  7. Blur the lightmap (berdasarkan jarak dari cahaya) sehingga Anda mendapatkan bayangan lembut.

Implementasi terakhir saya adalah (setiap langkah menjadi shader tunggal):

  1. Lakukan (1).
  2. Lakukan (2) dan (3) .
  3. Lakukan (4). Implementasinya sangat lambat: jika Anda dapat mencoba dan menggunakan GPGPU untuk ini. Saya tidak bisa menggunakan GPGPU (XNA) jadi yang saya lakukan adalah:
    • Siapkan mesh di mana kolom N / 2 pertama diwakili oleh paha N / 2 dengan posisi EXACT yang sama (mencakup kolom pertama dari buffer akhir) tetapi koordinat tekstur yang berbeda (hal yang sama untuk kolom N / 2 kedua)
    • Matikan pengujian mendalam pada GPU.
    • Gunakan fungsi blending MIN pixel.
  4. Lakukan (6) dan (7).

Ini cukup cerdik: ini pada dasarnya merupakan terjemahan langsung dari bagaimana bayangan ditangani dalam 3D menjadi 2D.

Perangkap

Perangkap utama adalah bahwa beberapa objek tidak boleh dibayangi: dalam contoh saya, saya sedang menulis klon Liero (cacing waktu nyata) dan karenanya tidak ingin, misalnya, cacing para pemain dibayangi (setidaknya satu di layar masing-masing pemain). Yang saya lakukan untuk benda-benda 'istimewa' ini adalah menggambarnya kembali sebagai langkah terakhir. Ironisnya adalah bahwa sebagian besar objek tidak dibayangi (cacing, latar depan lanskap) sehingga ada masalah penarikan di sini.

Jonathan Dickinson
sumber
Apakah penyesuaian Anda pada metode pengubahan ukuran satu-satunya hal untuk mempercepatnya untuk menangani 500 lampu di atas 60fps?
TravisG
OK, saya akan menerima jawabannya karena ini memecahkan masalah asli saya, tetapi tidak benar-benar menjawab untuk apa saya memberi hadiah. Saya akan menunggu dan mungkin seseorang perlu waktu lama untuk menjelaskan salah satu dari beberapa metode O (N) untuk pembuatan lapangan jarak jauh yang ditandatangani.
TravisG
@heishe tentang pertanyaan pertama Anda: tidak yakin. Saya melakukan semua optimasi dalam satu langkah - saya pikir saya ingat mematikannya dan menonton framerate turun secara substansial. All-in-all 6 draw draw per lampu akan membunuh framerate Anda. Seperti yang saya katakan sepertinya, dari apa yang saya tahu, Anda memiliki 4 bidang jarak yang ditandatangani pada langkah (5) - tetapi seseorang yang tahu lebih banyak tentang mereka perlu mengonfirmasi hal itu.
Jonathan Dickinson
Nah, ini adalah kasus yang sangat khusus dari bidang jarak yang ditandatangani. Dalam bidang jarak yang ditandai normal, setiap piksel berisi jarak ke rintangan terdekat. Dalam algoritma ini, bidang jarak hanya berisi satu hambatan, dan juga hambatan hanya 1 piksel di seluruh gambar (sumber cahaya), itulah sebabnya bidang jarak ini dapat dihasilkan dalam O (N).
TravisG
1
@heishe di sini adalah shader saya: gist.github.com/2384073 . DistortPS adalah 2 + 3.
Jonathan Dickinson