Research On Fast Collision Detection Algorithm Based On Particle Swarm And Ant Colony

Collision detection in computer graphics, virtual reality, computer games, animation, computer aided design, robotics and virtual manufacturing, etc are classic and the key problem, for many years have been more attention. At present, most of the virtual objects of geometric model is composed of tens of thousands of basic geometrical elements. Due to the complexity of the geometry of the virtual environment, making the collision detection increased greatly improve the computational complexity of complicated scene interactive consumes vast quantities of computer resources, therefore, collision detection in virtual conditions, often become a bottleneck. How to design a can meet the real-time, accuracy, the universality of efficient collision detection algorithm, become the problem to be solved.In the modern intelligent bionic algorithm for rapid development, the development of artificial intelligence optimization algorithm, intelligent optimization algorithm to researchers with unprecedented opportunities and challenges. Many intelligent algorithms, such as simulated annealing, genetic algorithm, ant colony optimization, particle swarm optimization, algorithms and other fish begin to apply to the collision detection algorithm, but the ant colony optimization, particle swarm optimization technology to the collision detection or not a sound approach.Virtual reality system for collision detection performance requirements of high interactivity requirements is also high, a detailed study of this thesis intelligent optimization algorithm superior technology, combined with artificial intelligence research of random collision detection algorithm. Swarm Intelligence in the classical PSO and the introduction of the improved ant colony algorithm in parallel random collision detection algorithm. Most of this paper include the following contents:(1) The particle swarm-based collision detection algorithm:particle swarm algorithm combines the advantages and the bounding box, the first structural level bounding box tree, first determine whether the intersection of the root of the object, if the objects do not intersect the collision, if the object Intersection space, the search algorithm using particle swarm leaf node of the tree traversal, if the leaf nodes in a cross walk, the objects collide. This algorithm has played a hierarchical bounding box and the advantages of PSO. Further improve the efficiency of collision detection.(2) based on parallel collision detection algorithm ant:ant colony optimization algorithm and the random combination of collision detection, the algorithm uses a parallel thought to accelerate the speed of collision detection in the initial testing phase, we quickly ruled out by surrounding trees Disjoint objects, and then parallel ant colony algorithm is applied to the collision detection, the basic unit of the objects and leaves as "ants", and then to traverse the search. The experiment shows this algorithm to further accelerate the efficiency of collision detection. Reduces the time complexity.