我们知道，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$，采样该路径的方法一共有三类：
- Unidirectional PT，直接用一系列BSDF采样构造出整个路径
- Unidirectional PT，但在到达$x_{k-1}$后转而使用光源采样得到$x_k$
- 在$x_2, \ldots, x_{k-2}$处使用VM（Vertex Merging），融合光子图中的顶点，得到剩下的路径 d 这些方法对应的路径pdf为：
其中$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 | y_2), p(y_2 \to y_1), p(y_1)$： |
- $\beta_p, \mathrm{pdf}_p$
- $d_{\mathrm{VMT}{i-1}}/p(y{i-2}\to y_{i-1})$
- $d_{\mathrm{VM}\leftarrow_{i-1}}/p(y_{i-2}\to y_{i-1})$
-
$(p_\mathrm{light}(y_1 y_2) + p(y_2 \to y_1)) / p(y_1)$
其中第四项可以预先乘到第二项上。
路径追踪
追踪一条路径的时候，需要携带的信息包括：
- $\beta, \mathrm{pdf}$
- $d_{\mathrm{PT}{i-1}}, p(x{i-2}\to x_{i-1}), p(x_{i-2}\leftarrow x_{i-1})$
- $d_{\mathrm{VM}\rightarrow_{i-1}}, p(x_{i-2}\to x_{i-1})$
每追踪到一个新顶点$x_a(a >= 2)$，都需要执行下面的操作：
- 如果$x_a$是光源表面的点，那么：
- a = 2，则构成一条长度为2的路径，直接计算最终计算
- a = 3，则存在BSDF采样和光源采样两种构成路径的技术，MIS之
- a > 3，则存在两种PT技术和许多种PM技术，利用$d_\mathrm{PT}$计算出MIS权重
- 在光源表面采样一点$x_{a+1}$，连接$x_a$和$x_b$构成完整的路径，此时：
- a + 1 = 3，则存在BSDF采样和光源采样两种构成路径的技术，MIS之
- a + 1 > 3，则使用$d_\mathrm{PT}$计算MIS权重
- 搜索光子图中$x_a$周围的光子，对每个光子做VM，并用$d_{\mathrm{VM}\rightarrow}$计算其MIS权重
PREVIOUS符号距离场生成
NEXT关于HLSL中的矩阵传参