光线追踪1 （Ray Tracing 1 - Whitted-Style Ray Tracing）

课程一共分为四个大的板块，目前已经学习了光栅化和几何，可以实现图1和2的效果，下面要来学习第三个大的板块，光线追踪。

为什么要使用光线追踪？

在学习光栅化时，我们在进行着色的过程中实现光照效果的时候可以发现，我们实现了环境光、漫反射、镜面反射，但是确没有做出阴影。因为光栅化考虑的只是一个局部的着色的过程，只是对那一个像素周围的区域进行着色，并没有考虑到全局进行着色，所以在实现物体表面的光照效果的时候，无法实现对应的阴影。

而光线追踪可以做到：

• 实现软阴影

• 能够很好的解决全局光照的问题
  
  上面三个图都是需要通过光线追踪来进行实现，特别是最后一个间接光照。我们在用光栅化进行着色的时候，对于环境光直接按照一个常数进行处理，但是实际上环境光的出现并不是经过一次反射得到的，比如上图图3，光线经过窗子射入屋内，然后光线撞到地板上进行反射，反射到天花板上在进行一次反射，最后反射到桌上。要实现更好的光照效果，就不能像之前那样单纯的将环境光设置为一个常量，所以需要光线追踪来实现。
  
  上图是绝地求生中的游戏截图，可以看到图片上的纹理非常粗糙，并且没有阴影，光照的效果也非常差。光栅化进行着色速度很快，但是质量确比较低，因为之前在学习光栅化的时候也可以发现，光栅化在很多地方都是进行一种近似的处理，比如插值，采样等过程，所以得到的效果并不好。
  
  而上图就是光线追踪的应用效果了，可以看到实现的效果非常的好。光线追踪得到的效果更加精确，但是，其速度确非常的慢。

• 光栅化更加适合实时(real-time)的渲染，比如在游戏领域，游戏需要较快的速度

• 光线追踪更适合离线（offline）的渲染，比如在制作上图的这种动画电影，都是将程序写好之前花大量的时间运行出来，然后组成电影，比如上面这一张图的渲染，就需要消耗10k个CPU时间。虽然目前也开始在游戏中应用光线追踪技术，如战地5，古墓丽影暗影等、但是开启光线追踪的效果之后帧数下降明显，只有高级游戏显卡才能够较为流畅的游玩。

介绍了这么多，下面开始介绍具体的光线追踪算法

基础光线追踪算法(Basic Ray-Tracing Algorithm)

在介绍算法之前，关于光线有一些说明：

• 我们认为光线是沿着直线传播的（虽然在物理上来看是错的）
• 当几束光线交叉时，并不会产生碰撞（虽然在物理上看是错误的）
• 光线是从光源传播到人眼的，但是在反转的情况下也是相同的，即从人眼传播到光源。正常来说，人眼能够看到物体，是因为有光线进入了人的眼中，但是这个逆过程我们可以认为，是人眼向物体发出了一种“感知光线”，然后才看到了物体，人眼发出“感知光线”的路径和光线的传播路径是相同的，即光路的可逆性。我们就是利用光路的可逆性，从人眼出发，对光线进行追踪。

光线的投射(Ray Casting)

平面是物体的投影平面，后面是实际的物体。光线的投射的过程：假设我们目前在往一个虚拟的世界看，我们是透过投影上面的投影的屏幕向虚拟世界中看，投影的平面被我们分成了由许多个像素组成。

• 我们先从人眼放出“感知光线”，放出的光线透过投影平面上的一个像素投射到虚拟世界的物体上的某一点
• 然后再从这一点向光源发出一条光线，检查该点是否在光照的范围内。

上面这一个过程就是利用光路的可逆性，正常是从光源到物体到人眼，而颠倒这个过程，就能够对光线进行追踪。

下面看一个具体的光线投射的例子

在这之前，有一些事情需要先声明一下：

• 我们的人眼是看作一个针孔摄像机，而不考虑人眼本身的大小
• 光源我们认为是一个点光源
• 人眼发出的光线在碰到场景中的物体时，我们认为光线会发射完美的反射或者折射。
  
• 从人眼发出了一条光线（蓝，eye ray），透过屏幕上的像素（每一个像素都是如此），打到了场景内的球上，和球有一个交点（closest scene intersection point）
• 可以看到在光线的延长线上还能够打到场景中的其他物体，但是我们只要最近的，这也就顺带解决了一个深度测试的问题。在前面光栅化进行深度测试时，需要维护一个深度缓存来记录每个像素所对应的最小深度，通过这种光线追踪的方式，找到最近的焦点就可以不用在记录深度了，怎么做后面再说。

• 之后我们需要考虑这个交点会不会被光源照射，于是从交点和光源连一条线，如果沿着这条光线中间没有任何物体阻挡，那么这个交点就可以被光线照射到 。
• 黑色的线为法线
• 有了法线、入射方向、出射方向就可计算着色，并且写入像素的值。像素变成灰色的了。

通过这种方法能够获得和光栅化近似相同的结果。在这里光线只弹射了一次，后面就介绍光线弹射多次的方法。

Recursive (Whitted-Style) Ray Tracing

Whitted光线追踪的着色效果就如上图。两个球分别实现了折射和反射，阴影的程度也不相同，在这个方法中就计算了光线的多次弹射，能够实现一个很不错的效果。

算法的具体说明如下：

还是之前的场景：

• 人眼射出一个“感知光线”,eye ray，透过一个像素打到了场景内的物体上，在物体表面上有一个交点。
  
• 打到物体的表面之后，光线发生了反射，射出了一条Reflected ray，打到了另一个物体上，并且也有一个交点。
  
• 光线的能量分成了两股，一股进行反射，而另外一股进行了折射，上图中折射进行了两次：
  • 打到球下表面的光线折射进入球内，发出一个Refracted Ray，从内部打到上表面的一个点上
  • 光线在上表面的这个点上再次进行了折射，发出了一个Refracted Ray，打到了长方体表面上的一个点上。
    
• 将这四个点都和光源进行连线，判断这四个点是否在光照范围内。
• 分别计算这4个点的着色
• 将四个点的着色相加，就得到了一开始“感知光线”透过的像素的着色效果。
  
  人眼发出的第一道感知光线我们称为primary ray，后面折射和反射的光线都称为secondary rays，四个点和光源的连线称为shadow rays。按照上面的过程，最终就能够得到下面的效果：
  

求光线与面的交点(Ray - Surface Intersection )

在了解了上面Whitted风格的光线追踪之后，要实现这个算法我们还需要知道如何求光线和面的交点。

定义一条光线

从上个图可以看出，要定义一条光线，只需要知道光线的出发点（点光源）和光线射出的方向向量即可，所以光线的代数定义如下：

上面的表示的是，在时间t时，光线的所到达的位置。t = 0时，光线还未出发，此时的光线是一个点，t = 1时，光线从原点出发，经过单位时间到达了o + d的位置，o和o + d两个点的连线，就是此时的光线。

光线和球面的交点（Ray Intersection with Sphere）

第一个公式为光线的公式，第二个公式则是球面的隐式表示公式。在数学中求一条线和一个面的交点时，只要令两式想等，求得的解就是线和面的交点。所以光线和球面的交点的求法也是将两个等式相等求解，经过化简，就可以得到下面的式子：

求出t，就可以得到交点，其中o , c , R 已知。然后再将该式子展开，使用求根公式，即可得到解。

二次方程的根有三种情况，分别是0、1、2个根，不同的根的数量对应的交点情况如下:

光线和隐式曲面求交点（Ray Intersection With Implicit Surface）

前面在介绍隐式曲面时已经说过，隐式曲面是使用一个等式来表示

求光线和隐式表示的曲面的交点的方法和上面类似，直接代入求解即可。

比如下面这些曲面求交点，直接带入即可。

求光线和三角形网格的交点（Ray Intersection With Triangle Mesh）

隐式表达的曲面通过上面的方法就可以求解，那么显示表达曲面该怎么办？就是通过求光线和三角形的交点。

通过求光线和三角形的交点，能够判断这个交点处是否在阴影内，是否可见、等等。并且还能够判断给定的一个点是在物体内还是在物体外面。比如有一个物体，有一个点，从这个点发出一条光线，光线是一条射线，如果点在物体内，那么光线和物体的交点一定是奇数个，如果在外，则是偶数个。

说那么多，那么该如何计算光线和三角形的交点？

• 最简单的一个思想，让每一个三角形都和光线求交点
• 问题：但这种做法会导致速度非常慢，于是就需要对其进行加速（后面再说）。

计算光线和三角形的交点

我们都知道三角形是处在一个平面上的，于是要求光线和三角形是否有交点，则可以按照如下的方法：

• 先求出光线和三角形所在平面的交点
• 判断这个交点是否在三角形内部

平面等式（Plane Equation）

要确定一个平面，需要该平面的法向量和平面上的任意一点。

• 一个法向量能够确定一系列平行的平面
• 再加上一个点，就可以定义到一个准确的平面

平面的等式如下：

p代表该平面上的任意一点，p‘代表平面上已知的一点，N代表法向量。平面方程的一般表示形式为:

计算光线和平面的交点

有了光线和平面的等式，直接将光线等式带入求解即可。

加速光线和平面求交点的计算（Accelerating Ray - Surface Intersection）

前面让每个三角形都和每一个光线进行交点的计算，那么复杂度 = 像素的个数 * 三角形网格的个数（在前面介绍光线追踪时，我们提到过，人眼从发出的光线会穿过每一个像素）。这种方法虽然有效，但是速度太慢，所以要对其进行改进，减少计算量，加快运行速度。

我们使用的方法是包围体（Bounding Volumes）。

包围体（Bounding Volumes）

前面在光栅化的部分，我们学过一个包围盒，这里的包围体的思想与前面类似。

包围体的思想是：

• 使用一个立体的盒子，将物体完整的包围起来。
• 当光线入射的时候，先判断光线是否和包围体有交点，如果和包围体没有交点，那么光线和包围体内部的物体一定没有交点，就可以不用再对这个内部物体上的每个三角形求交点；如果光线和包围体有交点，则下一步：
• 求光线和内部物体的每一个三角形的交点。包围体的效果如下：
  

轴对齐包围盒（Axis-Aligned Bounding Box, 缩写AABB）

我们一般使用轴对齐包围盒，轴对齐包围盒就是由三对相互垂直的平面所围成的一个立体空间。，如下图所示，只展示出了其中一对盒子。

求光线和轴对齐包围盒的交点（Ray Intersection with Axis-Aligned Box）

以2D的情况为例，3D的情况类似。在上面提到过，AABB是由三对相互垂直的平面所围成的，那么在2D的情况下，AABB就是由两对相互垂直的面所围成。

上图表示求光线和包围盒交点的过程：

• 求出光线在x = x0 和 x = x1上的交点，分别用t(min)和t(max)表示，代表光线最早和最晚通过在x方向上的对面，如图1
• 求出光线在y = y0 和 y = y1上的交点，分别用t(min)和t(max)表示，代表光线最早和最晚通过在x方向上的对面，如图2
• 求上面求出的两个光线进入时间和离开时间的交集，如图3

如何判断光线是否通过包围盒

核心思想：

• 当光线和每一对平面都有交点时，光线才会进入包围盒。

• 当光线离开任一对平面时，光线也就离开了包围盒。

• 对于每一对平面，我们都要计算出t(min)和t(max)，分别代表了光线的进入和离开的时间，t可以是负数。

• 对于每一个3D的包围盒，我们要对上一步算出的时间区间进行求交集。
  

• 如果t(enter) < t(exit)时，我们就知道，光线曾有一段时间是在盒子内部，也就是说光线和包围盒有交点。

有一些特殊情况：

• 如果t(exit) < 0，则代表物体在点光源的背后
• 如果t(exit) >= 0 而 t(enter) < 0，则代表这个光源就在物体的内部

总而言之，如果光线和包围盒有交点，则应该满足:

• t(enter) < t(exit) && t(exit) > = 0

为什么使用轴对齐包围盒？

使用轴对齐包围盒求交点非常简单。只要当光线的某一分量等于某一个特定值的时候，就说明光线和这个轴对齐的平面有交点了。