Interactive Continuous Collision Detection between Deformable Models using Connectivity-Based Culling

by Min Tang, Sean Curtis, Sung-Eui Yoon, and Dinesh Manocha.

University of North Carolina at Chapel Hill, USA
Zhejiang University, China
Korea Advanced Institute of Science and Technology (KAIST), South Korea

Abstract

We present an interactive algorithm for continuous collision detection between deformable models. We introduce two techniques to improve the culling efficiency and reduce the number of potentially colliding triangle candidate pairs. First, we present a novel formulation for continuous normal cones and use these normal cones to efficiently cull large regions of the mesh from self-collision tests. Second, we exploit the mesh connectivity and introduce the concept of "orphan sets" to eliminate almost all redundant elementary tests between adjacent triangles. In particular, we can reduce the number of elementary tests by many orders of magnitude. These culling techniques have been combined with bounding volume hierarchies and can result in one order of magnitude performance improvement as compared to prior algorithms for deformable models. We highlight the performance of our algorithm on several benchmarks, including cloth simulations, N-body simulations and breaking objects.


Benchmark I: Prince benchmark: A dancing actress with waving skirt. This model has 60K vertices and 40K triangles. Our novel CCD algorithm takes 45ms per frame to compute all the collisions, and is about one order of magnitude faster than prior approaches.	Benchmark II: Dragon benchmark:In this simulation, a bunny model is dropped on top of the dragon model and the dragon model breaks into many pieces. This model has 193K vertices and 253K triangles. In this scene with changing topologies, our algorithm obtain high culling efficiency and reduce the number of false positives by 20 times, as compared to prior CCD algorithms. The average CCD query time is about 878ms, about an order of magnitude faster than prior algorithms.	Benchmark III: N-body benchmark: In this simulation, multiple balls are colliding with each other. This scene has 18K vertices and 34K triangles. Our culling algorithms reduce the number of elementary test by 18 times and can find all collisions in about 89ms per frame.

Benchmark IV: Cloth benchmark: We drop a cloth on top of a ball and rotate the ball. This model has 46K vertices and 92K triangles and the simulation results in a high number of self-collision. Our algorithm takes about 290ms on average to perform continuous collision detection. Our culling techniques reduce the number of false positives by 38 times.	Benchmark V: Letters benchmark: Multiple alphabet and number shapes are interacting with a bowl. This model has 3K vertices and 5K triangles. It takes 9.4ms on average for CCD, which is almost 10 times faster than the running time presented in [SGG'06].

Paper (SPM'08) (PDF 2.2 MB)

Min Tang, Sean Curtis, Sung-Eui Yoon, Dinesh Manocha: Interactive continuous collision detection between deformable models using connectivity-based culling. Symposium on Solid and Physical Modeling 2008: 25-36.

   @inproceedings{TCYM08,
      author = {Tang, Min and Curtis, Sean and Yoon, Sung-Eui and Manocha, Dinesh},
      title = {Interactive continuous collision detection between deformable models using connectivity-based culling},
      booktitle = {SPM '08: Proceedings of the 2008 ACM symposium on Solid and physical modeling},
      year = {2008},
      isbn = {978-1-60558-106-2},
      pages = {25--36},
      location = {Stony Brook, New York},
      doi = {http://doi.acm.org/10.1145/1364901.1364908},
      publisher = {ACM},
      address = {New York, NY, USA},
  }

Paper (CGI'08) (PDF 1.8 MB)

Min Tang, Sung-Eui Yoon, Dinesh Manocha, Adjacency-based culling for continuous collision detection, The Visual Computer,24(7-9), Proceedings of CGI08 (Computer Graphics International), 545-553,2008.

   @article{TYM08,
      author = {Tang, Min and Yoon, Sung-Eui and Manocha, Dinesh},
      title = {Adjacency-based culling for continuous collision detection},
      journal = {Vis. Comput.},
      volume = {24},
      number = {7},
      year = {2008},
      issn = {0178-2789},
      pages = {545--553},
      doi = {http://dx.doi.org/10.1007/s00371-008-0235-y},
      publisher = {Springer-Verlag New York, Inc.},
      address = {Secaucus, NJ, USA},
  }

Paper (TVCG) (PDF 3.5 MB)

Min Tang, Sean Curtis, Sung-Eui Yoon, Dinesh Manocha. ICCD: Interactive Continuous Collision Detection between Deformable Models using Connectivity-Based Culling, IEEE Transactions on Visualization and Computer Graphics, 2009, 15(4): 544-557.

   @article{TCYM09,
      author = {Min Tang and Sean Curtis and Sung-Eui Yoon and Dinesh Manocha},
      title = {ICCD: Interactive Continuous Collision Detection between Deformable Models Using Connectivity-Based Culling},
      journal ={IEEE Transactions on Visualization and Computer Graphics},
      volume = {15},
      issn = {1077-2626},
      year = {2009},
      pages = {544-557},
      doi = {http://doi.ieeecomputersociety.org/10.1109/TVCG.2009.12},
      publisher = {IEEE Computer Society},
      address = {Los Alamitos, CA, USA},
  }

Video (19.1MB - WMV)

Running time of steps of high-level culling: This figure shows the ratio of running times of CNC updating, CNC testing & BVH traversal, CCT, and other computations (updating of k-DOPs and BVH, low-level culling, elementary tests, result collection, etc.

Acknowledgements

We would like to thank Stephane Redon for many useful discussions and his initial code for elementary tests. We also thank Rasmus Tamstorf, Naga Govindaraju, Avneesh Sud, Russ Gayle and Ming Lin for useful discussions and the benchmarks.

This research is supported in part by ARO Contracts DAAD19-02-1-0390 and W911NF-04-1-0088, NSF awards 0400134, 0429583 and 0404088, DARPA/RDECOM Contract N61339-04-C-0043, Disney and Intel. Yoon is supported in part by a seed grant from KAIST, ETRI, and IT R&D program of MIC/IITA contract ITAA1100070400010001000300200. Tang is supported in part by National Basic Research Program of China (No. 2006CB303106), Natural Science Foundation of Zhejiang, China (No. Y107403), Doctoral subject special scientific research fund of Education Ministry of China (No. 20070335074), and Future Academic Star fellowship from Zhejiang University.

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

by Min Tang, Sean Curtis, Sung-Eui Yoon, and Dinesh Manocha.

Contents

Related Links

Acknowledgements