CDFast: an Algorithm Combining Different Bounding Volume Strategies for Real Time Collision Detection

Abstract

Collision detection has a great importance in a large spectrum of disciplines, such as virtual reality, computer graphics, simulation of physical systems, robotics, solid modelling, and so on. In particular, some applications need to determine in real time if a collision occurs in order to guarantee an interactive behavior of the system. This paper presents an algorithm that combines different bounding strategies in order both to speed up and to reduce interference tests. A recursive space subdivision is performed by uniform grids to bound static objects within the environment; on the other hand, spheretrees, at different levels of detail, are used to encapsulate moving objects. The proposed methodology is compared with an approach that uses discrete orientation polytopes (k-dops). K-dops proved to be more efficient than other bounding volume strategies, such as oriented and axis-aligned bounding boxes. A theoretical evaluation of the algorithm complexity as well as experimental results are provided.