快速空间三角形对相交检测算法  

Fast Intersection Algorithm between Spatial Triangle Pairs

作　　者：邹益胜[1,2] 丁国富[2] 何邕[2] 

机构地区：[1]西南交通大学牵引动力国家重点实验室,四川成都610031 [2]西南交通大学机械工程学院,四川成都610031

出　　处：《西南交通大学学报》2011年第6期984-988,共5页Journal of Southwest Jiaotong University

基　　金：国家自然科学基金资助项目(50975240);四川省青年基金资助项目(09ZQ026-003)

摘　　要：为提高干涉检测的效率,提出了一种快速的三角形对相交检测算法.该算法基于三角形对的各边进行精确相交计算的原理,利用三角形边向量之间的线性相关性、线段的投影特性以及计算的中间结果,提高了三角形对相交检测的效率.采用多种样本对Guigue、Shen、Mller、Tropp等典型算法及本文算法的精度和效率进行测试.结果表明:本文算法与典型算法的检测精度相同,在三角形对样本相交率大于0.2的场合下,本文算法比典型算法的检测速度快3.5%以上,并且检测速度优势随相交率和检测规模的增加而增加.To improve the collision detection efficiency, a fast triangle-triangle intersection detection algorithm was proposed, which is based on the principle of accurate intersection calculation between edges of different triangles. In the algorithm, the linear dependence of edge vectors of triangles, projection character of segment, and intermediate calculation results are used to improve the performance of intersection detection. Many types of samples were used to test the accuracy and efficiency of the proposed algorithm in comparison with the typical algorithms proposed by Guiguc, Shen, M6ller, and Tropp. The experimental results show that the detection precision of the proposed algorithm was the same as the typical algorithms, but its detection speed of the former was over 3.5% faster than them in the case that triangles intersection rate was greater than 0.2, and the performance in detection speed increased with the intersection rate and the amounts of triangles increasing.

关 键 词：三角形 相交检测 线性相关 碰撞检测 投影特性 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]