Robust continuous collision detection for interactive deformable surfaces

Collision events between 3D objects in motion in computer animations or simulations are difficult to detect due to the difficulty of accurately sampling the motion paths of objects in space and time. One approach to this problem has been continuous collision detection but because the current approaches process potentially interacting primitive pairs (PIPPs) redundantly. This is time-expensive, especially where there are a large number of PIPPs. In this paper we propose a novel collision detection process that more accurately and robustly detects collisions on simulated meshed deformable surfaces. We embed a new layer, primitive filtering layer (PFL), to extract PIPPs. This has two results. It reduces the number of PIPPs significantly and it means that each interacting primitive pair is processed just one time. Experimental results show that this approach achieves interactive rates for complex deformable surfaces with large contact regions. This is especially practical for cloth dynamics. Our method is efficient, accurate, reliable, and robust even in the presence of objects with sharp features. We also present techniques to implement the method on programmable graphics processing units (GPUs). Copyright (c) 2007 John Wiley & Sons, Ltd.