by Naga Govindaraju, David Knott, Nitin Jain, Ilknur Kabul, Rasmus Tamstorf, Russell Gayle, Ming 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.

Benchmark I: This simulation generates complex folds and wrinkles on the skirt. The cloth is modeled as a mesh with 13K triangles. Our collision detection algorithm accurately checks for all self-collisions within 400-500ms during each step of the simulation. We significantly reduce the number of false positives and perform relatively few exact intersection tests between the primitives.	Benchmark II: We use our collision detection to compute all contacts, including self-collisions, during cloth simulation. The cloth mesh consists of more than 23K triangles and our chromatic decomposition partitions the mesh into 19 independent sets. Our algorithm accurately computes all the collisions within 400-550 msec during each step of the simulation.

Contents

Video

Related Links

CULLIDE: Interactive Collision Detection between Complex Models using Graphics Hardware

RCULLIDE: Fast and Reliable Collision Culling using Graphics Processors

Quick-CULLIDE: Efficient Inter- and Intra-Object Collision Culling using Graphics Hardware

Collision Detection

UNC GAMMA Group

CB #3175, Department of Computer Science
University of North Carolina
Chapel Hill, NC 27599-3175
919.962.1749
geom@cs.unc.edu