VolCCD: Fast Continuous Collision Culling between Deforming Volume Meshes

by Min Tang1, Dinesh Manocha2, Sung-Eui Yoon3, Peng Du1, Jae-Pil Heo3 and Ruofeng Tong1.

1 - Zhejiang University, China

2 - University of North Carolina at Chapel Hill, USA

3 - Korea Advanced Institute of Science and Technology (KAIST), South Korea


Car Crash: A Ford Explorer with 1.2M shell elements crashes against a rigid wall and deforms. These figures show exterior and interior views. Average CCD query time for inter- and intra-collision detection is 3.3 seconds per frame. We obtain 12 times performance improvement over prior methods.
Cutting Liver: A liver is cut during a surgical operation. The model has 3874 tetrahedra initially and is deformed to have 4338 tetrahedra because of the cutting operation. Average CCD query time is 53.2ms per frame. We achieve more than 10 times improvement over prior methods.
Octopi: Three deforming octopi with 24 tentacles (totally 17.6K tetrahedra). The simulation has multiple inter-object and intra-object collisions. The average CCD query time is 75ms per frame.
Bullet Penetration: A high speed copper bullet (with 11.8-12K hexahedra) hits a steel target and results in topological changes.

Airbag: The volume mesh of this deforming airbag has 9.1K elements. VolCCD performs inter-object and intra-object CCD queries at 88ms on average.




We present a novel culling algorithm to perform fast and robust continuous collision detection between deforming volume meshes. This includes a continuous separating axis test that can conservatively check whether two volume meshes overlap during a given time interval. Moreover, we present efficient methods to eliminate redundant elementary tests between the features (e.g., vertices, edges, and faces) of volume elements (e.g., tetrahedra). Our approach is applicable to various deforming meshes, including those with changing topologies, and efficiently computes the first time of contact. We are able to perform inter-object and intra-object collision queries in models represented with tens of thousands of volume elements at interactive rates on a single CPU core. Moreover, we observe more than an order of magnitude performance improvement over prior methods.



Paper  (PDF 4.4 MB)

Min Tang, Dinesh Manocha, Sung-Eui Yoon, Peng Du, Jae-Pil Heo, and Ruofeng Tong, VolCCD: Fast Continuous Collision Culling between Deforming Volume Meshes, ACM Transaction on Graphics, 30, 5, Article 111 (October 2011), 15 pages.

  author = {Tang, Min and Manocha, Dinesh and Yoon, Sung-Eui and Du, Peng and Heo, Jae-Pil and Tong, Ruofeng},
  title = {{VolCCD}: Fast Continuous Collision Culling between Deforming Volume Meshes},
  journal = {ACM Trans. Graph.},
  volume = {30},
  issue = {5},
  month = {May},
  year = {2011},
  pages = {111:1--111:15},

Video (8.45 MB)

Related Links

UNC dynamic model benchmark repository

Collision-Streams: Fast GPU-based Collision Detection for Deformable Models

Fast Continuous Collision Detection using Deforming Non-Penetration Filters

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 Jeremie Allard and SOFA team for providing Octopi Benchmark and Liver Cutting Benchmark, and helping us with the rendering. We thank Miguel Otaduy for useful discussions and thoughtful comments on an earlier draft. The Car Crash Benchmark and Airbag benchmarks from the Finite Element Model Archive provided by NCAC. We also want to thank Daniel Heiserer from BMW for many useful discussions.


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