The Research Of Collision Detection For Deformable Objects In Virtual Environment

Fast and accurate collision detection of objects in the virtual environment is an important foundation to enhance the realism of the virtual environment. In recent years, with the continuous development of computer graphics, virtual reality scenes are more and more complex, and the requirements of realistic sense in virtual interaction are also increasing. Therefore, precise and efficient collision detection algorithms have become the major points of study in computer graphics.Compared with collision detection of rigid body, collision detection of soft body has many different aspects. While soft objects are varying, the relative position between the component objects’vertices occur deformation. That makes the algorithm of collision detection in rigid object can not directly be applied to soft objects. The data structure of collision detection algorithm for soft objects must be real-time re-build or update. The bounding box can effectively and rapidly exclude objects that have not a collision in the scene, but the accuracy of complex objects is not satisfactory. Spatial decomposition method of uniform grid can better handle the problem of collision detection of soft objects, but the overhead for complex scenes is too large.This paper reviews the present situation of research on the collision detection problem, and provides the relevant analysis. Based on bounding volume boxes and space decomposition method, problems of software object collision detection were studied:1. The paper analysis the two methods about hierarchical bounding box algorithm and space decomposition method of entity space collision detection. Hierarchical bounding box algorithm can effectively solve the collision detection problem of rigid body, but for software object collision detection, Bounding Volume with high accuracy may have problems in the update stage after deformation. The space decomposition method is very effective for collision detection of deformable objects, and can effectively solve the self-collision problem. But for the scene which contains a large number of basic geometric elements, the algorithm will consume excessive resources.2. This paper proposes out a new algorithm, the algorithm is AABB bounding box combined with uniform grid space decomposition, using hash table as storage structure. Use of bounding box can ascertain the possible collision between a pair of objects rapidly, and make act the AABB bounding box on two objects overlap can filter out the basic set of overlap area in bounding box element. Decomposition phase in the following space is only to the selected elements make the basic set of uniform grid map, this article referred to as the local map; find out the elements for the basic set of collision. Finally we can use this element to find collision point for basic collection. The algorithm for different object collisions between maximum limit reduces the spatial decomposition stage need to network the basic set of map elements in quantity, so as to greatly improve the efficiency of algorithm.3. The research analysis scheme selection about the new algorithm to update the spatial data structure. According to the characteristics of the objects in the scene can choose to update or rebuild the data structure, the spatial data structure is updated for target, can improve the computing efficiency of the algorithm.