Lightweight Photon Mapping

 

我们知道,VCM(Vertex Connection & Merging)把PM(Photon Mapping)和BDPT(Bidirectional Path Tracing)融合了起来,可以鲁棒地handle一些比较难的场景。但是对大多数应用来说VCM的overhead实在太大了,大多数时候我们只需要用PT(Path Tracing)绘制不算复杂的照明,然后加上用PM画的焦散,所以这里讨论以下怎么把这两个算法结合起来,算是VCM的简化版。

长度不超过3的路径

对长度为2的路径$x_1x_2$,我们简单地从摄像机镜头上的点$x_1$发出射线,击中$x_2$处的光源,不需要做什么特别的处理。

对长度为3的路径$x_1x_2x_3$,我们使用MIS(Multiple Importance Sampling)结合BSDF采样和光源采样,也不需要PM的参与。

其他路径涉及的采样方法

对长度$k > 3$的路径$\bar x = x_1x_2\cdots x_k$,采样该路径的方法一共有三类:

  1. Unidirectional PT,直接用一系列BSDF采样构造出整个路径
  2. Unidirectional PT,但在到达$x_{k-1}$后转而使用光源采样得到$x_k$
  3. 在$x_2, \ldots, x_{k-2}$处使用VM(Vertex Merging),融合光子图中的顶点,得到剩下的路径 d 这些方法对应的路径pdf为:
\[\begin{aligned} p_{\mathrm{PT_{bsdf}}}(\bar x) &= p(x_1)\prod_{i=2}^kp(x_{i-1} \to x_i) \\ p_{\mathrm{PT_{light}}}(\bar x) &= p(x_1)\prod_{i=2}^{k-1}p(x_{i-1}\to x_i)p_\mathrm{light}(x_k|x_{k-1}) \\ p_{\mathrm{VM}_t}(\bar x) &= p(x_1)\prod_{i=2}^tp(x_{i-1}\to x_i)\prod_{i=t}^{k-1}p(x_i\leftarrow x_{i+1})p(x_k)\pi r^2 \end{aligned}\]

其中$p(a \to b)$是使用BSDF采样从顶点$a$采样顶点$b$的area pdf,$p(a \leftarrow b)$是其adjoint版本,$p_\mathrm{light}$是光源采样的area pdf,$p(x_1)$是摄像机镜头上的area pdf,$p(x_k)$是光子发射源的area pdf。现假设一共发射了$N_\mathrm{VM}$个光子,那么对采样方法$v$,其MIS权重是:

\[w_v(\bar x) = \frac{p_v(\bar x)}{p_{\mathrm{PT_{bsdf}}}(\bar x) + p_{\mathrm{PT_{light}}}(\bar x) + N_\mathrm{VM}\sum_{t=2}^{k-2}p_{\mathrm{VM}_t}(\bar x)}\]

计算$w_\mathrm{PT}$

我们做一些形式上的变换:

\[\begin{aligned} \frac 1 {w_\mathrm{PT_{bsdf}}(\bar x)} &= 1 + \frac{p_\mathrm{light}(x_k|x_{k-1})}{p(x_{k-1}\to x_k)} + N_\mathrm{VM}\pi r^2\sum_{t=2}^{k-2} \frac{ \prod_{i=2}^tp(x_{i-1}\to x_i) \prod_{i=t}^{k-1}p(x_i\leftarrow x_{i+1}) p(x_k) } { \prod_{i=2}^kp(x_{i-1} \to x_i) } \\ &= 1 + \frac{p_\mathrm{light}(x_k|x_{k-1})}{p(x_{k-1}\to x_k)} + \frac{N_\mathrm{VM}\pi r^2p(x_k)}{p(x_{k-1}\to x_k)} \sum_{t=2}^{k-2} p(x_t \leftarrow x_{t+1}) \prod_{i=t+1}^{k-1}\frac{p(x_i\leftarrow x_{i+1})}{p(x_{i-1}\to x_i)} \end{aligned}\]

令:

\[\begin{aligned} d_{\mathrm{PT}_m} &= \sum_{t=2}^m p(x_t \leftarrow x_{t+1})\prod_{i=t+1}^{m+1}\frac{p(x_i\leftarrow x_{i+1})}{p(x_{i-1}\to x_i)} \\ &= \frac{p(x_m\leftarrow x_{m+1})p(x_{m+1}\leftarrow x_{m+2})}{p(x_m\to x_{m+1})} + \sum_{t=2}^{m-1}p(x_t\leftarrow x_{t+1})\frac{p(x_{m+1}\leftarrow x_{m+2})}{p(x_m\to x_{m+1})}\prod_{i=t+1}^m\frac{p(x_i\leftarrow x_{i+1})}{p(x_{i-1}\to x_i)} \end{aligned}\]

把$m$换成$\tau = m + 2$,那么:

\[\begin{aligned} d_{\mathrm{PT}_3} &= 0 \\ d_{\mathrm{PT}_\tau} &= \frac{p(x_{\tau-2}\leftarrow x_{\tau-1})p(x_{\tau-1}\leftarrow x_{\tau})}{p(x_{\tau-2}\to x_{\tau-1})} + \frac{p(x_{\tau-1}\leftarrow x_{\tau})}{p(x_{\tau-2}\to x_{\tau-1})}d_{\mathrm{PT}_{\tau-1}} \\ w_\mathrm{PT_{bsdf}}(\bar x) &= \frac 1 { 1 + \dfrac{p_\mathrm{light}(x_k|x_{k-1})}{p(x_{k-1}\to x_k)} + \dfrac{N_\mathrm{VM}\pi r^2p(x_k)}{p(x_{k-1}\to x_k)} d_{\mathrm{PT}_{k}} } \end{aligned}\]

同理:

\[w_\mathrm{PT_{light}} = \frac 1 { 1 + \dfrac{p(x_{k-1}\to x_k)}{p_\mathrm{light}(x_k|x_{k-1})} + \dfrac{N_\mathrm{VM}\pi r^2p(x_k)}{p_\mathrm{light}(x_k|x_{k-1})} d_{\mathrm{PT}_{k}} }\]

计算$w_\mathrm{VM}$

整理一下形式:

\[\begin{aligned} \frac 1 {w_{\mathrm{VM}_t}(\bar x)} &= \frac{\prod_{i=2}^{k-1}p(x_{i-1} \to x_i)(p_\mathrm{light}(x_k|x_{k-1}) + p(x_{k-1}\to x_k))}{\prod_{i=2}^t p(x_{i-1}\to x_i)\prod_{i=t}^{k-1}p(x_i\leftarrow x_{i+1})p(x_k)\pi r^2} \\ &+ N_\mathrm{VM}\sum_{r=2}^{k-2}\frac{\prod_{i=2}^r p(x_{i-1}\to x_i)\prod_{i=r}^{k-1}p(x_i\leftarrow x_{i+1})}{\prod_{i=2}^t p(x_{i-1}\to x_i)\prod_{i=t}^{k-1}p(x_i\leftarrow x_{i+1})} \\ &= \mathcal W_1 + N_\mathrm{VM}\mathcal W_2 \end{aligned}\]

$\mathcal W_1$用于融合VM和PT,$\mathcal W_2$用于融合不同位置处的VM,接下来分别计算这俩。

计算$\mathcal W_{1}$

\[\begin{aligned} \mathcal W_1 &= \frac{\prod_{i=2}^{k-1}p(x_{i-1} \to x_i)(p_\mathrm{light}(x_k|x_{k-1}) + p(x_{k-1}\to x_k))}{\prod_{i=2}^t p(x_{i-1}\to x_i)\prod_{i=t}^{k-1}p(x_i\leftarrow x_{i+1})p(x_k)\pi r^2} \\ &= \frac{\prod_{i=t+1}^{k-1}p(x_{i-1}\to x_i)(p_\mathrm{light}(x_k|x_{k-1}) + p(x_{k-1}\to x_k))}{\prod_{i=t}^{k-1}p(x_i\leftarrow x_{i+1})p(x_k)\pi r^2} \\ &= \frac{p_\mathrm{light}(x_k|x_{k-1}) + p(x_{k-1}\to x_k)}{p(x_t\leftarrow x_{t+1})p(x_k)\pi r^2}\prod_{i=t+1}^{k-1}\frac{p(x_{i-1}\to x_i)}{p(x_i\leftarrow x_{i+1})} \end{aligned}\]

记$y_i = x_{k+1-i}$,则:

\[\begin{aligned} \mathcal W_1 = \frac{p_\mathrm{light}(y_1|y_2) + p(y_2\to y_1)}{p(x_t\leftarrow x_{t+1})p(y_1)\pi r^2}\prod_{i=1}^{k-(t+1)}\frac{p(y_{i+1}\leftarrow y_{i+2})}{p(y_i\to y_{i+1})} \end{aligned}\]

令:

\[d_{\mathrm{VMT}_m} = \prod_{i=1}^{m}\frac{p(y_{i+1}\leftarrow y_{i+2})}{p(y_i\to y_{i+1})}\]

并将$m$替换为$\tau = m + 2$,那么:

\[\begin{aligned} d_{\mathrm{VMT}_1} &= d_{\mathrm{VMT}_2} = 1 \\ d_{\mathrm{VMT}_\tau} &= \frac{p(y_{\tau-1}\leftarrow y_{\tau})}{p(y_{\tau-2}\to y_{\tau-1})}d_{\mathrm{VMT}_{\tau-1}}~~~(3 \le \tau \le k-t+1)\\ \mathcal W_1 &= \frac{p_\mathrm{light}(y_1|y_2) + p(y_2\to y_1)}{p(x_t\leftarrow x_{t+1})p(y_1)\pi r^2}d_{\mathrm{VMT}_{k-t+1}} \end{aligned}\]

计算$\mathcal W_2$

把$\mathcal W_2$按和式的下标拆成三项:

\[\begin{aligned} \mathcal W_2 &= \sum_{r=2}^{k-2}\frac{\prod_{i=2}^r p(x_{i-1}\to x_i)\prod_{i=r}^{k-1}p(x_i\leftarrow x_{i+1})}{\prod_{i=2}^t p(x_{i-1}\to x_i)\prod_{i=t}^{k-1}p(x_i\leftarrow x_{i+1})} \\ &= 1 + \sum_{r=2}^{t-1}\frac{\prod_{i=2}^r p(x_{i-1}\to x_i)\prod_{i=r}^{k-1}p(x_i\leftarrow x_{i+1})}{\prod_{i=2}^t p(x_{i-1}\to x_i)\prod_{i=t}^{k-1}p(x_i\leftarrow x_{i+1})} + \sum_{r=t+1}^{k-2}\frac{\prod_{i=2}^r p(x_{i-1}\to x_i)\prod_{i=r}^{k-1}p(x_i\leftarrow x_{i+1})}{\prod_{i=2}^t p(x_{i-1}\to x_i)\prod_{i=t}^{k-1}p(x_i\leftarrow x_{i+1})} \\ &= 1 + \mathcal W_{21} + \mathcal W_{22} \end{aligned}\]

然后分别整理$\mathcal W_{21}$和$\mathcal W_{22}$:

\[\begin{aligned} \mathcal W_{21} &= \sum_{r=2}^{t-1}\frac{\prod_{i=2}^{r}p(x_{i-1}\to x_{i})\prod_{i=r}^{t-1}p(x_i\leftarrow x_{i+1})\prod_{i=t}^{k-1}p(x_i\leftarrow x_{i+1})}{\prod_{i=2}^rp(x_{i-1}\to x_i)\prod_{i=r+1}^tp(x_{i-1}\to x_i)\prod_{i=t}^{k-1}p(x_i\leftarrow x_{i+1})} \\ &= \frac 1 {p(x_{t-1}\to x_t)}\sum_{r=2}^{t-1}p(x_r\leftarrow x_{r+1})\prod_{i=r+1}^{t-1}\frac{p(x_i\leftarrow x_{i+1})}{p(x_{i-1}\to x_i)} \\ \mathcal W_{22} &= \sum_{r=t+1}^{k-2}\frac{\prod_{i=2}^tp(x_{i-1}\to x_i)\prod_{i=t+1}^rp(x_{i-1}\to x_i)\prod_{i=r}^{k-1}p(x_i\leftarrow x_{i+1})}{\prod_{i=2}^tp(x_{i-1}\to x_i)\prod_{i=t}^{r-1}p(x_i\leftarrow x_{i+1})\prod_{i=r}^{k-1}p(x_i\leftarrow x_{i+1})} \\ &= \frac 1 {p(x_t\leftarrow x_{t+1})}\sum_{r=t+1}^{k-2}p(x_{r-1}\to x_r)\prod_{i=t+1}^{r-1}\frac{p(x_{i-1}\to x_i)}{p(x_i\leftarrow x_{i+1})} \\ &= \frac 1 {p(x_t\leftarrow x_{t+1})}\sum_{r=3}^{k-t}p(y_r\leftarrow y_{r+1})\prod_{i=r+1}^{k-t}\frac{p(y_i\leftarrow y_{i+1})}{p(y_{i-1}\to y_i)} \end{aligned}\]

令:

\[\begin{aligned} d_{\mathrm{VM}\to_m} &= \sum_{r=2}^{m}p(x_r\leftarrow x_{r+1})\prod_{i=r+1}^{m}\frac{p(x_i\leftarrow x_{i+1})}{p(x_{i-1}\to x_i)} \\ &= p(x_m\leftarrow x_{m+1}) + \sum_{r=2}^{m-1}p(x_r\leftarrow x_{r+1})\frac{p(x_m\leftarrow x_{m+1})}{p(x_{m-1}\to x_{m})}\prod_{i=r+1}^{m-1}\frac{p(x_i\leftarrow x_{i+1})}{p(x_{i-1}\to x_i)} \\ d_{\mathrm{VM}\leftarrow_m} &= \sum_{r=3}^{m}p(y_r\leftarrow y_{r+1})\prod_{i=r+1}^{m}\frac{p(y_i\leftarrow y_{i+1})}{p(y_{i-1}\to y_i)} \\ &= p(y_{m}\leftarrow y_{m+1}) + \sum_{r=3}^{m-1}p(y_r\leftarrow y_{r+1})\frac{p(y_m\leftarrow y_{m+1})}{p(y_{m-1}\to y_m)}\prod_{i=r+1}^{m-1}\frac{p(y_i\leftarrow y_{i+1})}{p(y_{i-1}\to y_i)} \end{aligned}\]

并将$m$替换为$\tau = m + 1$,那么:

\[\begin{aligned} d_{\mathrm{VM}\rightarrow_1} &= d_{\mathrm{VM}\rightarrow_2} = 0 \\ d_{\mathrm{VM}\leftarrow_1} &= d_{\mathrm{VM}\leftarrow_2} = d_{\mathrm{VM}\leftarrow_3} = 0 \\ d_{\mathrm{VM}\rightarrow_\tau} &= p(x_{\tau-1}\leftarrow x_\tau) + \frac{p(x_{\tau-1}\leftarrow x_{\tau})}{p(x_{\tau-2}\to x_{\tau-1})}d_{\mathrm{VM}\rightarrow_{\tau-1}}~~~(3 \le \tau \le t)\\ d_{\mathrm{VM}\leftarrow_\tau} &= p(y_{\tau-1}\leftarrow y_\tau) + \frac{p(y_{\tau-1}\leftarrow y_{\tau})}{p(y_{\tau-2}\to y_{\tau-1})}d_{\mathrm{VM}\leftarrow_{\tau-1}}~~~(4 \le \tau \le k-t+1) \\ \mathcal W_{21} &= \frac 1 {p(x_{t-1}\to x_t)}d_{\mathrm{VM}\rightarrow_t} \\ \mathcal W_{22} &= \frac 1 {p(x_t\leftarrow x_{t+1})}d_{\mathrm{VM}\leftarrow_{k-t+1}} \end{aligned}\]

Specular Event

如果某个顶点$x_i(2 \le i \le k-2)$或$y_i(3 \le i \le k-t+1)$处的散射是specular,那么在这里没法做vertex merging,有几个$d$需要对应地做出修改。

注意到:

\[d_{\mathrm{PT}_\tau} = \sum_{t=4}^{\tau}p(x_{t-2}\leftarrow x_{t-1})\cdots\]

在$\sum$中,$t=t_0$所代表的项对应了在$x_{t_0-2}$处进行的VM。因此,$x_i$为specular顶点意味着$d_{\mathrm{PT}_{i+2}}$的递推式中只包含上一项的乘积项,不包含另一个求和项。

类似地:

\[\begin{aligned} d_{\mathrm{VM}\rightarrow_\tau} &= \sum_{r=3}^\tau p(x_{\tau-1}\leftarrow x_\tau)\cdots \\ d_{\mathrm{VM}\leftarrow_\tau} &= \sum_{r=4}^\tau p(y_{\tau-1}\leftarrow y_\tau)\cdots \end{aligned}\]

在$\sum$中,$r = r_0$代表的项对应$x_{r_0-1}$或$y_{r_0-1}$处进行的VM,因此$x_i$或$y_i$为specular意味着$d_{\mathrm{VM}\rightarrow_{i+1}}$或$d_{\mathrm{VM}\leftarrow_{i+1}}$的递推式中只包含乘积项。

实现

光子图生成

注意到$d_{\mathrm{VMT}\tau }$的计算依赖于$p(y{\tau-2}\to y_{\tau-1})$和$p(y_{\tau-1}\leftarrow y_\tau)$,前者在构造光子路径时可以顺便记下来,但是后者的完整形式是$p(y_{\tau-1}\leftarrow y_\tau\leftarrow y_{\tau+1})$,其中的$y_{\tau+1}$为Camera Subpath的末端倒数第二个顶点,在构造光子图时是未知的。也就是说,光子$y_i$处记录的数据只能是$d_{\mathrm{VMT}{i-1}}/p(y{i-2}\to y_{i-1})$,实际的$d_{\mathrm{VMT}i}$只有在VM时才能计算。类似地,$y_i$处只记录$d{\mathrm{VM}\leftarrow_{i-1}}/p(y_{i-2}\to y_{i-1})$。

整理一下,光子$y_i$需要携带的信息至少包括$\beta_p, \mathrm{pdf}p, d{\mathrm{VMT}{i-1}}, d{\mathrm{VM}\leftarrow_{i-1}}, p_\mathrm{light}(y_1\mid y_2), p(y_2 \to y_1), p(y_1)$:

  1. $\beta_p, \mathrm{pdf}_p$
  2. $d_{\mathrm{VMT}{i-1}}/p(y{i-2}\to y_{i-1})$
  3. $d_{\mathrm{VM}\leftarrow_{i-1}}/p(y_{i-2}\to y_{i-1})$
  4. $(p_\mathrm{light}(y_1\mid y_2) + p(y_2 \to y_1)) / p(y_1)$

其中第四项可以预先乘到第二项上。

路径追踪

追踪一条路径的时候,需要携带的信息包括:

  1. $\beta, \mathrm{pdf}$
  2. $d_{\mathrm{PT}{i-1}}, p(x{i-2}\to x_{i-1}), p(x_{i-2}\leftarrow x_{i-1})$
  3. $d_{\mathrm{VM}\rightarrow_{i-1}}, p(x_{i-2}\to x_{i-1})$

每追踪到一个新顶点$x_a(a >= 2)$,都需要执行下面的操作:

  1. 如果$x_a$是光源表面的点,那么:
    • a = 2,则构成一条长度为2的路径,直接计算最终计算
    • a = 3,则存在BSDF采样和光源采样两种构成路径的技术,MIS之
    • a > 3,则存在两种PT技术和许多种PM技术,利用$d_\mathrm{PT}$计算出MIS权重
  2. 在光源表面采样一点$x_{a+1}$,连接$x_a$和$x_b$构成完整的路径,此时:
    • a + 1 = 3,则存在BSDF采样和光源采样两种构成路径的技术,MIS之
    • a + 1 > 3,则使用$d_\mathrm{PT}$计算MIS权重
  3. 搜索光子图中$x_a$周围的光子,对每个光子做VM,并用$d_{\mathrm{VM}\rightarrow}$计算其MIS权重