基于着色算法的并行碰撞检测算法*

提出了一种基于着色算法的并行碰撞检测算法，利用AABB包围盒较好的紧密性和包围球计算简单的优点以及并行算法中的分治策略构建物体的混合包围体层次(S-AABB)；然后采用破对称技术中的典型算法——着色算法，将每棵任务树编码，以产生各不相同的类别，并将不同的类别指派到不同的并行机，在并行机上采用多线程技术执行相同的类别的任务树的遍历，来检测是否有碰撞发生。实验结果表明，与现有的经典的I-COLLIDE等算法相比，该算法在效率、精确性方面具有明显优势，能够满足交互式复杂虚拟环境的实时性和精确性的要求。

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.