Research On GPU-Based Collision Detection Algorithms

Collision detection is to determine whether two moving objects collide or not at any moment. It is required, as a typical and efficient approach in practice, to consider whether the two objects collided in any of a sequence of discrete time frames. Collision detection is one of the most important researches in the fields of computer animation, game designing, robotics, computer graphics, and so on. This technique is necessary especially when the motion path of an object is defined interactively rather than pre-specified, such as motion planning in robotics in virtual reality application.Till now, a lot of achievements have been made in the problem of collision detection. However, the field of virtual reality is becoming more and more popular, which is followed by the increasing complexity of object models and environments, people's increasing requirements of the real-time interaction and environment reality. Especially in large complicated environments which consist of a large amount of moving objects, it is required to do collision detection among those moving objects. Consequently, unprecedented challenge has been brought about to the problem of collision detection.Graphics processing Unit (GPU), a stream processor with high parallelism, high computational power and memory bandwidth, serves as an efficient and satisfying solution to this problem. Researches on such kind of problem have become one of the hot topics on GPU research. This paper introduces the following two algorithms both of which apply the high computational power and parallelism of GPU to helping solve the problem of collision detection.1. Detect collision of two polytopes by searching a separating plane. An iterating heuristic method is applied to find the separating plane. After certain iterating steps, the algorithm can be terminated by either a separate plane being found or proving that these two polytopes are collided. At the same time, GPU is adopted to accelerate the key step - computation of the supporting vertex pair. Due to the high parallelism of GPU, the calculation of the key step, getting the support vertex pairs, is accelerated. A real-time collision detection for multiple objects in large environments is also introduced in this paper, based on the reduction method for computing the max value in GPU.2. An efficient algorithm for real time collision detection between complex deformable objects with closed surfaces by using graphics hardware. The algorithm adopts an effective use of the rendering buffers and the occlusion query operation, and can also be applied to detect self-collision. Though our current algorithm has some limitations, it requires neither expensive preprocessing nor complex data structures and is directly applicable to all kinds of models which are ready to render. In contrast to most existing methods, the proposed algorithm is completely implemented in graphics hardware and does not perform time consuming framebuffer readbacks from GPU. This significantly improves the performance.Several experiments and comparisons with other algorithms have been carried out to show the performance and efficiency of our algorithms.