Research On Collision Detection Algorithm Based On Optimization Model

Recent years, the collision detection between geometric models has became one of hot topics in many areas, such as cloth simulation, the motion planning of robotics, computation geometry, computer simulation, Virtual Reality(VR), Computer Graphics, Computer Animation, Virtual Surgery, CAD\CAM, and so on. Collision detection is a very key technology of the virtual reality field, also is a bottleneck of the virtual reality. Virtual reality technology is usually refers to that using the new interactive devices such as data glove to construct a kind of computer software and hardware environment which the users can experience the virtual state. Users wish that the feeling of the virtual objects of the virtual world is existent really. We not only want to see the virtual objects of the VR environment and their behaviors really, and we desire for the kinds of direct interaction with the virtual world to be personally on the scene naturally as far as possible. In order to ensure the real sense of the virtual reality, objects of the virtual reality must at first be impenetrable. Users should truly feel that the collision is existent and could operate appropriate responses real-time when they come into contact with the virtual objects and make the corresponding operation to the objects, in other words, the collisions should be detected timely and accurately. Consequently, collision detection is that the base if the interaction between the dynamic objects and the static objects, or the dynamic objects and dynamic objects, in the mass and complicated virtual environment. Real-time and accurate collision detection play an important role to improve the facticity and to enhance the immersive of the virtual simulation scene.This paper have done research and discussion to the collision detection arithmetic in the mass and complicated virtual environment, take aim at improving the real-time and accuracy of collision detection, by combining with the optimizing models such as particle swarm optimization(PSO), ant colony optimization(ACO), genetic algorithm(GA), etc. As a result to achieve the Real-time simulation by clipping collision detection between objects in the large-scale complex scene. Thus the collision detection time and response time of deformable objects would be cut down while the realism and immersion would be increased. The research of this paper would solve the bottleneck problem which is needed to be resolved urgently in virtual reality technology, and it will provide strong technical support for the rapid development of virtual reality technology.The paper mainly includes the following aspects:Firstly, this paper introduces the principle and current situation, analyzes the significance and the application prospects, of collision detection. And the paper compares the current collision detection algorithm comprehensively.Secondly, this paper researches on how to accelerate the hierarchical bounding box method in the rough collision detection phase in order to get rid of the basic geometric elements that impossible to collision. The changing of collision detection objects’topology shape and motion state (such as static or moving, movement velocity and direction) would lead the update of hierarchies bounding volume tree to be needed. Using the genetic algorithm (GA) to substitute approximate method or hill climbing method which is the traditional method, in order to lower the cost of the memory space of the update pf hierarchies bounding volume tree, improve the speed of the bounding box tree’s updating, thereby improve the efficiency of collision detection algorithm effectively.Once more, the paper introduces and analyses the constructor method and the overlapping test method to axis-aligned bounding box (AABB). According to the advantage that the overlapping test of AABB bounding box is relatively simple, the perfect balance of the binary tree of AAABB hierarchical bounding volumes would built by top-down approach. Based on the spatial locality of the collision behavior of the moving objects in the virtual environment, search on the AABB bounding box tree to find out the nodes which is needed to be update after the objects bad changed quickly by the harmonious particle swarm optimization (HPSO) model, according to do that, the updating cost of the bounding box tree in the virtual simulation system would be reduced, and then the efficiency of the collision detection algorithm would be enhanced.At last, as the implementation of above method, this paper builds a simulation system to detect the collision between the complex and transformable objects, using the accurate graphic API and the intuitional programming environment offered by OpenGL. The simulation testing scene which is in order to imitate the collision detection between cars and bowling balls achieves accurate and fast collision detection, the performance and characteristic of the above algorithms are analysed, firstly the feasibility of the improved collision detection algorithm based on the optimization model come up in this paper is testified, furthermore, the efficiency and accuracy of collision detection algorithm are enhanced.