9、光线追踪

简介

为什么需要光线追踪呢？因为Blinn-Phong这种局部模型无法处理全局效果

如上图中房屋顶部的所接受到的光可不仅仅是Blinn-Phong模型考虑的直接光源，还有可能是来自窗外的光源照射到地板，再发生反射照射到了房屋顶部，而这部分光是局部光照模型没有考虑到的，而光线追踪正是为了解决这种问题所提出的一种全局光照模型。

换个角度来考虑，光栅化虽然快但是得到的图像质量一般较低，为了追求更好的结果当然就会寻求更加完美的模型了。

光线追踪听名字就知道，讨论的核心是光线，因此我们首先对光线做一些假设

明白了光线的一些假设之后，想一想人为什么能看到不同的物体？是因为从物体表面上有光进入了人眼。那么能不能逆向思考一下，是不是也可理解为人眼发出了很多感知光线碰撞到了物体，所以可以看见呢？在古代可还真就有不少人这么想

当然，现代物理知识已经告诉我们这种观点是错误的，但是并不妨碍从中获取一些灵感，考虑一下对光线的第三条假设：光路可逆，所有进入到人眼的光，都可从人眼发出光按照原路反方向返回，那么利用这种模拟从人眼发射光线的方法不就可以还原出所有的光路了呢？没错这就是光线追踪的核心想法，正着不行那就反着来

Ray Casting

从人眼或摄像机向近投影平面上的每一个像素点发射一条光线，判断与场景物体的交点

当然一条光线自然可能会与不止一个物体相交，但是考虑遮挡关系，只去找最近的交点。接着连接该交点和光源，只要判断这条连线之间是否有物体存在就可以知道该交点是否在阴影之中

紧接着，自然可以利用Blinn-Phong模型对这个点进行局部光照模型计算，得到该像素的颜色，那么遍历所有近投影平面上的像素就能得到一张完整的图像。但如果光线追踪仅仅是在第一步Ray Casting就停止的话，那么它的效果与局部光照模型是一样的，因此我们需要第二步，真正的考虑全局效果

Recursive (Whitted-Style) Ray Tracing

考虑第一步中所做的Ray Casting，该条光线第一个与圆球物体相交，假设该圆球是一个玻璃球，那么便会发生镜面反射，如图

当然除了镜面反射之外，自然也存在折射，同时反射与折射出去的光线会可能与场景中的物体再次碰撞，发生第二次折射与反射

从图中可以见到，不仅仅是与圆球相交的那一点可以贡献光到达眼睛，折射与反射之后再与物体相交的点也可以贡献光(光路可逆原理)。简而言之，除了直接从光源照射到圆球交点再沿着 eye rays(第一条发射的光线)到眼睛中，也可能存在这样一种情形，有光照射到其他物体，再沿着eye rays的反射或折射的光线方向传回人眼

因此每一个交点的颜色贡献来自这样种几类型 直接光照，反射方向间接光，折射方向间接光（如果有折射的话）

下一步将这些所有交点与光源连接，称这些线为shadow rays（因为可以用来检测阴影），计算这些所有点的局部光照模型的结果，将其按照光线能量权重累加(该做法与递归过程等价，读者可以看看伪代码思考一下)，最终得到近投影平面上该像素点的颜色！而这就是一个全局光照模型了，因为不仅仅考虑了直接光源的贡献，还考虑各种折射与反射光线的贡献

光线的表示方法

我们可以将每一条光线想象成一条射线，那么每一条光线都会由起点及方向这两个属性所固定，如下图所示

除了起点 o, 以及方向 d 之外，还额外定义了一个参数 t 来表示光线行进的长度

光线与物体求交

光线与隐式曲面求交

以一个球体为例，二者表示方程

光线的表示方法在上节已经介绍过，对于一个球体来说，其表面上所有点 p, 到圆心c的距离是固定为 R 的， 也就得到了上述的球的隐式曲面方程

那么对于一个光线会在什么时候与球相交呢

当然是在一个点即满足光线方程，又满足球体方程的时候，所以可以计算如下，把p = o + t d 代入球体方程，利用一元二次方程的解法即可得到参数 t 值

同样的根据 b^2-4ac的正负关系，即可判断光线与球是一个交点还是两个交点又或是没有交点

这里只举了对一个球的隐式曲面交点的计算，对于所有其他隐式曲面过程都是类似的

光线与显示曲面求交

真正在图形学中大量运用的其实是显示曲面，更具体来说就是许许多多个三角形，因此如何判断一条光线与显示曲面的交点，其实也就是计算光线与三角形面的交点。对于任意一个平面，可以用如下图中的式子表达

图中对于平面方程的讲解已经很清楚。那么到这里其实已经成功把对显示曲面的求交又转化为了类似隐式曲面求交的方法，对于任意一个三角面来说，它一定处于一个平面之上，只需求出光线与平面的交点，再判断该交点是否在三角形内，就可以得到光线是否与三角形面相交的结果了

计算光线与平面交点的过程

**
得到参数 t 之后，自然可以计算出交点，并且再去计算出重心坐标就能判断该交点是否在三角形内了，但是这种方法略显繁琐，能一步就得到结果

直接将点的形式用重心坐标的形式表示，随后利用克莱姆法则求解线性方程组即可

反射与折射

反射方向的计算

反射方向计算相对容易，如下图所示，已知 l n想要求出反射方向r

计算如下：

r = 2 n ( l ⋅ n ) − l

**几何含义便是 入射光线 l 在法向上投影的两倍再减去入射光线 l 方向，即可得到r **

折射方向的计算

折射方向的推导其实是由斯奈尔定理(Snell’s Law)得来的

**其中n ，n t 分别代表反射平面两边的反射率，如下图所示左半部分为n，右半部分为n t **

但是，这仅仅是求得了反射角度，更希望得到的是向量形式的方向 t，因此根据上图，可以得到如下关系(图中皆为单位向量)：

其中 b 是未知的，但是可以根据入射光线 d 推出

如此(3)式当中所有的变量都是已知，计算得到折射方向 t 如下

菲涅耳反射

显而易见的，一定要保证根号里面是正数，那么有没有可能会是负数呢？我们说这是有可能的，如果从一个折射率大的空间折射如一个折射率小的空间，折射角度会增大，且有n / n t > 1，只要入射 θ 角度足够大，1 - cos^2就会接近1，那么此时根号里的数便会小于 0，而这也就意味着，此时没有折射项，光线全部反射

大家不妨在家实验一下，如果你垂直观察玻璃，你很容易看清玻璃外的东西(折射而来)，如果你视线玻璃近乎平行，此时你看到的大部分会是你自己(反射得到)，且视线越与玻璃平行，即与法线夹角越大，你的人像越加清晰，这种现象，就可以用菲涅尔反射来进行解释

简单来说，便是物体的反射率其实与你的观察角度即有关，对于绝缘体来说观察角度与法线夹角越大，反射的程度就越大，如下图

(其中光线极化什么的那两条线不用太去管，只要知道对于绝缘体角度越大反射越多即可)而导体则与绝缘体不同，他的反射率与夹角呈如下关系

想想金属确实反射率一直很大，所以很有光泽。符合上图的规律

那么对于任意一个物体该去怎么计算出它的精确的反射率呢

当然这里考虑了两个极化，然后再求平均，我们不需要知道为什么要这么算，只要知道，物体的反射率和入射角度，和入射空间的折射率，和物体的折射率有关就可以了，然后套公式算就能得出正确的反射率了！那么对于精确的算法来说，可以看到计算量是非常大的，因此就有大佬提出了个简单的算法，近似得到结果，但计算量大大减小

加速光线追踪

相比与光栅化中所使用的的Blinn-Phong模型，光线追踪显著了提升了图像质量，但随之而来的问题是渲染速度过慢。因为在判断光线与场景交点的时候，需要去进行所有三角形面与光线的求交，而且这仅仅是对一个像素而言。
那么总体来说光是进行光线与三角形的求交这样一个计算过程就一共要： 像素数量x三角形面数量x弹射次数这么多次，如下图这样一个场景，一共就有10.7M的三角形面

轴对齐包围盒(Axis-Aligned Bounding Box)

AABB(即轴对齐包围盒)提出的motivation是十分自然的，当有的光线显然不会与一个物体相交的时候，那么自然也没有必要去遍历该物体的所有三角形面，因此利用一个包围盒包住该物体，在与该物体的三角面计算求交之前先判断光线是否与包围盒相交，倘若连包围盒都与光线没有交点的话，那么显然不会与物体的三角面有交点

而所谓AABB也是一种包围盒，也是由三对平面的交集构成，只不过AABB的任意一对平面都与x-axis，y-axis或者z-axis垂直，所以称之为轴对齐包围盒。如下图所示

之所以这么设置的原因是为了方便进行光线与包围盒的求交运算！既然谈到了光线与包围盒的求交，那我们就来看看该过程如何实现

我们以2D AABB为例子，因此只有x，y两对平面，3D情况可类推

首先如上图最左边所示，求出光线与x平面的交点，将先进入的交点(偏小的那个)记为 tmin, 后出去的交点(偏大的那个)记为 tmax，紧接着如中间图所示计算出光线与y平面的两个交点同样记为另外一组tmin, tmax，当然计算的过程中要注意如果任意的 t < 0，那么这代表的是光线反向传播与对应平面的交点。

好了，看看现在我们得到了什么，光线与一对x平面的交点，与一对y平面的交点，究竟哪些点才是真正与盒子的交点呢

只有当光线进入了所有的平面才算是真正进入了盒子中

只要当光线离开了任意平面就算是真正离开了盒子

所以对每对平面的tmin，tmax做如下运算(负的也没有关系)

其中t enter 与 t exit 分别对应了上述两点条件，而对应所举的2D例子，最终求出了两个真正的与包围盒的交点如最右边图所示

但光线一定会与包围盒有交点吗？显然不是，那么什么条件下才会有交点呢？

我们说当t enter < t exit 的时候，光线所在直线一定在盒子中待过一段时间，也必然存在交点，但光线并不是直线，而是射线，除了保证了光线所在的直线在盒子里待过一段时间，还要考虑实际物理意义，具体如下

看看AABB为我们求交所带来的计算效率的提升

均匀空间划分Uniform Spatial Partitions (Grids)

明明已经可以通过事先对每个物体求一个包围盒，在与三角形面求交之前先对包围盒求交，这样不是已经可以达到不错加速效果了吗？

1 整个场景只有一个极其复杂的单一人物模型，那么只对这一个物体做包围盒的话，相当于对效率没有任何提升
2 整个场景充斥着大量的细小模型，如草，花之类的，每个模型可能只有很少的面，如果此时对每个物体求包围盒，得到的包围盒数量会相当之多，对于光线追踪效率来说效率提升有限

基于以上两点考虑，AABB并不应只局限于以物体模型为单位，可以更加精细的考虑到以三角面为单位。另外对于场景的许许多多包围盒来说应该要有一种数据结构将其统领起来。

因此如何更好的划分场景形成不同的AABB，使得划分之后的AABB能够更好的加速光线追踪，这就是接下来要考虑的问题关键！

那么接下来就从最简单的划分方法，均匀空间划分开始介绍。

第一步对所要考虑的场景找一个包围盒

第二步均匀划分这个大包围盒

第三步在每个重叠小包围盒上存储物体模型信息


以上就是均匀空间划分的全部过程了，简单来说就是将空间划分为多个均匀的小的AABB，再根据光线方向找出相交grid(这一步并不需要判断所有方格，正如上文提示，可以用brenham类似的方法来做)，再判断grid中是否存储了模型信息，若有则进一步求交。（这种划分方法假设了找出相交方格要比直接判断与物体求交相对容易，因此划分方格数的多少也是性能的关键，方格太少，没有加速效果，方格太多，判断与方格的求交可能会拖累效率）

因此这种方法最适合的场景就是空间中均匀布满了三角形面，如下图这种场景

如果说场景较为空旷，物体较小且分离得比较开，那么均匀分割的效果就会很差了，因为会有很多无效的方格与光线的求交过程

KD-Tree空间划分

一些常用的空间划分方法

第一种Oct-Tree，也就是八叉树，每次将空间分为8个相等的部分，再递归的对子空间进行划分，因为图中是2维例子，所以只划分了4部分。当划分的子空间足够小或是空间中三角形面的数量很少的时候会停止划分。这种方法的显著缺点是，随着维度的上升划分的空间数量会呈指数级增长。

第二种KD-Tree，也是本小节将要主要介绍的方法，其每次将空间划分为两部分，且划分依次沿着x-axis，y-axis，z-axis，即如图中所示，第一次横着将2维空间分为上下，第二次再竖着将上下两个子空间分别划分为左右部分，依次递归划分，终止条件与八叉树类似，细节问题之后按具体例子详解。

第三种BSP-Tree，其与KD-Tree类似，唯一不同的是划分不再沿着固定一轴，可以任意方向划分，缺点自然是划分的空间没有规则性，求交困难。

接下来从一个例子具体介绍KD-Tree

第一步将空间分为两部分

第二步对左右两个子空间换个方向再分为两部分(这里只画出了有半部分，其实左边也是一样)

如此递归的划分下去，且在划分过程当中遵循这样几点：

• 依次沿着x-axis,y-axis,z-axis划分，使得空间被划分的更加平衡
• 划分的位置由空间中三角面的分布决定，具体细节不展开
• 叶子节点存储对应空间的所有物体或三角面信息，中间节点仅存储指针指向两个子空间
• 当划分空间太小或是子空间内只有少量三角形则停止划分

当KD-Tree建立完成之后，如何进行光线与物体求交判断呢？过程如下：

第一步判断光线是否与最外层的包围盒相交

如果相交进一步判断是否与对应的两个子空间相交

注意！因图中做了简化，最大包围盒的左半边并没继续进行划分(实际上应该要划分的)，所以左半部分对应的1号空间是叶子节点，如果光线与之相交，进一步判断与存储与叶子节点的物体信息求交。左半边判断完之后，接着判断右半部分

同样如果对于有半部分存在相交情况，则对于右半部分的所有子空间，递归的执行这个步骤即可

更加具体的过程不再展开

优点：

利用KD-Tree的结构来构建AABB的好处是倘若光线与哪一部分空间不相交，那么则可以省略该部分空间所有子空间的判断过程，在原始的纯粹的AABB之上更进一步提升了加速效率。

缺点：

缺点是判断包围盒与三角面的是否相交较难，因此划分的过程不是那么想象的简单，其次同一个三角面可能被不同的包围盒同时占有，这两个不同包围盒内的叶节点会同时存储这一个三角形面

Bounding Volume Hierarchy

BVH与前几种方法最显著的区别就是，不再以空间作为划分依据，而是从对象的角度考虑，即三角形面

第一步同样找出场景的整体包围盒作为根节点

第二步找到合适的划分点，将最大包围盒内的三角形面分为两部分，再分别重新就算新的包围盒

注意到这里，包围盒会重叠，但一个三角形面只会被存储在唯一的包围盒内，而这也就解决了KD-Tree的缺点！
接下来与KD-Tree的建立类似，递归的对所有子空间重复该步骤

最终可以建立出如上图的所示的树形结构，同样为了画图方便，只进行了左半部分的划分，右半部分其实同理

BVH加速结构遍历节点的伪代码