Detecting collision of polytopes using a heuristic search for separating vectors

Abstract

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. 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 poly-hedra with a large number of vertices, HS-jump delivers the maximum efficiency if the objects are on average not very elongated.