在数控加工中，球头刀具由于其易定位、代码简单且适应性强而成为铣削加工的常用刀具．为了降低产品的试制周期和成本，可以采用数控仿真技术进行轨迹优化和虚拟加工．由于布尔求差运算耗时且所需资源要求较高，如何提升其计算速度，快速有效地模拟刀具的切削过程，成为数控仿真系统的一个研究热点．数控仿真通过工件和刀具之间的布尔求差来模拟铣削过程．现有的方法主要分为构造实体几何(constructive solid geometry，CSG)法和边界表示(boundary representation，B-rep)法．相较于构造实体几何，边界表示更能精确而直观地描述物体，基于边界表示的三角形网格表示已成为数控仿真的主要表示方法．由于立体光刻(stereo lithography，STL)文件能够记录高质量的三角形数据，且大多数显卡均具备三角形网格渲染功能，因此基于三角网格的立体光刻技术已成为计算机辅助应用中的主流方法．在通用布尔运算中，基于空间分割树和边界表示技术非常流行．然而基于分割树的仿真需要大量内存，并常导致不精确的几何表达．文献[1]指出，为了维持一个每边长100 mm、公差为0.01 mm的模型，需要108个分割树节点，这使得内存消耗成为不容忽视的问题．为了提高空间分割树算法的精度和健壮性，文献[2]采用环绕数标签的方法来减少网格构造的复杂性．以上方法为了识别加工部件的维度偏差，须要进行从分割树模型到边界表示模型的转换，这个转换过程增加了额外的复杂性．另外，在进行浮点计算过程中，由于固定大小的浮点数所引起的舍入问题 [3-4]，导致分割树单元边界产生裂缝，降低了计算精度和健壮性．与二叉空间分割(binary space partition，BSP)相比，边界表示还有更多挑战．最近的研究[5]指出，当边界表示处理共面或非常窄的三角形时，接近零的数值误差可能会导致错误的节点分类，从而影响最终结果的准确性．许多基于边界表示模型的算法在解决复杂模型时计算失败，这主要源于不稳定的精度．文献[6]建议用任意精度库来计算交点，但这会显著降低计算效率，须要进行精确性与效率之间的权衡．刀具与工件的啮合区域不断变化带来的反复布尔求差增加了计算复杂性，其中最具挑战性的是相交面的计算，相交面的构建包括交点三角化与拓扑一致性检查，其计算复杂，仿真时间成本高；当计算相交面时，无关三角形的搜索也容易成为瓶颈，细分筛选过程使得交点的计算效率受到较大影响；在复杂几何形状的交互检测中，精确射线投影法表现出明显优势，能在处理具有复杂表面的模型时精确计算交点位置．然而，文献[7-8]指出精确射线投影在计算效率上不如有向包围盒(oriented bounding box，OBB)，后者能够快速排除那些不相交的物体，但在动态变化的场景中，物体的频繁移动须要不断地重构树结构，这可能导致性能下降，在数控仿真场景下无法达到最优效果．另一方面，文献[9-10]认为通过三角形两两测试的方法还有改进的空间，网格中的相邻数据点在空间上呈现彼此接近的局部性现象，通过网格间的邻近关系搜索局部交点，能避免对模型进行全局扫描．因此，本研究基于十字网格结构，利用广度优先遍历的方法，从根节点开始逐层向外扩展．这种遍历方式在处理局部搜索问题时尤其有效．二叉空间分割树结构很难平衡内存开销与精度之间的矛盾[11-12]，边界表示模型只能近似表示真实物体，在网格面间往往存在间隙，而网格伸缩法可以拟合边界部分，能够较好地处理间隙问题．针对低效的求交运算，网格参数化法[13-14]作为一种处理几何信息的方法，将三维的几何信息转换到二维中，能简化模型间的相交区域，在处理求交问题中具有明显优势．通用的仿真算法将任意刀具的运动描述为扫掠体计算，复杂度高，对仿真任务实时性能带来了极大的挑战[15]．仿真任务对象的形状和复杂性极大地影响计算复杂度，简单的几何对象比高度不规则的形状更容易计算．由于球头刀具的运动可以被数控指令简化为直线与圆弧轨迹，因此本研究针对球头刀具的仿真并不涉及通用扫掠体的计算．为简化仿真计算，本研究考虑对球头刀具的直线或圆弧轨迹进行分段处理，根据球头刀具的几何形状，将数控运动的扫掠轨迹分割为圆柱、圆环和球体几种直线和圆弧轨迹．此外，由于仿真中须要判断刀具和节点之间的位置关系，传统的三角形相交测试(如环绕数、距离场等)，当进行位置判断时计算效率不佳，并且对模型的封闭性十分敏感[16]．文献[17]通过分割扫掠轨迹，将原始复杂的问题分解成一系列更小、更易处理的子问题．这一策略显著提升了搜索算法的效率，同时生成了更为均匀、几何形态更规则的网格单元．在这种思路的启发下，本研究采用数值微分分析法(digital differential analyzer，DDA)来构造简化扫掠轨迹的十字网格数据．数值微分分析法的优势在于其插值精度和灵活性，不仅适用于直线插值，也同样适用于圆弧及其他简单曲线的插值．借助数值微分分析法，可精确控制网格单元的生成，从而提高简化扫掠轨迹网格的均匀性和几何质量．1 十字网格布尔求差为了进行精确的布尔求差，刀具扫掠轨迹和工件的表面通常由大量的网格节点数据构成，对计算速度影响较大，合理构造表面的数据结构以及高效实现表面数据的查找、求交、增删操作能提升仿真效率．本研究提出一种十字网格图结构，利用邻接表进行动态索引，十字网格的布尔求差模型如下．若模型间相交，则存在相交轮廓线，网格间的交点集合可以准确地描述相交轮廓，图1(a)和(b)分别表示图1(c)中工件表面和刀具表面的十字网格，其在图1(c)中的环链A-B-C-D-E处相交．10.13245/j.hust.240592.F001图1十字网格布尔求差模型图1(c)中相交环链被映射在工件表面与刀具表面的十字网格表面，基于工件十字网格表面的相邻节点计算环链，两个相邻网格节点相隔在刀具扫掠轨迹的两侧(即外侧和内侧)，将两点构成的线段与扫掠轨迹求交，计算交点，迭代计算相交环链A-B-C-D-E．十字网格通过节点元素表示模型，节点间的相互引用关系能够很好地匹配扫掠轨迹二维映射的结构，此外，邻接表结构使得遍历算法避免了外部无关节点的查找，提高了修改模型的效率．2 基于二维映射的球头刀具布尔求差为了降低球头刀具布尔求差的运算量，本研究针对球、圆柱和圆环三类简化扫掠轨迹进行十字网格化，通过网格参数化法构建十字网格二维映射模型，以提高球头刀具布尔求差的计算速度．2.1　球头刀具扫掠轨迹简化数控系统中，当球头刀具切触面执行G01指令时，刀具运动产生的扫掠轨迹中间部分是圆柱，两端叠加球体部分．当执行G02指令时，刀具沿圆弧运动，空间中扫掠过的部分是环形，两端叠加球体．针对球头刀具扫掠轨迹的简化处理，主要从球体、圆柱与环形展开．在此仅说明球体的扫掠轨迹简化方案，其余场景的简化计算与球体简化方案类似．2.1.1　球头刀具扫掠轨迹简化策略二维映射将三维的数据转换为二维数据，降低布尔求差的复杂性．此外，本研究提出以球坐标形式描述基于离散网格模型的结构．球坐标和二维数组的转换关系如图2所示，描述了节点在球坐标系中的参数，以及将节点的球坐标参数映射到二维数组的方式，图中：θ为节点在球坐标系的方位角；φ为节点在球坐标系的仰角．仰角和方位角作为二维数组的两个参数，构建了该二维数组．10.13245/j.hust.240592.F002图2球体二维数组构建2.1.2　简化扫掠轨迹模型策略在平底刀具中的应用这种对刀具直线和圆弧扫掠轨迹的简化策略也适用于平底刀的计算，此策略将平底刀具的直线和圆弧扫掠轨迹简化为几何元素的组合，直线轨迹转化为立方体和圆柱，圆弧轨迹转换为圆柱壳模型．这种方法大幅降低了计算复杂性，从而提高了仿真的效率．因此，对于加工过程模拟和数控程序验证，是一种有效且高效的方法．2.2　球头刀具扫掠轨迹与工件的布尔求差为了对布尔求差计算进行简化，提高仿真速度，本研究设计一种基于十字网格图结构的二维映射布尔求差算法，将三维节点数据集合转换为二维数组结构．图3描述了球头刀具轨迹与工件布尔求差的步骤，图3(a)为刀具的三类扫掠轨迹，图3(b)描述了这些轨迹被离散为十字网格，图3(c)进一步说明十字网格作为二维数组的形式，图3(d)描述了工件和扫掠轨迹的交点与二维数组的关系，图3(e)描述如何将交点映射到二维数组中并生成闭合环链，图3(f)描述如何标记闭合环链的内部节点，图3(g)描述如何将标记的节点构造为相交面．定义二维数组与扫掠轨迹模型表面节点的映射关系为A(j,k,C)=(x,y,z)，j，k为二维数组地址，C为简化扫掠轨迹的几何特征，x，y，z为节点坐标值．另一方面，本研究通过在工件表面查找一对节点(αi,βi)以计算交点，该两点相邻，且以(αi,βi)为端点的线段与扫掠轨迹相交，定义交点为γi；设刀具扫掠轨迹模型为φ，定义求交计算为γi=(αi,βi)⋂φ，相交环链的计算定义为Y1={γi∈(αi,βi)⋂φ}；将相交环链节点γi映射至二维数组中，即(j,k)=A-1(γi,C)；定义Y2≔{γi|γi∈10.13245/j.hust.240592.F003图3球头刀具布尔求差计算流程A-1(γi,C)}，Y2构成二维数组闭合环链，λi为闭合环链上的节点．例如图3(e)所示的闭合环链a-b-c-d-e-f-g-h-i-j-k-l，基于二维数组闭合环链和广度优先遍历，标记所有位于环链内部的节点如图3(f)所示，生成由环链和环链内部节点构成的相交面如图3(g)所示．相交面的十字网格数据以链表形式被插入工件模型的十字网格数据中，另一方面，本研究基于广度优先遍历法标记所有内部节点，广度优先遍历选取内部节点中的一个作为初始节点进行搜索，并以当前节点是否属于Y1作为终止条件．由于搜索过程避免了所有外部节点的计算，因此该算法减少了计算时间．最后，删除未标记节点，完成工件与扫掠轨迹的布尔求差计算．二维数组上的每一个元素存储了扫掠轨迹表面的节点数据，本研究基于三类简化扫掠轨迹构建对应二维数组，如图3(a)和(b)所示．基于扫掠轨迹的几何特征求解位于二维数组表面的相交环链片段，并基于排序算法由环链片段集合构建闭合的相交环链，如图3(d)所示的相交环链A-B-C-D-E-F-G-H-I-J-K-L-M-N．相交环链被映射到二维数组，二维数组上被映射的节点对应相交环链的节点，即图3(e)中的二维数组闭合环链a-b-c-d-e-f-g-h-i-j-k-l．采用基于广度优先遍历的方法标记相交环链的内部节点，在图3(f)中内部节点标记为绿色，将所有被标记的内部节点和映射环链节点复制到工件表面，如图3(g)所示．在十字网格环链片段中，连续性是保证环链片段被正确标记和处理的关键．环链片段间的不连续性会导致“断链”现象，即环链在逻辑上不完整，无法表示一个封闭的区域．在环链片段之间可能存在不连续的情况，如图4所示．10.13245/j.hust.240592.F004图4十字网格插补图4(a)描述了环链不连续的场景，图4(b)描述了将这些不连续的部分插补后的结果，绿色节点是广度优先遍历的内部节点，黄色环链a-b-c-d-e-f-g-h-i表示一个不连续分布的环链．不连续片段可能令基于广度优先搜索算法的标记过程无法正确识别环链内部的节点，如图4(a)所示．为了确保算法能够正确标记内部节点，须要对不连续的环链进行插补，以恢复环链的完整，本研究用数值微分分析法来计算并插入中间缺失的节点．图4(b)中红色环链片段是通过数值微分分析法插补算法进行插补的结果，其中j，k，l节点为通过线性或近似线性步进方法沿环链预期路径生成的中间点，它们确保了环链的连续性和几何完整性．2.3　基于NURBS曲面的十字网格数据构造考虑到十字网格结构的模型同样适用于复杂曲面，本研究基于非均匀有理B样条(NURBS)曲面构造其十字网格数据，NURBS曲面通常在确定的两个节点矢量U与V之间进行分割．由NURBS曲面的方程可知，若要给出一张曲面的NURBS表示，则要明确定义的数据包括：控制顶点Pi,j及其加权因子wi，u参数的次数k，v参数的次数l，u方向的节点向量U与v方向的节点向量V．本研究通过细分在该单位正方形的网格面片来逼近NURBS曲面，实现基于NURBS曲面的十字网格数据构造．2.3.1　细分策略本研究采用均匀细分构造曲面数据，该细分策略可以确保全局一致的网格精度，从而避免由于局部网格密度不一致而引起的性能瓶颈，这对于快速查找相邻节点至关重要．为了细分NURBS曲面，必须确定参数域，该参数域通常由二维空间的u和v向量在规范化区间[0，1]×[0，1]内进行界定，u，v的模取值均在0到1之间．在u和v方向上均匀地插入新的节点，插入的节点数量由所需的网格精度要求决定．而后利用NURBS细分算法重新计算控制顶点的位置，以确保曲面形状保持不变；同时，控制点的权重也会被更新，以此维护曲面的连续性．这可以保证细分后的网格精确映射原始NURBS曲面的几何特征．2.3.2　细分误差均匀细分策略所产生的误差主要与NURBS曲面的原始定义和细分后的网格顶点之间的偏差有关．这种偏差可以通过比较原始NURBS曲面和细分后的曲面上相应点的位置来定量化．设S(u,v)为原始NURBS曲面，S^(u,v)为经过均匀细分后的曲面，则参数空间中的任意点(u,v)处的逼近误差E(u,v)可以定义为E(u,v)=S(u,v)-S^(u,v)，式中⋅为欧式距离．逼近误差的平均值Eavg可以进一步定义为Eavg=1A(D)∬DE(u,v)dudv，式中：D为曲面的参数域，通常为[0，1]×[0，1]；A(D)为曲面参数域的面积．3 实验结果及分析为了验证本文所提算法的综合性能，本研究从计算效率、健壮性、计算精度及在实际加工中的性能等方面对本文算法进行了全面评估．选择主流的开源图形处理库LIBIGL和CGAL等与本文算法进行比较，分别将布尔运算时间、处理的三角形数量、计算成功率及最大内存占用作为对比指标．为了进一步验证仿真算法在实际加工中的效果，本研究在其他算法和本文算法中开展了垫圈部件的仿真对比实验，比较各算法的三角形数量和总计算时间．为了评估本文算法的精度，通过UG软件进行精度的定量评估．3.1　扫掠轨迹的布尔求差运算对比为了展示本文算法在仿真计算中的性能，进行布尔求差对比实验，以验证本文方法应用于NURBS复杂曲面的可行性．本研究通过NURBS方法生成平面或曲面作为工件表面，与球头刀具的三类扫掠轨迹进行计算，结果如图5所示，其分别为球、圆柱、圆环的布尔求差结果．10.13245/j.hust.240592.F005图5NURBS表面与简化扫掠轨迹的布尔求差为了显示本文方法与其他方法的性能差异，本研究构建了由不同数量三角形组成的工件模型，分别进行球体、圆柱、环形的布尔求差计算，不同三角形数量(n)下的计算时间(t)如图6所示．布尔求差的计算效率与三角形数量呈线性关系．当处理较大数量三角形模型时，基于三角网格的二叉分割树结构须要对三角形进行相交测试，会产生许多无关节点计算，而本文方法通过相交环链节点追踪，避免了不必要的节点计算．此外，本文方法由于采用降维处理，相交节点的查找效率更高．统计结果显示，相对于其他主流方法，基于十字网格二维映射的方法可使布尔求差运算效率提升10倍以上，表明十字网格结构在模拟球头刀具切削方面具有明显优势．10.13245/j.hust.240592.F006图6布尔求差效率对比图3.2　精度与算法健壮性的关系为了评估浮点精度对布尔计算健壮性的影响．本研究设计比较十字网格结构、LIBIGL，CGAL，CORK和MeshLab这5种算法的成功率．分别采用单精度和双精度浮点数计算，用Thingi10K中的100个模型作为数据集，结果如表1所示．10.13245/j.hust.240592.T001表1算法成功率对比模式十字网格CGALCORKLIBIGLMeshLab单精度9977818383双精度9995919498%相比单精度模式，双精度模式能够提供更高的数值稳定性，在涉及大量计算中，双精度模式的成功率显著提高．此外，算法在设计上考虑了浮点数的不稳定性，并通过网格结构降低对精度的依赖，当处理非常近似的边界情况时，十字网格结构通过采用扫掠轨迹来简化交点计算过程，减少了浮点运算量，从而减轻了由于浮点数精度限制导致的累积误差，并且在计算上更加健壮．这一点与本文算法基于仿真需求而在精度与效率之间进行权衡的考虑相一致，能够在精度和效率保证的同时获得较好的健壮性．3.3　内存效率统计为了评估本文方法的内存效率，本实验分别将球体、圆柱、圆环扫掠轨迹与六棱锥工件模型进行布尔求差计算，对内存效率进行统计，与CGAL方法进行对比．为了使结果更有说服力，在每个实验中计算重复多次，将每次布尔求差的结果作为下一次计算的输入进行迭代计算，在多次布尔求差计算的结果中统计最大内存作为最终结果．如表2所示，表中每一行均为一个迭代轮次的最大值，可以看到十字网格结构的内存占用相较于二叉空间分割树结构减少约46%，可见通过描述节点元素可使模型的内存利用率显著提高．10.13245/j.hust.240592.T002表2内存消耗对比表轮次十字网格CGAL圆环圆柱球体圆环圆柱球体第1轮33.0051.0024.0071.0052.0078.00第2轮34.0052.0027.0093.0055.0066.00第3轮34.0054.0028.0078.0054.0085.00第4轮35.0053.0022.0065.0051.0074.00平均值34.0052.5025.2576.7553.0075.75MiB3.4　垫圈工件布尔运算的性能评估为了验证本文所提仿真算法在实际加工中的有效性，本研究通过实验对垫圈工件仿真的性能进行评估．针对由不同数量三角形构成的垫圈工件进行仿真，通过比较CORK，CGAL，MeshLab及本文算法在处理垫圈工件时的计算时间，评估各算法在处理不同分辨率工件模型时的性能情况．此外，为了准确评估本文算法的计算精度，通过UG软件对垫圈模型进行公差测量，以验证本文算法在实际应用中的有效性．首先进行垫圈工件布尔运算，然后将计算结果导入UG并测量模型的公差．基于十字网格算法的垫圈工件布尔运算利用垫圈加工的G代码提取加工所需指令，随后对每条直线或圆弧指令执行布尔求差运算，最终获得工件效果图如图7所示．10.13245/j.hust.240592.F007图7基于十字网格的垫圈工件布尔运算效果图7(a)描述了圆弧指令的布尔运算结果，图7(b)进一步描述了圆弧和直线指令的连续布尔运算结果．得益于十字网格算法的高健壮性，本文算法能够无缝地实现连续布尔求差运算，且本文算法采用相交环链的节点追踪和降维技术，即使面对复杂的工件和切削路径，也能保持计算的连续性和稳定性．本研究通过实验比较十字网格算法与其他几种主流技术在计算垫圈工件时的效率，结果如图8所示，十字网格算法在各个测试案例中的性能都较为突出．10.13245/j.hust.240592.F008图8仿真垫圈工件的算法性能对比图然后将上述垫圈工件数据导入UG软件进行公差测量，最终结果如图9所示．图9中绿色区域表示误差最小，其他颜色区域的误差可以参考色标．当外公差设置在5 nm时，分布在公差内的样本数为100%．从上述样本的统计情况发现该模型的精度最高可以达到5 nm，表明本研究提出的十字网格结构完全可以满足数控仿真的精度需求．10.13245/j.hust.240592.F009图9外公差为5 nm的垫圈工件模型公差图4 结语本研究提出了一种基于十字网格结构的球头刀具仿真算法，应用于数控仿真系统中的球头刀具连续布尔求差计算．通过构建十字网格数据和二维映射模型，模拟刀具与工件的切削过程．利用追踪轮廓线法计算球头刀具简化扫掠轨迹与工件表面的交点，以获得解析解，在不增加空间复杂度的同时降低了模型精度对算法健壮性的影响．与主流的三角形网格结构相比，本文方法具有更高的计算效率．值得注意的是，相交面与工件表面的边缘虽然视觉上连续，但底层的十字网格结构并未实现真正的连通，意味着两者在结构上是两个独立的图结构，这可能会影响后续的迭代计算准确性．十字网格在处理非流形表面(非流形表面指的是具有边界不连续性、孔洞或自相交的复杂结构)时也面临挑战，由于非流形表面在某些点上没有明确定义的内部和外部，使得简化扫掠轨迹和三角形交点的计算变得复杂，未来将针对以上挑战进行探索．