Importance Sampling

2012 July. written by 이주형 (Lee Ju Hyung)

Monte Carlo 적분을 수행할 때 Importance Sampling 을 이용해 해를 좀 더 효율적으로 구할 수 있다. 쉽게 설명하면 주어진 domain 에서 근사 적분을 수행해야 할때, 최대한 적은 샘플링으로 근사값을 구하기 위해 샘플값이 큰 부분을 더 높은 빈도로 샘플링하는 것이다. 결과적으로 Uniform sampling 보다 빠르게 원래의 적분값에 수렴하게 된다.

BRDF 모델이 복잡할 수록 정확한 Importance sampling 함수를 찾기가 어렵지만, Phong 등의 간단한 모델을 사용한다면 비교적 간단하게 구할 수 있다. 여기서는 Phong 모델의 Importance Sampling 방법만 설명하겠다.

Cosine Weighted Sampling

미소 입체각 $d\omega$ 에 대한 Cosine weighted PDF (Probability Density Function) $p(\omega)$ 를 구해보자.

PDF 의 정의에 의해,

$k\int_{\Omega} \cos\theta d\omega = k\int_0^{2\pi}} \int_0^\frac{\pi}{2}} \cos\theta \sin\theta d\phi = 1$

$k = \frac{1}{\pi}$

$\therefore p(\theta, \phi) = \frac{\cos\theta \sin\theta}{\pi}$

$\theta$ 에 대한 Marginal Density Function $p(\theta)$ 를 구해보자.

$\begin{aligned} p(\theta) &= \frac{1}{\pi} \int_0^{2\pi} \cos\theta \sin\theta d\phi\\ &= \frac{1}{\pi} \left[ \cos\theta \sin\theta \phi \right]_0^{2\pi}\\ &= 2\cos\theta \sin\theta \end{aligned}$

정해진 $\theta$ 의 $\phi$ 에 대한 Conditional Density Function $p(\phi | \theta)$ 를 구해보자.

$p(\phi | \theta) = \frac{p(\theta, \phi)}{p(\theta)} = \frac{1}{2\pi}$

이제 $p(\theta)$ 와 $p(\phi | \theta)$ 를 각각 적분해서 1D CDF (Cumulative Distribution Function) 를 만든다.

$\begin{aligned} P(\theta) &= \int_0^{\theta} 2 \cos\theta' \sin\theta' d\theta'\\ &= \int_0^{\theta} \sin 2\theta' d\theta'\\ &= \left[ \frac{-\cos 2\theta'}{2} \right]_0^\theta = 1 - \cos^2\theta \\ P(\phi | \theta) &= \int_0^{\phi} \frac{1}{2\pi} d\phi' \\ &= \left[ \frac{1}{2\pi} \phi' \right]_0^\phi = \frac{1}{2\pi} \phi \end{aligned}$

이제 각각의 역함수를 구한다.

$\begin{aligned} \theta &= \cos^{-1} \sqrt{1 - \xi_1} \\ \phi &= 2\pi \xi_2 \end{aligned}$

Cartesian 좌표계로 나타내면,

$\begin{aligned} x &= \sin\theta \cos\phi = \sqrt{\xi_1} \cos 2\pi \xi_2\\ y &= \sin\theta \sin\phi = \sqrt{\xi_1} \sin 2\pi \xi_2\\ z &= \cos\theta = \sqrt{1 - \xi_1} \end{aligned}$

결론적으로 uniform 랜덤 변수인 $\xi_1, \xi_2 \in \interval[{0, 1}]$ 로, $\cos\theta$ 로 가중되어 분산된 랜덤 방향 벡터를 구할 수 있게 됐다.

Power Cosine Weighted Sampling

아까와 비슷한 방식으로 Power cosine weighted PDF 를 구해보자.

PDF 의 정의에 의해,

$k\int_{\Omega} \cos^n\theta d\omega = 1$

$\int_0^{2\pi} \int_0^{\pi/2} \cos^n \theta \sin\theta d\theta d\phi = 2\pi \int_0^{\pi/2} \cos^n\theta \sin\theta d\theta = 2\pi T$

치환된 T 를 풀면,

$\begin{aligned} T &= \int_o^{\pi/2} \cos^n \theta \sin\theta d\theta\\ &= \left[ -\cos^{n+1} \right]_0^{\pi/2} + \int_0^{\pi/2} n \cos^{n-1} \theta (-\sin\theta) (-\cos\theta) d\theta\\ &= 2\pi - nT \\ &= \frac{2\pi}{n+1} \end{aligned}$

$k = \frac{n+1}{2\pi}$

$\therefore p(\theta, \phi) = \frac{n+1}{2\pi} \cos^n \theta \sin \theta$

$\theta$ 에 대한 Marginal Density Function $p(\theta)$ 를 구해보자.

$\begin{aligned} p(\theta) &= \frac{n+1}{2\pi} \int_0^{2\pi} \cos^n\theta \sin\theta d\phi \\ &= \frac{n+1}{2\pi} \left[ \cos^n\theta \sin\theta \phi \right]_0^{2\pi} \\ &= (n+1) \cos^n\theta \sin\theta \end{aligned}$

정해진 $\theta$ 의 $\phi$ 에 대한 Conditional Density Function $p(\phi | \theta)$ 를 구해보자.

$p(\phi | \theta) = \frac{p(\theta, \phi)}{p(\theta)} = \frac{1}{2\pi}$

이제 $p(\theta)$ 와 $p(\phi | \theta)$ 를 각각 적분해서 1D CDF (Cumulative Distribution Function) 를 만든다.

$P(\theta) = (n+1) \int_0^{\theta} 2 \cos^n\theta' \sin\theta' d\theta' = (n+1) T$

치환된 T 를 풀면,

$\begin{aligned} T &= \int_0^{\theta} \cos^n\theta' \sin\theta' d\theta'\\ &= \left[ -\cos^{n+1} \right]_0^{\theta} - n \int_0^\theta \cos^{n-1} \theta' (-\sin\theta') (-\cos\theta') d\theta'\\ &= -\cos^{n+1}\theta' + 1 - n T \\ &= \frac{1 - \cos^{n+1} \theta}{n+1} \end{aligned}$

$\therefore P(\theta) = 1 - \cos^{n+1} \theta$

$\begin{aligned} P(\phi | \theta) &= \int_0^{\phi} \frac{1}{2\pi} d\phi' \\ &= \left[ \frac{1}{2\pi} \phi' \right]_0^\phi = \frac{1}{2\pi} \phi \end{aligned}$

이제 각각의 역함수를 구한다.

$\begin{aligned} \theta &= \cos^{-1} \left( (1 - \xi_1)^{\frac{1}{n+1}} \right) \\ \phi &= 2\pi \xi_2 \end{aligned}$

Cartesian 좌표계로 나타내면,

$\begin{aligned} x &= \sin\theta \cos\phi = \sqrt{1 - (1 - \xi_1)^{\frac{2}{n+1}}} \cos 2\pi \xi_2\\ y &= \sin\theta \sin\phi = \sqrt{1 - (1 - \xi_1)^{\frac{2}{n+1}}} \sin 2\pi \xi_2\\ z &= \cos\theta = (1 - \xi_1)^{\frac{1}{n+1}} \end{aligned}$

결론적으로 uniform 랜덤 변수인 $\xi_1, \xi_2 \in \interval[{0, 1}]$ 로, $\cos^n\theta$ 로 가중되어 분산된 랜덤 방향 벡터를 구할 수 있게 됐다.

Importance Sampling for Phong Model

지금까지의 식들을 조합해서 Phong 모델의 Monte Carlo 적분시 Importance Sampling 에 필요한 PDF 와 샘플링 함수를 구할 수 있다.

Phong 라이팅 모델에 대한 BRDF 식은,

$f_r = \frac{\rho_d}{\pi} + \rho_s \frac{n+2}{2\pi} \frac{(L \cdot S)^n}{N \cdot L}$

렌더링 적분식에는 $N \cdot L = \cos\theta_d$ 가 곱해지므로,

$\begin{aligned} \int_{\Omega} f_r L_i \cos\theta_d d\omega &= \int_{\Omega} \left( \frac{\rho_d}{\pi} L_i \cos\theta_d + \rho_s \frac{n+2}{2\pi} \cos^n\theta_s L_i \right) d\omega \\ &= \frac{\rho_d}{\pi} \int_{\Omega} L_i \cos\theta_d d\omega + \rho_s \frac{n+2}{2\pi} \int_{\Omega} \cos^n\theta_s L_i d\omega \end{aligned}$

여기서 빛이 표면에 부딪혀 반사될 때 Lambert 산란 확률을 $\rho_d$ , Specular 반사 확률을 $\rho_s$ 라고 할 수 있다.

random 값 $u$ 에 의해 $u < \rho_d$ 이면 Cosine weighted sampling 을 $\rho_d < u < \rho_d + \rho_s$ 이면 Power cosine weighted sampling 을 수행하면 된다.

단, Cosine weighted sampling 에서 $\theta$ 는 $L$ 과 $N$ 사이의 각도이고, Power cosine weighted sampling 에서 $\theta$ 는 $L$ 과 $S$ 사이의 각도를 말한다. 즉, 반구면에 대한 Monte Carlo 적분을 수행할때 Lambert diffuse 적분식의 up 방향 벡터는 $N$ 이지만, Phong specular 적분식은 $S$ 를 up 방향 벡터로 하면 된다. 실제로 랜덤 샘플링할 때 적절히 up 방향의 로컬 축으로 변환해야 할 것이다.