Detecting collision of polytopes using a heuristic search for separating vectors

摘要

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 ·r i )r i , where r i =(q i -p i )/(q i -p i ). 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.