基于改进OBB包围盒的碰撞检测算法*

史旭升，乔立红，朱作为

(北京航空航天大学 机械工程及自动化学院先进制造技术与系统研究中心，北京 100191)

车铣复合加工作为一种先进的加工技术，在加工复杂的高精密零件和异形零件等领域都有不可替代的地位.车铣复合加工机床包含多主轴多刀架结构，在精密微小零件的高速加工过程中，多把刀架在狭小的空间中同时加工零件，刀架之间极易发生干涉碰撞现象[1].

随着计算机技术的发展，虚拟仿真技术在降低成本、提高效率方面都有显著优势.碰撞检测算法主要有空间分解法和层次包围盒法两种算法，其核心思想都是尽可能减少相交测试对象的数目来提高检测速度.空间分解法适用于在稀疏的环境中分布比较均匀的几何对象间的检测，层次包围盒法则应用更为广泛，适应复杂环境中的碰撞检测[2].车铣复合加工环境复杂，运动对象多，因此，在本研究中选用了基于层次包围盒的方法.传统检测方法是进行一次或多次试切、不断调试，直到确认能够完成预定的加工要求，该方法效率低、周期长、成本高.为了提高检测效率，基于虚拟仿真技术的碰撞检测算法[3-7]，为数控加工方案的修正提供了依据，但是在修正过程中需要工艺人员根据经验预估修正方式，由预估引起的不确定性和偶然性，给生产计划带来一定风险，如果不能及时解决可能影响生产进度.为了避免盲目预估，减少反复修正的次数，提高准确率，保证精度，本文提出了基于改进OBB包围盒的快速碰撞检测算法.

1 问题描述

现有研究倾向于通过碰撞检测确定发生碰撞的对象，没有考虑具体的交点信息.数控加工仿真软件给出的碰撞检测结果是加工过程中发生碰撞的对象，这些碰撞检测数据可以基本满足数控加工仿真的需求[1].但是由于碰撞结果比较笼统，需要反复调整或校正加工速度、切削量或刀具伸长量等方式来修正.为了避免盲目的参数预估，减少反复修正的次数，提高准确率保证精度，准确计算出三角面的初始碰撞时间和碰撞位置显得尤其重要[8].针对车铣复合数控加工仿真碰撞检测精确度低的问题，本文提出了一种基于改进OBB包围盒的碰撞检测算法.

2 碰撞检测算法

碰撞检测算法分为3个部分：预处理阶段、粗检阶段和精检阶段.该算法以车铣复合加工仿真碰撞检测信息作为输入，计算出碰撞单元组之间发生的初始碰撞时间和位置.

2.1 创建OBB包围盒及层次包围盒树

车铣复合加工碰撞检测预处理阶段的主要内容是创建碰撞单元组对象的包围盒及层次包围盒树.具体步骤如下：

步骤1创建车铣复合加工仿真环境.主要是车铣复合加工机床组件的创建，如刀具、刀架、主轴等，根据机床的运动学关系，建立机床运动学模型.

步骤2车铣复合加工仿真碰撞检测.通过创建加工方法和加工操作，利用数控仿真软件进行车铣复合加工仿真，并进行碰撞检测.

步骤3获取车铣复合加工仿真过程中发生碰撞的碰撞组信息.设碰撞单元组信息表示为:

(1)

M={M1,M2,…,Mk]

(2)

步骤4创建OBB包围盒.根据碰撞单元组对象所包含的三角面片信息，创建相应的OBB包围盒，分别标记为包围盒A和包围盒B.

步骤5创建OBB层次包围盒树.以八叉树的形式进行空间划分，按照“自上而下”的方法创建层次包围盒树，分别标记为OBB_A和OBB_B.

层次包围盒树子节点主要分为3种类型，即实节点、空节点和灰节点.当叶子节点与几何对象实体完全重合时用实节点表示，当叶子节点与几何对象实体部分重合时用灰节点表示，当叶子节点与几何对象实体分离时用空节点表示.这样叶子节点中就储存了离散表面所包含的三角面片数据，用于精确碰撞检测.

其中空节点不包含几何实体，在计算中被剔除，减少运算节点数目；实节点与几何对象完全重合，认为该节点是最末端子节点，不需要再分割，可直接用于下一步进行精确碰撞检测计算；灰节点包含几何对象以外的空间，直接用于精确碰撞检测可能引起伪碰撞现象，所以如果灰节点存在碰撞现象，需要进一步分割，直到满足设定的层次包围盒深度或者所有叶子节点都是空节点或实节点为止，如果灰节点不存在碰撞现象，则不需要进一步分割，减少不必要的节点数目和存储数据.

在建立层次结构时，层次结构树深度的确定需要遵循两个原则：划分深度不宜太大，从而在遍历时，只需很少的步数，就能完成从根节点到叶子节点的搜索；划分深度不宜太小，否则每个子节点内包含的三角面片数量太多,加重了精确检测的计算压力.层次包围盒树子节点的深度与几何模型及其精度相关[9]，本文结合检测对象的几何模型及精度，设层次包围盒树子节点最大深度为6.

2.2 基于分离轴定理的初始碰撞检测

碰撞检测的粗检阶段是基于分离轴定理，通过广度优先搜索的策略遍历层次包围盒树子节点，快速剔除不发生碰撞的子节点，当发生碰撞的节点不可分割时，则记为：

(3)

W={W1,W2,…,Wk}

(4)

对于一对OBB，需测试15条可能的分离轴(每个OBB的3个面方向，每个OBB的3条边方向的两两组合)，只要找到一条这样的分离轴，就可以判定这两个OBB是不相交的.如图1所示为分离轴定理示意图，其中L表示两个包围盒的某一分离轴，Oa和Ob分别表示两个包围盒的中心位置，S是包围盒中心位置在分离轴上投影的距离，ra和rb是包围盒在分离轴上投影的距离，当存在分离轴使S>ra+rb时，则OBB处于分离状态，反之则视为相交.在某些情况下，该算法会将分离的盒体报告为相交，但不会遗漏相应的碰撞结果，在初始碰撞检测阶段该算法计算简单，能够快速剔除不发生碰撞的包围盒.

图1 分离轴定理示意图

2.3 基于三角面片的精确碰撞检测

碰撞检测的精检阶段是应用分离轴定理，判断碰撞节点所包含的三角面片之间的相交情况，然后应用回退技术，计算出三角面片发生碰撞的初始碰撞时间和碰撞位置.

已知在粗检阶段计算得到相交包围盒节点集合：W={W1,W2,…,Wk}.设Wk1是包围盒节点集合W的第k个元素中层次包围盒OBB_A的节点，Wk2是包围盒节点集合W的第k个元素中层次包围盒OBB_B的节点.应用分离轴定理考查11个分离轴(平行于两个三角形面法线的两个轴，两个三角形之间的9种边边组合).若两个三角形在任一分离轴上的投影区间不相交，则两个三角形分离；若投影区间在所有分离轴上都相交，则两个三角形必定相交.把发生相交的三角形组记为：

(5)

Q{Q1,Q2,…,Qn}

(6)

关于初始时间及位置的计算和改进方法将在第4节进行详细阐述.

3 改进的OBB包围盒算法

3.1 传统OBB包围盒算法

创建OBB包围盒时，确定包围盒的中心位置和最佳方向是关键.传统算法是根据几何模型的三角面片信息，利用均值和单位化协方差矩阵的统计量来计算包围盒的位置和方向.已知组成几何对象的基本几何元素为三角形，设包含的三角面片数为n，且第i个三角形的顶点坐标为(pi,qi,ri)，则包围盒的中心位置为：

(7)

由于该算法是各三角形顶点的简单平均，如果几何体结构不均匀，在体积相等的区域，有的部分三角面片数量多，有的部分三角面片数量少，这样计算出来的包围盒就会向三角面片数量多的部分偏移(如图2(a)所示).显然这将导致一部分包围盒在几何体外面，使碰撞检测出现误检的现象.

3.2 改进的OBB包围盒算法

为了解决传统包围盒算法计算结果不准确的问题，本文提出区域加权的改进算法，该算法的核心思想是把几何对象划分为表面积相近的i个区域，分别计算每个区域的中心坐标mi，再求这几个区域中心坐标的平均值：

(8)

(9)

碰撞单元组对象的结构存在很大不确定性，无法采用统一的表面积划分方法.本文采用人机交互的方式，借助CAD软件的“分析-测量面”获取几何形面表面积的功能，把产品划分为几个相近的区域，根据产品结构可划分为3～5个区域.本文把万向节零件划分为3个表面积相近的区域(如图2(b)所示)，通过采用改进的OBB包围盒算法，使矫正之后的包围盒紧紧地包围物体(如图2(c)所示).

(a)改进前

(b)区域划分

(c)改进后

4 初始碰撞时间及位置的计算

4.1 初始碰撞时间的计算

设在t=Tk时刻车铣复合加工发生碰撞现象，由于仿真精度和系统反应时间的问题无法保证Tk就是物体之间的初始碰撞时间.本文应用回退技术计算初始碰撞时间.

设两个三角面片在某个临近时间t=T0时未发生相交，则第一次发生碰撞的时间为t=T(T0

T0是三角面片相交之前的某个时间，如何选择T0直接影响初始时间的计算效率.假设在Tk时刻两个三角面片相交，则回退的最大时间差表示为Δt，则Δt={N/(|va-vb|·L)}，其中N表示两个三角形中最长的边，va和vb分别表示两个三角面片的运动速度，L是三角形的分离轴，则T0=T-Δt.在区间t∈[T0,T)内做回退处理，回退次数是可控的，可以通过增大三角形剖分的精度来减少回退次数.设时间t的步长为0.02 s，在测试中发现，回退次数一般不大于5.

在应用回退技术的过程中，需要推导出时间区间t∈[T0,T)内每个回退点的位置信息.这里应用洛伦兹变换理论，根据三角面片的顶点坐标和运动状态v，可以计算出任意时刻的三角面片位置信息.

通过遍历集合Q{Q1,Q2,…,Qn}包含的所有元素，并应用回退技术计算出每对相交三角面片的初始相交时间，得出集合：

T{T1,T2,…,Tn}

(10)

比较集合T中的元素，则最小时间为检测对象初始碰撞时间记为Tmin.

4.2 初始碰撞位置的计算

两个三角形初次相交时，必交于一点或者一条线段.若Tmin对应的三角面片对数目大于1，则三角形相交于一条线段.

设△ABC和△DEF是Tmin时相交的一对三角形.设E1=B-A,E2=C-A和E3=E2-E1为△ABC的三条边，N1=E1×E2为法线，{A+x1E1+x2E2}表示△ABC包含的点，其中(0≤x1≤1,0≤x2≤1,x1+x2≤1).L1=E-D，L2=F-D和L3=L2-L1为△DEF三条边，N2=L1×L2为法线，△DEF包含的点记为：{D+y1L1+y2L2}，其中(0≤y1≤1,0≤y2≤1,y1+y2≤1).

则初始碰撞位置就转换为计算Tmin时两个三角形交点P的问题，即求解:

A+x1E1+x2E2-Tva=

D+y1L1+y2L2-Tvb

(11)

其中T=Tk-Tmin，va是碰撞检测对象A的运动速度，vb是碰撞检测对象B的运动速度.

设初始相交位置在△DEF的任意一条边上，则有y1=0,y2=0;y1=1,y2=0和y1=0,y2=1三种情况.筛选出满足条件(0≤x1≤1,0≤x2≤1)的x1和x2.如果x1或x2不在[0,1]范围内，则假设不成立.重新假设初始相交点的位置在△ABC的任意一条边上，同理，根据x1=0,x2=0;x1=1,x2=0和x1=0,x2=1三种情况，筛选出满足条件(0≤y1≤1,0≤y2≤1)的y1和y2.因为三角形相交，所以一定能计算出满足条件的系数x1，x2或系数y1，y2.

若计算出满足条件的(0≤x1≤1,0≤x2≤1)的x1和x2.则把相应的y1和y2代入D+y1L1+y2L2-Tvb得交点P的坐标.反之，则把x1和x2代入A+x1E1+x2E2-Tva得交点P的坐标.

如果以每种假设为计算单元，本文提出的假设算法总共需要计算3+3=6次.

常用基于分离轴的测试方案[10]，分别计算11个分离轴情况下，每一类分离轴有不同的3种情况(详细内容见文献[10])，计算出相应的x1和x2的系数，满足条件时，则根据系数计算出P点的坐标.计算11×3次.

区间相交算法是一种类似于分离轴测试的改进方案[6].该算法先计算出两个三角形所在平面的交线，然后比较分离轴中与交线L最接近平行的一条分离轴，测试在3种假设情况下满足条件的系数，再计算出P点的坐标.计算11+3次.

综上所述，本文关于三角面片相交位置的计算次数比分离轴算法的计算次数少了80%，比区间相交算法的计算次数少了50%，明显提升了计算效率.

5 实例验证

5.1 OBB包围盒的创建

本文以某型号万向节零件的车铣复合加工为例，进行碰撞检测算法实例验证.以CAD软件为仿真平台，创建了用于车铣复合加工仿真的机床、刀具、工件和夹紧装置等三维模型，配置机床的运动学关系，选择数控系统为simens840D.仿真碰撞检测结果显示共发生碰撞次数为15次.

本文以数控加工3分12秒时刀架1与刀架2发生的碰撞为例.由发生碰撞的时间和工艺过程推算得出，刀架1车削万向节外圆和刀架2钻削万向节轴向孔时刀架1的刀具和刀架2的刀座发生了碰撞.相应的碰撞信息描述为：

应用改进的OBB包围盒算法得出：刀架1上车刀的包围盒中心坐标Oa(91.5,151.5,0)，半轴长分别为(71,67.5,50)，方向轴坐标为(保留小数点后两位)(-0.48,-0.72,-0.50;0.68,-0.67,0.31;-0.56,-0.19,0.81)；刀架2上钻刀刀座的包围盒中心坐标Ob(217.5,0,0)，半轴长分别为(55,170,170)，(1,0,0;0,1,0;0,0,1)为方向轴坐标.根据八叉树空间分割法，可以计算出OBB层次包围盒树的每一个节点和子节点的包围盒中心坐标及半长轴尺寸.

5.2 计算结果

通过粗检阶段得出，发生相交的子节点集合：

W={W1,W2,W3,W4,W5}

其中：

通过精检阶段得出，发生相交的三角面片有93对.初始碰撞时间为工步2加工运行到17.83 s，初始碰撞位置为P(132.5,36.4,0).图3为数控加工仿真碰撞示意图.其中碰撞对象A为车刀，运动速度为va，碰撞对象B为钻刀刀座,运动速度为vb，加工对象W为工件，A沿着工件径向竖直向下做直线运动，B沿着工件轴线方法向左做直线运动.在局部放大示意图中，相交区域用C表示，点P为发生初始碰撞的位置.

在车削外圆与钻削轴向孔时，刀架1的车刀与刀架2的钻刀刀座发生碰撞.有以下4种修正方案：

方案1.增加钻刀的伸长量.把钻刀的伸长量由50 mm调整到56.2 mm以上，使钻刀刀座与车刀距离增加，有可能避免碰撞现象；

方案2.增加车削加工车削速度.把车刀的切削速度增加到2.5 mm/s以上，使钻刀与车刀在碰撞区域的运动轨迹产生时间差；

图3 数控加工仿真碰撞示意图

方案3.减小钻削速度.钻刀的切削速度减小到0.7 mm/s以下，使钻刀与车刀在碰撞区域的运动轨迹产生时间差；

方案4.调整工艺方案.将车削加工与钻削加工分开加工.

以上4种方案中，方案1最方便快捷，且能保证切削效率和精度.方案2和方案3分别通过增加和减小加工参数避免干涉碰撞发生.如果参数修改幅度太大，会影响到加工效率和精度.方案4如果只是将车削加工与钻削加工分为两个工步进行加工，将影响加工效率.由于碰撞现象发生的情况各异，暂时还无法用统一的标准规定修正方案，详细修正计算过程这里不展开论述.本文采用方案1修正碰撞现象.经验证有效避免了碰撞现象.如图4所示为车铣复合加工碰撞检测流程示意图.

图4 碰撞检测计算流程图

6 结 论

本文创建的车铣复合加工仿真环境比CAM软件通过刀位文件仿真更真实，更接近实际加工情况，提供了可靠的碰撞检测信息.在预处理阶段，建立了改进的OBB包围盒及其层次包围盒树；在粗检阶段和精检阶段，基于分离轴定理和回退技术，计算出了初始碰撞时间及位置.实例验证结果表明，计算结果准确，为操作人员进行加工修正提供了可靠的依据，避免了盲目的参数预估，减少反复修正的次数，提高了效率，对车铣复合加工和制造也具有很重要的意义.

[1]吴宝海,严亚楠,罗明,等.车铣复合加工的关键技术与应用前景[J].航空制造技术,2010(19):42-45.

WU Bao-hai,YAN Ya-nan,LUO Ming,etal.Key technology and application prospect of turning/milling machining [J].Aeronautical Manufacturing Technology,2010(19):42-45.(In Chinese)

[2]KOCKARA S,HALIC T,IQBAL K,etal.Collision detection: a survey[C]//IEEE International Conference on Systems,Man and Cybernetics.Montreal Canada:IEEE,2007:4046-4051.

[3]郑锦铜,江铭鸿.刚性基础上摇晃桥柱系统地震反应研究[J].湖南大学学报：自然科学版,2013,40(4):32-41.

ZHENG Jin-tong,JIANG Ming-hong.Seismic response of rocking pier system on rigid foundation[J].Jounral of Hunan University: Natural Sciences,2013,40(4):32-41.(In Chinese)

[4]孟志强,何涛,尹望吾,等.六角弹簧管汽车碰撞吸能装置的效能研究[J].湖南大学学报：自然科学版,2011,38 (11):43-46.

MENG Zhi-qiang,HE Tao,YIN Wang-wu,etal.Research on the performances of hexagonal spring tube energy-absorbing device for car crash[J].Jounral of Hunan University: Natural Sciences,2011,38(11):43-46.(In Chinese)

[5]PAZOUKI A,MAZHAR H,NEGRUT D.Parallel collision detection of ellipsoids with applications in large scale multi body dynamics[J].Mathematics and Computers in Simulation,2012,82:879-894.

[6]JIA Xiao-hong,CHOI Yi-king,BERNARD Mourrain,etal.An algebraic approach to continuous collision detection for ellipsoids[J].Computer Aided Geometric Design,2011,28: 164-176.

[7]CHANG Jung-woo,WANG Wen-ping,KIM Myung-soo.Efficient collision detection using a dual OBB-sphere bounding volume hierarchy[J].Computer-Aided Design,2010,42(1): 50-57.

[8]黄通浪,唐敏,董金祥.一种快速精确的连续碰撞检测算法[J].浙江大学学报:工学版,2006,40(6):1051-1055.

HUANG Tong-lang,TANG Min,DONG Jin-xiang.Fast and accurate continuous collision detection between rigid bodies[J].Journal of Zhejiang University: Engineering Science,2006,40(6):1051-1055.(In Chinese)

[9]康勇,熊岳山,费先宏,等.基于空间分解和包围盒层次的混合碰撞检测算法[J].计算机仿真,2010(6):191-193.

KANG Yong,XIONG Yue-shan,FEI Xian-hong,etal.A hybrid collision detection algorithm based on spatial partitioning and bounding volume hierarchy[J].Computer Simulation,2010(6):191-193.(In Chinese)

[10]David eberly geometric tool LLC.Dynamic collision detection using oriented bounding boxes[EB/OL].[2013-09-21].http://www.geometrictools.com/.