Research And Implementation Of Collision Detection Algorithms Based On Mixed Bounding Box

Currently,3D models have been widely used in robot technology, computer graphics,animation, computer games, virtual reality simulation and other areas. Collision detectionbetween 3D objects has become an integral part on these areas. As the development of virtualreality technology, the scene simulation is becoming more and more complicated. Accordingly,when dealing with such kind of larger and more complex data sets associated with thecollision detection, the data structures and algorithms are becoming more complex. As thecore technology, the research of collision detection is the most important. Therefore,improving the efficiency of collision detection algorithm have very great significance.Bounding Volume Hierarchies(BVH) has been widely used as a well-acknowledgedcollision detection method. The basic thought of bounding box method is to substitutecomplex geometry with simple geometry. It first conducts rough detection on the boundingboxes of object because geometries are likely to intersect with each other when boundingboxes intersect with each other, so that large quantities of geometries that are unlikely tointersect with other will be ruled out. Bounding boxes are mainly as follows: Axis-AlignedBounding Box(AABB), Sphere, Oriented Bounding Box(OBB), Fixed Directions Hull(FDH), and k-dop bounding box. The several kinds of bounding box method mentionedabove have their advantages and disadvantages. Sphere is loose, but the overlap test is fastand it is easy to update. AABB is close, but the overlap test and update speed is slower thansphere. In real-time and tightness the OBB detection performance is the best. In this paper,based on a comprehensive understanding of the various algorithms, I would focus on OBBcollision detection, and optimize the OBB-based collision detection library RAPID. Theresearch and discussion are shown as follows:(1) Combining with the advantages of both AABB and OBB, we modify the structure ofAABB bounding box to make it easy to construct and update, and then the efficiency ofcollision detection is improved.(2) Based on the RAPID algorithm which is a BVH tree algorithm based on OBB, thispaper proposes a new collision detection algorithm based on maxed bounding box. First, thispaper use the modified AABB as the top layer of the hierarchical bounding tree to remove thedisjoint objects quickly. Then the overlapped objects will be deliver to the lower layer for theOBB test. the AABB is stored by the linked list to reduce the number of the OBB test.(3) The triangle-triangle intersection in RAPID is use Separation axis test, the calculationis very large.Here we use the method of triangle–triangle intersection test based OBBcollision detection. By recycling computation results from the OBB test, we can make thetriangle test more efficient than other conventional methods that start the triangle intersectiontest from the scratch.Finally, this paper use VS2010 and Open GL to build a simulation system. For the goal ofcollision detection time, this paper design same scenarios to verify the algorithm.Experimental data show that compare with RAPID, the detection efficiency of the optimizedalgorithm has obvious advantages.