Bagaimana cara raytrace Bezier?

Saya mencoba pertanyaan ini di math.SE dan yang mengejutkan, jawabannya adalah "persamaannya terlalu buruk, hanya memberi makan fungsi itu ke pencari akar angka". Tetapi jika Anda menganggap diri Anda "seorang pria grafis" seperti saya, dan telah bermain secara luas dengan kurva Bezier untuk pekerjaan desain, saya harus percaya bahwa lebih baik dapat dilakukan. Ada algoritma yang diterbitkan oleh Kajiya bahwa saya tidak memiliki latar belakang untuk memahami (Matriks Sylvester), tetapi saran terkait matematika.SE adalah bahwa hasilnya adalah derajat-18 polinomial dalam t, dan Anda masih perlu menyelesaikannya secara numerik. Saya punya ide lain dengan hasil yang serupa .

Jadi, apakah ini merupakan mimpi pipa total untuk berharap dapat menyelesaikan persimpangan permukaan Ray / Bezier secara aljabar, sehingga memungkinkan untuk membuat kode secara eksplisit dan memiliki kelancaran super-cepat super?

Kecuali itu, apa metode tercepat untuk melakukan perhitungan ini? Bisakah Anda "menemukan goyangan" untuk mendapatkan ikatan yang ketat (dan target) untuk subdivisi rekursif? Jika Anda harus menggunakan pencari akar angka (mendesah), properti apa yang dibutuhkan dan apakah ada pilihan terbaik untuk kecepatan?

Pikiran orisinal saya adalah tentang mempersiapkan permukaan tertentu, mirip dengan ekspansi Laplace seperti yang dijelaskan dalam jawaban untuk pertanyaan matematika saya lainnya tentang segitiga . Tetapi saya juga tertarik pada metode umum. Saya hanya memikirkan satu set bentuk tetap, seperti teko Utah . Tapi saya akan sangat tertarik dengan cara mengoptimalkan koherensi temporal di seluruh frame animasi.

Pertama, inilah metode Kajiya yang saya pikir Anda pikirkan: Kajiya, Ray Tracing Parametric Patches , SIGGRAPH 82. Versi laporan teknologi mungkin lebih informatif.

Apa yang saya harap Anda dapatkan dari itu adalah bahwa itu tidak mustahil dan itu tidak sulit secara konseptual jika Anda tidak keberatan mengotori tangan Anda dengan geometri aljabar dan bilangan kompleks. Namun, melakukannya secara langsung sangat mahal.

Pelacak sinar "nyata" cenderung melakukan kombinasi dua hal:

• Menempatkan hierarki pembatas (mis. AABBs) pada tambalan untuk mendapatkan "nilai awal" yang bagus untuk pencari akar angka. Jika Anda melakukan ini dengan baik, Anda dapat menghindari masalah "kerut".
• Tesselating patch ke cangkang DDG dan ray menelusuri mereka seperti jerat poligon.

Poin terakhir itu kedengarannya seperti membunuh persyaratan "super-smoothness", tetapi hampir tidak seburuk itu jika Anda menggunakan diferensial sinar . Menyesuaikan level tessellation dengan "ukuran" sinar membatasi kesalahan dengan baik. Selain itu, Anda mungkin perlu diferensial untuk koordinat tekstur, jadi sebaiknya Anda menggunakannya untuk mengontrol akurasi tes persimpangan juga.

Mengeksploitasi koherensi temporal bukanlah ide yang buruk, tetapi bagaimana tepatnya Anda melakukan itu sangat tergantung pada representasi grafik adegan Anda. Anda mungkin ingin melihat ray coherence. Tanyakan mesin pencari favorit Anda tentang paket ray tracing dan ray penataan kembali .

apakah itu mimpi pipa total untuk berharap bisa menyelesaikan persimpangan permukaan Ray / Bezier secara aljabar

Ya, itu mimpi pipa. Patch Bezier bikubik adalah permukaan aljabar derajat 18. Untuk memotong sinar dengan permukaan ini, Anda harus menemukan akar polinomial derajat 18. Tidak ada rumus untuk akar ini - Anda harus menemukannya dengan metode numerik . Bahkan, ada hasil matematika ( teorema Abel-Ruffini ) yang memberi tahu kita bahwa tidak akan pernah ada rumus untuk akar persamaan di luar derajat 4. Matematika tidak hanya mengatakan bahwa rumus belum ditemukan; dikatakan bahwa mereka tidak akan pernah ditemukan, karena mereka tidak dapat ada.

Jika Anda benar-benar ingin melakukan penelusuran sinar aljabar analitik (aljabar), Anda dapat mencoba menggunakan tambalan Steiner . Ini memiliki derajat 4, sehingga persimpangan ray-patch dapat dihitung dengan menemukan akar kuartik (yaitu polinomial derajat 4). Ada rumus untuk menemukan akar kuartik, tetapi mereka cukup jahat, dan sangat sulit untuk menulis kode yang mengimplementasikan rumus dengan andal.

Pilihan lain, yang saya gunakan beberapa dekade yang lalu (ya!), Adalah menggunakan skema Toth dari tahun 1985 yang menggunakan aritmatika interval untuk mempersempit ruang pencarian. IIRC, akhirnya akan beralih ke Newton-Rhapson tetapi, sekali lagi IIRC, saya pikir jarang diperlukan lebih dari satu atau dua langkah untuk mendapatkan solusi yang baik.

Meskipun saya belum melihatnya (well, terlepas dari pandangan sekilas) Mitchell telah menerbitkan beberapa karya terbaru tentang penelusuran ray dengan matematika interval.

(Saya harus menambahkan bahwa, jika Anda hanya melakukan permukaan Bezier, maka metode interval mungkin sedikit "berlebihan" karena Anda dapat menggunakan trik seperti mekar untuk mendapatkan batasan dan turunan. Jika, bagaimanapun, Anda menggabungkan kurva Bezier dengan fungsi lain, misal rotasi di sekitar sumbu, maka umumnya lebih berguna.)

https://www.shadertoy.com/results?query=bezier urutkan berdasarkan usia, untuk masalah kompatibilitas:

, ... menunjukkan banyak solusi dari banyak himpunan bagian-spline, baik mengembalikan jarak ke spline 2d, atau melacak patch 3d. Splines dan patch datang dalam berbagai bentuk. Behindine beind paling sederhana, bezier menjadi simple, nurbs menjadi terlalu kompleks. Semakin banyak kendala yang Anda tambahkan ke spline Anda, semakin mudah ia dapatkan. NURBS adalah ekstensi berlebihan; - Ketidakberagaman bobot ("NU") mengurangi efisiensi dibandingkan dengan splines yang lebih simetris - Rasionalitasnya (R) juga menambahkan beberapa kompleksitas, untuk segmentasi (penjatahan) dan pencampuran dengan segmen terdekat (Dipecahkan secara rekursif).

bezier-patch-tracing adalah pemecahan masalah dan dengan itu datang prioritas kontekstual pada presisi; dalam rangka untuk memecahkan persamaan kuadratik. ini menjadi tidak praktis pada eksponen yang lebih tinggi dari kubik, karena kompleksitas eksponensial dan kehilangan presisi.

ray-marching == sphere-tracking adalah pendekatan heuristik yang lebih sederhana untuk pemecahan akar, yang tampaknya menjadi solusi sederhana dan paling efisien untuk merender sebagian besar patch splines.

Representasi-Lagrange menyederhanakan penelusuran / marching (karena L-point berada pada spline sedangkan ControlVector-point (dari spline yang sama persis) jarang pada spline)

Kasus khusus dari sphinensin-spline, di mana turunan pertama stat dan akhir adalah == 0. menyederhanakan kontinuitas dan melibatkan lebih sedikit perbedaan (less subtraction). Patch surga dapat dilacak secara efisien dalam satu lintasan: https://www.shadertoy.com/view/4djfW3 sementara spline kubik lainnya (atau lebih tinggi) menjadikan pendekatan sphere-tracking / ray-march heuristik lebih efisien (dan " cukup tepat ") daripada berani menghitung secara analitis semua root untuk menjaga root positif terkecil (dengan akumulasi kesalahan presisi secara eksponensial untuk setiap root).

Dalam grafik komputer, splines dan patch hampir sepenuhnya diganti oleh z-brushing pada tahun 2006. z-brushing menggunakan peta perpindahan dengan koordinat homogen, atau bahkan menggunakan "tipe" yang kita gunakan sebagai gabungan dari lingkup dan garis garis (garis garis memiliki radius 0, bola memiliki panjang 0, penyatuan sederhana dan bermanfaat). Untuk kehilangan kecil dalam presisi untuk keuntungan besar dalam kinerja dengan biaya memori yang relatif rendah untuk pencarian, yang mudah dibuat dinamis pada gpu.