凸多面体碰撞检测的棱线投影分离算法

A Collision Detection Algorithm between Convex Polyhedrons Based on Projection of Edges

针对凸多面体碰撞检测问题,以直线投影法为基础对分离面投影法进行改进,提出一种采用棱线投影分离的凸多面体实时精确碰撞检测算法.首先分析了凸多面体各种相对位置关系并提出了投影分离线的概念,针对凸多面体的各种分离情况证明投影分离线的存在;其次选取凸多面体相向面上的棱集构造准投影分离线,通过沿着准投影分离线方向投影可将3D凸多面体碰撞检测降维为2D凸多边形的碰撞检测问题;最后将分离投影的思想延用至为2D凸多边形的碰撞检测,再次将2D问题降维为1D问题.算法分析和实验结果表明,该算法对于凸多面体碰撞检测具有较高的响应速度和检测精度.

This paper presents a fast and accurate collision detection algorithm for convex polyhedrons, which employs the method of projection-separating edges based on linear projection. This algorithm improves the algorithm of projection-separating planes. First, this paper proposes the concept of projection-separating lines, and proves the existence of the separating lines in any separated condition. Second, the quasi projection-separating lines set is created from the opposite surfaces on convex polyhedrons, then the problem of the collision detection between 3D convex polyhedron is converted to the collision detection between 2D convex polygons by the projection of the lines; Third, the projection method has been applied to convex polygons and 2D problem is converted to 1D problem. The experimental results show that the proposed algorithm has high detection accuracy and response speed.