 |
| 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. |
Abstract
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.
Contents
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.
@ARTICLE {VolCCD,
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
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
Acknowledgements
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
919.962.1749
geom@cs.unc.edu