Research And Implementation Of Collision Detection Algorithm In Three-dimensional Game

It is quite challenging to detect collision between objects in domains of virtual reality, computer animation, computer graphics, computer game, etc. Its basic task is to identify whether a contact or penetration has happened in virtual environment, the reality and enhanced immersion of which depend largely on fast and exact collision detection. A huge number of objects with complicate geometries exist in such environment that collision detection often takes up a lot of storage space and processing time, so the efficiency of collision detection exerts a very great influence to real-time and authenticity of virtual environment.Two rigid object collision detection problems in three-dimensional games are researched in this paper, including collision detection between dynamic objects and static objects, and that between dynamic objects and dynamic objects. According to the existing collision detection algorithms, a corresponding solution is proposed for the two collision detections for three-dimensional games.(1) The general framework of collision detection algorithms is described and some classification and comparison are done as well. AABB hierarchical bounding volume is adopted during detailed testing phase, after optimizing its storage structure.(2) As for the first type of detection, an algorithm that combines Space subdivision algorithm with hierarchical bounding volume algorithm is proposed, identifying potential intersection with BSP space subdivision algorithm in the first detection phase, while AABB hierarchical bounding volume in the coming detailed testing phase.Moreover, surrounded by a ball-based approach is used to optimize the BSP tree construction.(3) While for the collision detection between dynamic objects and dynamic objects, an algorithm combining Projection Interval Ranking Method with hierarchical bounding volume Method is designed. In the first testing phase, AABB projection range ranking algorithm is used to identify potential intersection. And then, AABB hierarchical bounding volume is used in the detailed testing phase. Temporal and spatial correlation is introduced to the whole process of collision detection to accelerate collision detection.(4) Finally, the efficiency of the algorithm is proved by experimental results.