MCCD: Multi-core collision detection between deformable models using front-based decomposition

We present a novel parallel algorithm for fast continuous collision detection (CCD) between deformable models using multi-core processors. We use a hierarchical representation to accelerate these queries and present an incremental algorithm that exploits temporal coherence between successive frames. Our formulation distributes the computation among multiple cores by using fine-grained front-based decomposition. We also present efficient techniques to reduce the number of elementary tests and analyze the scalability of our approach. We have implemented the parallel algorithm on eight core and 16 core PCs, and observe up to 7× and 13× speedups respectively, on complex benchmarks.