Particle-based Collision Detection

Abstract

In the paper we present a novel algorithm for collision detection between complex geometric objects represented by polygonal models and undergoing rigid motions and deformations. Most algorithms described in the literature deal with rigid bodies and are based on some kind of hierarchical representations. We present the alternative approach. The algorithm relies on the idea of "sensor particles": interacting particles distributed on a surface. Two types of particles that interact in a special way are used for determining the minimum distance between two models. The algorithm has been implemented and used in real time simulation of dynamic interaction between geometric objects. A detailed description of the algorithm, animation examples, and benchmarks are included in the paper. A potential application of this software algorithm is collision detection for animation of bodies with deformable surfaces.