Zhejiang University, China

University of North Carolina at Chapel Hill, USA

Deforming Filter: For a deforming triangle T and a deforming vertex P defined by T₀,T₁ and P₀, P₁ respectively, the bounding volume test (c) becomes quite conservative. The coplanarity test (d) checks whether a penetration between the primitives during the time interval. If the vertex is always on the same side of the triangle during the entire time interval, then the four vertices associated with that elementary test cannot be coplanar during the time interval [0, 1] and therefore, no collision occurs.

Edges involved by EE tests with different culling methods: This figure shows edges (highlighted in green) used by EE tests during a specific frame of the Cloth benchmark with coplanarity-based culling and bounding volume based culling respectively. Comparing to only bounding volume based culling, the number of EE elementary tests are reduced by 80% with the deforming non-penetration filter (left).

Benchmark Lion: In this simulation, a stone falls on top of a Chinese lion model and the lion gradually breaks into a high number of colliding pieces. This model has 805K vertices and 1.6M triangles. In this fracture scene with changing topologies, our new algorithm based on a deforming filter increases the culling efficiency and reduces the number of elementary test by 10x as compared to prior methods and improves the performance of the CCD algorithm by 4.1x.

Abstract

We present a novel culling algorithm that uses deforming non-penetration filters to improve the performance of continuous collision detection (CCD) algorithms. The underlying idea is to use a simple and effective filter that reduces the number of false positives and the elementary tests between the primitives. This filter is derived from the coplanarity condition and can be easily combined with other methods used to accelerate CCD. We have implemented the algorithm and tested its performance on many non-rigid simulations. In practice, we can reduce the number of false positives significantly and improve the performance of overall CCD algorithm by 1.5-8.2 times.

Contents

Paper  (PDF 1.7 MB)

Min Tang, Dinesh Manocha, Ruofeng Tong, Fast Continuous Collision Detection using Deforming Non-Penetration Filters, in Proceedings of ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games (i3D 2010), Washington DC, Feb. 19-21, 2010: 7-13.

   @inproceedings{1730806,
      author = {Tang, Min and Manocha, Dinesh and Tong, Ruofeng},
      title = {Fast continuous collision detection using deforming non-penetration filters},
      booktitle = {I3D '10: Proceedings of the 2010 ACM SIGGRAPH symposium on Interactive 3D Graphics and Games},
      year = {2010},
      isbn = {978-1-60558-939-8},
      pages = {7--13},
      location = {Washington, D.C.},
      doi = {http://doi.acm.org/10.1145/1730804.1730806},
      publisher = {ACM},
      address = {New York, NY, USA},
  }

Video (15 MB)

DNF Source code

Source code: Self-CCD

Related Links