Parallel Collision Detection Algorithm Research Based On CUDA

Collision detection is one of the key problems in compute graphics simulation, its basic task is to determine whether the collisions happened between objects in virtual scene and to achieve the collision respnse, to ensure the authenticity of the scene. In the past few decades, researchers have proposed many excellent collision detection algorithms, these algorithms have solved the collision problems in virtual enviroment and have a certain real-time. However, with the increasing demands of authenticity of virtual scene, the real-time of these algorithms which achieved on single processor is reduced because of the increased scene scale and model complexity, thus, the core issue of current research is how to improve the speed of collision detection. In recent years, the computing capacity of GPU makes a significant leap forward because of the rapid development of graphics processors, using the architecture which has a large number of programmable stream processors allows the computing capacity of GPU gets a hundred times more than CPU. The CUDA which NVIDIA launched a general purpose computing platform allows the powerful parallel computing capacity of GPU to solve the general purpose computing works besides graphics processing. CUDA platform has brought new ideas for researches of collision detection algorithms, based on analyzing the existing algorithms, this paper proposed a CUDA-based parallel collision detection algorithm, two aspects of hierarchical bounding volumes has been improved as follow:1. By analyzing the serial algorithm which uses bottom-up method to establish hierarchical bounding volumes tree, we attributed the creation of hierarchical bounding volumes tree as a CUDA-fitted data parallel problem by searching the parallel problems, and proposed the corresponding parallel algorithm.2. Proposed using multithreads to parallelly traverse hierarchy tree to avoid the situation which serial algorithm needs two trees mutual traverse, and implemented the algorithm on CUDA by using simulated stack to traverse binary tree.The result shows that CUDA-based parallel collision detection algorithm can effectively improve the speed of collision detection and better meet the needs of real-time.