最近在尝试归纳UE的间接光方案，了解到其用于间接光计算的Lightmass流程使用的算法就是photon mapping，为了追本溯源，对整个光照计算逻辑有一个更为清晰的认识，这里对photon mapping算法进行了一番简单的学习，这里将学习材料整理之后文档输出出来，一方面希望读者看到有谬误之处可以不吝指正，另一方面也希望后面看到其他相关材料可以补充进来，不断完善相关主题的内容。
正文
1. Photon Mapping算法实现逻辑
Photon Mapping算法最早由Jensen在96年提出，中间经过众多大佬的优化与修正，产出了一系列的实现算法，这里将按照一定的逻辑关系输出多种算法的实现策略，方便理解与阅读。
1.1 标准算法
Jensen在96年提出的Photon Mapping（PM）算法是整个算法逻辑的基础，因此这里会先介绍这个算法的具体实现逻辑。
标准PM算法由两个pass组成，分别是Photon Map Generation Pass与Lighting Pass。
1.1.1 Photon Map Generation Pass
这个Pass主要用于完成Photon（光子）的发射以及Photon Map的创建工作，其实现逻辑给出如下：
- 从光源向各个方向发射photon，如下图所示
从光源视角来看，部分方向出发的photon是不会与场景发生碰撞的，因此为了节省消耗提升效率，这里可以通过为photon增加一个标记来判断是否需要进行碰撞检测迭代，通常会采用一个叫做projection map的贴图来指明有效的发射方向，如下图所示，红色方框中的那一段就是有效的发射方向：
那么如何判定是否会发生碰撞呢？简单来说，就是从光源视角，将场景分割成多个Cell，每个Cell对应于projection map上的一个像素，当Cell中没有物件时，将projection map上的对应像素标记为off即可。
如下图所示，不同光源的发射方向是不一样的，点光是均匀方向，面光源则是随机发射：
每个发射的photon的主要参数为flux而非Radiance，也就是光通量，这个数值通常用于表征发射功率，数值可以用光源的Flux除以发射的光子数来求得：
光子发出之后，就会进入与场景的交互过程，整个交互过程可以看成多次迭代，每次迭代为photon在当前的位置沿着当前的速度与场景发生的一次碰撞检测：
- 碰撞过程中将数据存储在photon map中
1.1 photon map说是一个map，实际上会将之以KD-Tree（也就是三维空间中的二叉树）结构进行存储。在Lighting Pass会需要进行大量的空间查找，使用KD-Tree有助于实现算法加速
1.2 实际上只有发生漫反射时的数据才需要存储，镜面反射的数据会在Lighting Pass中通过Ray Tracing来得到
1.3 photon map中像素数据格式如下图所示：
struct photon
{
float x,y,z;//碰撞位置
char p[4];//RGBE编码的光照flux
char phi, theta;//入射光方向
short flag;//用于KD-Tree结构的数据
}
每次碰撞后根据交互类型决定是否进行下一次迭代：
- 继续迭代
- 反射
- 折射
- 终止迭代
- 吸收
- 逸出，即射出场景之外
交互类型由概率确定的：现实中的光线与物件碰撞后是多种交互类型并存的，但是按照这种模式计算会增加复杂度，为了简化计算，假设photon碰撞后能量不变，每次碰撞只发生一种交互，交互类型由概率确定，即类似于俄罗斯轮盘，根据材质属性，设定各种交互类型的发生概率，根据概率触发后续行为。
1.1.2 Lighting Pass
Lighting Pass就是用photon map来完成场景光照计算，来深入实现细节之前，先来看看光照计算的总体公式。
1.1.2.1 光照公式
最终我们需要计算屏幕空间上每个像素（或者三维空间的probe的SH系数求解同样需要计算各个方向的Radiance或者Irradiance）的Radiance，而这个Radiance包含四个部分：
这四个部分的计算公式给出如下：
由于最终需要计算的是Radiance，而photon中存储的却是flux，因此公式需要经过一次转换：
由于
因此可以有：
1.1.2.2 光照计算逻辑
光照有两种计算方式，分别是直接使用photon map数据作为光照结果以及photon map作为间接光与焦散计算数据。
1.1.2.2.1 直接使用photon map数据作为光照结果
直接使用photon map数据作为光照结果的计算方式，其实现逻辑给出如下。
对于屏幕空间中对每个像素而言，可以直接根据photon map来估计其亮度与颜色，这过程本质上是概率密度估计。而由于光子分布是无规律的，因此可以使用非参数估计法，具体来说有如下三种方式：
1. 直方图估计
1.1 具体算法
1.1.1 将场景分割成大小相同的cell
1.1.2 统计每个cell中的光子数目占比m
1.1.3 将m除以cell的体积作为整个cell中的所有点的光子密度
1.2 特点
1.2.1 缺点：密度函数不够平滑
2. 核函数估计
2.1 具体算法
2.1.1 设定一个估计范围
2.1.2 统计这个范围内的光子数据
2.1.3 为范围内的每个光子设定一个权重，权重与到当前像素的距离平方成反比， 这是与直方图估计的主要区别
2.1.4 光子数目占比需要考虑权重，最终依然需要除以体积作为光子密度
** 2.2 特点**
2.2.1 优点：相对于直方图估计而言，密度函数变得平滑
3. KNN（k近邻）估计
3.1 具体算法
3.1.1 以目标点为球心，选取最近的k个光子作为样本
3.1.2 求得k个光子的最小包围球的半径r
3.1.3 光子密度=k/(nV)，k是光子数目，n是总的光子数目，V是包围球的体积
3.2 特点
3.2.1 缺点
3.2.1.1 光子数目较少，且r不是无穷小使得这个算法是有偏的，只有光子密度无穷高，r趋近于0，结果才是无偏的。r的存在会导致两种误差：boundary bias，物体边缘部分会存在偏差；topological bias，物体凹凸不平的区域会存在偏差。在使用不同的估算算法的时候，结果表现也有所不同：球面估计，通常是过估计，即过亮；碟形估计或者表面法向量约束，则会导致过暗。
直接使用photon map用于光照计算的特点为：
- 优点：计算效率高
- 缺点：内存消耗较高，存在低频误差，不适合用作直接光照输入数据
其结果如下图所示：
1.1.2.2.2 photon map作为间接光与焦散计算数据
因为photon map直接用于光照结果会存在低频误差等原因，因此后面通常会使用photon map作为间接光与焦散计算数据。
最终的光照计算会拆分成两条不同的计算路径：
- 光线追踪处理
- 漫反射表面的直接光照
- 镜面反射
- photon map处理
- 漫反射表面的间接光照
- 焦散光照
漫反射表面的间接光照中，由于photon分布比较稀疏，直接按照前面的非参数估计方法计算得到的结果精度较差，通常会采用final gathering（FG）算法来提升精度。
如下图所示，FG算法的实现逻辑是：
- 在屏幕空间创建一系列final gathering点，可以直接为每个像素分配一个
- 在每个FG点处，沿着法线朝着上半球面发射多条FG射线
- 每条射线与场景漫反射表面碰撞后，通过KNN算法求得碰撞点的光照亮度与颜色
- 将多条FG射线的采样结果进行平均
- 将多个FG点的计算结果进行平均
这个算法的特点有：
- 优点：可以使用较少的全局漫反射光子就能得到较好效果
- 缺点：耗时高，想要得到较好效果，需要生成数百条FG射线；不能消除boundary bias跟topological bias
焦散光照的计算这里就给出一个大概，后续有时间再来补充：photon map除了存储全局漫反射光子，还需要存储全局焦散光子（折射），这类光子的数量要较大，之后按照KNN算法进行直接光照计算，给出几张效果图：
原始的PM算法是有偏差的：
- boundary bias
- topological bias
表现为：
- 灰暗的墙角
- 错误的颜色辉映
- 漏光
1.2 photon ray splatting算法
这个算法是07年由Herzog等人提出来，跟原始算法相比，相当于将思路反过来。
整个算法依然是分成两个pass，分别是eye tracing跟photon tracing。
在eye tracing pass中，先进行视觉空间的光线追踪，为屏幕空间的每个像素发射一条射线，每条射线与漫反射表面的交点通过KD-Tree记录下来。
在photon tracing pass中，光源发射多个光子，这里的光子是一个带有一定宽度的光子，宽度会决定后面碰撞过程中的覆盖范围，如下图所示：
每个光子在碰撞的过程中通过前面的KD-Tree检测周边一定范围内的eye sample，将光子对一定范围内的eye sample进行亮度与颜色叠加。
这个算法的优点是可以较好的解决前面的两种偏差（boundary bias，topological bias），缺点则是依然存在偏差（proximity bias），这个偏差需要发射大量光子才能消除，在splatting算法中由于不需要存储photon map，而eye sample是跟屏幕空间像素有关，通过KD-Tree是可以存储下来的。
1.3 Progressive Photon Mapping（PPM）算法
这个算法是08年由Hachisuka等人提出，相当于将splatting算法中的photon tracing进行多轮，每一轮使用不同的半径r（这里的r是指光子的检测范围吗？），每一轮都渲染出一张图片，随着轮数的增加，r也越变越小，光子数目越来越多（是多轮累积的结果，还是随着轮数增加光子数目也增多？），结果也越来越好。由于倒转了顺序，光子搜集算法又从KNN变换回了直方图，虽然KNN能够以较少光子得到较好效果，但是由于PPM算法中光子已经较多，这个优势已经不明显了，由于光子数目增多了，所以在PPM算法中甚至不需要消耗高昂的Final Gathering了。
其不足之处在于难以模拟反射模糊、运动模糊、DOF等效果，效果图给出如下：
1.4 Stochastic Progressive Photon Mapping（SPPM）算法
这个算法是09年由Hachisuka等人提出，与PPM的区别是，eye tracing也是多轮，相当于进行多次splatting算法，每轮eye tracing会对射线方向进行轻微扰动，实际上并不是真的对eye tracing进行多轮，而是在photon tracing之后对eye sample进行一下扰动，如下图所示：
这个算法的优点是鲁棒、健壮，在光滑反射的效果远好于PPM；缺点则是算法效率低于PPM。
1.5 正向SPPM算法
这个算法是11年由Claude Knaus等人提出，跟SPPM算法逻辑一致，不同的是不再如Splatting算法一样翻转原始Photon Mapping算法的实现逻辑，而是采用跟原始Photon Mapping算法一样的算法流程。
2. Photon Mapping算法的特点
Photon Mapping算法的优点有：
- 容易模拟SDS（Specular-Diffuse-Specular）光线传播路径的效果，可用于模拟光线追踪难以实现的焦散现象
- 相对于光线追踪的高频瑕疵，Photon Mapping算法所导致的瑕疵较为低频，不易察觉
其缺点则为统计上有偏算法，有偏算法是指期望值跟实际数值存在偏差的统计方法
参考
[1] photon mapping学习笔记
[2] 再谈光子映射
[3] Lightmass源码分析之 经典Photon Mapping算法介绍
[4] Lightmass分析(一) 光子映射(Photon Mapping)简介
[5] Photon Mapping
[6] Global Illumination using Photon Maps
[7] Photon Mapping
[8] Final Gathering
