The Real Time Collision Detection Algorithm Using OBB Tree

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, an real time collision detection algorithm using OBB tree have been designed, 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), and utilizing the parallel computing performance of multi-processor machines.From the perspective of using the high computing power of graphics hardware, a fast collision detection algorithm based on image space is presented, 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 detectionalgorithms. 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 oriented bounding box (OBB) tree, is 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.