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.
Video(25.2MB)
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.
Abstract
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.
Contents
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
SGLab
Benchmarks
Dept. of Computer Science
KAIST
373-1 Guseong-dong, Yuseong-gu, Daejeon, 305-701
South Korea
sglabkaist dot gmail dot com
