空间两三角形的相交问题

于海燕， 何援军

（1. 东华大学机械工程学院，上海 201620；2. 上海交通大学计算机系，上海 200240）

空间两三角形的相交问题

于海燕1， 何援军2

（1. 东华大学机械工程学院，上海 201620；2. 上海交通大学计算机系，上海 200240）

重点考虑几何奇异问题，同时兼顾算法的效率。运用“分而治之”的方法从一维解得到二维解，进而得到三维解，将空间问题变为平面问题、线性问题。基于几何代数化依赖于坐标系，引入“计算坐标系”，简化了几何的表述与关系的类型，使“几何奇异”状态最后归结为平面上线段被三角形裁剪时的共点、共线问题，简单而明晰，从而可从理论上保证算法的鲁棒性，以平面处理的形式给出了两个空间三角形求交的完整解决方案。测试证明，几何关系、几何奇异类型与计算的简化足以弥补因“变换”而增加的额外开销。算法的速度也能达到实用要求——在笔记本电脑上也能达到每秒100万对三角形的相交计算。

几何计算；三角形相交；降维；几何奇异；计算坐标系

计算机构造的虚拟对象往往由成千上万个简单几何形状（如四边形面片，特别是三角形面片）组成。因此，碰撞检测算法归根结底是对这类简单几何形状的关系测试。高效的三角形与三角形测试对于提高碰撞检测算法效率，增强虚拟场景的展现起至关重要的作用。

近年国内外对三角形与三角形求交测试的研究较为活跃，但通常将主要工作集中在如何加速算法的速度上。

Christer Ericson对这种只偏重速度、忽视稳定性的研究方法表示担心：“They do reduce the number of floating-point operations compared to previous methods, but I don’t care.（这些算法与以前的算法相比是减少了浮点运算，但是我不感兴趣。）”他指出： “Frequently they test the primitives in some large number of random configurations and report the average time it took to do a test.（大都采用一些大规模随机产生的三角形间的相交计算的测试手段）”，“This kind of testing is very unlikely to hit the cases where the tests fail due to robustness issues.（这种测试很难检测到影响算法鲁棒性的状况）”[1]。

实际上，两个三角形边的平行、共面、相交于某一个点、某一条边的几何奇异现象在“随机”产生的测试例子中常常不会被碰到，因此，检测出现遗漏。而在应用中，对一个几何奇异的处理错误往往导致系统的崩溃。

本文重点考虑两个空间三角形位置的几何奇异情况，将几何奇异的现象归结为平面上少数几种简单情况，从理论上解决几何奇异对稳定性的影响。在此基础上追求算法的效率，达到应用要求。

1 研究现状

如图1所示，空间两三角形的关系通常为4种情况：

1） 相交，如图1(a)所示，公共部分为一直线段；此时，两三角形所在平面相交。

2） 相叠，公共部分为一面区域，如图1(b)所示，此时两三角形共面；

3） 相离，无公共部分，如图1(c)所示，不论两个三角形所在平面是相交、平行或重叠，两三角形都可能相离。

4） 碰撞，两三角形处于接触的临界状态，包括共点和共边界两种状态，如图1(d)所示；也可以看作是相交或相叠的奇异状态。

直接计算空间两三角形的公共部分（交点、交线段或共面区域）的过程一般比较复杂，计算复杂度较大。迅速排除两个三角形不相交是判断空间两三角形关系的常用策略，因为在实际应用中真正相关的三角形数目在整个模型中占的比例常较小。

已经有多种关于三角形求交的算法，比较著名的有以下几种。

Möller算法[2]原理，如图2所示，设两个三角形A和B所在的平面分别为ΠA、ΠB。如果三角形A、B分别与平面ΠB、ΠA平面相交于LA、LB，则LA、LB必定在两平面ΠA、ΠB的交线L上；若 LA、LB有重叠部分，则两三角形相交，如图2(a)所示，否则就相离，如图 2(b)所示。通过计算三角形A的顶点与平面ΠB的距离以及三角形B的顶点与平面 ΠA的距离来判断三角形与平面的关系，从而快速排除部分不相交的三角形。这种方法需要建立两个三角形所在的平面。进行三角形分别与对方所在平面的2次“求交”及最后交线“重叠”部分的求取。

图2 两三角形空间求交的基本原理

Held[3]与Möller算法类似，首先判断三角形B的各个顶点是否位于平面 ΠA的同侧进行早期排除。如果B的3个顶点位于ΠA的两侧，则构造线段s=B∩ΠA。通过测试线段s是否与A相交来判断三角形对的相交与否。这种方法将空间三角形的相交测试降维为二维的线段与三角形的相交测试。

Tropp算法[4]与已有算法的重大不同是不用几何方法而采用代数方法，求解线性方程组，通过重利用方程组中的共同单元及矩阵的线性操作的策略减少计算量。

国内外学者在以上典型的三角形与三角形相交测试算法的基础上，提出了一些改进算法。张忠祥和王士同提出了基于 Ayellet 算法的改进算法[5]。首先快速排除掉两三角形不相交或共面的两种情况，然后分别计算一个三角形与另一个三角形所在平面相交线段，最后检测这两条线段是否有公共点。如果有公共点则三角形对相交，反之则不相交。邹益胜等对三角形求交的主要算法作了较为详细的描述并给出了测试结果[6]。

对于算法本身，很多改进算法都是在Möller和 Held算法基础上进行的。在算法的稳定性方面，大多算法采用代数的方式描述，很难从理论上阐明对各种奇异状态的处理；在算法评估方面，重点在于算法速度的测试，包括不同相交率对算法性能影响的测试，以及计算量的统计等。而对于稳定性的测试方面缺少详细的分析与测试。

本文将Möller相交判断原理加以改进，并首次提出一种基于投影降维的方法，将各种空间状态的几何奇异降为平面问题；并建立基于视图的几何表述与求解机制，在理论上保证算法的稳定性。

2 算法原理与策略

本文将 Möller求交判断的基本原理改造为以下两步（标识如图2所示），减少计算量。

1） 先求取B与ΠA的交线段得到LB；

2） 再求取LB在A内的部分得到交线。

首先，建立一个合适的计算坐标系，使其中一个三角形在坐标平面上。再基于两面正投影原理，将空间两三角形的问题归结为平面上直线段与三角形（或直线段）的位置关系问题。最后，求交与重叠判定两项工作也在平面上解决。

实施中采用以下策略，使相交计算与测试更快速、稳定、精确：

1） 几何代数化依赖于坐标系，选取合适的标系，简化几何的表述与计算。

2） 尽可能利用简单的比较和计算，例如利用包围球、盒来排除无关的计算对象，尽量减少主计算。

3） 降低维数，如把三维降为二维、二维降为一维。

4） 能处理各种特殊情况，尽可能充分利用标准的算法，提高算法的鲁棒性。

5） 尽量避免那些开销量大的计算，如三角函数、平方根、除法等。

3 计算坐标系

一个合适的坐标系可以简化几何的表述与代数运算，本算法将建立一个计算坐标系。计算坐标系的构造方法如下：设有两三角形A(A0, A1, A2)与B(B0, B1, B2)，以A所在的平面作为xy坐标平面，该平面的法向作为z轴，并以A的一条边（例子中选取边向量A1A2）作为x轴，如图3所示。（详见后面的“基本算法1”）。

图3 计算坐标系

记xy坐标平面为H面，zx坐标平面为V面，A与B在V面与H面上的投影分别为AV、AH与BV、BH。

在这个计算坐标系下，三角形A与B的表述与关系具有下列7项性质：

1） AH=A，即A所在平面就是xy坐标平面（V面），且A只占y≥0半平面。

2） AV积聚成一条x轴上的线段，即其中，

3） B在V、H面上的投影虽不定，但只可能是三角形或直线段2种。

4） 如果BV的3个z坐标值同号，那么B与A相离（图4的①、⑤、⑥，有0值时是碰撞关系）。

5） 如果BV的3个z坐标值相同，B与A所在平面平行；如果此时有1个z为0，两平面就重叠，即在平行条件下只要有1个BV的|z|＞0，B与A就不重叠。

6） 如果 BV与 AV相交，那么交点坐标为(x0,0,0)与(x1,0,0)，交点可通过BV每条边向量端点的z坐标值求得（详见后面“基本算法2”）。如果两个交点满足max(x0, x1)≤XL或者min(x0, x1)≥XR，那么B与A相离（图4的③、⑦，等于0时是碰撞关系）。

6） 在V面，A与B的位置关系只有如下2种情况：

（1） 水平直线段与直线段的关系，如图4(a)所示；（2）水平直线段与三角形的关系，如图4(b)所示。

图4 计算坐标系下空间两三角形在V面投影的关系

图4(a)中的V面上列出了A与B的线-线关系，其中①、③、⑤3种情况显出AV与BV是相离的，因而空间的A与B也相离，只需对②、④两种情况作进一步的检测。同样，在图4(b)中列出了V面上A与B的线-三角形关系，其中⑥、⑦两种情况也显出AV与BV是相离的，A与B也就相离，只需对⑧作进一步的检测。因此，A与B在①、⑤、⑥与③、⑦分布状态下的相离可以迅速予以排除，只需对②、④及⑧状态作进一步的检测，而这些检测均是在平面上进行的，后面会详细阐述对这些状态奇异性的解决策略。

引入计算坐标系不仅使得基于投影的两个空间三角形间的计算变得十分简单，更重要的是将空间几何奇异完全归结为平面问题，例如，能准确区分两个三角形“碰撞”与“相交”状态，使算法的稳定性和正确性大幅度提高。

4 总体算法设计与实现

4.1 两三角形计算的总体框架

在计算坐标系下，选取zx(V)与xy(H)投影面，求取两三角形顶点的两面正投影；根据两三角形的投影关系判断其空间位置关系，总体框架如图5所示。

图5 算法的总体框架

算法的主要步骤只需 3步（标识如图 3所示）。

1） 建立计算坐标系

（1） 过A(A0, A1, A2)的3个顶点建立平xy(H)平面，其法向作为 z轴，并以 A的一条边向量A1A2作为x轴，建立计算坐标系。（2）将A与B的顶点均变换到此坐标系下。

2） 在计算坐标系下求交计算：

（1） 求取B与A所在平面ΠA的交线段LB。

（2）求取LB在A内的部分Q0Q1。

Q0Q1就是B与A在计算坐标系下的交线。

3） 变换回原坐标系

如果A与B有交线，将其端点变换回原坐标系，得到A与B在原坐标系下的交线段。

4.2 计算坐标系下两三角形交线的计算

根据计算坐标系下两三角形表述与关系性质，其交线必定在xy平面上，如图6所示。这可以简化求取B与ΠA的交线段LB及求取LB在A内的部分这两步工作，具体分析如下：

图6 计算坐标系下两三角形交线的计算

Step 1 求取三角形B与ΠA的交线段LB。

因此，求取三角形B与ΠA的交线段LB简化为线性问题：

先在zx坐标平面上求取AV所在直线（在x轴上）与BV的交线，即LB在zx坐标平面上投影的两个端点其中ti为交点在BV边上参数，xi为交点的x坐标(i=0,1)，xi在AV与BV上是相同的，而zi为0；然后通过ti在B的相应三维边上插出第三维坐标yi，最后得到B与H面(ΠA)的交线P0P1。

Step 2 求取LB在A内的部分。

LB本身就在xy平面上，因此，这项工作在xy平面上进行：

计算Q0Q1=P0P1∩AH，如果Q0Q1=Φ，A与B相离；如果Q0=Q1，A与B是碰撞关系（1点接触）；如果Q0Q1≠Φ，那么Q0Q1就是三角形A与B的交线。

下面是本文提出的计算坐标系下两个三角形求交算法。

计算坐标系下空间两三角形求交算法（标识见图4）

输入：A，B 被检测的2个三角形

输出：*L Line3D 交线

返回值：0 三角形A与B 空间相离1 三角形A与B 空间相交2 三角形A与B 空间点碰撞点3 三角形A与B 空间线碰撞线-1三角形A与B 共面 重叠-2 三角形A与B 共面 相离-3 三角形A与B 共面 点碰撞-4 三角形A与B 共面 线碰撞-5 三角形A与B 平行 但非共面相离

说明：本算法针对A与B均为空间三角形，需先排除A

与B退化成空间直线段的情况

本算法在计算坐标系下进行，即已实施了以下操作：

(1)过三角形A的3个顶点建立平面作为xy（H）面，其法向作为z轴，首边向量作为x轴，建立新坐标系;

(2)三角形A与B均已变换到此坐标系下; //both AVand AWare line segments

int IntTwoTriangles3D(TRiangle A, TRiangle B, Line3D

*L)

{

//B∥H，both Bv and Bw are lines，①、②、③

//根据B的3点z坐标是否相同检测B∥H

if (B∥H ) { //B∥H

if (B与A共面) { //根据B的z坐标是否为0检测B与A的共面性

判断AH与BH两个三角形的关系；

if (AH与BH重叠) k=-1; //B与A共面重叠

if (AH与BH相离) k=-2; //B与A共面相离

if (AH与BH相交于一点) k=-3; //点碰撞

if (AH与BH相交于一线) k=-4; //线碰撞

}

else k=-5; //A与B平行但非共面=相离

return k;

} //B∥H

//B与A不平行，利用V、H平面计算

在V面上求取AV（直线）与BV边上交点与及对应的参数t0,A;

if (无交点) return 0; //③、⑤、⑥、⑦

根据交点在BV边上参数t0,A在B上插出y三维坐标，得到P0(x0,y0,0)与P1(x1,y1,0); //⑧

//x0、x1的值在三角形A与B上是相同的，不必重算。z0、z1在H面上，为0。

在H面上求取Q0Q1=P0P1∩AH;

if (Q0Q1=Φ) return 0; //三角形A与B不相交

if (Q0=Q1) return 2; //三角形A与B共面点碰撞

if (Q0Q1与AH某边重叠) return 3; //线碰撞

将Q0、Q1变换回原坐标系；//Q0Q1即为交线。

return 1;

}

5 基本算法的实现

下面给出两空间三角形求交时用到的一些基本算法，除变换算法以外，其余算法均在平面上进行。

5.1 构筑基于三角形的计算坐标系

基本算法1 设三角形由P1、P2、P3三点给出，构筑基于这三点的计算坐标系x*y*z*，如图7所示：

图7 以三角形构筑计算坐标系

1） P1P2单位向量作为n1(a1b1c1)

2） 通过P1、P2、P3三点求取三角形的单位法向量为n3(a3b3c3)。

上述以 P1为原点而互相垂直的三个单位向量n1、n2与n3构成计算坐标系x*y*z*，其中，n1、n2在三角形所在平面上，n3为平面的法向。新旧两坐标系间的坐标变换矩阵为：

和

其中，参数d1，d2，d3与D1、D2、D3根据新坐标系原点通过点P1求得：

变换公式为：

5.2 V面上交点的计算

在计算坐标系下，AV是x轴上的一段线段[XL, XR], BV可能是直线段或三角形。

1） 交点参数

基本算法2 设BV某个边的两端点为P0(x0, 0, z0)与P1(x1, 0, z1)，由于AV在x轴上，若边P0P1与AV有交点，则P0与P1必定一个在x轴上方，另一个在x轴下方，而交点的z=0，如图8所示。有：

如果z0与z1的符号相同，边P0P1与x轴不相交；

（1） 如果z0与z1的符号相反，边与x轴相交，交点为Pt=P0+t(P1-P0)，式中t=|z0|/(|z0|+|z1|)。

（2） 如果z0与z1中有一个或两个为0，则边与与x轴相交，交点为z坐标为零的端点。

（3） AH上的三维交点坐标(x, y, 0): x=x0+ t(x1-x0), y=y0+t(y1-y0)。

图8 V面上交点的计算

2） AV与BV的求交计算

基本算法 3 如果 BV是三角形，如图 9(a)所示，根据z=0的原则依次求取BV的3条边与x轴的交点，一般情况下，这样的交点有2个。设交点的参数为ti(i=0,1)，根据ti插出它的xi坐标，得到交点的参数(ti, xi, ni)，这里，ni是该交点在BV上的边号，因为三角形有3条边，ni可能的值为0、1、2。参数(ti, ni)将用于在H面上计算该交点的y值。

如果BV是直线段，实际上是B的3边在V面的积聚投影，如图9(b)所示，仍应作为3条边分别计算。虽然两交点的(ti, xi)参数是一样的，但是所在边号ni不一样，用(ti, ni)去求交点在空间的y时就会得到2个不同的值。

图9 V面上求交的统一

这样，不管 BV是三角形还是直线段，在本算法中在V面上求取交点的计算方式是统一的。

3） 排除AV与BV相离

基本算法4 为加速算法，可用拒绝判定快速排除AV与BV的相离。在计算坐标系下，排除计算也十分简单。

在z方向，如果BV的3个z坐标全为正或全为负，表明BV完全在AV的上方或下方，两者就无重叠关系（图10①）；

在x轴上，如果2个交点均位于AV右端点的右边（max(x0, x1)＞XR）或均位于AV左端点的左边（min(x0, x1)＜XL），那么AV与BV就相离（图10③）。

图10 水平线段与三角形的位置分布图

5.3 H面上直线段与三角形的交集的求取

基本算法 5 求取LB在A内的部分就是在H面上求取LB与AH的交集。线段与三角形的交集可借用任何一种凸多边形裁剪算法，这里借用Cyrus-Beck参数化裁剪算法[7]，将Cyrus-Beck对凸多边形参数化裁剪算法改造成 Cyrus-Beck三角形参数化裁剪算法，并增加了被裁剪线的端点或其本身在三角形边界上的奇异情况的处理（参见7.2 H面上线段与三角形的交集的几何奇异）。

6 几何奇异处理

6.1 V面求交时的几何奇异

在 V面上是直线段(AV)与三角形(BV)的三条边的求交，交点数可能是1、2、3个。

1） 交点数为1

表示交点在AV的左端点（x=0，图11④）或右端点（x=XR，图 11⑧），BV位于 AV的左侧或右侧。进一步对交点作 AH的包容性测试，如果交点在AH的内部或边界上，则A与B为“碰撞”关系，否则为相离关系；

2） 交点数为2

此时可能是正常交点（图11⑤）、共边（图11⑥）及共点（图 11⑦），前两者（⑤、⑥）进一步进行AH的裁剪测试，所得结果即为A与B的交线；后者（⑦）的交点数为1的处理方法相同；

3） 交点数为3

此时必有一个交点通过 BV的一个顶点（图11①、②、③），解决方法为删除通过顶点的一个交点。因为参数ti是基于BV的边向量的，因此，通过 BV的一个顶点的交点的参数 ti必有一个为0，另一个为1，如果不计ti=0的交点（也可不计ti=1的交点），交点就减为正常的2个。设3个交点的排列为0、1、2，处理方法是：

if (t0=0) t0=t2; n0=n2; //图11②

else if (t1=0) t1=t2; n1=n2; //图11①

n--; //n为交点计数，原来为3，现在为2

6.2 H面上线段与三角形的交集的几何奇异

H面上线段与三角形的交集的求取系借用Cyrus-Beck参数化裁剪算法，分为以下5种情况，奇异情况比较好处理，如图(12)所示。

1）正常的裁剪，如图12(a)所示；

2）直线穿越三角形的一个顶点，使得线段与三角形有3个交点，破坏了直线进出三角形的奇偶性，如图12(b)所示；

3）是直线通过顶点，但不“穿越”三角形，如图12(c)所示。

图12 三角形裁剪的奇异情况

4） 直线与三角形的某一边重合，在平面是共线，反映到空间是两三角形“共线”碰撞，如图12(d)所示。

5） 直线段的一个端点在三角形的边界上，反映到空间是两三角形“共点”碰撞，如图(e)所示。

上述(1)、(2)空间两三角形有交线，(3)、(4)、(5)“碰撞”。

最后，当H面上的线段退化为一点时，需要检测该点是否在 AH的内部，如果是，空间两三角形“共点”碰撞，否则，两三角形空间相离。

6.3 两三角形共面时的几何奇异

当两个三角形共面时，可能出现相离、碰撞（共点、共线）、重叠（包括内含）等关系。

不能简单地用“判断B(A)的顶点是否在A(B)的内部”，因为，即使两个三角形的顶点均在对方之外，两者仍可能是相交关系。

本文采用“如果B各边与A有交集，那就有重叠（反之也然）”的策略判定平面上两三角形的重叠关系。将两个三角形的重叠关系的问题降为“一线段与一三角形的重叠关系”的判定。最后也归结到前节“线段被三角形裁剪”算法中的一些奇异情况。

1) B中任一边被A三角形裁剪后如果有显示部分，两三角形为重叠关系；

2) B中三边被A三角形裁剪后均无显示部分，两三角形为相离关系；

3) B中任一边被A三角形裁剪后只显示1点，两三角形为点重叠关系；

4) B中任一边与A三角形的某边界重合，两三角形为边重叠关系。

需要注意的是，4)比3)的优先级高。

因为平面上2个三角形重叠时可能多达6个交点，最多可产生六边形，因此，“准确重叠部分的求取”并非一个简单的问题。考虑到大多数空间三角形关系处理的目标是判定他们的相离、碰撞和重叠关系等，只有在“曲面求交”等一类应用中才追究“准确重叠部分的求取”，因此，本算法不展开对它进一步讨论。而且这是一个平面问题，也可以参考文献[8]，用“两个平面多边形的布尔运算”方法解决。

7 测试与分析

7.1 奇异测试

两个空间三角形的奇异情况可在共面、相交情况下出现。共面情况下可能有共点、共线、内含等；相交情况下可能有共点、共线等。

本算法根据这些情况构造了相应的奇异测试例子。测试样本根据两三角形所位平面的关系分为平面平行、重合和相交3大类，如图13所示。

图13 测试样本的分类

测试样本中，先将一个三角形A固定，变换另一三角形B的位置实现各种空间位置关系。对一个A，设计了包括图1、图4、图10、图11以及图12中描述位置关系在内的23种与A位置呈现含奇异状态的三角形B。此外，还设计了其它30种空间位置关系的三角形，包含了各种直接分离、H面检测等情况（图14）。测试结果是本算法均能正确处理。

图14 三视图表达的测试样本举例

7.2 速度测试

用40对三角形，重复100万次相交计算，分别在笔记本电脑与台式电脑两类机器上进行测试，测试结果如表1所示。

表1 本算法对40×1000000对空间三角形进行相交测试的时间表(sec)

计算坐标系下的测试，在笔记本电脑上，0.95秒(38/40)可处理100万对三角形的相交计算，在台式电脑上，0.7秒(28/40)可处理100万对三角形的相交计算。

在一般坐标系下测试，在笔记本电脑上，1.2秒(47/40)可处理100万对三角形的相交计算，在台式电脑上，0.775秒(31/40)可处理100万对三角形的相交计算。

7.3 算法分析

在粗略排除阶段，可以采用直接三维空间判断和投影判断相结合的方法。例如，图4中的①、⑤、⑥状态也可直接在三维空间进行判断：对三角形A建立一个平面，ax+by+cz+d=0，将三角形B的3个顶点代入A的这个平面方程，得到3个数：如果全部同号，则三角形B与A分离。而对于排除图4中的③、⑦状态用投影办法较好。

本算法需要进行“计算坐标系的建立”、“A与B三个顶点的齐次变换”以及“交点变换回原坐标系”等变换计算。因此，我们专门考察了变换在本算法中所占时间的份额——最高为 16%左右。

实际上，在大规模的三角形求交计算中不需要对每对求交的三角形进行计算坐标系的建立与变换计算，例如，对每一个A建立计算坐标系，变换1次A，而只对与A相关的（一系列）B进行变换即可。

经计算坐标系下的投影降维，A与B的关系可以直接用图形在平面上“画”出来，将空间几何关系降解为视图中直线段与三角形（或直线段）的关系，能严格区分两个三角形的“碰撞”、“相交”“相离”与“重叠”的关系，便于发现处理各种几何奇异情况；同时这种变换使算法变得更清晰，计算更简单，例如“两线段求交的参数求取只需1次加法，1次除法”。因此，综合分析，本算法的变换开销利大于弊。

在计算策略上，充分利用直线的参数表述，采用分而治之的办法将空间问题变为平面问题、线性问题，使得几何表述更简单、几何间的关系更清晰，可以使用更多的“通用”的算法，例如，凸多边形裁剪算法，使算法更为规范。

8 总 结

本文给出了一种基于投影降维的空间两三角形求交检测方法的详细方案和算法。这是一种几何化的全新思路，能从理论上严格保各种奇异情况的发现与正确处理。也为其它基本几何元求交、碰撞检测等提供了一种新的解题思路。

[1] Christer Ericson. Triangle-triangle tests, plus the art of benchmarking [EB/OL]. http://realtimecollisiondetection. net/blog/?p=29.

[2] Möller T. A fast triangle-triangle intersection test [J]. Journal of Graphics Tools, 1997, 2(2): 25-30.

[3] Held M. Erit: a collection of efficient and reliable intersection tests [J]. Journal of Graphics Tools, 1997, 2(4): 25-44.

[4] Tropp O Tala, Shimshoni I. A fast triangle to triangle intersection test for collision etection [J]. Computer Animation and Virtual Worlds, 2006, 17(5): 527-535.

[5] 张忠祥, 王士同. 三角形对的快速相交测试[J]. 计算机工程与设计, 2010, 3(4): 869-875.

[6] 邹益胜, 丁国富, 何 邕, 等. 空间三角形快速相检测算法[J]. 计算机应用研究, 2008, 25(10): 2907-2909.

[7] CYRUS M, BECK J. Generalized two-and three-dimensional clip-ping [J]. Computers and Graphics, 1978, 3(1): 23-28.

[8] 何援军. 计算机图形学(第 2版)[M]. 北京: 机械工业出版社, 2009.

Testing the Intersection Status of Two Triangles

Yu Haiyan1, He Yuanjun2
( 1. College of Mechanical Engineering, Donghua University, Shanghai 201620, China; 2. Dept. of Computer Science & Engineering, Shanghai Jiaotong University, Shanghai 200240, China )

This paper focuses on geometric singularity and algorithm speed. In our algorithm, a 3D problem is reduced to planes and is further divided to a linear problem. In order to simplify the representation of geometric problem, a computational coordinate system is constructed. Thus, the geometric singularity of two triangles is reduced to planar problems between a line and a triangle, which limits the singularity to co-points and co-lines. Consequently, the complex spatial geometric singularity can be represented by planar drawings simply and visually and the robustness of our algorithm can be certificated theoretically. This paper gives the whole algorithm and detailed schemes. Experiment tests show that the priority in simplifying geometric relations, geometric singularity and calculations is sufficient to make up for the cost of transformation. The speed is 1 million pairs of triangles per second on a notebook computer.

geometric computing; triangles intersection; dimension reduction; geometric singularity; computational coordinates

TP 391.72

A

2095-302X (2013)04-0054-09

2013-04-29；定稿日期：2013-05-03

国家自然基金资助项目（61073083）；中央高校基本科研业务费专项资金资助

于海燕（1974-），女，黑龙江海林人，副教授，博士，主要研究方向为CAD/CG。E-mail：yuhy@dhu.edu.cn