Fast Collision Detection among Deformable Objects using Graphics Processors

development, virtual environments, robotics, and engineering simulations. It
is often one of the major computational bottlenecks in dynamic simulation of
complex systems. In this talk, I will mainly address the problem of
collision detection among multiple deformable and breakable objects in large
environments using graphics hardware. Our algorithm computes a potentially
colliding set (PCS) using visibility queries. It involves no pre-computation
and proceeds in multiple stages: PCS computation at an object level and PCS
computation at sub-object level, followed by exact collision detection. We
use a linear time two-pass rendering algorithm to compute each PCS
efficiently. Our collision-pruning algorithm can also compute
self-collisions in general deformable models. Further, we overcome the
sampling and precision problems in our pruning algorithm by fattening the
triangles sufficiently in the PCS. In contrast to prior GPU-based collision
detection algorithms, our algorithm guarantees that no collisions will be
missed due to limited frame-buffer precision or quantization errors during
rasterization. Moreover, the overall approach makes no assumption about the
input primitives or the object's motion and is directly applicable to all
triangulated models. It has been implemented on a PC with an NVIDIA GeForce
FX 5900 Ultra graphics card and applied to different environments composed
of a high number of moving objects with tens of thousands of triangles. It
is able to compute all the overlapping primitives in a few milliseconds.