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. 03] 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 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 msec on a PC with a Pentium IV 3.4 GHz CPU and an NVIDIA GeForce FX 6800 Ultra GPU. | Wireframe of the cloth piece shown in the left image. |
CULLIDE: Interactive Collision Detection between Complex Models using Graphics Hardware
RCULLIDE: Fast and Reliable Collision Culling using Graphics Processors
CB #3175, Department of Computer Science
University of North Carolina
Chapel Hill, NC 27599-3175
919.962.1749
geom@cs.unc.edu