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.
AbstractWe 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)
BenchmarksVideo (36MB - DIVX) -- An appendix of the benchmarks used in the paper Additional benchmarks. |