Interactive collision detection between deformable models using chromatic decomposition

Autor:	Russell Gayle, Ilknur Kabul, David Knott, Naga K. Govindaraju, Nitin Jain, Dinesh Manocha, Ming C. Lin, Rasmus Tamstorf
Rok vydání:	2005
Předmět:	Cloth modeling Theoretical computer science Speedup Computer science Decomposition (computer science) Collision detection Chromatic scale Graph coloring Computer Graphics and Computer-Aided Design Algorithm ComputingMethodologies_COMPUTERGRAPHICS
Zdroj:	ACM Transactions on Graphics. 24:991-999
ISSN:	1557-7368 0730-0301
Popis:	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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e97eb219c14c9ed9896c1a779142719e https://doi.org/10.1145/1073204.1073301 Zobrazit plný text záznamu