摘要
为了有效地提高凸面体之间的碰撞检测效率,提出一种凸多面体快速碰撞检测的投影分离算法.该算法通过判断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.
出处
《计算机辅助设计与图形学学报》
EI
CSCD
北大核心
2010年第4期639-646,共8页
Journal of Computer-Aided Design & Computer Graphics
基金
国家自然科学基金(50575031)
湘潭大学博士启动基金(09QDZ18)
关键词
凸多面体
碰撞检测
投影分离
polytope
collision detection
projection-separation
