摘要
为提高碰撞检测的响应速度,提出了一种基于Ayellet算法的改进算法。该算法从代数的角度出发,首先快速排除掉三角形对不相交或共面的两种情况,然后分别计算一个三角形与另一个三角形所在平面的相交线段,最后检测这两条线段是否有公共点。如果有公共点则三角形对相交,反之则不相交。该算法也可以应用于类似的问题,如矩形对的相交测试、多边形对的相交测试。实验结果表明,该算法的速度优于改进前的算法。
To improve the response speed of collision detection,an improved algorithm based on Ayellet algorithm is proposed.The algorithm from the algebraic point of view,firstly fast rejects the possibilities of the disjointed or coplanar triangles,secondly separately calculates the intersecting line segments between one triangle and the plane defined by the other triangle,finally detects if there are the public points between the two segments.If any the triangles are intersection,conversely do not intersect.This algorithm can also be applied to similar problems,such as rectangle to rectangle intersection test,and polygon to polygon intersection test.Experiments show that the proposed algorithm is faster than Ayellet algorithm.
出处
《计算机工程与设计》
CSCD
北大核心
2010年第4期869-871,875,共4页
Computer Engineering and Design
关键词
碰撞检测
三角形对
相交测试
矩形对
多边形对
collision detection triangle to triangle intersection test rectangle to rectangle polygon to polygon
