Fast Intersection Algorithm between Spatial Triangle Pairs
-
摘要: 为提高干涉检测的效率,提出了一种快速的三角形对相交检测算法.该算法基于三角形对的各边进行 精确相交计算的原理,利用三角形边向量之间的线性相关性、线段的投影特性以及计算的中间结果,提高了三角 形对相交检测的效率.采用多种样本对Guigue、Shen、M昳ller、Tropp等典型算法及本文算法的精度和效率进行 测试.结果表明:本文算法与典型算法的检测精度相同,在三角形对样本相交率大于0.2的场合下,本文算法比 典型算法的检测速度快3.5%以上,并且检测速度优势随相交率和检测规模的增加而增加.Abstract: 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 Guigue, Shen, Mller, 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.
-
Key words:
- triangle /
- intersection test /
- linear dependence /
- collision detection /
- projection character
点击查看大图
计量
- 文章访问数: 1074
- HTML全文浏览量: 65
- PDF下载量: 509
- 被引次数: 0