Fast Collision Detection for Deformable Models using Representative-Triangles Sean Curtis, Rasmus Tamstorf, Dinesh Manocha University of North Carolina at Chapel Hill An animated sequence of a flamenco dancer with 26K vertices, 75K edges and 50K triangles, consisting of 350 frames. We observed up to a 15X reduction in elementary tests and a 4.9X increase in speed on this benchmark. Our new method calculates all self-collisions and inter-object collisions in 200 ms per frame. Abstract We present a new approach to accelerate collision detection for deformable models. Our formulation applies to all triangulated models and significantly reduces the number of elementary tests between features of the mesh, i.e., vertices, edges and faces. We introduce the notion of Representative-Triangles, standard geometric triangles augmented with mesh feature information and use this representation to achieve better collision query performance. The resulting approach can be combined with bounding volume hierarchies and works well for both inter-object and self-collision detection. We demonstrate the benefit of Representative-Triangles on continuous collision detection for cloth simulation and N-body collision scenarios. We observe up to a one-order of magnitude reduction in feature-pair tests and up to a 5X improvement in query time. Paper (in I3D 2008: Symposium on Interactive 3D Graphics and Games) (PDF 2.7 MB) Slides for I3D 2008 presentation (PDF 4.8 MB) Benchmarks Video (36MB - DIVX) -- An appendix of the benchmarks used in the paper Additional benchmarks. An n-body simulation with 18 K vertices, 51 K edges and 34 K triangles consisting of 374 frames. We observed up to a 9X reduction in elementary tests and a 5.3X increase in speed on this benchmark. A cloth simulation with 20 K vertices, 60 K edges and 40 K triangles consisting of 1044 frames. We observed up to a 28X reduction in elementary tests and a 5.1X increase in speed on this benchmark. A cloth simulation with 47 K vertices, 139 K edges and 92 K triangles consisting of 464 frames. We observed up to a 12X reduction in elementary tests and a 4.98X increase in speed on this benchmark using R-Triangles.