Fast Continuous Collision Detection using Deforming Non-Penetration Filters

by Min Tang, Dinesh Manocha, and Ruofeng Tong.

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 T0,T1 and P0, P1 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.


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.


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.

      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 = {},
      publisher = {ACM},
      address = {New York, NY, USA},

Video (15 MB)

DNF Source code

Source code: Self-CCD


Related Links

UNC dynamic model benchmark repository

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

MCCD: Multi-Core Collision Detection between Deformable Models using Front-Based Decomposition

Fast Collision Detection for Deformable Models using Representative-Triangles

DeformCD: Collision Detection between Deforming Objects

Self-CCD: Continuous Collision Detection for Deforming Objects

Interactive Collision Detection between Deformable Models using Chromatic Decomposition

Fast Proximity Computation Among Deformable Models using Discrete Voronoi Diagrams

CULLIDE: Interactive Collision Detection between Complex Models using Graphics Hardware

RCULLIDE: Fast and Reliable Collision Culling using Graphics Processors

Quick-CULLIDE: Efficient Inter- and Intra-Object Collision Culling using Graphics Hardware

Collision Detection



We would like to thank Jieyi Zhao, Jiang Lin, Peng Du and Ming Lin for useful discussions and the benchmarks. The cloth models were provided by Rasmus Tamstorf at Disney Animation.

This research is supported in part by National Basic Research Program of China (No. 2006CB303106), MOE-Intel special research fund on information technology (No. MOE-INTEL-09-05), ARO Contract W911NF-04-1-0088, NSF awards 0636208, 0917040 and 0904990, DARPA/RDECOM Contract WR91CRB-08-C-0137, and Intel. Tang is supported in part by Natural Science Foundation of China (No. 60803054), National Key Technology R&D Program, China (No. 2006BAF01A45-05), Natural Science Foundation of Zhejiang, China (No. Y107403), Doctoral subject special scientific research fund of Education Ministry of China (No. 20070335074).

CB #3175, Department of Computer Science
University of North Carolina
Chapel Hill, NC 27599-3175