Large, Complex Scenes, Fast Collision Detection Technology

Collision detection has been researched in many fields such as robot motion planning and computer graphics for a long time. In recent years, with the rising of virtual reality and distributed interactive simulation, many researches focus on collision detection, and exact collision detection is very important to improve reality and enhance immersion for virtual environment, however, the complexity of virtual environment especially the large scale complex environment brings higher requirement to collision detection.This thesis makes a study of collision detection between rigid bodies in large scale complex environment, resolves the problem of collision detection in complex environment, and ensures the real time interactivity in the system; finally complete a rapid collision detection system--LargeCollide, which is based on hierarchical OBB algorithm. The main work in this thesis is below:1. Based on the intensive survey and comprehensive analyses of various approaches to collision detection, we select the most effective algorithm in such situation which is called hierarchical OBB algorithm as the core technique in LargeCollide system. However because the memory requirement in this algorithm is so huge that we can not afford, the author optimizes it and achieves better result. Moreover, a new and more accurate triangle-OBB test is used instead of OBB-OBB test to improve the efficiency of the system. Experiments show that the optimized algorithm not only can save half of the memory, but also can speed up the algorithm.2. Based on the scene coherence, the author chooses sweep and prune algorithm to further reduce the time in detailed collision detection. Because the complexity of sweep and prune algorithm is only O(n), it's extremely effective for solving complete pairwise collision detection problem, and just needs few time. Although it can't solve the penetration problem caused by fixed step, it can ensure that the primary collision detection can be completed in constant time. Experiments prove that this new system structure can speed up the process of collision detection in large scale complex environment. Because we use AABB in sweep and prune algorithm, LargeCollide system performs much better when the objects in environment are far apart.