基于全局无翻转参数化的网格曲面几何纹理激光打印路径生成

Generating Laser Printing Paths for Geometric Textures on Grid Surfaces Based on Inversion-Free Parameterization

摘要: 针对传统曲面网格上几何纹理在激光打印轨迹规划中需要求解复杂的空间求交问题，提出了一种基于全局无翻转参数化的网格曲面几何纹理激光打印路径规划算法。首先采用EBP低扭曲全局无翻转参数化算法将基础曲面展开平面；然后利用平面几何纹理求得分层的切片然后放置在参数域内求得平面分层往复式参数轨迹；最后利用映射分段线性以及双射的特点和高度场映射方法构建空间轨迹。实验结果表明，本算法高效、鲁棒性且扩展性强。

Abstract: We present a novel laser printing path planning algorithm for geometric textures on mesh surfaces that overcomes the complex spatial intersection problems associated with traditional geometric texture laser printing trajectory planning on surface meshes. Our approach is based on an inver-sion-free parameterization of the mesh surface. Specifically, we employ the EBP low-distortion in-version-free parameterization algorithm to flatten the base surface onto a plane. From there, we generate layered slices of the planar geometric texture and place them within the parameter do-main to obtain a planar layered reciprocating parameter trajectory. Finally, we utilize mapping segmentation linear and Bijective properties, as well as height field mapping methods, to construct a spatial trajectory. Experimental results show that our algorithm is efficient, robust, and highly scalable.

1. 引言

在数字艺术、建筑等领域，几何纹理不仅可以被用来增强设计的美学价值和表现力，同时还可以传达特定的信息和情感。在计算机中三维模型表面或者几何纹理往往采用三角形网格表示，但是由于三角形网格缺乏曲面参数等信息，这限制了一些激光打印轨迹对于加工曲面几何纹理的适用性。目前，三角网格曲面的激光或者刀轨迹规划方法主要利用的截平面法、投影法，其求解过程需要大量的求交计算且难以适应复杂的曲面以及复杂的曲面纹理的特征变化 [1] [2] 。

通过曲面参数化的方法可以将高度复杂的三维刀轨规划问题转化到参数平面上的问题，从而有效地完成求解运算维度的降维 [3] [4] [5] 。Xu等人 [6] 、Sun等人 [7] 提出了一种基于调和映射的网格曲面刀轨规划方法，然而该方法未考虑到网格曲面参数化时的拉伸变形量，导致在扭曲过大的情况下形成的轨迹误差较大。许晨旸等人 [8] 修正了Xu等人 [6] 利用保角映射算法，引入了拉伸系数从而减少了映射拉伸变形所造成的误差。Chen等人 [9] 同样利用调和映射生成了复杂网格曲面螺旋刀轨，但其三维轨迹参数直接通过投影的方式转换到参数域内，因而存在一定误差。针对以上问题，Zhao等人 [10] 提出了基于改进的Floater保角参数化算法的简化轨迹参数计算方法，但其计算的轨迹参数仅局限于参数方向上，并未充分考虑网格曲面参数化是分片线性的特点。Xu等人 [11] 利用保角映射算法生成了适用于三维复杂图案雕刻的刀具轨迹生成算法，该雕刻轨迹不需要精确的轨迹参数且可以忽略映射拉伸变形的问题，但算法扩展性很差。

针对上述问题，本文利用全局无翻转参数化算法(Efficient Bijective Parameterizations. EBP) [12] 将基础曲面展平为无翻转、无自交和低扭曲的平面网格，然后将平面纹理的分层交线与参数域构建平面参数化轨迹，最后利用全局无翻转映射的双射和分段线性的特征和高度映射方法构建空间的曲面几何纹理的加工轨迹。该方法由参数以及平面纹理生成，避免了先有算法在直接规划三维带来的复杂的空间求交问题以及其他参数化方法扭曲过大的问题。

2. 算法

采用基于全局无翻转参数化的激光打印路径生成算法能够对三角曲面上的复杂几何纹理进行加工轨迹的规划，算法的基本步骤如下：利用应用三角网格曲面的参数化算法将空间曲面模型映射至平面参数域上；将平面几何纹理分层切削得到平面交线；规划二维的几何纹理分层的激光打印参数轨迹；通过全通过逆映射生成分层的曲面激光打印路径。

2.1. 三角网格的全局无翻转参数化

任意的参数化并不能满足激光打印几何纹理的路径生成算法的需求，因为如果参数化的结果出现翻转或者重叠，则曲面与参数域上的点不能一一对应，这会导致映射前后信息的确实，从而进行路径生成的时候产生了错误的路径。在构建全局无翻转映射之前我们需要先定义网格的扭曲。根据高斯绝妙定理，任何可直接展开成平面的曲面的高斯曲率必须处处为零。这意味着，如果曲面上存在任何一个点的高斯曲率不为零，则该曲面在该点处必然会出现扭曲或变形。设 $f:\Omega \to \hat{\Omega }$ 为几何映射，在域 $\text{Ω}$ 内的任意一点 $x_0$ 的一个领域内作用一个增向量 $\text{Δ}x$ ，得到映射后新的点 $x^{*}$ 可以通过映射f的一阶泰勒式近似表示：

$x^{*}=f\left(x_0+\Delta x\right)\approx f\left(x_0\right)+J_f\left(x_0\right)\Delta x$ (1)

其中 $J_f\left(x_0\right)$ 为映射f在 $x_0$ 处的雅克比矩阵，即增向量 $\text{Δ}x$ 经过 $J_f\left(x_0\right)$ 的线性变换作用于点 $f\left(x_0\right)$ 。由于参数化映射在三角形网格下是分段线性的，所以 $J_f$ 在每个三角形内是常矩阵。对 $J_f$ 进行奇异值分解：

$J_f=U\Sigma V^{\text{T}}$ (2)

其中 $\Sigma =\text{diag}\left\{{\sigma }_1,{\sigma }_2\right\}$ 为 $J_f$ 奇异值构成的对角矩阵，它表示该映射将改点的圆形领域拉伸变形为椭圆形。如图1所示，以三角形经过映射后椭圆形领域的长短轴变为原来的领域半径的 ${\sigma }_1,{\sigma }_2$ 倍。

Figure 1. Geometric significance of singular values of Jacobian Matrix

图1. 雅克比矩阵的奇异值的几何意义

不失一般性，我们假设 ${\sigma }_1\ge {\sigma }_2$ 。当 ${\sigma }_1={\sigma }_2=1$ 时， $J_f$ 是一个旋转矩阵，映射前后三角形完全等，是一个等距映射。当 ${\sigma }_1={\sigma }_2$ 时， $J_f$ 是一个相似矩阵，映射前后三角形相似为共性映射。如果 $\det J_f<0$ ，即 ${\sigma }_2<0$ ，则三角形发生了翻转。为了降低共性、等距扭曲，许多研究者提出了很多能量来表示三角形，其中最常用是Smith等人 [13] 提出的对称Drichlet能量：

$E_{SD}={\Vert J_f\Vert }_F^2+{\Vert J_f\Vert }_F^{-2}={\sigma }_1^2+{\sigma }_1^{-2}+{\sigma }_2^2+{\sigma }_2^{-2}$ (3)

其中 ${\Vert \cdot \Vert }_F$ 表示矩阵的Frobenius范数。

EBP算法 [12] 与前人的工作一致，先将参数化初始化为双射的Tutte嵌入，然后优化避免翻转三角形且确保无相交边界和扭曲最小化的能量：

$\underset{\hat{\mathcal{M}},\hat{\mathcal{S}}}{\min }{E}_d\left(\mathcal{M},\hat{\mathcal{M}}\right)+{\lambda }_b{E}_b\left({\mathcal{B}}_S\right)+{\lambda }_s{E}_d\left(\mathcal{S},\hat{\mathcal{S}}\right)$ (4)

其中 $\mathcal{M}$ 和 $\hat{\mathcal{M}}$ 表示待参数化的曲面和参数化后的曲面； $\mathcal{S}$ 表示算法引入的三角紧密壳网格，它拥有如下的性质：1) $\mathcal{S}$ 是包含 $\hat{\mathcal{M}}$ 且含有少量的非 $\hat{\mathcal{M}}$ 的三角形。2) $\hat{\mathcal{M}}$ 的边界处于 $\mathcal{S}$ 之中，且不处于 $\mathcal{S}$ 的边界 ${\mathcal{B}}_S$ 上。3) $\mathcal{S}$ 的边界 ${\mathcal{B}}_S$ 的边界边远少于 $\hat{\mathcal{M}}$ 的边界边； $\hat{\mathcal{S}}$ 表示 $\mathcal{S}$ 的形变结果。从式(4)可以看到，能量第一项 $E_d\left(\mathcal{M},\hat{\mathcal{M}}\right)$ 是当三角形退化或者翻转时趋于无穷大的三角形失真度量能量，任何现有的无翻转失真度量都可以用来定义该能量，本文使用上述的对称Drichlet能量；能量第二项 $E_b\left(\mathcal{B}\right)$ 表示为边界障碍函数，一但不相邻的边界相交，边界障碍函数就变为无穷大。 $E_d\left(\mathcal{S},\hat{\mathcal{S}}\right)$ 是紧密壳网格变形的失真能量，该能量在优化过程中使其边界可以自由地改变行传以最小化失真。 ${\lambda }_b$ 和 ${\lambda }_s$ 是平衡能量的正参数。该算法的能量的具体实现和参数调整策略以及求解方法见文献 [12] ，这里不做赘述。

2.2. 平面分层参数轨迹的生成

对于给定的基础曲面 $\mathcal{M}$ 和平面几何纹理 $\mathcal{N}$ ，它们拥有共同的世界坐标系。首先利用2.1节提到的EBP方法 [12] 构建曲面 $\mathcal{M}$ 的一个全局无翻转参数化映射 $\varphi$ 从而得到平面参数域网格 $\hat{\mathcal{M}}$ 。然后构建平面几何纹理的z轴分层切片，即求0到几何纹理高度h之需求的分层个数 $N_s$ 个等距与z轴平行的平面与几何纹理之间的交点与交线。然后将得到交点去除z轴分别放置于参数域 $\hat{\mathcal{M}}$ 中。由于平面几何纹理映射能到曲面 $\mathcal{M}$ 且世界坐标相同，所以得到交线均处于参数域 $\hat{\mathcal{M}}$ 中。如图2所示，以一层x轴平行的往复式参数轨迹为例，先构建参数域 $\hat{\mathcal{M}}$ 的轴线包围盒。假设往复式轨迹的间距为 $\Delta l$ ，包围盒的y轴长度为l，包围盒的左下角点为(0, 0)，则共有 $N_l=\lfloor l/\Delta l\rfloor$ 条平行的直线，它们的y轴坐标分别为 $\left(l-N_l\Delta l\right)/2+i\Delta l$ ，其中 $\lfloor a\rfloor$ 表示不大于a的最大整数。将这些直线与参数网格 $\hat{\mathcal{M}}$ 和几何纹理的分层交线求交后得到一系列有序列的交点然后构成了轨迹，最后去除几何纹理交线内部的交点和线段并且连接平行直线的首尾端点以构成往复式平面轨迹。

Figure 2. Generation of planar reciprocating trajectories

图2. 平面往复式轨迹的生成

2.3. 空间分层参数轨迹的生成

如果参数化映射参数化映射 $\varphi$ 为全局无翻转映射，所以对于其逆映射 $\psi ={\varphi }^{-1}$ 而言，在 $\hat{\mathcal{M}}$ 上的每个顶点 ${\hat{x}}_i$ 处都通过该逆映射对应到原基础曲面上唯一且确定的点 $x_i$ ：

$\psi \left({\hat{x}}_i\right)={\varphi }^{-1}\left({\hat{x}}_i\right)=x_i$ (5)

根据三角形网格中参数化映射 $\varphi$ 分段线性且双射的特点 [5] ，在参数域 $\hat{\mathcal{M}}$ 中三角形 ${\hat{f}}_i=\left({\hat{v}}_{i,0},{\hat{v}}_{i,1},{\hat{v}}_{i,2}\right)$ 上的一点 ${\hat{x}}_f$ 均可以对应为曲面 $\mathcal{M}$ 上 $f_i=\left(v_{i,0},v_{i,1},v_{i,2}\right)$ 唯一且确定的一点 $x_f$ ：

$\begin{array}{c}\psi \left({\hat{x}}_f\right)=\psi \left(m\left({\hat{v}}_{i,1}-{\hat{v}}_{i,0}\right)+n\left({\hat{v}}_{i,2}-{\hat{v}}_{i,0}\right)+{\hat{v}}_{i,0}\right)\\ =m\left(\psi \left({\hat{v}}_{i,1}\right)-\psi \left({\hat{v}}_{i,0}\right)\right)+n\left(\psi \left({\hat{v}}_{i,2}\right)-\psi \left({\hat{v}}_{i,0}\right)\right)+\psi \left({\hat{v}}_{i,0}\right)\\ =m\left(v_{i,1}-v_{i,0}\right)+n\left(v_{i,2}-v_{i,0}\right)+v_{i,0}\\ =x_f\end{array}$ (6)

因此利用该性质，可以将上一节的生成的分层平面往复路径映射到曲面 $\mathcal{M}$ 。由于每层的往复路径对于不同高度下平面纹理的切片，所以本文提出高度场的曲面映射方法。对于一层纹理而言，假设该层纹理的切片的z轴的高度为h，此时其空间激光打印路径上的点 $x_f^z$ 是表示为：

$x_f^z=x_f+h\stackrel{\to }{N}$ (7)

其中 $x_f$ 是该纹理z轴切片的平面路径映射到曲面 $\mathcal{M}$ 的点， $\stackrel{\to }{N}$ 表示曲面 $\mathcal{M}$ 在 $x_f$ 处的单位法向量。这有两种情况：1) 如果 $x_f$ 在曲面 $\mathcal{M}$ 的一个三角面片 $f_i$ 内且不处于边上时，此时 $\stackrel{\to }{N}$ 等于三角面片 $f_i$ 的单位法向量。2) 如果 $x_f$ 在曲面 $\mathcal{M}$ 的一个边上，此时无法直接使用面的法向量来表示改点的单位法向量。我们提出了基于面公共边的方向的方法表示改点的单位法向量，具体的表述如下：除了边界边以外，其他的边均是两个面片的公共边，所以边上顶点可以包含该边的面片法向量的平均值，即：

$\stackrel{\to }{N}=\{\begin{array}{ll}\frac{{\stackrel{\to }{N}}_{f1}+{\stackrel{\to }{N}}_{f2}}{\Vert {\stackrel{\to }{N}}_{f1}+{\stackrel{\to }{N}}_{f2}\Vert }\hfill & x_f\in \mathcal{E}\backslash \partial \mathcal{M}\hfill \\ {\stackrel{\to }{N}}_f/\Vert {\stackrel{\to }{N}}_f\Vert \hfill & x_f\in \partial \mathcal{M}\hfill \end{array}$ (8)

其中 ${\stackrel{\to }{N}}_{f1}$ 和 ${\stackrel{\to }{N}}_{f2}$ 表示非边界边中包含该公共边的两个面的法向量。 ${\stackrel{\to }{N}}_f$ 表示边界边所在的面的法向量。

3. 实验及分析

本文采用C++语言来实现上述的空间纹理打印路径算法，其中涉及到的向量和矩阵计算使用Eigen库。为了验证算法的有效性，本文进行了一系列实验来验证本算法生成轨迹的效果。

如图3所示，(a)为微软鼠标样式的基础曲面模型以及附着在上面的几何纹理，该微软鼠标模型含有9722个三角面片以及4996个顶点；(b)为本章算法生成的激光打印空间往复式路径；(c)为本算法生成的激光路径在纹理上附着情况。可以观察到，生成的轨迹与几何曲面形状十分相似，以分层的形式贴合待加工的曲面，同时每层的纹理很好的表示了基础曲面上的几何纹理。同时本文还对大量其他不同基础曲面以及不同纹理运用本算法构建其加工轨迹。本文在实验中设计了12种不同样式的平面几何纹理，它可以生成不同纹理高度、不同纹理单元数量的平面纹理。利用上述的方法生成的纹理算法生成48种不同的几何纹理映射到20中不同的基础曲面上，在这960个实验里均能够快速高效的生成几何纹理的往复式轨迹。部分实验结果的具体效果参考图4。综上所述本算法对于不同复杂的曲面均有良好的适应性，算法鲁棒性高。

(a) 待加工曲面 (b) 轨迹生成结果 (c) 轨迹在曲面上贴合的结果

Figure 3. Reciprocating trajectory generation of geometric textures on face models

图3. 微软鼠标模型上几何纹理的往复式轨迹生成

Figure 4. Reciprocating trajectory generation of geometric textures on different models

图4. 不同模型上几何纹理的往复式轨迹生成

4. 结语

本文提出了基于全局无翻转参数化的网格曲面的几何纹理的激光打印轨迹规划方法，首先利用高效的EBP算法将网格曲面展开成无自交、无翻转、低扭曲的平面二维参数网格；然后利用平面几何纹理的交线以及平面二维参数网格生成往复式平面参数轨迹；最后利用全局无翻转参数化映射分段线性和双射的特点以及高度场的曲面映射方法生成分层的空间往复式轨迹；最后构建了一系列实验来验证本文提出的算法，实验结果表明，使用本文算法生成的轨迹能够很好的包裹空间几何纹理，使用该轨迹加工能够获得期望的效果，本算法鲁棒性高、效率。同时本算法中参数化算法可以更新为其他算法高效的全局无翻转映射算法，框架通用性好。

NOTES

^*通讯作者。