Aplikasi Integrasi Monte Carlo dalam Rendering

Kita semua mempelajari metode numerik dalam pelajaran matematika. Ini adalah metode seperti integrasi, interpolasi, seri, dan sebagainya. Ada dua jenis metode numerik: deterministik dan acak.

Metode integrasi fungsi deterministik tipikal $$$f$ dalam jangkauan $$$[a, b]$ Sepertinya ini: kami ambil $$$n + 1$ poin spasi merata $$$t_0 = a, t_1 = a + \ frac {b - a} {n}, \ ldots, t_n - b$ menghitung $$$f$ di titik tengah $$$\ frac {t_i + t_ {i + 1}} {2}$ dari setiap interval yang ditentukan oleh titik-titik ini, merangkum hasil dan kalikan dengan lebar setiap interval $$$\ frac {b -a} {b}$ . Untuk fungsi yang cukup berkelanjutan $$$f$ dengan meningkatnya $$$n$ hasilnya akan konvergen ke nilai yang benar.


Metode probabilistik, atau metode Monte Carlo untuk menghitung, atau, lebih tepatnya, perkiraan kasar integral $$$f$ dalam jangkauan $$$[a, b]$ terlihat seperti ini: biarkan $$$X_1, \ ldots, X_n$ - Poin yang dipilih secara acak dalam interval $$$[a, b]$ . Lalu $$$Y = (b - a) \ frac {1} {n} \ sum_ {i = 1} ^ {n} f (X_i)$ Adalah nilai acak yang rata-rata adalah integral $$$\ int _ {[a, b]} f$ . Untuk mengimplementasikan metode ini, kami menggunakan generator angka acak yang menghasilkan $$$n$ poin dalam interval $$$[a, b]$ kami menghitung di masing-masing $$$f$ , rata-rata hasil dan kalikan dengan $$$b-a$ . Ini memberi kita nilai perkiraan integral, seperti yang ditunjukkan pada gambar di bawah ini. $$$\ int _ {- 1} ^ {1} \ sqrt {1 - x ^ 2} dx$ dengan 20 sampel mendekati hasil yang benar sama dengan $$$\ frac {\ pi} {2}$ .


Tentu saja, setiap kali kami menghitung nilai perkiraan seperti itu, kami akan mendapatkan hasil yang berbeda. Varian dari nilai-nilai ini tergantung pada bentuk fungsi. $$$f$ . Jika kita menghasilkan poin acak $$$x_i$ tidak merata, maka kita perlu sedikit mengubah formula. Namun berkat penggunaan distribusi poin yang tidak merata, kami mendapatkan keuntungan besar: memaksa distribusi yang tidak merata untuk memberikan preferensi pada poin $$$x_i$ dimana $$$f (x)$ besar, kita dapat secara signifikan mengurangi varians dari nilai perkiraan. Prinsip pengambilan sampel yang tidak seragam ini disebut pengambilan sampel secara signifikan .


Sejak beberapa dekade terakhir, transisi berskala besar dari pendekatan deterministik ke acak telah dilakukan dalam teknik rendering, kami akan mempelajari pendekatan acak yang digunakan untuk memecahkan persamaan rendering. Untuk melakukan ini, kami menggunakan variabel acak, ekspektasi matematika dan varians. Kami berurusan dengan nilai-nilai diskrit, karena komputer pada dasarnya bersifat diskrit. Jumlah kontinyu berhubungan dengan fungsi kerapatan probabilitas , tetapi dalam artikel kami tidak akan mempertimbangkannya. Kami akan berbicara tentang kemungkinan fungsi massa. PMF memiliki dua properti:

1. Untuk masing-masing $$$s \ dalam S$ ada $$$p (s) \ geq 0$ .
2. $$$\ sum_ {s \ dalam S} p (s) = 1$

Properti pertama disebut non-negatif. Yang kedua disebut "normalitas." Secara intuitif, itu $$$S$ mewakili himpunan hasil beberapa percobaan, dan $$$p (s)$ Merupakan hasil dari probabilitas $$$s$ anggota $$$S$ . Hasilnya adalah bagian dari ruang probabilitas. Probabilitas hasil adalah jumlah elemen PMF dari hasil ini, sejak

$$

$$Pr \ {E \} = \ sum_ {s \ in S} p (s)$$

Variabel acak adalah fungsi, biasanya dilambangkan dengan huruf kapital, yang menetapkan bilangan real dalam ruang probabilitas:

$$

$$X: S \ rightarrow \ boldsymbol {R}.$$

Perhatikan bahwa fungsinya $$$X$ - Ini bukan variabel, tetapi fungsi dengan nilai nyata. Dia juga tidak acak , $$$X (s)$ Adalah bilangan real terpisah untuk hasil apa pun $$$s \ dalam S$ .

Variabel acak digunakan untuk menentukan hasil. Misalnya banyak hasil $$$s$ untuk itu $$$X (s) = 1$ , yaitu, jika ht dan th adalah himpunan garis yang menunjukkan "elang" atau "ekor", maka

$$

$$E = {s \ dalam S: X (s) = 1}$$

dan

$$

$$= {ht, th}$$

ini adalah hasil dengan probabilitas $$$\ frac {1} {2}$ . Kami menulisnya sebagai $$$Pr \ {X = 1 \} = \ frac {1} {2}$ . Kami menggunakan predikat $$$X = 1$ sebagai entri singkat untuk hasil yang ditentukan oleh predikat.

Mari kita lihat fragmen kode yang mensimulasikan percobaan yang dijelaskan oleh rumus yang disajikan di atas:

headcount = 0 if (randb()): // first coin flip headcount++ if (randb()): // second coin flip headcount++ return headcount 

Di sini kita menunjukkan oleh ranb() fungsi Boolean yang mengembalikan true dalam setengah kasus. Bagaimana hubungannya dengan abstraksi kita? Bayangkan banyak $$$S$ semua kemungkinan eksekusi program, mendeklarasikan dua eksekusi nilai yang sama dikembalikan oleh ranb , identik berpasangan. Ini berarti bahwa ada empat kemungkinan eksekusi program di mana dua ranb() memanggil return TT, TF, FT, dan FF. Dari pengalaman kami sendiri, kami dapat mengatakan bahwa keempat pencapaian ini sama-sama memungkinkan, yaitu masing-masing terjadi pada sekitar seperempat kasus.

Sekarang analoginya menjadi lebih jelas. Banyaknya kemungkinan eksekusi suatu program dan probabilitas yang terkait dengannya adalah ruang probabilitas. Variabel program yang bergantung pada panggilan ranb adalah variabel acak. Saya harap semuanya jelas bagi Anda sekarang.

Mari kita bahas nilai yang diharapkan, juga disebut rata-rata. Ini pada dasarnya adalah jumlah produk PMF dan variabel acak:

$$

$$E [X] = \ sum_ {s \ in S} p (s) X (s)$$

Bayangkan bahwa h adalah "elang" dan t adalah "ekor". Kami sudah membahas ht dan th. Ada juga hh dan tt. Oleh karena itu, nilai yang diharapkan adalah sebagai berikut:

$$

$$E [X] = p (hh) X (hh) + p (ht) X (ht) + p (th) X (th) + p (tt) X (tt)$$

$$

$$= \ frac {1} {4}. 2 + \ frac {1} {4}. 1 + \ frac {1} {4}. 1 + \ frac {1} {4} .0$$

$$

$$= 1 \ text {QED}$$

Anda mungkin bertanya-tanya dari mana asalnya $$$X$ . Di sini saya maksudkan bahwa kita harus memberi makna $$$X$ sendiri Dalam hal ini, kami menetapkan h ke 1, dan t ke 0. $$$X (hh)$ sama dengan 2 karena mengandung 2 $$$h$ .

Mari kita bicara tentang distribusi. Distribusi probabilitas adalah fungsi yang memberikan probabilitas berbagai hasil dari suatu peristiwa.

Ketika kita mengatakan itu variabel acak $$$X$ memiliki distribusi $$$f$ maka harus menunjukkan $$$X \ sim f$ .

Nilai hamburan terakumulasi sekitar $$$X$ disebut dispersinya dan didefinisikan sebagai berikut:

$$

$$\ boldsymbol {Var} [X] = E [(X - \ bar {X}) ^ 2]$$

Dimana $$$\ bar {X}$ Apakah rata-rata $$$X$ .

$$$\ sqrt {\ boldsymbol {Var}}$ disebut standar deviasi . Variabel acak $$$X$ dan $$$Y$ disebut independen jika:

$$

$$Pr \ {X = x \ teks {dan} Y = y \} = Pr \ {X = x \}. Pr \ {Y = y \}$$

Properti penting dari variabel acak independen:

1. $$$E [XY] = E [X] E [Y]$
2. $$$\ boldsymbol {Var} [X + Y] = \ boldsymbol {Var} [X] + \ boldsymbol {Var} [Y]$

Ketika saya mulai dengan cerita tentang probabilitas, saya membandingkan probabilitas kontinu dan diskrit. Kami memeriksa probabilitas diskrit. Sekarang mari kita bicara tentang perbedaan antara probabilitas kontinu dan diskrit:

1. Nilai kontinu. Artinya, jumlahnya tidak terbatas.
2. Beberapa aspek analisis memerlukan kehalusan matematis seperti kemampuan terukur .
3. Ruang probabilitas kami akan menjadi tak terbatas. Alih-alih PMF, kita harus menggunakan fungsi densitas probabilitas (PDF).

Properti PDF:

1. Untuk masing-masing $$$s \ dalam S$ kami punya $$$p (s) \ geq 0$
2. $$$\ int_ {s \ dalam S} p (s) = 1$

Tetapi jika distribusinya $$$S$ merata , maka pdf didefinisikan seperti ini:


Dengan probabilitas berkelanjutan $$$E [X]$ didefinisikan sebagai berikut:

$$

$$E [X]: = \ int_ {s \ in S} p (s) X (s)$$

Sekarang bandingkan definisi PMF dan PDF:

$$

$$\ mathbb {PMF} \ rightarrow p_y (t) = Pr \ {Y = t \} \ text {for} t \ dalam T$$

$$

$$\ mathbb {PDF} \ rightarrow Pr \ {a \ leq X \ leq b \} = \ int_a ^ bp (r) dr$$

Dalam kasus probabilitas kontinu, variabel acak lebih baik disebut titik acak . Karena kalau $$$S$ Apakah ruang probabilitas, dan $$$Y: S \ rightarrow T$ ditampilkan dalam ruang yang berbeda dari $$$\ mathbb {R}$ maka kita harus menelepon $$$Y$ titik acak , bukan variabel acak. Konsep kepadatan probabilitas berlaku di sini, karena kita dapat mengatakannya untuk apa saja $$$U \ subset T$ kami memiliki:


Sekarang mari kita terapkan apa yang telah kita pelajari ke bola. Bola memiliki tiga koordinat: lintang, bujur, dan komplemen lintang. Kami menggunakan penambahan garis bujur dan lintang hanya di $$$\ mathbb {R} ^ 2$ , koordinat Kartesius dua dimensi diterapkan pada variabel acak $$$S$ ubah dia menjadi $$$S ^ 2$ . Kami mendapatkan detail berikut:

$$

$$Y: [0, 1] \ kali [0, 1] \ rightarrow S ^ 2: (u, v) \ rightarrow (\ cos (2 \ pi u) \ sin (\ pi v), \ cos (\ pi v) \ sin (2 \ pi u) sin (\ pi v))$$

Kami mulai dengan kepadatan probabilitas yang seragam $$$p$ di $$$[0, 1] \ kali [0, 1]$ , atau $$$p (u, v) = 1$ . Lihatlah rumus kepadatan probabilitas seragam di atas. Untuk kenyamanan, kami akan menulis $$$(x, y, z) = Y (u, v)$ .

Kami memiliki pemahaman intuitif bahwa jika Anda memilih titik secara merata dan acak dalam satuan persegi dan digunakan $$$f$ untuk mengubahnya menjadi titik pada unit sphere, mereka akan terakumulasi di sebelah kutub. Ini berarti bahwa kepadatan probabilitas yang diperoleh di $$$T$ tidak akan seragam. Ini ditunjukkan pada gambar di bawah ini.


Sekarang kita akan membahas cara untuk memperkirakan nilai yang diharapkan dari variabel acak kontinu dan aplikasinya untuk menentukan integral. Ini penting karena dalam rendering kita perlu menentukan nilai integral reflektifitas :

$$

$$L ^ {ref} (P, \ omega_o) = \ int _ {\ omega_i \ dalam S _ {+} ^ {2}} L (P, - \ omega_i) f_s (P, \ omega_i, \ omega_0) \ omega_i. \ boldsymbol {n} d \ omega_i,$$

untuk berbagai nilai $$$P$ dan $$$\ omega_0$ . Nilai $$$\ omega$ Apakah arah cahaya kejadian. Kode menghasilkan nomor acak yang terdistribusi secara merata dalam interval $$$[0, 1]$ dan mengambil akar kuadrat, menciptakan nilai dalam rentang dari 0 hingga 1. Jika kita menggunakan PDF untuk itu, karena ini adalah nilai yang seragam, maka nilai yang diharapkan akan sama $$$\ frac {2} {3}$ . Nilai ini juga merupakan nilai rata-rata $$$f (x) = \ sqrt {x}$ dalam interval ini. Apa artinya ini?

Pertimbangkan Teorema 3.48 dari buku Computer Graphics: Principles and Practice. Dia mengatakan itu jika $$$f: [a, b] \ rightarrow \ mathbb {R}$ adalah fungsi dengan nilai nyata, dan $$$X \ sim \ boldsymbol {U} (a, b)$ adalah variabel acak seragam dalam interval $$$[a, b]$ lalu $$$(b-a) f (x)$ Merupakan variabel acak yang nilainya diharapkan memiliki formulir:

$$

$$E [(b-a) f (x)] = \ int_a ^ b f (x) dx.$$

Apa yang dikatakan di sini kepada kita? Ini berarti Anda dapat menggunakan algoritma acak untuk menghitung nilai integral jika kami mengeksekusi kode berkali-kali dan rata-rata hasilnya .

Dalam kasus umum, kami mendapatkan nilai tertentu $$$C$ , seperti pada integral yang ditunjukkan di atas, yang perlu ditentukan, dan beberapa algoritma acak yang mengembalikan nilai perkiraan $$$C$ . Variabel acak untuk suatu kuantitas disebut estimator . Estimator dianggap bebas distorsi jika nilai yang diharapkan adalah $$$C$ . Dalam kasus umum, estimator tanpa distorsi lebih disukai daripada distorsi.

Kami telah membahas probabilitas diskrit dan berkesinambungan. Tetapi ada tipe ketiga, yang disebut probabilitas campuran dan digunakan dalam rendering. Probabilitas seperti itu muncul karena pulsa dalam fungsi distribusi hamburan dua arah, atau pulsa yang disebabkan oleh sumber titik penerangan. Probabilitas seperti itu didefinisikan dalam set kontinu, misalnya, dalam interval $$$[0, 1]$ tetapi tidak secara ketat ditentukan oleh fungsi PDF. Pertimbangkan program berikut:

 if uniform(0, 1) > 0.6 : return 0.3 else : return uniform(0, 1) 

Dalam enam puluh persen kasus, program akan mengembalikan 0,3, dan di 40% sisanya, itu akan mengembalikan nilai yang didistribusikan secara merata di $$$[0, 1]$ . Nilai kembali adalah variabel acak dengan massa probabilitas 0,6 pada 0,3, dan PDF-nya di semua titik lainnya ditetapkan sebagai $$$d (x) = 0,4$ . Kita harus mendefinisikan PDF sebagai:


Secara umum, variabel acak variabel campuran adalah variabel yang terdapat sejumlah titik terbatas di bidang definisi PDF, dan sebaliknya, titik yang terdistribusi seragam di mana PMF tidak didefinisikan.