A Fast Collision Detection Algorithm Based On GPU

Collision detection is an important research topic of Computer Graphics,virtual reality and so on. With the launch of the multi-core GPU acting as a general purpose computing tools, the traditional collision detection algorithm which is implemented based on CPU ushered in a new stage of development. GPU that possessed superior computing power provides an effective way to enhance the efficiency of collision detection of high computational complexity.We research the traditional collision detection algorithm implemented based on CPU in this paper. With the GPU features of general-purpose compute, we provided the collision detection algorithm based on spatial decomposition and bounding box which can be executed in parallel with GPU. We improve the traditional serial algorithm from three aspects as following:1) First we improved the collision detection algorithm based on uniform spatial meshing.We just Store the subunits that contain the effective data by construct the hash functions in parallel on the GPU. The video memory can be saved and the basic geometric elements can be distributed to the subunits rapidly and the potential intersection subunits can be positioned quickly by this means. Through the phase of space decomposition we can narrow the scope of the collision detection at the beginning of the test.The first phase establishes good groundwork for the second phase.2) Then we improved the traditional algorithm which is based on hierarchical bounding box.We adopt the bottom-up approach to build the AABB bounding box tree in parallel on the GPU.We adopted the approach of breadth-first traversal to do the intersection test between the AABB bounding boxes in parallel on the GPU. Then the potential intersecting primitive triangles can be confirmed in the second stage.3) At last we improved the intersection test between the primitive triangles and used the vector criterion method to do the intersection test between the primitive triangles in parallel on the GPU. The data of primitive triangles in the CPU memory is to be mapped to the GPU memory and then we use all the threads of the GPU to do the intersection test in parallel. This method can improve the efficiency of collision detection obviously.The collision detection algorithm in this article is not limited to the combination of the three stages, the results said that for the collision detection algorithm based on space division and bounding box. Compared to the collision detection algorithm based on CPU,the collision detection algorithm based on GPU can improve the efficiency of collision detectioneffectively.But for the moderately complex 3D models,the collision detection algorithm based on space decomposition is more efficient then the collision detection algorithm based on space division and bounding box. For the simple 3D models, the collision detection algorithm based on primitive triangles intersection test is more efficient then the collision detection algorithm based on space decomposition when the algorithm is executed on multi-core GPU. For the Complex 3D models, the collision detection algorithm based on space division and bounding box is more efficient then the two kinds of collision detection algorithm that were introduced above when the algorithm is executed on multi-core GPU.