PCCD: Parallel Continuous Collision Detection

by DukSu Kim, Jae-Pil Heo, and Sung-eui Yoon.
Dept. of CS, KAIST, Technical Report CS-TR-2008-298, Oct., 2008

This tech. report is extended and published as HPCCD: Hybrid Parallel Continuous Collision Detection at Pacific Graphics 2009.


The left two images show two frame of our cloth simulation benchmark consisting of 92 K triangles. The right image shows the frame rate, frames per second (fps), of our parallel continuous collision detection method with an ideal frame rate as- suming a perfect scalability as a function of the number of cores in the CPU architecture. In this benchmark our method spends 56 ms for continuous collision detection including self-collisions on average and 6.4 times performance improvement by using 8-cores over using a single-core. We use an Intel Xeon machine with two 2.83 GHz quad-core CPUs.


We present a novel parallel continuous collision detection (PCCD) method to utilize the widely available multi-core CPU architecture. Our method works with a wide variety of deforming models and supports self-collision detection. Our method uses a featurebased bounding volume hierarchy (BVH) to improve the performance of continuous collision detection. Also, our method selectively performs lazy reconstructions. To design a highly scalable PCCD method, we propose novel task decomposition methods for our BVH-based collision detection and dynamic task assignment methods to obtain a high load-balancing among computation workloads assigned to each thread. Our method achieves up to 7.3 times performance improvement by using 8-cores compared to using a single-core. The high performance improvement is mainly due to a few dependencies and synchronizations among different computation tasks performed in each thread. As a result, our PCCD method is able to achieve an interactive performance, 50 ms-140 ms, on average, for various deforming benchmarks consisting of hundreds of thousand triangles.


Paper: PCCD: Parallel Continuous Collision Detection,
Extended and published as HPCCD at Pacific Graphics 2009

Related Links

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