空间三角面片对相交判断算法

删除或更新信息，请邮件至freekaoyan#163.com(#换成@)

本站小编 Free考研考试/2020-04-15

关立文 ¹ , 戴玉喜 ² , 王立平 ¹
1. 清华大学机械工程系, 北京 100084;
2. 电子科技大学机械电子工程学院, 成都 611731

收稿日期：2016-09-15
基金项目：国家科技重大专项（2013ZX04001-021）
作者简介：关立文(1972-), 男, 副研究员。E-mail:guanlw@tsinghua.edu.cn

摘要：空间三角面片对相交判断是数控加工过程仿真中碰撞干涉检验和材料去除仿真等研究的关键技术。为了提高算法准确性和计算效率，该文提出一种基于向量运算的三角面片对相交快速判断算法，有效避免了计算误差对相交判断准确性影响，全面解决共面和异面情况下的快速准确判断问题，通过与典型相交判定算法比较，该算法与被比较算法的检测准确率都能够达到100%。该文算法全面考虑了异面和共面情况，综合计算效率有所提高。
关键词：数控加工碰撞检测空间三角面片对相交判断向量运算
Intersection test algorithm for spacial triangular facets
GUAN Liwen¹, DAI Yuxi², WANG Liping¹
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 machiningcollision detectionspacial triangular facetsintersection testvector operation
三角面片对相交快速准确判断是STL(stereo lithography)模型Bool运算^[1-3]和计算机虚拟仿真^[4-6]等研究的关键技术。目前典型三角面片对相交判断算法有文[7-10]等研究，大部分算法以M?ller算法^[7]为基础，通过投影变换将空间三角面片对求交转换为两线段求交问题，邹益胜等^[11]对三角面片异面求交算法作了改进，于海燕等^[12]采用投影降维转换为二维平面求交问题。
总体上看，已有算法侧重于研究三角面片异面时的相交判断方法，大多基于M?ller算法运用投影求交的思想做一些改进，对共面情况研究较少，由于计算机处理过程中存在误差，可能存在判断错误。
本文提出一种全面快速的三角面片相交判断算法，采用向量点积和叉积，针对三角面片共面和异面情况均给出具体判断方法，能够克服计算机处理误差导致判断错误，算法结构简单明了，精度、效率和全面性均有提高。
1 算法原理在STL格式模型中，三角面片顶点相对于实体外侧法向量按照逆时针排列。不失一般性，设拟相交判断的2个三角面片为T₁和T₂，T₁的3个顶点分别为A₁、B₁和C₁，所在平面为π₁，法向量为n₁; T₂的3个顶点分别为A₂、B₂和C₂，所在平面为π₂，法向量为n₂。
根据T₂与π₁的关系或T₁与π₂的关系可以初步将T₁、T₂的相交状态分为3种情况。
1) T₂不与平面π₁相交或T₁不与平面π₂相交，则T₁、T₂一定不相交。
2) T₂在平面π₁上或T₁在平面π₂上，则T₁、T₂共面，转化为二维平面三角面片相交问题。
3) T₂与平面π₁相交或T₁与平面π₂相交，则T₁、T₂异面，分别判断T₂中是否存在边与T₁相交以及T₁中是否存在边与T₂相交即可。
1.1 一定不相交的情况判断T₂的3个顶点是否在平面π₁同侧，建立表达式：

$\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)

如果t₁、t₂和t₃同号且都不为零，则三角面片T₁和T₂不相交。如图 1所示，T₂的3个顶点均在π₁平面上部，t₁、t₂和t₃均大于0，T₁和T₂不相交；当t₁、t₂和t₃均小于0，T₂的3个顶点均在π₁平面下部，T₁和T₂不相交。

图 1 T₂在π₁上半空间

图选项

1.2 共面情况计算T₁和T₂的法向量叉积f：

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

(2)

如果f=0，T₁与T₂是否平行(或共面)需要继续判断T₂的任一顶点是否在π₁上，即式(1) 中t₁、t₂和t₃为0，则T₁和T₂共面，此时三角面片对相交判断是二维平面三角面片对相交判断问题，判定算法如下。
步骤1??分别判断A₁、B₁和C₁是否在三角面片T₂内, A₂、B₂和C₂是否在三角面片T₁内，如果以上判断结果有一个为真，则三角面片T₁和T₂相交；如果以上判断结果均为否，转步骤2。
判断三角面片所在平面内一点是否在三角面片内，算法如下。
求取三角面片每一条边向量在平面内的垂向量，再通过垂向量方向判断另一顶点与待检测点是否在边向量所在直线的同一侧。如图 2所示，判断A₂是否在三角面片T₁内，首先建立表达式：

图 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)

如果k₁、k₂、k₃均为非负，则A₂在三角形T₁内；如果k₁、k₂、k₃中存在负值，则A₂不在T₁内。
图 2a为k₁>0，k₂>0，k₃ < 0，此时k₃为负，所以A₂在三角面片T₁外部；图 2b为k₁>0, k₂>0, k₃>0，此时k₁、k₂、k₃均为非负，所以A₂在三角面片T₁内部；图 2c为k₁>0，k₂>0，k₃=0, 此时k₁、k₂、k₃均为非负，A₂在三角面片T₁内部，因k₃=0，所以A₂在T₁的边C₁A₁上；图 2d为k₁=0, k₂>0, k₃=0，此时k₁、k₂、k₃均为非负，A₂在三角面片T₁内部，因k₁=0且k₃=0，所以A₂在T₁的顶点A₁上。
当T₁的3个顶点均沿法向量方向逆时针排列时，式(3) 中各对应算式中的后一项均为负，如在k₁中A₁C₁·(A₁B₁×n₁)的值为负(k₂、k₃中对应项亦如此)，当T₁三顶点均沿法向量方向顺时针排列，该项值为正。
步骤2??如果A₁、B₁和C₁都不在三角面片T₂内且A₂、B₂和C₂也都不在三角面片T₁内，此时如果T₁、T₂相交只有可能是图 3中所示情况。只需判断T₂的3个顶点是否在T₁每条边A₁B₁、B₁C₁、C₁A₁异侧，以及T₁的3个顶点是否在T₂每条边A₂B₂、B₂C₂、C₂A₂异侧。如果都满足，则T₁、T₂相交，否则不相交。

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

图选项

例如，判断T₂三顶点A₂、B₂、C₂是否在A₁B₁异侧，建立表达式：

$\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)

如果计算得h₁、h₂和h₃不同时为正或不同时为负，则A₂、B₂、C₂在A₁B₁异侧。
1.3 异面情况如果式(2) 中f的计算结果不为0，则三角面片T₁和T₂异面，分别判断线段A₁B₁、B₁C₁、C₁A₁是否与三角面片T₂相交，以及线段A₂B₂、B₂C₂、C₂A₂和三角面片是否与T₁相交，如果以上判断结果均为否，则三角面片T₁和T₂不相交；如果以上判断结果有一个为真，则三角面片T₁和T₂相交。其中线段与三角面片的相交判断是通过运用向量之间点积和叉积的特点来判断线段是否穿过三角面片而实现的，如图 4所示，判断T₂的边A₂B₂是否与三角面片T₁相交，建立表达式：

图 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)

当S₁=S₂=0时，线段A₂B₂与T₁共面；否则A₂B₂与T₁异面。以下从共面和异面2种情况展开论述。
1) 异面。由于A₂B₂与T₁异面，首先计算(S₁·S₂)，倘若结果为正，则A₂B₂在π₁同侧，判定A₂B₂不与T₁相交；否则A₂、B₂在π₁异侧且A₂和B₂至少有一点不在平面π₁上。假设A₂不在π₁上。建立表达式：

$\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)

如果g₁、g₂和g₃计算结果中存在小于0的情况，则线段A₂B₂与三角面片T₁不相交；如果3个结果均为非负，则线段A₂B₂与三角面片T₁相交。如图 4a所示，此时A₂B₂与T₁相交，g₁、g₂、g₃的计算结果均为非负；而A₂、C₂在π₁异侧，但是线段A₂C₂不与T₁相交，对应上述表达式必定存在小于0的情况。
2) 共面。如果A₂B₂与T₁共面，首先运用前述方法判断A₂、B₂是否在T₁内，若至少存在一点在T₁内，则线段A₂B₂与T₁相交；若A₂、B₂都不在T₁内，只有2种情况：A₂B₂与T₁不相交和A₂B₂与T₁共面相交。此时如果A₂B₂与T₁共面相交，T₁中必定存在边与T₂异面相交，由于T₁、T₂的每一条边都要作相交判断，所以当A₂、B₂都不在T₁内，算法中可认定为不相交或不作处理，不影响T₁、T₂相交判定最终结果。如图 4b所示，A₂、B₂都不在T₁内，但A₂B₂与T₁共面相交，而在T₁中A₁C₁、B₁C₁都与三角面片T₂异面相交，而它们会在异面线段与三角面片的相交判断中被检测出来。
2 算法流程根据上述计算原理，本文算法流程如图 5所示。

图 5 算法流程图

图选项

根据算法原理中的方法可将算法的计算流程描述如下。
1) 计算T₁各顶点与π₁的关系及T₂各顶点与π₂的关系，排除不相交情况。总流程的伪代码为:
if (A₁、B₁和C₁在π₂同侧或A₂、B₂和C₂在π₁同侧)
??T₁、T₂不相交，返回假；
else
??if (n₁与n₂平行，且T₂任一顶点在π₁上)
????判定T₁、T₂共面，goto(2)；
??else
????判定T₁、T₂异面，goto(3)；
??end if
end if
2) 当T₁、T₂共面时，计算流程的伪代码为：
if (存在T₁的顶点在T₂内部或者存在T₂的顶点在T₁内部)
????判定T₁、T₂相交，返回真；
??else
????if (T₂的顶点分布在T₁每一条边异侧且T₁的顶点分布在T₂每一条边异侧)
????T₁、T₂相交，返回真；
??else
????T₁、T₂不相交，返回假；
??end if
end if
3) 当T₁、T₂异面时，计算流程的伪代码为：
if (存在T₂边与T₁相交或存在T₁的边与T₂相交)
??判定T₁、T₂相交，返回真；
else
??T₁、T₂不相交，返回假；
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)