Parallel collision detection algorithm based on coloring algorithm
基于着色算法的并行碰撞检测算法*

This paper presented a new parallel collision detection algorithm based on coloring algorithm. At first, incorporated the merits of both AABB bounding box and bounding spheres to construct a hybrid bounding representation of arbitrary non-convex polyhedra (S-AABB) for attaining speed, balanced especially the S-AABB using divide-and-conquer technologies which were mostly primary technologies in parallel algorithm. Then applied symmetry breaking-k-coloring technology which was also important in parallel algorithm in order to reduce different categories, and assign them to different processors; also multi-thread was used in multi-processor computer. At last, experiments results show that the algorithm is advantageous over other current typical collision detection such as I-COLLIDE regarding efficiency and accuracy, so can meets the real-time and accurate requirements in complex interactive virtual environment.