The Research On Collision Detection Algorithm Based On Bounding Volume And Particle Swarm Optimization

Collision detection has been researched in many fields, such as robotics, computer graphics, computer animation, computational geometry, and CAD/CAM. The recently research indicate that the requirements for real-time of collision detection have become higher than before, because the perceived quality of most interactive 3D applications does not depend on exact simulation, but rather on real-time response to collisions.After giving a comprehensive understanding and intensive analysis for all kinds of algorithms of collision detection, we try to consider the collision detection problem as an optimization search problem, and present an efficient algorithm for detecting collisions which is a combination of bounding volume hierarchies (BVHs), particle swarm optimization (PSO) and stochastic collision detection algorithm, aiming at improving real-time of collision detection.Thesis research stochastic collision detection algorithm and accelerate the searching process by PSO. Then we introduce PSO which is a classical algorithm in swarm intelligence algorithms to collision detection domain, and consider the OBB bounding volume of triangles as a particle to detecting collisions between complex models.Thesis present an efficient algorithm for detecting collisions which is a combination of BVHs and stochastic method based on PSO. Thesis first reduce the search space by using the technique of OBB bounding volume, then we obtain the interference triangles by using stochastic method based on PSO.At last, Thesis give an efficiency evaluation about the algorithm and find it is a reasonable choice for complex models.