Teori Probabilitas untuk Rendering yang Akurat Secara Fisik

Pendahuluan

Dalam rendering, perhitungan integral pasti multidimensi sering digunakan: misalnya, untuk menentukan visibilitas sumber cahaya spasial (cahaya area), luminositas yang mencapai wilayah piksel, luminositas yang tiba dalam periode waktu tertentu dan iradiasi yang datang melalui belahan titik permukaan. Perhitungan integral ini biasanya dilakukan menggunakan integrasi Monte Carlo, di mana integral digantikan oleh ekspektasi percobaan stokastik.

Pada artikel ini saya akan berbicara secara rinci tentang proses integrasi dasar Monte Carlo, serta beberapa teknik untuk mengurangi varians teknik. Ini akan dilakukan dari sudut pandang praktis - diasumsikan bahwa pembaca tidak terlalu akrab dengan teori probabilitas, tetapi masih ingin mengembangkan algoritma render yang efektif dan benar.

Integral yang ditentukan

Integral pasti adalah integral dari formulir $$$\ int_ {a} ^ {b} f (x) dx$ dimana $$$[a, b]$ Apakah segmen (atau wilayah), $$$x$ - skalar, dan $$$f (x)$ - fungsi yang dapat dihitung untuk titik mana pun di segmen. Seperti yang ditulis di Wikipedia , integral tertentu adalah area dengan tanda di pesawat $$$x$ dibatasi oleh jadwal $$$f$ poros $$$x$ dan garis-garis vertikal $$$x = a$ dan $$$x = b$ ( Gambar 1a ).

Konsep ini secara logis meluas ke jumlah dimensi yang lebih tinggi: untuk integral ganda tertentu, area dengan tanda menjadi volume dengan tanda ( Gambar 1b ), dan secara umum untuk beberapa integral tertentu menjadi volume multidimensi dengan sebuah tanda .


Gambar 1: contoh integral tertentu.

Dalam beberapa kasus, area dapat ditentukan secara analitis , misalnya untuk $$$f (x) = 2$ : di segmen $$$[a, b]$ area akan sama $$$2 (b-a)$ . Dalam kasus lain, solusi analitis tidak mungkin, misalnya, ketika kita perlu mengetahui volume bagian gunung es di atas air ( Gambar 1c ). Dalam kasus seperti itu $$$f (x)$ sering dapat ditentukan dengan pengambilan sampel .

Integrasi numerik

Kita dapat kira-kira menghitung luas integral kompleks menggunakan integrasi numerik . Salah satu contoh adalah jumlah Riemann . Jumlah ini dihitung dengan membagi area menjadi bentuk reguler (misalnya, persegi panjang), yang bersama-sama membentuk area yang mirip dengan area sebenarnya. Jumlah Riemann didefinisikan sebagai berikut:

$$

$$\ tag {1} S = \ sum_ {i = 1} ^ {n} f (x_i) \ Delta x_i$$

$$$n$ Apakah jumlah sub-interval, dan $$$\ Delta x_i = \ frac {b-a} {n}$ - lebar satu sub-interval. Untuk setiap interval $$$i$ kami sampel $$$f$ pada satu titik $$$x_i$ di dalam sub-interval (pada Gambar 2, titik ini berada di awal sub-interval).


Gambar 2: Jumlah Riemann.

Perlu dicatat bahwa dengan meningkatnya $$$n$ jumlah Riemann menyatu dengan nilai riil integral:

$$

$$\ tag {2} \ int_ {a} ^ {b} f (x) dx = \ lim_ {|| \ Delta x || \ hingga 0} \ sum_ {i = 1} ^ {n} f (x_i) \ Delta x_i$$

Jumlah Riemann juga dapat digunakan untuk dimensi besar ( Gambar 3 ). Namun, di sini kita dihadapkan dengan masalah: untuk fungsi dengan dua parameter, jumlah sub-interval harus jauh lebih besar jika kita ingin mencapai resolusi yang sebanding dengan yang digunakan dalam kasus dua dimensi. Fenomena ini disebut kutukan dimensi , dan dalam dimensi yang lebih tinggi ia diperburuk.


Gambar 3: Jumlah Riemann untuk integral ganda.

Sekarang kita akan mengevaluasi keakuratan jumlah Riemann untuk fungsi berikut (kami sengaja memilih fungsi yang kompleks):

$$

$$\ tag {3} f (x) = \ kiri | \ sin \ kiri (\ frac {1} {2} x + \ frac {\ pi} {2} \ kanan) \ tan \ frac {x} {27} + \ sin \ kiri (\ frac {3} {5} x ^ 2 \ kanan) + \ frac {4} {x + \ pi + 1} -1 \ kanan |$$

Grafik fungsi pada suatu segmen $$$[- 2.5,2.5]$ ditunjukkan di bawah ini. Untuk referensi, kami menghitung integral tertentu dalam Wolfram Alpha $$$\ int _ {- 2.5} ^ {2.5} f (x)$ mendapatkan area $$$3,12970$ . Grafik di sebelah kanan menunjukkan keakuratan integrasi numerik menggunakan jumlah Riemann untuk meningkatkan $$$n$ .


Gambar 4: Grafik fungsi dan akurasi jumlah Riemann. Bahkan dengan yang kecil $$$n$ kami mendapatkan hasil yang cukup akurat.

Untuk mendapatkan gagasan tentang keakuratan, kami memberikan angka: untuk $$$n = 50$ kesalahannya adalah $$$~ 2 \ times10 ^ {- 3}$ . Di $$$n = 100$ kesalahannya adalah $$$~ 3 \ times10 ^ {- 4}$ . Urutan besarnya berikut diperoleh dengan $$$n = 200$ .

Untuk informasi lebih lanjut tentang jumlah Riemann, lihat sumber daya berikut:

• Kahn Academy: https://www.khanacademy.org/math/ap-calculus-ab/ab-accumulation-riemann-sums/ab-riemann-sums/v/simple-riemann-approximation-using-rectangles
• Wikipedia: https://en.wikipedia.org/wiki/Riemann_sum

Monte Carlo (1)

Saat rendering, hampir tidak ada (dan mungkin tidak sama sekali?) Integral adalah tunggal . Ini berarti bahwa kita akan dengan cepat menghadapi kutukan dimensi. Selain itu, pengambilan sampel suatu fungsi pada interval yang sama dikenakan pengambilan sampel dan distorsi yang tidak mencukupi : kita dapat melewatkan nilai-nilai penting dari fungsi tersebut atau mendapatkan gangguan tak terduga antara fungsi sampel dan pola pengambilan sampel ( Gambar 5 ).


Gambar 5: distorsi menyebabkan hilangnya bagian-bagian dari fungsi sampel (merah) dan, dalam hal ini, interpretasi fungsi yang sepenuhnya salah.

Masalah-masalah ini diselesaikan dengan menggunakan teknik yang disebut integrasi Monte Carlo . Mirip dengan jumlah Riemann, ia juga menggunakan sampling fungsi pada serangkaian titik, tetapi tidak seperti pola jumlah Riemann deterministik , kami menggunakan bahan yang secara fundamental tidak deterministik : angka acak.

Integrasi Monte Carlo didasarkan pada pengamatan berikut: integral dapat digantikan oleh ekspektasi percobaan stokastik:

$$

$$\ tag {4} \ int_ {a} ^ {b} f (x) dx = (ba) E \ kiri [f (X) \ kanan] \ approx \ frac {ba} {n} \ sum_ {i = 1} ^ {n} f (X)$$

Dengan kata lain, kami mencicipi fungsinya $$$n$ kali pada titik acak dalam suatu segmen (dilambangkan dengan modal $$$X$ ), rata-rata sampel dan kalikan dengan lebar segmen (untuk fungsi satu dimensi). Seperti dalam kasus jumlah Riemann, kapan $$$n$ hingga tak terhingga, nilai rata-rata sampel menyatu dengan harapan, yaitu, dengan nilai sebenarnya dari integral.

Sedikit teori probabilitas

Penting untuk memahami setiap konsep yang digunakan di sini. Mari kita mulai dengan menunggu : ini adalah nilai yang diharapkan untuk satu sampel. Perhatikan bahwa ini belum tentu merupakan nilai yang mungkin, yang mungkin tampak berlawanan dengan intuisi. Misalnya, ketika kita melempar dadu, harapannya sama dengan $$$3,5$ - rata-rata dari semua hasil yang mungkin: $$$(1 + 2 + 3 + 4 + 5 + 6) /6=21/6=3.5$ .

Konsep kedua adalah angka acak . Ini mungkin tampak jelas, tetapi untuk integrasi Monte Carlo kita perlu angka acak yang terdistribusi secara merata, yaitu setiap nilai harus memiliki probabilitas generasi yang sama. Kami akan membicarakan lebih lanjut tentang ini nanti.

Konsep ketiga adalah penyimpangan dan varians yang terkait dengannya. Bahkan ketika kita mengambil sejumlah kecil angka, nilai rata-rata yang diharapkan, serta harapan dari masing-masing sampel individu, harus sama. Namun, ketika menghitung persamaan 4, kita jarang mendapatkan nilai seperti itu. Deviasi adalah perbedaan antara harapan dan hasil percobaan: $$$X-E (X)$ .

Dalam praktiknya, penyimpangan ini memiliki distribusi yang menarik:


Ini adalah grafik dari distribusi normal , atau distribusi Gaussian : ini menunjukkan bahwa tidak semua penyimpangan memiliki kemungkinan yang sama. Bahkan, sekitar 68,2% sampel berada dalam kisaran $$$-1 \ sigma..1 \ sigma$ dimana $$$\ sigma$ (sigma) adalah standar deviasi . Deviasi standar dapat dijelaskan dalam dua cara:

• Deviasi standar adalah ukuran variabilitas data.
• 95% titik data berada di dalam $$$2 \ sigma$ dari rata-rata.

Ada dua metode untuk menentukan standar deviasi:

1. Simpangan baku $$$\ sigma = \ sqrt {\ frac {1} {n} \ sum_ {i = 1} ^ {n} \ kiri (X_i-E \ kiri [X \ kanan] \ kanan) ^ 2}$ : dapat dihitung jika ada distribusi probabilitas diskrit dan ekspektasinya diketahui $$$E [X]$ . Ini berlaku untuk kubus di mana $$$X = {1,2,3,4,5,6}$ dan $$$E [X] = 3,5$ . Mengganti angka, kita dapatkan $$$\ sigma = 1,71$ .
2. Juga, standar deviasi sampel dapat dihitung sebagai $$$\ sigma = \ sqrt {\ frac {1} {n-1} \ sum_ {i = 1} ^ {n} \ kiri (X_i-X \ kanan) ^ 2}$ . Baca lebih lanjut tentang ini di Wikipedia .

Periksa: apakah ini benar? Jika $$$\ sigma = 1,71$ , kami menyatakan bahwa 68,2% dari sampel berada dalam 1,71 dari 3,5. Kami tahu itu $$${2,3,4,5}$ memenuhi kriteria ini, dan $$$1$ dan $$$6$ - tidak. Empat dari enam adalah 66,7%. Jika kubus kami dapat menghasilkan nilai dalam interval $$$[1..6]$ , maka kita akan mendapatkan 68,2%.

Alih-alih standar deviasi, konsep varians terkait, yang didefinisikan sebagai $$$Var \ kiri [X \ kanan] = \ sigma ^ 2$ . Karena kuadrat digunakan, varians selalu positif, yang membantu dalam perhitungan.

Monte Carlo (2)

Di atas, kami kira-kira menghitung persamaan 3 menggunakan jumlah Riemann. Sekarang kami ulangi percobaan ini dengan integrasi Monte Carlo. Ingatlah bahwa integrasi Monte Carlo didefinisikan sebagai berikut:

$$

$$\ tag {5} \ int_ {a} ^ {b} f (x) dx = (ba) E \ kiri [f (X) \ kanan] \ approx \ frac {ba} {n} \ sum_ {i = 1} ^ {n} f (X)$$

Mari kita terjemahkan ini ke dalam kode C:

double sum = 0; for( int i = 0; i < n; i++ ) sum += f( Rand( 5 ) - 2.5 ); sum = (sum * 5.0) / (double)n; 

Hasil untuk nilai dari $$$n = 2$ sebelumnya $$$n = 200$ ditunjukkan pada grafik di bawah ini. Dari sini dapat diasumsikan bahwa integrasi Monte Carlo memanifestasikan dirinya jauh lebih buruk daripada jumlah Riemann. Pemeriksaan yang lebih dekat dari kesalahan mengatakan bahwa dengan $$$n = 200$ kesalahan rata-rata dari jumlah Riemann adalah $$$0,0002$ dan Monte Carlo $$$0,13$ .


Gambar 6: Kesalahan Monte Carlo di 2.200 sampel.

Dalam dimensi yang lebih tinggi, perbedaan ini berkurang, tetapi tidak sepenuhnya dihilangkan. Persamaan yang ditunjukkan di bawah ini adalah versi diperluas dari yang digunakan di atas, menerima dua parameter:

$$

$$f (x, y) = \ kiri | \ sin \ kiri (\ frac {1} {2} x + \ frac {\ pi} {2} \ kanan) \ tan \ frac {x} {27} + \ sin \ kiri (\ frac {1} {6} x ^ 2 \ kanan) + \ frac {4} {x + \ pi + 1} -1 \ kanan | \ kiri | \ sin \ kiri (1,1 \ kanan) \ cos \ kiri (2.3x \ kanan) \ kanan | (6)$$

Gambar 7: Grafik persamaan di atas.

Di bidang definisi $$$x∈ [-2.5,2.5], y∈ [-2.5,2.5]$ volume dibatasi oleh fungsi dan bidang ini $$$xy$ sama $$$6.8685$ . Di $$$n = 400$ (20 × 20 sampel) kesalahan jumlah Riemann adalah $$$0,043$ . Dengan jumlah sampel yang sama, kesalahan integrasi rata-rata Monte Carlo adalah $$$0,33$ . Ini lebih baik dari hasil sebelumnya, tetapi perbedaannya masih signifikan. Untuk memahami masalah ini, kita akan mempelajari teknik pengurangan dispersi integrasi Monte Carlo yang terkenal yang disebut "stratifikasi".


Gambar 8: dampak stratifikasi; a) sampel dengan distribusi yang buruk; b) sampel dengan distribusi seragam.

Stratifikasi meningkatkan keseragaman angka acak. Dalam Gambar 8a , delapan angka acak digunakan untuk sampel fungsi. Karena setiap angka dipilih secara acak, mereka sering berubah menjadi tidak merata pada domain definisi. Gambar 8b menunjukkan efek stratifikasi: area definisi dibagi menjadi delapan strata, dan posisi acak dipilih di setiap strata, yang meningkatkan keseragaman.

Efek pada varians cukup jelas. Gambar 9a menunjukkan grafik hasil dengan dan tanpa stratifikasi. Gambar 9b menunjukkan kesalahan nilai perkiraan. Di $$$n = 10$ kesalahan rata-rata untuk 8 strata adalah $$$0,05$ ; untuk 20 strata - $$$0,07$ , dan untuk 200 strata berkurang menjadi $$$0,002$ . Berdasarkan hasil ini, tampaknya layak menggunakan sejumlah besar strata. Namun, stratifikasi memiliki kelemahan yang meningkat dengan meningkatnya jumlah strata. Pertama, jumlah sampel harus selalu kelipatan dari jumlah strata; kedua, seperti dalam jumlah Riemann, stratifikasi menderita kutukan dimensi.


Gambar 9: stratifikasi dan varians: a) nilai perkiraan untuk jumlah sampel dari n = 2 hingga n = 200; b) penyimpangan.

Pentingnya Sampel

Di bagian sebelumnya, kami sampel persamaan secara merata. Perpanjangan fungsi integrasi Monte Carlo memungkinkan kita untuk mengubah situasi:

$$

$$\ tag {7} \ int_ {a} ^ {b} f (x) dx = (ba) E \ kiri [f (X) \ kanan] \ approx \ frac {ba} {n} \ sum_ {i = 1} ^ {n} \ frac {f (X)} {p (X)}$$

Di sini $$$p (X)$ Adalah fungsi probabilitas kerapatan (pdf) : menentukan probabilitas relatif bahwa variabel acak akan mengambil nilai tertentu.

Untuk variabel acak seragam dalam interval $$$0..1$ , pdf adalah 1 ( Gambar 10 a), dan ini berarti bahwa setiap nilai memiliki probabilitas pilihan yang sama. Jika kita mengintegrasikan fungsi ini ke atas $$$[0,0.5]$ maka kita mendapatkan probabilitas di $$$0,5$ dari apa $$$X <\ frac {1} {2}$ . Untuk $$$X> \ frac {1} {2}$ kami jelas mendapatkan probabilitas yang sama.


Gambar 10: Distribusi Probabilitas. a) pdf konstan di mana setiap sampel memiliki probabilitas pilihan yang sama; b) pdf, di mana sampel di bawah 0,5 memiliki probabilitas pemilihan yang lebih tinggi.

Gambar 10b menunjukkan pdf lain. Dalam hal ini, kemungkinan menghasilkan angka lebih kecil $$$\ frac {1} {2}$ sama dengan 70%. Ini dapat diimplementasikan menggunakan potongan kode berikut:

 float SamplePdf() { if (Rand() < 0.7f) return Rand( 0.5f ); else return Rand( 0.5f ) + 0.5f; } 

Pdf ini didefinisikan sebagai berikut:

$$

$$\ tag {8} p (x) = \ kiri \ {\ begin {matrix} 1.4, jika x <\ frac {1} {2} \\ 0.6, jika tidak \ end {matrix} \ kanan.$$

Angka-angka $$$1,4$ dan $$$0,6$ mencerminkan kebutuhan probabilitas itu $$$x <\ frac {1} {2}$ sama dengan 70%. Saat mengintegrasikan pdf dengan $$$[0 .. \ frac {1} {2}]$ memberi $$$1,4 \ times \ frac {1} {2}$ , dan $$$0,6 \ kali \ frac {1} {2}$ sama dengan $$$0,3$ . Ini menggambarkan persyaratan penting untuk semua pdf secara umum: hasil mengintegrasikan pdf harus 1. Persyaratan lain adalah itu $$$p (x)$ tidak boleh nol jika $$$f (x)$ bukan nol: itu berarti bagian-bagiannya $$$f$ memiliki probabilitas sampling nol, yang jelas mempengaruhi nilainya.

Beberapa tips untuk memahami konsep pdf:

• Satu nilai pdf tidak menggambarkan probabilitas: oleh karena itu, pdf lokal dapat lebih besar dari 1 (misalnya, seperti dalam pdf yang baru saja diperiksa).
• Namun, integral dari domain definisi pdf adalah probabilitas, yang berarti bahwa integrasi pdf memberikan 1.

Satu nilai dapat diartikan sebagai kemungkinan relatif dari penampilan nilai tertentu.

Perlu dipertimbangkan bahwa distribusi normal adalah fungsi dari distribusi probabilitas: ini memberi kita probabilitas bahwa beberapa variabel acak akan berada dalam interval tertentu. Dalam kasus distribusi normal, variabel acak ini adalah penyimpangan dari rata-rata. Seperti pdf yang layak, hasil mengintegrasikan distribusi normal adalah 1.

Oleh karena itu, Persamaan 7 memungkinkan kita untuk melakukan pengambilan sampel yang tidak seragam. Ini mengkompensasinya dengan membagi setiap sampel dengan probabilitas relatif dari pilihannya. Pentingnya ini ditunjukkan pada Gambar 11a . Grafik fungsi menunjukkan interval signifikan di mana nilainya $$$0$ . Pengambilan sampel di area ini tidak ada gunanya: tidak ada yang ditambahkan ke jumlah, kami hanya membagi dengan jumlah yang lebih besar. Ingat gunung es dari Gambar 1c : tidak masuk akal untuk mencicipi ketinggian di area besar di sekitar gunung es.


Gambar 11: pdf untuk fungsi dengan nilai nol.

Pdf menggunakan pengetahuan fungsi ini ditunjukkan pada Gambar 11b . Perhatikan bahwa pdf ini sebenarnya nol untuk rentang nilai. Ini tidak mengubahnya menjadi pdf yang salah: di beberapa tempat, fungsinya nol. Kita dapat memperluas ide ini melampaui nol. Sampel sebaiknya dihabiskan di tempat-tempat di mana fungsi memiliki nilai signifikan. Faktanya, pdf ideal sebanding dengan fungsi sampel . Pdf yang sangat bagus untuk fungsi kita ditunjukkan pada Gambar 12a . Pdf yang lebih baik ditunjukkan pada Gambar 12b . Dalam kedua kasus, kita tidak boleh lupa untuk menormalkannya sehingga integralnya sama dengan 1.


Gambar 12: Enhanced pdf untuk fungsi pada Gambar 11.

Pdf pada Gambar 12 menimbulkan dua tugas bagi kita:

1. cara membuat pdf seperti itu;
2. bagaimana sampel pdf tersebut?

Jawaban untuk kedua pertanyaan itu sama: kita tidak perlu melakukan ini. Dalam banyak kasus, fungsi yang ingin kita integrasikan tidak diketahui, dan satu-satunya cara untuk menentukan tempat-tempat yang signifikan adalah dengan mengambil sampelnya, dan untuk ini kita perlu pdf; situasi klasik "ayam dan telur".

Namun, dalam kasus lain, kami memiliki gagasan kasar tentang di mana fungsi dapat memberikan nilai yang lebih tinggi atau nilai nol. Dalam kasus seperti itu, pdf yang sangat kasar seringkali lebih baik daripada tanpa pdf.

Juga, kami mungkin memiliki kesempatan untuk membuat pdf dengan cepat. Beberapa sampel memberikan gagasan tentang bentuk fungsi, dan atas dasar itu kami mengarahkan sampel berikutnya ke tempat-tempat di mana kami mengharapkan nilai tinggi, yang kami gunakan untuk meningkatkan pdf, dan sebagainya.

Pada artikel selanjutnya, kami akan menerapkan konsep-konsep ini untuk implementasi rendering. Tantangan serius adalah membangun pdf. Kami memeriksa beberapa kasus di mana pdf membantu dalam pengambilan sampel.