Collision detection between complex polyhedra

Collision detection (CD) between two objects is a complex task which demands spatial decomposition or bounding volume hierarchy in order to classify the features of the objects for a successful intersection test. Moreover, when the objects are complex and have concavities, holes, etc., the complexity of the decomposition increases and it is necessary to find a method which detects all special cases and degenerations.In this paper, we present a method for CD between complex polyhedra. We use a polyhedron representation based on simplicial coverings. With such as representation it is possible to model complex objects by using simpler objects (simplices), without any previous decomposition into convex pieces. The spatial decomposition so-called tetra-tree is utilized in order to classify the simplices of the covering, as well as a bounding volume hierarchy based on tetrahedra and spheres which allows us to drastically reduce the number of intersection tests between the features of both polyhedra. A time study has been performed to obtain a real time CD between two complex objects.