The Collision Detection Algorithm Based On Image Space

Real time collision detection is one of the most important problems in the fields of robotics, computer animation, and virtual reality, etc. Its fundamental task is to detect whether there are contacts or penetrations between two or among multiple objects. Indeed, there have been many research achievements on solving the problem of collision detection, this problem, however, is yet to be solved with the emergence of such burgeoning techniques as virtual reality, and the demands of real time interactivity and realistic simulation of motions of virtual objects thereafter.Based on the intensive survey and comprehensive analyses of various approaches to collision detection, several algorithms have been analyzed, expanded and implemented and verified to explore the possibility of speeding up the process of collision detection from, respectively, the perspectives of using the high computing power of graphics hardware, exploring the programmability of graphics processing units (GPUs).From the perspective of using the high computing power of graphics hardware, a collision detection algorithm based on image space is analyzed, which combines graphics hardware capabilities with a simplified geometric representation to facilitate the process of collision detection between complex geometric objects. The method can process arbitrarily shaped mesh objects, while preserving the merits of image-based collision detection algorithms. This is achieved by decomposing the surfaces of an object into a list of convex pieces. High efficiency of the algorithm is obtained by organizing the convex pieces into a binary tree with nodes composed of convex pieces, and by adopting triangle strip compression, which is a kind of real time rendering techniques. Furthermore, the sphere tree and the oriented bounding box (OBB) tree, are used to exclude those convex pieces that don't interfere with each other as early as possible, and the result of OBB overlapping test is used to facilitate the viewing parameter setting for real time rendering. And the time-space relativity is also used to improve the efficiency of the algorithm.