2. 电子科技大学 机械电子工程学院, 成都 611731
2. School of Mechatronics Engineering, University of Electronic Science and Technology of China, Chengdu 611731, China
三角面片对相交快速准确判断是STL(stereo lithography)模型Bool运算[1-3]和计算机虚拟仿真[4-6]等研究的关键技术。目前典型三角面片对相交判断算法有文[7-10]等研究,大部分算法以Möller算法[7]为基础,通过投影变换将空间三角面片对求交转换为两线段求交问题,邹益胜等[11]对三角面片异面求交算法作了改进,于海燕等[12]采用投影降维转换为二维平面求交问题。
总体上看,已有算法侧重于研究三角面片异面时的相交判断方法,大多基于Möller算法运用投影求交的思想做一些改进,对共面情况研究较少,由于计算机处理过程中存在误差,可能存在判断错误。
本文提出一种全面快速的三角面片相交判断算法,采用向量点积和叉积,针对三角面片共面和异面情况均给出具体判断方法,能够克服计算机处理误差导致判断错误,算法结构简单明了,精度、效率和全面性均有提高。
1 算法原理在STL格式模型中,三角面片顶点相对于实体外侧法向量按照逆时针排列。不失一般性,设拟相交判断的2个三角面片为T1和T2,T1的3个顶点分别为A1、B1和C1,所在平面为π1,法向量为n1; T2的3个顶点分别为A2、B2和C2,所在平面为π2,法向量为n2。
根据T2与π1的关系或T1与π2的关系可以初步将T1、T2的相交状态分为3种情况。
1) T2不与平面π1相交或T1不与平面π2相交,则T1、T2一定不相交。
2) T2在平面π1上或T1在平面π2上,则T1、T2共面,转化为二维平面三角面片相交问题。
3) T2与平面π1相交或T1与平面π2相交,则T1、T2异面,分别判断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) |
如果t1、t2和t3同号且都不为零,则三角面片T1和T2不相交。如图 1所示,T2的3个顶点均在π1平面上部,t1、t2和t3均大于0,T1和T2不相交;当t1、t2和t3均小于0,T2的3个顶点均在π1平面下部,T1和T2不相交。
1.2 共面情况
计算T1和T2的法向量叉积f:
$ \pmb{f} = {\pmb{n}_1} \times {\pmb{n}_2}. $ | (2) |
如果f=0,T1与T2是否平行(或共面)需要继续判断T2的任一顶点是否在π1上,即式(1) 中t1、t2和t3为0,则T1和T2共面,此时三角面片对相交判断是二维平面三角面片对相交判断问题,判定算法如下。
步骤1 分别判断A1、B1和C1是否在三角面片T2内, A2、B2和C2是否在三角面片T1内,如果以上判断结果有一个为真,则三角面片T1和T2相交;如果以上判断结果均为否,转步骤2。
判断三角面片所在平面内一点是否在三角面片内,算法如下。
求取三角面片每一条边向量在平面内的垂向量,再通过垂向量方向判断另一顶点与待检测点是否在边向量所在直线的同一侧。如图 2所示,判断A2是否在三角面片T1内,首先建立表达式:
$ \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) |
如果k1、k2、k3均为非负,则A2在三角形T1内;如果k1、k2、k3中存在负值,则A2不在T1内。
图 2a为k1>0,k2>0,k3 < 0,此时k3为负,所以A2在三角面片T1外部;图 2b为k1>0, k2>0, k3>0,此时k1、k2、k3均为非负,所以A2在三角面片T1内部;图 2c为k1>0,k2>0,k3=0, 此时k1、k2、k3均为非负,A2在三角面片T1内部,因k3=0,所以A2在T1的边C1A1上;图 2d为k1=0, k2>0, k3=0,此时k1、k2、k3均为非负,A2在三角面片T1内部,因k1=0且k3=0,所以A2在T1的顶点A1上。
当T1的3个顶点均沿法向量方向逆时针排列时,式(3) 中各对应算式中的后一项均为负,如在k1中A1C1·(A1B1×n1)的值为负(k2、k3中对应项亦如此),当T1三顶点均沿法向量方向顺时针排列,该项值为正。
步骤2 如果A1、B1和C1都不在三角面片T2内且A2、B2和C2也都不在三角面片T1内,此时如果T1、T2相交只有可能是图 3中所示情况。只需判断T2的3个顶点是否在T1每条边A1B1、B1C1、C1A1异侧,以及T1的3个顶点是否在T2每条边A2B2、B2C2、C2A2异侧。如果都满足,则T1、T2相交,否则不相交。
例如,判断T2三顶点A2、B2、C2是否在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) |
如果计算得h1、h2和h3不同时为正或不同时为负,则A2、B2、C2在A1B1异侧。
1.3 异面情况如果式(2) 中f的计算结果不为0,则三角面片T1和T2异面,分别判断线段A1B1、B1C1、C1A1是否与三角面片T2相交,以及线段A2B2、B2C2、C2A2和三角面片是否与T1相交,如果以上判断结果均为否,则三角面片T1和T2不相交;如果以上判断结果有一个为真,则三角面片T1和T2相交。其中线段与三角面片的相交判断是通过运用向量之间点积和叉积的特点来判断线段是否穿过三角面片而实现的,如图 4所示,判断T2的边A2B2是否与三角面片T1相交,建立表达式:
$ {\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时,线段A2B2与T1共面;否则A2B2与T1异面。以下从共面和异面2种情况展开论述。
1) 异面。由于A2B2与T1异面,首先计算(S1·S2),倘若结果为正,则A2B2在π1同侧,判定A2B2不与T1相交;否则A2、B2在π1异侧且A2和B2至少有一点不在平面π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) |
如果g1、g2和g3计算结果中存在小于0的情况,则线段A2B2与三角面片T1不相交;如果3个结果均为非负,则线段A2B2与三角面片T1相交。如图 4a所示,此时A2B2与T1相交,g1、g2、g3的计算结果均为非负;而A2、C2在π1异侧,但是线段A2C2不与T1相交,对应上述表达式必定存在小于0的情况。
2) 共面。如果A2B2与T1共面,首先运用前述方法判断A2、B2是否在T1内,若至少存在一点在T1内,则线段A2B2与T1相交;若A2、B2都不在T1内,只有2种情况:A2B2与T1不相交和A2B2与T1共面相交。此时如果A2B2与T1共面相交,T1中必定存在边与T2异面相交,由于T1、T2的每一条边都要作相交判断,所以当A2、B2都不在T1内,算法中可认定为不相交或不作处理,不影响T1、T2相交判定最终结果。如图 4b所示,A2、B2都不在T1内,但A2B2与T1共面相交,而在T1中A1C1、B1C1都与三角面片T2异面相交,而它们会在异面线段与三角面片的相交判断中被检测出来。
2 算法流程根据上述计算原理,本文算法流程如图 5所示。
根据算法原理中的方法可将算法的计算流程描述如下。
1) 计算T1各顶点与π1的关系及T2各顶点与π2的关系,排除不相交情况。总流程的伪代码为:
if (A1、B1和C1在π2同侧或A2、B2和C2在π1同侧)
T1、T2不相交,返回假;
else
if (n1与n2平行,且T2任一顶点在π1上)
判定T1、T2共面,goto(2);
else
判定T1、T2异面,goto(3);
end if
end if
2) 当T1、T2共面时,计算流程的伪代码为:
if (存在T1的顶点在T2内部或者存在T2的顶点在T1内部)
判定T1、T2相交,返回真;
else
if (T2的顶点分布在T1每一条边异侧且T1的顶点分布在T2每一条边异侧)
T1、T2相交,返回真;
else
T1、T2不相交,返回假;
end if
end if
3) 当T1、T2异面时,计算流程的伪代码为:
if (存在T2边与T1相交或存在T1的边与T2相交)
判定T1、T2相交,返回真;
else
T1、T2不相交,返回假;
end if
3 算法分析与测试计算量决定着算法运行速度,算法中有加减、乘除、比较、绝对值和赋值等运算,这几种运算运行时间视为相同[13],算法计算量可看成这几种运算总和。目前典型算法侧重于三角面片异面时相交判断,邹益胜等[11]算法在Möller[7]的基础上进行了改进,对比了各算法计算量,表 1给出异面情况时本文算法运算量与现有算法对比,从中可知,本文算法比其他算法的计算量要小很多。
目前典型算法主要是在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%;当三角面片异面相交时稍有降低,总体计算效率有所改善。
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) |