标题: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, XQ(liyou@jn-public.sd.cninfo.net)
通讯作者地址:[Li, X.-Q] Coll. of Comp. Sci. and Technol., Shandong Univ., Ji'nan 250100, China;
来源:Jisuanji Xuebao/Chinese Journal of Computers
出版年:2003
卷:26
期:7
页码:837-847
关键词: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.
收录类别:SCOPUS;SCOPUS
Scopus被引频次:8
资源类型:期刊论文
原文链接:https://www.scopus.com/inward/record.uri?eid=2-s2.0-0142028668&partnerID=40&md5=e9288efd9cd8afa2e0e68a0bb8f6835c
TOP