图形学——光线追踪
之前我们重视的是镜面反射和漫反射的效果，对于折射却提到很少。这意味着只能显示非透明的东西。想要显示比如透明的水晶球，还有更复杂的，比如镜面中的场景，就需要光线追踪。
Whitted模型是第一个光线追踪模型。Whitted是图形学大佬，只发表了19篇文章，就被评为了工程院院士。所以大佬的作品在质不在量。光线追踪算法可以实现其他算法很难达到的视觉效果，被广泛使用。
说光线追踪，首先要知道，人之所以能看到东西，是光线经过一系列反射折射等等最终摄入我们的眼睛。光线追踪的思路就是顺着这个原理倒回去。首先，计算机有个显示缓存区，是由空间中的像素组成的，人眼透过这些像素看到场景中的物品。对于每个像素\(P\)计算其颜色值。步骤如下：
- 计算视点连接像素\(P\)中心的光线（Ray）延长后所碰到的第一个物品的交点
- 使用局部光照模型计算交点处的颜色值，到目前我们还只能看到投射的效果
- 沿交点处的反射和折射方向对光线进行追踪，比如反射，折射方向有别的物品，对这个物品继续利用局部光照模型等，则进行加权叠加，这样就能实现更逼真的反射和折射效果
通过光线追踪，可以很容易地表现出来阴影，反射，折射等引人入胜的视觉效果。由于一个递归的过程，光线追踪适用于更复杂的物体表示方法。
简单原理图：
效果图：
光线求交（Ray Intersection）
光线的表示
光线由射线表示：
- \(P(t) = R_0+t\cdot R_d\)
- \(R_0 = (x_0,y_0,z_0)\)为光线的源点;\(R_d=(x_d,y_d,z_d)\)表示光线的朝向，一般来说为单位向量
- \(t\)表示光线到达的位置，在光线的正方向上\(t\ge 0\)
光线与平面求交
平面的表示
- 显示表示：\(n_0=(A,B,C),P_0=(x_0,y_0,z_0)\)分别表示法向量和平面上一点
- 隐示表示：\(\begin{aligned}H(P) &= Ax+By+Cz+D=0\\=&nP+D=0\end{aligned}\)
点到平面的距离：
- 当\(n\)是单位法向量时，\(P\)到平面\(H\)的距离为\(H(P)\)
根据平面和光线的方程得到方程组，求解即可： \[ P(t) = R_0+t\cdot R_d\\ n\cdot P(t) + D = 0 \] 解得：\(t = -(D+n\cdot R_0)/(n\cdot R_d)\)，最后验算\(t>0\)。
光线与三角形求交
首先求与三角形平面交点，再检查交点是否在三角形内。不过对于三角形中的点有多种表示方法，因此我们可以使用更简单的操作。
- 重心坐标：
三角形\(P_0P_1P_2\)内部一点\(P\)可以表示为： \[
P = \alpha P_0 + \beta P_1 + \gamma P_2
\] 这里的\((\alpha,\beta,\gamma)\)被称为重心坐标。满足\(0\leq\alpha,\beta,\gamma \leq
1,\alpha+\beta+\gamma=1\)。
重心坐标有很多应用，纹理映射，法向插值，颜色插值等等。
通过将重心坐标与射线方程联立： \[ P = (1 - \beta - \gamma)P_0+\beta P_1 + \gamma P_2 = R_0+tR_d \] 也就是： \[ \begin{pmatrix}R_d &P_0-P_1 & P_0-P_2 \end{pmatrix}\begin{pmatrix} t\\ \beta\\ \gamma \end{pmatrix} = P_0 - R_0 \] 最后需要检查\(t,\alpha,\beta,\gamma\)的有效性。
光线与多边形求交
与多边形求交也非常重要。思路为求与多边形平面交点，再检查交点是否在多边形内。为了判断第二个，首先我们需要将平面和交点投影到XY，XZ或者YZ面，然后判断在这个平面上的关系。这时候需要使用交点检测算法，属于计算几何的范畴。交点检测算法的原理如下：
很简单，如果一个点是多边形的内点，那么从它射出去的一条射线，与多边形边的交点是奇数个。如果是外点，则交点为0或者为偶数个。但是这检测的过程中会有一些有歧义的地方，比如射线和边重叠了，或者射线和多边形顶点重叠了，需要进行额外的判断。
这个算法的一个改进是根据交点为原点来建立坐标系，而x的正半轴就是射出去的线的方向。这样很多事情会方便很多，但是本质上没有太大的区别。
另外一个算法是面积法，通过计算该点与各个边组成的三角形面积之和，如果等于多边形的面积，则在内部。但是这个还需要进行多边形的面积计算。
最后介绍一个叫弧长法。弧长法是最快的算法，不过是一步步简化的，最开始也需要大量计算。看下图：
我们会判断该点与各个边的夹角，这个夹角是按照一定方向过去的，如果夹角之和为\(2\pi\)，则为内点，如果最后和为0，则为外点。如果代数和为\(\pi\)，则点在多边形上。
仔细一看，这个方法也不算那么简单，因为计算夹角和计算面积可能区别不大。但是弧长法可以继续改进。我们将该点作为坐标系原点，各个象限内点的符号分别为：\((+,+),(-,+),(-,-),(+,-)\)。如果某个顶点\(P_i\)的某个坐标为0，则符号为+，如果该顶点为\((0,0)\)，则说明该顶点为被测点，则弧长变化为下表：
| \((x_i,y_i)\) | \((x_{i+1},y_{i+1})\) | 弧长变化 | 象限变化 |
|---|---|---|---|
| (+,+) | (+,+) | 0 | I->II |
| (+,+) | (-,+) | \(\pi/2\) | I->II |
| (+,+) | (-,-) | \(\pi\) | I->III |
| … | … | … | … |
下面的变化依照上面的规律。这是计算各个之间弧长（并不是真正的角度）的方法，另外一种方法通过计算: \[ f = y_{i+1}x_i - x_{i+1}y_i \] 如果\(f=0\)，则边穿过坐标原点，如果\(f>0\)，弧长代数和增加\(\pi\)，否则弧长代数和减少\(\pi\)。最后，得到弧长和为\(2\pi\)，则为内点。
弧长法好的地方在与它除了速度外还有鲁棒性。因为计算不能精确为0或者\(2\pi\)，只要近似，我们就能得到结果。
光线与球面交点
之前的交点计算都是比较简单的，这次说说与球面的交点。球的隐式方程为： \[ \Vert P(t) - P_c \Vert = r \] 最容易想到的方法，是根据方程组来解。联立球的坐标和射线坐标，我们可以得到一个一元二次方程组，从而得到两个解。这个方法的缺点是，需要解方程。而且，我们往往仅需要一个交点即可。下面介绍另一种几何方法。看下图：
- 计算视点指向球心的向量为\(l: l = P_c - R_0\)。
- 判断视点是否位于球体内部，这个也非常简单，只要判断\(l^2,r^2\)的大小即可。如果视点位于球面上，需要考虑退化情况。
- 计算球心到光线所在直线的投影点（垂足）： \(t_p = l\cdot R_d\)，\(t_p\)也就是在\(R_d\)方向上的距离。如果\(t_p<0\)，则光线与球面不相交。因为我们没法看到后面。
- 计算\(d\)，\(d\)很好算，如果\(d^2 > r^2\)，不相交。
- 计算\(t’\)，为投影点到光线与球面的交点的距离，它也可以根据圆内的简单直角三角形利用勾股定理得到，得到\(t’\)后：
- 如果光源在球体外部，\(t = t_p - t’\)
- 如果光源在球体内部，\(t = t_p + t’\)
由此就计算出来了\(t\)，从而得到交点。虽然上面的过程看着也比较复杂，但是只是简单的向量乘积，因此速度更快，而且鲁棒性更高。而解方程由于有较多除法，可能会遇到奇异解。
光线与长方体交点
求光线与长方体的交点是非常有必要的。因为在做光线追踪的时候，对于一个复杂的模型的所有三角面片进行求交点是非常麻烦的，最后求出来结果可能是根本没有交点。因此会需要一个预处理，来排除一定没有交点的情况。这时候常用的方法是用长方体做对物体做包围盒。如果光线与包围盒不相交，那么和模型也一定不相交。这个思想在图形学中是非常重要而且普遍应用的。
对于长方体的求交最直接的想法是向多边形求交那样，对于长方体的6个面进行判断，但是由于长方体的形状特殊，实际上有更简便的方法。首先，长方形有6个面，每两个面是互相平行的，平面方程：\(Ax+By+Cz+d = 0\)，也就是只有\(d\)有区别。这两个面一个是近平面，一个是远平面。我们求对每对平面（不是长方体的面，是长方体面所在平面）求\(t_{max},t_{min}\),最后得到： \[ t^{(1)}_{max},t^{(1)}_{min}, t^{(2)}_{max},t^{(2)}_{min},t^{(3)}_{max},t^{(3)}_{min}. \] 接着，我们对所有的最大值求最小值，对所有的最小值求最大值。得到： \[ t_{max} = \min\{t^{(1)}_{max},t^{(2)}_{max},t^{(3)}_{max} \}\\ t_{min} = \max\{t^{(1)}_{min},t^{(2)}_{min},t^{(3)}_{min} \} \] 如果\(t_{max} \ge t_{min}\)，则这两个就是光线与长方体的交点。对于这个算法的原理解释，我们可以在二维的情况下画图理解，这个思路是非常巧妙的，如下：
实际上，这个不光是长方体，只要有一组组平行面组成的多面体（凸的）都可以。
计算阴影
在交点向着光源发出一条射线，如果有遮挡，那说明该点位于阴影区域。在计算阴影区域时，我们只需关注是否与物体相交，而不用关注哪个是最近交点。
思考
光线追踪算法从提出到现在，依然在广泛使用。而近些年在光线追踪方面的改进，也是主要用于加速求交等等。思考光线追踪的过程，从人眼出发，反向去找交点从而得到各个效果，是非常聪明的做法。
首先，我们初中就学过，在宏观世界里，光逆向之后可以回到原点。因此这个方法是符合常识的。第二个，如果我们从光源出发，那么一个光源应该射出多少条射线？光源理论上发出来无数条光线，而在计算机中，我们不能做到无数，只能均匀发出一系列光线，而这些光线最后能弹射到人眼中的只占了一小部分，既浪费了计算量，也无法保证每个像素都能被光线弹射到，这样使得效果也差，算是费力不讨好，如下图：
而从视点出发，对每个像素进行反向追踪，计算量不算大，又能得到很好的效果。
要知道光线追踪算法是一个递归算法，那么这个递归如何停止。因为很有可能这个递归会一直走下去。这种情况下有两种做法，一是达到一定的层数后，自动结束递归，第二个是通过衰减系数。前面我们也知道，不管折射还是反射都是会损耗光的能量，如果这个光递归了很久衰减系数低到一定的阈值，我们就将其忽略，结束递归。这二者都能取到不错的效果。因为即使递归少了一辆层，看上去依然能得到很惊艳的光线追踪效果。
