HPCCD: Hybrid Parallel Continuous Collision Detection using CPUs and GPUs

by Duk-Su Kim, Jae-Pil Heo, Jaehyuk Huh, John Kim, ,and Sung-eui Yoon.

(Appear at) Computer Graphics Forum (Pacific Graphics) 2009

Received a distinguished paper award at the conference


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.


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.


Paper: HPCCD: Hybrid Parallel Continuous Collision Detection using CPUs and GPUs,
Appear at Pacific Graphics 2009
Talk slides (Pacific Graphics 2009)

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"


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

Related Links

Scheduling in Heterogeneous Computing Environments for Proximity Queries : Extended work of this project

FASTCD: Fracturing-Aware Stable Collision Detection

PCCD: Parallel Continuous Collision Detection

Interactive Continuous Collision Detection between Deformable Models using Connectivity-Based Culling




Dept. of Computer Science
373-1 Guseong-dong, Yuseong-gu, Daejeon, 305-701
South Korea
sglabkaist dot gmail dot com