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

Parallel collision detection algorithm based on coloring algorithm

作　　者：赵伟[1,2] 谭睿璞[2] 杨秋娜[3] 丁文保[2] 李文辉[1] 

机构地区：[1]吉林大学计算机科学与技术学院,长春130012 [2]长春工业大学计算机科学与工程学院,长春130012 [3]西北工业大学软件与微电子学院,西安710072

出　　处：《计算机应用研究》2009年第5期1695-1699,共5页Application Research of Computers

基　　金：国家自然科学基金资助项目(60573182,69883004)

摘　　要：提出了一种基于着色算法的并行碰撞检测算法,利用AABB包围盒较好的紧密性和包围球计算简单的优点以及并行算法中的分治策略构建物体的混合包围体层次(S-AABB);然后采用破对称技术中的典型算法——着色算法,将每棵任务树编码,以产生各不相同的类别,并将不同的类别指派到不同的并行机,在并行机上采用多线程技术执行相同的类别的任务树的遍历,来检测是否有碰撞发生。实验结果表明,与现有的经典的I-COLLIDE等算法相比,该算法在效率、精确性方面具有明显优势,能够满足交互式复杂虚拟环境的实时性和精确性的要求。This paper presented a new parallel collision detection algorithm based on coloring algorithm. At first, incorporated the merits of both AABB bounding box and hounding spheres to construct a hybrid bounding representation of arbitrary nonconvex 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 multithread 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.

关 键 词：碰撞检测 混合包围体层次 并行技术 破对称 着色算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]