三角网格曲面共形参数化研究综述

2021-09-19李海生曹国梁吴晓群

图学学报 2021年4期

李海生，曹国梁，魏阳，吴晓群，蔡强

(1.北京工商大学计算机学院，北京 100048；2.食品安全大数据技术北京市重点实验室，北京 100048)

随着3D 采集技术的日趋成熟，大量三维模型数据被应用于各个领域，其复杂的几何外形，使得三维曲面表面网格处理成为一项艰巨的任务。以纹理映射为发端，曲面参数化[1-2]逐渐成熟起来，通过建立三维曲面到特定参数域的映射关系，把三维网格参数化到参数域空间，并对参数化后的网格进行处理，为复杂曲面的处理提供了新的角度。

参数化探讨的是：给定一个由空间点集xi∈R3组成的三角网格曲面S和一个参数域D，寻求一个在参数域上的点ui∈D到xi∈S的一一映射ψ，使得参数域上的网格与原始网格拓扑同构，并在保证参数域上所有三角网格之间不相互重叠的同时，寻求与原始网格之间几何度量的变形最小化，即畸变最小化。本文讨论的所有曲面都是黎曼曲面，即连通的一维复流形。

根据参数化特点的不同，主要分为等距、保面积[3]和保角参数化。保角参数化在变换前后保持曲面三角网格夹角不变的同时保持了曲面的局部形状，所以又称为共形参数化，能够对任意拓扑曲面进行参数化。

用S和S*分别表示源曲面和目标曲面，φ:S→S*表示映射。令(x,y,z)表示源曲面局部坐标，(u,v)表示目标曲面的局部坐标，映射的局部表示为

假设φ:S→S*是微分同胚，γ1,γ2S⊂ 是原曲面上曲线，相交于点p＝γ1∩γ2，如图1 所示。在交点p处，曲线的切向量交角为θ。φ曲线γ1,γ2映射成目标曲面上的曲线φ（γ1）,φ（γ2），相交于φ（p），并且曲线φ（γ1）,φ（γ2）在φ（p）处的交角也等于θ，即

图1 保角变换示意图 Fig.1 Diagram of conformal transformation

如果上式对应一切可能的曲线γ1,γ2均成立，则映射φ被称为保角变换，也称共形变换。由于计算机处理离散曲面，很难满足完全保角的情况，所以共形性也常常被称作最大相似性(similarity)。

对于共形参数化而言，结合不同参数域的选择，往往能够确定参数域的边界以及函数求解方法。本文主要以参数域作为分类依据，综述了近年来基于三角网格曲面的共形参数化方法，对现有的参数化算法进行优缺点比较，并讨论了共形参数化目前存在的主要难点问题和今后可能的发展趋势。

1 相关概念

曲面共形参数化方法不仅利用拓扑性质，还依赖于各类离散理论对网格进行度量。如，微分1 形式、同伦群基底、圆填充理论等。下面简要介绍几类广泛应用于共形参数化的相关概念与理论基础。

1.1 调和映射

如果曲面有类似圆盘一样的拓扑结构，即曲面是带有边界的单连通曲面，那么调和映射[3]就能解决共形参数化的问题。黎曼流形间的调和映射是学习几何和拓扑的重要工具。调和映射的数学本质是求解一个椭圆偏微分方程，这使得计算能够有效进行并得到稳定的数值解。目前调和映射最常见的就是采用离散拉普拉斯-贝尔特拉米(Laplace-Beltrami，LB)算子[4]，LB 算子是Laplace 算子在流形上的推广。如果有顶点数为n的三角网格M，f是定义在M上的函数，则该函数在顶点vi处的离散LB 算子为

其中，ωij为作用在边ij上的权重，根据ωij取值的不同，调和映射的结果也不同。调和映射的思想就是寻找合适的能量函数，通过对函数优化从而使得调和能量最小。特别的对于零亏格闭合曲面，在自由边界的前提下调和映射和共形映射等价。

1.2 拟共形映射

拟共形参数化和共形参数化不同之处在于共形参数化将曲面上无穷小圆映射成无穷小圆，而拟共形参数化则将曲面上无穷小圆映射成无穷小椭圆，曲面的局部形状不能被完好保持。但是对于找不到共形参数化方法的曲面而言，拟共形映射也是很好的补充。

1.3 离散曲率流

曲率流，顾名思义，就是让曲率像热流一样进行扩散。通过将曲面黎曼度量形变，使得曲面的曲率依随时间而演化，最后曲率趋于一个常数，从而将三维曲面展平到二维参数域，即寻找一个合适的能量函数，使曲率流能得到唯一的最优解。

1.4 同伦群基底

通常对于较为复杂带亏格三角网格曲面的参数化需要先求曲面的一个切割图，使得曲面在切割之后拓扑上等价于圆盘。其切割图中每个度不等于2 的节点将切割图分成一系列分支{a1,b1,a2,b2,…,ag,bg}，这些分支就是基本群的生成元，也叫基本群的基底。假设有一个曲面S，q∈S是在S上的基点，这里的基点是指满足有理参数曲面张量积为零的参数对，g为曲面亏格数。在曲面S上，从q出发最终又回到q而没有交叉点的线路组成了通过q的回路。如果任意2 条通过q点的回路l和lʹ可以在不离开曲面S的情况下从一条回路连续地变换成另外一条，称这2 条回路彼此同伦，所有同伦回路构成同伦类。所有同伦类形成同伦群表示为π1(S,q)。π1(S,q)的一组生成元由{a1,b1,…,ag,bg}组成。图2(a)表示同伦群π1(S,q)其中的一组生成元{a1,b1,a2,b2}，图2(b)显示了S的一个基本域，其边界表示为庞加莱给出了二维曲面拓扑同胚的前提，即当且仅当其的基本群同构。因此可以通过计算曲面的同伦群基底将带亏格曲面映射到基本域。

图2 基本群的典范基底及其基本域 ((a)通伦群基底；(b)基本域) Fig.2 A set of canonical basis of the fundamental group ((a) Homotopy group basis;(b) Fundamental domain)

1.5 圆填充理论

圆填充(circle packing，CP)就是在离散情形下，通过CP方法[5]的引入在网格的每个顶点处设置一个圆，圆的半径即为网格的度量。在不同几何背景中，在共形形变保证圆与圆交角不变的情况下，通过改变半径，达到参数化的目的，如图3所示。在网格上，顶点的曲率一般和网格边长相关，而CP 理论成功地建立了曲率与网格顶点的关联，这样通过改变在顶点上圆的半径就能使曲率跟随变化。

图3 圆填充示意图 Fig.3 Diagram of circle packing

1.6 离散Ricci 流

Hamilton 定义了关于高斯曲率的Ricci 流[6]，即

其中，g(t)为与时间相关的度量；K(t)为随时间而变化的高斯曲率。将其推广到离散情形，即

离散曲率流通常采用CP 度量作为网格初始度量，在得到边长后利用余弦定理计算出网格中每个三角形{vi,vj,vk}的内角角度θi,θj,θk，以θi计算为例，即

其中，θi为在三角形{vi,vj,vk}中以vi为顶点的角；li为顶点vi对应的边ljk的边长，不同嵌入背景下角度余弦定理的计算不同。由此可以计算出网格上每个点vi的离散高斯曲率

离散高斯曲率被定义为角欠(angle deficit)，对于内顶点，角欠就是围绕顶点的周角与2π作差，对于边界顶点，则与π作差，角欠在一定程度上反映了曲面局部的凹凸变化。

2 参数域

参数化的应用决定了参数化的首要步骤就是确定一个合适的参数空间。根据曲面拓扑结构的不同，几何背景通常是欧氏平面、单位球面和二维双曲空间中的一种。根据不同的几何背景，参数化的参数域选择往往不同。根据参数域的不同，把共形参数化分为平面域、球面域和双曲空间域3 类(图4)。

图4 参数域分类示意图 Fig.4 Diagram of parameter domain classification

3 平面域

对于共形参数化而言，参数域通常是平面域，平面也是欧式空间中最常见的二维表示。平面参数化最早主要用来进行3D 纹理贴图，对于纹理和图像而言，平面是最自然的载体，对平面图像的处理复杂度远小于直接操作三维曲面。从应用的角度最为常见的平面域就是固定边界，但在参数化的过程中可能导致边界网格变形严重，为了解决边界参数化失真的情况，自由边界参数化和无缝参数化得到发展，但是推广到复杂拓扑曲面的情形，这2 类参数化往往效果不佳。

针对平面域，主要有以下几类常见共形参数化方法。

3.1 固定边界参数化

早期的平面参数化方法大多将原始网格映射到平面凸多边形上，即首先找到原始网格的边界，并将边界点映射到平面凸多边形上，然后将每个内部点表示为其一环点的加权平均，最后通过求解线性方程组得到相应的参数化结果。其中有代表性的是TUTTE[7]的凸组合嵌入；文献[3]最早介绍的离散调和映射；还有FLOATER[8-9]的保形参数化和基于调和函数中值定理提出的均值(mean-value)参数化方法，以上方法的区别在于使用了不同的加权方法。

对于带有多边界的联通曲面，共形几何理论[10]保证其能被共形映射到平面圆域上，平面圆域的好处在于无论边界点个数多少，总能保证参数域边界光滑，以确保视觉效果良好。此外，圆域中心和半径都是由曲面的几何决定的，其更能保持曲面局部形状。这类参数化中的经典当属Koebe 迭代方法[11]，如图5 所示，文献[12]提出广义Koebe 迭代方法，即对传统Koebe方法中圆盘映射

图5 传统Koebe 迭代方法[11] ((a)多边界曲面；(b)首次共形映射；(c)第二条外圆边界；(d)内部区域填色；(e)第二次共形映射) Fig.5 Conventional Koebe’s iteration method[11] ((a) Multi-boundary surface;(b) First mapping;(c) The second boundary; (d) Filling color;(e) Second mapping)

每次选择2 个边界映射成环，保留Koebe 迭代线性高效的同时，加快了函数收敛速率，提高了计算效率。

对于零亏格曲面，GU 和YAU[13]提出一种非线性优化方法来计算零亏格曲面的全局共形参数化，该方法对球的切平面进行优化，不足之处为算法梯度下降过程慢，并且处理细长特征时容易产生网格重叠的现象。在此基础上，CHOI 和LUI[14]优化了共形结果，提出了一种针对圆盘拓扑曲面的线性参数化方法，如图6 所示。通过求解稀疏对称正定线性方程组，结合拟共形映射减小共形扭曲以确保函数双射，能够处理尖锐且不规则的三角网格，提高了计算效率。但该方法目前还不能最优分配边界顶点，这样效果会受到影响。

图6 圆盘线性参数化[14] ((a)输入模型；(b)双重覆盖；(c) Choi 改进) Fig.6 Linear parameterization of disk topology[14] ((a) Input model;(b) Double covering;(c) Choi’s improvement)

对于单亏格曲面的共形参数化，常常使用微分1 形式和曲率流进行计算。不同于曲率流，微分1形式计算一个全纯映射，进而给出曲面的一种度量，共形于原度量。文献[15]中实现了单亏格曲面共形结构的计算，该方法基于Hodge 理论[16]，通过将全纯1 形式与亏格相关的奇点数相结合来获得给定曲面的平坦度量。算法首先计算网格曲面的同伦群基

并对每个ωi计算与之上同调的唯一的调和1 形式ζi，接着计算每个ζi的共轭，记为*ζi，从而构造全纯1 形式

对以上全纯微分基形式进行求积分，便能得到对应的共形映射。该方法可找到一个全纯1 形式的完备基。

LUO[17]研究了曲面上的离散Yamabe 流，并将其作为微分1 形式的积分对曲面上的度量进行共形变化，通过使用余切拉普拉斯方程将曲率进行热流扩散。LIU 等[18]提出了基于欧式Ricci 流的曲面共形参数化方法，通过设计边界曲率来控制边界点的位置。随后文献[19]通过将全纯1 形式与亏格相关的奇点数相结合来获得给定表面的平坦度量，利用牛顿迭代法不断优化能量函数通过创建离散Ricci 边权重矩阵(Hessian 矩阵)来更新共形因子，达到更新圆填充度量的效果，从而获得全局平滑的参数化。基于微分1 形式的方法虽然高效，但是对于高亏格曲面的计算，往往会产生不必要的奇异点，导致整体参数化质量下降。

对于高亏格曲面，文献[20]提出一种基于调和映射的非线性参数化方法。该方法首先采用贪心算法找到高亏格曲面的同伦群基底，沿基底将曲面切开以简化其拓扑，然后通过余切边权重计算曲面的调和映射，最后使用拉普拉斯切向法最小化调和能量得到共形映射。和曲率流方法不同之处在于，该方法简单易行，并且使用的平面度量也方便用于曲面拟合，不需要高质量的三角网格使该算法鲁棒性更强，不足之处在于未涉及高精度模型的处理，即高质量三角化模型特征保留的问题。

这类固定边界参数化方法的优势在于用到的变形度量都是线性函数，缺点在于这些算法通常预先指定边界在某个凸多边形上，由于预先指定的边界与实际情况往往不相符，从而导致参数化前后变形较大[21]。

3.2 自由边界参数化

固定边界的参数化算法易于构造函数并求解，但是容易导致边界网格扭曲严重，且不易推广到复杂外形的曲面。相比之下，另一类平面参数化算法[22-31]把边界作为求解的一环，不固定边界的形状从而减小失真。这类参数化方法也称为自由边界参数化，其使得平面参数化的理论更加完备。

文献[22]提出了最小二乘共形映射(least squares conformal maps，LSCM)，采用最小二乘近似柯西-黎曼方程的方法计算了圆盘拓扑曲面的拟共形参数化。文献[23]介绍了一种基于角度平展(angle based flattening，ABF)的非线性参数化方法，把参数化过程建模为一个求解角度的模型，在得到二维平面上模型中每个三角形的3 个角度之后，再根据角度间接求解顶点的位置，缺陷在于存在边界自交问题，并且计算代价较高。随后文献[24]改进了ABF 提出的ABF++方法，其将三角网格曲面的参数化问题表述为参数网格角度误差的最小优化方程，即

进行线性近似

在提高计算效率的同时减少了角度误差，缺陷是增大了面积变形。图7 为ABF++方法和线性ABF方法变形程度比较，可以看到，这类方法直接对角度进行优化以达到保角的效果，线性ABF方法更注重角度和面积变形的均衡。

图7 2 种角度方法比较[25] ((a) ABF++方法；(b) Linear ABF方法) Fig.7 Comparison of two angle methods[25] ((a) ABF++method;(b) Linear ABF method)

文献[26]设计一种谱方法共形参数化 (spectral conformal parameterization，SCP)方法来寻找稀疏对称矩阵的特征值，通过最小化加权共形能量来计算高质量共形参数化，相比之前的线性方法[27]，该方法计算速度不占优，且不能保证生成无折叠(fold-free)的参数化结果，但优点在于共形扭曲更小；和一些非线性方法[28]相比，该方法速度一般，但参数化结果视觉效果更好，寻求计算开销与参数化质量之间的一种均衡。文献[29]设计了一种自由边界曲率扩散的算法，该方法使用CP 度量简化共形映射，从初始的共形参数化开始，优化面积扭曲函数，同时保持CP 度量共形等价，最后通过反曲率映射得到最优共形参数化，该方法控制了面积变形，但只优化了奇异顶点，仍需改进的是对整个顶点集的优化。

文献[33]对SCP，ABF++和刚性变换[31](as rigid as possible，ARAP)方法进行了介绍，同时提出一种满足双射条件的非线性自由边界参数化，即自由边界双射映射(bijective parameterization with free boundary，BPFB)方法，但该方法不属于共形参数化方法。图8 和表1 分别给出了SCP，BPFB 等 4 种方法的结果比较。可以看到，相比于其他自由边界参数化方法，ABF++方法的求解效率较高，且参数化后扭曲较小。

图8 自由边界参数化效果比较[33] Fig.8 Comparison of free boundary parameterization quality[33]

表1 自由边界参数化算法计算速度比较[24] (s)Table 1 Comparison of calculation speed of free boundary parameterization algorithms[24] (s)

3.3 无缝参数化

不论是固定边界还是自由边界，平面参数化都针对拓扑等价于圆盘的曲面。由于构造拓扑圆盘的过程中，往往需要对曲面进行切割，对于切割处的参数化容易产生误差。因此，近年来对于无缝曲面参数化的研究日益增多，无缝参数化常被用来进行无缝纹理映射[34]和形状匹配[35]。无缝参数化直观解释就是没有产生切割偏差的参数化，在切割过程中采用刚性变换进行过渡。例如MYLES 和ZORIN[36]面向无缝全局参数化，提出一种增量平展方法，将锥形奇异点即锥点(cone singularities)放置在网格表面上，从嵌入度量开始迭代表面的度量，将表面不断增长的部分限制为零高斯曲率，高斯曲率将集中在孤立的收缩区域，最终形成锥点。AIGERMAN等[37]设计了一种无缝映射的方法，如图9 所示，该方法首先对曲面进行切割，然后分别映射到平面进行比较，对不重合的区域进行一系列仿射变换，通过最小化共形扭曲能量函数得到曲面的无缝参数化。该方法能处理任意数量的标记点(landmarks)，缺陷在于非线性求解保证找到函数局部最优解，但计算代价高。

图9 无缝映射示意图[37] ((a)分别参数化到平面；(b)非重叠部分进行仿射变换并得到参数化结果)Fig.9 Diagram of seamless mapping[37] ((a) Mapping to a disk respectively; (b) Affine transformation of non-overlapping parts and result)

文献[38]将凸组合嵌入方法应用在欧式轨道流形(euclidean orbifold)上，通过求解稀疏线性系统来计算嵌入，该方法能够生成无缝的全局参数化，且满足曲面到欧式轨道流形之间的双射，不足之处在于只能放置有限锥点，因而不能进一步减小参数化导致的扭曲。

3.4 其他参数化

和上述平面参数化方法相比较，SPRINGBORN等[39]提出三角网格共形等价(conformal equivalence of triangle meshes，CETM)通过最小化凸能量函数将表面网格映射到平面域，并设计自动放置算法减少参数化的失真，从而构造离散共形等价。文献[40]提出一种线性参数化方法边界优先映射(boundary first flatting，BFF)。不同于自由边界和固定边界的方法，BFF 通过稀疏矩阵分解能够直接、完全控制边界长度和角度，即意味着边界可以手动编辑，且有成型的软件供用户使用。相比于传统的共形参数化方法LSCM[22]和SCP[26]，BFF 能够适应任意边界条件，相比于CETM 等非线性方法，BFF 计算代价更小，且参数化效果几乎相同，如图10 所示。

图10 BFF方法和CETM方法比较[40] ((a)原始模型；(b) CETM方法；(c) BFF方法) Fig.10 Comparison of BFF method and CETM method[40] ((a) Input model;(b) CETM method;(c) BFF method)

相比于无缝参数化，BFF方法能针对任意锥点放置的参数化，使参数化适应尖锐的拐角，从而将曲面共形参数化到任意形状。BFF方法的不足之处在于只能处理拓扑于圆盘的曲面。进一步，文献[41]在不超过固定总锥角的所有可能的锥度配置情况下将全局失真最小化。

通过对目前比较流行的平面参数化方法进行汇总，总结出相关的参数化方法、参数域边界条件、是否满足双射以及方法是否迭代，见表2。

表2 平面参数化方法汇总Table 2 Summary of planar parameterization methods

4 球面域

除了平面参数化，另一种常见的参数域就是单位球面，将三维曲面参数化到球面上。假设有角度θ∈[0,2π)，ϕ∈[-π/2,π/2)，则球面坐标为

如图11 所示，对于每对θ和ϕ的取值，都能对应球面上一个点坐标。

图11 球面坐标系示意图 Fig.11 Diagram of spherical coordinate

由于零亏格曲面在拓扑上等价于单位球面，因此对于零亏格曲面而言，球面域是天然且无缝的参数域。根据求解方法的不同，球面共形参数化主要分为基于能量优化的方法和基于凸组合嵌入的方法。

4.1 基于能量优化方法

该方法主要思想是构造不同的能量函数，通过对能量函数进行优化从而将源曲面参数化到单位球面。GU 等[45]指出，亏格为0 的闭合曲面的共形映射可以由球面间调和映射来实现。LAI 等[46]通过最小化调和能量来进行球面参数化，该方法对于狭长的网格能产生无折叠的参数化，效率和效果在以往参数化[13]基础上有提升，但没有推广到任意拓扑曲面。WANG 等[47]提出ARAP 的球面参数化方法，通过对球半径迭代优化解决球面参数化过程中存在的非线性约束问题，从而将平面ARAP[31]方法推广到球面域。随后在文献[48]中提出一种低失真双射映射(bijective and low distortion，BLD)方法，该方法在球面ARAP方法基础上采用一种块坐标下降的迭代算法进一步减小失真，并保证了参数化双射。图12 为4 种典型球面参数化方法的比较，其中深色部分代表三角网格失真严重或出现翻折的情况，参数化结果下方对应的4 个数值分别表示最大失真、平均失真、超出BLD方法最大失真三角面片数目以及超出BLD方法倒置的三角面片数目。

图12 4 种球面参数化方法效果对比[48] Fig.12 Comparison of the effects of four spherical parameterization methods[48]

4.2 基于凸组合嵌入方法

该方法可将平面凸组合的方法推广到球面域，即把网格嵌入球面凸多边形，在保留凸组合方法求解简单高效的同时，和球面域的天然特性进行结合，以产生高质量的参数化。AIGERMAN 等[49]将凸组合嵌入的方法扩展到了球形目标域，参数化满足双射条件并且计算速度较快。相比于欧式情形[37]，该方法等价于共形映射，参数化失真小，球面的锥点放置灵活，不足之处在于该方法必须预先指定锥点的位置及角度，并且该方法有2 个假设不能保证总是成立，只有满足这2 个假设才能得到相应参数化结果，即：假设球面最大边长不超过π/2；假设排除了迪利克雷(Dirichlet)能量的关键点，这些关键点属于非平凡的同伦类。

5 双曲空间域

除了平面域和球面域，双曲空间域也是共形参数化的研究重点。虽然不及平面域的简易性(易于构造，求解快速)和球面域的天然性(零亏格曲面拓扑等价，曲率恒正)，但是双曲空间域能够处理更多锥点的放置情况，并且对于复杂拓扑曲面，即高亏格曲面而言，双曲结构有潜力取代定义在流形样条中的仿射结构，这也使得目前对于高亏格曲面的处理，大多选择双曲平面作为参数域。

AIGERMAN 和LIPMAN[50]将凸组合嵌入方法推广到了双曲空间，满足映射无缝同胚的同时具备处理高亏格曲面的能力，和其他处理高亏格曲面不同的地方在于切割的方法。双曲空间凸组合嵌入的方法缺陷在于固定参数域的边界会影响参数化的质量，并且切割的方式比较简单，锥点手动放置生成，不能保证最优选择。图13 给出3 种典型参数空间下凸组合嵌入的效果图。

图13 不同几何背景下的凸组合嵌入效果图比较[38,48-49] ((a)欧式平面；(b)双曲平面；(c)球面) Fig.13 Comparison of convex combination embedding effects in different parameter spaces[38,48-49] ((a) Euclidean plane;(b) Hyperbolic plane;(c) Spherical plane)