改进的全局参数化方法

洪程　章登义　苏科华　武小平　郑昌金

摘要：

针对多亏格曲面参数化变形较大、运算复杂度高的问题，提出一种改进的基于全纯1形式的全局参数化方法。该方法以参数化的梯度场为出发点，采用更快速的同调群和上同调群计算方法。首先，利用简化的割图法计算曲面的同调群以确定其拓扑结构；其次，定义特定的调和函数计算闭合1形式来构造由梯度场形成的线性空间的上同调群；然后，最小化调和能量将上同调群扩散为调和1形式；最后，线性组合调和1形式构造出全纯1形式并在基本域上积分即得到参数化。由上同调群、同调群相关理论分析表明，该方法所得参数化是一种全局的、边界自由的共形映射。基于多组高亏格模型的实验证明，与原有基于全纯1形式的全局参数化算法相比，本算法视觉效果更好，平均误差更小，运算效率更高。

关键词：

全局参数化；全纯1形式；调和能量；共形映射；割图

中图分类号：

TP391.41

文献标志码：A

Abstract：

Focusing on the issue that nonzero genus surface parameterization has large deformation and high computational complexity， an improved global parameterization approach based on holomorphic 1form was proposed， which starts from the gradient field and adapts easier and faster method to compute homology and cohomology group. Firstly， a simplified cut graph method was used to construct homology group to determine the topology. Secondly， cohomology group of the linear space formed by the gradient field was calculated by defining special harmonic function to figure out closed 1form. Thirdly， homology group was diffused to harmonic 1form through minimizing harmonic energy. Finally， holomorphic 1form was computed by combining linearly harmonic 1form and the parameterization was obtained by integrating holomorphic 1form on the surface basic domain. Theoretical analysis of homology group and cohomology group shows that the parameterization is a global， borderfree conformal mapping. Experimental results based on nonzero genus model show that， compared with the former global parameterization based on holomorphic 1form， the proposed algorithm has better visual effect， smaller average error and higher operation efficiency.

英文关键词Key words：

global parameterization； holomorphic 1form； harmonic energy； conformal mapping； cut graph

0引言

曲面参数化是一种几何处理的基本工具，它将三维曲面投射到标准域（如平面区域、球面、多面体），从而把复杂几何模型的几何处理操作转移到简单几何模型上，大大简化数字几何处理操作，因此广泛应用于纹理映射、曲面可视化、重新网格化和曲面拟合等过程。

参数化本质是一种三维网格曲面与参数域之间的可逆映射关系，一个有效的参数化必须是双射且不能存在网格重叠。理想情况是三角网格曲面与参数域之间的映射等距，但除可扩展曲面外绝大多数曲面难以实现，因此在该过程中必定产生图形扭曲。保证有效性的同时使变形最小成为参数化中的关键问题。随着曲面参数化应用愈加广泛，针对不同参数性质的方法相继提出，以下是五种针对零亏格曲面的经典方法。

1）Floater[1]采用网格顶点与其相连接的顶点的凸組合表示三角网格的平面参数化，通过求解线性方程组得到结果；但是该方法要求边界必须为凸多边形，因此极大程度上限制了其实际应用。

2）能量方程最小化方法关键在于建立能量方程，基于此，在边界条件下求出极值得到参数化。最早由Eck等[2]引入调和映射并在连续Dirichlet积分基础上提出调和能量方程，因调和映射具有局部保角性，从而使角度变形缩小。随后，Desbrun等[3]给出基于曲面高斯曲率积分的欧拉示性函数，引进并最小化二次能量最终得到与文献[2]类似效果；该方法运算复杂度低，但需要固定边界，因此可能产生较大形变。Sander等[4]提出最大限度地减少纹理在曲面上的位置和方向偏移的最小拉伸方法，Jin等[5]将该方法推广至3D，取得了较好效果。

3）最小二乘共形映射方法由Lévy等[6]提出，以正交性和齐次空间理论为基础定义连续的共形映射，并使用最小二乘法逼近离散的柯西黎曼方程得到参数化，取得了较好的保角效果；但不能保证结果为双射，意味着可能存在网格局部重叠。

4）Sheffer等[7]提出的保角展平方法将复杂三角网格分割为多个可展面片进行参数化，并列出一系列约束条件，以防止网格展平重叠，最终取得极小的角度形变；但计算量大，也不能解决多边界问题。

5）最佳等距参数化方法由Hormann等[8]提出，在原始网格和参数域之间引进线性映射，以求解带约束的非线性系统。该方法在平移、缩放、旋转等变换下度量均为定值，无需固定边界，但是运算复杂度较高。

上述五种方法均针对零亏格曲面，而在实际应用中多亏格曲面普遍存在，因此将参数化向多亏格曲面推广十分必要。最经典的方法是Gu[9]在2003年提出的基于全纯1形式的全局参数化方法，基于Hodge理论使用热扩散的方式计算每个上同调类的调和形式，利用Hodge星算子构成全纯形式，这是首次将参数化方法应用到高亏格曲面，为全局参数化开辟新道路。但该方法在奇点的处理效果一般，此外关于同调群和上同调群的构造过程较为复杂，处理速度偏慢。

随后出现了不少基于文献[9]方法扩展的参数化方法及应用。2006年，受到几何处理应用的启发，Ray等[10]结合几何信息，对输入指定的正交向量场提供一种曲率自适应的参数化方法，能实现同时保面积和角度的效果，适合网格化和曲面拟合；但是该方法需指定输入，不能自动完成所有曲面的参数化。Tong等[11]推广到带有锥奇点的1形式方法并用来网格修复和平铺。2009年， Zeng等[12-13]将全纯微分方法应用于计算带多个边界的亏格为0的曲面上的共形映射以及拟共形映射。上述所有的推广方法均在奇点的处理方式提出改进，取得更好的效果，但仍存在提升空间。

除离散全纯微分外全局参数化还有另一种重要方法：里奇流（Ricci Flow），其中较为突出的是cicle packing[14]和circle pattern[15]度量方法。近几年仍有不少学者提出新的全局参数化方法并取得较好的效果。例如2012年Myles等[16]提出基于迭代压扁方式最小化ARAP（AsRigidAsPossible）能量的全局参数化方法，并于2014年提出采用交叉场对曲面四边形网格化，实现对任意输入曲面的参数化[17]。

为了寻找更优的全局参数化方法，所面临的挑战有：一是对结构更复杂的高亏格曲面，如何准确获取其拓扑信息并降低计算复杂度；二是如何保证参数化的有效性，并最小化形变。针对以上问题，本文基于文献[9]提出以下改进：采用改进的割图法计算同调群；定义特定的调和函数求解闭合1形式来构造上同调群。同调群和上同调群理论为改进方法的合理性和可行性提供解释，实验采用多组多亏格模型并从适用性、误差和处理速率进行比较，突出改进之处的效果。

2.1同调群基底

從理论角度探讨，存在诸多计算同调群基底的方法。文献[9]中计算同调群基底的方法是通过诱导边界算子成为Smith标准型。首先将网格采用渐进网格算法[18]简化，例如将4000个面的网格降为400个面的网格；当找到降采样网格的同调群基底后拉回到原始网格并检查每个顶点的邻域以保证每个基底的连通性；最后采用Dijkstra算法简化基底。

本算法用到割图（cut graph）概念，割图是指三角网格曲面上的一族边集，使得曲面去掉这些边后变成拓扑圆盘。Seifertvan Kampen理论可以证明割图的生成元就是同调群的生成元，因此可将求同调群基底转化为求割图基底。

割图相关算法有treecotree decomposition[19]，本文基于文献[19]的思想提出用最小生成树构造割图。文献[19]通过不断迭代执行插入和删除操作，动态更新生成元且不断逼近最短割图，最终得到同调群基底。而在参数化中着重点并非寻找最短割图而是梯度场的基底构造，因此采用过程更为简单的最小生成树方法。

得到割图后利用最小生成树方法计算割图基底，对于每个叶子节点都存在到根节点的一条唯一回路，所有的回路便构成同调群的基底。

算法1计算曲面割图。

输入：曲面M；

输出：曲面割图G。

1）计算对偶曲面，顶点v的对偶为面，面f的对偶为顶点，边e的对偶为；

2）采用广度优先搜索构造的最小生成树；

3）返回G={e|}。

算法1所得割图G可迭代删除与度为1的顶点相连的边，以减少后期不必要的运算。沿割图G剪开曲面M得到曲面基本域D。

算法2计算同调群基底。

输入：割图G；

输出：同调群基底H1（M）。

1）G中选定根节点v，构建最小生成树T，记每个叶子节点vi到根节点v的唯一路径为γi；

2）GT={e1，e2，…，e2g}，对ek∈GT，且ek =[vi，vj] 则存在回路lk = γi[vi，vj]γ-1j；

3）返回同调群基底H1（M） ={l1，l2，…，l2g}。

从时间复杂度上分析，文献[9]引进渐进网格算法简化的原因是在诱导中本身会产生大量计算花费，同时这种类似降采样的方式虽然能提高计算效率，但是不能完全保留原始网格信息，对同调群基底的构造具有局限性。当对亏格为g，顶点数为n的网格参数化时，简化网格的时间复杂度为o（n log n），诱导边结算子为Smith标准型的时间复杂度为o（n2），拉回到原始网格后需遍历检查每个顶点的邻域关系o（n），总的时间复杂度为o（n+n log n+n2）。而本算法只需要两次遍历，平均时间复杂度为o（n log n）。相比之下，用改进的割图法求同调群的算法过程更简单，时间复杂度更低。

2.2上同调群基底

文献[9]先选取任意两个同调群基底并沿基底剪开曲面；然后将剪开的曲面映射到单位矩形或单位圆盘，计算其对偶1形式；最后将对偶1形式拉回原曲面，直至所有同调群基底遍历完毕得到上同调群基底。

本算法利用同调群和上同调群的对偶关系定义特定的调和函数计算闭合1形式，组成上同调群的基底。首先将曲面M沿着割图G剪开得到拓扑盘，每条半边∈都唯一对应一条半边h∈M。将边界上的点按序排列，={v0，v1，…，vk，vk+1，…，vn-1}。假定M上的半边h+i，h-i均与边e相邻，那么在上：

+i=[vk，vk+1]，-i=[vs，vs+1]

接着构造调和函数fi：→R，满足：

fi（vj）=0，vj

1，vj∈，k

0，vj∈，s

然后定义闭合1形式ωi（h）=dfi（），那么Ω={ω1，ω2，…，w2g}便组成了上同调群H1（M）的基底。

算法3计算上同调基底。

输入：亏格为g的闭合曲面M；

输出：上同调群基底H1（M）。

3实验结果与分析

实验环境为Windows 8.1操作系统，Intel i5 4200处理器，1.6GHz主频，4GB内存。使用VS2010、C++编程实现，采用图形处理库openMesh 3.3，矩阵计算工具Eigen 3.2.4。输入的网格文件格式为off格式，显示网格的可视化软件为基于开源软件MeshViewer二次开发的miniMeshViewer。实验分析将从本算法对高亏格曲面的适用性和对数据的处理效率两方面入手。

3.1适用性

第一组实验模型如图1所示，从上到下、从左至右编号为1～6，亏格分别为1、2、3、5、6、7。本算法和文献[9]算法的参数化结果对比如图2所示。

一般衡量参数化之好坏主要使用以下两种方法，第一种是通过视觉上的平滑效果进行主观判定，但人眼无法分辨更细微的差异；另一种是采用度量的方法，计算三维网格和参数域之间的几何度量偏差[20]，得以衡量整体形变。

首先通过直接的观察判断两种算法的整体效果，由图2所示知两者对非边界区域的处理均较为合理，无明显的变形。现放大边界处区域进行仔细对比，由于本算法与文献[9]均采用梯度场的方法，生成的同调群基底各有所异，故现在分别考量割图同伦群基底即衔接之处的细节，图3展示编号为1、3、6模型的局部放大结果。

由图3可知，两者在割图分裂之处均存在不连贯细节，原因在于两种方法均立足于全纯微分方法，差异在于获取曲面拓扑结构和梯度场的构造方法。仔细观察文献[9]所展示的锯齿状更为明显，黑白棋盘的交错更加剧烈，究其根源是采用了渐进算法简化网格，而本算法利用改进的割图方法去构造同伦群基底更加精准，保留曲面的所有信息，故而取得相对连贯的效果，但仍存在改进空间。

然后通过计量顶点和面积的平均相对偏差来估量两者孰优孰劣，计算公式[20]如下：

Distarea=∑jS（Tj）∑Ti∈MS（Ti）-S（T*j）∑Ti∈MS（T*i）2

Distangle=∑j∑i=1，2，3Ai2π-A*i2π+e2

其中： j為网格的三角形个数指标，S和A是三角形面积和角度，e表示三角形的角盈。该误差测量是一个整体变形度量，实验数据如表格1所示。

从表1可对比得，当曲面亏格越高，两者的误差差距更加明显，证实本文算法相对文献[9]取得更小的平均误差。其中缘由在于本文算法采用调和函数计算闭合1形式去构造梯度场的基底，更贴近曲面的真实情况，文献[9]基于映射到单位矩形或单位圆盘求对偶1形式的方法不可避免会对梯度场造成扭曲，故而产生额外的误差。综合直观效果和误差数据分析，总体上说，本文算法实现了对高亏格曲面的参数化，并取得较小的形变误差。

3.2处理效率

为了凸显本文算法效率的提高，第二组实验采取数据规模更大的实验模型，如图4所示，从上到下、从左至右编号分别为7～12。关于第二组实验模型的数据属性和实验结果如表2所示。因每次实验需随机取点以计算同调群基底，而其所生之基底皆相异，所以采用平均时间来度量。

的差异越来越大，可知本文算法相对于文献[9]所述方法，在计算速度上有较大提高。考虑算法本身的平均时间复杂度是o（g3n log n），与网格的大小（点、边、面数）、亏格g有关，取得提升的根本原因得益于求同调群和上同调群过程的简化。一方面，基于割图的思想且绕开寻找最优割图采用最实用的最小生成树方法计算割图及其基底，降低了构造同调群的时间花销；另一方面，采用特定的调和函数逐一计算同调群基底的对偶形式，避免重复剪开、映射曲面的中间过程，精简了计算过程。

4结语

本文基于文献[9]改进的全局参数化方法利用同调群和上同调群的理论对多亏格曲面实现了更连贯的视觉效果和更高的处理效率，并且能控制角度和面积平均误差在更小的范围内，因此提高了在实际应用如纹理映射中的适用性。但是在曲面同伦群基底的边界处理上仍有提升的空间，未来将深入探究如何在不同的参数化结果中筛选最优解。

参考文献：

[1]

FLOATER M S. Parametrization and smooth approximation of surface triangulations [J]. Computer Aided Geometric Design， 1997， 14（3）： 231-250.

[2]

ECK M， DEROSE T， DUCHAMP T， et al. Multiresolution analysis of arbitrary meshes [C]// SIGGRAPH 95： Proceedings of the 22nd Annual Conference on Computer Graphics and Interactive Techniques. New York： ACM， 1995： 173-182.

[3]

DESBRUN M， MEYER M， ALLIEZ P. Intrinsic parameterizations of surface meshes [J]. Computer Graphics Forum， 2002， 21（3）： 209-218.

[4]

SANDER P V， SNYDER J， GORTLER S J， et al. Texture mapping progressive meshes [C]// SIGGRAPH 01： Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques. New York： ACM， 2001： 409-416.

[5]

JIN Y， QIAN G P， ZHAO J Y， et al. Stretchminimizing volumetric parameterization [J]. Journal of Computer Science and Technology， 2015， 30（3）： 553-564.

[6]

LVY B， MALLET J L. Nondistorted texture mapping for sheared triangulated meshes [C]// SIGGRAPH 98： Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques. New York：ACM， 1998： 343-352.

[7]

SHEFFER A， DE STURLER E. Parameterization of faceted surfaces for meshing using anglebased flattening [J]. Engineering with Computers， 2001， 17（3）： 326-337.

[8]

KAI H， GREINER G. MIPS： an efficient global parametrization method [C]// Curve & Surface Design： Saint-Malo. Nashville：Vanderbilt University Press， 2000.

HORMANN K， GREINER G. MIPS： an efficient global parametrization method [EB/OL]. [20151123]. http：//www.inf.usi.ch/hormann/papers/Hormann.2000.MAE.pdf.

[9]

GU X， YAU S T. Global conformal surface parameterization [C]// SGP 03： Proceedings of the 2003 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing. AirelaVille， Switzerland： Eurographics Association， 2003： 127-137.

[10]

RAY N， LI W C， LVY B， et al. Periodic global parameterization [J]. ACM Transactions on Graphics， 2006， 25（4）： 1460-1485.

[11]

TONG Y， ALLIEZ P， COHENSTEINER D， et al. Designing quadrangulations with discrete harmonic forms [C]// SGP 06： Proceedings of the 4th Eurographics Symposium on Geometry Processing. AirelaVille， Switzerland： Eurographics Association， 2006： 201-210.

[12]

ZENG W， YIN X， ZHANG M， et al. Generalized Koebes method for conformal mapping multiply connected domains [C]// SPM 09： Proceedings of the 2009 SIAM/ACM Joint Conference on Geometric and Physical Modeling. New York： ACM， 2009： 89-100.

[13]

ZENG W， LUO F， YAU S T， et al. Surface quasiconformal mapping by solving Beltrami equations [M]// HANCOCK E R， MARTIN R R， SABIN M A. Mathematics of Surfaces XIII， LNCS 5654. Berlin： Springer， 2009： 391-408.

[14]

RODIN B， SULLIVAN D. The convergence of circle packings to the Riemann mapping [J]. Journal of Differential Geometry， 1987， 26（26）： 349-360.

[15]

KHAREVYCH L， SPRINGBORN B， SCHRDER P. Discrete conformal mappings via circle patterns [J]. ACM Transactions on Graphics， 2006， 25（2）： 412-438.

[16]

MYLES A， ZORIN D. Global parametrization by incremental flattening [J]. ACM Transactions on Graphics， 2012， 31（4）： Article No. 109.

[17]

MYLES A， PIETRONI N， ZORIN D. Robust fieldaligned global parametrization [J]. ACM Transactions on Graphics， 2014， 33（4）： Article No. 135.

[18]

HOPPE H. Viewdependent refinement of progressive meshes [C]// SIGGRAPH 97： Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques. New York： ACM Press/AddisonWesley Publishing Company， 1997： 189-198.

[19]

EPPSTEIN D. Dynamic generators of topologically embedded graphs [C]// SODA 03： Proceedings of the 14th Annual ACMSIAM Symposium on Discrete Algorithms. Philadelphia， PA： SIAM， 2003： 599-608.

[20]

胡國飞，方兴，彭群生.凸组合球面参数化[J].计算机辅助设计与图形学学报，2004，16（5）：632-637.（HU G F， FANG X， PENG Q S. Convex combi nation spherical parameterization [J]. Journal of ComputerAided Design and Computer Graphics， 2004， 16（5）： 632-637.）