空间三角面片对相交判断算法
关立文 1 , 戴玉喜 2 , 王立平 1     
1. 清华大学 机械工程系, 北京 100084;
2. 电子科技大学 机械电子工程学院, 成都 611731
摘要:空间三角面片对相交判断是数控加工过程仿真中碰撞干涉检验和材料去除仿真等研究的关键技术。为了提高算法准确性和计算效率,该文提出一种基于向量运算的三角面片对相交快速判断算法,有效避免了计算误差对相交判断准确性影响,全面解决共面和异面情况下的快速准确判断问题,通过与典型相交判定算法比较,该算法与被比较算法的检测准确率都能够达到100%。该文算法全面考虑了异面和共面情况,综合计算效率有所提高。
关键词数控加工    碰撞检测    空间三角面片对    相交判断    向量运算    
Intersection test algorithm for spacial triangular facets
GUAN Liwen1, DAI Yuxi2, WANG Liping1     
1. Department of Mechanical Engineering, Tsinghua University, Beijing 100084, China;
2. School of Mechatronics Engineering, University of Electronic Science and Technology of China, Chengdu 611731, China
Abstract: Intersection tests for spacial triangular facets is one of the key techniques for collision and interference detection in material cutting algorithms for numerically controlled machining. A fast, spacial triangular facet intersection test algorithm was developed based on vector operations that avoids test faults due to calculational errors. The algorithm deals with all relationships between triangular facets such as being in the same plane or different planes. The algorithm efficiency and accuracy is much better than traditional algorithms.
Key words: numerical control machining     collision detection     spacial triangular facets     intersection test     vector operation    

三角面片对相交快速准确判断是STL(stereo lithography)模型Bool运算[1-3]和计算机虚拟仿真[4-6]等研究的关键技术。目前典型三角面片对相交判断算法有文[7-10]等研究,大部分算法以Möller算法[7]为基础,通过投影变换将空间三角面片对求交转换为两线段求交问题,邹益胜等[11]对三角面片异面求交算法作了改进,于海燕等[12]采用投影降维转换为二维平面求交问题。

总体上看,已有算法侧重于研究三角面片异面时的相交判断方法,大多基于Möller算法运用投影求交的思想做一些改进,对共面情况研究较少,由于计算机处理过程中存在误差,可能存在判断错误。

本文提出一种全面快速的三角面片相交判断算法,采用向量点积和叉积,针对三角面片共面和异面情况均给出具体判断方法,能够克服计算机处理误差导致判断错误,算法结构简单明了,精度、效率和全面性均有提高。

1 算法原理

在STL格式模型中,三角面片顶点相对于实体外侧法向量按照逆时针排列。不失一般性,设拟相交判断的2个三角面片为T1T2T1的3个顶点分别为A1B1C1,所在平面为π1,法向量为n1; T2的3个顶点分别为A2B2C2,所在平面为π2,法向量为n2

根据T2π1的关系或T1π2的关系可以初步将T1T2的相交状态分为3种情况。

1) T2不与平面π1相交或T1不与平面π2相交,则T1T2一定不相交。

2) T2在平面π1上或T1在平面π2上,则T1T2共面,转化为二维平面三角面片相交问题。

3) T2与平面π1相交或T1与平面π2相交,则T1T2异面,分别判断T2中是否存在边与T1相交以及T1中是否存在边与T2相交即可。

1.1 一定不相交的情况

判断T2的3个顶点是否在平面π1同侧,建立表达式:

$ \left\{ \begin{array}{l} {t_1} = {\pmb{A}_1}{\pmb{A}_2} \cdot {\pmb{n}_1}, \\ {t_2} = {\pmb{A}_1}{\pmb{B}_2} \cdot {\pmb{n}_1}, \\ {t_3} = {\pmb{A}_1}{\pmb{C}_2} \cdot {\pmb{n}_1}. \end{array} \right. $ (1)

如果t1t2t3同号且都不为零,则三角面片T1T2不相交。如图 1所示,T2的3个顶点均在π1平面上部,t1t2t3均大于0,T1T2不相交;当t1t2t3均小于0,T2的3个顶点均在π1平面下部,T1T2不相交。

图 1 T2π1上半空间

1.2 共面情况

计算T1T2的法向量叉积f

$ \pmb{f} = {\pmb{n}_1} \times {\pmb{n}_2}. $ (2)

如果f=0T1T2是否平行(或共面)需要继续判断T2的任一顶点是否在π1上,即式(1) 中t1t2t3为0,则T1T2共面,此时三角面片对相交判断是二维平面三角面片对相交判断问题,判定算法如下。

步骤1  分别判断A1B1C1是否在三角面片T2内, A2B2C2是否在三角面片T1内,如果以上判断结果有一个为真,则三角面片T1T2相交;如果以上判断结果均为否,转步骤2。

判断三角面片所在平面内一点是否在三角面片内,算法如下。

求取三角面片每一条边向量在平面内的垂向量,再通过垂向量方向判断另一顶点与待检测点是否在边向量所在直线的同一侧。如图 2所示,判断A2是否在三角面片T1内,首先建立表达式:

图 2 点与三角面片的关系

$ \left\{ \begin{array}{l} {k_1} = \left[{{\pmb{A}_1}{\pmb{A}_2} \cdot \left( {{\pmb{A}_1}{\pmb{B}_1} \times {\pmb{n}_1}} \right)} \right] \cdot \left[{{\pmb{A}_1}{\pmb{C}_1} \cdot \left( {{\pmb{A}_1}{\pmb{B}_1} \times {\pmb{n}_1}} \right)} \right], \\ {k_2} = \left[{{\pmb{B}_1}{\pmb{A}_2} \cdot \left( {{\pmb{B}_1}{\pmb{C}_1} \times {\pmb{n}_1}} \right)} \right] \cdot \left[{{\pmb{B}_1}{\pmb{A}_1} \cdot \left( {{\pmb{B}_1}{\pmb{C}_1} \times {\pmb{n}_1}} \right)} \right], \\ {k_3} = \left[{{\pmb{C}_1}{\pmb{A}_2} \cdot \left( {{\pmb{C}_1}{\pmb{A}_1} \times {\pmb{n}_1}} \right)} \right] \cdot \left[{{\pmb{C}_1}{\pmb{B}_1} \cdot \left( {{\pmb{C}_1}{\pmb{A}_1} \times {\pmb{n}_1}} \right)} \right]. \end{array} \right. $ (3)

如果k1k2k3均为非负,则A2在三角形T1内;如果k1k2k3中存在负值,则A2不在T1内。

图 2ak1>0,k2>0,k3 < 0,此时k3为负,所以A2在三角面片T1外部;图 2bk1>0, k2>0, k3>0,此时k1k2k3均为非负,所以A2在三角面片T1内部;图 2ck1>0,k2>0,k3=0, 此时k1k2k3均为非负,A2在三角面片T1内部,因k3=0,所以A2T1的边C1A1上;图 2dk1=0, k2>0, k3=0,此时k1k2k3均为非负,A2在三角面片T1内部,因k1=0且k3=0,所以A2T1的顶点A1上。

T1的3个顶点均沿法向量方向逆时针排列时,式(3) 中各对应算式中的后一项均为负,如在k1A1C1·(A1B1×n1)的值为负(k2k3中对应项亦如此),当T1三顶点均沿法向量方向顺时针排列,该项值为正。

步骤2  如果A1B1C1都不在三角面片T2内且A2B2C2也都不在三角面片T1内,此时如果T1T2相交只有可能是图 3中所示情况。只需判断T2的3个顶点是否在T1每条边A1B1B1C1C1A1异侧,以及T1的3个顶点是否在T2每条边A2B2B2C2C2A2异侧。如果都满足,则T1T2相交,否则不相交。

图 3 点不在三角面片内部时的相交情况

例如,判断T2三顶点A2B2C2是否在A1B1异侧,建立表达式:

$ \left\{ \begin{array}{l} {h_1} = {\pmb{A}_1}{\pmb{A}_2} \cdot \left( {{\pmb{A}_1}{\pmb{B}_1} \times {\pmb{n}_1}} \right), \\ {h_2} = {\pmb{A}_1}{\pmb{B}_2} \cdot \left( {{\pmb{A}_1}{\pmb{B}_1} \times {\pmb{n}_1}} \right), \\ {h_3} = {\pmb{A}_1}{\pmb{C}_2} \cdot \left( {{\pmb{A}_1}{\pmb{B}_1} \times {\pmb{n}_1}} \right). \end{array} \right. $ (4)

如果计算得h1h2h3不同时为正或不同时为负,则A2B2C2A1B1异侧。

1.3 异面情况

如果式(2) 中f的计算结果不为0,则三角面片T1T2异面,分别判断线段A1B1B1C1C1A1是否与三角面片T2相交,以及线段A2B2B2C2C2A2和三角面片是否与T1相交,如果以上判断结果均为否,则三角面片T1T2不相交;如果以上判断结果有一个为真,则三角面片T1T2相交。其中线段与三角面片的相交判断是通过运用向量之间点积和叉积的特点来判断线段是否穿过三角面片而实现的,如图 4所示,判断T2的边A2B2是否与三角面片T1相交,建立表达式:

图 4 线段与三角面片部分相交情况

$ {\pmb{S}_1} = {\pmb{A}_1}{\pmb{A}_2} \times {\pmb{n}_1}, $ (5)
$ {\pmb{S}_2} = {\pmb{A}_1}{\pmb{B}_2} \times {\pmb{n}_1}. $ (6)

S1=S2=0时,线段A2B2T1共面;否则A2B2T1异面。以下从共面和异面2种情况展开论述。

1) 异面。由于A2B2T1异面,首先计算(S1·S2),倘若结果为正,则A2B2π1同侧,判定A2B2不与T1相交;否则A2B2π1异侧且A2B2至少有一点不在平面π1上。假设A2不在π1上。建立表达式:

$ \left\{ \begin{array}{l} {g_1} = \left[{{\pmb{A}_1}{\pmb{B}_2} \cdot \left( {{\pmb{A}_1}{\pmb{B}_1} \times {\pmb{A}_1}{\pmb{A}_2}} \right)} \right] \cdot \\ \;\;\;\;\;\;\;\left[{{\pmb{A}_1}{\pmb{C}_1} \cdot \left( {{\pmb{A}_1}{\pmb{B}_1} \times {\pmb{A}_1}{\pmb{A}_2}} \right)} \right], \\ {g_2} = \left[{{\pmb{B}_1}{\pmb{B}_2} \cdot \left( {{\pmb{B}_1}{\pmb{C}_1} \times {\pmb{B}_1}{\pmb{A}_2}} \right)} \right] \cdot \\ \;\;\;\;\;\;\;\left[{{\pmb{B}_1}{\pmb{A}_1} \cdot \left( {{\pmb{B}_1}{\pmb{C}_1} \times {\pmb{B}_1}{\pmb{A}_2}} \right)} \right], \\ {g_3} = \left[{{\pmb{C}_1}{\pmb{B}_2} \cdot \left( {{\pmb{C}_1}{\pmb{A}_1} \times {\pmb{C}_1}{\pmb{A}_2}} \right)} \right] \cdot \\ \;\;\;\;\;\;\;\left[{{\pmb{C}_1}{\pmb{B}_1} \cdot \left( {{\pmb{C}_1}{\pmb{A}_1} \times {\pmb{C}_1}{\pmb{A}_2}} \right)} \right]. \end{array} \right. $ (7)

如果g1g2g3计算结果中存在小于0的情况,则线段A2B2与三角面片T1不相交;如果3个结果均为非负,则线段A2B2与三角面片T1相交。如图 4a所示,此时A2B2T1相交,g1g2g3的计算结果均为非负;而A2C2π1异侧,但是线段A2C2不与T1相交,对应上述表达式必定存在小于0的情况。

2) 共面。如果A2B2T1共面,首先运用前述方法判断A2B2是否在T1内,若至少存在一点在T1内,则线段A2B2T1相交;若A2B2都不在T1内,只有2种情况:A2B2T1不相交和A2B2T1共面相交。此时如果A2B2T1共面相交,T1中必定存在边与T2异面相交,由于T1T2的每一条边都要作相交判断,所以当A2B2都不在T1内,算法中可认定为不相交或不作处理,不影响T1T2相交判定最终结果。如图 4b所示,A2B2都不在T1内,但A2B2T1共面相交,而在T1A1C1B1C1都与三角面片T2异面相交,而它们会在异面线段与三角面片的相交判断中被检测出来。

2 算法流程

根据上述计算原理,本文算法流程如图 5所示。

图 5 算法流程图

根据算法原理中的方法可将算法的计算流程描述如下。

1) 计算T1各顶点与π1的关系及T2各顶点与π2的关系,排除不相交情况。总流程的伪代码为:

if (A1B1C1π2同侧或A2B2C2π1同侧)

  T1T2不相交,返回假;

else

  if (n1n2平行,且T2任一顶点在π1上)

    判定T1T2共面,goto(2);

  else

    判定T1T2异面,goto(3);

  end if

end if

2) 当T1T2共面时,计算流程的伪代码为:

if (存在T1的顶点在T2内部或者存在T2的顶点在T1内部)

    判定T1T2相交,返回真;

  else

    if (T2的顶点分布在T1每一条边异侧且T1的顶点分布在T2每一条边异侧)

    T1T2相交,返回真;

  else

    T1T2不相交,返回假;

  end if

end if

3) 当T1T2异面时,计算流程的伪代码为:

if (存在T2边与T1相交或存在T1的边与T2相交)

  判定T1T2相交,返回真;

else

  T1T2不相交,返回假;

end if

3 算法分析与测试

计算量决定着算法运行速度,算法中有加减、乘除、比较、绝对值和赋值等运算,这几种运算运行时间视为相同[13],算法计算量可看成这几种运算总和。目前典型算法侧重于三角面片异面时相交判断,邹益胜等[11]算法在Möller[7]的基础上进行了改进,对比了各算法计算量,表 1给出异面情况时本文算法运算量与现有算法对比,从中可知,本文算法比其他算法的计算量要小很多。

表 1 判断空间三角面片异面相交时各算法计算量的比较
算法 加减 乘除 比较 绝对值 赋值 计算量
文[9] 76 52 10/18 0 64 138/146
文[10] 70 56/58 12/82 0 62 138/210
文[7] 57 63 12/22 3/9 70 135/154
文[8] 42/45 56/57 22/30 0 36/44 120/132
文[11] 37/45 52/54 22 0 45 111/121
本文 5 24/28 38 0 32 67/71

目前典型算法主要是在Möller算法基础上对异面情况改进,共面情况仍采用Möller算法。根据文[11]所述,当三角形对样本相交率大于0.2时,改进算法检测效率优于其他典型算法,且随着相交率和检测规模的增大优势越明显。为提高本文算法测试效率,从异面与共面两方面进行测试比较,其中异面情况以文[11]改进的算法为比较对象,共面情况以Möller算法为比较对象,进行本文算法实际性能的检测。计算机硬件条件为:AMD A8-4 500 M,1.90 GHz,内存4 GB,Win XP操作系统。

测试内容:三角面片对不同相交情况的检测速度和检测准确度的比较。

测试方案:每种相交情况为一个样本,每个样本由10组相交三角面片对组成,测试程序循环运行1 000次。每个样本检测5次,取平均值。

测试工具:MATLAB R2014a。

测试结果(见表 2)表明:本文算法与被比较算法的检测准确率都能够达到100%;当三角面片异面不相交、共面不相交、共面相交时,本文算法计算速度提高25%~48%;当三角面片异面相交时稍有降低,总体计算效率有所改善。

表 2 不同相交情况下本文算法与改进算法对三角面片检测速度及准确率的比较
算法 异面不相交 异面相交 共面不相交 共面相交
t/s 准确率/% t/s 准确率/% t/s 准确率/% t/s 准确率/%
文[11] 14.357 2 100 17.668 7 100
文[7] 60.062 8 100 34.939 4 100
本文 9.761 0 100 19.707 7 100 44.772 7 100 18.186 8 100

4 总结

本文提出了一种基于向量运算的空间三角面片对快速全面相交判断算法,有效避免了计算误差对相交判断准确性影响,验证对比结果表明:该算法能有效避免计算误差的影响,提高综合判断效率和检测精度。

参考文献
[1] 刘冰, 张李超, 莫健华, 等. STL模型布尔运算交线链和交线环提取算法[J]. 华中科技大学学报(自然科学版), 2009, 37(3): 113–115. LIU Bing, ZHANG Lichao, MO Jianhua, et al. Forming intersection chains and loops in Boolean operation of STL models[J]. Journal of Huazhong University of Science and Technology (Natural Science Edition), 2009, 37(3): 113–115. (in Chinese)
[2] 赵斌涛. 基于桁架结构的3-D打印轻量化模型生成研究[D]. 杭州: 浙江大学, 2016. ZHAO Bintao. Research on the Generation of Truss Structure based 3-D Printing Lightweight Model[D]. Hangzhou:Zhejiang University, 2016. (in Chinese) http://cdmd.cnki.com.cn/Article/CDMD-10335-1016042411.htm
[3] 熊建伟数控加工过程几何仿真中碰撞检测与精度检验技术研究[D]. 成都: 电子科技大学, 2014. XIONG Jianwei. Research on Collision Detection and Precision Verification in the CNC Machining Simulation[D]. Chengdu:University of Electronic Science and Technology of China, 2014. (in Chinese) http://cdmd.cnki.com.cn/Article/CDMD-10614-1015706384.htm
[4] 姜燕, 李亢. 计算机虚拟仿真技术在医学教学中的应用研究[J]. 内江科技, 2016, 37(5): 48–49. JANG Yan, LI Kang. Research on the application of computer virtual simulation technology in medical teaching[J]. Neijiang Science and Technology, 2016, 37(5): 48–49. (in Chinese)
[5] 蔡大鹏, 谭亮. 计算机虚拟仿真实验平台的实现[J]. 软件导刊.教育技术, 2017, 16(1): 76–77. CAI Dapeng, TAN Liang. Realization of computer virtual simulation experiment platform[J]. Software Guide and Educational Technology, 2017, 16(1): 76–77. (in Chinese)
[6] 侯伟伟, 宁汝新, 刘检华. 虚拟装配中基于精确模型的碰撞检测算法[J]. 计算机辅助设计与图形学学报, 2010, 22(5): 797–802. HOU Weiwei, NING Ruxin, LIU Jianhua. A collision detection algorithm based on accurate models in virtual assembly[J]. Journal of Computer Aided Design & Computer Graphics, 2010, 22(5): 797–802. (in Chinese)
[7] Möller T. A fast triangle-triangle intersection test[J]. Journal of Graphics Tools, 1997, 2(2): 25–30. DOI:10.1080/10867651.1997.10487472
[8] Tropp O, Tal A, Shimshoni I. A fast triangle to triangle intersection test for collision detection[J]. Computer Animation and Virtual Worlds, 2006, 17(5): 527–535. DOI:10.1002/(ISSN)1546-427X
[9] Devillers O, Guigue P. Faster Triangle-triangle Intersection Tests[D]. Paris:INRIA, 2002. http://halshs.archives-ouvertes.fr/INRIA-SOPHIA/inria-00072100v1
[10] Shen H, Heng P A, Tang Z. A fast triangle-triangle overlap test using signed distances[J]. Journal of Graphics Tools, 2003, 8(1): 17–23.
[11] 邹益胜, 丁国富, 何邕. 快速空间三角形对相交检测算法[J]. 西南交通大学学报, 2011, 46(6): 984–988. ZOU Yisheng, DING Guofu, HE Yi. Fast intersection algorithm between spatial triangle pairs[J]. Journal of Southwest Jiaotong University, 2011, 46(6): 984–988. (in Chinese)
[12] 于海燕, 何援军. 空间两三角形的相交问题[J]. 图学学报, 2013, 34(4): 54–62. YU Haiyan, HE Yuanjun. Testing the intersection status of two triangles[J]. Journal of Graphics, 2013, 34(4): 54–62. (in Chinese)