Particle Oriented Collision Detection using Simplicial Coverings and Tetra-Trees

Abstract

Collision detection (CD) among complex objects in motion is an open question because of its algorithmic complexity. In this paper, we present a CD algorithm between a particle and a complex rigid solid. In order to represent solids, we use a simplicial covering scheme by means of 3-simplices. With this representation system, complex polyhedra and closed triangle meshes can be represented and used in CD with a particle. A particle can be represented by a point, where the real dimensions of the particle are not important. This CD algorithm has been extended for a particle represented by a sphere which in turn represents an approximation to the particle dimensions. In order to efficiently classify the particles and the simplices of the polyhedra covering, we use a new hierarchical data structure named tetra-tree that decomposes the space into tetra-cones. These algorithms also use bounding volumes and temporal and geometric coherence, as well as incremental calculations in order to determine the collision in an efficient and exact way. Because of the use of sign operations with signed volumes and barycentric coordinates, we conclude that operations carried out using this method are more robust and efficient than those used in classic algorithms.