We present a novel parallel
algorithm for fast continuous collision detection (CCD) between deformable
models using multi-core processors. We use a hierarchical representation to
accelerate these queries and present an incremental algorithm that exploits
temporal coherence between successive frames. Our formulation distributes the
computation among multiple cores by using fine-grained front-based
decomposition. We also present efficient techniques to reduce the number of
elementary tests and analyze the scalability of our approach. We have
implemented the parallel algorithm on 8 core and 16 core PCs, and observe up to
7X and 13X speedups respectively, on complex benchmarks.
Contents
Short paper at SPM'09 (PDF 270 KB)
Min Tang, Dinesh Manocha, Ruofeng Tong. Multi-Core collision detection between deformable models. 2009 SIAM/ACM Joint Conference on Geometric and Physical Modeling, 2009, pp.355-360.
@inproceedings{TMT09,
author = {Tang, Min and Manocha, Dinesh and Tong, Ruofeng},
title = {Multi-core collision detection between deformable models},
booktitle = {SPM '09: 2009 SIAM/ACM Joint Conference on Geometric and Physical Modeling},
year = {2009},
isbn = {978-1-60558-711-0},
pages = {355--360},
location = {San Francisco, California},
doi = {http://doi.acm.org/10.1145/1629255.1629303},
publisher = {ACM},
address = {New York, NY, USA},
}
Paper (Graphical Models) (PDF 2.1 MB)
Min Tang, Dinesh Manocha, Ruofeng Tong, MCCD: Multi-Core collision detection between deformable models using front-based decomposition, Graphical Models, Vol. 72, No. 2, pp.7-23, 2010.
@article{TMT10-GMOD,
author = {Tang, Min and Manocha, Dinesh and Tong, Ruofeng},
title = {MCCD: Multi-Core collision detection between deformable models using front-based decomposition},
journal ={Graphical Models},
volume = {72},
number = {2},
issn = {1524-0703},
year = {2010},
pages = {7-23},
doi = {DOI: 10.1016/j.gmod.2010.01.001},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
Source code
Video (19.4MB)
Related Links
UNC dynamic model benchmark
repository
Interactive Continuous Collision
Detection between Deformable Models using Connectivity-Based Culling
MCCD: Multi-core Continuous Collision Detection for Deforming Objects
Self-CCD: Continuous Collision Detection for Deforming Objects
DeformCD: Collision Detection
between 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 thank Sung-Eui Yoon, Sean Curtis, Rasmus Tamstorf, Naga Govindaraju,
Avneesh Sud, Russ Gayle and Ming Lin for useful discussions and the benchmarks.
We thanks Jiang Lin for helping to make the AVI Fies.
This research is supported in part by National Basic Research Program of China
(No. 2006CB303106), ARO Contracts DAAD19-02-1-0390 and W911NF-04-1-0088, NSF
awards 0400134, 0429583 and 0404088, DARPA/RDECOM Contract N61339-04-C-0043,
Disney and Intel. Tang is supported in part by National 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
919.962.1749
geom@cs.unc.edu
