凸多面体快速碰撞检测的投影分离算法  

A Fast Projection-Separation Approach for Collision Detection between Polytopes

作　　者：黎自强[1,2] 

机构地区：[1]大连理工大学计算机科学与工程系,大连116024 [2]湘潭大学信息工程学院,湘潭411105

出　　处：《计算机辅助设计与图形学学报》2010年第4期639-646,共8页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家自然科学基金(50575031);湘潭大学博士启动基金(09QDZ18)

摘　　要：为了有效地提高凸面体之间的碰撞检测效率,提出一种凸多面体快速碰撞检测的投影分离算法.该算法通过判断2个凸多面体在中心线上的正投影不相交,或者分别构造它们的准投影分离面集合,并从这2个集合中找到一个投影分离面,来判断2个凸多面体分离;否则,判断为相交.对于2个准投影分离面集合,依次交替地判断它们的每一个面是投影分离面还是相交面,以加快2个凸多面体相交检测.计算复杂度分析和数值实验表明:该算法平均检测效率高于其他检测算法.In order to improve the efficiency of the collision detection for two convex polytopes, this paper proposes a fast projection-separation approach. It respectively constructs quasi projectionseparation facet sets of two convex polytopes while their orthogonal projection on the centerline overlap mutually. Afterward it judges the separation of two convex polytopes by confirming non-overlap in orthographic projection on the centerline or by finding out a projection separation facet from two quasi projection-separation facet sets, otherwise a collision is judged. This approach speeds up the intersecting detection by orderly judging alternately whether every facet of two quasi projectionseparation facet sets is projection-separation facet or intersecting one. Complexity analysis and numeric experiments show that its average detection efficiency is superior to existing algorithms.

关 键 词：凸多面体 碰撞检测 投影分离 

分 类 号：TP242.2[自动化与计算机技术—检测技术与自动化装置]