Research On The Technology Of Collision Detection For Object In Virtual Environment

Collision Detection in Virtual Environment is a classic topic in research area of computer graphics, computer animation, robotics, computational geometry and computational visualization. The real-time and accurate collision detection is essential to improve the authenticity of the virtual environment and enhance the immersion virtual environment. Despite a lot of valuable and practical results at home and abroad, the problem of collision detection is also increasingly prominent with the emergence of new areas of the virtual reality and the improvement of the authenticity and real-time requirement. How to improve the collision detection algorithm efficiency and accuracy has always been a focus of the research. The most core issue is how to effectively improve the speed of collision detection in order to maintain the authenticity of the virtual environment.Giving a comprehensive analysis and research for all kinds of collision detection algorithms, the paper designs, implements and validates a group of new collision detection algorithms with good performance based on the characteristics and limitations of the existing algorithm. The main research works and contributions are as follows:1. A new object-oriented parallel collision detection algorithm is presented in the paper. The algorithm ensures uniqueness of collision response. When moving objects are much less than the stationary ones, the time complexity is O (n ) where n is the number of objects in virtual environments. Compared with other methods, this algorithm reduces the time complexity of the detection effectively and reasonably. The parallel idea is put forward to further speed up the detection speed. The algorithm has good versatility, well suitable for objects of various movement and updates status in real-time to complete the dynamic collision detection. It also ensures the autonomy of the simulation nodes and simulation control system's scalability.2. A collision detection algorithm based on bounding box tree is proposed in the paper. The collision detection speed is improved by optimizing the storage structure of AABB bounding box and creating a certain priority policy on the bounding box tree, and the time-out counter helps avoid the missed detection. The first top-down search algorithm can give accurate calculation of collision detection, and provide collision site, the distance between objects, speed and other information. And the second bottom-up search algorithm is mainly applied to the objects which have collisions last times for the purpose of quickly determining whether or not the collision happened and to a large extent avoiding unnecessary testing.3. A new algorithm dividing a polyhedron into tetrahedrons is proposed in the paper. A parallel idea is proposed to implement the parallel collision detection algorithm based on the dividing algorithm. Thus the two complex polyhedron's collision detection can be turned into parallel collision detection between the tetrahedron. Ensuring the accuracy, collision detection algorithm meets the real-time requirements and solves the problem of general collision detection algorithm which is only applicable to the convex polyhedron. The paper completes the parallel collision detection algorithm based on bounding box tree.4. A new parallel collision detection algorithm based on PSO(Particle Swarm Optimization) is proposed in the paper. The collision detection problem is transformed to the optimization problems of the space formed by the number of characteristics of the two models. Using the intelligent search features of the PSO algorithm, the search process of the local minimum characteristics is completed during collision detection. The optimization model is fully parallel based on dividing polyhedron algorithm. Then the parallel PSO collision detection can be completed. The parallel collision detection algorithm based on PSO can greatly improve efficiency. The algorithm inherits the advantage of general collision detection algorithm based on the intersection and breaks their limitation. It is applied to the collision detection of the arbitrary polyhedron ensuring the efficiency. With the application of parallel technology, the detection speed can be improved by adjusting the number of nodes.5. A new parallel collision detection algorithm based on a genetic algorithm is proposed, which turns polyhedron intersection problem into linear programming with constraints problem. Evolutionary process is parallel on different computing nodes. After the treatment of constraints, the exchange of excellent gene is implemented through the exchange of information among certain populations, which solve the problem of polyhedron intersection and implement collision detection algorithm. Compared with traditional methods, the parallel collision detection algorithm based on a genetic algorithm enhances the speed of collision detection with high precision. Meanwhile, it can be applied to the real-time dynamic collision detection of arbitrary polyhedron.Experiments and related applications show that the object-oriented collision detection algorithm proposed in the paper has good versatility. It ensures the autonomy of each simulation node and system's scalability. Other types of collision detection algorithms proposed in this paper have high accuracy and speed, which fit for collision detection of arbitrary polyhedron and meet the technical requirements of collision detection in virtual environment.