基于启发式搜索分离向量的凸多面体碰撞检测

摘要

碰撞检测是计算机模拟物理过程的基础,在计算机图形学、CAD/CAM、虚拟现实和机器人等领域有着广泛的应用.该文给出了一个新的用于凸多面体碰撞检测的算法--HP-jump.HP-jump建立了一个有效的碰撞检测模型用于报告物体的碰撞, 同时提供了一个快速的启发式的策略用于搜索两个凸多面体的分离向量.该算法是利用凸多面体的层次表示来搜索支撑顶点对,用平衡二叉树来记录球面凸多边形的顶点,同时还利用了时间、空间相关性,这些都加速了算法的执行.该文的最后给出了HP-jump与GJK,I-COLLIDE算法的比较.%The collision detection problem is to determine whether two moving objects collide or not at any moment. It is fundamental to computer simulation of a physical environment, and has applications in computer graphics, CAD/CAM, virtual reality, and robotics. This paper proposes a new method, called HS-jump, for collision detection for polytopes. HS-jump combines an efficient scheme to report collision for two colliding polytopes and a fast heuristic strategy to search for a separating vector of two separated polytopes. A separating vector is the normal vector of a separating plane of two disjoint polytopes. Suppose an ordered pair (p,q) is a supporting vertex pair of two polytopes P and Q with respect to a vector S, if it satisfies the separating condition S*(q-p)>0, then P and Q do not collide and S is called a separating vector. The algorithm firstly sets a nonzero vector as the candidate separating vector S and computes the supporting vertex pair (p,q). If the separating condition is satisfied, then P and Q are disjoint and the algorithm terminates. Otherwise the new candidate separating vector S is obtained using the heuristic formula Si+1=Si-2(Si*ri)ri, where ri=(qi-pi)/(qi-pi). This step is repeated until the algorithm finds the vector S which satisfies the separating condition or reports that P and Q collide by noting that the spherical convex polygon formed from the supporting vertex pairs is empty. To speed up the implementation of the algorithm, the hierarchical representation of a polytope is used to compute the supporting vertex pair, and a balanced binary tree is used to store the vertices of the spherical convex polygon, and between-frame coherence is exploited . Due to the particular nature of the search scheme used, HS-jump becomes more efficient when the convex polyhedra are more spherically shaped. Hence, in the case of applying HS-jump to convex polyhedra with a large number of vertices, HS-jump delivers the maximum efficiency if the objects are on average not very elongated.