一种改进的快速求射线与三角形交点的算法

张炜喆

（同济大学电子与信息工程学院，上海，201804）

0 引言

随着图形学技术的突破和发展，光线追踪算法正在逐步取代光栅化算法，成为实时渲染领域新的主流技术。不论是光线追踪还是光栅化，它们都离不开三角形这一最基础的几何模型。因此，能否快速准确的计算出光线和三角形的交点决定了整个渲染过程的效率。

解决该问题的一个十分朴素的思路是首先联立射线的参数方程和平面的参数方程，求解出光线与三角形所在平面的交点，然后通过三次叉积的计算来判断该交点是否在三角形内部。但是由于要经过两个复杂的步骤以及多次向量计算，该算法在如今并没有被实际项目采用。Möller和Trumbore后来提出了一种改进的被简称为MT的算法[1]，也是现在最为通行的算法，它将三角形和射线的交点用三角形的重心坐标的形式表示，经过一系列移项，使其转化为形如Ax=c的形式，其中A是一个可逆矩阵，x和c都是列向量。在此基础上，MT算法利用克莱姆法则对该等式求解，从而可以得到三角形与射线交点的用重心坐标表示的数学形式。该算法极大地降低了计算射线-三角形交点的时间复杂度。

目前存在的更快的求解射线与三角形交点的方法大多从利用各式各样的数据结构来优化的角度出发，比如基于空间划分，将图像空间递归的拆分为不同层次的树结构[2]，或是通过层次包围，动态的计算包围了三角边顶点的最小矩形包围盒[3]等。这些算法在提高计算效率的同时也大幅增加了内存空间的开销。

本文从纯算法理论的角度出发，旨在减少单位时间内基本运算的次数。首先通过一次坐标变换，将射线和三角形从全局坐标系转换到重心坐标系中，再求解变化后的坐标的交点。该算法所用到的计算步骤比MT算法更少，因此可以做到每次求解三角形与射线交点的速度都比MT算法更快。此外，该算法构造变换的方式能够确保其矩阵形式所使用的许多系数为此前被预计算出来的值，不需要做多余和额外的存储，因此能够使得预处理的内存开销最小化。

相较于其他算法，该算法具有良好的拓展性和应用价值。对于已经使用了MT算法实现的光线追踪器或是光栅化渲染项目，不需要大幅调整自身的代码结构，而只需要将其中用MT算法求解光线与三角形交点的模块替换为本文提供的算法就可以在得到相同图像的同时大幅提高图片渲染以及图像生成的效率。对于使用数据结构来加速计算光线与三角形交点的案例，该算法的思路依然可以部分应用于其中，从而加速整个计算的过程。

1 数学定义

2 算法步骤

在三角形初始化的过程中，首先计算出定义1.3中提到的从全局坐标系到重心坐标系的转换矩阵T，并将该矩阵作为三角形信息的一部分储存下来。由于矩阵计算的过程会把该坐标转换为齐次坐标系中进行计算，根据齐次坐标系的性质，易知该矩阵第四行的值不参与相关涉及到变量的运算，且它的值一定为( )0,0,0,1，故可以只储存该矩阵前三行的内容，从而节省了大量的内存空间。

当我们计算出了转换矩阵T的值，则可以按照以下四个步骤得到坐标的重心表示形式：

3 时间复杂度分析

根据MT算法的描述[1]，它至少需要进行三次向量混合积的计算，而每次向量混合积的计算需要12次乘法运算和5次加法运算（此处暂时不考虑向量中有0的情况）。为了方便统计和比较效率，我们定义1次乘法运算或1次加法运算为1次元运算。忽略MT算法中涉及到的标量除法等耗时较少的计算，则MT算法至少需要进行34次元运算。

对于本文提出的方法，按照算法步骤中的4个步骤依次统计运算次数：

(a)该步骤是一个4×4的矩阵左乘一个4× 1的列向量，由于该矩阵的第四行为(0 ,0,0,1)，列向量的第四行为1（齐次坐标的性质），展开化简后可以得出需要的元计算为18次。

(b)该步骤为一个标量除以一个标量，由于除法可以看作是乘法的逆运算，故需要元计算1次。

(c)该步骤需要2次标量乘法和2次加法，合计元计算2次。

(d)该步骤为比较的过程，不计入运算的步骤中。

将以上四个步骤需要的元计算次数进行加总，得出本文提出的算法需要的元计算次数至少为23次，远小于MT算法需要的34次。

4 空间复杂度分析

由于MT算法不需要储存额外的变量信息，因此不存在超出所有变量自身以外的内存空间开销。

本文提出的算法所需的额外内存占用主要在于预处理时使用的转换矩阵T。由于不需要考虑T矩阵第四行的值，所以单个三角形需要额外储存的内存为12个自由变量。同时，由于该矩阵只与三角形自身的性质相关，而与射线的参数无关，因此该部分内存可以在计算完所有需要和同一三角形相交的射线后释放，总体上来说不会大幅增加内存的消耗。

5 实际运行结果

本文采取了两种方式来比较该算法和通用的MT算法的性能：一是分别独立实现两种算法，用不同三角形数量的测试集各自进行一轮测试；二是将该算法分别嵌入一个完整的光栅化项目和一个完整的光线追踪器中，比较在实际项目中该算法和MT算法的效率。

实验表明，在这两种情况下，本文提出的算法都比MT算法更快。

■5.1 独立计时实验

此部分比较了本文提出算法的运行时间和原始版本的MT算法的运行时间，同时也比较了MT算法在sse4框架[4]下的一个改编版本：该框架经过高度的调整，可以在现代CPU上快速的执行MT算法。根据文献[5]设计的测试程序，该程序能够生成指定数量以及指定射线-三角形命中率（射线-三角形命中率指的是有射线能够与之相交的三角形占总三角形个数的比例）的射线和三角形的集合，其中每条射线都与至少一个三角形相交。该程序能够进行本文提出算法的12-自由元版本、9-自由元版本、原始的MT算法以及在sse4框架下的改编MT算法的比较。

在未经特殊申明的情况下，本文涉及的所有实验皆在以下运行环境运行：CPU 2.8GHz Core i7-7700HQ，内存16 GB of RAM，硬盘512 GB of SSD，操作系统Windows 10 2004 64位，IDE编译优化设置为-O3级别的Visual Studio 2019。

本文对上述涉及到的两种算法进行了轻微的修改，但是仍然尽可能地使其接近原始算法的意图，以方便能用C++的形式进行复现。由于当前sse4框架下的MT算法还使用了SIMD功能以提升其并行性，本文在实现该算法时删除了这一特性以保障一个平等的实验测试环境。值得一提的是，SIMD提供的并行特性并不与本文提出的算法排斥，因此将该部分功能添加到本文提出的算法中将是未来的研究方向之一。

表1展现了本次实验的结果。表格中展现的百分数代表该算法在当前实验环境下运行所需的时间和MT算法在当前实验环境下运行所需时间的比例。可以看到，不论三角形数和射线-三角形命中率如何变化，本文提出算法的12-自由元版本都稳定的快于9-自由元的版本，而12-自由元的版本在所有实验条件下运行时间均在MT算法的30%～50%之间。当射线-三角形命中率仅为0.1时，12-自由元版本依然在运行效率上略高于sse4框架下的MT算法，随着射线-三角形命中率的增高，12-自由元的版本和sse4框架下的MT算法的效率差距逐渐拉大，在射线-三角形命中率高达0.9时，12-自由元的版本运行时间约为sse4框架下的MT算法的50%左右。当射线-三角形命中率为最低的0.1时，9-自由元的版本比sse4框架下的MT算法效率略低，但是随着射线-三角形命中率增大到0.5和0.9，其运行速度反超sse4框架下的MT算法，处在12-自由元的版本和sse4框架下的MT算法中间。

表1 不同数据集下三种算法和MT算法运行效率对比

值得注意的是，对于每个三角形，sse4框架下的MT算法需要预先计算一个顶点、两条边和三角形的法线，总共需要48个字节的额外内存开销（假设所有数据为单精度浮点数），而9-自由元的版本仅需额外36个字节的内存空间（假设所有数据为单精度浮点数）。

■5.2 在真实场景下的应用

为了测试本文提出的算法在真实复杂场景下的正确性和有效性，该部分选取了两个显示效果明显的渲染项目，其中一个项目由Blinn-Phong光照模型[6]在光栅化下实现，另一个项目则使用了一个初阶版本的路径追踪器完成。

本次测试所做的工作仅仅为将这两个项目中用MT算法求解射线-三角形交点的函数修改为本文提出的算法，其余部分未做任何改动。最终得到的结果如表2所示。可以看到，在真实场景下本文提出的算法在效率上的提升不如上一个实验显著。原因在于在真实的渲染项目中，除了计算射线-三角形的交点以外，还有其他的函数消耗大量时间，比如模型的加载，计算光的反射，图层的处理等。这两个场景最终渲染生成的图像如图1和图2所示。

表2 两个场景下本文提出的算法和MT算法运行效率对比

图1 基于Blinn—Phong光照模型和光栅化渲染

图2 基于路径追踪器渲染

6 结论

本文提出并测试了一种新型的计算射线-三角形交点的方法，它以对每个三角形进行预处理和储存少量的额外信息为代价，能够快速的求解出射线与三角形的交点。储存的额外信息并不会妨碍渲染工作的进行，即使是在一些大型的渲染项目中，它依然可以稳定并准确的运行。

该算法在效率上远远优于通用的MT算法，并在一定条件下优于MT算法的改进版本。在完整的渲染工程中，本文提出的方法在获得相同视觉效果的同时取得了比MT算法更快的结果。进一步的工作可以考虑将本文提出的算法和前述所涉及到的数据结构相结合，以期能够得到时间复杂度更小的综合实现方案。

文献[5]指出，世界上并不存在一种最快的求解射线与三角形交点的方法，不同的算法在不同的运行条件和数据集下各有优劣。随着图形学和实时渲染技术的进一步发展，对于在短时间获取稳定准确图像的需求不会减少。本文提出的算法正是在这样的背景下进行的一点思考，如果能够该思路融入到一些已经实现的光栅化项目和路径追踪器项目中，将很有希望能够获取更大的成果。