The Research On GPU Based Collision Detection Algorithm

Collision detection is used to detect whether there are contacts or penetrations between two or among multiple objects, and is one of the most important problems in the fields of computer graphics, virtual reality, computer game and CAD/CAM etc. Indeed, after many years of study, there have been many mature collision detection algorithms to some extent. However,as the three-dimensional models in application get more and more complicated and the demands for real time interactivity and realistic simulation of motions of virtual object increase, higher requirement of the efficiency of collision detection algorithm has been put forward. At the same time, the rapid development of GPGPU provides a new approach to the problem of real time collision detection.Based on the comprehensive analyses of various collision detection algorithms, utilizing the CUDA platform, a collision detection algorithm is presented and improved from the three perspectives as follows:First, from the perspective of the general-purpose computing of GPU, a GPGPU based collision detection algorithm is presented. The algorithm performs the overlapping tests between the triangles of one object and the triangles of another to judge whether there are collision between the two objects. All of the computations are mapped to multiple threads of GPU by the platform of CUDA to utilize the great computing power of GPU.Secondly, based on the algorithm presented foregoing, hierarchy tree is adopted to improve the performance of the algorithm, and a GPGPU based real-time collision detection is presented. For the collision detection of two objects, the algorithm performs the overlapping tests between the hierarchical bounding boxes of one object and the triangles of the other object at first, excluding the apparently no-overlapping triangles quickly, reducing the computing complexity from O(N2) to O(N); Then, performs the overlapping tests between the potentially overlapped triangles of the two objects, and obtains the result of collision detection. All the computations are finished in parallel by GPU's multiple threads. By utilizing the conception of heterogeneous operation of CPU+GPU and assigning the computations rationally between CPU and GPU and, this algorithm has achieved a fairly good performance.Finally, according to the optimization principles of CUDA, the algorithm is improved from the perspectives of shared memory and the parallelism degree of threads. The shared memory is used to diminish the times of access to global memory; the dimensions of grid and block are configured appropriately according to the computation complexity and the computing capacity of GPU.The experiment shows our GPGPU based real time collision detection algorithm can adapt the collision detection of arbitrary shaped objects, possessing higher efficiency. The research in this paper provides some theoretical value and practical meaning to real time collision detection, and promotes the development of GPGPU.