基于改进OBB包围盒的碰撞检测算法
2014-08-08史旭升乔立红朱作为
史旭升+乔立红+朱作为
文章编号：16742974(2014)05002606
收稿日期：20130925
基金项目：国家科技重大专项项目（2011ZX04016-021）；北京市教育委员会共建资助项目
作者简介：史旭升（1983-），男，陕西蒲城人，北京航空航天大学博士研究生
通讯联系人，E-mail: lhqiao@buaa.edu.cn
摘 要： 针对车铣复合数控加工仿真碰撞检测精确度低的问题，提出了一种基于改进OBB包围盒的快速碰撞检测算法.该算法基于改进的OBB包围盒算法，利用车铣复合加工仿真碰撞检测的结果，创建碰撞单元组的包围盒及层次包围盒树；通过粗检阶段计算出包围盒树的相交节点集合，计算得到发生碰撞的三角形面片集合；应用回退技术，解得初始碰撞时间及位置.实例验证结果表明，该算法有效提高了车铣复合数控加工碰撞检测的精确度.
关键词：车铣复合；碰撞检测；OBB（Oriented Bounding Box）包围盒；分离轴定理；三角面片
中图分类号：TP391 文献标识码：A
Algorithm of Collision Detection Based
on Improved Oriented Bounding Box
SHI Xusheng，QIAO Lihong，ZHU Zuowei
(Advanced Manufacturing Technology and Systems Research Center, School of Manufacturing
Engineering and Automation,Beihang University, Beijing 100191, China)
Abstract:To solve the problem of the low precision of collision detection in the turnmill combined machining simulation, a rapid collision detection algorithm based on the improved theory of Oriented Bounding Box was proposed. This algorithm, based on the improved oriented bounding box, and using the collision detection result as the input, creates the oriented bounding box and hierarchical bounding box tree of the collision unit group. During the rough detection phase, the intersecting nodes are detected. In the following precise detection phase, the triangular patches of the objects in collision are detected. With the application of feedback technology, the initial time and position of the collision are calculated. A case study shows that this algorithm increases the efficiency and precision of the collision detection in numerical control simulation.
Key words: turnmilling; collision detection; OBB(Oriented Bounding Box); SAT(Separating Axis Theorem);triangular patches
车铣复合加工作为一种先进的加工技术，在加工复杂的高精密零件和异形零件等领域都有不可替代的地位.车铣复合加工机床包含多主轴多刀架结构，在精密微小零件的高速加工过程中，多把刀架在狭小的空间中同时加工零件，刀架之间极易发生干涉碰撞现象[1].
随着计算机技术的发展，虚拟仿真技术在降低成本、提高效率方面都有显著优势.碰撞检测算法主要有空间分解法和层次包围盒法两种算法，其核心思想都是尽可能减少相交测试对象的数目来提高检测速度.空间分解法适用于在稀疏的环境中分布比较均匀的几何对象间的检测，层次包围盒法则应用更为广泛，适应复杂环境中的碰撞检测[2].车铣复合加工环境复杂，运动对象多，因此，在本研究中选用了基于层次包围盒的方法.传统检测方法是进行一次或多次试切、不断调试，直到确认能够完成预定的加工要求，该方法效率低、周期长、成本高.为了提高检测效率，基于虚拟仿真技术的碰撞检测算法[3-7]，为数控加工方案的修正提供了依据，但是在修正过程中需要工艺人员根据经验预估修正方式，由预估引起的不确定性和偶然性，给生产计划带来一定风险，如果不能及时解决可能影响生产进度.为了避免盲目预估，减少反复修正的次数，提高准确率，保证精度，本文提出了基于改进OBB包围盒的快速碰撞检测算法.
1 问题描述
现有研究倾向于通过碰撞检测确定发生碰撞的对象，没有考虑具体的交点信息.数控加工仿真软件给出的碰撞检测结果是加工过程中发生碰撞的对象，这些碰撞检测数据可以基本满足数控加工仿真的需求[1].但是由于碰撞结果比较笼统，需要反复调整或校正加工速度、切削量或刀具伸长量等方式来修正.为了避免盲目的参数预估，减少反复修正的次数，提高准确率保证精度，准确计算出三角面的初始碰撞时间和碰撞位置显得尤其重要[8].针对车铣复合数控加工仿真碰撞检测精确度低的问题，本文提出了一种基于改进OBB包围盒的碰撞检测算法.
2 碰撞检测算法
碰撞检测算法分为3个部分：预处理阶段、粗检阶段和精检阶段.该算法以车铣复合加工仿真碰撞检测信息作为输入，计算出碰撞单元组之间发生的初始碰撞时间和位置.
2.1 创建OBB包围盒及层次包围盒树
车铣复合加工碰撞检测预处理阶段的主要内容是创建碰撞单元组对象的包围盒及层次包围盒树.具体步骤如下：
步骤1 创建车铣复合加工仿真环境.主要是车铣复合加工机床组件的创建，如刀具、刀架、主轴等，根据机床的运动学关系，建立机床运动学模型.
步骤2 车铣复合加工仿真碰撞检测.通过创建加工方法和加工操作，利用数控仿真软件进行车铣复合加工仿真，并进行碰撞检测.
步骤3 获取车铣复合加工仿真过程中发生碰撞的碰撞组信息.设碰撞单元组信息表示为:
Mk=Tkab,Ak,∑Aki,νka,Bk,∑Bkj,νkb（1）
Tkab为第k对碰撞单元组发生碰撞的时间；Ak为碰撞单元组的对象1，νka为Ak的运动速度, ∑Aki表示Ak所包含的三角面片集合∑Akipi,qi,ri；Bk为碰撞单元组的对象2，νkb为Bk的运动速度，∑Bki为Bk包含的三角面片集合∑Bkjpj,qj,rj.则车铣复合加工仿真碰撞组信息集合可表示为：
M=M1,M2,…,Mk（2）
步骤4 创建OBB包围盒.根据碰撞单元组对象所包含的三角面片信息，创建相应的OBB包围盒，分别标记为包围盒A和包围盒B.
步骤5 创建OBB层次包围盒树.以八叉树的形式进行空间划分，按照“自上而下”的方法创建层次包围盒树，分别标记为OBB_A和OBB_B.
层次包围盒树子节点主要分为3种类型，即实节点、空节点和灰节点.当叶子节点与几何对象实体完全重合时用实节点表示，当叶子节点与几何对象实体部分重合时用灰节点表示，当叶子节点与几何对象实体分离时用空节点表示.这样叶子节点中就储存了离散表面所包含的三角面片数据，用于精确碰撞检测.
其中空节点不包含几何实体，在计算中被剔除，减少运算节点数目；实节点与几何对象完全重合，认为该节点是最末端子节点，不需要再分割，可直接用于下一步进行精确碰撞检测计算；灰节点包含几何对象以外的空间，直接用于精确碰撞检测可能引起伪碰撞现象，所以如果灰节点存在碰撞现象，需要进一步分割，直到满足设定的层次包围盒深度或者所有叶子节点都是空节点或实节点为止，如果灰节点不存在碰撞现象，则不需要进一步分割，减少不必要的节点数目和存储数据.
在建立层次结构时，层次结构树深度的确定需要遵循两个原则：划分深度不宜太大，从而在遍历时，只需很少的步数，就能完成从根节点到叶子节点的搜索；划分深度不宜太小，否则每个子节点内包含的三角面片数量太多, 加重了精确检测的计算压力.层次包围盒树子节点的深度与几何模型及其精度相关[9]，本文结合检测对象的几何模型及精度，设层次包围盒树子节点最大深度为6.
2.2 基于分离轴定理的初始碰撞检测
碰撞检测的粗检阶段是基于分离轴定理，通过广度优先搜索的策略遍历层次包围盒树子节点，快速剔除不发生碰撞的子节点，当发生碰撞的节点不可分割时，则记为：
WkOBB_Ani,OBB_Bmj （3）
其中OBB_Ani是指层次包围盒A的第i层第n个子节点，OBB_Bmj是指层次包围盒B的第j层第m个子节点，Wk表示第k对发生相交的子节点组.层次包围盒OBB_A和OBB_B所有相交子节点组集合可表示为：
W=W1,W2,…,Wk（4）
对于一对OBB，需测试15条可能的分离轴(每个OBB的3个面方向，每个OBB的3条边方向的两两组合)，只要找到一条这样的分离轴，就可以判定这两个OBB是不相交的.如图1所示为分离轴定理示意图，其中L表示两个包围盒的某一分离轴，Oa和Ob分别表示两个包围盒的中心位置，S是包围盒中心位置在分离轴上投影的距离，ra和rb是包围盒在分离轴上投影的距离，当存在分离轴使S>ra+rb时，则OBB处于分离状态，反之则视为相交.在某些情况下，该算法会将分离的盒体报告为相交，但不会遗漏相应的碰撞结果，在初始碰撞检测阶段该算法计算简单，能够快速剔除不发生碰撞的包围盒.
图1 分离轴定理示意图
Fig.1 Separating axis theorem diagram
2.3 基于三角面片的精确碰撞检测
碰撞检测的精检阶段是应用分离轴定理，判断碰撞节点所包含的三角面片之间的相交情况，然后应用回退技术，计算出三角面片发生碰撞的初始碰撞时间和碰撞位置.
已知在粗检阶段计算得到相交包围盒节点集合：W=W1,W2,…,Wk.设Wk1是包围盒节点集合W的第k个元素中层次包围盒OBB_A的节点，Wk2是包围盒节点集合W的第k个元素中层次包围盒OBB_B的节点.应用分离轴定理考查11个分离轴（平行于两个三角形面法线的两个轴，两个三角形之间的9种边边组合）.若两个三角形在任一分离轴上的投影区间不相交，则两个三角形分离；若投影区间在所有分离轴上都相交，则两个三角形必定相交.把发生相交的三角形组记为：
QnSki,Skj （5）
其中Ski是指相交包围盒节点集合中的第k个元素对中层次包围盒OBB_A的节点包含的第i个三角面片信息；Skj是指相交包围盒节点集合中的第k个元素对中层次包围盒OBB_B的节点包含的第j个三角面片信息.Qn表示第n对发生相交的三角面片.层次包围盒OBB_A和OBB_B所有相交三角面片对集合表示为：
QQ1,Q2,…,Qn （6）
关于初始时间及位置的计算和改进方法将在第4节进行详细阐述.
3 改进的OBB包围盒算法
3.1 传统OBB包围盒算法
创建OBB包围盒时，确定包围盒的中心位置和最佳方向是关键.传统算法是根据几何模型的三角面片信息，利用均值和单位化协方差矩阵的统计量来计算包围盒的位置和方向.已知组成几何对象的基本几何元素为三角形，设包含的三角面片数为n，且第i个三角形的顶点坐标为(pi,qi,ri)，则包围盒的中心位置为：
m=13n∑ni=1(pi+qi+ri)（7）
由于该算法是各三角形顶点的简单平均，如果几何体结构不均匀，在体积相等的区域，有的部分三角面片数量多，有的部分三角面片数量少，这样计算出来的包围盒就会向三角面片数量多的部分偏移（如图2（a）所示）.显然这将导致一部分包围盒在几何体外面，使碰撞检测出现误检的现象.
3.2 改进的OBB包围盒算法
为了解决传统包围盒算法计算结果不准确的问题，本文提出区域加权的改进算法，该算法的核心思想是把几何对象划分为表面积相近的i个区域，分别计算每个区域的中心坐标mi，再求这几个区域中心坐标的平均值：
m=∑i1mii （8）
其中mi=13∑ji=1(pj+qj+rj)，协方差矩阵元素为：
Cjk=13n∑ni=1(pijpik +qijqik+rijrik)（9）
其中1≤j,k≤3，pi=pi-m, qi=qi-m和 ri=ri-m都是3×1阶向量，例如qi=(qi1,qi2,qi3)T.其次，计算协方差矩阵C［Cjk］的特征向量并单位化，作为包围盒的方向轴，几何体顶点在各方向轴上的投影区间长度就是相应的包围盒尺寸.
碰撞单元组对象的结构存在很大不确定性，无法采用统一的表面积划分方法.本文采用人机交互的方式，借助CAD软件的“分析-测量面”获取几何形面表面积的功能，把产品划分为几个相近的区域，根据产品结构可划分为3~5个区域.本文把万向节零件划分为3个表面积相近的区域（如图2（b）所示），通过采用改进的OBB包围盒算法，使矫正之后的包围盒紧紧地包围物体（如图2（c）所示）.
（a)改进前
(b)区域划分
(c)改进后
图2 OBB包围盒改进效果对比图
Fig.2 Comparison chartof improved OBB
4 初始碰撞时间及位置的计算
4.1 初始碰撞时间的计算
设在t=Tk时刻车铣复合加工发生碰撞现象，由于仿真精度和系统反应时间的问题无法保证Tk就是物体之间的初始碰撞时间.本文应用回退技术计算初始碰撞时间.
设两个三角面片在某个临近时间t=T0时未发生相交，则第一次发生碰撞的时间为t=TT0 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，可以计算出任意时刻的三角面片位置信息. 通过遍历集合QQ1,Q2,…,Qn包含的所有元素，并应用回退技术计算出每对相交三角面片的初始相交时间，得出集合： TT1,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的刀座发生了碰撞.相应的碰撞信息描述为： M1={0:45 min ,刀架1,∑A1i,2 mm/s,刀架2,∑B1j,0.8 mm/s} 其中“0:45 min”是指某工步在45 s时发生碰撞现象，“刀架1”是碰撞对象1，∑Aki表示刀架1的几何信息，“2 mm/s”刀架1沿碰撞方向的加工参数；“刀架2”是碰撞对象2，∑Bkj表示刀架2的几何信息，“0.8 mm/s”是刀架2沿碰撞方向的加工参数；应用CAD软件导出stl文件的功能，选择公差为0.08 mm，则导出发生碰撞的两个对象的三角面片数量分别为864个和13 632个. 应用改进的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
其中：
W1OBB_A135,OBB_B116
W2OBB_A155,OBB_B86
W3OBB_A235,OBB_B146
W4OBB_A135,OBB_B156
W5OBB_A76,OBB_B146.
通过精检阶段得出，发生相交的三角面片有93对.初始碰撞时间为工步2加工运行到17.83 s，初始碰撞位置为P132.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 数控加工仿真碰撞示意图
Fig.3 The graph of collision in NC simulation
方案3.减小钻削速度.钻刀的切削速度减小到0.7 mm/s以下，使钻刀与车刀在碰撞区域的运动轨迹产生时间差；
方案4.调整工艺方案.将车削加工与钻削加工分开加工.
以上4种方案中，方案1最方便快捷，且能保证切削效率和精度.方案2和方案3分别通过增加和减小加工参数避免干涉碰撞发生.如果参数修改幅度太大，会影响到加工效率和精度.方案4如果只是将车削加工与钻削加工分为两个工步进行加工，将影响加工效率.由于碰撞现象发生的情况各异，暂时还无法用统一的标准规定修正方案，详细修正计算过程这里不展开论述.本文采用方案1修正碰撞现象.经验证有效避免了碰撞现象.如图4所示为车铣复合加工碰撞检测流程示意图.
图4 碰撞检测计算流程图
Fig.4Flow chart of collision detection algorithm
6 结 论
本文创建的车铣复合加工仿真环境比CAM软件通过刀位文件仿真更真实，更接近实际加工情况，提供了可靠的碰撞检测信息.在预处理阶段，建立了改进的OBB包围盒及其层次包围盒树；在粗检阶段和精检阶段，基于分离轴定理和回退技术，计算出了初始碰撞时间及位置.实例验证结果表明，计算结果准确，为操作人员进行加工修正提供了可靠的依据，避免了盲目的参数预估，减少反复修正的次数，提高了效率，对车铣复合加工和制造也具有很重要的意义.
参考文献
［1］ 吴宝海,严亚楠,罗明,等.车铣复合加工的关键技术与应用前景[J].航空制造技术,2010（19）:42-45.
WU Baohai, YAN Yanan, LUO Ming, et al. 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, et al. 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 Jintong,JIANG Minghong. 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 Zhiqiang,HE Tao,YIN Wangwu,et al. Research on the performances of hexagonal spring tube energyabsorbing 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 Xiaohong, CHOI Yiking, BERNARD Mourrain, et al. An algebraic approach to continuous collision detection for ellipsoids[J]. Computer Aided Geometric Design,2011,28: 164-176.
［7］ CHANG Jungwoo,WANG Wenping, KIM Myungsoo. Efficient collision detection using a dual OBBsphere bounding volume hierarchy[J]. ComputerAided Design, 2010,42(1): 50-57.
［8］ 黄通浪, 唐敏, 董金祥.一种快速精确的连续碰撞检测算法[J].浙江大学学报:工学版,2006, 40(6):1051-1055.
HUANG Tonglang, TANG Min, DONG Jinxiang. 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 Yueshan, FEI Xianhong, et al.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].[20130921]. http://www.geometrictools.com/.
5.2 计算结果
通过粗检阶段得出，发生相交的子节点集合：
W=W1,W2,W3,W4,W5
其中：
W1OBB_A135,OBB_B116
W2OBB_A155,OBB_B86
W3OBB_A235,OBB_B146
W4OBB_A135,OBB_B156
W5OBB_A76,OBB_B146.
通过精检阶段得出，发生相交的三角面片有93对.初始碰撞时间为工步2加工运行到17.83 s，初始碰撞位置为P132.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 数控加工仿真碰撞示意图
Fig.3 The graph of collision in NC simulation
方案3.减小钻削速度.钻刀的切削速度减小到0.7 mm/s以下，使钻刀与车刀在碰撞区域的运动轨迹产生时间差；
方案4.调整工艺方案.将车削加工与钻削加工分开加工.
以上4种方案中，方案1最方便快捷，且能保证切削效率和精度.方案2和方案3分别通过增加和减小加工参数避免干涉碰撞发生.如果参数修改幅度太大，会影响到加工效率和精度.方案4如果只是将车削加工与钻削加工分为两个工步进行加工，将影响加工效率.由于碰撞现象发生的情况各异，暂时还无法用统一的标准规定修正方案，详细修正计算过程这里不展开论述.本文采用方案1修正碰撞现象.经验证有效避免了碰撞现象.如图4所示为车铣复合加工碰撞检测流程示意图.
图4 碰撞检测计算流程图
Fig.4Flow chart of collision detection algorithm
6 结 论
本文创建的车铣复合加工仿真环境比CAM软件通过刀位文件仿真更真实，更接近实际加工情况，提供了可靠的碰撞检测信息.在预处理阶段，建立了改进的OBB包围盒及其层次包围盒树；在粗检阶段和精检阶段，基于分离轴定理和回退技术，计算出了初始碰撞时间及位置.实例验证结果表明，计算结果准确，为操作人员进行加工修正提供了可靠的依据，避免了盲目的参数预估，减少反复修正的次数，提高了效率，对车铣复合加工和制造也具有很重要的意义.
参考文献
［1］ 吴宝海,严亚楠,罗明,等.车铣复合加工的关键技术与应用前景[J].航空制造技术,2010（19）:42-45.
WU Baohai, YAN Yanan, LUO Ming, et al. 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, et al. 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 Jintong,JIANG Minghong. 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 Zhiqiang,HE Tao,YIN Wangwu,et al. Research on the performances of hexagonal spring tube energyabsorbing 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 Xiaohong, CHOI Yiking, BERNARD Mourrain, et al. An algebraic approach to continuous collision detection for ellipsoids[J]. Computer Aided Geometric Design,2011,28: 164-176.
［7］ CHANG Jungwoo,WANG Wenping, KIM Myungsoo. Efficient collision detection using a dual OBBsphere bounding volume hierarchy[J]. ComputerAided Design, 2010,42(1): 50-57.
［8］ 黄通浪, 唐敏, 董金祥.一种快速精确的连续碰撞检测算法[J].浙江大学学报:工学版,2006, 40(6):1051-1055.
HUANG Tonglang, TANG Min, DONG Jinxiang. 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 Yueshan, FEI Xianhong, et al.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].[20130921]. http://www.geometrictools.com/.
5.2 计算结果
通过粗检阶段得出，发生相交的子节点集合：
W=W1,W2,W3,W4,W5
其中：
W1OBB_A135,OBB_B116
W2OBB_A155,OBB_B86
W3OBB_A235,OBB_B146
W4OBB_A135,OBB_B156
W5OBB_A76,OBB_B146.
通过精检阶段得出，发生相交的三角面片有93对.初始碰撞时间为工步2加工运行到17.83 s，初始碰撞位置为P132.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 数控加工仿真碰撞示意图
Fig.3 The graph of collision in NC simulation
方案3.减小钻削速度.钻刀的切削速度减小到0.7 mm/s以下，使钻刀与车刀在碰撞区域的运动轨迹产生时间差；
方案4.调整工艺方案.将车削加工与钻削加工分开加工.
以上4种方案中，方案1最方便快捷，且能保证切削效率和精度.方案2和方案3分别通过增加和减小加工参数避免干涉碰撞发生.如果参数修改幅度太大，会影响到加工效率和精度.方案4如果只是将车削加工与钻削加工分为两个工步进行加工，将影响加工效率.由于碰撞现象发生的情况各异，暂时还无法用统一的标准规定修正方案，详细修正计算过程这里不展开论述.本文采用方案1修正碰撞现象.经验证有效避免了碰撞现象.如图4所示为车铣复合加工碰撞检测流程示意图.
图4 碰撞检测计算流程图
Fig.4Flow chart of collision detection algorithm
6 结 论
本文创建的车铣复合加工仿真环境比CAM软件通过刀位文件仿真更真实，更接近实际加工情况，提供了可靠的碰撞检测信息.在预处理阶段，建立了改进的OBB包围盒及其层次包围盒树；在粗检阶段和精检阶段，基于分离轴定理和回退技术，计算出了初始碰撞时间及位置.实例验证结果表明，计算结果准确，为操作人员进行加工修正提供了可靠的依据，避免了盲目的参数预估，减少反复修正的次数，提高了效率，对车铣复合加工和制造也具有很重要的意义.
参考文献
［1］ 吴宝海,严亚楠,罗明,等.车铣复合加工的关键技术与应用前景[J].航空制造技术,2010（19）:42-45.
WU Baohai, YAN Yanan, LUO Ming, et al. 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, et al. 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 Jintong,JIANG Minghong. 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 Zhiqiang,HE Tao,YIN Wangwu,et al. Research on the performances of hexagonal spring tube energyabsorbing 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 Xiaohong, CHOI Yiking, BERNARD Mourrain, et al. An algebraic approach to continuous collision detection for ellipsoids[J]. Computer Aided Geometric Design,2011,28: 164-176.
［7］ CHANG Jungwoo,WANG Wenping, KIM Myungsoo. Efficient collision detection using a dual OBBsphere bounding volume hierarchy[J]. ComputerAided Design, 2010,42(1): 50-57.
［8］ 黄通浪, 唐敏, 董金祥.一种快速精确的连续碰撞检测算法[J].浙江大学学报:工学版,2006, 40(6):1051-1055.
HUANG Tonglang, TANG Min, DONG Jinxiang. 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 Yueshan, FEI Xianhong, et al.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].[20130921]. http://www.geometrictools.com/.
