Multi-Core Collision Detection between Deformable Models (original) (raw)
University of North Carolina at Chapel Hill, USA Zhejiang University, China
 Figure 13: Speedup on the N-body benchmark: The speedups are 6.59X with 8 cores and 9.1X with 16 cores. It takes 12.4ms per frame to compute all the collisions with 16 cores. Figure 15: Speedup on the BART benchmark: The speedups are 6.61X with 8 cores and 10X with 16 cores. It takes 21.2ms per frame to compute all the collisions with 16 cores. Figure 14: Speedup on the Cloth-ball benchmark: The speedups are 6.79X with 8 cores and 9.6X with 16 cores. It takes 35.8ms per frame to compute all the collisions with 16 cores. |
 Figure 11: Speedup on the Princess benchmark: The speedups are 6.22X with 8 cores and 9.1X with 16 cores. It takes 5.9ms per frame to compute all the collisions with 16 cores.  Figure 12: Speedup on the Flamenco benchmark: The speedups are 7:68X with 8 cores and 11.5X with 16 cores. It takes 30.7ms per frame to compute all the collisions with 16 cores. |
|---|
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.
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},
}
Video (19.4MB)
Related Links
UNC dynamic model benchmark repository
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
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