机器人仿真系统中碰撞检测算法的优化

郑尊鹏

青岛科技大学，山东青岛 266042

机器人仿真系统中碰撞检测算法的优化

郑尊鹏

青岛科技大学，山东青岛 266042

碰撞检测是机器人仿真系统中的重要问题之一。本文介绍了碰撞检测算法的基本分类，对层次包围盒的几种基本算法进行了分析比较，重点阐述了混合包围盒法，并将其应用于仿真系统中碰撞检测问题的解决，提高了检测速度、优化了检测算法。

仿真系统；碰撞检测；层次包围盒；混合包围盒

0 引言

在物理模型中检测运动物体是否相互碰撞的过程称为碰撞检测（Collision Detection,CD），也称为干涉检测或接触检测。碰撞检测是基于现实生活中一个普遍存在的事实：两个不可穿透的对象不可能共享相同的空间区域。

在机器人仿真系统中，经常需要对多个机器人在同一工作单元中的协同作业进行仿真。为避免因机器人的工作空间之间存在重叠交叉区域而发生相互干涉的问题，要引入碰撞检测来判定多个机器人在给定时间域内的同一时刻是否占有相同区域。碰撞检测是机器人仿真系统不可回避的问题之一，快速而有效的碰撞检测功能是仿真系统成功的关键。

1 碰撞检测算法

由于碰撞检测问题由来已久，在不同领域涌现出了许多碰撞检测算法。在这些算法中比较经典的研究成果包括空间分割法（space decomposition）和层次包围盒法（hierarchical bounding bolumes）及其一系列改进算法等。

空间分割法是将包含物体的虚拟空间分割为多个体积相等的小单元格，每个物体对应于一个或多个小单元中，碰撞检测时只需对占据同一单元格或相邻单元格的几何对象进行相交测试。比较典型的方法有k-d树、八叉树、BSP（binary space partitioning）树、四面体网和规则网格等。层次包围盒法是用几何特性简单的包围盒近似地描述虚拟场景中复杂的几何对象，进而通过构造树状层次结构逐步逼近对象的几何模型，直到几乎完全获得对象的几何特性。典型的类型有沿坐标轴包围盒AABB（axis-aligned bounding box）、包围球（spheres）、方向包围盒 OBB（oriented bounding box）、离散方向多面体k-DOP（k-discrete orientation polytopes）等。前者适用于对象较少且均匀分布的空间；后者适用于复杂环境中的碰撞检测，且应用广泛。

2 层次包围盒类型

2.1 AABB

AABB是指一个包含给定对象且各边平行于坐标轴的最小六面体，它需要6个标量来描述，即组成物体基本几何元素的顶点x、y、z坐标的最大值和最小值。AABB的紧密性相对较差，但计算十分简单。AABB的相交测试是比较简单的，两个对象当且仅当它们在3个坐标轴上的投影区间均重叠即相交；也是最快的，最多只需要6次比较运算。AABB间的相交测试和包围盒的更新速度比其他算法效率高，因此使用也最广泛。

2.2 包围球

包围球被定义为包含该对象的最小的球体，仅需两个标量描述，即球心和半径。包围球的计算时间多于AABB，但存储一个包围球只需两个浮点数，缩小了包围盒所需的存储空间。包围球的相交测试比较简单，是用球体包围整个几何体。包围球紧密性最差，故使用较少。

2.3 OBB

一个给定对象的OBB被定义为包含该对象且相对于坐标轴方向任意的最小的正六面体。OBB的紧密性最好，因其方向的任意性使它可以根据被包围对象的形状特点尽可能紧密地包围对象，大大提高了算法的效率。但这也使其相交测试变得复杂，不能有效处理变形体的碰撞检测。一般来说，OBB的总体性能优于前两种方法，并且实时性较高。

2.4 k-DOP

由于AABB和包围球的紧密性较差，而OBB的重叠测试和节点修改耗费又较高，所以提出了一种折中的k-DOP算法。k-DOP是一个凸多面体，它使用k/2对平行平面来包围物体。当k值取足够大时，k-DOP就发展成物体的凸包。

K的取值要根据碰撞检测的不同需要而定，通过调整k值，k-DOP可以在碰撞检测的简单性和包裹物体的紧密性之间灵活取舍，以满足特定的要求。k-DOP的紧密性要优于AABB，相交测试的复杂度要小于OBB，从而提高了碰撞检测的效率。

3 混合包围盒

对层次包围盒法来说，其自身的简单性和所包围物体的紧密性是相互矛盾的。简单性是指包围盒要比被包围的几何对象简单，既要求几何形状简单易于计算，又要求相交测试算法简单运算快速；紧密性则要求包围盒尽可能贴近被包围的对象。事实上，一种包围盒的简单性越高则紧密性越差，反之亦然，很难达到一定的平衡。

一般来说，AABB较适合于椭长形但与坐标轴夹角不大的物体，OBB则适合于椭长形且与坐标轴有一定夹角的物体；而包围球较适合于三个坐标轴上分布比较均匀或经常发生旋转运动的物体，k-DOP则适合用在表面结构比较复杂但不发生旋转的物体上。

为了既能利用包围盒的优点，又能避免它们的不足，可以采用混合包围盒法。即根据同一物体上不同的几何特征选用不同的包围盒，缩减可能发生碰撞的范围，并通过包围盒之间的求交运算，优化碰撞检测算法，提高碰撞检测的时效性。

4 结论

检测速度的提高是机器人仿真系统碰撞检测的核心问题。我们在七自由度机器人仿真控制系统中，结合机器人动作的轨迹采用了AABB-OBB混合包围盒法。在包围盒树的顶层采用AABB，在树的其他层次采用OBB，使AABB简单性好和OBB紧密性好的优点有效结合。从而实现了碰撞检测算法的优化，加快了检测的速度，提高了检测的实时性和可靠性。实验结果表明，比OBB算法提高了大约10%～15%。此算法可应用于形状复杂刚体的实时碰撞检测，并且场景规模越大，算法改进的效果越明显。

[1]崔汉国，陈军，王大宇.虚拟环境中优化的OBB碰撞检测算法研究[J].计算机工程与设计，2007(11)：2524-2526.

[2]申玉斌，蔡勇，华才健.虚拟环境中的碰撞检测技术的研究与应用[J].交通与计算机，2005(1)：23.

[3]蔡文军，陈虎.基于混合模型的碰撞检测优化算法研究[J].计算机与现代化，2006(7)：49-52.

TP24

A

1674-6708（2011）48-0191-01