Théorie des probabilités pour un rendu physiquement précis

Présentation

Dans le rendu, le calcul d'intégrales définies multidimensionnelles est souvent utilisé: par exemple, pour déterminer la visibilité des sources lumineuses spatiales (lumière de zone), la luminosité atteignant la région des pixels, la luminosité arrivant sur une période de temps et l'irradiation pénétrant à travers l'hémisphère d'un point de surface. Le calcul de ces intégrales est généralement effectué à l'aide de l'intégration de Monte Carlo, dans laquelle l'intégrale est remplacée par l'attente d'une expérience stochastique.

Dans cet article, je parlerai en détail du processus d'intégration de base de Monte Carlo, ainsi que de plusieurs techniques pour réduire la variance de la technique. Cela se fera d'un point de vue pratique - on suppose que le lecteur n'est pas très familier avec la théorie des probabilités, mais souhaite toujours développer des algorithmes de rendu efficaces et corrects.

Intégrales définies

Une intégrale définie est une intégrale de la forme $$$\ int_ {a} ^ {b} f (x) dx$ où $$$[a, b]$ Est un segment (ou une région), $$$x$ - scalaire, et $$$f (x)$ - une fonction qui peut être calculée pour n'importe quel point du segment. Comme écrit dans Wikipedia , une certaine intégrale est une zone avec un signe sur un avion $$$x$ limité par le calendrier $$$f$ axe $$$x$ et lignes verticales $$$x = a$ et $$$x = b$ ( Figure 1a ).

Ce concept s'étend logiquement à un plus grand nombre de dimensions: pour une certaine double intégrale, la zone avec un signe devient un volume avec un signe ( figure 1b ), et en général pour certaines intégrales multiples, elle devient un volume multidimensionnel avec un signe .


Figure 1: exemples de certaines intégrales.

Dans certains cas, la zone peut être déterminée analytiquement , par exemple, pour $$$f (x) = 2$ : sur le segment $$$[a, b]$ la surface sera égale $$ . Dans d'autres cas, une solution analytique est impossible, par exemple, lorsque nous devons connaître le volume de la partie de l'iceberg au-dessus de l'eau ( figure 1c ). Dans de tels cas $$$f (x)$ peuvent souvent être déterminés par échantillonnage .

Intégration numérique

Nous pouvons approximativement calculer l'aire des intégrales complexes en utilisant l'intégration numérique . Un exemple est la somme de Riemann . Ce montant est calculé en divisant la zone en formes régulières (par exemple, des rectangles), qui forment ensemble une zone similaire à une vraie zone. La somme de Riemann est définie comme suit:

$$

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

$$$n$ Est le nombre de sous-intervalles, et $$$\ Delta x_i = \ frac {b-a} {n}$ - la largeur d'un sous-intervalle. Pour chaque intervalle $$$i$ nous goûtons $$$f$ à un moment donné $$$x_i$ à l'intérieur du sous-intervalle (dans la figure 2, ce point est au début du sous-intervalle).


Figure 2: somme de Riemann.

Il convient de noter qu’au $$$n$ la somme de Riemann converge vers la valeur réelle de l'intégrale:

$$

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

La somme de Riemann peut également être utilisée pour de grandes dimensions ( figure 3 ). Cependant, nous sommes ici confrontés à un problème: pour une fonction à deux paramètres, le nombre de sous-intervalles doit être beaucoup plus important si nous voulons obtenir une résolution comparable à celle utilisée dans le cas bidimensionnel. Ce phénomène est appelé la malédiction des dimensions et, dans les dimensions supérieures, il est exacerbé.


Figure 3: somme de Riemann pour une intégrale double.

Nous allons maintenant évaluer la précision de la somme de Riemann pour la fonction suivante (nous avons intentionnellement choisi une fonction complexe):

$$

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

Graphique de fonction sur un segment $$$[- 2,5,2,5]$ montré ci-dessous. Pour référence, nous avons calculé une certaine intégrale dans Wolfram Alpha $$$\ int _ {- 2.5} ^ {2.5} f (x)$ obtenir la zone $$$3.12970$ . Le graphique de droite montre la précision de l'intégration numérique en utilisant la somme de Riemann pour augmenter $$$n$ .


Figure 4: Graphique de fonction et précision de somme de Riemann. Même avec de petites $$$n$ nous obtenons un résultat assez précis.

Pour avoir une idée de la précision, nous donnons les chiffres: pour $$$n = 50$ l'erreur est $$$~ 2 \ times10 ^ {- 3}$ . À $$$n = 100$ l'erreur est $$$~ 3 \ times10 ^ {- 4}$ . L'ordre de grandeur suivant est obtenu avec $$$n = 200$ .

Pour plus d'informations sur les montants Riemann, consultez les ressources suivantes:

• Académie de Kahn: https://www.khanacademy.org/math/ap-calculus-ab/ab-accumulation-riemann-sums/ab-riemann-sums/v/simple-riemann-approximation-using-rectangles
• Wikipédia: https://en.wikipedia.org/wiki/Riemann_sum

Monte-Carlo (1)

Lors du rendu, presque aucune (et peut-être aucune?) Les intégrales sont uniques . Cela signifie que nous rencontrerons rapidement la malédiction des dimensions. De plus, l'échantillonnage d'une fonction à intervalles égaux est soumis à un échantillonnage et une distorsion insuffisants : nous pouvons ignorer des valeurs importantes de la fonction ou obtenir des interférences mutuelles involontaires entre la fonction échantillonnée et le motif d'échantillonnage ( figure 5 ).


Figure 5: les distorsions conduisent à la perte de parties de la fonction échantillonnée (rouge) et, dans ce cas, à une interprétation complètement incorrecte de la fonction.

Ces problèmes sont résolus à l'aide d'une technique appelée intégration Monte Carlo . Semblable à la somme de Riemann, il utilise également l'échantillonnage de fonction à un ensemble de points, mais contrairement au modèle de somme déterministe de Riemann, nous utilisons un ingrédient fondamentalement non déterministe : les nombres aléatoires.

L'intégration de Monte Carlo est basée sur l'observation suivante: l'intégrale peut être remplacée par l' attente d'une expérience stochastique:

$$

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

En d'autres termes, nous échantillonnons la fonction $$$n$ fois à des points aléatoires dans un segment (dénoté par une majuscule $$$X$ ), faire la moyenne des échantillons et multiplier par la largeur du segment (pour une fonction unidimensionnelle). Comme dans le cas de la somme de Riemann, lorsque $$$n$ à l'infini, la valeur moyenne des échantillons converge vers l'attente, c'est-à-dire vers la vraie valeur de l'intégrale.

Un peu de théorie des probabilités

Il est important de comprendre chacun des concepts utilisés ici. Commençons par l' attente : c'est la valeur attendue pour un seul échantillon. Notez que ce n'est pas nécessairement une valeur possible , ce qui peut sembler contre-intuitif. Par exemple, lorsque nous lançons le dé, l'attente est égale à $$ - la moyenne de tous les résultats possibles: $$$(1 + 2 + 3 + 4 + 5 + 6) /6=21/6=3.5$ .

Le deuxième concept est celui des nombres aléatoires . Cela peut sembler évident, mais pour l'intégration de Monte Carlo, nous avons besoin de nombres aléatoires uniformément distribués, c'est-à-dire chaque valeur doit avoir une probabilité égale de génération. Nous en reparlerons plus tard.

Le troisième concept est l' écart et la variance qui lui est associée. Même lorsque nous prenons un petit nombre de chiffres, la valeur moyenne attendue, ainsi que les attentes de chaque échantillon individuel, devraient être les mêmes. Cependant, lors du calcul de l' équation 4, nous obtenons rarement une telle valeur. L'écart est la différence entre l'attente et le résultat de l'expérience: $$$X-E (X)$ .

En pratique, cet écart a une distribution intéressante:


Il s'agit d'un graphique de la distribution normale , ou distribution gaussienne : il montre que toutes les déviations ne sont pas également probables. En fait, environ 68,2% des échantillons se situent dans la plage $$$-1 \ sigma..1 \ sigma$ où $$$\ sigma$ (sigma) est l' écart type . L'écart type peut être décrit de deux manières:

• L'écart type est une mesure de la variabilité des données.
• 95% des points de données se trouvent dans $$$2 \ sigma$ de la moyenne.

Il existe deux méthodes pour déterminer l'écart type:

1. Écart type $$$\ sigma = \ sqrt {\ frac {1} {n} \ sum_ {i = 1} ^ {n} \ left (X_i-E \ left [X \ right] \ right) ^ 2}$ : il peut être calculé s'il existe une distribution de probabilité discrète et que l'espérance est connue $$$E [X]$ . Cela est vrai pour les cubes dans lesquels $$$X = {1,2,3,4,5,6}$ et $$$E [X] = 3,5$ . En substituant les chiffres, nous obtenons $$$\ sigma = 1,71$ .
2. De plus, l'écart type des échantillons peut être calculé comme $$$\ sigma = \ sqrt {\ frac {1} {n-1} \ sum_ {i = 1} ^ {n} \ left (X_i-X \ right) ^ 2}$ . En savoir plus sur Wikipédia .

Vérifier: est-ce correct? Si $$$\ sigma = 1,71$ , nous déclarons que 68,2% des échantillons sont à moins de 1,71 sur 3,5. Nous savons que $$${2,3,4,5}$ satisfaire à ce critère, et $$$1$ et $$ - non. Quatre sur six représentent 66,7%. Si notre cube pouvait produire n'importe quelle valeur dans l'intervalle $$$[1..6]$ , alors nous obtiendrions exactement 68,2%.

Au lieu de l'écart-type, le concept de variance associé, qui est défini comme $$$Var \ left [X \ right] = \ sigma ^ 2$ . Puisque le carré est utilisé, la variance est toujours positive, ce qui facilite les calculs.

Monte-Carlo (2)

Ci-dessus, nous avons approximativement calculé l' équation 3 en utilisant la somme de Riemann. Maintenant, nous répétons cette expérience avec l'intégration Monte Carlo. Rappelons que l'intégration de Monte Carlo est définie comme suit:

$$

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

Traduisons cela en code C:

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

Résultat pour les valeurs de $$$n = 2$ avant $$$n = 200$ montré dans le tableau ci-dessous. On peut en déduire que l'intégration de Monte-Carlo se manifeste bien pire que la somme de Riemann. Un examen plus approfondi de l'erreur indique qu'avec $$$n = 200$ l'erreur moyenne de la somme de Riemann est $$ et Monte Carlo $$ .


Figure 6: erreur de Monte Carlo à 2..200 échantillons.

Dans les dimensions supérieures, cette différence est réduite, mais pas complètement éliminée. L'équation ci-dessous est une version étendue de celle utilisée ci-dessus, recevant deux paramètres:

$$

$$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 \ gauche (2,3x \ droite) \ droite | (6)$$

Figure 7: Graphique de l'équation ci-dessus.

Dans le domaine de la définition $$$x∈ [-2,5,2,5], y∈ [-2,5,2,5]$ volume limité par cette fonction et ce plan $$$xy$ est égal $$ . À $$$n = 400$ (20 × 20 échantillons) l'erreur de la somme de Riemann est $$ . Avec le même nombre d'échantillons, l'erreur d'intégration moyenne de Monte Carlo est $$ . C'est mieux que le résultat précédent, mais la différence est toujours significative. Pour comprendre ce problème, nous étudierons la technique bien connue de réduction de dispersion d'intégration Monte Carlo appelée «stratification».


Figure 8: impact de la stratification; a) échantillons avec une mauvaise distribution; b) échantillons à distribution uniforme.

La stratification augmente l' uniformité des nombres aléatoires. Dans la figure 8a , huit nombres aléatoires sont utilisés pour échantillonner la fonction. Étant donné que chaque nombre est sélectionné au hasard, ils se révèlent souvent être inégalement répartis sur le domaine de la définition. La figure 8b montre l'effet de la stratification: la zone de définition est divisée en huit strates et une position aléatoire est sélectionnée dans chaque strate, ce qui améliore l'uniformité.

L'effet sur la variance est assez évident. La figure 9a montre un graphique des résultats avec et sans stratification. La figure 9b montre l'erreur de valeur approximative. À $$$n = 10$ l'erreur moyenne pour 8 strates est $$ ; pour 20 strates - $$ , et pour 200 strates, il diminue à $$ . Sur la base de ces résultats, il semble qu'il soit utile d'utiliser un grand nombre de strates. Cependant, la stratification présente des inconvénients qui augmentent avec l'augmentation du nombre de strates. Premièrement, le nombre d'échantillons doit toujours être un multiple du nombre de strates; deuxièmement, comme dans la somme de Riemann, la stratification souffre de la malédiction des dimensions.


Figure 9: stratification et variance: a) une valeur approximative pour le nombre d'échantillons de n = 2 à n = 200; b) déviation.

Échantillon d'importance

Dans les sections précédentes, nous avons échantillonné les équations uniformément. L'extension de la fonction d'intégration de Monte Carlo nous permet de changer la donne:

$$

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

Ici $$$p (X)$ Est une fonction de densité de probabilité (pdf) : elle détermine la probabilité relative qu'une variable aléatoire prenne une certaine valeur.

Pour une variable aléatoire uniforme dans l'intervalle $$$0..1$ , pdf est 1 ( figure 10 a), ce qui signifie que chaque valeur a la même probabilité de choix. Si nous intégrons cette fonction sur $$$[0,0,5]$ alors nous obtenons la probabilité $$ de quoi $$$X <\ frac {1} {2}$ . Pour $$$X> \ frac {1} {2}$ nous obtenons évidemment la même probabilité.


Figure 10: distributions de probabilité. a) pdf constant auquel chaque échantillon a une probabilité de choix égale; b) pdf, où les échantillons inférieurs à 0,5 ont une probabilité de sélection plus élevée.

La figure 10b montre un autre pdf. Dans ce cas, la probabilité de générer un nombre est moindre $$$\ frac {1} {2}$ égal à 70%. Cela peut être implémenté à l'aide de l'extrait de code suivant:

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

Ce pdf est défini comme suit:

$$

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

Les chiffres $$ et $$ reflètent le besoin que la probabilité $$$x <\ frac {1} {2}$ était égal à 70%. Lors de l'intégration de pdf par $$$[0 .. \ frac {1} {2}]$ donne $$ et $$ est égal $$ . Cela illustre une exigence importante pour tous les fichiers PDF en général: le résultat de l'intégration du pdf doit être 1. Une autre exigence est que $$$p (x)$ ne peut pas être nul si $$$f (x)$ non nul: cela signifierait que les parties $$$f$ ont une probabilité d'échantillonnage nulle, ce qui affecte évidemment la valeur.

Quelques conseils pour comprendre le concept pdf:

• Une valeur pdf ne décrit pas la probabilité: par conséquent, localement, le pdf peut être supérieur à 1 (par exemple, comme dans le pdf que nous venons d'examiner).
• Cependant, l'intégrale sur le domaine de définition de pdf est une probabilité, ce qui signifie que l'intégration de pdf donne 1.

Une valeur peut être interprétée comme la possibilité relative d' apparaître d'une valeur spécifique.

Il convient de considérer que la distribution normale est une fonction de distribution de probabilité: elle nous donne la probabilité qu'une variable aléatoire se trouve dans un certain intervalle. Dans le cas d'une distribution normale, cette variable aléatoire est un écart par rapport à la moyenne. Comme tout pdf décent, le résultat de l'intégration de la distribution normale est 1.

Par conséquent, l' équation 7 nous permet d'effectuer un échantillonnage non uniforme. Il le compense en divisant chaque échantillon par la probabilité relative de son choix. L'importance de cela est illustrée à la figure 11a . Le graphique de fonction montre un intervalle significatif dans lequel sa valeur est $$$0$ . L'échantillonnage dans ce domaine est inutile: rien n'est ajouté à la somme, nous divisons simplement par un plus grand nombre. Rappelez-vous l'iceberg de la figure 1c : cela n'a aucun sens d'échantillonner la hauteur dans une grande zone autour de l'iceberg.


Figure 11: pdf pour une fonction avec des valeurs nulles.

Un pdf utilisant cette connaissance de la fonction est illustré à la figure 11b . Notez que ce pdf est en fait nul pour la plage de valeurs. Cela ne le transforme pas en un pdf incorrect: à certains endroits, la fonction est nulle. Nous pouvons étendre cette idée au-delà de zéro. Les échantillons sont mieux dépensés aux endroits où la fonction a des valeurs significatives. En fait, le pdf idéal est proportionnel à la fonction échantillonnée . Un très bon pdf pour notre fonction est illustré à la figure 12a . Un pdf encore meilleur est illustré à la figure 12b . Dans les deux cas, il ne faut pas oublier de le normaliser pour que l'intégrale soit égale à 1.


Figure 12: PDF amélioré pour la fonction de la figure 11.

Le pdf de la figure 12 nous pose deux tâches:

1. comment créer un tel pdf;
2. comment échantillonner un tel pdf?

La réponse aux deux questions est la même: nous n'avons pas besoin de le faire. Dans de nombreux cas, la fonction que nous voulons intégrer est inconnue, et la seule façon de déterminer les endroits où elle est significative est de l'échantillonner, et pour cela nous avons besoin de pdf; situation classique de «poulet et œufs».

Cependant, dans d'autres cas, nous avons une idée approximative de l'endroit où la fonction peut donner des valeurs plus élevées ou des valeurs nulles. Dans de tels cas, un pdf très grossier est souvent meilleur que pas de pdf.

De plus, nous pouvons avoir la possibilité de créer des fichiers PDF à la volée. Quelques échantillons donnent une idée de la forme de la fonction, et sur la base de celle-ci, nous orientons les échantillons suivants vers les endroits où nous attendons des valeurs élevées, que nous utilisons pour améliorer le pdf, etc.

Dans le prochain article, nous appliquerons ces concepts à l'implémentation du rendu. Un défi sérieux est la construction de pdf. Nous examinons plusieurs cas où les pdfs aident à l'échantillonnage.