Teoria da Probabilidade para Renderização Fisicamente Precisa

1. Introdução

Na renderização, o cálculo de integrais definidas multidimensionais é frequentemente usado: por exemplo, para determinar a visibilidade de fontes de luz espaciais (área de luz), luminosidade atingindo a região de pixel, luminosidade chegando ao longo de um período de tempo e irradiação entrando no hemisfério de um ponto de superfície. O cálculo dessas integrais é geralmente realizado usando a integração Monte Carlo, na qual a integral é substituída pela expectativa de um experimento estocástico.

Neste artigo, falarei em detalhes sobre o processo básico de integração de Monte Carlo, bem como várias técnicas para reduzir a variação da técnica. Isso será feito de um ponto de vista prático - presume-se que o leitor não esteja muito familiarizado com a teoria da probabilidade, mas ainda deseje desenvolver algoritmos de renderização eficazes e corretos.

Integrais definidas

Uma integral definida é uma integral da forma $$$\ int_ {a} ^ {b} f (x) dx$ onde $$$[a, b]$ É um segmento (ou região), $$$x$ - escalar e $$$f (x)$ - uma função que pode ser calculada para qualquer ponto do segmento. Conforme escrito na Wikipedia , uma certa integral é uma área com um sinal em um avião $$$x$ limitado pela programação $$$f$ eixo $$$x$ linhas verticais $$$x = a$ e $$$x = b$ ( Figura 1a ).

Esse conceito logicamente se estende a um número maior de dimensões: para uma certa integral dupla, a área com um sinal se torna um volume com um sinal ( Figura 1b ) e, em geral, para certas integrais múltiplas, torna-se um volume multidimensional com um sinal .


Figura 1: exemplos de certas integrais.

Em alguns casos, a área pode ser determinada analiticamente , por exemplo, para $$$f (x) = 2$ : no segmento $$$[a, b]$ a área será igual $$$2 (b-a)$ . Em outros casos, uma solução analítica é impossível, por exemplo, quando precisamos descobrir o volume da parte do iceberg acima da água ( Figura 1c ). Nesses casos $$$f (x)$ frequentemente pode ser determinado por amostragem .

Integração numérica

Podemos calcular aproximadamente a área de integrais complexas usando integração numérica . Um exemplo é a soma de Riemann . Esse valor é calculado dividindo a área em formas regulares (por exemplo, retângulos), que juntos formam uma área semelhante a uma área verdadeira. A soma de Riemann é definida da seguinte forma:

$$

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

$$$n$ É o número de subintervalos e $$$\ Delta x_i = \ frac {b-a} {n}$ - a largura de um sub-intervalo. Para cada intervalo $$$i$ nós provamos $$$f$ em um ponto $$$x_i$ dentro do sub-intervalo (na Figura 2, este ponto está no início do sub-intervalo).


Figura 2: soma de Riemann.

Vale ressaltar que, com o aumento da $$$n$ a soma de Riemann converge para o valor real da integral:

$$

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

A soma de Riemann também pode ser usada para grandes dimensões ( Figura 3 ). No entanto, aqui estamos diante de um problema: para uma função com dois parâmetros, o número de subintervalos deve ser muito maior se quisermos obter uma resolução comparável à usada no caso bidimensional. Esse fenômeno é chamado de maldição das dimensões e, em dimensões superiores, é exacerbado.


Figura 3: Soma de Riemann para uma integral dupla.

Agora avaliaremos a precisão da soma de Riemann para a seguinte função (escolhemos intencionalmente uma função complexa):

$$

$$\ tag {3} f (x) = \ esquerda | \ 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 |$$

Gráfico de função em um segmento $$$[- 2,5,2,5]$ mostrado abaixo. Para referência, calculamos uma certa integral no Wolfram Alpha $$$\ int _ {- 2,5} ^ {2,5} f (x)$ ficando área $$$3,12970$ . O gráfico à direita mostra a precisão da integração numérica usando a soma de Riemann para aumentar $$$n$ .


Figura 4: Gráfico de funções e precisão da soma de Riemann. Mesmo com pequenas $$$n$ obtemos um resultado bastante preciso.

Para ter uma idéia da precisão, damos os números: para $$$n = 50$ o erro é $$$~ 2 \ times10 ^ {- 3}$ . At $$$n = 100$ o erro é $$$~ 3 \ times10 ^ {- 4}$ . A seguinte ordem de grandeza é obtida com $$$n = 200$ .

Para mais informações sobre valores de Riemann, consulte os seguintes recursos:

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

Ao renderizar, quase nenhum (e talvez nenhum?) Integrais são únicos . Isso significa que encontraremos rapidamente a maldição das dimensões. Além disso, a amostragem de uma função em intervalos iguais está sujeita a amostragem e distorção insuficientes : podemos pular valores importantes da função ou obter interferência inesperada entre a função amostrada e o padrão de amostragem ( Figura 5 ).


Figura 5: distorções levam à perda de partes da função amostrada (vermelho) e, neste caso, a uma interpretação completamente incorreta da função.

Esses problemas são resolvidos usando uma técnica chamada integração de Monte Carlo . Semelhante à soma de Riemann, ele também usa amostragem de funções em um conjunto de pontos, mas, diferentemente do padrão determinístico de soma de Riemann, usamos um ingrediente fundamentalmente não determinístico : números aleatórios.

A integração de Monte Carlo é baseada na seguinte observação: a integral pode ser substituída pela expectativa de um experimento estocástico:

$$

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

Em outras palavras, nós mostramos a função $$$n$ vezes em pontos aleatórios dentro de um segmento (indicado por uma capital $$$X$ ), calcule a média das amostras e multiplique pela largura do segmento (para uma função unidimensional). Como no caso da soma de Riemann, quando $$$n$ até o infinito, o valor médio das amostras converge para a expectativa, ou seja, para o valor real da integral.

Um pouco de teoria das probabilidades

É importante entender cada um dos conceitos usados ​​aqui. Vamos começar com a espera : este é o valor esperado para uma única amostra. Observe que esse não é necessariamente um valor possível , o que pode parecer contra-intuitivo. Por exemplo, quando rolamos o dado, a expectativa é igual a $$$3,5$ - a média de todos os resultados possíveis: $$$(1 + 2 + 3 + 4 + 5 + 6) /6=21/6=3,5$ .

O segundo conceito são números aleatórios . Isso pode parecer óbvio, mas para a integração de Monte Carlo, precisamos de números aleatórios distribuídos uniformemente, ou seja, cada valor deve ter uma probabilidade igual de geração. Falaremos mais sobre isso mais tarde.

O terceiro conceito é desvio e a variação associada a ele. Mesmo quando tomamos um pequeno número de números, o valor médio esperado, bem como a expectativa de cada amostra individual, deve ser o mesmo. No entanto, ao calcular a equação 4, raramente obtemos esse valor. Desvio é a diferença entre a expectativa e o resultado do experimento: $$$X-E (X)$ .

Na prática, esse desvio tem uma distribuição interessante:


Este é um gráfico da distribuição normal ou distribuição gaussiana : mostra que nem todos os desvios são igualmente prováveis. De fato, aproximadamente 68,2% das amostras estão na faixa $$$-1 \ sigma..1 \ sigma$ onde $$$\ sigma$ (sigma) é o desvio padrão . O desvio padrão pode ser descrito de duas maneiras:

• O desvio padrão é uma medida da variabilidade dos dados.
• 95% dos pontos de dados estão dentro $$$2 \ sigma$ da média.

Existem dois métodos para determinar o desvio padrão:

1. Desvio padrão $$$\ sigma = \ sqrt {\ frac {1} {n} \ sum_ {i = 1} ^ {n} \ left (X_i-E \ left [X \ right] \ right) ^ 2}$ : pode ser calculado se houver uma distribuição de probabilidade discreta e a expectativa for conhecida $$$E [X]$ . Isso vale para cubos em que $$$X = {1,2,3,4,5,6}$ e $$$E [X] = 3,5$ . Substituindo os números, obtemos $$$\ sigma = 1,71$ .
2. Além disso, o desvio padrão das amostras pode ser calculado como $$$\ sigma = \ sqrt {\ frac {1} {n-1} \ sum_ {i = 1} ^ {n} \ esquerda (X_i-X \ right) ^ 2}$ . Leia mais sobre isso na Wikipedia .

Verificar: isso está correto? Se $$$\ sigma = 1,71$ , declaramos que 68,2% das amostras estão dentro de 1,71 de 3,5. Nós sabemos que $$${2,3,4,5}$ satisfazem este critério, e $$$1$ e $$$6$ não. Quatro de seis são 66,7%. Se nosso cubo pudesse produzir algum valor no intervalo $$$[1..6]$ , obteríamos exatamente 68,2%.

Em vez do desvio padrão, o conceito associado de variação , definido como $$$Var \ left [X \ right] = \ sigma ^ 2$ . Como o quadrado é usado, a variação é sempre positiva, o que ajuda nos cálculos.

Monte Carlo (2)

Acima, calculamos aproximadamente a equação 3 usando a soma de Riemann. Agora repetimos esse experimento com a integração de Monte Carlo. Lembre-se de que a integração de Monte Carlo é definida da seguinte maneira:

$$

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

Vamos traduzir isso para o código C:

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

Resultado para valores de $$$n = 2$ antes $$$n = 200$ mostrado na tabela abaixo. A partir disso, pode-se supor que a integração de Monte Carlo se manifeste muito pior do que a soma de Riemann. Um exame mais detalhado do erro diz que, com $$$n = 200$ o erro médio da soma de Riemann é $$$0,0002$ e Monte Carlo $$ .


Figura 6: Erro de Monte Carlo em 2.200 amostras.

Em dimensões mais altas, essa diferença é reduzida, mas não completamente eliminada. A equação mostrada abaixo é uma versão expandida da usada acima, recebendo dois parâmetros:

$$

$$f (x, y) = \ esquerda | \ 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 \ esquerda (2,3x \ direita) \ direita | (6)$$

Figura 7: Gráfico da equação acima.

No campo da definição $$$x∈ [-2,5,2,5], y∈ [-2,5,2,5]$ volume limitado por esta função e plano $$$xy$ é igual $$$6.8685$ . At $$$n = 400$ (20 × 20 amostras), o erro da soma de Riemann é $$$0,043$ . Com o mesmo número de amostras, o erro médio de integração de Monte Carlo é $$ . Isso é melhor que o resultado anterior, mas a diferença ainda é significativa. Para entender esse problema, estudaremos a conhecida técnica de redução de dispersão da integração Monte Carlo chamada “estratificação”.


Figura 8: impacto da estratificação; a) amostras com má distribuição; b) amostras com distribuição uniforme.

A estratificação aumenta a uniformidade dos números aleatórios. Na Figura 8a , oito números aleatórios são usados ​​para amostrar a função. Como cada número é selecionado aleatoriamente, eles geralmente são distribuídos de maneira desigual no domínio da definição. A Figura 8b mostra o efeito da estratificação: a área de definição é dividida em oito estratos e uma posição aleatória é selecionada em cada estrato, o que melhora a uniformidade.

O efeito sobre a variação é bastante óbvio. A Figura 9a mostra um gráfico dos resultados com e sem estratificação. A Figura 9b mostra o erro aproximado do valor. At $$$n = 10$ o erro médio para 8 estratos é $$$0,05$ ; para 20 estratos - $$$0,07$ e, para 200 estratos, diminui para $$$0,002$ . Com base nesses resultados, parece que vale a pena usar um grande número de estratos. No entanto, a estratificação tem desvantagens que aumentam com o aumento do número de estratos. Em primeiro lugar, o número de amostras deve sempre ser um múltiplo do número de estratos; segundo, como na soma de Riemann, a estratificação sofre com a maldição das dimensões.


Figura 9: estratificação e variância: a) um valor aproximado para o número de amostras de n = 2 a n = 200; b) desvio.

Amostra de importância

Nas seções anteriores, amostramos as equações uniformemente. A extensão da função integradora de Monte Carlo nos permite mudar a situação:

$$

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

Aqui $$$p (X)$ É uma função de densidade de probabilidade (pdf) : determina a probabilidade relativa de uma variável aleatória assumir um determinado valor.

Para uma variável aleatória uniforme no intervalo $$$0..1$ , pdf é 1 ( Figura 10 a), e isso significa que cada valor tem a mesma probabilidade de escolha. Se integrarmos essa função sobre $$$[0,0,5]$ então temos a probabilidade em $$$0,5$ do que $$$X <\ frac {1} {2}$ . Para $$$X> \ frac {1} {2}$ obviamente temos a mesma probabilidade.


Figura 10: Distribuições de probabilidade. a) pdf constante no qual cada amostra tem igual probabilidade de escolha; b) pdf, onde amostras abaixo de 0,5 têm maior probabilidade de seleção.

A Figura 10b mostra outro pdf. Nesse caso, a probabilidade de gerar um número é menor $$$\ frac {1} {2}$ igual a 70%. Isso pode ser implementado usando o seguinte snippet de código:

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

Este pdf é definido da seguinte forma:

$$

$$\ tag {8} p (x) = \ esquerda \ {\ begin {matrix} 1.4, se x <\ frac {1} {2} \\ 0.6, caso contrário \ end {matrix} \ right.$$

Os números $$$1,4$ e $$ refletem a necessidade dessa probabilidade $$$x <\ frac {1} {2}$ foi igual a 70%. Ao integrar pdf por $$$[0 .. \ frac {1} {2}]$ dá $$$1,4 \ times \ frac {1} {2}$ e $$$0,6 \ times \ frac {1} {2}$ é igual a $$$0,3$ . Isso ilustra um requisito importante para todos os pdfs em geral: o resultado da integração do pdf deve ser 1. Outro requisito é que $$$p (x)$ não pode ser zero se $$$f (x)$ diferente de zero: significaria que as partes $$$f$ tem uma probabilidade de amostragem zero, o que obviamente afeta o valor.

Algumas dicas para entender o conceito de pdf:

• Um valor em pdf não descreve a probabilidade: portanto, o pdf local pode ser maior que 1 (por exemplo, como no pdf que acabamos de examinar).
• No entanto, a integral sobre o domínio da definição de pdf é uma probabilidade, o que significa que a integração de pdf fornece 1.

Um valor pode ser interpretado como a possibilidade relativa da aparência de um valor específico.

Vale considerar que a distribuição normal é uma função da distribuição de probabilidade: ela nos dá a probabilidade de que alguma variável aleatória esteja em um determinado intervalo. No caso de uma distribuição normal, essa variável aleatória é um desvio da média. Como qualquer pdf decente, o resultado da integração da distribuição normal é 1.

Portanto, a Equação 7 nos permite realizar amostragens não uniformes. Ele compensa isso dividindo cada amostra pela probabilidade relativa de sua escolha. A importância disso é mostrada na Figura 11a . O gráfico da função mostra um intervalo significativo em que seu valor é $$$0$ . A amostragem nesta área é inútil: nada é adicionado à soma, simplesmente dividimos por um número maior. Lembre-se do iceberg da Figura 1c : não faz sentido amostrar a altura em uma grande área ao redor do iceberg.


Figura 11: pdf para uma função com valores zero.

Um pdf usando esse conhecimento da função é mostrado na Figura 11b . Observe que este pdf é realmente zero para o intervalo de valores. Isso não o transforma em um pdf incorreto: em alguns lugares, a função é zero. Podemos estender essa idéia além de zero. As amostras são melhor usadas nos locais em que a função possui valores significativos. De fato, o pdf ideal é proporcional à função de amostra . Um pdf muito bom para nossa função é mostrado na Figura 12a . Um pdf ainda melhor é mostrado na Figura 12b . Nos dois casos, não devemos esquecer de normalizá- la para que a integral seja igual a 1.


Figura 12: PDF aprimorado para a função na Figura 11.

O pdf da Figura 12 apresenta duas tarefas para nós:

1. como criar esse pdf;
2. como provar esse pdf?

A resposta para as duas perguntas é a mesma: não precisamos fazer isso. Em muitos casos, a função que queremos integrar é desconhecida, e a única maneira de determinar os locais onde é significativo é amostrá-la e, para isso, precisamos de pdf; situação clássica de “frango e ovos”.

No entanto, em outros casos, temos uma idéia aproximada de onde a função pode fornecer valores mais altos ou zero. Nesses casos, um pdf muito áspero geralmente é melhor que nenhum pdf.

Além disso, podemos ter a oportunidade de criar pdf em tempo real. Algumas amostras dão uma idéia da forma da função e, com base nela, direcionamos as amostras subsequentes para os locais em que esperamos altos valores, que usamos para melhorar o pdf, e assim por diante.

No próximo artigo, aplicaremos esses conceitos à implementação de renderização. Um sério desafio é construir pdf. Examinamos vários casos em que os PDFs ajudam na amostragem.