QUICK-CULLIDE: Efficient Inter- and Intra-Object Collision Culling Using Graphics Hardware

Naga K. Govindaraju, Ming C. Lin, and Dinesh Manocha

We present a fast collision culling algorithm for performing inter- and intra-object collision detection among complex models using graphics hardware. Our algorithm is based on CULLIDE [Govindaraju et al. 2003] and performs visibility queries on the GPUs to eliminate a subset of geometric primitives that are not in close proximity. We present an extension to CULLIDE to perform intra-object or self-collisions between complex models. Furthermore, we use a novel visibility-based classification scheme to compute potentially-colliding and collision-free subsets of objects and primitives that considerably improves the culling performance. We have implemented our algorithm on a PC with an NVIDIA GeForce FX 6800 Ultra graphics card and applied it to a cloth simulation with 20K triangles. three complex simulations, each consisting of objects with tens of thousands of triangles. In practice, we are able to compute all the self-collisions for cloth simulation up to image-space precision at interactive rates. Furthermore, our novel visibility-based classification can improve the culling efficiency by an order of magnitude in many scenarios.

Cloth   Wireframe
Cloth Simulation: This figure shows an instance of a cloth falling over a circular table. The cloth is modeled using 20K triangles. Our algorithm QUICK-CULLIDE is able to compute all the self-collisions in about 21 ms on a PC with a Pentium 4 3.4 GHz CPU and an NVIDIA GeForce FX 6800 Ultra GPU.   Wireframe of the cloth piece shown in the left image.


Related Links


CB #3175, Department of Computer Science
University of North Carolina
Chapel Hill, NC 27599-3175
(919) 962-1749