标题：Detecting collision of polytopes using a heuristic search for separating vectors
作者：Li X.-Q.; Meng X.-X.; Wang J.Y.; Wang W.-P.; Chung K.; Yiu S.M.
作者机构：[Li, X.-Q] Coll. of Comp. Sci. and Technol., Shandong Univ., Ji'nan 250100, China;[ Meng, X.-X] Coll. of Comp. Sci. and Technol., Shandong Univ., Ji'n 更多
通讯作者地址：[Li, X.-Q] Coll. of Comp. Sci. and Technol., Shandong Univ., Ji'nan 250100, China;
来源：Jisuanji Xuebao/Chinese Journal of Computers
关键词：Collision detection; Computational geometry; Computer graphics; Virtual reality
摘要：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.