Monte-Carlo-Integrationsanwendung beim Rendern

Wir alle haben im Laufe der Mathematik numerische Methoden studiert. Dies sind Methoden wie Integration, Interpolation, Reihen usw. Es gibt zwei Arten numerischer Methoden: deterministische und randomisierte.

Typische Methode zur Integration deterministischer Funktionen $$$f$im Bereich $$$[a, b]$Es sieht so aus: Wir nehmen $$$n + 1$gleichmäßig verteilte Punkte $$$t_0 = a, t_1 = a + \ frac {b - a} {n}, \ ldots, t_n - b$berechnen $$$f$in der Mitte $$$\ frac {t_i + t_ {i + 1}} {2}$Fassen Sie von jedem der durch diese Punkte definierten Intervalle die Ergebnisse zusammen und multiplizieren Sie sie mit der Breite jedes Intervalls $$$\ frac {b -a} {b}$. Für ausreichend kontinuierliche Funktionen $$$f$mit zunehmender $$$n$Das Ergebnis konvergiert auf den richtigen Wert.


Die probabilistische Methode oder die Monte-Carlo- Methode zur Berechnung oder genauer eine ungefähre Schätzung des Integrals $$$f$im Bereich $$$[a, b]$sieht so aus: lass $$$X_1, \ ldots, X_n$- zufällig ausgewählte Punkte im Intervall $$$[a, b]$. Dann $$$Y = (b - a) \ frac {1} {n} \ sum_ {i = 1} ^ {n} f (X_i)$Ist ein Zufallswert, dessen Durchschnitt ein Integral ist $$$\ int _ {[a, b]} f$. Um die Methode zu implementieren, verwenden wir einen Zufallszahlengenerator, der generiert $$$n$Punkte im Intervall $$$[a, b]$wir berechnen in jedem $$$f$, mittle die Ergebnisse und multipliziere mit $$$b-a$. Dies gibt uns den ungefähren Wert des Integrals, wie in der folgenden Abbildung gezeigt. $$$\ int _ {- 1} ^ {1} \ sqrt {1 - x ^ 2} dx$mit 20 Proben entspricht ungefähr das korrekte Ergebnis gleich $$$\ frac {\ pi} {2}$.


Natürlich erhalten wir jedes Mal, wenn wir einen solchen ungefähren Wert berechnen, ein anderes Ergebnis. Die Varianz dieser Werte hängt von der Form der Funktion ab. $$$f$. Wenn wir zufällige Punkte generieren $$$x_i$ungleichmäßig müssen wir dann die Formel leicht ändern. Dank der ungleichmäßigen Punkteverteilung erhalten wir jedoch einen großen Vorteil: Wir zwingen die ungleichmäßige Verteilung dazu, den Punkten den Vorzug zu geben $$$x_i$wo $$$f (x)$groß, können wir die Varianz der ungefähren Werte signifikant reduzieren. Dieses Prinzip der ungleichmäßigen Probenahme wird als Probenahme nach Signifikanz bezeichnet .


Da in den letzten Jahrzehnten in Rendering-Techniken ein groß angelegter Übergang von deterministischen zu randomisierten Ansätzen stattgefunden hat, werden wir die randomisierten Ansätze untersuchen, die zur Lösung von Rendering-Gleichungen verwendet werden. Dazu verwenden wir Zufallsvariablen, mathematische Erwartungen und Varianz. Wir haben es mit diskreten Werten zu tun, weil Computer diskreter Natur sind. Kontinuierliche Größen befassen sich mit der Wahrscheinlichkeitsdichtefunktion , werden jedoch im Artikel nicht berücksichtigt. Wir werden über die Wahrscheinlichkeitsmassenfunktion sprechen. PMF hat zwei Eigenschaften:

1. Für jeden $$$s \ in S$existiert $$$p (s) \ geq 0$.
2. $$$\ sum_ {s \ in S} p (s) = 1$

Die erste Eigenschaft heißt Nicht-Negativität. Die zweite heißt "Normalität". Intuitiv das $$$S$stellt die Menge der Ergebnisse eines Experiments dar, und $$$p (s)$Ist das Ergebnis der Wahrscheinlichkeit $$$s$Mitglied $$$S$. Das Ergebnis ist eine Teilmenge des Wahrscheinlichkeitsraums. Die Wahrscheinlichkeit eines Ergebnisses ist die Summe der PMF-Elemente dieses Ergebnisses, da

$$

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

Eine Zufallsvariable ist eine Funktion, die normalerweise durch einen Großbuchstaben gekennzeichnet ist und reelle Zahlen in den Wahrscheinlichkeitsraum einfügt:

$$

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

Beachten Sie, dass die Funktion $$$X$- Dies ist keine Variable, sondern eine Funktion mit reellen Werten. Sie ist auch nicht zufällig , $$$X (s)$Ist eine separate reelle Zahl für jedes Ergebnis $$$s \ in S$.

Eine Zufallsvariable wird verwendet, um die Ergebnisse zu bestimmen. Zum Beispiel viele Ergebnisse $$$s$für welche $$$X (s) = 1$Das heißt, wenn ht und th die Reihe von Linien sind, die "Adler" oder "Schwänze" bezeichnen, dann

$$

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

und

$$

$$= {ht, th}$$

es ist ein Ergebnis mit Wahrscheinlichkeit $$$\ frac {1} {2}$. Wir schreiben es als $$$Pr \ {X = 1 \} = \ frac {1} {2}$ . Wir verwenden das Prädikat $$$X = 1$als verkürzter Eintrag für das vom Prädikat bestimmte Ergebnis.

Schauen wir uns ein Codefragment an, das ein Experiment simuliert, das durch die oben dargestellten Formeln beschrieben wird:

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

Hier bezeichnen wir mit ranb() Boolesche Funktion, die in der Hälfte der Fälle true zurückgibt. Wie hängt es mit unserer Abstraktion zusammen? Stell dir viel vor $$$S$Alle möglichen Ausführungen des Programms, wobei zwei Ausführungen mit denselben Werten ranb , die von ranb , paarweise identisch. Dies bedeutet, dass es vier mögliche Ausführungen des Programms gibt, in denen zwei ranb() -Aufrufe TT, TF, FT und FF zurückgeben. Aus eigener Erfahrung können wir sagen, dass diese vier Leistungen gleich wahrscheinlich sind, dh jeweils in etwa einem Viertel der Fälle auftreten.

Jetzt wird die Analogie klarer. Die vielen möglichen Ausführungen eines Programms und die damit verbundenen Wahrscheinlichkeiten sind ein Wahrscheinlichkeitsraum. Programmvariablen, die von ranb Aufrufen abhängen, sind Zufallsvariablen. Ich hoffe dir ist jetzt alles klar.

Lassen Sie uns den erwarteten Wert diskutieren, der auch als Durchschnitt bezeichnet wird. Dies ist im Wesentlichen die Summe des Produkts aus PMF und einer Zufallsvariablen:

$$

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

Stellen Sie sich vor, h sind "Adler" und t sind "Schwänze". Wir haben bereits ht und th behandelt. Es gibt auch hh und tt. Daher ist der erwartete Wert wie folgt:

$$

$$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}$$

Sie fragen sich vielleicht, woher es kam $$$X$. Hier meinte ich, wir sollten Bedeutung zuweisen $$$X$von dir selbst. In diesem Fall haben wir h 1 und t 0 zugewiesen. $$$X (hh)$gleich 2, weil es 2 enthält $$$h$.

Sprechen wir über die Verteilung. Die Wahrscheinlichkeitsverteilung ist eine Funktion, die die Wahrscheinlichkeiten verschiedener Ergebnisse eines Ereignisses angibt.

Wenn wir sagen, dass eine Zufallsvariable $$$X$hat eine Verteilung $$$f$dann sollte anzeigen $$$X \ sim f$.

Streuwerte haben sich angesammelt $$$X$heißt seine Dispersion und ist wie folgt definiert:

$$

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

Wo $$$\ bar {X}$Ist durchschnittlich $$$X$.

$$$\ sqrt {\ boldsymbol {Var}}$Standardabweichung genannt . Zufällige Variablen $$$X$und $$$Y$werden als unabhängig bezeichnet, wenn:

$$

$$Pr \ {X = x \ text {und} Y = y \} = Pr \ {X = x \}. Pr \ {Y = y \}$$

Wichtige Eigenschaften unabhängiger Zufallsvariablen:

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

Als ich mit einer Geschichte über die Wahrscheinlichkeit begann, verglich ich kontinuierliche und diskrete Wahrscheinlichkeiten. Wir haben die diskrete Wahrscheinlichkeit untersucht. Lassen Sie uns nun über den Unterschied zwischen kontinuierlichen und diskreten Wahrscheinlichkeiten sprechen:

1. Die Werte sind kontinuierlich. Das heißt, die Zahlen sind unendlich.
2. Einige Aspekte der Analyse erfordern mathematische Feinheiten wie die Messbarkeit .
3. Unser Wahrscheinlichkeitsraum wird unendlich sein. Anstelle von PMF sollten wir die Wahrscheinlichkeitsdichtefunktion (PDF) verwenden.

PDF-Eigenschaften:

1. Für jeden $$$s \ in S$wir haben $$$p (s) \ geq 0$
2. $$$\ int_ {s \ in S} p (s) = 1$

Aber wenn die Verteilung $$$S$gleichmäßig , dann ist das pdf wie folgt definiert:


Mit kontinuierlicher Wahrscheinlichkeit $$$E [X]$wie folgt definiert:

$$

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

Vergleichen Sie nun die Definitionen von PMF und PDF:

$$

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

$$

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

Bei kontinuierlicher Wahrscheinlichkeit werden Zufallsvariablen besser als Zufallspunkte bezeichnet . Denn wenn $$$S$Ist der Wahrscheinlichkeitsraum und $$$Y: S \ rightarrow T$in einem anderen Raum als angezeigt $$$\ mathbb {R}$dann sollten wir anrufen $$$Y$zufälliger Punkt , keine zufällige Variable. Das Konzept der Wahrscheinlichkeitsdichte ist hier anwendbar, weil wir das für jeden sagen können $$$U \ Teilmenge T$wir haben:


Wenden wir nun das Gelernte auf die Sphäre an. Die Kugel hat drei Koordinaten: Breitengrad, Längengrad und Breitengradkomplement. Wir verwenden Längen- und Breitengradaddition nur in $$$\ mathbb {R} ^ 2$zweidimensionale kartesische Koordinaten, die auf eine Zufallsvariable angewendet werden $$$S$mach sie zu $$$S ^ 2$. Wir erhalten folgendes Detail:

$$

$$Y: [0, 1] \ times [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))$$

Wir beginnen mit einer einheitlichen Wahrscheinlichkeitsdichte $$$p$bei $$$[0, 1] \ times [0, 1]$oder $$$p (u, v) = 1$. Schauen Sie sich die Formel für die einheitliche Wahrscheinlichkeitsdichte oben an. Der Einfachheit halber werden wir schreiben $$$(x, y, z) = Y (u, v)$.

Wir haben ein intuitives Verständnis dafür, dass, wenn Sie Punkte gleichmäßig und zufällig in einem Einheitsquadrat auswählen und verwenden $$$f$Um sie in Punkte auf einer Einheitskugel umzuwandeln, sammeln sie sich neben dem Pol an. Dies bedeutet, dass die erhaltene Wahrscheinlichkeitsdichte in $$$T$wird nicht einheitlich sein. Dies ist in der folgenden Abbildung dargestellt.


Nun werden wir Möglichkeiten diskutieren, den erwarteten Wert einer kontinuierlichen Zufallsvariablen zu approximieren und ihre Anwendung zur Bestimmung der Integrale. Dies ist wichtig, da beim Rendern der Wert des Reflektivitätsintegrals bestimmt werden muss :

$$

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

für verschiedene Werte $$$P$und $$$\ omega_0$. Wert $$$\ omega$Ist die Richtung des einfallenden Lichts. Code, der eine Zufallszahl erzeugt, die gleichmäßig im Intervall verteilt ist $$$[0, 1]$Wenn Sie die Quadratwurzel ziehen, wird ein Wert im Bereich von 0 bis 1 erstellt. Wenn wir PDF dafür verwenden, ist der erwartete Wert gleich, da dies ein einheitlicher Wert ist $$$\ frac {2} {3}$. Auch dieser Wert ist der Durchschnittswert $$$f (x) = \ sqrt {x}$in diesem Intervall. Was bedeutet das?

Betrachten Sie Satz 3.48 aus dem Buch Computergrafik: Prinzipien und Praxis. Sie sagt das wenn $$$f: [a, b] \ rightarrow \ mathbb {R}$ist eine Funktion mit reellen Werten und $$$X \ sim \ boldsymbol {U} (a, b)$ist eine einheitliche Zufallsvariable im Intervall $$$[a, b]$dann $$$(b-a) f (x)$Ist eine Zufallsvariable, deren erwarteter Wert die Form hat:

$$

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

Was sagt uns das? Dies bedeutet, dass Sie einen zufälligen Algorithmus verwenden können, um den Wert des Integrals zu berechnen, wenn wir den Code viele Male ausführen und die Ergebnisse mitteln .

Im allgemeinen Fall erhalten wir einen bestimmten Wert $$$C$, wie im oben gezeigten Integral, das bestimmt werden muss, und einem zufälligen Algorithmus, der einen ungefähren Wert zurückgibt $$$C$. Eine solche Zufallsvariable für eine Größe wird als Schätzer bezeichnet . Ein Schätzer gilt als verzerrungsfrei, wenn sein erwarteter Wert ist $$$C$. Im allgemeinen Fall sind Schätzer ohne Verzerrungen Verzerrungen vorzuziehen.

Wir haben bereits diskrete und kontinuierliche Wahrscheinlichkeiten diskutiert. Es gibt jedoch einen dritten Typ, der als gemischte Wahrscheinlichkeiten bezeichnet wird und beim Rendern verwendet wird. Solche Wahrscheinlichkeiten entstehen aufgrund von Impulsen in den Verteilungsfunktionen der bidirektionalen Streuung oder von Impulsen, die durch Punktbeleuchtungsquellen verursacht werden. Solche Wahrscheinlichkeiten werden beispielsweise im Intervall in einer kontinuierlichen Menge definiert $$$[0, 1]$aber nicht streng durch die PDF-Funktion definiert. Betrachten Sie das folgende Programm:

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

In sechzig Prozent der Fälle gibt das Programm 0,3 zurück, und in den restlichen 40 Prozent gibt es einen Wert zurück, der gleichmäßig verteilt ist $$$[0, 1]$. Der Rückgabewert ist eine Zufallsvariable mit einer Wahrscheinlichkeitsmasse von 0,6 bei 0,3, und das PDF an allen anderen Punkten wird als angegeben $$$d (x) = 0,4$. Wir müssen das PDF definieren als:


Im Allgemeinen ist eine Zufallsvariable mit gemischten Variablen eine Variable, für die es im PDF-Definitionsbereich eine endliche Menge von Punkten gibt, und umgekehrt gleichmäßig verteilte Punkte, an denen die PMF nicht definiert ist.