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

文中提出一种基于包围盒和空间分解的碰撞检测算法，用以解决软体的碰撞检测。算法使用AABB包围盒做初步检测，确定可能发生碰撞的物体。再根据包围盒的重叠情况缩小可能发生碰撞的区域，利用哈希表作为数据储存结构进行空间分解，将物体包围盒重叠区域的基本几何元素的空间网格映射到哈希表中，将碰撞区域缩小到基本几何元素，最后用基元碰撞检测找出具体碰撞点。由于前期AABB包围盒的处理减少了空间分解阶段需要映射的基本几何元素数量，该算法具有较高的运算速度。

A Collision Detection Algorithm Based on Bounding Box and Spatial Subdivision

A collision detection algorithm based on the bounding volume and spatial subdivision for the collision detection of deformable objects is proposed. The algorithm does preliminary detection with AABB bounding volume boxes to find the objects which may be colli- ded. Then according to the area of overlap of the bounding box reduce the possible collision, use hash table as a data storage structure for spatial decomposition, the spatial grid of basic geometric elements in the object bounding box overlap area is mapped to a hash table, re- ducing the collision area to basic geometric elements, with primitive collision detection to find out specific collision point finally. Owing to the detection of AABB to reduce the number of object primitives, so this algorithm has a better performance.