橄榄核雕是古老的, 其因精美的刀工、精致的造型、多样的艺术表现性而备受青睐. 近年来, 人们开始将数控雕刻机应用于橄榄核雕刻领域, 机器雕刻的出现解决了人工雕刻耗费工时长、品质良莠不齐、无法大规模生产以及造价高等缺点. 但是如, 若将已有的三维模型直接用于橄榄核机器雕刻, 易造成雕穿的现象, 且无法发挥橄榄核雕随形雕刻的艺术特色. 目前业界在进行橄榄核机器雕刻时仍然由专业人员使用商业CAD软件手工调整三维模型再进行数控编程得到雕刻刀路. 这个过程需要较高的人力成本且具有不可复制性. 如果存在一种面向橄榄核机器雕刻的模型编辑与刀具路径规划方法, 必定会大大改善目前橄榄核机器雕刻的加工效果, 提高加工效率并可以以较低的成本实现随形雕刻.

　　在橄榄核机器雕刻领域, 硬件方面已相对成熟, 除了可以使用常规雕刻机搭配橄榄核专用夹具进行雕刻外, 田杰宇等[2]研发了一种基于并联机构的核雕专用设备. 然而目前学术界对面向橄榄核机器雕刻的模型编辑与刀具路径规划研究较少, 难以对工业界提供具有针对性的指导.

　　三维模型变形问题一直是国内外计算机图形学领域的研究热点, 经过众多学者多年研究已经取得了诸多研究成果. 空间变形技术最早由Sederberg等[3]提出, 主要思想是将待变形的目标模型嵌入到某个控制网格中, 通过对控制网格顶点的操作使嵌入其中的目标模型基于函数插值进行变形. 此后学者们提出了一系列无需控制网格的方法如最小二乘法[4]、径向基函数法(radical basis function, RBF)[5]及线]等. 其中, 径向基函数法基于径向基函数插值技术生成光滑的插值曲面, 是一种常用且快速的无控制网格法. Botsch等[7]通过定义一个三维径向基函数插值变形场并求解线性方程组, 得到径向基函数混合权重以及表示仿射变换的低次多项式的系数, 从而对目标模型进行变形. Levi 等[8]提出采用测地距离作为基函数的距离形式, 实现了较为自然的变形.空间变形技术运算速度快, 且对目标模型的表示方式没有要求, 因此得到了广泛的应用, 然而在进行大尺度变形时, 空间变形技术不能很好地保持模型原有的局部特征. 基于曲面的变形可以很好地解决这一问题

　　9]. 其主要思想是: 预先在目标模型上选择一些顶点作为变形控制顶点, 移动控制顶点, 其他顶点通过优化能量函数发生相应的变化, 从而得到最终变形结果[10]. 在此框架下, Sorkine等[11]提出一种近似刚性(as rigid as possible, ARAP)三维模型变形方法: 将模型中每个顶点以及该顶点1-邻域的三角面片定义为一个单元, 在变形过程中, 将单元实际变换与刚性变换的差值定义为刚性能量函数, 然后在后续操作中基于“变形-求局部旋转-再变形”的迭代过程最小化该函数, 保证每个单元近似刚性变形, 从而尽可能地保持目标模型的局部几何细节. 此后众多学者针对能量函数的定义、单元的定义等对ARAP变形方法提出了改进方案: Levi等[12]提出一种基于旋转光滑项的改进版本的能量函数SR-ARAP, Chen等[13]将 ARAP 方法中的单元从顶点的1-邻域三角面片扩展到r-邻域三角面片, Colaianni等[14]在原 ARAP 的能量形式中加入各向异性的局部变换等. ARAP 算法实现简单, 易于操控, 它是目前基于曲面的变形框架下变形效果较好的算法.在基于三维数字模型的数控加工刀具路径规划领域, 主要方法有偏置刀位点路径截面法(cutter location, CL路径截面法)和刀触点路径截面法(cutter contact, CC路径截面法). CC路径截面法如

　　所示, 用一组平行的约束面与被加工模型求交, 将交线作为刀具接触点路径来生成刀具轨迹[15], 约束面一般是平面[16], 也称为截平面. CC路径截面法可以灵活控制走刀路线, 生成均匀的刀具路径, 因此加工效率较高, 适合复杂模型的加工[17]. 在对CC路径截面的研究中, 邱晓杰等[18]采用二阶连续可导的三次B样条曲线对切片得到的刀触点轨迹进行拟合, 继而按一定的加工步长对其进行插补得到最终的刀触点轨迹. 孙殿柱等[19]针对三角贝塞尔曲面引入R×S树快速准确地获取相交面片集, 并自适应地离散为三角网格, 然后计算截平面与离散后的三角网格的交点并进行偏置作为刀具路径; Li等[20]针对圆角刀具的特性, 利用模型切片数据直接得到刀触点轨迹, 通过刀触点偏置计算刀位点轨迹, 然后进行干涉检测处理得到刀具路径.

　　所示, 有一定风险出现雕穿的现象, 且不能体现橄榄核随形雕刻的艺术特色; 若由专业3D建模设计师使用商业CAD软件制作橄榄核雕刻模型, 再进行数控编程得到加工路径, 整个过程需要跨行业合作, 时间上往往需要数小时甚至数天, 有较高的人工成本与时间成本, 最终效果与设计师的技术水平、审美水平高度相关, 不具备可复制性, 不能批量生产, 同时个性化设计较为复杂.

　　首先, 输入橄榄核模型与待雕刻模型, 基于主成分分析法对橄榄核模型与待雕刻模型进行刚性对齐, 继而使用改进的RBF变形算法与ARAP变形算法进行模型变形得到编辑后的待加工模型, 然后基于模型拓扑结构与扫描平面法对编辑后的待加工模型进行模型切片, 再由切片信息作为基数据通过干涉处理与坐标映射生成加工刀具路径, 最后进行雕刻加工, 得到加工成品.

　　与待雕刻模型$G$调整到合适的相对位置.根据两模型的顶点信息, 使用主成分分析法利用协方差矩阵计算得到两模型的主轴, 进而计算得到两模型的方向包围盒

　　所示. 此后, 为方便后续刀路生成过程中刀位点坐标计算, 再将两者共同进行仿射变换至: 主轴与坐标系z轴重合, 橄榄核模型$O$中最低点z轴坐标为0.

　　为使待雕刻模型更好地填充适配橄榄核模型, 在雕刻过程中更好地保留橄榄核自身的特点做到随形雕刻, 需要进行模型变形. 考虑到待雕刻模型与橄榄核模型自身的类圆柱特性, 本文使用改进的基于径向基函数(RBF)的变形算法以及尽可能刚性(ARAP)变形算法, 结合层次包围盒树(bounding volume hierarchy, BVH)进行碰撞检测, 最终实现待雕刻模型随橄榄核模型随形变形的效果.

　　以及表示仿射变换的低次多项式的系数$M,\;t$, 带入式(4)即可得到任一顶点变形后的位置, 也即得到了变形后的模型.2.2.2 基于层次包围盒树的碰撞检测

　　为降低后续碰撞检测计算复杂度, 提高计算速度, 首先对两模型构建层次包围盒树. 其核心思想是使用几何特征简单的包围盒近似表示复杂的几何模型, 在进行碰撞检测时, 仅对包围盒重叠的模型进一步计算. 将包围盒嵌套而构造树状结构, 可以方便地进行逐层求精以及精确求交. 构建层次包围盒树的步骤如下.

　　(4)将当前节点的左节点和右节点分别作为当前节点, 重复步骤(2)与(3)直到所有节点包围盒都只存在一个三角面片.

　　构建BVH树的过程示意图如图7所示, 按上述步骤构造的BVH树是一个二叉树, 其结构如图8所示.依照上述过程完成对橄榄核模型与待雕刻模型建树后, 对两模型进行碰撞检测. 定义碰撞检测函数, 其实现逻辑如下: 输入两节点

　　与${N_B}$, 若两节点不相交则输出false, 结束; 若相交, 则将${N_A}$与${N_B}$依次赋值为其左右子节点, 递归调用该函数, 直至不相交输出false或${N_A}$与${N_B}$皆为叶子节点; 若${N_A}$与${N_B}$皆为叶子节点, 再精确判断两叶子节点对应的三角面片是否相交, 相交输出true, 否则输出false. 将两模型层次包围盒树的根节点${N_O}$与${N_G}$输入到该碰撞检测函数, 返回值为true则代表两模型相交, 返回值为false则代表两模型不相交.

　　所示: 将每一次RBF变形的控制点放缩倍数改为${{{r_d}} \mathord{\left/ {\vphantom {{{r_d}} n}} \right. } n}$,${r_d}$为第2.2.1节求得的放缩倍数. 每进行一次RBF变形后, 都进行碰撞检测, 若不发生碰撞, 则进行下一次变形, 否则结束变形并回退到上一次变形结果. 由于橄榄核模型$O$在整个过程中不进行任何改变, 所以只对其进行一次BVH树的构建, 减少时间消耗.待雕刻模型经过上述变形后效果如

　　(b)所示. 模型变形前后较好地保持了局部细节, 没有出现明显的失线 ARAP网格变形由于橄榄核呈梭形“两头小, 中间大”的特性, 经过基于RBF的变形后, 其两端仍有部分空白空间, 针对这一问题采用ARAP变形对待雕刻模型

　　轴求交, 得到两个相交三角面片, 将三角面片上所有顶点加入控制点集${V_C}$.对控制点集${V_C}$中每个顶点

　　, 取其周围半径为r的球体内的所有顶点作为与该控制顶点v对应的自由点集${V_F}$. 此外, 为简化后续计算, 提升网格变形速度, 取顶点v周围半径为2r的球体内的所有顶点作为与该控制顶点对应的全部感兴趣顶点集${V_I}$,$r = 0.2 \times {{\textit{z}}_{\max}}$.定义控制顶点$v$对应的点集

　　组成的网格为输入网格$S$. 获取输入网格$S$的邻接信息, 定义单元(cell)为网格$S$中顶点${v_i}$及其1-邻域顶点, 定义一个单元变形前后产生的刚性能量如式(9)所示:

　　为该控制点的法向量; 对于自由点, 求解拉普拉斯变形结果作为初始猜测;(2)基于当前顶点位置$p$, 求解

　　. 首先将式(9)带入式(10), 并进行推导化简, 再使用奇异值分解的方法估算出每个单元的最佳旋转矩阵${R_i}$;(3)基于目前最近旋转矩阵${R_i}$, 求解

　　和$p$, 即重复步骤(2)到(3), 直至迭代次数达到设置要求或网格刚性能量小于指定的阈值为止.待雕刻模型进行ARAP变形后如图10(c)–

　　(e)所示, 待雕刻模型可以较好地填充橄榄核模型, 达到了随形状雕刻的效果.3 刀具路径规划刀具路径规划阶段的主要目标为: 根据模型编辑后得到的待雕刻模型, 进行模型切片、干涉处理并根据预置的刀具信息生成可供雕刻机直接读取并执行加工的刀具路径.

　　模型切片是将一组平行的截平面依次与待雕刻模型求交, 得到一系列闭合切片轮廓, 作为生成刀具路径的基数据.

　　中的三角面片, 添加其中与当前截平面相交的三角面片;(5)$i$自增, 重复步骤(3)、步骤(4)直至

　　的增大, 求与当前截平面相交的三角面片所需遍历的面数会减少, 效率得到提高.3.1.2 相交三角面片交点计算由第3.1.1节得到的待雕刻模型与平面

　　以及截平面与所有三角面片的交点. 接下来需要基于模型的拓扑结构将上一小节得到的交点一定顺序排列得到切片轮廓. 在${F_i}$中选择一个未被使用过的三角面片作为种子面片, 基于待雕刻模型的拓扑关系寻找种子面片的邻接三角面片, 直至遍历${F_i}$中所有三角面片. 对于任一特定截平面${\textit{z}} = {{\textit{z}}_i}$, 得到其切片数据的流程如图13所示.图 12

　　中任选一未遍历三角面片作为种子面片; 若能够找到种子面片, 则创建一轮廓数据contour, 并将其与截平面的交点加入当前contour; 进入第二层循环, 基于拓扑结构根据当前三角面片寻找与之相邻的未遍历三角面片, 并将其与截平面的交点加入当前contour; 若找不到种