Abstract: A collision detection algorithm based on mixed bounding box was proposed using k-dops and bounding sphere between complex objects. In the preliminary period, bounding box binary tree of the objects was established. A k-dops was established at the inner layer of node and a bounding sphere was established at the outer layer of node. In collision detection period, firstly the intersection test used sphere-sphere method for fast overlap test in outer layer, eliminating the possibility of collision between objects far apart. Then it accurately determined the contact status among objects in closer proximity by kdops-kdops test in inner layer. The experimental results, compared with that of QuickCD, show that the proposed algorithm is efficient in collision detection between complex objects.

Key words: collision detection, bounding sphere, k-dops, mixed bounding box

摘要： 提出了一种基于k-dops包围盒与包围球相结合的碰撞检测算法。预处理阶段为几何对象构造包围盒二叉树，其中节点的内层构造k-dops包围盒，节点的外层构造包围球。碰撞检测阶段，首先利用包围球快速排除不可能发生相交的物体，然后利用k-dops包围盒进一步精确地判断物体对是否发生相交。通过与QuickCD算法的性能进行比较，证明了这种混合包围盒能够有效地提高复杂结构几何体之间碰撞检测的效率。

关键词: 碰撞检测, 包围球, k-dops, 混合包围盒