随着纺织工业的智能化与自动化发展，利用机械臂代替人工进行纱筒搬运、落纱及包装等工序，能够有效提升产品的质量和生产效率，减轻工人的劳动强度，促进企业的可持续发展。在机械臂自动化装取纱筒的作业过程中，物体包络与碰撞检测是实现高效、精准作业的核心环节。为确保机械臂在抓取纱筒过程中的安全性，构建其与作业环境的包围盒，并进行碰撞检测至关重要^[1-2]。

目前，国内外对于包围盒的研究相对成熟。传统的包围盒主要包括轴对齐包围盒（axis-aligned bounding box, AABB）^[3]、有向包围盒（oriented bounding box, OBB）^[4]、包围球（bounding sphere）^[5]和固定方向凸包（fixed direction hull, FDH）^[6]等。其中，FDH的紧密性与k值（k个方向）呈正相关，但高k值会显著增加内存占用率，在实时性要求高的场景中适用性受限。因此，本文将FDH排除在重点研究范围之外。包围盒算法通过几何近似与分层筛选策略，能够显著降低计算复杂度和平衡检测效率。张宇等^[7]利用球体与胶囊体代替传统混合层次包围盒中底层叶节点的包围盒结构，有效地提升了包围盒的包络精度，但该方法的应用场景相对局限。靳雁霞等^[8]利用混合层次包围盒结合空间网格法，提升了碰撞检测效率，该方法适用于柔性体与复杂刚性体交互的场景，但简化后的模型会丢失细节，且空间网格法的计算约束增加了系统开销。唐源皓等^[9]利用区域中心法和二叉树构造了OBB层次包围盒，并设定质点还原距离，通过将还原距离外的障碍物作为质点，简化了碰撞检测过程。Safeea等^[10]提出了一种用于人机交互的圆柱体间最小距离计算方法，通过正交三角分解将优化问题转换为几何空间中的最近点问题，该方法在简单场景中表现优异。

通过包围盒算法对物体进行包络后，需要对物体之间进行碰撞检测。碰撞检测算法主要分为基于图像空间与基于几何空间两类^[11]。基于图像空间的碰撞检测算法通过GPU（graphics processing unit，图形处理单元）将物体三维模型投影到二维平面，并利用深度缓存、模板缓存等渲染技术，判断物体之间的相交情况。Xiong等^[12]利用单视角RGB-D相机的彩色图像和深度图像生成3D点云数据，并通过下采样处理障碍物与基于障碍物分块的向量计算，使得机械臂末端执行器能够主动避开障碍物，减少了被动避障的局限性。常见的基于几何空间的碰撞检测算法包括空间剖分算法（如均匀网络、八叉树等）^[13-14]、GJK（Gilbert-Johnson-Keerthi）算法^[15-16]和分离轴定理^[17-18]等。这些算法可通过几何运算快速筛选出潜在的碰撞对象，且能够精确验证实际的相交情况。Flores-Caballero等^[19]基于分离轴定理精确检测了无人机路径与障碍物的几何碰撞，有效地提高了计算精度和复杂场景下无人机系统导航的可靠性。Montaut等^[20]将GJK算法与FW（Frank-Wolfe）算法（即条件梯度算法或梯度投影算法）的优化框架相结合，通过迭代优化过程，显著降低了机器人仿真过程中大规模凸多边形碰撞检测的计算成本。

本文针对机械臂自动化装取纱筒作业中的物体包络与碰撞检测问题，提出了一种基于凸包（convex hull）的改进混合层次包围盒算法。该算法通过提高叶节点的包络精度，可有效解决某些场景下因包络前后包围盒体积增大而导致机械臂无法准确识别纱筒的问题。针对传统分离轴定理在检测复杂凸多边形时因需要对每条边的法线方向进行分离轴碰撞检测而导致检测次数多、计算量大的问题，提出了梯度下降分离轴算法，根据分离轴每次旋转的角度和分离轴上投影的重合量来计算下一次分离轴旋转的角度与方向，以快速确定最优的分离轴位置。

包围盒算法利用简单图形来近似表示复杂不规则图形的几何形状，并通过最小化计算复杂度来加速后续对图形的处理。该算法具有简洁、计算效率高和减少空间浪费的优点。如图1(a)所示，纱筒的高度为25 cm，底面外径为12 cm，顶面外径为10 cm、内径为4 cm，倾斜角度为45°。采用常见的包围盒（AABB、OBB、包围球）对纱筒模型进行包络，如图1(b)至图1(d)所示。

常见包围盒对纱筒的包络结果如表1所示。由表1可知，在传统的包围盒中，OBB的包络紧密度最高，包围盒重叠率达到57.45%；包围球的包络紧密度最差，包围盒重叠率仅为25.28%。但是，即便是包络紧密度最高的OBB，仍存在超过40%的冗余空间，这是传统包围盒算法的固有局限性。

凸包是计算几何中的一个基本概念，其数学定义为：给定平面点集P⊂R²，存在唯一的极小凸集CH(P)且满足P⊆CH(P)，该凸集的边界所构成的凸多边形称为点集P的凸包。凸包的核心特征如下：

1）极小性：CH(P)为所有包含P的凸集中面积最小的集合，对于任意点集P的凸集C均满足CH(P)⊆C。

2）凸性：凸包内部任意两点的连线完全包含在凸包内部。

3）凸包的边界由点集中的一部分点构成。

本文使用Graham Scan算法（葛立恒扫描算法）来构造凸包。Graham Scan算法可以直接在原始数据上进行运算，空间复杂度为O(1)。若需保持原始输入数据的不变性，则可将最终生成的凸包顶点序列存储于一个新数组中。由于在扫描凸包前要进行排序，排序过程的时间复杂度为O(mlg m)，后续扫描过程的时间复杂度为O(m)，则整个算法的复杂度为O(mlg m)。图2所示为Graham Scan算法流程。

在利用凸包进行包络时，当物体表面没有凹形部位时，凸包通常不会改变物体体积。鉴于纱筒本身为规则的中空圆台，在这种情况下，凸包仅会将纱筒内部简化，将其转化为一个完整的圆台形态，如图3所示。

根据图3，凸包包络后的体积为2 382.37 cm³，包围盒的重叠率达到86.81%。基于此，本文引入凸包作为包围盒算法，以提升物体的包络精度。

纱筒装取机械臂由多个零部件组成，将刚性连接部分视作一个整体，对每个部分进行凸包包络，以降低机械臂运动过程中凸包更新迭代的复杂度。如图4所示，将机械臂分为基座、基座关节、大臂、小臂和末端执行器五部分。

利用SolidWorks软件对机械臂与纱筒进行建模，首先将装配体模型格式转化为obj格式，然后利用点云库PCL1.9.1将obj格式文件转化为pcb点云文件，点云中的离散点数量设置为50 000个，最后利用MATLAB软件处理pcb点云文件，以建立相应的凸包模型。纱筒和机械臂各部分的点云图与对应的凸包模型如图5所示。

不同于单一的包围盒算法，混合层次包围盒是在包围盒的基础上构建一个递归的树形结构，将多个包围盒组织起来，用于快速判断多个物体之间是否发生碰撞：通过分层处理先判断大范围内的包围盒之间是否发生碰撞，若没有碰撞，则立刻跳过该范围内子包围盒的碰撞检测。该算法通过递归将物体划分为不同层次，减少了需要碰撞检测的物体数量，显著提高了检测效率。传统混合层次包围盒的结构为上层AABB、下层OBB，OBB的包络精度虽优于AABB，但仍会产生大量的冗余空间。因此，本文引入凸包作为混合层次包围盒的底层结构。如图6所示，改进混合层次包围盒的结构为上层AABB、中层OBB、下层凸包。改进后的结构实现了效率与精度的平衡：上层AABB与中层OBB可快速排除不发生碰撞的无关物体，底层凸包结构通过提高叶节点的包络精度，减少了冗余空间，从而提高碰撞检测精度。

对于基于凸包的混合层次包围盒，在节点测试过程中，上层的AABB层作为粗略检测层，利用其检测方便、速度快和构造代价低的特点，快速筛选出距离较远、不可能发生碰撞的节点；中层的OBB层作为缓冲检测层，通过更紧密的包络筛选出有可能发生碰撞的节点；下层的凸包层通过最紧密的包络，精确地判断有可能发生碰撞的节点是否发生碰撞。改进后的混合层次包围盒根据不同层次包围盒的构造难度、检测时间和包络精度等，采用递进方式进行分层检测，即通过粗略检测、较精确检测和精确检测，实现了高效、高精度的碰撞检测。

如图7所示，当利用传统混合层次包围盒算法对2个机械臂进行碰撞检测时，AABB层与OBB层都发生碰撞，最终判定这2个机械臂发生碰撞。而采用改进混合层次包围盒算法进行碰撞检测时，在AABB层检测阶段，判定发生碰撞；在OBB层检测阶段，结果显示仍存在碰撞；在凸包层检测阶段，精确的计算结果表明，左侧机械臂的小臂与右侧机械臂的末端执行器之间不存在几何干涉，最终判定2个机械臂未发生实际碰撞。相较于传统的混合层次包围盒算法，改进混合层次包围盒算法通过底层凸包结构的精确包络机制，有效地降低了误判率，避免了因包围盒包络精度不足而导致的碰撞判定错误。

基于混合层次包围盒的碰撞检测是一种优化的碰撞检测方法，其核心思想是为需要进行碰撞检测的物体构建一个空间层次结构。在该层次结构中，每个节点均以一个由包围盒包络简化后的结构来近似表示对应物体的几何形状。碰撞检测逐层进行，先检测最顶层的父包围盒是否相交，只有当检测到父包围盒相交时，才会继续检测其子包围盒的相交情况。若父包围盒没有相交，则可跳过其所有子包围盒的检测，从而快速排除大量不可能发生碰撞的物体，显著减少不必要的计算。

在进行碰撞检测时，采用同层优先遍历原则，对待检测物体的父包围盒进行检测。如图8所示，以对包围盒10与14所包络的物体进行碰撞检测为例，具体步骤如下：

步骤1：对包围盒10与14的最外层父包围盒进行检测，即对包围盒2与3进行检测，检测方法为AABB碰撞检测。首先，利用物体在X、Y、Z轴方向上投影坐标的最小值和最大值（即x_min、x_max、y_min、y_max、z_min、z_max）建立矩形包围盒，该包围盒上的所有点满足如下数学约束条件：

然后，将2个包围盒投影到3个坐标轴上，并对比2个包围盒的投影是否存在重叠，以判断其是否相交。

1）检查在X轴上是否重叠。

若x_{1, max}<x_{2, min}或x_{2, max}<x_{1, min}，则表示2个AABB在X轴上没有重叠。

2）检查在Y轴上是否重叠。

若y_{1, max}<y_{2, min}或y_{2, max}<y_{1, min}，则表示2个AABB在Y轴上没有重叠。

3）检查在Z轴上是否重叠。

若z_{1, max}<z_{2, min}或z_{2, max}<z_{1, min}，则表示2个AABB在Z轴上没有重叠。

若包围盒在任意一条轴上都没有重叠，则表明2个AABB之间不相交，即包围盒10与14所包络的物体之间必定不发生碰撞；若检测出相交，则进行步骤2。

步骤2：对最外层父包围盒的下一层子包围盒进行检测，即对包围盒5与7进行检测，检测方法为OBB碰撞检测。分离轴定理是OBB层常用的检测方法，若包围盒5与7在空间中任意一个平面上的投影不存在重叠，则这2个包围盒之间不相交，说明包围盒10与14所包络的物体之间必不会发生碰撞；若检测出相交，则进行步骤3。

步骤3：对包围盒10与14进行最精确的凸包碰撞检测，若检测结果为相交，则判定对应的2个物体发生碰撞；反之，判定为不发生碰撞。凸包碰撞检测采用梯度下降分离轴算法。

利用分离轴定理对凸包进行碰撞检测时，在二维情况下，若2个凸多边形不相交，则必存在1条分离轴，使得这2个多边形在该轴上的正交投影区间不发生重叠；在三维情况下，若2个凸多面体不相交，则必存在1个分离面，使得这2个多面体在该平面上的正交投影区间不发生重叠。

如图9所示（本文以二维情况为例），给定一个分离轴L，并将凸多边形A和凸多边形B投影到该轴上。对于任意一个凸多边形，在计算其在分离轴L上的投影区间时，先确定分离轴L的单位向量 u，再计算多边形各顶点的位置向量（即该顶点按序指向相邻顶点的向量）与 u 的点积。

对于凸多边形A和B，分别定义proj _A (L)和proj _B (L)为多边形A和B在分离轴L上的投影区间：

式中： a_i 和 b_j 分别为凸多边形A和B各顶点的位置向量。

若在分离轴的某一位置上，2个凸多边形的投影区间proj _A(L)和proj _B(L)不存在重叠，即图9所示的绿色线段，则表示这2个凸多面形不相交，即：

若2个凸多边形的投影区间存在重叠，则需要改变分离轴的角度并再次进行判断。当达到设定检测次数时，若2个凸多边形的投影区间仍存在重叠，则认为这2个多边形之间相交。对于分离轴数量的设定，当判断对象为一对OBB时，最多设置15条潜在的分离轴。同理，当判断对象为凸多面体时，潜在分离轴的数量为物体A、物体B的面法向量数量与两物体边数量的乘积之和。

在传统分离轴定理中，所选择的潜在分离轴为随机选取或凸多面体某一面的法向量以及各边向量两两叉乘所得的向量。随着凸多面体边数的增加，潜在分离轴的数量增加，则检测次数随之增多。特别是在要求物体包络精度高的情况下，如上文所述，在对物体进行建模并提取点云后，利用Graham Scan算法进行凸包构建，最终形成了一个由多个三角面片构成的凸多面体，其面数量多达万个，若仍使用传统分离轴定理进行碰撞检测，所需测试的潜在分离轴数量极其庞大，导致检测效率严重降低。为提高检测效率，对传统分离轴定理进行改进。如图10所示，2个凸多边形在分离轴L₁上投影的重合区间为红色较长线段；将分离轴L₁旋转至L₂位置后，2个凸多边形在分离轴上投影的重合长度随之减小；再将分离轴L₂旋转至L₃位置后，2个凸多边形的投影不发生重合，表明这2个多边形不相交。因此，可根据2个凸多边形在各分离轴上投影重合长度的不同，以投影重合长度作为参考，按越靠近最优分离轴所对应的投影重合长度越短的原则，设计梯度下降分离轴算法。

首先，随机选取一个分离轴位置，并分析2个凸多边形在分离轴上的投影是否重合，若投影完全重合（一个凸多边形的投影完全覆盖另一个凸多边形的投影），则重新选取分离轴位置；若投影并非完全重合，则将分离轴顺时针或逆时针旋转0.1°，计算对应的投影重合长度变化量，并以此为依据计算下一次分离轴旋转的角度，以此动态调整分离轴位置，依次循环。若投影不重合，则表明2个凸多边形不相交，否则重复循环。设置总循环次数为N，若循环结束后，2个凸多边形仍未分离，则判定发生碰撞。根据分离轴定理，只要存在1条分离轴满足投影分离，即可判定物体不发生碰撞。因此，在循环过程中，即使是收敛至局部最优，只要该解所对应的分离轴满足投影分离条件，就能判定两物体不发生碰撞，无需达到全局最优解。在梯度下降分离轴算法中，投影重合长度变化率r的计算式如下：

式中：ΔLcurrent为当前2个凸多边形投影的重合长度，ΔLprevious为上一次2个凸多边形投影的重合长度。

若变化率r为负值，则说明当前的重合长度缩短；若r为正值，则说明当前的重合长度增加。

由此可得分离轴的旋转角度：

式中：Δθnext为下一次分离轴的旋转角度；Δθcurrent为当前分离轴相较于上一次分离轴的旋转角度；α为调节因子，用于控制旋转角度的变化幅度，针对工业场景，α的取值范围为[0, 0.5] ^[21-22]。为避免旋转步长过小导致收敛缓慢以及步长过大导致剧烈震荡，本文设α∈0.05,0.5，α的取值与∣r∣呈正相关。

若r<0且∣r∣较大（∣r∣>0.3），则可适当减小旋转步长，避免因步长过大而导致无法稳定逼近最优分离轴，可将α设置为较大值，如α=0.4。

若r<0且∣r∣较小（0.1≤∣r∣≤0.3），则稍微增大旋转步长，在保证收敛可靠性的同时提高搜索效率，可将α设置为较小值，如α=0.1。

若r>0，则增大旋转步长以提高搜索效率，可将α设置为较大值，如α=0.5。

若∣r∣接近0（∣r∣<0.01），即投影重合长度变化缓慢，则可适当增大旋转步长以提高搜索效率，可采用较小的α，如α=0.2。

综上，梯度下降分离轴算法的流程如图11所示。

为验证所提出的改进混合层次包围盒算法与梯度下降分离轴算法的效果，设计以下对比实验：1）在机械臂的不同部位应用不同包围盒算法，对比其包络紧密度与构造时间；2）对比改进前后的分离轴算法在碰撞检测中的迭代耗时与迭代次数。计算机配置为64位Windows 11操作系统、Intel(R) Core(TM) i7-12650H 处理器、RTX4060显卡、16 GB内存。

针对纱筒装取作业，利用MATLAB R2022a软件计算基于AABB、OBB、包围球、凸包四种不同包围盒对纱筒和机械臂各部分进行包络所需的时间以及对应的包络体积，通过综合对比并结合实际情况，得出效果较好的包络方式。包围盒的包络紧密度越高，说明其表征物体几何轮廓的精度越高，进而可提升碰撞检测的准确性。

表2所示为利用4种包围盒对纱筒和机械臂各部分进行包络后的结果对比。对于纱筒，凸包的包络体积相较于AABB减小了28.81%，相较于OBB减小了28.81%，相较于包围球减小了61.54%；对于机械臂末端执行器，凸包的包络体积相较于其余3种包围盒分别减小了55.81%、53.26%、92.84%。由于机械臂每个部位的初始位置与倾斜角度不同，使得包络体积不同，但凸包对各部位的包络体积均小于其他包围盒。

表3所示为基于2种混合层次包围盒的纱筒和机械臂的总包络体积对比。由表3可知，相较于传统混合层次包围盒算法，本文所提出的基于凸包的改进混合层次包围盒算法的包络剔除率提升了37.243%，包络精度提升了25.352%，说明采用以凸包作为混合层次包围盒叶节点的优化策略，能够显著减小包围盒的包络体积，从而提升碰撞检测精度。通过实验结果可以看出，相较于其他包围盒，凸包虽然在构造时间上不占优势，但可在场景的初始化阶段完成构造，对于后续的更新迭代，只需对其空间位姿进行矩阵变换，即可实时更新凸包的空间状态，实现一次构建、多次复用的高效更新机制，且凸包在包络精度上有很大提升，这有助于探索更优的机械臂抓取路径。

在利用不同的包围盒算法对物体进行包络简化时，可能会出现包络后体积膨胀的情况。当物体排布密集时，这种体积膨胀现象会显著增加误判的风险：即在实际未发生碰撞时，因包围盒重叠而误判为碰撞。

图12所示为西安纺织集团公司纺织车间的纱筒架。在纺织加工过程中，需要通过机械臂来自动抓取摆放在纱筒架上的待加工纱筒。在三维空间中，纱筒的摆放具有一定的空间分布特征，其几何形状和空间位置对碰撞检测的准确性至关重要。在利用机械臂抓取纱筒的过程中，当利用不同包围盒对纱筒进行包络后，体积明显增大。当纱筒之间摆放较为紧密时，则可能会出现包络前不碰撞、包络后因体积增大而碰撞的问题，从而导致机械臂不能准确识别纱筒。

图13所示为基于4种包围盒对纱筒的包络效果对比。为方便观察，选择包络后模型在XOZ或XOY平面上的投影进行对比。从图13(a)至图13(c)中可以看出，利用AABB、OBB、包围球包络纱筒后体积明显增大，最终导致机械臂抓取失败，但利用凸包对纱筒进行包络后，几何形态与原始纱筒高度相似，且能最大限度地保留原始纱筒的几何特征，这可为后续的纱筒抓取与机械臂路径规划提供可靠保障，有效提升系统的整体性能。

为验证本文所提出的梯度下降分离轴算法的性能，分别对传统分离轴算法、梯度下降分离轴算法与基于最近点的分离轴算法^[18]进行对比，实验对象为纱筒与机械臂大臂的碰撞检测。

表4和表5所示分别为传统分离轴算法与改进分离轴算法在不碰撞和碰撞两种条件下的计算效率对比。其中，梯度下降分离轴算法的检测次数阈值设定需综合考虑精度约束、场景复杂度与可靠性要求。通过对IEEE ICRA 2019—2023核心论文中上万组仿真实验进行统计可知：对于90%以上的刚体碰撞问题，最多迭代50次即可使梯度范数下降至设定阈值以下，将迭代次数增加至100次，检测精度的提升不足2%，而迭代耗时呈线性增长趋势。基于此，选择50次作为迭代次数阈值具有广泛的适用性。图14所示为无碰撞情况下3种分离轴算法单次迭代耗时的对比。

从表4与图14中可以看出，在无碰撞情况下，梯度下降分离轴算法在计算效率上明显优于传统分离轴算法与基于最近点的分离轴算法：平均迭代耗时分别缩短了90.67%和38.24%，平均迭代次数分别减少了98.48%和56.56%，内存增量分别减少了97.26%和55.45%。由表5可知，在碰撞情况下，传统分离轴算法和基于最近点的分离轴算法的平均迭代耗时、平均迭代次数和内存增量均显著高于梯度下降分离轴算法，该算法能够在50次迭代内快速停止，节约了计算成本。此外，传统的分离轴算法需要对复杂凸多面体的每条分离轴进行逐一验证，计算量庞大；基于最近点的分离轴算法与传统分离轴算法相同，也需要对凸多面体的每条分离轴进行逐一验证；而梯度下降分离轴算法基于投影重合长度来计算分离轴的旋转角度，区别于传统的依赖凸多面体各边几何信息的分离轴算法，其在处理复杂凸多面体的碰撞检测问题时，可将检测问题转化为连续优化问题。对于边长数量庞大、面数多的凸多面体，梯度下降分离轴算法通过减少需要验证的分离轴数量，显著提升了碰撞检测效率。该算法的核心在于：将每次迭代的分离轴位置逐渐逼近最优分离轴，最终得到可有效分离2个凸多面体的最优分离轴，提升了计算效率和鲁棒性。

本文针对传统混合层次包围盒因包络精度不足、几何近似度过低而导致包络体积膨胀，以及由此引发的机械臂在稠密纱筒阵列中误识别率较高的问题，提出了一种基于凸包的混合层次包围盒模型叶节点优化策略，将传统混合层次包围盒算法中底部的OBB替换为凸包结构，以提高几何贴合精度。对于传统分离轴算法在复杂凸多面体碰撞检测过程中存在计算效率低的问题，提出了梯度下降分离轴算法，并推导了分离轴旋转角度的计算公式，根据每次在分离轴上的投影重合长度变化量来确定下一次分离轴的旋转角度，并使分离轴向投影重合长度减小的方向旋转。所提出的改进方法使机械臂能够准确识别需要抓取的纱筒，并快速检测出2个物体之间是否发生碰撞，这可为后续的纱筒抓取与机械臂路径规划提供可靠依据。