Application d'intégration Monte Carlo dans le rendu

Nous avons tous étudié les méthodes numériques au cours des mathématiques. Ce sont des méthodes telles que l'intégration, l'interpolation, les séries, etc. Il existe deux types de méthodes numériques: déterministes et randomisées.

Méthode typique d'intégration de la fonction déterministe $$$f$ dans la gamme $$$[a, b]$ Cela ressemble à ceci: nous prenons $$$n + 1$ points régulièrement espacés $$$t_0 = a, t_1 = a + \ frac {b - a} {n}, \ ldots, t_n - b$ calculer $$$f$ à mi-chemin $$$\ frac {t_i + t_ {i + 1}} {2}$ de chacun des intervalles définis par ces points, résumez les résultats et multipliez par la largeur de chaque intervalle $$$\ frac {b -a} {b}$ . Pour des fonctions suffisamment continues $$$f$ avec l'augmentation $$$n$ le résultat convergera vers la valeur correcte.


La méthode probabiliste, ou la méthode de Monte Carlo pour calculer, ou, plus précisément, une estimation approximative de l' intégrale $$$f$ dans la gamme $$$[a, b]$ ressemble à ceci: laissez $$$X_1, \ ldots, X_n$ - points sélectionnés au hasard dans l'intervalle $$$[a, b]$ . Alors $$$Y = (b - a) \ frac {1} {n} \ sum_ {i = 1} ^ {n} f (X_i)$ Est une valeur aléatoire dont la moyenne est une intégrale $$$\ int _ {[a, b]} f$ . Pour implémenter la méthode, nous utilisons un générateur de nombres aléatoires qui génère $$$n$ points dans l'intervalle $$$[a, b]$ nous calculons dans chaque $$$f$ , faire la moyenne des résultats et multiplier par $$$b-a$ . Cela nous donne la valeur approximative de l'intégrale, comme indiqué dans la figure ci-dessous. $$$\ int _ {- 1} ^ {1} \ sqrt {1 - x ^ 2} dx$ avec 20 échantillons se rapproche du résultat correct égal à $$$\ frac {\ pi} {2}$ .


Bien sûr, chaque fois que nous calculons une telle valeur approximative, nous obtiendrons un résultat différent. La variance de ces valeurs dépend de la forme de la fonction. $$$f$ . Si nous générons des points aléatoires $$$x_i$ de manière inégale, nous devons alors modifier légèrement la formule. Mais grâce à l'utilisation d'une distribution inégale des points, nous obtenons un énorme avantage: forcer la distribution inégale à privilégier les points $$$x_i$ où $$$f (x)$ grande, nous pouvons réduire considérablement la variance des valeurs approximatives. Ce principe d'échantillonnage non uniforme est appelé échantillonnage par signification .


Étant donné qu'au cours des dernières décennies, une transition à grande échelle des approches déterministes aux approches aléatoires a eu lieu dans les techniques de rendu, nous étudierons les approches randomisées utilisées pour résoudre les équations de rendu. Pour ce faire, nous utilisons des variables aléatoires, l'espérance mathématique et la variance. Nous avons affaire à des valeurs discrètes, car les ordinateurs sont de nature discrète. Les quantités continues traitent de la fonction de densité de probabilité , mais dans l'article nous ne la considérerons pas. Nous parlerons de la fonction de masse de probabilité. PMF a deux propriétés:

1. Pour chacun $$$s \ in S$ existe $$$p (s) \ geq 0$ .
2. $$$\ sum_ {s \ in S} p (s) = 1$

La première propriété est appelée non-négativité. La seconde est appelée «normalité». Intuitivement, $$$S$ représente l'ensemble des résultats d'une expérience, et $$$p (s)$ Est le résultat de la probabilité $$$s$ membre $$$S$ . Le résultat est un sous-ensemble de l'espace de probabilité. La probabilité d'un résultat est la somme des éléments PMF de ce résultat, car

$$

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

Une variable aléatoire est une fonction, généralement désignée par une lettre majuscule, qui met des nombres réels dans l'espace de probabilité:

$$

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

Notez que la fonction $$$X$ - Ce n'est pas une variable, mais une fonction avec des valeurs réelles. Elle n'est pas non plus aléatoire , $$$X (s)$ Est un nombre réel distinct pour tout résultat $$$s \ in S$ .

Une variable aléatoire est utilisée pour déterminer les résultats. Par exemple, de nombreux résultats $$$s$ pour lequel $$$X (s) = 1$ , c'est-à-dire que si ht et th sont l'ensemble des lignes indiquant "aigles" ou "queues", alors

$$

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

et

$$

$$= {ht, th}$$

c'est un résultat avec probabilité $$$\ frac {1} {2}$ . Nous l'écrivons comme $$$Pr \ {X = 1 \} = \ frac {1} {2}$ . Nous utilisons le prédicat $$$X = 1$ comme entrée raccourcie pour le résultat déterminé par le prédicat.

Jetons un coup d'œil à un fragment de code simulant une expérience décrite par les formules présentées ci-dessus:

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

Ici, nous désignons ranb() fonction booléenne qui renvoie vrai dans la moitié des cas. Comment est-elle liée à notre abstraction? Imaginez beaucoup $$$S$ toutes les exécutions possibles du programme, déclarant deux exécutions les mêmes valeurs retournées par ranb , identiques par paire. Cela signifie qu'il existe quatre exécutions possibles du programme dans lesquelles deux ranb() renvoient TT, TF, FT et FF. D'après notre propre expérience, nous pouvons dire que ces quatre réalisations sont également probables, c'est-à-dire qu'elles se produisent chacune dans environ un quart des cas.

Maintenant, l'analogie devient plus claire. Les nombreuses exécutions possibles d'un programme et les probabilités qui leur sont associées sont un espace de probabilité. Les variables de programme qui dépendent des appels ranb sont des variables aléatoires. J'espère que tout est clair pour vous maintenant.

Discutons de la valeur attendue, également appelée moyenne. Il s'agit essentiellement de la somme du produit de PMF et d'une variable aléatoire:

$$

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

Imaginez que h sont des «aigles» et t sont des «queues». Nous avons déjà couvert ht et th. Il y a aussi hh et tt. Par conséquent, la valeur attendue sera la suivante:

$$

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

Vous vous demandez peut-être d'où il vient $$$X$ . Ici, je voulais dire que nous devrions attribuer un sens $$$X$ par vous-même. Dans ce cas, nous avons attribué h à 1 et t à 0. $$$X (hh)$ est égal à 2 car il contient 2 $$$h$ .

Parlons de distribution. La distribution de probabilité est une fonction qui donne les probabilités de divers résultats d'un événement.

Quand on dit qu'une variable aléatoire $$$X$ a une distribution $$$f$ devrait alors indiquer $$$X \ sim f$ .

Valeurs de diffusion accumulées autour $$$X$ est appelé sa dispersion et est défini comme suit:

$$

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

O Where $$$\ bar {X}$ Est moyen $$$X$ .

$$$\ sqrt {\ boldsymbol {Var}}$ appelé écart-type . Variables aléatoires $$$X$ et $$$Y$ sont appelés indépendants si:

$$

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

Propriétés importantes des variables aléatoires indépendantes:

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

Quand j'ai commencé avec une histoire sur la probabilité, j'ai comparé des probabilités continues et discrètes. Nous avons examiné la probabilité discrète. Parlons maintenant de la différence entre les probabilités continues et discrètes:

1. Les valeurs sont continues. Autrement dit, les nombres sont infinis.
2. Certains aspects de l'analyse nécessitent des subtilités mathématiques telles que la mesurabilité .
3. Notre espace de probabilité sera infini. Au lieu de PMF, nous devrions utiliser la fonction de densité de probabilité (PDF).

Propriétés PDF:

1. Pour chacun $$$s \ in S$ nous avons $$$p (s) \ geq 0$
2. $$$\ int_ {s \ in S} p (s) = 1$

Mais si la distribution $$$S$ uniformément , le pdf est défini comme ceci:


Avec une probabilité continue $$$E [X]$ défini comme suit:

$$

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

Comparez maintenant les définitions de PMF et 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$$

Dans le cas d'une probabilité continue, les variables aléatoires sont mieux appelées points aléatoires . Parce que si $$$S$ Est l'espace de probabilité, et $$$Y: S \ rightarrow T$ affiché dans un espace différent de celui $$$\ mathbb {R}$ alors nous devrions appeler $$$Y$ point aléatoire , pas une variable aléatoire. Le concept de densité de probabilité est applicable ici, car on peut dire que pour tout $$$U \ sous-ensemble T$ nous avons:


Appliquons maintenant ce que nous avons appris à la sphère. La sphère a trois coordonnées: latitude, longitude et complément de latitude. Nous utilisons l'addition de longitude et de latitude uniquement dans $$$\ mathbb {R} ^ 2$ , coordonnées cartésiennes bidimensionnelles appliquées à une variable aléatoire $$$S$ la transformer en $$$S ^ 2$ . Nous obtenons les détails suivants:

$$

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

Nous commençons avec une densité de probabilité uniforme $$$p$ à $$$[0, 1] \ fois [0, 1]$ , ou $$$p (u, v) = 1$ . Regardez la formule de densité de probabilité uniforme ci-dessus. Pour plus de commodité, nous écrirons $$$(x, y, z) = Y (u, v)$ .

Nous comprenons intuitivement que si vous sélectionnez des points de manière uniforme et aléatoire dans un carré unitaire et que vous utilisez $$$f$ pour les convertir en points sur une sphère unitaire, ils s'accumuleront à côté du pôle. Cela signifie que la densité de probabilité obtenue en $$$T$ ne sera pas uniforme. Ceci est illustré dans la figure ci-dessous.


Nous allons maintenant discuter des moyens d'approximer la valeur attendue d'une variable aléatoire continue et de son application pour déterminer les intégrales. Ceci est important car dans le rendu, nous devons déterminer la valeur de l'intégrale de réflectivité :

$$

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

pour différentes valeurs $$$P$ et $$$\ omega_0$ . Valeur $$$\ omega$ Est la direction de la lumière incidente. Code générant un nombre aléatoire uniformément distribué dans l'intervalle $$$[0, 1]$ et en prenant la racine carrée, crée une valeur dans la plage de 0 à 1. Si nous utilisons PDF pour cela, car il s'agit d'une valeur uniforme, la valeur attendue sera égale $$$\ frac {2} {3}$ . Cette valeur est également la valeur moyenne $$$f (x) = \ sqrt {x}$ dans cet intervalle. Qu'est-ce que cela signifie?

Prenons le théorème 3.48 du livre Computer Graphics: Principles and Practice. Elle dit que si $$$f: [a, b] \ rightarrow \ mathbb {R}$ est une fonction avec des valeurs réelles, et $$$X \ sim \ boldsymbol {U} (a, b)$ est une variable aléatoire uniforme dans l'intervalle $$$[a, b]$ alors $$$(b-a) f (x)$ Est une variable aléatoire dont la valeur attendue a la forme:

$$

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

Qu'est-ce que cela nous apprend? Cela signifie que vous pouvez utiliser un algorithme aléatoire pour calculer la valeur de l'intégrale si nous exécutons le code plusieurs fois et faisons la moyenne des résultats .

Dans le cas général, nous obtenons une certaine valeur $$$C$ , comme dans l'intégrale ci-dessus, qui doit être déterminée, et un algorithme aléatoire qui renvoie une valeur approximative $$$C$ . Une telle variable aléatoire pour une quantité est appelée un estimateur . Un estimateur est considéré comme sans distorsion si sa valeur attendue est $$$C$ . Dans le cas général, les estimateurs sans distorsion sont préférables aux distorsions.

Nous avons déjà discuté des probabilités discrètes et continues. Mais il existe un troisième type, appelé probabilités mixtes et utilisé dans le rendu. Ces probabilités sont dues à des impulsions dans les fonctions de distribution de la diffusion bidirectionnelle ou à des impulsions provoquées par des sources ponctuelles d'éclairage. Ces probabilités sont définies dans un ensemble continu, par exemple, dans l'intervalle $$$[0, 1]$ mais pas strictement défini par la fonction PDF. Considérez le programme suivant:

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

Dans soixante pour cent des cas, le programme renverra 0,3 et dans les 40% restants, il renverra une valeur uniformément répartie en $$$[0, 1]$ . La valeur de retour est une variable aléatoire avec une masse de probabilité de 0,6 à 0,3, et son PDF à tous les autres points est spécifié comme $$$d (x) = 0,4$ . Nous devons définir le PDF comme:


En général, une variable aléatoire à variable mixte est une variable pour laquelle il existe un ensemble fini de points dans la zone de définition PDF, et vice versa, des points uniformément répartis où la PMF n'est pas définie.