基于包围盒与空间分解的碰撞检测算法

本文提出了一种基于包围盒方法与空间分解方法相结合的碰撞检测算法,用于解决变形体的碰撞检测问题。该算法首先用包围盒来快速判断物体之间是否相交,如果相交则进一步用空间分解法来定位相交的区域,在此阶段用哈希表的数据结构来保存物体的几何信息。与其他碰撞检测算法相比较,本算法不仅能够较大地节省空间,而且时间复杂度也比较低。除此之外,本算法不仅能够找出发生碰撞的基本几何元素对,而且还能够精确地找出碰撞点。

The Collision Detection Algorithm Based on Combination of Buonding Volumes and Space Division

This paper proposes a new collision detection algorithm that combines bounding volume boxes method and space division method. It can solve the collision detection problems between deformable objects. First,the algorithm uses bounding volume boxes to determine if objects are intersecting. If they do,if further uses space division to locate the intersection areas and it use the data structure called hash table to'store the geometry information of objects on this phase. Comparing to other collision detection algorithm,the algorithm this paper proposes not only has the advan- tage that it can save the storage space well but also its time compleaity is comparatively low. Besides,it can find not ouly the colloding elementary geometry entity pairs but also the precise colliding points.