Research On Collision Detection Algorithm In 3D Space

Collision detection has been researched in many fields such as robot motion planning and computer graphics for a long time. In recent years, with the rising of virtual reality and distributed interactive simulation, many researches focus on collision detection,especially for the flexible objects . Efficient and Exact collision detection is very important to improve reality and enhance immersion for virtual environment. The complexity and real-time of virtual environment bring new requirement to collision detection.By analyzing the domestic and overseas related works, the advantages and disadvantages of various collision detection algorithms and their application environment are discussed systematically. Through a lot of research on the collision detection algorithm of bounding box, an improved collision detection algorithm based on AABB (Axis-Aligned Bounding Boxes) has been designed, and the way to construct a hierarchical bounding-box, which is very close to the object, by continuous partition of the object is presented. The object's movement in virtual environment can be divided into translational motion and rotation, by analyzing and utilizing the basic nature of Axis-Aligned Bounding Boxes, an updating method to hierarchical bounding-box tree has been used in the experiment. How to deal with the object's deformation is an research focus in collision detection, based on the analyzing of several deformation situations, the corresponding solutions are designed respectively, as to deal with the updating problems of hierarchical bounding-box tree when the object is in the situation of proportional zoom and extrusion deformation as well as topology deformation.Experimental results show that, compared to the algorithm of hierarchical bounding-sphere, the method improves the performance of constructing hierarchical bounding-box tree and the exact collision detection in the translational motion. As for the rotation, the method performs better than the algorithm of hierarchical bounding-sphere in the exact collision detection, but worse than it in constructing hierarchical bounding-box tree, which is where can be improved of this algorithm.