Pccd: Parallel continuous collision detection

We present a novel parallel continuous collision detection (PCCD) method to utilize the widely available multi-core CPU architec-ture. Our method works with a wide variety of deforming models and supports self-collision detection. Our method uses a feature-based bounding volume hierarchy (BVH) to improve the perfor-mance of continuous collision detection. Also, our method selec-tively 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 work-loads 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 computa-tion 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.