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_1{x}_2$，我们简单地从摄像机镜头上的点$x_1$发出射线，击中$x_2$处的光源，不需要做什么特别的处理。

对长度为3的路径$x_1{x}_2{x}_3$，我们使用MIS（Multiple Importance Sampling）结合BSDF采样和光源采样，也不需要PM的参与。

长度超过3的路径

对长度$k>3$的路径$\bar{x}=x_1{x}_2\cdots x_k$，采样该路径的方法一共有三类：

1. Unidirectional PT，直接用一系列BSDF采样构造出整个路径
2. Unidirectional PT，但在到达$x_{k-1}$后转而使用光源采样得到$x_k$
3. 在$x_2,\dots ,x_{k-2}$处使用VM（Vertex Merging），融合光子图中的顶点，得到剩下的路径

这些方法对应的路径pdf为：

$$\begin{array}{rl}{p}_{\mathrm{P}{\mathrm{T}}_{\mathrm{bsdf}}}(\bar{x})& =p(x_1)\prod _{i=2}^{k}p(x_{i-1}\to x_i)\\ p_{\mathrm{P}{\mathrm{T}}_{\mathrm{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}^{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\end{array}$$

其中$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{P}{\mathrm{T}}_{\mathrm{bsdf}}}(\bar{x})+p_{\mathrm{P}{\mathrm{T}}_{\mathrm{light}}}(\bar{x})+N_{\mathrm{VM}}{\sum }_{t=2}^{k-2}{p}_{{\mathrm{VM}}_t}(\bar{x})}$$

计算wPT

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

$$\begin{array}{rl}\frac{1}{w_{\mathrm{P}{\mathrm{T}}_{\mathrm{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}^{t}p(x_{i-1}\to x_i){\prod }_{i=t}^{k-1}p(x_i\leftarrow x_{i+1})p(x_k)}{{\prod }_{i=2}^{k}p(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^{2}p(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{array}$$

令：

$$\begin{array}{rl}{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{array}$$

把$m$换成$\tau =m+2$，那么：

$$\begin{array}{rl}{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{P}{\mathrm{T}}_{\mathrm{bsdf}}}(\bar{x})& =\frac{1}{1+\frac{p_{\mathrm{light}}(x_k|x_{k-1})}{p(x_{k-1}\to x_k)}+\frac{N_{\mathrm{VM}}\pi r^{2}p(x_k)}{p(x_{k-1}\to x_k)}{d}_{{\mathrm{PT}}_k}}\end{array}$$

同理：

$$w_{\mathrm{P}{\mathrm{T}}_{\mathrm{light}}}=\frac{1}{1+\frac{p(x_{k-1}\to x_k)}{p_{\mathrm{light}}(x_k|x_{k-1})}+\frac{N_{\mathrm{VM}}\pi r^{2}p(x_k)}{p_{\mathrm{light}}(x_k|x_{k-1})}{d}_{{\mathrm{PT}}_k}}$$

计算wVM

整理一下形式：

$$\begin{array}{rl}\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{array}$$

${\mathcal{W}}_1$用于融合VM和PT，${\mathcal{W}}_2$用于融合不同位置处的VM，接下来分别计算这俩。

计算W1

$$\begin{array}{rl}{\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{array}$$

记$y_i=x_{k+1-i}$，则：

$$\begin{array}{r}{\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{array}$$

令：

$$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{array}{rl}{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{array}$$

计算W2

把${\mathcal{W}}_2$按和式的下标拆成三项：

$$\begin{array}{rl}{\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{array}$$

然后分别整理${\mathcal{W}}_{21}$和${\mathcal{W}}_{22}$：

$$\begin{array}{rl}{\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}^{r}p(x_{i-1}\to x_i){\prod }_{i=r+1}^{t}p(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}^{t}p(x_{i-1}\to x_i){\prod }_{i=t+1}^{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}^{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{array}$$

令：

$$\begin{array}{rl}{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{array}$$

并将$m$替换为$\tau =m+1$，那么：

$$\begin{array}{rl}{d}_{\mathrm{VM}{\to }_1}& =d_{\mathrm{VM}{\to }_2}=0\\ d_{\mathrm{VM}{\leftarrow }_1}& =d_{\mathrm{VM}{\leftarrow }_2}=d_{\mathrm{VM}{\leftarrow }_3}=0\\ d_{\mathrm{VM}{\to }_{\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}{\to }_{\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}{\to }_t}\\ {\mathcal{W}}_{22}& =\frac{1}{p(x_t\leftarrow x_{t+1})}{d}_{\mathrm{VM}{\leftarrow }_{k-t+1}}\end{array}$$

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{array}{rl}{d}_{\mathrm{VM}{\to }_{\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{array}$$

在$\sum$中，$r=r_0$代表的项对应$x_{r_0-1}$或$y_{r_0-1}$处进行的VM，因此$x_i$或$y_i$为specular意味着$d_{\mathrm{VM}{\to }_{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}{\to }_{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}\to }$计算其MIS权重