Parallel Collision Detection Algorithm Based on Decomposing a Polyhedron into Tetrahedrons

Despite significant progress that has been made in developing efficient collision detection algorithms for convex polyhedrons, limited and slow progress has been reported in developing collision detection algorithm for nonconvex polyhedron. To narrow this gap we present a parallel collision detection algorithm. The algorithm consist of two stages. The first stage involves decomposing nonconvex polyhedron into terahedrons. The second stage involves detecting the collision to tetrahedrons in parallel. In the first stage, the decomposing methode´s theoretic provement and its implementation was given. In the second stage, we detailed described the parallel algorithm. Compared with the other algorithms, research result shows that the parallel algorithm greatly improve the collision detection speed with high accuracy.