浅谈网格参数化算法及应用

周丽勤 顾立志

【摘 要】网格参数化不仅可以应用在计算机图形学，还可以应用在计算机几何设计及逆向工程、虚拟技术等诸多领域。文章根据不同的参数域，简述了网格参数化的不同算法及各种算法在不同领域的应用和优缺点，并简述如何控制参数化变形的方法。

【关键词】网格参数化;参数域;控制参数变形

【中图分类号】TP391.7 【文献标识码】A 【文章编号】1674-0688（2019）05-0113-03

在计算机图形学、逆向工程、增材制造、虚拟技术等领域的几何模型大部分是以网格的形式表示。网格模型所表达的物体数据是凌乱、离散、无序、难以利用的。直接处理这些网格模型是比较困难的。网格参数化是指为网格模型表面建立一一映射的参数域，映射后得到的参数化网格的拓扑关系同构于原始曲面网格，且几何度量的变形最小化。从而对复杂网格模型的处理可以转化为相对简单的参数化网格处理。

网格参数化方法可根据参数域的不同分为平面参数化、基网格参数化、球面参数化、柱面参数化及交叉参数化。不同的网格参数化方法都被不同程度地应用到网格纹理映射、网格重构、网格压缩编辑[2]等领域。

1 网格参数域的分类

1.1 平面参数化

平面参数化是把一个空间三角网格尽可能均匀地摊平到某个平面区域，平面参数化是目前研究得最多、最简单的参数化算法。Floater在Tutte等人提出凸组合方法的基础上给每条边附加一个与边长相关的权值，进面得出改进后的凸组合方法。Floater提出保形参数化和均值参数的研究，一般是先固定网格边界，用线性函数作为变形度量，这样计算相对简单，但得不到自由边界的网格参数化结果，只能应用于与拓扑圆盘同构的网格曲面。所以，对于亏格大于0的网格曲面，如果按一定规则来划分网格，往往会引起参数化结果不连续，并且在某些部位容易造成较大的变形[1]。

1.1.1 保相似的平面参数化

张磊等人[3]提出了保相似的平面参数化，这种方法的优点是建立相应三角形的相似性。通过控制网格的相邻两边的夹角和长度比例，在最小二乘的意义下基本保持不变，进而达到三角形的相似。此方法也适用于添加任何线性约束条件，与现有的一些方法相比，该算法几何意义直观，而且求解速度很快，参数化的结果也比较理想，操作简便。缺点：无法保证平面参数化结果的有效性，即不会发生三角片的翻转[3]。保相似平面参数化和Sheffer方法的对比如图1所示。

1.1.2 基于邻域多边形特征的网格参数化

因保相似平面参数化，在距离约束点较远的网格处有较大的参数化变形。彭威等人[4]利用保相似原理，通过邻域多边形顶点建立了网格顶点一阶邻域多边形特征方程组，求解该线性方程组得到了空间网格在二维平面上的展平结果[4]。此方法适用于包含三角形和四边形单元的混合网格模型，得到的参数化结果具有自由的边界，且使得网格参数化扭曲较小。例如：工程零件、汽车钣金类零件网格模型。车身侧板模型网格参数化对比图如图2所示。

1.1.3 ARAP参数化

Liu等人[9]提出一种可以在保角和保面积中，取得较好的平衡的非线性能量函数，这种函数算法仅适用于与拓扑圆盘同构的网格曲面，不足之处在于此算法无法保证局部单射[1]。后来Myles等人[8]在ARAP算法的基础上，改进了ARAP算法，使之更能适用于全局参数。解决方法如下：将ARAP参数化方法从拓扑圆盘曲面拓展到三维网格曲面。用全局参数化算法优化等距误差。此能量函数方法可以在保角和保面积中取得较好的平衡，不会因为为了保角使得面积发生很大的变形。

文献[5]中提出基于尽可能保形（As-Rigid-As-PosSible，ARAP）参数化的約束纹理映射算法，使得三维人脸网格三角形角度变形和面积变形均达到最小，进而使得纹理映射的形变最小。并利用比例嵌入方法控制形变，使映射效果更加自然，而且减少了优化次数。

1.1.4 ABF++保角参数化

文献[5]中提出基于ABF++保角参数化的网格曲面刀轨规划方法。通过保角参数化算法，可以将三维网格展平到参数域内，分析参数网格映射后产生的变形量，并由变形量计算出每个三角片内的映射拉伸系数与梯度，将三维网格上的轨迹参数转换为二维，再根据参数域内的二维轨迹参数直接生成线性刀具轨迹和非线性刀具轨迹。

ABF++算法计算速度快，角度变形较小，如果网格模型不存在边界处变形较大的问题，可保证三维网格与参数网格之间的一一映射关系[5]。

1.2 基网格参数化

基网格参数化属于全局参数化，适用于亏格大于0的网格曲面。基网格参数化的主要优点是可以保留原始网格的拓扑关系，减少后续参数处理所造成的变形。

基网格参数化算法是通过种子点构造Voronoi图，以及Voronoi图的对偶Delaunay三角剖分形成的，之后使用调和映射计算内部顶点的参数值。虽然之后有自适应曲面参数化、三角基网格、四边形基网格[1]。

1.3 球面参数化

球面参数化的研究方法有球面松弛法、严寒冰等人提出的采用球面坐标计算凸组合球面参数化的凸组合法及周昆等人提出的累进网格方法。

球面参数化产生的变形扭曲较大、计算困难、失真程度高，因此此算法主要适用于0亏格的闭曲面（如图3所示）。

1.4 柱面参数化

郭潇晟等人[7]对于形态接近于圆柱或具有单支简单骨架的封闭、半封闭的网格模型，提出一种骨架引导的网格模型圆柱面参数化方法。

柱面参数化研究方法：先引入超柱面参数域定义，通过模型的简化建立其与超柱面的基本映射关系，再将顶点反插入柱面参数域来恢复原模型拓扑，进而对初始参数化结果，运用拉伸形变尺度的优化，实现基本的柱面参数化;对于具有强骨架信息的复杂模型[7]，由于超柱面侧面可展，超柱面参数化适用于对0亏格封闭模型的参数化。并且对人体和动物等可以通过骨架指引对人体、动物等0亏格封闭模型进行超圆柱面参数化，这样减小了模型的几何形变。相对于球面参数化，柱面参数化变形会小一点。

1.5 交叉参数化

与基网格参数化类似，交叉参数化通常需要一个公共参数域。可以通过对原始网格进行简化作为基参数域，也可以通过自动生成模板参数域及采用四边形面片作为公共基参数域。交叉参数化一般应用于曲面间变形及曲面混合（blending）等（如图4所示）。

这些方法研究的困难在于以下几个方面：①对于狭长和复杂的网格，难于在健壮和效率之间取得平衡。②因公共参数域的映射误差在后续映射被放大，这样会造成曲面间的变形相对较大。③面片间不连续，这样就需要对网格进行各种后处理。

后续研究可以考虑将柱面参数化方法作为交叉参数化方法的公共参数，以减少各面片之间不连续。

2 减轻参数变形方法

2.1 锥状奇异点

文献[4]直接把原始网格的顶点作为锥状奇异点，将部分锥状奇异点进行算法处理得到曲率为0的点，接下来采用贪心策略算法优化这些低失真的原始网格曲面，这样参数化的曲面变形相对较小。这样通过原始网上的锥状奇导点可以避免映射误差被放大，同时可以减小参数化变形的产生。

2.2 变形能量优化

文献[12]对MIPS（Most-Isometric Parameterizations）、BDM（有界失真映射）、LIM（局部内射映射）、AMIPS（能量函数）及ABF++（Fast and Robust Angle based flattening）基于角度空間的保角参数化算法作了大量的对比研究。从最大偏差、平均偏差和标准偏差对比到最大角度扭曲、均值角度扭曲及各种算法的运行时间等都进行了研究，最后得出结论：AMIPS（能量函数）的优点是能够抑制网格曲面的最大变形，这样就能进一步地控制变形分布，实现局部单射。AMIPS相对其他能量优化函数的计算速度仅次于ABF++，扭曲变形相对较小，能够比较好地保持等距;ABF++算法计算速度快，但是会产生较大的偏差，从而造成曲面产生大的曲面变形;BDM算法虽可以限定扭曲上界，但不易选择，算法运行时间长;LIM算法的优点是均值扭曲小，可是最大值扭曲高。每个算法都有其优缺点，可以根据不同场合及需要达到的效果进行选择。

3 总结

网格参数化为了适应不同的场景有不同的参数化算法，从而获得高质量的网格参数化。不论哪一种算法，其目的都是让网格有较小的扭曲，减少变形量，降低失真性。这需要运用不同的数学算法对原始网格信息进行处理。文中通过保角度、保面积、保特征、柱面特征族及能量函数等方法，使参数化简单化，原始网格失真性低来对图形进行处理。这个过程需要涉及很多领域，如逼近理论、应用数学和有限元建模、数字图像处理等。本文中提到的参数化算法，只是网格参数化中的一小部分，还有半自动网格参数、自动网格参数化、全局参数化、局部参数化等，需要我们不断学习和研究。

参 考 文 献

[1]郭凤华，张彩明，焦文江.网格参数化研究进展[J].软件学报，2016，27（1）：112-135.

[2]钱江，陈志杨，叶修梓，等.基于参数化技术的网格分割[J].浙江大学学报（工学版），2008（8）：1370-1375.

[3]张磊，刘利刚，王国瑾.保相似的网格参数化[J]. 中国图象图形学报，2008，13（12）：2383-2387.

[4]彭威，陈文亮.基于邻域多边形特征和能量优化的网格参数化[J].中国机械工程，2011，22（22）：2694-2699.

[5]闫婷，齐美彬，蒋建国，等.基于ARAP参数化算法的约束纹理映射[J].合肥工业大学学报（自然科学版），2017，40（6）：757-762.

[6]许晨旸，李静蓉，王清辉，等.利用ABF++保角参数化的网格曲面刀轨规划[J].计算机辅助设计与图形学学报，2017，29（4）：728-733.

[7]郭潇晟，郭延文，郭凯，等.骨架引导的网格模型圆柱面参数化[J].计算机辅助设计与图形学学报，2011，23（1）：161-169.

[8]Myles A，Zorin D.Global parametrization by incremental flattening[J].ACM Trans. on Graphics，2012，31（4）：109-111.

[9]Liu L，Zhang L，Xu Y，et al.A local/global approach to mesh parameterization[J].Computer Gr-aphics Forum，2008，27（5）：1495-1504.

[10]Wu H，Pan C，Zha H，et al.Partwise cross-parameterization via nonregular convex hull domains. IEEE Trans[J].on Visualization and Computer Gra-phics，2011，17（10）：1531-1544.

[11]Zayer R，Rssl C，Seidel HP.Curvilinear spherical parameterization. In：Proc. of the 2006 Intl Conf.on Shape Modeling and Applications（SMI 2006）[J].IEEE Computer Society，2006（4）：57-64.

[12]Fu X，Liu Y，Guo B.Computing locally injective mappings by advanced MIPS[J]. ACM Trans. on Graphics，2015，34（4）：71-72.

[责任编辑：陈泽琦]