Abstract: A parallel collision detection algorithm is presented. The algorithm mostly builds balance-BoxTrees of every objects in environment using divide and conquer technologies in parallel algorithm, form traversing of a WorkTrees by traversing two BoxTrees and speeds up collision detection algorithm applying pipelining in parallel algorithm and traversing the WorkTrees by parting tenors. It also applies multi-threads in tenors thus it can run on both single processor computer and multi-processor computer.

Key words: collision detection, parallel algorithm, BoxTree, divide and conquer, pipelining

摘要： 提出一种基于并行的碰撞检测算法。该算法主要采用并行算法中的分治策略建立环境中每个物体的平衡包围盒树，通过遍历每两棵包围盒树形成对一任务树的遍历，采用并行算法中的流水线技术，利用划分进程遍历任务树从而加速碰撞检测算法。该算法在进程中也应用了多线程技术，因而能运行于单处理机和多处理机上。

关键词: 碰撞检测, 并行算法, 包围盒树, 分治, 流水线

CLC Number: 

• TP391