This figure shows the overall structure of the HPCCD
method. It performs the BVH update and traversal at CPUs and the
elementary tests at GPUs.
These images show two frames of our cloth simulation
benchmark consisting of 92 K triangles. In this benchmark, our
method spends 23 ms for CCD including self-collisions on average
and achieves 10.4 times performance improvement by using four
CPU-cores and two GPUs over a serial CPU-based CCD method.
This figure shows two frames during the N-body simulation
benchmark with two different model complexities: 34 K and
146 K triangles. Our method spends 6.8 ms and 54 ms on average
and achieves 11.4 times and 13.6 times performance improvements
for two different model complexities.
Abstract
We present a novel, hybrid parallel continuous collision detection (HPCCD) method that exploits the availability of
multi-core CPU and GPU architectures. HPCCD is based on a bounding volume hierarchy (BVH) and selectively
performs lazy reconstructions. Our method works with a wide variety of deforming models and supports selfcollision
detection. HPCCD takes advantage of hybrid multi-core architectures . using the general-purpose CPUs
to perform the BVH traversal and culling while GPUs are used to perform elementary tests that reduce to solving
cubic equations. We propose a novel task decomposition method that leads to a lock-free, parallel algorithm in the
main loop of our BVH-based collision detection to create a highly scalable algorithm. By exploiting the availability
of hybrid, multi-core CPU and GPU architectures, our proposed method achieves more than an order of magnitude
improvement in performance using four CPU-cores and two GPUs, compared to using a single CPU-core. This
performance improvement results in an interactive performance, up to 148 fps, for various deforming benchmarks
consisting of tens or hundreds of thousand triangles.
@article{HPCCD09,
author = {Duksu Kim and Jae-Pil Heo and Jaehyuk Huh and John Kim and Sung-Eui Yoon},
title = {{HPCCD}: Hybrid Parallel Continuous Collision Detection using CPUs and GPUs},
journal = {Computer Graphics Forum (Pacific Graphics)},
year = {2009}
volume = {28}
number = {7}
page = "1791--1800"
}
Acknowledgements
We would like to thank anonymous reviewers for their constructive feedbacks.
We also thank Min Tang, Dinesh Manocha, Joon-Kyung Seong, Young J. Kim, Won-Ki
Jeong, Samuel
Brice, and members of SGLab. for their supports and code sharing. The tested
models are courtesy of the UNC dynamic model benchmarks. This project was
supported in part by MKE/MCST/IITA [2008-F-033-02,2008-F-030-02], MCST/KEIT
[2006-S-045-1], MKE/IITA u-Learning, MKE digital mask control,
MCST/KOCCA-CTR\&DP-2009, KRF-2008-313-D00922, and MSRA E-heritage
