Research On Collision Detection Algorithm Based On AABB Bounding Volume

Collision detection has been researched in many fields, such as computational geometry, computer graphics and robot motion planning. In recent years, collision detection has been a hot topic with the boom of virtual reality and distributed simulation technology. Fast and exact collision detection is very important to improve reality and enhance immersion for virtual environment.Bounding volume hierarchy provides an effective method to resolve the time complexity in collision detection. The idea behind it is to approximate the object with a simpler bounding volume that is a little bigger than the object. In building hierarchies on object, one can obtain increasingly more accurate approximations of the objects. So during traversing bounding volume hierarchy, it speeds up collision detection by prune away primitives pairs, which will not intersect clearly though rapid intersection test between bounding volumes and just deal with those bounding volume is intersected. The choice of bounding volume is the basic and key problem of this approach. This paper analyzes different bounding volumes and correlative algorithms. Because AABB parallels coordinate, we choose it to approximate the object. Analyzing the collision detection algorithm based on AABB, we found that the speed of algorithm can be affected by three factors: intersection test between bounding volumes, traversing of AABB tree and intersection test between primitives. This paper summarizes the methods about three factors and provides improvement methods from temporal-spacial coherence and memory space.The implementation speed of collision detection algorithm is affected by intersection test between AABB bounding volumes directly. Bounding volume sorting is an effective method to estimate the intersection between AABB. We don't adopt of insertion sort algorithm but the diminishing increment sort algorithm to sort AABBs' orthogonal projections onto the axes of the coordinate system. Collision is a local behavior, i.e., an object can only collide with objects in its proximity and is hardly affected by objects far away from where the object is. But the orthogonal projections of two removed objects can overlap on one axis possibly, in order to overcome this, during the sorting procedure each axis is cut into a series of segments containing the (nearly) same number of projection intervals. This will reduce the computational time of collision detection algorithm, and speeds up the global search procedure. Collision detection algorithm based on AABB tree is improved from a space perspective in local search procedure. From the constructing process of AABB tree, the amount of byte of AABB bounding-volume for internal node is reduced. We wipe the bounding-volume out from leaf nodes structure based on a fast triangle-triangle intersection test algorithm, and then wipe the leaf nodes out. We optimize the storage of AABB bounding-volume and leaf node at the same time. The direct result is that it can save a large amount of space and speed up the algorithm.