Research On Collision Detection Algorithm Based On GPU Parallel Speedup

Collision detection in computer graphics mainly refers to two or more objects in a virtual scene occupies the same position at the same time. Since the advent of computers, the collision detection has attracted attention and study. With the development of computer technology, people against the reality of virtual scene is more and more high, and collision detection in virtual scene with the realism and immersion is critical. As time progresses, the researchers focused on improving efficiency of many algorithms for collision detection, these algorithms for particular occasions at that time produced very good results and met real-time. However, with the increasing complexity of virtual scene and objects, the real-time of collision detection has been greatly affected. In recent years, with the development graphics processor, GPU revolutionary changes in structure and functions, makes the GPU can be used in general purpose, therefore, it provides new ideas and methods on how to solve the problem of collision detection with real- time.Based on in-depth analysis of typical collision detection algorithm,using the parallel processing capabilities of GPU, we presented a collision detection algorithm based on parallel GPU accelerated.the algorithm have been designed and improved in the following aspects:①through in-depth analysis of collision detection algorithm based on the AABB hierarchical tree, we explore part of the algorithm which can be parallelized. And during in constructing bounding volume hierarchy tree, the adoption of a bottom-up approach of parallel processing, accelerate the speed of generating and updating hierarchy tree.②when traverse the hierarchy tree,we also optimize the parallel processing, and that is become a GPU based real-time collision detection algorithm for general-purpose computing. When deciding whether two objects collide, we directly use the triangle to traverse the all bounding box of another object, and get the result. Due to algorithm using CUDA thread of way to for processing, so just Executive a traverse of process, its time complex is O(n), compared to the algorithm implement on CPU,the time complex is O(N2), that maks great progress. When collision detection is over, the GPU return the results to the CPU, and the CPU goes to the next step with the results. By using the "CPU+GPU " modern, we assign different tasks to different part to perform with extend their advantages, which makes performance a lot.Experimental results show that the collision detection algorithm based on parallel GPU acceleration achieved very good results. Even for more complicated models and scenes, it still meet the requirements of real-time collision detection.