（6）
这里，，而且。在六个表达式中，一些参数出
现多次，例如dy1?rz1。因此我们可以通过只计算这些参数一次来减少算法操作的复杂性。
dp2和dp3具有相同的符号时，当dp1，?p1p2p3不与平面内的三角形?q1q2q3有相交。当这三个值都为0时，这两个三角形在统一个平面上。在这种很少出现的特殊情况下，我们采取Mo¨ller [3] 的算法。当三角形?p1p2p3与包含三角形
?q1q2q3的平面相交时，或者反之，我们继续测试两个三角形之间的相交状况，
正如下面的讨论。
3.4 三角与三角的相交
假设P是包含三角形?p1p2p3的平面，Q是包含三角形?q1q2q3的平面；假设L是平面P与Q的相交线。当三角形?p1p2p3与平面Q相交时，三角形?p1p2p3也与直线L相交于一条线段。当且仅当这两条线段相交重叠时这两个三角形相交，如图3[3]所示。
我们需要计算每一条线段的终点来检测是否这两条线段重叠。这里的终点是指三角形两边与包含另外一个三角形平面的相交点。不失普遍性，我们可以假设
dp1和dp2有不同的方向而且边
与平面Q相交。边上的一点v被参数化为
p1?t（p2-p1），t?[0,1]，而且点v到平面Q的距离定义为dp1?t（dp2-dp1）。当这个距离为0时，点v包含于平面Q中；因此向量算得到：
v?p1?dp1（7） （p2-p1）dp1-dp2与平面Q的相交点通过下式计
没有必要精确地计算相交点的位置[3]。这两条线段都包含于直线L；因此即使直线L投影到本来的坐标轴[3]，重叠测试结果也会被保留。在我们的算法中，
（rz0，rz1，rz2）L的方向矢量由z轴方向向量（0,0,1）与普通向量=的叉积所决定。
当rz1的模比rz1的模大时，方向向量暗示x轴与y轴是适当的坐标轴。（-rz1，rz0，0）因此，我们只需要为选定的坐标轴坐标评估公式（7）。
3.5 分类消除
公式（7）包含一个加法，两个减法，一个乘法和一个除法。在现在的计算机系统中，除法比其他简单的计算操作例如加减法或者乘法与比较[8]花费4到8倍的执行时间。因此，我们移除除法，如下所示。当四个终点以这样的方式给出A?Bx0，A?Cx1，D?Ey0并且D?Fy1，重叠测试与使用代替初始四个终点的
Ax0x1y0y1?Bx1y0y1，
Ax0x1y0y1?Cx0y0y1,
Dx0x1y0y1?Ex0y0y1和
Dx0x1y0y1?Fx0y0y1所得到的结果一样。关于此方案的更多详细的信息请参照如
下链接：
http://jgt.akpeters.com/papers/Mo¨ller97
图3.减少至两条线段的重叠测试
接下来的关于操作数的讨论是基于Mo¨ller[3]的修订版算法，正如之前所提到的移除除法的思想。
4.计算次数
在我们开始详细算法的计算次数之前，我们需要理解对于输入的三角形，他们的表示方法在算法所采取的坐标系中的不同之处。假设T1和T2分别是在动作
M1和M2的移动下的两个移动物体O1和O2中分别包含的三角形。此外，我们还
（）假设R1和R2分别是T1和T2的矩形包围体。在传统的碰撞检测系统中，Tii?1,2（）是在物体Oi的坐标系中所表示的。于此相反，我们是在矩形包围体T的ii?1,2局部坐标系中表示三角形Ri的。
为了测试两个三角形之间的相交测试，我们需要将这两个三角形早同一个坐标系统中表示。为了达到这个目的，传统算法在物体O1的坐标系中检测T1和M12（T2）的相交，这里M12=M1-1M2，就M1而言，是M2的相对运动。（注意：移动矩阵M12只为移动物体O1和O2的框架构建一次。）于此对应，我们的算法是在矩形包围体R1的局部坐标系中表示三角形T1和M12（T2）。注意，两个三角形的OBB层次包围树相交测试同样在R1的局部坐标系中完成。因此，在我们的算法中，M12（T2）的转换是测试三角相交的OBB算法的附加产品结果。在其他传统的算法中，我们需要从头计算M12（T2），这远比我们的算法付出的代价大。
在例如Mo¨ller[3],Held[4]以及Guigue和Devillers[5]的方案中，M12（T2）的转换需要27次乘法和27次加法。Tropp al.[6]利用一个顶点和两个向量表示每一个三角形，因此27次乘法与27次加法是必须的。在我们的算法中，转换已经在之前的OBB测试步骤中完成，因此不需要任何附加的操作。
表1的前三行展现了以前算法的计算计算次数，同时最后一行是我们这个算法中所需要的计算次数。三角--平面 Ⅰ反应了第一次三角—平面的相交测试的计算次数，包括M12（T2）的坐标转换。于此相反，三角—平面 Ⅱ反应了第二次三角—平面相交测试的附加计算次数。注意，Tropp et al.[6]仅仅使用一次三角—平面测试。因此就不存在第二次测试以及计算次数。（由于Tropp et al.[6]更加高效，因此在这次对比中我们没有比较Held [4].）最后，三角—三角反应最后的三角—三角相交测试的计算次数。我们算法的操作可以按如下操作进行：
表1 每一种不同算法的计算次数
1. 第一次三角—平面相交测试
·如公式（1）--（3）所示，计算三个方向距离dp1，dp2和dp3，仅仅通过
三次乘法，一次减法和五次加法或者减法。
·为了三角—平面的测试，两次乘法以及两次比较也是必须的，包括特殊情形[3]的检测。
2. 第二次三角—平面相交测试：
·如公式（4）--（6）所示，计算三个方向距离dq1，dq2和dq3，仅仅通过五次加法或者减法以及三次乘法。
·为了三角—平面测试，两次乘法与两次比较也是必须的，包括特殊情形[3]的检测。
3. 最后三角—三角相交测试
·当x轴作为选定的坐标轴，我们需要五次加法或者减法和三次乘法来计算q1x，q2x和q3x，以及为了计算p1x的一次减法。类似的，当y轴作为选定的坐标轴时，我么您需要同样的计算次数。
·没有除法的公式（7）需要12次加法或者减法和16次的乘法计算去检测两条线段是否重叠。有一些情况下，我们需要两次额外的乘法计算去判断是哪两条边与包含另外三角形的平面所相交。
5.实验结果
我们已经在C++环境中试验了我们的三角相交测试算法，平台是内存为2.0G的英特尔酷睿2主板，主频为2.4GHz。为了对比，出了我们算法的测试，我们也测试了其他三种三角—三角相交测试，包括Mo¨ller[3]，Guigue[5]，和Tropp et al.[6]。测试细节包括源代码可以凑够下列链接中查看： ·http://jgt.akpeters.com/papers/Mo¨ller97/. ·http://jgt.akpeters.com/papers/GuigueDevillers03/. ·http://mis.hevra.haifa.ac.il/~ishimshoni/TRI/.
5.1 三种情况介绍
为了展现我们这个算法的效率，我们在三种不同的情形中做了测试，每一种都对应不同输入和位置以及方向属性。
在情形Ⅰ中，我们重复一次Klosowski et al.[9]测试，一个包含404个三角形的模型沿着一条包含2528个框架的路移动，这个框架在包含有229824个三角形的飞机内部。有176137对矩形包围体在进行相交测试。
在情形Ⅱ中，我们采用两个Happy Buddha模型，每一个模型都由15536个三角形组成，而且我们将这两个模型置在229824个相对位置和方向都不相同的配置中。我们是通过Trenkel et al. [10]的球体方法制造的配置，它是碰撞检测算法的基准模型。对于输入的模型，我们用了4种各不相同的相对距离大小，-2%，
