新浪博客

光线追踪及相关数学原理与实践（四）

2021-01-19 23:28阅读：

http://blog.sina.cn/dpool/blog/u/3390875822

光线追踪及相关数学原理与实践（四）
接上文继续，如果没看过的话可先看下上文。
三.光子映射（Photon Mapping）
首先要说明的是，接下来要介绍的光子映射也并不是全新的算法，它的实现依然要借助于前面提到的各种算法。所以，前文的光线追踪里讲的Ray Casting、WRT、DRT其实是狭义上的光线追踪，或者也可以称之为传统的光线追踪，它们最大的共同特点就是诞生于渲染方程出现之前。而实际中当我们碰到“光线追踪”这个词时，经常代表的是一个比较笼统的概念，指的是一个比较泛的技术族，也就是广义上的光线追踪，它包含传统的光线追踪以及所有基于它的技术，所以也包含路径追踪和光子映射、以及下文的MLT、还有本文未曾提到的一些算法。
BDPT的过程实际上是生成Light Path、生成Eye Path、两者做匹配，然后轮番进行。Eye Path是跟屏幕像素坐标有关的，但Light Path每次构建是在相同条件下独立进行的，数学上就是前文提到的IDD的情况。所以这个过程的问题就是每轮Eye Path做匹配的对象不应该仅局限于本轮构建出的Light Path，而应该是所有构建过的Light Path，只不过Light Path的历史数据流失了访问不到。所以要改良这
个过程的话我们自然的想到应该预先生成一大堆Light Path然后保存下来，这就是光子映射（Photon Mapping，简称PM）诞生的原因。
PM的算法出现于1993-1994年，第一篇论文是在1995年由Henrik Wann Jensen和Niels Jørgen Christensen发表。PM的核心思想是从光源发射大量光子，光子与场景发生碰撞时若满足一定条件将被存储到光子图（Photon Map）中，所以PM是一种对计算机存储空间消耗较大的算法。
由于光子图本身包含的数据量是相当庞大的，而后续的Backward Tracing又会对光子图进行非常多次的查询（数量级大致为渲染图像的像素数* DRT对每个像素的细分数），所以光子图的查询算法对渲染时间至关重要。要想降低每次查询的时间复杂度就得提前用合适的数据结构来表示光子图，这里通常采用的数据结构是K-D树（K-Dimensional Tree）。它的作用和计算光线与物体碰撞检测时常用的包围体层次结构（Bounding Volume Hierarchy，简称BVH）一样，都属于一些加速光线追踪过程的手段。
顾名思义，K-D树本身是用来划分K维空间的，它本质上是一棵平衡二叉树。先来看下K-D树的创建和最近邻节点查询：创建时每次对方差最大的维度做分割，分割以该维度的中位数做区分，再次进行分割时从剩余维度中继续以上步骤直到新的一轮；查询时先找到最近的叶子节点，然后进行回溯向父节点及兄弟节点递归查询有没有更近的节点。
光线追踪及相关数学原理与实践（四）
图3-1 光子图示意
例三.设x,y,z∈[0,10]的三维空间区域O中有点集：
{(1,4,7),(3,8,5),(4,5,2),(6,3,9),(8,1,3),(9,7,4)}
（1）K-D树的创建
光线追踪及相关数学原理与实践（四）
X方向上的方差最大，所以首先应分割X方向，中间点是(4,5,2)或(6,3,9)可任取一点，在这里取(4,5,2)。所以做垂直于X轴且经过点(4,5,2)的平面，将三维空间O分割成两部分。
对于(4,5,2)所划分的x值较小的空间，有(1,4,7)、(3,8,5)两个点：
光线追踪及相关数学原理与实践（四）
所以先做垂直于Y轴且经过(1,4,7)的平面。然后由于此轮只剩下Z轴没有切分，所以再做垂直于Z轴且经过(3,8,5)的平面。
对于(4,5,2) 所划分的另一侧空间，有(6,3,9)、(8,1,3)、(9,7,4)三个点：
光线追踪及相关数学原理与实践（四）
所以先做垂直于Z轴且经过(9,7,4)的平面。然后由于此轮只剩下Y轴没有切分，所以对于(9,7,4)的子树都做垂直于Y轴的平面，分别经过(6,3,9)、(8,1,3)。
最终该点集对空间O的划分图示如下：
光线追踪及相关数学原理与实践（四） 图3-2 K-D树对三维空间的划分
（2）K-D树的最近邻节点查询
设查询的点为P(7.6,3.7,4.2)。先对K-D树进行深度优先搜索（Depth First Search，简称DFS），得到叶子节点(6,3,9)。(7.6,3.7,4.2)与(6,3,9)的距离为5.11。P到平面z=4的距离为0.2<5.11，所以还需检查(9,7,4)及其另一子树(8,1,3)。P到(9,7,4)的距离为3.59，到(8,1,3)的距离为2.98，所以目前已知P的最邻近节点更新为(8,1,3)。P到平面x=4的距离为3.6>2.98，由于点(4,5,2)在平面x=4上，所以若以2.98做球P不可能包含点(4,5,2)更不可能包含(4,5,2)另一侧空间的点，所以查询结束，离P最近的点是(8,1,3)。
了解K-D树的基本知识后，具体看下PM的过程：
（1）Forward Tracing
要把光源理解成大量光子的集合体，可以形象的看作在Houdini软件里对光源进行了Vellum Configure Grain节点的处理，假设光源的辐射通量是Φ(W)，一共由N个光子组成，则一个光子代表的辐射通量就是：
光线追踪及相关数学原理与实践（四）
然后分别对每个光子进行Forward Tracing。有些论文会把把ΔΦ当做光通量，无所谓的，这只是光度学学科上的一个叫法，考虑了人眼主观感受因素后通过光谱光视效率函数对辐射通量做了次转换而已。
（2）构建光子图
根据上面得到的光子数据，构建K-D树来表示光子图，树的建立算法和上文讲述的一样。每次找中位数进行空间划分的过程本质上就是个排序过程，不过由于光子数量特别庞大尤其是进行第一次空间划分的时候，所以需要寻找一个高效的排序算法。而我们每次排完其实只需要保证中位数节点的所有左子树的节点都不大于该节点，所有右子树的节点都不小于该节点，至于左右子树都是无序的即可，因为左右子树以后每次排序时要划分的空间维度一直在变，所以每次排序的结果是不需要所有元素都有序，这样就可以把排序算法的时间复杂度降到快速排序的O(nlogn)以下的水平，详细步骤可参考C++11里nth_element函数的实现。
光线追踪及相关数学原理与实践（四）
图3-3 将场景（左）的光子图（右）可视化显示的效果
（3）Backward Tracing
光子图记录的是场景的照明信息，确切的说是碰撞点的入射通量，Backward Tracing时可利用光子图中的信息估计光子密度，进而估计该点的辐射亮度。
根据辐射通量、辐射照度、辐射亮度的定义，可以将入射的辐射亮度表示成：
光线追踪及相关数学原理与实践（四）
将上式带入渲染方程式2-15，得：
光线追踪及相关数学原理与实践（四）
所以光子密度的估计的思路可以是以查找点O为球心做一个能包含K个光子数的球体O，该球半径越小则光子密度越大。ΔΦp代表球体O内各个光子的辐射通量，ΔA代表球体O的投影圆面积，即：
光线追踪及相关数学原理与实践（四）
其中R为球体O的半径
光线追踪及相关数学原理与实践（四）
图3-4 球体法估计光子密度
因此对光子图的查询实际上是要对K-D树进行K近邻（K Nearest Neighbour，简称KNN）查询，而该查询算法其实并不需要像上述最近邻节点查询那样要先按DFS到叶子节点，而是直接从根节点开始查询即可，并用一个容量为K的大顶堆或优先级队列记录离查询点最近的K个光子。我们之所以引入K-D树的实质目的就是为了能降低这里的KNN查询的时间复杂度。
以上给出了一种光子密度的估计方式，此方案实现比较简单，不过很容易想到的一个缺陷就是在模型结构转折处的光子密度会估计不准，比如两面墙的交界边附近。因为即便一个面上的光子实际是分布均匀的，但在这个面的边缘地带做球体会囊括相邻面上的光子，导致用半径更小的球体就可以包含K个光子，对最终画面效果造成的影响是在结构转折处会莫名其妙的突然变亮。这一问题的解决办法是改用被Henrik Wann Jensen称为Disc的几何体，如下图所示，即沿着查询点的法线方向被压扁过的球体，这样能使得面的边缘处会在该面上寻找更多的光子，减弱受到其它面上的光子的影响。
光线追踪及相关数学原理与实践（四）
图3-5 用Disc进行KNN查询
该方案还有另一个缺陷就是这样处理的渲染结果通常会比较模糊。究其原因，我们现在在做的事情本质是就是在用一些离散的光子样本来拟合一个能反应光子分布的真实函数，从数学思想上讲，这是在做回归分析；从信号处理的角度讲，就是在做滤波，而前面的思路实际上是使用了一个均值滤波器，在学数字图像处理时我们知道均值滤波的缺点是由于不考虑权重因素导致细节丢失严重，所以缓解模糊问题的解决方案就是改用其它滤波器。Henrik Wann Jensen在他的PHD论文中推荐使用锥形滤波器，该滤波器本质是一个加权求和的过程，让光子携带的辐射通量在求和时的权重随着离查询点的距离的增大而减小，即：
光线追踪及相关数学原理与实践（四）
其中r为光子到查询点的距离，k（k≥1）是为了可以不让边界上的光子权重为0而引入的滤波器特征常数。在加入权重影响后，Jensen给出了用锥形滤波器计算的公式：
光线追踪及相关数学原理与实践（四）
我们注意到该式分母位置多了个因子(1-2/(3k))，至于其来历Jensen并没有对此做出解释，也没有查到其他学者对此因子的推导过程。但其实只要熟悉各种积分，要搞清这个因子的由来并不困难。在讲MIS时也提过，权重算法的设计要遵循总和为1的原则。所以我们假设如果按式3-5处理的话，先求出在投影圆内的权重总和是多少，然后再除以此和就做到归1化了。这个总和的求解抽象成数学问题就是：在一个半径为r的圆内的点的值为w，求该圆内所有值的总和。很明显这无非就是一个在该圆的区域上的积分问题，用二重积分转极坐标就可轻松求出，具体过程如下：
光线追踪及相关数学原理与实践（四）
每个光子的权重提公因式后所以就有了式3-6所示的要在求和符号前面除以(1-2/(3k))ΔA。
PM在光线追踪领域的应用非常之广，比如著名的V-Ray渲染器，是当前比较主流的光线追踪算法。PM也有一些改进的算法，比如较有名的渐进式光子映射（Progressive Photon Mapping，简称PPM）。

PM的实践方面，我使用的是两个结构非常复杂的3D扫描模型，并且加了调试功能——可以把得到光子图可视化显示出来，当发射了10万个光子时，光子图如下图所示：
光线追踪及相关数学原理与实践（四）
图3-6 光子图
可以看到有的地方光子密集，比如半球光源的周围，这里最终会形成光源在天花板上的光晕；有的地方光子稀疏，比如两件玻璃工艺品周围的一些区域，这些地方最终会形成投影。并且能观察到左边绿墙对天花板、后墙、地板的左侧和右边红墙的光照影响以及右边红墙对天花板、后墙、地板的右侧和左边绿墙的光照影响。
下图是我用PM进行渲染的效果。结构复杂的玻璃工艺品的光学现象呈现在了我们眼前。墙壁上团状的低频噪声是PM经常出现的现象，发射更多的光子可以得到更好的渲染质量当然耗时也会越多。
光线追踪及相关数学原理与实践（四）
图3-7 PM的实践





四*.梅特波利斯光照传输（Metropolis Light Transport）
在现实中一些复杂的场景里，经常会出现更为极端隐蔽光源问题，在此情况下对于前述所有方法而言有效光照路径的追踪效率依旧低下。比如如图4-1所示的室内结构，对于Room3内的物体而言，一条能找到光源Window的有效光照路径必须还要能成功通过Door1和Door2才行，若用常规的算法渲染必然会浪费大量的路径计算。
光线追踪及相关数学原理与实践（四）
图4-1 户型图
梅特波利斯光照传输（Metropolis Light Transport，简称MLT）能较好的解决该问题。MLT所基于的前提是一条有效光照路径的附近的光照路径也很有可能是有效的。所以其核心思想就是当在一个复杂的场景中好不容易找到一条能到达光源的路径后，就应该在该路径附近寻找更多的路径。而在一条路径附近随机寻找另一条路径的方法就是MLT的一个重要概念——突变策略（Mutation Strategy）。
光线追踪及相关数学原理与实践（四）
图4-2 有效光照路径附近的光照路径也更可能有效
MLT最早是由Eric Veach于1997年提出，此方法也被称之为Original MLT或Veach-Style MLT，但Original MLT算法上过于复杂，实现起来非常困难，以至于当时世界上没有人能把它实现出来，包括Veach自己，直到在Veach提出后的第13年即2010年才终于有人能把它实现出来。实际中，人们在这期间使用的MLT算法主要是2002由Kelemen提出的Primary Sample Space MLT（简称PSSMLT），因为相比Original MLT而言，PSSMLT更容易于理解和实现些。2014年，Hachisuka在PSSMLT的基础上做了小幅度改进提出了Multiplexed MLT（简称MMLT）。
在此就不对MLT展开叙述了，因为MLT牵扯到的理论比较复杂并且实际应用上目前而言也不太广泛。MLT的算法也还处于更新迭代中，近几年也有新的重要研究成果不断涌现，其中较知名的是在2017年SIGGRAPH中由Jacopo Pantaleon提出的Charted MLT（简称CMLT）以及在2018年SIGGRAPH中由Benedikt Bitterli等人提出的Reversible Jump MLT（简称RJMLT）。





写在后面
站在一个更高的层次去看上面干的事情其实就是设计光照系统，纵观50多年的光线追踪发展史，一个很大的特点就是系统能稳定运转的前提条件在不断减少，而整个工学科领域往往都是一个越好的系统应对各种条件的能力越强，这种能力被称为鲁棒性（Robust），这也是PBR领域一些成熟方案之所以能成为经典的原因。

1. 光线追踪的价值
可以分两方面来看，因为技术的价值往往会具有学术性的一面和商业性的一面：
在学术性上，光线追踪是理解PBR必不可少的基础知识，它和PBR是相辅相成的关系，不了解光线追踪很难对PBR有较深入的认识，脱离PBR去研究光线追踪也会一头雾水。在一些国内外计算机图形艺术相关专业一流的高校里，这些专业的本科或研究生的渲染课程或多或少都会涉及到光线追踪，而且网络上这块的一些具体实现很多都是高校的学生在搞，所以学术价值是毋庸置疑的。
说到高校，在渲染领域含金量比较高的，我想先提一下达特茅斯学院（Dartmouth College）。Dartmouth不仅是常春藤联盟成员，也是Basic语言的诞生地。以下是该校的学生作品：
光线追踪及相关数学原理与实践（四）
图 学生作品
光线追踪及相关数学原理与实践（四）
图 学生作品
下面这幅是知名度较大的斯坦福大学（Stanford University）的学生作品，其中对布料质感的模拟还是很棒的：
光线追踪及相关数学原理与实践（四）
图 学生作品

在商业性上，总体而言的话，像开头讲述的那样现阶段光线追踪在离线渲染领域的应用相对而言比较成熟些，比如室内外效果图、电影、广告等；在实时渲染领域光线追踪的应用如日方升，比如游戏、虚拟现实等。
就游戏领域而言的话，在离线渲染方面，光线追踪其实也有一些应用，比如预烘焙，再者就是相关游戏视频比如OP、宣传片等；在实时渲染方面，目前集中于国外一些用Frostbite之类的物理引擎开发的3A级PC游戏大作。但是，国内行业的现状却演化成同质化的手游比比皆然，而沾边点的应用也就限于对云这种Volume用一下光线步进（Ray Marching），而且还得做不少取舍来优化，想要在移动平台上普及光线追踪的话诚然还需要一定的时间，所以如果是抱有急功近利的心态去研究光线追踪来追求浮躁的商业化技术输出的话，那估计得让你失望了。
不过学术价值在一定条件下是可以转换成商业价值的。Blinn定律告诉我们：“As technology advances, rendering time remains constant.”——随着技术发展，渲染时间不变。因为人们对高质量画面的需要也会日益增长，所以硬件的不断革新虽然理论上允许渲染耗时更少，但实际上反而一定会采用更复杂的渲染技术来追求更高质量的画面，哪怕牺牲掉渲染速度的增益。而面对现实世界中纷繁复杂的光照现象，当追求照片级真实感渲染（Photo-Realistic Rendering，简称PRR）的效果时，在渲染每个屏幕像素的时候就必须要知道整个场景的信息实现全局光照，这点在本文的开头就已经点明，然而光栅化对此却无能为力，这时光栅化的发展就会陷入瓶颈，所以在实时渲染领域里光线追踪取代光栅化是迟早的事，各大游戏引擎的实时光线追踪也因此成为业界当下比较热门的渲染课题。也许现在说光栅化时代的终结、实时光线追踪时代的来临有点为之过早，这是今天显卡厂商的用语，但是可以确信光线追踪是游戏渲染的明天。



2.光线追踪的学习
首先，艺术层面上，对现实世界的观察和理解非常重要，毕竟艺术来源于生活。PBR的本质就是用计算机模拟现实效果，所以自己得先清楚现实世界究竟是什么样子，平常留心和思考各种光照现象的成因。举几个例子：
（1）漫反射的相互反射（Diffuse Inter-Reflections）
相对于金属材质的反射，漫反射的相互反射很容易被忽略，但却对表现非常重要。想想以前在画室静物水粉写生学画果子的时候，刚开始眼睛没有受过训练看到的梨就是黄色的、苹果就是红色的，后来知道一个果子要画很多个色块，但这种色彩变化看起来很微妙，经常拿不定主意到底色相是更偏什么一点，再后来知道确定不了的时候就找找周围物体的颜色往这偏点，当然色感很好的同学能直接看出来。在色彩中常说的颜色是“你中有我，我中有你”，其实依据的就是漫反射的相互反射，画过水彩画的话会体会更深些。下图是找的以前我在画室学画时的一幅静物水粉来说明一下：
光线追踪及相关数学原理与实践（四）
图 个人水粉画
下面是我的一个未上漆的木头材质球，然后我拿静物摄影常用的摄像卡纸的补光面当背景，用三脚架固定相机在同一方位拍摄。衬底是张普通的打印纸，当打印红色和绿色时，拍摄的照片分别如下图所示：
光线追踪及相关数学原理与实践（四）
图 红纸上木头材质球的照片
光线追踪及相关数学原理与实践（四）
图 绿纸上木头材质球的照片
可以看到不同颜色的纸张对木头材质球的影响，特别是材质球底部的色彩倾向变化非常明显，同时也能感受到两张照片给人造成的不同冷暖感觉。
渲染时若要表现的真实就必须把这点体现出来。下图中左侧是没有考虑漫反射的相互反射的情况，给人的感觉像是本来有角色和场景两张图片，然后找了个P图水平逊色点的人在Photoshop里把角色抠了下来拖到了场景里，根本没有体现出光照系统内元素之间的关系；相反右侧是考虑了漫反射的相互反射，也许程度上略有夸张但整体看起来更真实。
光线追踪及相关数学原理与实践（四）
图 有（右）无（左）考虑漫反射的相互反射的效果对比
（2）焦散（Caustics）
上文的一些实践中场景里的玻璃球在地面上形成的亮斑叫做焦散（Caustics）。下图是我在阳光下实际拍摄的我的一个玻璃材质球：
光线追踪及相关数学原理与实践（四）
图 玻璃材质球照片
焦散是光线通过表面不平的半透物体后由于光的折射造成的在投影面出现明暗偏移的现象，比如水底的水光。下图是找的以前我在山上随拍的张照片，能明显看到有阳光的地方在水底的形成的焦散现象：
光线追踪及相关数学原理与实践（四）
图 风景随拍
若在焦散区域没有足够的反弹光线经过半透体对光源进行采样，往往会在焦散区域形成明显的噪点。 MLT的思想在模拟焦散效果上较具优势。

其次，技术层面上，数学基础也非常重要。计算机只是个工具而已，相信对光线追踪的具体实现感到困惑的人也不会是因为代码语法上有障碍，原因就是光线追踪的技术难点是落在数学上，而且不再拘泥于传统的向量、矩阵之类的线性代数知识，大量的概率论和高等数学的知识也都会用上。
然后，关于光线追踪的书籍，《Physically Based Rendering: From Theory To Implementation, Third Edition》是在此领域公认的比较权威的，这就是业内人士常提到的PBRT。下图是我用PBRT的的库渲染的第三方场景：
光线追踪及相关数学原理与实践（四）
图 渲染效果
另外，在硬件方面，使用DXR研究光线追踪对电脑显卡的配置是有要求的，一般的个人笔记本是招架不住的，除非自带雷电3接口还可以尝试外接显卡补救。
总体而言，光线追踪的内容体系比较庞大，想要掌握的话需要投入不少学习时间。本文是篇幅有限省去了很多的内容，比如无偏性和收敛性的证明这种很理论化的、俄罗斯转盘这种很好理解的等等等等，实际学起来并不会像看篇文章这么轻松。光线追踪也还有许多前沿的效果需要研究，比如对BSSRDF这种复杂材质的渲染、对真实毛发这种复杂模型的渲染等等。



















我的更多文章

下载客户端阅读体验更佳

APP专享