面向车身数字化工艺开发的三坐标碰撞算法研究

王雪琪，赵文政

（上海理工大学机械工程学院，上海 200093）

0 引言

经历数十年的高速发展，汽车工业已然成为推动国民经济高质量发展的重要支柱，我国也成为最大的汽车生产国与消费国。然而，自主品牌和自有技术存在的短板阻碍了我国制造业从“制造”向“智造”转型的步伐。

在汽车行业，车身制造质量不仅影响消费者的主观评价，还对制造过程综合成本控制、汽车使用性能提升等方面起到决定性作用。我国自主品牌的乘用车制造行业起步较晚，车身综合尺寸偏差往往大于5mm，而欧美、日、韩等汽车制造强国的综合尺寸偏差控制在1.5～3.5mm 之间，明显优于我国自主品牌的车身制造质量，导致国产乘用车市场占有率低、产品竞争力弱。

三坐标测量机因其高精度、柔性测量等特点成为白车身、车门系统、底板总成等关键零部件与整车检测的首选，但由于三坐标测量机在运动过程中一旦发生碰撞时，首先需要进行碰撞检测，并按照之前设定的避障策略添加空间移动点，以获取无碰撞的局部检测路径。因此，局部检测路径的规划结果是影响全局检测路径规划质量的最重要因素，关键在于研究高效、准确的碰撞检测算法与通用的避障策略。

目前，碰撞检测可分为静态碰撞检测和动态碰撞检测［1］。其中，静态碰撞检测算法多用于凸多边形的碰撞检测，针对凹多边形可先将其分解成多个凸边形后，再进行碰撞检测。这种方法主要用于研究静止状态下物体是否发生干涉，检测精度要求较高。Uchiki 等［2］提出了一种空间占有法的碰撞检测方法，能够快速、准确检测三维空间中自由物体之间的碰撞。申静波等［3］基于现有的相交检测算法提出了基于夹边边对的空间平面凸多边形快速相交检测方法。然而，现有静态碰撞检测多适用于检测凸多边形碰撞，对于凹多边形的碰撞检测只能先将其分解为多个凸多边形后再进行碰撞检测，因此增加了三坐标静态碰撞检测算法的计算时间，效率较低。

动态碰撞检测则主要研究物体运动过程中是否发生碰撞，被广泛运用于三维游戏等虚拟现实中，又可细分为离散碰撞检测和连续碰撞检测。

离散碰撞检测是将物体的运动轨迹按照一定步长离散化，并分别对每一段进行碰撞检测，代表方法包括层次包围盒法［4］和空间分割［5］。Alvarez 等［6］基于零件离散化的三角形面片，应用空间划分技术（K-dimensional tree，Kdtree）减少测头与零件之间的交叉试验次数。Dong 等［7］使用轴向包围盒法（Aixe Align Bounding Box，AABB）进行碰撞检测。Tang等［8］利用非均匀有理B样条曲面对被测物体进行三角划分，再利用分离轴定理实现碰撞检测，提高了检测效率与准确度。Han 等［9］基于空间分割法求解测头运动直线轨迹与被测物体所在空间的交集，再利用RE-OP 算法对碰撞路径进行优化。上述离散碰撞检测均能快速进行碰撞判别，但会因步长影响无法完全保证检测准确性。

连续碰撞检测算法通过对物体移动过程中扫过的空间进行建模，进而实现碰撞判定。代表方法包括基于扫描实体的算法［10-11］、保守前进算法及其改进算法［12］、基于GJK 的算法［13-15］、射线追踪法［16-17］等。Albuquerque 等［18］利用射线跟踪技术确定检测点与目标点之间在运动过程中是否与三棱柱发生碰撞。Buchal 等［19］在网格构建过程中，基于图像冲突检测方法对每一特征进行碰撞检测。Lu等［20］将改进的三维射线追踪法应用于坐标测量机所在空间的八叉树中，以检测任意两特征间的障碍物。张应中等［15］提出适用于简单凸体之间的线性连续碰撞检测算法。然而，在连续碰撞检测中仍存在检测速度慢的问题［21-23］，且随着运动轨迹复杂度的增加，环境空间建模也会随之变得更加困难。

综上所述，面对不同应用场景，学者们提出了不同的碰撞检测算法和改进算法以提高检测效率及准确度，然而现有碰撞检测算法仍无法高效解决复杂环境下的碰撞检测问题。例如，面对车身复杂结构与五轴三坐标之间的碰撞检测，尤其针车身与测头的连续运动过程的扫掠建模与快速碰撞检测方面，仍存在碰撞检测效率低与碰撞检测精度差等问题。

为了从根本上解决问题，本文提出一种基于GJK（Gilbert Johnson Keerth）的快速连续碰撞检测（Fast Continuous Collision Detection）。

1 三坐标测量仪碰撞检测算法

针对现有动态碰撞检测算法在车身三坐标碰撞检测应用中的不足，对车身进行三角面片化，将三坐标的测头、测针、接长杆进行层次包围盒化等处理，实现对三坐标运动轨迹所占空间的建模，提出基于OBB 包围盒（Oriented Bounding Box）和GJK 碰撞检测相结合的分级碰撞检测算法。算法流程如图1所示。

Fig.1 Dynamic collision detection algorithm flow图1 动态碰撞检测算法流程

由于车身是300～500 个薄板冲压零件焊接而成的总成件，具有以下特点：①长度和宽度远大于厚度；②内部存在空腔形态，且内部空腔中存在需要测量的检测特征；③尺寸较大，曲面结构复杂。因此，若将车身进行包围处理不仅增加了建模的难度，且建模精度较低。为解决该问题，采用网格化思想，基于曲面曲率变化对车身进行三角面片化处理。图2为三角面片化的车身模型。

Fig.2 Diagram of body in white triangulation图2 白车身三角面片化示意图

由于测头与车身、接长杆与车身之间碰撞检测是保证CMM 无碰撞路径最主要的保障，而三坐标测量机是由多个零部件组合而成的实体，如何合理建模使所构造的函数更简单、计算量少、运行效率高且模型接近实体是现阶段亟待解决的问题。为此，本文针对三坐标测量机的特点，采用圆柱体及球体对其本体进行包络，结合三坐标各个关节形状的特点对其进行建模，不仅降低了环境建模的难度，同时提高了模型的精度。图3 为简化后三坐标机测头结构模型。

Fig.3 Simplified model of CMM probe structure图3 三坐标测头结构简化模型

1.1 基于空间几何的静态碰撞检测

三坐标路径规划的碰撞检测可分为静态碰撞检测及动态碰撞检测。其中，静态碰撞主要为三坐标与车身之间的碰撞检测；动态碰撞检测包括运动过程中三坐标与三坐标之间碰撞检测、三坐标与车身之间碰撞检测两种。首先将详细阐述基于空间几何距离的静态碰撞检测算法及所提出的基于分级连续碰撞检测的动态碰撞检测算法。

测头系统中探针与接长杆可简化为圆柱体结构，旋转中心可简化为球体结构。因此，测头与车身结构的静态碰撞探测可转化为筛选点云是否存在于测头系统所占几何空间中，对于旋转中心而言，静态碰撞探测可以表示为：

其中，（Xj，Yj，Zj）为车身离散化节点的坐标值，（Xo，Yo，Zo）为简化关节中心点坐标，Δdq为车身点云节点到测头中心点的距离和简化球体半径的差值，若Δdq＜0则三坐标与车身发生碰撞，否则不发生碰撞。

对于探针与接长杆而言，先根据点云节点与圆柱体表面点之间的矢量夹角的计算结果进行粗筛选，再计算点云节点与圆柱体轴线见的距离，确定是否存在静态碰撞，其判断过程可表示为：

1.2 基于分级检测的动态碰撞检测算法

CMM 采用的是接触式测量方式，但测头在移动过程中大多与车身之间存在逼近距离。针对这一规律，首先采用包围盒对测头结构的运动轨迹所占空间进行简化，初步判断其与车身是否发生碰撞。

图4（彩图扫OSID 码可见，下同）中橙色曲面表示测头结构从t0时刻到tend时刻的移动轨迹，青色为测头结构移动轨迹所占空间的包围盒。可根据测头点云信息得到测头结构从t0时刻到tend时刻在空间中的位置U（iXi，Yi，Zi）、Li（Xi，Yi，Zi）（i=1，2，...，P），最终通过OBB 包围盒确定各个节点的坐标值，具体步骤如下：

各测头中心点的均值为：

根据式（1）可得到协方差H：

其中，j，k分别表示所采用的坐标分量即x、y、z，1≤j，k≤

通过公式（3）可得到3×3 对称的协方差矩阵H，将H的3 个特征向量正交化后即为OBB 的3 条轴方向，最后计算OBB 内各顶点在这3 条轴上的投影最大、最小值即可确定OBB 的3条边长及各交点的坐标。

Fig.4 CMM probe motion modeling based on bounding box method图4 基于包围盒法的CMM测头运动建模示意图

若粗检测过程中三坐标测头结构与车身发生碰撞，则进一步基于GJK 碰撞检测算法确定车身与三坐标各个关节是否发生碰撞。GJK 模型是一种用来确定两个凸集之间最短距离是否小于零，从而确定两物体是否发生碰撞的方法，相关基本概念如下：

（1）Q表示三维空间的一个点集，则包含Q的所有凸集的交集称为Q的凸包（Convex Hull，CH），记为CH（Q）。

（2）如果有A，B两个点集，令a和b为分别为A和B中的顶点位置，则2 个点集A和B的Minkowski 差可定义为C=A⊖B=｛a-b：a∈A，b∈B｝，当且仅当CH（C）包含原点时，则表示凸包A和凸包B发生碰撞。

（3）对于凸集C内沿给定方向v且距离凸集最远的点被称为支撑点，这一过程被称作支撑映射，可记作Sc（v）。如图5所示，P点为凸集C沿v方向的支撑点。

Fig.5 Support point P of convex body C on direction v图5 凸体C在方向v上的支撑点P

设三坐标测头从t0时刻到tend时刻所形成凸体，记为CTU，即测头结构在［t0，tend］时间区间内所形成凸体的凸集可由各个边的节点表示。车身某处三角面片记为BIW，用D（Cmm，BIW）表示两凸体之间的距离，则两者之间的距离可表示为：

设两凸体Cmm、BIW之间的Minkowski 差C所构成的凸包CSO 与原点之间的最短距离设置为d，则存在有d(C) ∈C且||d(C)||=min{||x||：x∈C}，CSO中所有顶点集合为W，GJK 算法通过迭代方式计算CSO 中距离原点最近的点，并保证每次生成的单形体节点W更接近于原点，记第k次迭代产生形体的顶点集合为Wk。

对于［t0，tend］时间区间内测头结构所形成的凸体TUT与车身三角面片BIW之间的GJK 算法的碰撞检测过程：

步骤1：给定初始方向，输入两凸体CTU、BIW 之间的Minkowski 差C所形成凸包CSO，其中CSO 中初始顶点集合为W0=∅。

步骤2：计算凸包CSO 与原点之间的最短距离为dk，该点记为vk。

步骤3：若dk为0，则三坐标包围盒与车身发生碰撞算法结束；若不为0，则转到步骤3。

步骤4：对于Wk中不包含vk的子单形体，将其顶点从Wk中剔除。

步骤5：沿初始方向负方向即计算凸包CSO 沿-vk所在方向的支撑点wk。

步骤6：若‖vk‖2-vkwk≤ε2，则结束迭代过程，并输出三坐标与车身不相交。若k＞K，则三坐标与车身不碰撞；否则k=k+1，将wk加到Wk中并返回步骤1。

步骤7：输出三坐标测头结构与车身状态。

2 实验及分析

为验证本文算法的有效性和实时性，建立三维场景复杂度不同的场景进行测试。选取具有两个大小不同的正方体作为实验对象，正方体由程序生成，并且每个正方体的移动方向和速度随机生成，当两个正方体发生碰撞时，会显示碰撞信息，如图6所示。

Fig.6 Collision detection in the following experimental scenario图6 实验场景下的碰撞检测

在上述研究基础上，以白车身为例，阐明本文所提出的分级碰撞检测的有效性，对某型号白车身单一车次内所需检测的关键尺寸特征进行碰撞检测，并与现有方法进行比较。

由于侧围外板的CAD 数模结构由侧围外板薄板件、众多加强件、功能件等多种零件连接而成。因此，在对侧围外板进行测量时，首先将其放置在固定支架小车上并利用夹具进行固定，然后将支架小车及侧围外板件放置于先前设定好的测量机的检测区域，最后进行测量机校准、坐标系重建及对侧围外板关键尺寸特征进行检测。

利用有限元软件对侧围外板及固定支架进行网格划分，选用四边形与三角形结合的划分模式，对划分网格的节点进行提取，共获得1 728 995 个车身离散化点云坐标。如图7 所示，蓝色的为车身点云，红色的为车身测点，共689个。

Fig.7 Point cloud diagram of side outer plate and fixed support图7 侧围外板及固定支架点云图

图8 为基于OBB 粗略检测下三坐标测头结构与车身发生冲突的情况。其中，绿色点代表车身点云，蓝色线条代表包围盒，可见三坐标测头结构在运动过程中与障碍物之间发生冲突。随后，本文将三坐标运动轨迹进行离散化处理，表1为三坐标离散轨迹点。

Fig.8 Results of the bracketing box-based detection图8 基于包围盒的检测结果

Table 1 Trace points of three-dimensional probe structure in discrete space表1 三坐标测头结构离散空间轨迹点

图9 为构造三坐标测头结构运动轨迹包络体。将车身点云转换为凸多面体形式，采用GJK 精细化进行碰撞检测。

由图9 可见，三坐标测头结构在运动过程中与障碍物之间发生了冲突，从而验证本文碰撞检测算法的有效性。

Fig.9 Graded collision detection results图9 分级碰撞检测结果

通过在车身场景下的测试，对本文提出的分级碰撞检测算法和仅有包围盒的碰撞检测效率进行了比较实验，共记录50 个测点的平均检测时间，仿真实验结果如图10所示。

通过测试数据可知，在同一场景下本文提出的碰撞检测效率相较于仅有包围盒的碰撞检测，在实时性方面提升显著，能够基本满足虚拟场景中对碰撞检测的实时性要求。

3 结语

本文提出了一种基于分级连续碰撞检测算法，该算法针对静态碰撞检测算法中存在的“隧道效应”和计算效率低的问题，根据三坐标测头结构的特征进行简化，利用分级碰撞检测算法在有限的步骤内检测是否发生碰撞。

仿真结果表明，提出的算法具有较快的响应速度和较高的检测速度。下一步将以提高动态碰撞检测的效率为方向进行深入研究。