Interactive Collision Detection between Deformable Models Using Chromatic Decomposition (original) (raw)

Naga K. Govindaraju, David Knott, Nitin Jain, Ilknur Kabul, Rasmus Tamstorf, Russell Gayle, Ming C. Lin, and Dinesh Manocha

We present a novel algorithm for accurately detecting all contacts, including self-collisions, between deformable models. We precompute a chromatic decomposition of a mesh into non-adjacent primitives using graph coloring algorithms. The chromatic decomposition enables us to check for collisions between non-adjacent primitives using a linear-time culling algorithm. As a result, we achieve higher culling efficiency and significantly reduce the number of false positives. We use our algorithm to check for collisions among complex deformable models consisting of tens of thousands of triangles for cloth modeling and medical simulation. Our algorithm accurately computes all contacts at interactive rates. We observed up to an order of magnitude speedup over prior methods.

Contents

• Interactive Collision Detection between Deformable Models Using Chromatic Decomposition, ACM SIGGRAPH 2005.
• Video (900 MB)

Related Links

• CULLIDE: Interactive Collision Detection Between Complex Models Using Graphics Hardware
• Quick-CULLIDE: Efficient Inter- and Intra-Object Collision Culling Using Graphics Hardware
• RCULLIDE: Fast and Reliable Collision Culling Using Graphics Processors
• Collision Detection and Proximity Queries
• Geometric Algorithms for Modeling, Motion, and Animation

Contact

CB #3175, Department of Computer Science
University of North Carolina
Chapel Hill, NC 27599-3175
(919) 962-1749
geom@cs.unc.edu