Wahrscheinlichkeitstheorie für physikalisch genaues Rendern

Einleitung

Beim Rendern wird häufig die Berechnung mehrdimensionaler bestimmter Integrale verwendet: Zum Beispiel, um die Sichtbarkeit von räumlichen Lichtquellen (Flächenlicht), die den Pixelbereich erreichende Helligkeit, die über einen Zeitraum eintreffende Helligkeit und die durch die Halbkugel eines Oberflächenpunkts eintretende Strahlung zu bestimmen. Die Berechnung dieser Integrale erfolgt üblicherweise mit Hilfe der Monte-Carlo-Integration, bei der das Integral durch die Erwartung eines stochastischen Experiments ersetzt wird.

In diesem Artikel werde ich detailliert auf den grundlegenden Monte-Carlo-Integrationsprozess sowie auf verschiedene Techniken zur Reduzierung der Varianz der Technik eingehen. Dies erfolgt aus praktischer Sicht - es wird davon ausgegangen, dass der Leser mit der Wahrscheinlichkeitstheorie nicht sehr vertraut ist, aber dennoch effektive und korrekte Rendering-Algorithmen entwickeln möchte.

Definierte Integrale

Ein bestimmtes Integral ist ein Integral der Form $$$\ int_ {a} ^ {b} f (x) dx$ wo $$$[a, b]$ Ist ein Segment (oder eine Region), $$$x$ - Skalar und $$$f (x)$ - eine Funktion, die für jeden Punkt im Segment berechnet werden kann. Wie in Wikipedia geschrieben , ist ein bestimmtes Integral ein Bereich mit einem Zeichen in einer Ebene $$$x$ zeitlich begrenzt $$$f$ Achse $$$x$ und vertikale Linien $$$x = a$ und $$$x = b$ ( Abbildung 1a ).

Dieses Konzept erstreckt sich logischerweise auf eine größere Anzahl von Dimensionen: Für ein bestimmtes Doppelintegral wird der Bereich mit einem Vorzeichen zu einem Volumen mit einem Vorzeichen ( Abbildung 1b ), und für bestimmte Mehrfachintegrale wird es im Allgemeinen zu einem mehrdimensionalen Volumen mit einem Vorzeichen .


Abbildung 1: Beispiele für bestimmte Integrale.

In einigen Fällen kann die Fläche beispielsweise analytisch bestimmt werden , z $$$f (x) = 2$ : auf dem Segment $$$[a, b]$ Die Fläche wird gleich sein $$$2 (b-a)$ . In anderen Fällen ist eine analytische Lösung beispielsweise unmöglich, wenn wir das Volumen des Teils des Eisbergs über dem Wasser ermitteln müssen ( Abbildung 1c ). In solchen Fällen $$$f (x)$ oft kann durch Stichproben bestimmt werden.

Numerische Integration

Wir können die Fläche komplexer Integrale durch numerische Integration näherungsweise berechnen. Ein Beispiel ist die Riemannsche Summe . Dieser Betrag wird berechnet, indem die Fläche in regelmäßige Formen (z. B. Rechtecke) unterteilt wird, die zusammen eine Fläche bilden, die einer echten Fläche ähnlich ist. Die Riemannsche Summe ist wie folgt definiert:

$$

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

$$$n$ Ist die Anzahl der Unterintervalle und $$$\ Delta x_i = \ frac {b-a} {n}$ - die Breite eines Unterintervalls. Für jedes Intervall $$$i$ wir probieren $$$f$ an einem Punkt $$$x_i$ innerhalb des Unterintervalls (in Abbildung 2 befindet sich dieser Punkt am Anfang des Unterintervalls).


Abbildung 2: Riemann-Summe.

Es ist erwähnenswert, dass mit zunehmender $$$n$ die Riemannsche Summe konvergiert gegen den realen Wert des Integrals:

$$

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

Die Riemann-Summe kann auch für große Dimensionen verwendet werden ( Abbildung 3 ). Hier haben wir jedoch ein Problem: Für eine Funktion mit zwei Parametern sollte die Anzahl der Teilintervalle viel größer sein, wenn wir eine Auflösung erreichen wollen, die mit der im zweidimensionalen Fall verwendeten vergleichbar ist. Dieses Phänomen nennt man den Fluch der Dimensionen , und in höheren Dimensionen verschärft es sich.


Abbildung 3: Riemann-Summe für ein Doppelintegral.

Nun werden wir die Genauigkeit der Riemann-Summe für die folgende Funktion auswerten (wir haben absichtlich eine komplexe Funktion gewählt):

$$

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

Funktionsdiagramm für ein Segment $$$[- 2.5,2.5]$ unten gezeigt. Als Referenz haben wir ein bestimmtes Integral in Wolfram Alpha berechnet $$$\ int _ {- 2.5} ^ {2.5} f (x)$ Bereich bekommen $$$3.12970$ . Die Grafik rechts zeigt die Genauigkeit der numerischen Integration unter Verwendung der Riemann-Summe zur Erhöhung $$$n$ .


Abbildung 4: Funktionsgraph und Riemannsche Summengenauigkeit. Auch bei kleinen $$$n$ Wir erhalten ein ziemlich genaues Ergebnis.

Um sich ein Bild von der Genauigkeit zu machen, geben wir die Zahlen ein: z $$$n = 50$ der fehler ist $$$~ 2 \ times10 ^ {- 3}$ . Bei $$$n = 100$ der fehler ist $$$~ 3 \ times10 ^ {- 4}$ . Die folgende Größenordnung ergibt sich mit $$$n = 200$ .

Weitere Informationen zu Riemann-Beträgen finden Sie in den folgenden Ressourcen:

• 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)

Beim Rendern sind fast keine (und vielleicht überhaupt keine?) Integrale einzeln . Das heißt, wir werden schnell auf den Fluch der Dimensionen stoßen. Darüber hinaus ist das Abtasten einer Funktion in gleichen Intervallen nicht ausreichend abgetastet und verzerrt : Es können wichtige Werte der Funktion übersprungen oder ungewollte gegenseitige Interferenzen zwischen der abgetasteten Funktion und dem Abtastmuster auftreten ( Abbildung 5 ).


Abbildung 5: Verzerrungen führen zum Verlust von Teilen der abgetasteten Funktion (rot) und in diesem Fall zu einer völlig falschen Interpretation der Funktion.

Diese Probleme werden mit einer Technik namens Monte-Carlo-Integration gelöst. Ähnlich wie bei der Riemann-Summe wird auch bei einer Menge von Punkten eine Funktionsabtastung verwendet, aber im Gegensatz zum deterministischen Riemann-Summenmuster wird eine grundsätzlich nicht deterministische Zutat verwendet: Zufallszahlen.

Die Monte-Carlo-Integration basiert auf folgender Beobachtung: Das Integral kann durch die Erwartung eines stochastischen Experiments ersetzt werden:

$$

$$\ tag {4} \ int_ {a} ^ {b} f (x) dx = (ba) E \ left [f (X) \ right] \ ungefähr \ frac {ba} {n} \ sum_ {i = 1} ^ {n} f (X)$$

Mit anderen Worten, wir testen die Funktion $$$n$ Zeiten an zufälligen Punkten innerhalb eines Segments (bezeichnet mit einem Großbuchstaben) $$$X$ ), mittle die Abtastwerte und multipliziere mit der Breite des Segments (für eine eindimensionale Funktion). Wie im Fall der Riemannschen Summe, wenn $$$n$ bis unendlich konvergiert der Durchschnittswert der Abtastwerte zur Erwartung, dh zum wahren Wert des Integrals.

Ein bisschen Wahrscheinlichkeitstheorie

Es ist wichtig, jedes der hier verwendeten Konzepte zu verstehen. Beginnen wir mit dem Warten : Dies ist der Wert, der für eine einzelne Stichprobe erwartet wird. Beachten Sie, dass dies nicht unbedingt ein möglicher Wert ist, der möglicherweise nicht intuitiv zu sein scheint. Wenn wir zum Beispiel den Würfel werfen, ist die Erwartung gleich $$$3.5$ - der Durchschnitt aller möglichen Ergebnisse: $$$(1 + 2 + 3 + 4 + 5 + 6) /6=21/6=3.5$ .

Das zweite Konzept sind Zufallszahlen . Dies mag offensichtlich erscheinen, aber für die Monte-Carlo-Integration benötigen wir gleichmäßig verteilte Zufallszahlen, d.h. Jeder Wert sollte die gleiche Wahrscheinlichkeit der Erzeugung haben. Wir werden später mehr darüber sprechen.

Das dritte Konzept ist die Abweichung und die damit verbundene Varianz . Selbst wenn wir eine kleine Anzahl von Zahlen verwenden, sollten der erwartete Durchschnittswert sowie die Erwartung für jede einzelne Stichprobe gleich sein. Bei der Berechnung von Gleichung 4 erhalten wir jedoch selten einen solchen Wert. Abweichung ist der Unterschied zwischen der Erwartung und dem Ergebnis des Experiments: $$$X-E (X)$ .

In der Praxis hat diese Abweichung eine interessante Verteilung:


Dies ist ein Diagramm der Normalverteilung oder der Gaußschen Verteilung : Es zeigt, dass nicht alle Abweichungen gleich wahrscheinlich sind. Tatsächlich liegen ungefähr 68,2% der Proben im Bereich $$$-1 \ sigma..1 \ sigma$ wo $$$\ sigma$ (Sigma) ist die Standardabweichung . Die Standardabweichung kann auf zwei Arten beschrieben werden:

• Die Standardabweichung ist ein Maß für die Datenvariabilität .
• 95% der Datenpunkte liegen innerhalb $$$2 \ sigma$ vom Durchschnitt.

Es gibt zwei Methoden, um die Standardabweichung zu bestimmen:

1. Standardabweichung $$$\ sigma = \ sqrt {\ frac {1} {n} \ sum_ {i = 1} ^ {n} \ left (X_i-E \ left [X \ right] \ right) ^ 2}$ : Kann berechnet werden, wenn eine diskrete Wahrscheinlichkeitsverteilung vorliegt und die Erwartung bekannt ist $$$E [X]$ . Dies gilt für Würfel, in denen $$$X = {1,2,3,4,5,6}$ und $$$E [X] = 3.5$ . Wenn wir die Zahlen ersetzen, bekommen wir $$$\ sigma = 1.71$ .
2. Auch die Standardabweichung der Stichproben kann wie folgt berechnet werden $$$\ sigma = \ sqrt {\ frac {1} {n-1} \ sum_ {i = 1} ^ {n} \ left (X_i-X \ right) ^ 2}$ . Lesen Sie mehr dazu auf Wikipedia .

Überprüfen Sie: Ist das richtig? Wenn $$$\ sigma = 1.71$ erklären wir, dass 68,2% der Proben innerhalb von 1,71 von 3,5 liegen. Wir wissen das $$${2,3,4,5}$ dieses Kriterium erfüllen und $$$1$ und $$$6$ - Nein. Vier von sechs sind 66,7%. Wenn unser Würfel irgendeinen Wert in dem Intervall erzeugen könnte $$$[1..6]$ Dann würden wir genau 68,2% bekommen.

Anstelle der Standardabweichung wird das zugehörige Konzept der Varianz definiert als $$$Var \ left [X \ right] = \ sigma ^ 2$ . Da das Quadrat verwendet wird, ist die Varianz immer positiv, was bei den Berechnungen hilfreich ist.

Monte Carlo (2)

Oben haben wir Gleichung 3 mit der Riemann-Summe näherungsweise berechnet. Nun wiederholen wir dieses Experiment mit der Monte-Carlo-Integration. Denken Sie daran, dass die Monte-Carlo-Integration wie folgt definiert ist:

$$

$$\ tag {5} \ int_ {a} ^ {b} f (x) dx = (ba) E \ left [f (X) \ right] \ ungefähr \ frac {ba} {n} \ sum_ {i = 1} ^ {n} f (X)$$

Lassen Sie uns dies in C-Code übersetzen:

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

Ergebnis für Werte von $$$n = 2$ vorher $$$n = 200$ in der folgenden Tabelle gezeigt. Daraus ist zu schließen, dass die Monte-Carlo-Integration deutlich schlechter ausfällt als die Riemann-Summe. Eine genauere Betrachtung des Fehlers besagt, dass mit $$$n = 200$ der durchschnittliche Fehler der Riemann-Summe ist $$$0,0002$ und Monte Carlo $$$0.13$ .


Abbildung 6: Monte-Carlo-Fehler bei 2..200 Stichproben.

In höheren Dimensionen wird dieser Unterschied verringert, aber nicht vollständig beseitigt. Die unten gezeigte Gleichung ist eine erweiterte Version der oben verwendeten und empfängt zwei Parameter:

$$

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

Abbildung 7: Graph der obigen Gleichung.

Im Bereich der Definition $$$x∈ [-2,5,2,5], y∈ [-2,5,2,5]$ Volumen durch diese Funktion und Ebene begrenzt $$$xy$ ist gleich $$$6.8685$ . Bei $$$n = 400$ (20 × 20 Abtastwerte) ist der Fehler der Riemannschen Summe $$$0.043$ . Bei der gleichen Anzahl von Abtastwerten beträgt der durchschnittliche Monte-Carlo-Integrationsfehler $$$0,33$ . Dies ist besser als das vorherige Ergebnis, aber der Unterschied ist immer noch signifikant. Um dieses Problem zu verstehen, werden wir die bekannte Monte-Carlo-Integrationsdispersionsreduktionstechnik untersuchen, die als "Schichtung" bezeichnet wird.


Abbildung 8: Auswirkungen der Schichtung; a) Proben mit schlechter Verteilung; b) Proben mit gleichmäßiger Verteilung.

Durch die Schichtung wird die Einheitlichkeit der Zufallszahlen erhöht. In 8a werden acht Zufallszahlen verwendet, um die Funktion abzutasten. Da jede Zahl zufällig ausgewählt wird, stellt sich heraus, dass sie häufig ungleichmäßig über den Definitionsbereich verteilt sind. Abbildung 8b zeigt den Effekt der Schichtung: Der Definitionsbereich ist in acht Schichten unterteilt, und in jeder Schicht wird eine zufällige Position ausgewählt, wodurch die Gleichmäßigkeit verbessert wird.

Der Effekt auf die Varianz ist ziemlich offensichtlich. 9a zeigt eine grafische Darstellung der Ergebnisse mit und ohne Schichtung. Abbildung 9b zeigt den ungefähren Wertefehler. Bei $$$n = 10$ Der durchschnittliche Fehler für 8 Schichten ist $$$0.05$ ; für 20 Schichten - $$$0.07$ und für 200 Schichten sinkt es auf $$ . Aufgrund dieser Ergebnisse scheint es sinnvoll, eine große Anzahl von Streifen zu verwenden. Die Schichtung weist jedoch Nachteile auf, die mit zunehmender Anzahl von Schichten zunehmen. Erstens sollte die Anzahl der Stichproben immer ein Vielfaches der Anzahl der Schichten sein. zweitens leidet die Schichtung wie in der Riemannschen Summe unter dem Fluch der Dimensionen.


Abbildung 9: Schichtung und Varianz: a) ein ungefährer Wert für die Anzahl der Stichproben von n = 2 bis n = 200; b) Abweichung.

Beispiel für die Wichtigkeit

In den vorherigen Abschnitten haben wir die Gleichungen gleichmäßig abgetastet. Die Erweiterung der Integrationsfunktion von Monte Carlo ermöglicht es uns, die Situation zu ändern:

$$

$$\ tag {7} \ int_ {a} ^ {b} f (x) dx = (ba) E \ left [f (X) \ right] \ ungefähr \ frac {ba} {n} \ sum_ {i = 1} ^ {n} \ frac {f (X)} {p (X)}$$

Hier $$$p (X)$ Ist eine Wahrscheinlichkeitsdichtefunktion (pdf) : Sie bestimmt die relative Wahrscheinlichkeit, dass eine Zufallsvariable einen bestimmten Wert annimmt.

Für eine einheitliche Zufallsvariable im Intervall $$$0..1$ , pdf ist 1 ( Abbildung 10 a), und dies bedeutet, dass jeder Wert die gleiche Wahrscheinlichkeit der Wahl hat. Wenn wir diese Funktion über integrieren $$$[0,0.5]$ dann bekommen wir die Wahrscheinlichkeit in $$$0.5$ von was $$$X <\ frac {1} {2}$ . Für $$$X> \ frac {1} {2}$ Wir haben offensichtlich die gleiche Wahrscheinlichkeit.


Abbildung 10: Wahrscheinlichkeitsverteilungen. a) Konstante pdf, bei der jede Stichprobe die gleiche Wahrscheinlichkeit der Wahl hat; b) pdf, wenn Stichproben unter 0,5 eine höhere Selektionswahrscheinlichkeit haben.

Abbildung 10b zeigt ein weiteres PDF. In diesem Fall ist die Wahrscheinlichkeit, eine Zahl zu erzeugen, geringer $$$\ frac {1} {2}$ gleich 70%. Dies kann mit dem folgenden Code-Snippet implementiert werden:

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

Dieses PDF ist wie folgt definiert:

$$

$$\ tag {8} p (x) = \ left \ {\ begin {matrix} 1.4, wenn x <\ frac {1} {2} \\ 0.6, andernfalls \ end {matrix} \ right.$$

Die zahlen $$$1.4$ und $$$0.6$ reflektieren die Notwendigkeit dieser Wahrscheinlichkeit $$$x <\ frac {1} {2}$ war gleich 70%. Bei der Integration von PDF von $$$[0 .. \ frac {1} {2}]$ gibt $$$1.4 \ times \ frac {1} {2}$ und $$$0.6 \ times \ frac {1} {2}$ gleich $$$0.3$ . Dies zeigt eine wichtige Anforderung für alle PDFs im Allgemeinen: Das Ergebnis der PDF-Integration sollte 1 sein. Eine weitere Anforderung ist die folgende $$$p (x)$ kann nicht null sein, wenn $$$f (x)$ ungleich null: es würde bedeuten, dass die teile $$$f$ haben eine Stichprobenwahrscheinlichkeit von Null, was sich offensichtlich auf den Wert auswirkt.

Einige Tipps zum Verständnis des PDF-Konzepts:

• Ein PDF-Wert beschreibt nicht die Wahrscheinlichkeit: Daher kann das lokale PDF größer als 1 sein (z. B. wie im gerade untersuchten PDF).
• Das Integral über den Definitionsbereich von pdf ist jedoch eine Wahrscheinlichkeit, was bedeutet, dass die Integration von pdf 1 ergibt.

Ein Wert kann als relative Möglichkeit des Auftretens eines bestimmten Werts interpretiert werden.

Es ist zu bedenken, dass die Normalverteilung eine Wahrscheinlichkeitsverteilungsfunktion ist: Sie gibt uns die Wahrscheinlichkeit, dass sich eine Zufallsvariable in einem bestimmten Intervall befindet. Bei einer Normalverteilung ist diese Zufallsvariable eine Abweichung vom Mittelwert. Wie bei jedem anständigen PDF ist das Ergebnis der Integration der Normalverteilung 1.

Daher können wir mit Gleichung 7 eine ungleichmäßige Abtastung durchführen. Sie kompensiert dies, indem sie jede Stichprobe durch die relative Wahrscheinlichkeit ihrer Wahl dividiert. Wie wichtig dies ist, zeigt Abbildung 11a . Der Funktionsgraph zeigt ein signifikantes Intervall, in dem sein Wert liegt $$$0$ . Das Abtasten in diesem Bereich ist sinnlos: Der Summe wird nichts hinzugefügt, wir teilen einfach durch eine größere Zahl. Denken Sie an den Eisberg aus Abbildung 1c : Es macht keinen Sinn, die Höhe in einem großen Bereich um den Eisberg zu messen.


Abbildung 11: pdf für eine Funktion mit Nullwerten.

Ein PDF mit dieser Kenntnis der Funktion ist in Abbildung 11b dargestellt . Beachten Sie, dass dieses PDF für den Wertebereich tatsächlich Null ist. Dies macht es nicht zu einem falschen PDF: An manchen Stellen ist die Funktion Null. Wir können diese Idee über Null hinaus erweitern. Die Proben werden am besten an den Stellen ausgegeben, an denen die Funktion signifikante Werte aufweist. Tatsächlich ist das ideale PDF proportional zur abgetasteten Funktion . Ein sehr gutes PDF für unsere Funktion ist in Abbildung 12a dargestellt . Ein noch besseres PDF wird in Abbildung 12b gezeigt . In beiden Fällen dürfen wir nicht vergessen, es so zu normalisieren , dass das Integral gleich 1 ist.


Abbildung 12: Erweitertes PDF für die Funktion in Abbildung 11.

Das PDF in Abbildung 12 stellt uns vor zwei Aufgaben:

1. Wie erstelle ich ein solches PDF?
2. wie man ein solches pdf probiert?

Die Antwort auf beide Fragen ist die gleiche: Wir brauchen das nicht zu tun. In vielen Fällen ist die Funktion, die wir integrieren möchten, unbekannt, und die einzige Möglichkeit, die Stellen zu bestimmen, an denen sie von Bedeutung ist, besteht darin, sie abzutasten. Dazu benötigen wir PDF-Dateien. klassische Situation von "Hühnchen und Eiern".

In anderen Fällen haben wir jedoch eine ungefähre Vorstellung davon, wo die Funktion höhere Werte oder Nullwerte liefern kann. In solchen Fällen ist ein sehr raues PDF oft besser als kein PDF.

Möglicherweise haben wir auch die Möglichkeit, PDFs im laufenden Betrieb zu erstellen. Einige Beispiele geben eine Vorstellung von der Form der Funktion, und auf deren Grundlage richten wir die nachfolgenden Beispiele an die Stellen, an denen wir hohe Werte erwarten, die wir zur Verbesserung von PDF-Dateien usw. verwenden.

Im nächsten Artikel wenden wir diese Konzepte auf die Rendering-Implementierung an. Eine ernsthafte Herausforderung ist das Erstellen von PDF. Wir untersuchen mehrere Fälle, in denen pdfs bei der Stichprobenauswahl hilfreich ist.