VolCCD: Fast Continuous Collision Culling
between Deforming Volume Meshes
1 - Zhejiang University,
China
2 - University of North Carolina at Chapel
Hill, USA
3 - Korea Advanced Institute of
Science and Technology (KAIST), South Korea
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
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
UNC GAMMA Group
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
