论文：A Fast Triangle-Triangle Intersection Test

作者：Tomas Moller
时间：2012.04.06

1.简介

计算两个三角形是否相交的算法及优化。（碰撞检测算法）

2.介绍

碰撞检测算法：

OBBTree（文章“OBBTree: A Hierarchical Structure for Rapid Interference Detection” Cottschalk 96）
sphere hierarchies (文章“Approximat ing Polyhedra with Spheres for Time-Critical Collision Detection” Hubbard 96)
BV-tress(文章“"Efficient Collision Detection Using Bounding Volume Hierarchies of k-DOPs” Klosowski 97)

3.相测试方法

• 两个三角形表示：$T_1$T1​,$T_2$T2​;
• 三角形点：$T_1$T1​：$V_0^1$V01​，$V_1^1$V11​，$V_2^1$V21​； $T_2$T2​：$V_0^2$V02​，$V_1^2$V12​，$V_2^2$V22​
• 三角形所在的面：$\pi_1$π1​,$\pi_2$π2​

第一步：平面$\pi_2$π2​方程： $N_2·X + d_2 = 0$N2​⋅X+d2​=0, $X$X为平面任意一点
其中：$N_2 = (V_1^2-V_0^2)×（V_2^2 -V_0^2);$N2​=(V12​−V02​)×（V22​−V02​); $d_2=-N_2·V_0^2;$d2​=−N2​⋅V02​;
第二步：表示$T_1$T1​上点到$\pi_2$π2​的距离
$d_{v_i^1}=N_2·V_i^1+d_2,i=0,1,2;$dvi1​​=N2​⋅Vi1​+d2​,i=0,1,2;
第三步：判断
①当$d_{v_i^1} ≠ 0，i=0,1,2$dvi1​​​=0，i=0,1,2成立，且符号相同，则$T_1$T1​位于$\pi_2$π2​一侧，则不会相交。同理$T_2$T2​,$\pi_1$π1​也可以排除相交情况。这两个拒绝检测可以较早的排除掉许多三角形对。
②当$d_{v_i^1} = 0，i=0,1,2$dvi1​​=0，i=0,1,2成立，两个三角形共平面，稍后讨论。
③排除上述两种情况，$\pi_1$π1​，$\pi_2$π2​相交与一条直线$L=O+tD$L=O+tD,其中$D=N_1×N_2,为直线方向;$D=N1​×N2​,为直线方向;$O$O是线上一点。且可以确定$T_1$T1​,$T_2$T2​均与直线相交，当相交区间有重叠时，可判断两三角形相交。两种情况如图1所示。

针对这种情况将需要计算出$T_1$T1​在$L$L上的相交标量区间，我们可以假设$V_0^1$V01​，$V_2^1$V21​在同侧，$V_1^1$V11​在$\pi_2$π2​另一侧（其他情况①②已排除）。
三角形顶点到直线的投影：$p_{v_i^1} =D·（V_i^1-O）;$pvi1​​=D⋅（Vi1​−O）;
几何关系如图2所示。

然后我们需要计算线段参数$t_1$t1​，有$B=\overline{V_0^1V_1^1}∩L = O+t_1D$B=V01​V11​​∩L=O+t1​D
用$K_i^1$Ki1​表示$V_i^1$Vi1​在$\pi_2$π2​上的投影，我们可以找到相似三角形$△V_0^1BK_0^1$△V01​BK01​和$△V_1^1BK_1^1$△V11​BK11​。所以$t_1=p_{v_0^1}+(p_{v_1^1}-p_{v_0^1)}\frac{d_{v_0^1}}{d_{v_0^1}-d_{v_1^1}};$t1​=pv01​​+(pv11​​−pv01​)​dv01​​−dv11​​dv01​​​;
同理计算$t_2$t2​,同理$T_2$T2​。
如果两个区间重叠，则三角形相交。
回头看②中同面情况，将三角形投影在两三角形面积最大的轴平面，问题转换为二维的三角形重叠测试。首先测试$T_1$T1​中所有的边是否与$T_2$T2​中所有边相交，有相交则两三角形相交成立。否则需要排除包含情况。采用点在三角形中测试（文章"Point in Polygon Strategies"Haines 94）,$T_1$T1​在$T_2$T2​中以及$T_2$T2​在$T_1$T1​中。

4.优化

①由于整体平移不改变相交测试结果，所以计算$p_{v_i^1}$pvi1​​可以简化
$p_{v_i^1} =D·V_i^1，i=0,1,2;$pvi1​​=D⋅Vi1​，i=0,1,2; $O$O可以不用计算。
②我们可以将直线$L$L投影到最一致的轴上（与直线$L$L夹角最小的轴，即$max(|D_x|,|D_y|,|D_z|)$max(∣Dx​∣,∣Dy​∣,∣Dz​∣)对应的轴），$p_{v_i^1}$pvi1​​计算可以进一步简化
$p_{v_i^1}= \begin{cases}V_{ix}^1,if |D_x| = max(|D_x|,|D_y|,|D_z|) \\V_{iy}^1,if |D_y| = max(|D_x|,|D_y|,|D_z|) \\V_{iz}^1,if |D_z| = max(|D_x|,|D_y|,|D_z|) \end{cases},i=0,1,2;$pvi1​​=⎩⎪⎨⎪⎧​Vix1​,if∣Dx​∣=max(∣Dx​∣,∣Dy​∣,∣Dz​∣)Viy1​,if∣Dy​∣=max(∣Dx​∣,∣Dy​∣,∣Dz​∣)Viz1​,if∣Dz​∣=max(∣Dx​∣,∣Dy​∣,∣Dz​∣)​,i=0,1,2;
其中$V_{0x}^1$V0x1​表示$V_0^1$V01​的$x$x方向分量，其它类似。

5.实现和性能

步骤：

①计算$T_2$T2​方程；
②若$T_1$T1​所有点在同侧，返回不相交；
③计算$T_1$T1​方程；
④若$T_2$T2​所有点在同侧，返回不相交；
⑤计算相交直线，并投影到最大轴
⑥计算每个三角形相交区间
⑦区间相交
同面情况很少见，可以放到后面处理。
注意事项：
①点在面上的判断，需要引入固定小值EPSILON($\epsilon$ϵ)，当距离小于该值是认为，点在面上。
②根据情况判断是否需要考虑三角形退化为直线和点的情况，若需要，不得不优先考虑退化情况。
性能：
Oxygen VR-platform中内部碰撞检测包使用了这个方法。