Deformable Body Collision Detection Algorithm

A rapid and robust collision detection algorithm plays an important role in many fields such as virtual reality, computer game and computer aid design. In recent years, collision detection has been a hot topic with the boom of virtual reality and distributed simulation technology.Compared with rigid object, the deformable object has the distinctive feature that the relative position of vertices comprising the object changes when the object moves. For rigid object, the data structures that most collision detection algorithms depend on end in the pre-processing phase. But for deformable object, the collision detection algorithm fit for rigid object can't apply to the deformable object. Because the relative displacement of vertices changes, the data structure applied to collision detection must be rebuilt or refit in real time.This paper has tried to make improvements from two aspects for the collision detection algorithm of deformable objects. First, improvement is made to the traditional AABB hierarchical bounding boxes by the compressive AABB bounding box, trying to optimize the traditional hierarchical bounding boxes from a space perspective. The direct result is that it can save a large amount of space and enhance the efficiency of collision detection dramatically. The second method proposes a new collision detection algorithm that combines bounding volume boxes method and space subdivision method. It can solve the collision detection problems between deformable objects. Compared with other collision detection algorithm, the algorithm this paper proposes not only has the advantage that it can save the storage space but also its time complexity is comparatively low. Besides, it can find not only the colliding elementary geometry element pairs but also the precise colliding points.