A Study On The Collision Detection In Complex Virtual Environment

Over the past 20 years, the computer graphics has a considerable development, three-dimensional computer graphics is widely applied in various fields, on the other hand, the deepening of graphics applications in these areas also gives higher requirement. Realistic real-time has become a focus of people's attention.Collision detection between objects in virtual environment is a realistic and challenging problem in virtual-reality, the computer animation, three-dimensional games, virtual assembly applications. Its basic task is to identify whether two or more geometry objects are in contact, and make the collision response. To improve the immersion and realism in a virtual environment, quick collision detection plays an important role. However, due to there are a large number of objects and the complexity of the geometry in the virtual environment, process of the collision detection often takes a lot of storage space and processing time, the efficiency of collision detection algorithm constrained the authenticity of the virtual scene.This paper proposes some improvement methods to solve the problems which exist in collision detection algorithms after comprehensive understanding and analyzing each kind of collision detection algorithms:1. This paper gives the general framework of collision detection algorithm in open-source graphics engine, then by analyzing the exist problem, this paper proposes a method of deal with collision detection among moving objects and collision detection between objects to static scene separately according to their features.2. This paper propose an optimization algorithm for multi-object collision detection based on kd-tree. We use quick sort to projection interval in the preliminary test stage to find intersecting objects. Then, we use the optimized kd-tree structure in detailed testing stage. We discussed and proposed improved method to construction strategy, partition plane selecting, termination condition, update strategy of kd-tree for collision detection.3. By analyzing the temporal correlation of collision detection, this paper propose a strategy of acceleration which reduce the number of intersection tests while traversal bounding volume tree by recording intersection case last time sampling. This method is especially for collision detection between moving objects and static scene. 4. Finally, we analyzed and tested the efficiency of the algorithm.