船舶维修中基于包围盒的碰撞检测算法

徐鹏 罗恒

摘 要：针对船舶维修中管路设备无三维放样的情况，导致管路设备间存在一定的干涉，为便于维修过程中的施工、减少返工，急需一种基于包围盒的碰撞检测算法。根据舰船具体特点和实际需要，从管路设备的空间几何位置关系出发，采用了基于球包围盒和轴对称包围盒的混合层次包围盒方法的碰撞检测算法，在判断碰撞分析时运用基于混合积的线段相交判定方法。结果表明：混合層次包围盒方法的碰撞检测算法较传统方法简单易于实现，运算速度快，可分析判断管路设备的干涉情况，从而有效的避免维修中管路设备的干涉，该包围盒碰撞检测算法能极大缩短工程周期和节约成本。

关键词：碰撞检测;混合层次包围盒;混合积;干涉

1引言

在船舶维修中经常会遇到一些设备、管路被拆卸、重新制作、更换回装，由于船舶上一些舱室部位设备、管路诸多且管路走向较为复杂，而重新制作的设备、管路会导致外形尺寸误差，同时回装时设备管路位置的变化会导致回装时发生干涉。在船舶维修中一旦发生碰撞干涉现象，需对设备、管路进行改进或将其安装位置进行变更，会导致工程的各种返工，同时维修性分析中碰撞检测贯穿于产品设计的整个阶段[1]，因此在船舶维修中对设备、管路间的干涉碰撞检测的研究十分重要。

船舶中的设备管路间的干涉，对应的是几何空间上三维实体的的碰撞检测。碰撞检测是虚拟现实、计算机图形学中最基本且非常重要的组成部分，在计算机和工业应用领域应用十分广泛。针对碰撞检测问题，国内外已经开展了大量的算法及其研究工作。根据三维空间上的物体，Lin[2]主要做的是静态干涉检测算法;国内部分高校的研究，如清华大学[3]、上海交通大学[4]、浙江大学[5]等主要从事基础研究工作，他们的研究均取得了一定的进展。从物体的三维几何特性出发，根据物体实际特点来进行几何计算，从而有了层次包围盒法[6]和空间分割法等成熟算法[7-8]，但是这些研究的大部分碰撞检测算法，基本都是根据具体的应用场合来设定，从而应用上具有一定的局限性，且算法的效率还不是很高。本文从三维实体的几何空间角度出发，运用球包围盒和轴对称包围盒混合的层次包围盒法，使碰撞检测算法易于实现、简单可靠且效率较高，实用性较强。

2基本原理

2.1碰撞检测算法

一般情况下，根据时空来判断检测算法，该算法可以分为基于时间域的碰撞检测算法和基于空间域的碰撞检测算法两类[9]。碰撞检测在CAD/CAM、计算机动画、机器人、路径和运动规划、模拟驾驶等领域有着广泛的应用，而碰撞检测是通过布尔运算来判断是否发生碰撞。一般工程应用主要是空间域上的碰撞检测算法，运动过程中的碰撞检测算法是基于时间域，其具体分类如图1所示：

2.2包围盒检测方法

根据图1，文章采用的碰撞检测算法是基于空间域的，在空间域的碰撞检测中，常用包围盒方法有：包围球（Sphere）、沿坐标轴的轴向包围盒（AABB Axis-Aligned Bounding Boxes）、方向包围盒（OBB Oriented Bounding Box）、固定方向凸包（FDH Fixed  Direction Hull或K-Dops Discrete Orientation Polytope）等。三维空间实体中的AABB包围盒具有表现形式为六面体、六面体中的每条边都平行于一个坐标平面的特点，故求取简单，不仅适合于刚体的检测，也应用于软体中，在大多数碰撞检测算法中得到良好应用。包围球的相交测试通过球心和半径来判断，因此判断起来较快速简单，具有实时检测过程中不再更新的特点，因此可以先通过该方法来快速判断那些不相交的三维实体，极大缩短了相交判断测试时间[5，10]。针对这些包围盒适用范围，结合实船设备管路几何特点，本文采用包围球和AABB包围盒相结合的包围盒检测算法，可结合发挥这两种方法的优势，提高运算效率和缩短时间。

2.3 层次包围盒树检测方法

所谓的层次包围盒树，根据其具体含义，即树结构树节点数据值由包围盒构成，具体几何定义为：假设给定物体W，集合S表示为W中所有包含基本几何元素的集合，将该几何元素集定义为一棵树，树是基于集合S上的包围盒层次结构，则称为层次包围盒树，所具有的性质[11]如下：

（1）树中的每个节点v与S的一个子集相对应;

（2）节点v的数据值为集合S的包围盒;

（3）根结点对应于全集S，其数据值为全集S的包围盒;

（4）树中的每个叶节点指向的是物体W的几何基本元素。

根据上述定义及性质，将物体的多个包围盒按照树来进行划分，一棵层次包围盒树为完全的当且仅当该树中每个叶节点对应于S的一个单元素子集，也就是只包含一个基本几何元素。由此可知，层次包围盒树与一般的树形结构不一样，在构造的时候，需要考虑每个节点上的基本几何元素子集及包围盒的几何特性，这也是所需特别注意地方。

3算法实现

对于空间实物体，首先获取实物的几何数据，根据设计绘制的设备、管道三维实体提取得到三维数据，然后将三维数据导成STL数据，将实物用许多三角面片表示，如某三角形面片A，存储表示为Triangle A（Point Pa，Point Pb，Point Pc，Point Pn，），其中Pa、Pb、Pc分别表示三角形的三个顶点，Pn表示三角形面片的法向量，Point表示为P（x，y，z）。因此可利用三角面片表示法来存储空间任意三维实体。针对船舶维修中设备、管路的碰撞，本文采用了基于包围球、包围盒混合的碰撞检测算法，主要是该算法构造和相交测试都比较简单、容易实现，并且具有算法计算速度较快等优势。采用的层次包围盒方法，还可递归地对包围盒进行逐次划分，将划分后的包围盒更加紧密地包围物体，划分越多表达越准确，越能代表实物体。只有当将两物体包围起来的包围盒发生相交时，才需要进一步对物体间进行相交判断测试。碰撞处理一般分为碰撞检测、碰撞确定、碰撞响应三步。算法实现的具体流程如图2所示。

3.1步骤一：包围球、AABB包围盒间相交测试

对于给定的实体对象，依照前面三角面片表示方法，首先需分别计算所有三角面片中所有顶点的X坐标、Y坐标和Z坐标均值，以确定包围球的球心Q点，由球心Q与三个最大坐标值所确定的点间距离来计算半径r。判断包围球间的相交测试比较简单，对于两个包围球Q1和Q2，只需要判断两球心距離和半径之间的关系，如果球心Q1、Q2间的距离小于半径之和：，则判定两包围球相交[12，13];反之，两包围球相离。

两个AABB包围盒相交当且仅当它们在三个坐标轴上的投影区段都有重叠，所以这里将AABB包围盒的相交测试转化到一维空间来解决，通过对AABB包围盒在x、y、z三个坐标轴上的投影排序来确定相交的AABB包围盒，可采用希尔排序[14]。

假设两个实物对象的包围矩形分别为P、Q，对应的各自顶点参数为、，则两物体是否相交判断如下[11]：

（1）Ifor，then判断两矩形P和Q不存在相交;otherwise，If，then判断矩形P和Q可能相交，需进步判断是否相交，转入步骤（2）;

（2）Ifor，then矩形P和Q不相交;otherwise，，then矩形P和Q可能相交，需进步计算判断，此时转入步骤（3）;

（3）Ifor，then矩形P和Q不相交;otherwise，，then判断矩形P和Q一定相交。

3.2步骤二：层次包围盒树的遍历

在众多碰撞检测算法中，基于层次包围盒树的碰撞检测算法是目前运用得较多也是相对比较成熟的碰撞检测算法。此类算法一般流程如下图3：

3.3步骤三：三角形之间的相交测试

首先将两物体的包围盒树遍历各自叶节点，判断叶节点是否相交，此时碰撞检测算法进行算法的最底层--基本几何元素间的相交测试。三角形之间的相交测试结果，将直接关联到物体碰撞检测的结果，即If三角形间相交，then判定两物体发生碰撞;otherwise继续进行其它三角形对的相交测试判断。最终相交测试结果：If所有三角形对间均为不相交，then判定两物体不相交。碰撞检测过程中，只要有一对三角形相交，则立即停止三角形对的相交测试，返回碰撞结果，触发碰撞响应[15]。

不妨假设顶点均已知的三角形对ABC、DEF，则对这两个三角形按照下面给出的步骤判断它们是否发生相交。

步骤1：判定其中一个三角形ABC的支撑超平面是否与另一个三角形DEF相交。

计算支撑超平面的法向量（设A点的坐标为（，，），，同理可得到B、C、D、E、F的坐标向量），令、、，对以下几种情况进行判断：①若sd、se和sf全部为正值或者全部为负值，说明DEF的三个顶点都位于支撑超平面的相同的一侧，因此两个三角形不相交。②倘若sd、se和sf均为零值，说明两个三角形共面，此时将两个三角形投影到二维平面，从而转换成二维空间的相交测试。

步骤2：计算出三角形ABC和三角形DEF所在平面间的交线，这条线段位于平面上。如果这条线段与三角形DEF相交，线段与三角形边相交的判断可用混合积法[3，16，17]，或者完全包含于三角形DEF中，则两三角形相交，否则不相交。

3.4步骤四：得出碰撞检测结果

一旦有检测到有三角形发生相交，则立即停止碰撞检测，输出碰撞结果;以此类推，遍布实物体W1、W2中所有的三角形面片，若都不相交，则实物体也不相交。

4应用及结论

根据系统设计要求，在Proe软件中绘制三维实体，并将三维实体以三角形面片形式保存为STL格式的数据文件;然后将STL格式文件读入到程序中，根据上述算法实现步骤及相关要求，先将一个个实物体按照三角面片且带法向量来存储;对于多个实物体，需要构建层次包围盒树，将树的节点存储为一个个实物对象;然后遍历层次包围盒树，分别对要分析的实体进行干涉碰撞情况判断，管路设备的干涉情况具体如下图4。

若发现管路设备存在干涉碰撞情况，可进行如下处理：一是将干涉设备或者管路进行移位，在不影响其他物体干涉碰撞情况下，将干涉物体间的距离变大，即可消除存在的干涉管路设备;另外一种方法，改变干涉部位的形状，在不影响两物体性能及要求情况下，对两物体要干涉的局部部位形状进行改变，从而有效避免干涉碰撞。总之，在船舶维修中，经常对船舶管路设备进行局部维修，若未经过判断直接将管路设备安装到船上，安装后则很可能会出现干涉情况，从而导致设备管路安装的返工，同时需要根据现场安装情况进步判断干涉，这样将会导致工程的返工，还有可能影响原来船上的管路设备，导致在安装过程中，损坏原有部件，造成的损失不可估量。如果在管路设备安装前，对管路设备的干涉进行判断，在制作管路设备时就考虑到干涉情况，即可避免工程的返工，大大缩短工程的周期，减少人力、物力等经费。

5结论

本文从几何空间角度出发，分析了空间实物干涉碰撞的可能性，运用球包围盒和轴对称包围盒混合的层次包围盒法，该方法易于实现、简单可靠。基于几何空间位置的碰撞分析方法，引入了基于混合积的线段相交的判定方法，提高了碰撞分析的运算速度;基于包围盒的碰撞检测算法有效地解决了船舶维修中三维实体干涉碰撞问题，能缩短工程周期及减少各项费用。

参考文献：

[1]汤鹏.维修性分析与仿真中的高效碰撞检测算法研究[D].长沙：国防科学技术大学，机械工程.

[2]Lin M C， Gottschalk S. Collision detection between geometric models： a survey[C].Proc of IMA Conference on Mathematics of Surfaces.1998： 37-56.

[3]王浩，张航义.一种适合多机空战仿真的碰撞检测算法及应用[J].系统仿真学报，2004， 16（9）： 1931-1934.

[4]邓琛，张琴舜.虚拟现实系统中碰撞检测技术初探[J].微型电脑应用，2002，19（8）：55-56.

[5]范昭炜.实时碰撞检测技术研究[D].杭州：浙江大学，2003.

[6]胡祥潇.一种三维碰撞检测并行算法的设计与实现[D].武汉：华中科技大学，计算机应用技术.

[7]王志强，洪嘉振，杨辉.碰撞检测问题研究综述[J].软件学报，1999，10（5）：545-551.

[8]李芙玲，张瑾.碰撞检测技术研究[J].华北科技学院学报，2006，1（2）：71-73.

[9]姜光焱.基于包围盒的碰撞检测算法的研究及应用[D].成都：电子科技大学，信号与信息处理.

[10]陈学文，丑武胜，刘静华等.基于包围盒的碰撞检测算法研究[J]. 计算机工程与应用， 2005，41（5）： 46-50.

[11]高玉琴.三维空间中碰撞检测算法的研究[D].武汉：华中科技大学，计算机应用.

[12]章勤，黄琨，李光明.一种基于OBB的碰撞检测算法的改进.华中科技大学学报（自然科学版）， 2003.1（6）：52-58.

[13]Antonio Benitez， Maria del Carmen Ramirez， Daniel Vallejo.  Collision Detection Using Sphere-Tree Construction[C].In：Proceedings  of the 15th International Conference on Electronics， Communications  and Computers （CONIELECOMP05）.NW Washington， DC USA：  IEEE Computer Society，2005：286-291.

[14]王晓荣，王萌，李春贵.基于AABB包围盒的碰撞检测算法的研究[J].计算机工程与科学，2010，32（4）：59-61.

[15]邹益胜，丁国富，何邕等.空间三角形快速相交检测算法[J].计算机应用研究，2008，25（10）：2906-2910.

[16]肖翔.基于幾何的三维地下供水管网碰撞分析[D].武汉：华中科技大学，模式识别与智能系统.

[17]王舒鹏，方莉.混合积判断线段相交的方法分析[J].电脑开发与应用， 2006， 19（10）：34-35.