2016, Vol. 27
网格参数化通常是指镶嵌在三维空间中的一个二维流形曲面与一个简单的参数域之间的一一映射[1].参数化最早是作为纹理映射的工具被引入到计算机图形学,在过去的几十年中,它逐渐成为一种无处不在的工具,广泛应用于网格模型的处理,例如纹理映射、细节转换、网格变形、网格编辑、网格重剖、网格压缩、曲面拟合、曲面变形、形状分析等等[2, 3],如图 1所示.
|
图 1 网格参数化的应用 Fig.1 Mesh parameterization applications |
最近几十年来,参数化一直是研究的热点,国内外专家、学者和技术人员在网格参数化方面做了大量的研究工作,网格曲面参数化取得了相当程度的进展,但是仍然有很多重要的问题值得进一步研究[10].
为了适应不同的应用背景和参数化特性,人们开发了不同的参数化方法,这些参数化方法采用的参数域不同,取得参数化的质量也不尽相同.本文首先对文中用到的一些术语进行简单的回顾,然后从参数域和参数化质量两个方面讨论网格参数化的研究现状.
1.1 术 语 1.1.1 一一映射由于几何模型是嵌入在三维空间中的二维流形,它本身不具备规则的参数域,这给三维模型的高效处理带来了很多困难.网格参数化就是研究三维空间中的几何模型和某个更简单、更规则的参数域之间的一个映射,使许多在复杂的二维流形上执行的操作能转换到简单的参数域上执行,从而提高操作的可行性和效率.许多应用程序要求一一映射,也即参数域内点与原始网格上的点一一对应.对于某些应用程序,局部一一映射(没有三角形翻转)就已足够;另外一些应用程序则需要全局一一映射(边界不自交).目前,只有一部分参数化方法能够保证局部或全局一一映射,其他一些方法在输入满足特定条件下才能够保证一一映射.
1.1.2 保长度参数化参数域上三角形t=[u 0,u 1,u 2]的几何形状一般区别于原始网格曲面上的三角形T=[p 0,p 1,p 2]的几何形状,如图 2所示(图中ST是网格曲面,Ω是参数域[2]),导致参数化出现角度和面积失真变形.
为了更好地理解这种变形,我们从微分几何的角度来考察曲面上的点p =f(u,v),将u =(u,v)稍微偏离(Δu,Δv)后,新点f(u+Δu,v+Δv)可以用f的一阶泰勒展式$\tilde f$来逼近.
| \[\tilde f(u + {\rm{\Delta }}u,v + {\rm{\Delta }}v) = f(u,v) + {f_u}(u,v){\rm{\Delta }}u + {f_v}(u,v){\rm{\Delta }}v.\] |
把上面的泰勒展式改写为
| \[\tilde f(u + {\rm{\Delta }}u,v + {\rm{\Delta }}v) = p + {J_f}(u)\left( {\begin{array}{*{20}{c}} {{\rm{\Delta }}u}\\ {{\rm{\Delta }}v} \end{array}} \right).\] |
这里,Jf=(fu,fv)是f的雅可比矩阵.接下来,对雅可比矩阵采用奇异值分解,得到:
| \[{J_f} = U\Sigma {V^T} = U\left( {\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} {{\sigma _1}}\\ 0 \end{array}}&{\begin{array}{*{20}{c}} 0\\ {{\sigma _2}} \end{array}}\\ 0↦0 \end{array}} \right){V^T},\] |
其中,奇异值σ1≥σ2>0,正交矩阵U ∈R3×3和V ∈R2×2的列向量分别为U1,U2,U3和V 1,V 2.线性变换$\tilde f$将u =(u,v)邻域的点映射到曲面上点p =f(u,v)处的切平面Tp,并且将以u 为中心的圆转换为以p 为中心的椭圆.把线性变换$\tilde f$分解,分解过程如图 3所示.
● 首先,变换VT将所有u 邻域的点旋转,使得V1,V2对齐u轴和v轴;
● 然后,变换σ在u轴方向拉伸σ1和v轴方向拉伸σ2;
● 最后,变换U将单位向量(1,0)和(0,1)映射到p 点处的切平面Tp上的向量U 1和U 2.
最后的结果是$\tilde f$将以u 为中心、半径为r的圆映射到以p 为中心、轴长为rσ1和rσ2的椭圆,并且将正交
标架[V1,V2]映射到正交标架[σ1U1,σ2U2].
将圆变换到椭圆的变换称为参数化的局部度量失真(local metric distortion),局部度量失真的信息隐藏在奇异值σ1和σ2中.
● σ1=σ2=1⇔f是保长度参数化:Jf是旋转加单位拉伸变换,没有扭曲角度,也没有拉伸长度;
● σ1=σ2⇔f是保角度参数化:Jf是旋转加拉伸变换,两个方向拉伸的长度相同,没有扭曲角度,故保角度;
● σ1σ2=1⇔f是保面积参数化:Jf是旋转加拉伸变换,由于两个方向拉伸的长度不同,因而扭曲角度,但是由于奇异值的积等于1,因而在参数域上圆的面积与相应切平面上椭圆的面积相等,也即保面积.
显然,保长度参数化既保角度又保面积.换句话说,保长度等价于保角度+保面积.
理想参数化是保长度的,也即零失真的参数化.很少一部分网格曲面能够得到保长度的参数化,网格曲面参数化的总体目标就是找到三维空间中的几何模型和某个参数域之间的一个映射,并且最小化不可避免的度量失真[11].为此,人们定义了许多度量扭曲的能量函数,这些能量函数可以分为如下3类.
(1) 调和映射(harmonic map)
早期参数化方法[12]采用Dirichlet能量度量局部扭曲.
| ${E_D}({\sigma _1},{\sigma _2}) = \frac{1}{2}(\sigma _1^2 + \sigma _2^2).$ |
(2) 保角映射
保角映射的本质是调和映射[2],文献[13, 14]使用以下保角能量:
| ${E_C}({\sigma _1},{\sigma _2}) = \frac{1}{2}{({\sigma _1} - {\sigma _2})^2}.$ |
保角映射也是求解一个线性问题,优点是只需要固定边界上的两个点就可以得到唯一解,缺点是参数化结果依赖这两个点的选择,并且非一一映射的问题依然存在.
显然,当σ1=σ2时,EC取得最小值.除了EC,文献[15]引入称作MIPS(most-isometric parameteri-zations)的能量函数.
| ${E_M}({\sigma _1},{\sigma _2}) = \frac{{{\sigma _1}}}{{{\sigma _2}}} + \frac{{{\sigma _2}}}{{{\sigma _1}}}.$ |
EM也在σ1=σ2时取得最小值,并且该能量函数是对称的.
| ${E_M}(\sigma _1^T,\sigma _2^T) = {E_M}(\sigma _1^t,\sigma _2^t).$ |
同时度量了参数化映射f|t和逆映射g|T的扭曲,并且该能量函数可以保证一一映射.
(3) 其他度量扭曲的能量函数
这方面工作比较多,有的基于格林-拉格朗日变形张量(Green-Lagrange deformation tensor)[16].
| ${E_G}({\sigma _1},{\sigma _2}) = {(\sigma _1^2 - 1)^2} + {(\sigma _2^2 - 1)^2}.$ |
文献[17]引入了L∞拉伸能量和L2拉伸能量.
| $\begin{array}{c} {E_\infty }({\sigma _1},{\sigma _2}) = {\sigma _1},\\ {E_2}({\sigma _1},{\sigma _2}) = \sqrt {\frac{1}{2}(\sigma _1^2 + \sigma _2^2)} , \end{array}$ |
其中,E2是局部Dirichlet能量的平方根.与调和映射不同,E2中的奇异值是参数化映射f|t的奇异值,而不是逆映射g|T的奇异值.文献[17]建议的拉伸度量现已成为保长度的标准度量,广泛应用于图形学领域.
文献[18]建议使用如下对称的L∞拉伸能量:
ES(σ1,σ2)=max(σ1,1/σ2).
文献[19]将映射和逆映射的L2拉伸能量求和:
L2(T)2=L2-stretch(M1→M2)2+L2-stretch(M2→M1)2, 从而得到对称拉伸能量.
然而,L2拉伸能量不能区分各向同性和各向异性的拉伸.为此,文献[20]定义了如下基于格林-拉格朗日变形张量的能量函数.
| ${E_{{\rm{GR}}}} = 2({(a - 1)^2} + 2{b^2} + {(c - 1)^2}) = ({(a - c)^2} + 4{b^2}) + {(a + c - 2)^2} = E_{conforml}^2 + E_{area}^2,$ |
其中,a,b,c来自\[J_f^T{J_f} = \left( {\begin{array}{*{20}{c}} {{f_u} \cdot {f_u}}&{{f_u} \cdot {f_v}}\\ {{f_v} \cdot {f_u}}&{{f_v} \cdot {f_v}} \end{array}} \right) = \left( {\begin{array}{*{20}{c}} a&b\\ b&c \end{array}} \right).\]为了保角度的需要,a=c,b=0;特别地,为了保长度的需要,a=c=1.
文献[20]将格林-拉格朗日变形张量用于度量扭曲和引导面片优化,虽然文献[16]利用格林-拉格朗日变形张量度量扭曲,但在文献[20]之前,格林-拉格朗日变形张量没有用在面片优化中.后来,文献[21]提出了类似格林-拉格朗日变形张量的、称作ARAP(as rigid as possible)的非线性能量函数:
EARAP=(σ1-1)2+(σ2-1)2.
该能量函数可以在保角和保面积中取得较好的平衡[11],并且该能量函数得到了较为广泛的应用.
为了保证局部内射,三角形不能改变方向.这就要求,当σ2靠近0时,能量函数趋近无穷.在以上的扭曲度量中, EM、对称L∞和对称L2拉伸能量满足局部内射的要求.然而,以上这些方法计算效率差别很大,EM能量函数计算速度快,因而,文献[22]建议采用如下计算高效、满足局部内射的等距能量.
| ${E_{efficient}}({\sigma _1},{\sigma _2}) = \sigma _1^2 + \sigma _2^2 + \sigma _1^{ - 2} + \sigma _2^{ - 2},$ |
其中,Eefficient类似文献[19]建议的对称L2拉伸能量[22].
1.1.3 参数域简单参数域简单是指组成参数域的面片数量少,每个面片具有规则形状(例如矩形),能够对齐特征,对于非拓扑圆盘需要分片的情形,片与片之间的转换函数简单[23].通常情况下,单一的单位正方形平面片是最简单的参数域;如果组成网格曲面M的每个平面三角形都用作参数域,那么这个参数域过于复杂,以至在这种复杂参数域上的参数化没有实际用处[23].
2 参数域早期,人们主要对平面域上的网格参数化感兴趣.平面参数化的优势在于,平面是二维形式中最简单的,也是纹理、图像等最自然的载体.平面参数化的缺点在于,仅适用于与拓扑圆盘同构的网格曲面,对于亏格大于0的网格曲面,一般需要按照一定的规则将整个网格分片.分片往往会引起参数化结果不连续,一些应用对参数化不连续非常敏感甚至完全不能忍受,于是,当被参数化的对象不是一个拓扑圆盘时,为了避免平面参数化不必要的拓扑分割,一些算法使用非平面参数域,例如基网格域和球面域.
与基网格参数化类似,交叉参数化(cross parameterization)又称作曲面间的映射,通常也需要一个公共基参数域.
文献[2, 3, 10]都对网格参数化进行了很好的综述,为了避免重复,我们将重点阐述近年来有代表性的研究工作.
2.1 平面域对于亏格大于0的网格曲面,平面参数化往往需要分片,如图 4(a)和图 4(b)所示.在此基础上,平面参数化可分为边界固定和边界自由两种.早期的平面参数化大部分为边界固定的参数化方法.例如,Floater提出的保持形状参数化[24]和均值参数化[25]等,这几种边界固定参数化方法的优势在于,用到的变形度量都是线性函数;缺点在于,这些算法通常预先把边界指定在某个凸多边形上,由于预先指定的边界与实际情况可能相差较大,因而往往导致变形较大.后来的研究多集中在边界自由的参数化方法上,例如文献[6, 13, 14, 26],这些方法把边界作为求解结果的一部分,因而变形较小.这种自由边界参数化算法给出了平面参数化的一个很好的理论框架,在实践上也得到很好的结果[10],缺点是计算速度往往较慢[2].
|
图 4 Fig.4 |
由于分片往往会引起参数化结果不连续,有些应用不允许参数化不连续,为此,人们研究了全局参数化,如图 4(c)所示.其中,图 4(a)、图 4(b)指的是对于任意拓扑结构的形状,平面参数化一般需要分割,大量的分片会造成不连续,影响某些应用;图 4(c)所示表示全局参数化算法不存在这个问题[2].
近年来,人们研究实现了无缝全局参数化.无缝全局参数化非常有用,因为它能产生无缝纹理映射[27].无缝全局参数化f具有下面的性质(如图 5所示).
● 如果P1,P2是切割边界上的点,并且切割前是同一个点P,那么P1,P2的参数位置q1,q2满足q2=rq1+t.这里,r=Rkπ/2是角度等于kπ/2的旋转变换,k是一个整数,t是平移变换,对t没有约束;
● 如果进一步对t增加约束,让t为整数,那么这样的全局参数化可用于四边形网格重剖[28, 29].
2.2 基网格域基网格参数域是指结构上比较简单的网格,如图 6所示.历史上最常用的基网格参数域是单纯复形[30, 31],单纯复形可以看作是传统网格的一部分,只包含连接信息.
|
图 6 基网格 Fig.6 Base mesh |
Eck等人[12]最早提出基网格参数化,通过种子点构造Voronoi图,Voronoi图的对偶Delaunay三角剖分构成了参数化的基网格;然后,使用调和映射计算内部顶点的参数值.该方法的缺点在于,分片算法不稳定,分片时间和调和映射时间花费都较高.Lee等人[30]提出了多分辨率的自适应曲面参数化方法(multiresolution adapative parameterization of surfaces,简称MAPS),该方法依照一定规则移除顶点,把网格简化,得到一组三角形状面片构成的基网格;然后,在每个面片上计算参数值,所有先前被删除的顶点都参数化到基网格上.文献[31]使用聚类技术来产生曲面片之间的连接,并从中导出基网格.受MAPS启发,文献[32]把输入三角网格通过Catmull-Clark细分得到四边形网格;然后,通过网格简化得到四边形基参数域.在简化过程中,文献[32]采用关键帧映射技术保存每层细节,用于引导原先被删除的顶点参数化到基网格上.Schreiner等人[19]提出基网格可以是抽象的,没有嵌入到三维空间中.后来,文献[1]基于抽象基网格将三维网格简化,得到基网格参数域;并采用全局优化减少变形,组成参数域的子区域Dj都是单位长度的等边三角形,子区域Dj通过f映射回三维网格M.文献[1]的目标是,尽可能地使每个区域f(Dj)具有相同面积和相同长度的路径.文献[1]与多种方法的比较见表 1,表 1比较了多种方法得到的L2拉伸能量(L2拉伸能量=1意味着零失真)[17].从表 1可以看出:文献[1]比文献[19, 26, 31, 33]的变形要小,比文献[20]的变形稍微大一些.
|
表 1 文献[1]与其他多种方法得到的L2拉伸能量比较[1] Table 1 Comparison of L2 stretch efficiency of the results obtained with parameterization |
文献[1]与文献[27]的比较如图 7所示(在每一行中,左边度量面积变形程度,右边度量等距变形(isometric distortion)程度.图中度量面积变形的颜色范围为log1/2(蓝色)到log2(红色);度量等距变形的颜色范围为0(蓝色)到0.5(红色)[27]).文献[1]注重最小化面积变形,但是整体上偏离了保长度;而文献[27]引起的 面积变形和等距变形都比文献[1]要小,并且文献[27]引起的面积变形集中在奇异点上.
|
图 7 上面一行:文献[1]算法得到的结果,下面一行是文献[27]算法得到的结果[27] Fig.7 Upper row: The parameterization results of Ref.[1], lower row: Parameterization results of Ref.[27][27] |
基网格参数化的优势在于适用高亏格的情形,能够保留原始网格的拓扑关系,并且在几何上与原始网格近似,通常参数化变形较小[10].基网格参数化的主要困难在于很难构造一个符合实际要求的基网格.
2.3 球面域球面域如图 8所示.
|
图 8 球面参数化 Fig.8 Spherical parameterization |
球面域上的参数化方法基本上可以分成3类[10].
1) 球面松弛的方法:例如,文献[35, 36]首先构造模型的最小包围球面,把网格的所有顶点投影到该球面上,然后固定球面上若干顶点位置,其他顶点的位置通过离散Laplace算子不断松弛得到.该方法因多次循环而代价很高.
2) 基于凸组合的方法:Gotsman等人[37]将平面参数化的凸组合方法扩展到球面参数化,该方法需要求解一个复杂的非线性方程,Gotsman等人未提出有效的求解方法,因而他们的方法局限于小网格;严寒冰等人[38]采用球面坐标计算凸组合球面参数化,提高了计算效率;Gu等人[39]基于调和能量,构造了球面保角映射,保持映射前后局部角度不变.与其他研究脑表面保形映射的方法相比,例如文献[40]保角但却能够引起长度和面积变形,而文献[39]比文献[40]更精确,不会引起大的面积变形;
3) 基于累进网格的方法:文献[8, 41]首先通过边折叠不断对面片简化,直到把面片简化成一个凸多面体,每次删除的顶点都被参数化到当前简化网格上;然后把凸多面体投影到单位球面上,得到初始球面参数化网格;最后执行顶点分裂操作,并把每次顶点分裂操作生成的新顶点放置到单位球面上.为了减轻变形,文献[8]将最小化拉伸(stretch)[17]的定义扩展到球面域,构造球面保长度参数化.
文献[8]与文献[19]方法的比较见表 2(文献[8]把球面作为中间域,将网格曲面参数化到一个八面体上;文献[19]直接将网格曲面参数化到八面体上),从表 2可以看出,文献[19]比文献[8]算法引起的变形要小.
|
|
表 2 文献[19]与文献[8]方法得到L2拉伸度量比较[19] Table 2 Comparison of L2stretch efficiency of the results obtained with spherical parametrization Ref.[8] and Ref.[19][19] |
球面参数化适合亏格为0的闭曲面,相对于平面参数化和基网格参数化,球面参数化的研究少得多,这是因为,球面参数化产生的变形扭曲较大并且球面参数化比平面参数化困难.
2.4 交叉参数化交叉参数化特别适用于曲面间变形、纹理映射和曲面混合(blending)等等,文献[42]对用于曲面间变形的交叉参数化进行了很好的综述.
与基网格参数化类似,交叉参数化通常需要一个公共的基参数域,虽然有很多构造基参数域和对基参数域优化的方法,例如文献[1, 31],但是这些方法不能直接推广到交叉参数化.许多交叉参数化方法采用规则参数域,但是通常引起的变形较大.更常用的方法是对原始网格进行化简得到基参数域,例如:Praun等人[43]在输入网格上连接用户给定的特征点,这些特征点之间的连线把输入网格分割成若干个三角形状的面片,每个三角形状面片与用户给定的模板参数域对应,面片的特征点对应模板参数域的顶点;文献[19, 44]进一步扩展了文献[43]的思想,在划分三角形状面片的同时自动生成模板参数域;还有一些方法采用四边形面片作为公共基参数域.这些方法的困难在于:(1) 规则面片很难逼近复杂的边界和狭长的区域,因而难以在鲁棒和效率之间取得平衡;(2) 单个面片的映射误差可能会在组合映射中被放大,导致最后曲面间的映射有很大的误差;(3) 面片之间很难做到连续,因而往往需要光滑和重剖等后处理[44].
有些方法使用目标网格作为公共参数域,例如:Allen等人[45]使用模板拟合技术为一组人体模型构建交叉参数化,利用用户指定的几十个标记点直接将整个样品模型映射到模板模型;Sumner和Popovic[46]提出了一种迭代最近点的算法来建立三维网格之间的映射.然而,这些方法没有考虑保持形状,当输入模型在几何上差别很大时,会产生很大的误差或变形失真.
综上可以看出,一个合适的参数域对于交叉参数化至关重要.Wu等人[47]认为,作为交叉参数化的公共基,参数域不能太“松”也不能太“紧”:公共基参数域应能很好地逼近模型以避免映射误差,也即不能太“松”;另一方面,公共基参数域应该是规则的,从而网格能够较容易地映射到参数域,也即不能太“紧”.规则的参数域,例如球面、平面、柱面和大型三角面片,通常太“松”,以至于不能很好地逼近复杂的网格模型;如果采用复杂的目标模型本身作为公共基参数域 又太“紧”了,往往在拟合过程中导致局部最优.因此,文献[47]采用非规则的凸包作为公共基参数域,如图 9所示.
与规则参数域相比,网格的复杂形状可以较容易地映射到凸包参数域,可以比较精确地逼近目标的几何形状.方法的缺点在于:对于复杂的网格模型,不同区域有可能嵌入到凸包的相同部分.与文献[44]相比,这两种方法都是保形(保角度)的参数化,得到曲面变形的视觉效果都不错,都可以用于变形和形状融合;所不同的是,文献[47]中算法比文献[44]中算法要快并且鲁棒,见表 3.
还有一些研究主要讨论具有不同拓扑结构模型之间的映射,例如:Zhang等人[20]注意到许多模型包含一些相对简单的形状,每个简单形状具有自己的参数化,据此将模型分解成一系列的面片;Bennett等人[48]引入一个初始的特征对准方案,该方案允许用户识别拓扑结构的变化;Li等人[49]提出了一个裤子(pants)分解方法,把输入模型分解成一系列裤子,每条裤子实际上是拥有3条边界并且亏格为0的面片,通过把相应的裤子映射到两个规则的六角形域,就可以得到两个模型之间的一一映射,该方法可以处理不同亏格的几何模型.
交叉参数化也不可避免地导致参数化前后不同程度的扭曲变形.为了减少变形,文献[44]采用翻转路径算子(flipping path operator)和基于松弛的平滑算子(relaxtion-based smoothing operator)减少交叉参数化变形.当定位点(anchor point)分布不均匀时,变形依然很大.翻转路径算子未能发挥作用的主要原因在于,引导算子的度量仅仅考虑了基参数域的度(也即邻接定位点的路径数量).文献[9]的保长度基参数域(length-preserved base domain)优化算法可以解决上述问题,该算法首先采用文献[44]的方法构造一个基参数域,然后对基参数域进行优化以有效地减轻交叉参数化带来的变形失真.与文献[44]相比,文献[9]得到的拉伸失真较小.文献[19]采用了类似文献[44]的方法构造基参数域,并且试图通过逐步求精优化减轻变形.文献[48]迭代优化网格顶点,以减少对称拉伸变形.文献[20]基于格林-拉格朗日张量引导面片优化和度量拉伸变形,拉伸能量L2[17]和基于格林-拉格朗日张量的能量EGR[20]进行了比较,见表 4.
|
|
表 4 拉伸能量L2[17]和基于格林-拉格朗日张量的能量EGR[20]比较[20] Table 4 Comparison between optimization metrics L2 of Ref.[17] and Green-Lagrange tensor (noted as EGR) of Ref.[20][20] |
表 4中对9个模型分别采用两种能量优化,表中上面一行基于L2优化,下面一行基于EGR优化;对每种优化方法采用两种方式度量参数化扭曲:每个模型的左边列采用L2度量扭曲,右边列采用EGR度量扭曲.通过比较可以得出:对于所有的测试模型,基于EGR优化得到的扭曲(无论是用L2还是EGR 度量)都比采用L2优化得到的扭曲要低.文献[19, 20]与其他方法的比较见表 1,文献[20]在这几种方法中引起的变形最小.
除了平面参数化,曲面间一一映射的一种常用方法也是将曲面分片,每片是一个拓扑圆盘,然后将这些拓扑圆盘通过某些优化过程映射到一个公共参数域上.与平面参数化一样,分片往往会引起映射结果不连续,为此,文献[50]开发出一种曲面之间的无缝映射技术,该技术对如何分片不敏感,如图 10所示(图 10(a)和图 10(b)中是相同的两个人体模型,不同之处在于人体模型的切割位置不同;图 10(c)是图 10(a)采用文献[50]方法得到的结果;图 10(d)是图 10(b)采用文献[50]方法得到的结果.曲面间的映射插值用户给定的用小球显示的地标.为了便于观察,将曲面间的映射可视化为将男性模型上的纹理映射到女性模型上,映射不受切割位置的影响,纹理在切割线处没有产生缝隙和扭曲).
交叉参数化的主要困难在于,很难为具有相似特征和拓扑结构的不同输入模型构造一个合适的公共基参数域.
3 参数化质量高质量的网格参数化是许多应用的基础.网格参数化质量的定义取决于应用背景,通常情况下,高质量的参数化需要满足保长度(同时保面积和保角度)、保特征、参数域简单等[23].下面就把参数化分为这3类,分别介绍其研究现状.
3.1 保长度保长度的参数化要求网格曲面是可展的,但是一般网格曲面不满足这个约束,因此人们考虑弱一些的约束,只考虑保角度或者保面积.与保长度不同,从连续曲面到平面的保角映射总是存在,一些工作考虑了保角映射的离散近似,例如文献[13, 14, 24, 25, 30, 41];还有一些工作,例如,Sheffer等人[6]提出了基于角度展开的ABF(angle- based flattening)方法,该方法可以看作是保角映射的另一种离散近似,方法的缺点是,存在边界自交问题,并且计算代价较高;后来,文献[51]改进了ABF求解方法,提出了ABF++;Zayer等人[26]对ABF方法进行线性近似,显著提高了计算效率.可是,减少角度变形通常会增大面积变形,而很多应用不希望面积变形,因此,另一类参数化的目标是保面积,例如,Zou等人[52]提出一种利用迭代优化保面积的参数化方法,该方法的缺点在于不适合狭长的三角形;文献[32]对基网格采用自适应的重采样以减少参数化面积变形,与保角映射很少的自由度相比,保面积的映射自由度很大,所以一般需要添加其他的约束条件.实际应用中多采取折衷的方法,例如文献[1, 53, 54].还有一些方法考虑了保长度或者保拉伸,例如文献[17-20].但是上面这些优化问题往往需要采用高代价的非线性方法求解.Liu等人[21]提出一种方法可以有效地最小化一种类似格林-拉格朗日变形张量[16]的非线性能量函数,并且他们提出的EARAP能量函数可以在保角和保面积中取得较好的平衡[11].该方法的局限性在于,仅适用于与拓扑圆盘同构的网格曲面,并且不能保证局部单射[22].后来,Myles等人[27]将ARAP参数化方法从拓扑圆盘曲面拓展到一般的三维网格曲面,使得ARAP可 以用于全局参 数化.在文献[27]之前,鲜有全局参数化算法直接优化等距误差.文献[55]没有声明保长度是它的优化目标,该方法采用的能量函数非常接近文献[27]建议的全局ARAP参数化,因而,文献[55]比基于保角映射和调和映射的全局参数化方法得到的等距扭曲要小[27].文献[55]引起的等距扭曲与文献[56]和文献[57]相似,因此,文献[27]与文献[55]进行了比较,比较结果如图 1 1 所示.图 11(a)和图 11(b)是保特征的文献[55]方法得到的结果,引起的变形相对较大;图 11(c)和图 11(d)是没有考虑特征保持,注重减少变形的文献[27]方法得到的结果.度量变形的能量函数为EARAP,可视化颜色设置为:蓝色表示变形为0,红色表示变形为0.5,蓝色到红色的过渡色表示变形在0~0.5之间,其中,孤立的点为锥状奇异点(cone singularities)[27].从图 11可以看出,文献[27]< ; /span>比文献[55]引起的参数化变形要小.
|
图 11 Fig.11 |
有些方法通过锥状奇异点进一步减轻参数化变形[58],通常的做法是:在网格模型上选择一些点作为锥状奇异点,将整个模型的高斯曲率集中在这些孤立的锥状奇异点上,锥状奇异点的高斯曲率不为0,其他网格点的高斯曲率为0.等距扭曲可以通过锥状奇异点得到缓解,例如文献[55-57],这3种方法使用相同的引导方向场,文献[56]比文献[57]和文献[55]增加了奇异点,减轻了等距扭曲[59];保角参数化也可以通过对锥状奇异点的合适处理得到改善[11],例如文献[58, 60, 61, 62]都在网格上选择一些点作为锥状奇异点.如果允许增加锥状奇异点,那么参数化问题将变得更为复杂,因为需要确定锥状奇异点的位置和锥状奇异点处的高斯曲率.文献[63, 64]把曲率集中到用户指定的锥状奇异点.文献[60, 62]遵循“自上而下”的方式自动放置锥状奇异点,这个技术可以回溯到文献[65],具体的做法是:从一个没有锥状奇异点的高失真的平面开始,通过一种贪心算法添加锥状奇异点,逐渐把锥状奇异点添加到最大失真区域,直到所需数目的锥状奇异点被添加,或者失真能量低于给定的阈值.这种方法对放置少量的锥状奇异点非常有效,但是随着奇异点数目的增多,该方法就变得不可靠了[27].与此相反,文献[27]把所有的原始网格顶点视为锥状奇异点,从原始网格曲面(而不是平面)开始,逐渐让一些锥状奇异点变成0曲率的顶点,将曲率集中在孤立的锥状奇异点上,这样,从低失真的原始网格曲面而不是高失真的平面开始采用贪心策略优化,最后会得到具有较低变形的参数化.文献[27]没有考虑特征对齐,文献[28]在特征对齐的约束下,将曲率集中到奇异点上从而减轻变形,并且文献[28]在算法中增加了一个可调因子,可以通过调整该因子增加奇异点以减轻参数化变形.
最近,文献[22, 66]在考虑参数化健壮的同时致力于减轻变形,其中,文献[66]对MIPS方法加以改进,在MIPS保角能量${E_M}({J_f}) = \frac{{{\sigma _1}}}{{{\sigma _2}}} + \frac{{{\sigma _2}}}{{{\sigma _1}}}$的基础上定义了等距能量(isometric energy).
Eiso(Jf)=αEM(Jf)+(1-α)Edet(Jf),
其中,${E_{\det }}({J_f}) = \frac{1}{2}(\det ({J_f}) + \det {({J_f})^{ - 1}}).$在实验中[66],把α设置为0.5.并且,文献[66]定义了保角和等距的AMIPS (advanced MIPS)能量函数如下:
| $\begin{array}{c} E_{{\rm{MIPS}}}^* = \sum {\exp (s \cdot {E_M})} ,\\ E_{iso}^* = \sum {\exp (s \cdot {E_{iso}}) = \sum {\exp (s \cdot {E_M} + s \cdot {E_{\det }})} } . \end{array}$ |
这里,
● ∑是指对网格上的所有元素求和;
● s是一个参数用于控制惩罚程度:若s很小,则几乎不能惩罚最大扭曲;若s太大,则又会引起数值不稳定.
通过最优化AMIPS能量函数,可以有效抑制最大变形,从而能够紧密控制变形分布,并且AMIPS继承了MIPS方法局部单射的优点.AMIPS与BDM(bounded distortion mapping,简称BDM)[67]和LIM(locally injective mapping,简称LIM)[68]保长度比较如图 12(图中颜色是对Δiso的编码,在参数域中,蓝色表示LIM和BDM方法产生的等距扭曲比AMIPS方法产生的最大扭曲要大)和表 5所示;AMIPS与MIPS[15],ABF++[51],BDM[67]和LIM[68]保角度比较如图 13(蓝色边表明,保角扭曲比AMIPS方法产生的保角扭曲的最大值还要大)和表 6所示.保长度和保角度参数化初始都是将单片网格通过凸组合映射到单位圆形参数域,不同之处在于后续优化的目标函数有所不同.在图 12和表 5中:AMIPS最小化$\delta _{dev}^{iso}$;而在BDM和LIM方法中,采用EARAP作为优化目标函数.由于文献[66]对BDM方法最优上界没有先验知识,因此测试了两个上界,分别是5和9.
|
图 12 对兔子头部模型和Bimba模型分别采用AMIPS,LIM和BDM方法得到的保长度参数化比较[66] Fig.12 Isometric parameterizations of a Bunny head and Bimba using AMIPS, LIM and BDM[66] |
|
图 13 MIPS,ABF++,BDM,LIM和AMIPS方法保角参数化比较[66] Fig.13 Comparison among conformal parameterizations of models using MIPS, ABF++, BDM, LIM and AMIPS[66] |
|
|
表 5 AMIPS,LIM和BDM方法得到的保长度参数化比较[66] Table 5 Isometric parameterizations of models using AMIPS, LIM and BDM[66] |
在表 5和图 12中,${\delta ^{iso}} = \max \{ {\sigma _{\max }},\sigma _{\min }^{ - 1}\} $是文献[18]建议的对称L∞拉伸能量ES(详见第1.1节),如果所有奇异值等于1,Δiso达到最小值1.等距扭曲用Δiso度量,Δiso比EARAP能量好,因为EARAP不能很好地度量收缩变形,特别是当σmin接近于0时;角度扭曲用${\delta ^{con}} = {\sigma _{\max }} \cdot \sigma _{\min }^{ - 1}$度量,如果所有奇异值都相等,则Δcon达到最小值1.表中扭曲度量包括网格上所有元素的最大偏差(最坏情况)、平均偏差和标准差,分别记作$\delta _{\max }^{iso},\delta _{avg}^{iso},\delta _{dev}^{iso},\delta _{\max }^{con},\delta _{avg}^{con},\delta _{dev}^{con}$.从图 12和表 5可以看出,AMIPS得到的结果好于或者不低于BDM和LIM方法:图 12的纹理模型表明,AMIPS较好地保持了等距;表 5表明,AMIPS计算速度最快并且得到的$\delta _{dev}^{iso}$值最小.与保长度参数化类似,保角度参数化也是从高失真的凸映射开始,如果直接优化$E_{{\rm{MIPS}}}^{\rm{*}}$需要较多的迭代,因此,文献[66]在前1 000次迭代中采用保长度参数化,然后改为优化$E_{{\rm{MIPS}}}^*$能量函数.BDM和LIM优化[14]建议的保角能量EC(详见第1.1节).表 6中的3组数值分别是最大角度扭曲、均值角度扭曲以及运行时间.从图 13所示结果可以看出:标准MIPS陷入局部最小引起较大扭曲; ABF++用时最少可是产生的最大偏差高,甚至产生反转三角形;如果算法收敛,BDM可以限定扭曲上界,但是这个上界不易选择.例如,男人模型的上界是42,骆驼模型的上界是27,并且BDM最费时间;LIM产生的均值扭曲小,可是最大值扭曲高,并且LIM的效率受到网格尺寸的影响;AMIPS方法具有最低的最大值扭曲和平均扭曲,并且计算速度仅次于ABF++.
|
|
表 6 MIPS,ABF++,BDM,LIM,AMIPS方法得到的保角参数化方法比较[66] Table 6 Comparison among conformal parameterizations using MIPS, ABF++, BDM, LIM and AMIPS[66] |
文献[22]自动构造变形小、一一映射的参数化,为了保证局部单射、减轻变形和提高计算效率,采用防止三角形局部反转、计算高效、度量等距扭曲的能量函数Eefficient(详见第1.1节)和防止边界自交的函数EB.与以往致力于一一映射的方法不同,文献[22]不限制边界的形状,允许优化边界以减轻扭曲.实验结果表明,为了得到一一映射而添加边界约束,使得参数化变形增大,如表 7和图 14所示.表 7显示了对不同模型采用Eefficient度量得到的单个三角形的平均误差和最大误差(误差最小值为4.327,注意到:当σ1=σ2时,Eefficient取得最小值为4),添加边界约束使得平均误差值略增,这在图中大面积的折叠区域表现得尤为突出.文献[22]的缺陷在于:使用了一个非凸的能量函数,对于给定的扭曲能量不能保证找到全局最小.
|
图 14 Triceratops模型:左边采用Eefficient优化,右边采用Eefficient和EB优化[22] Fig.14 Triceratops optimized with Eefficient on the left and Eefficient and EB on the right[22] |
|
|
表 7 带边界约束优化和不带边界约束优化得到的等距度量Eefficient的比较[22] Table 7 The average error and maximum error using isometric metric Eefficient with and without EB[22] |
Dong等人[33]基于Morse-Smale理论提出了一种生成四边网格的算法,通过沿梯度场连接Laplace谱函数的极值点构造四边网格.后来,Huang等人[69]扩展了文献[33]的方法,他们的方法可以控制奇异点和保持特征.Ray等人[56]提出了周期全局参数化的方法,参数化受两个正交矢量场的约束.除了一小部分奇异点外,这种方法在其他区域的参数化结果是连续的,该方法适用于任意亏格的表面,方法的缺点是需要非线性优化.文献[57]受文献[56]的启发,将给定方向场在2-流形的分支覆盖上转换成单一方向场,简化了算法实现,并且减少了奇异点. Bommes等人[55]基于特征曲线约束构造了一个对称方向场(cross field),然后,基于对称方向场的引导计算一个全局参数化.他们把对称方向场的构造和全局参数化的计算转换成混合整数问题,构造出尽可能与网格特征相符合的参数化.与文献[27]相比,如图 11所示,文献[55]尽可能地保持特征,而文献[27]的主要目标是减少变形,未考虑保持特征.后来,Myles等人[28]将区域平滑的方法和保形映射集成在一个由 文献[70]建议的框架中,不仅可以最小化参数化变形,还能对齐特征.最近,Myles等人[29]提出一种鲁棒的能够对齐对称方向场的参数化算法,算法首先基于对称方向场构造一个初始的四边形网格划分,接下来修改四边形网格的结构以保证存在一个全局参数化,然后把每个四边形映射到矩形区域上(矩形的边长由四边形的边长决定)得到一个初始参数化,最后的参数化通过求解一个凸约束优化问题而得到.文献[29]比文献[55, 67, 71]的算法更鲁棒,如图 15所示(图中MIQ,BD,IGM和RGP分别是采用文献[29, 55, 67, 71]得到的结果,对股骨模型,采用BD方法得到的反转三角形隐藏在洞中看不见).
|
图 15 一些非一一映射参数化的例子(反转的三角形用红色显示)[29] Fig.15 Examples of non-bijective parametrizations (inverted triangles shown in red)[29] |
Liao等人[72]提出了利用拉普拉斯Beltrami算子(Laplace-Beltrami operator,简称LBO)的特征函数构造对齐结构特征的参数化方法,算法首先利用LBO的多个特征函数来捕捉不同尺度的结构特征,然后构造一个受结构特征约束的光滑对称方向场,最后在光滑对称方向场的引导下得到参数化.与主曲率引导的参数化相比,主曲率和特征函数都可以用于捕捉物体的结构特征,但是主曲率方法无法忽略一些细节从而导致多余奇点的出现,而来自特征函数的参数线能够对齐物体的轴方向,忽略了一些细微的凹凸不平或者不规则形状.
前面许多工作基于对称方向场,对称方向场是正交、单位长度的标架场,对称方向场不支持各向异性.后来, Kovacs等人[73]对文献[55]进行了改进,可以创建曲率对齐、各向异性的四边形网格.Liu等人[74]将文献[55]拓展到非正交的共轭方向场,旨在设计由平面四边形元素组成的建筑结构.Panozzo等人[75]引入标架场,标架场也是对称方向场的拓展,与对称方向场不同,它允许非正交、非单位长度;标架场能够产生各向异性和非均匀的四边形网格,使得用户不仅能够控制特征对齐,还能控制各向异性元素分布的稠密程度,如图 16所示(颜色描述了网格元素的面积.红色小,蓝色大,红色到蓝色的过渡色表示面积大小在红色和蓝色之间[75]).
|
图 16 文献[55]方法得到的均匀四边形网格与文献[75]方法得到的各向异性的四边形网格相比较[75] Fig.16 Comparison between uniform quadrangulation of Ref.[55] and anisotropic quadrangulation of Ref.[75][75] |
这两种方法使用了相同数量的四边形,采用了同样的约束,使用文献[75]中的方法得到的Haursdorff误差比文献[55]中的方法得到的Haursdorff误差低20%.然而,设计通用的标架场仍然是一个具有挑战性的任务:需要在用户输入或实用性需求(如对齐给定方向和满足尺寸约束)与标架场的平滑性及不可避免的奇异点之间取得平衡.输入约束依赖具体的应用可能约束不足或者约束过度,平滑性和方向约束可能与尺寸约束冲突,这使得用户引导的设计过程冗长而乏味,自动生成的标架场可能会导致不准确,需要交互添加或删除约束,直到生成可以接受的标架场[76].为此,文献[76]提出了一种新的生成标架场的方法,因为通用的标架场(具有任意各向异性、方向和大小)可以被视为特定黎曼度量的对称方向场,该文作者首先在输入表面上计算一个兼容稀疏或稠密输入约束的离散黎曼度量,然后,通过在黎曼度量中寻找一个最优的对称方向场得到标架场.文献[76]放弃曲面是嵌入在欧几里德空间的观点,转而考虑更一般情况下的黎曼流形,显著增加了设计标架场的灵活性,可以更好地控制各向异性并精确地对齐特征曲线.如果输入模型具有显著特征,文献[76]与文献[75]的比较可如图 17所示(文献[76](右边)允许控制自动特征对齐和人工调整局部各向异性(中间,标记在输入场上的两对方向约束),而文献[75](左)由于缺乏控制不能得到想要的纵横比),文献[75]甚至在这种基本的模型上都不能控制各向异性.
目前,多数方法假设输入的网格都是“好”网格,这里的好网格是指无噪声、分段光滑、不存在太多过于丰富的细节.这些细微的几何和拓扑类型的特征或者噪声会导致出现严重问题:在好的情况下,这些带有细节的输入导致四边形剖分产生扭曲;在坏的情况下,算法会失败,如图 18所示(图中左边是好网格,右边的输入网格带有噪声).这在实践中是一个很大的问题,因为通过激光扫描得到的输入网格往往都带有噪声.为此,Ebke等人[77]重新构造了对称方向场和基于对称方向场引导的参数化,在构造过程中有效地抑制了细微的几何和拓扑类型的噪声或者特征,充分保留了占主导地位的特征.
最近,文献[78]提出了一种交互设计四边形剖分的方法,该方法基于一个以数据库形式存放的大型模式数据集,该模式数据集是从艺术家人工设计的模型中学习得到的.运行时,用户通过草绘(draw stroke)定义粗面片(patch)(如图 19中所示黄线)和希望的边流(edge flow)(如图 19中所示红线).系统查询模式数据库抽取出与用户草绘匹配的模式嵌入草绘的粗面片内部,算法主过程如图 19所示(给定一些手工制作的四边形输入模型,文献[78]从这些模型中学习手工剖分四边形的模式,这些模式存放到一个数据库中,用于剖分用户基于草图设计的粗面片布局.用户通过草绘定义粗面片(黄线)、边流(红色),系统自动地从数据库中选择符合用户定义的剖分四边形的模式).
文献[78]与自动生成四边形剖分的方法相比,大多数自动生成四边形剖分的算法依赖于一个指导方向场,例如对称方向场,这些方向场是通过静态几何分析从原始网格提取的,静态几何分析方法只能获取几何特性,导致得到的四边形网格很规整,但却缺少语义特性,比如人脸的脸颊(如图 20所示);相反地,文献[78]允许艺术家手工对齐四边形的语义特征,可以生成适合应用在动画和娱乐行业的理想四边形网格,如图 20所示.
|
图 20 文献[55](左)、文献[78](右)与得到的四边形网格比较[78] Fig.20 A comparison between quadrangulations proposed by Ref.[55] on the left and Ref.[78] on the right[78] |
Gu等人[65]将整个三角网格映射到一个正方形参数域,这种映射只适合亏格为0的曲面,并且映射引起的变形较大.Sander等人[79]采用多片几何图像显著降低了参数化变形,他们利用聚类技术,通过迭代进行种子点选取和面片增长,将参数域分成一系列不规则的面片.但是,由于边界不规则,需要采用复杂的方法处理边界之间的不连续.Tarini等人[53]利用多立方体(polycube)作为参数域,把曲面映射到嵌入在三维空间的多立方体上,多立方体映射提供了一个非常紧凑且简单的表示.文献[80]通过允许T形连接将网格曲面分成一系列四边形面片,类似的 想法被文献[81]用来提高参数域的简单性,这种方法表现出很大程度的自适应性,面片尺寸可以明显改变以符合表面细节.然而,T形连接的存在使得参数域的结构变得复杂,导致该算法在多种情况下不能用.一些方法采用手工构造简单参数域,例如文献[82];另外一些采用半自动方法,例如文献[83];还有一些采用自动方法,例如文献[23]适用于对称方向场,直接作用于奇异点连线图本身.文献[84]将流形M划分为一组四边形面片,这些四边形面片可以用作参数域.与文献[23, 85]不同,文献[84]不是直接在原始网格上构建奇异点之间的连线图,而是基于奇异点连线图的对偶图,对偶图由一些封闭曲线交叉构成,文献[84]称这些封闭曲线为对偶环,如图 21所示(从左到右:四边形布局、对偶环和对偶带).对偶环可以直接表示全局连接约束,容易满足结构一致性要求.与文献[23, 85]相比,文献[84]的化简效果较好,如图 22所示(从左到右分别是非简单参数域以及文献[23, 84, 85]得到的结果,图 中数字是组成参数域的四边面片数).文献[84]的缺点在于:自动放置的奇异点往往没有体现全局结构特征;对偶环有时不能满足几何保真要求,如图 23所示(图中左边是基于对偶环(黄色)得到的原始奇异点图(黑色),右边是加入一条绿色的新环后得到的奇异点图(黑色).显然,右边面片比左边面片更接近矩形).
文献[23, 85]给出的上述方法不是基于原始三角网格构造简单参数域,而是基于四边网格,通过迭代调整四边网格结构简化参数域,其中,文献[85]在对齐特征的前提下简化了四边形网格结构,文献[71]直接在流形上构造粗面片布局(coarse patch layouts),为了保证一一映射引入凸约束.
与文献[84]的贪婪策略相比,文献[71]采用全局branch-and-cut优化策略得到的四边形布局在大多数情况下拥有较少面片,见表 8,并且依然可以对齐给定的对称方向场;对偶环算法受奇异点位置的影响不大,因为通常情况下,对偶环算法搜索的曲线远离奇异点,而奇异点的位置对文献[71]算法的影响较大,实验结果表明,采用文献[71]的算法,一些奇异点移动到更有意义的几何位置.
上述许多方法主要讨论了简单参数域的结构或者拓扑方面的问题,而文献[87]主要讨论简单参数域的几何保真性问题,如图 24所示.文献[87]对一个粗四边形布局进行优化,该方法重视表面的各向异性和特征,得到变形小且对齐主曲率方向的参数化.该方法的关键贡献是一种新型、高效的技术,该技术直接受最小化偏差失真的目标驱动,不断优化节点位置.与文献[23]比较,文献[87]具有较好的几何保真性,如图 25和表 9所示.
|
图 24 上面是算法[87]的输入,下面是文献[87]方法的输出[87] Fig.24 Given a rough layout graph (top), the output of the method of Ref.[87] (bottom)[87] |
|
图 25 文献[23](红色)与文献[87](绿色)的比较[87] Fig.25 Comparison of the method proposed by Ref.[23] (red) and Ref.[87] (green)[87] |
|
|
表 9 文献[87]与文献[23]方法得到的Econfor保角能量比较[87] Table 9 Comparison of conformal energy Econfor obtained by Ref.[23] and Ref.[87][87] |
表 9中,${E_{confor}} = \frac{1}{A}\int_M {{E_M}} ,$其中,${E_M} = \frac{{{\sigma _1}}}{{{\sigma _2}}} + \frac{{{\sigma _2}}}{{{\sigma _1}}}$[15](详见第1.1节),A是网格曲面M的面积.
尽管实验结果表明(如图 22所示)自动算法减少了四边形布局的面片数量,取得了很好的化简效果,但是自动方法仍存在一定的局限性,往往不能处理复杂的结构[59],而人工方法繁琐复杂,为此,文献[86]采用交互方式设计四边形布局.
Campen等人引入对偶带(dual strip)的概念,如图 21所示,对偶带是具有宽度的对偶环,虽然对偶环足以定义四边形布局的拓扑结构,但是对偶环缺乏几何尺寸,不适合交互.现有交互工具通常提供局部算子,用于创建单个顶点、单条边和单个四边形,这些局部算子难以体现全局结构,而四边形面片布局需要体现全局结构特征.文献[86]从全局来考虑,采用对偶带编织(dual strip weaving)短时间内可以勾画出大量的四边形面片,降低了交互设计对用户专业性的要求,缺点是没有局部调整的能力.
4 其他参数化一些文献将现有的网格参数化方法进行扩展,例如:He等人[11]将文献[21]中的ARAP方法应用到细分曲面参数化;文献[88]将文献[55]的方法扩展到深度图像集,深度图像集可以通过直接测量现实世界中的物体得到,也可以通过绘制虚拟物体得到,每个深度图像通过映射函数映射到一个参数域,四边形网格可以通过在参数域上采样得到,参数化结果可以用于四边网格重剖以及纹理映射等等,这种方法对噪声不敏感,但当存在大量噪声时参数化会出现不连续;文献[89]将文献[57]加以扩展,提出了一种新的六边形全局参数化方法,如图 26所示(左边:参数化;右边:纹理),该算法可用于三角形和六边形网格重剖以及纹理映射等.
5 结束语
本文主要从参数域和参数化质量两个方面来介绍网格参数化的研究现状,概括介绍了每项技术的主要思想,讨论每项技术的主要特性,并对其中一些方法与其他方法进行了比较分析.虽然网格参数化已经取得了丰富的理论成果和应用技术,但是仍然存在如下一些难点问题.
● 目前,只有极少的方法不经过用户的介入就能得到一一映射的网格参数化[22],对于一般的网格,如何得到一一映射和低失真的网格参数化,在很大程度上仍然是一个难题[90];
● 高质量的网格参数化需要满足参数域简单,一些致力于简单参数域的方法往往采用从现有三角网格产生粗面片布局,但从三角网格自动产生理想的粗面片布局依然是一个具有挑战性的难题[78];
● 多立方体参数化(polycube parameterization)采用多立方体作为参数域,是一类特殊的全局参数化方法.该类方法使纹理映射变得简单,还可以生成高质量的四边形网格.虽然近年来涌现了许多关于多立方体参数化的研究,但自动或半自动构造健壮的多立方体参数化,仍然是一个开放性的难题[59].
网格参数化还有一些重要问题需要进一步深入研究,未来可能的研究方向可有如下几个.
● 参数化质量.
通常情况下,高质量的参数化需要满足保长度、保特征、参数域简单等条件.为了进一步提高参数化质量,由于一般模型不是可展曲面,不可能得到保长度的参数化,因此针对一般模型,需要研究快速获得最接近于零失真或者保长度的参数化方法.参数化应用越来越广泛,需要进一步考虑针对特定应用描述复杂的约束和获得带复杂约束的参数化方法.为了获得简单参数域,需要提升用作参数域的网格质量.特别地,奇异点的位置和数量可以减轻参数化变形和提升用作参数域的网格质量,因此需要研究奇异点的放置问题.许多致力于简单参数域的方法从现有三角网格自动产生粗面片布局,但是,自动方法具有一定的局限性,往往不能处理复杂的结构.在工厂里,粗面片布局往往是由专业设计人员手工创建的,在创建过程中,专业设计人员依据特殊的应用背景,充分运用他们的语义知识和经验.工厂里应用的造型系统允许用户手工绘制点和边,但是手工操作过程过于耗时,并且容易出错,因此需要研究高效的交互创建粗面片布局的方法.
● 健壮性.
一方面,目前只有一部分参数化方法能够保证局部或全局一一映射,其他一些方法在输入满足特定条件下可以保证一一映射;另一方面,目前参数化方法往往假设输入网格没有噪声、分段平滑、没有太多太细的特征,但实际上,输入网格往往不完备、含有噪声,这样的输入网格尤其需要健壮的参数化方法.
● 数学基础.
参数化的许多目标依赖于从理论上深入理解参数化技术,这就需要将参数化与科学计算的其他一些领域,例如逼近理论、应用数学和有限元建模等相关联.这些领域的一些技术从20世纪40年代以来得到了持续的开发,目前已经发展成熟.将这些领域的先进技术引入到几何处理领域中来,有可能导致重大发展[59].
| [1] | Pietroni N, Tarini M, Cignoni P. Almost isometric mesh parameterization through abstract domains. IEEE Trans. on Visualization and Computer Graphics, 2010,16(4):621-635 . |
| [2] | Hormann K, Lévy B, Sheffer A. Mesh parameterization: Theory and practice. In: Proc. of the SIGGRAPH Asia 2008 ACM SIGGRAPH ASIA 2008 Courses. New York: ACM Press, 2008. 12:1-12:87 . |
| [3] | Sheffer A, Praun E, Rose K. Mesh parameterization methods and their applications. Foundations and Trends in Computer Graphics and Vision, 2006,2(2):105-171 . |
| [4] | Lévy B. Constrained texture mapping for polygonal meshes. In: Proc. of the ACM SIGGRAPH 2001. Los Angeles: ACM Press, 2001. 417-424 . |
| [5] | Biermann H, Martin I, Bernardini F, Zorin D. Cut-and-Paste editing of multiresolution surfaces. ACM Trans. on Graphics, 2002, 21(3):312-321 . |
| [6] | Sheffer A, Sturler E. Parameterization of faceted surfaces for meshing using angle-based flattening. Engineering with Computers, 2001,17(3):326-337 . |
| [7] | Lévy B. Dual domain extrapolation. ACM Trans. on Graphics, 2003,22(3):364-369 . |
| [8] | Praun E, Hoppe H. Spherical parametrization and remeshing. ACM Trans. on Graphics, 2003,22(3):340-349 . |
| [9] | Kwok T, Zhang Y, Wang C. Efficient optimization of common base domains for cross parameterization. IEEE Trans. on Visualization and Computer Graphics, 2012,18(10):1678-1692 . |
| [10] | Hu SM, Yang YL, Lai YK. Research progress of digital geometry processing. Chinese Journal of Computers, 2009,32(8):1-8 (in Chinese with English abstract). |
| [11] | He L, Schaefer S, Hormann K. Parameterizing subdivision surfaces. ACM Trans. on Graphics, 2010,29(4):120:1-120:6 . |
| [12] | Eck M, Derose T, Duchamp T. Multiresolution analysis of arbitrary meshes. In: Proc. of the ACM SIGGRAPH. ACM Press, 1995. 173-182 . |
| [13] | Desbrun M, Meyer M, Alliez P. Intrinsic parameterizations of surface meshes. Computer Graphics Forum, 2002,21(2):209-218 . |
| [14] | Lévy B, Petitjean S, Ray N, Maillot J. Least squares conformal maps for automatic texture atlas generation. ACM Trans. on Graphics, 2002,21(3):362-371 . |
| [15] | Hormann K, Greiner G. MIPS: An efficient global parametrization method. In: Laurent PJ, Sablonniere P, Schumaker LL, eds. Proc. of the Curve and Surface Design. Nashville: Vanderbil University Press, 2000. 153-162. |
| [16] | Maillot J, Yahia H, Verroust A. Interactive texture mapping. In: Proc. of the ACM SIGGRAPH’93. ACM Press, 1993. 27-34 . |
| [17] | Sander P, Snyder J, Gortler S, Hoppe H. Texture mapping progressive meshes. In: Proc. of the ACM SIGGRAPH. Los Angeles: ACM Press, 2001. 409-416 . |
| [18] | Sorkine O, Cohen-Or D, Goldenthal R, Lischinski D. Bounded-Distortion piecewise mesh parametric zation. In: Proc. of the IEEE Visualization. Boston: IEEE Computer Society, 2002. 355-362 . |
| [19] | Schreiner J, Asirvatham A, Praun E, Hoppe H. Inter-Surface mapping. ACM Trans. on Graphics, 2004,23(3):870-877 . |
| [20] | Zhang E, Mischaikow K, Turk G. Feature-Based surface parameterization and texture mapping. ACM Trans. on Graphics, 2005, 24(1):1-27 . |
| [21] | Liu L, Zhang L, Xu Y, Gotsman C, Gortler S. A local/global approach to mesh parameterization. Computer Graphics Forum, 2008, 27(5):1495-1504 . |
| [22] | Smith J, Schaefer S. Bijective parameterization with free boundaries. ACM Trans. on Graphics, 2015,34(4):70:1-70:9 . |
| [23] | Tarini M, Puppo E, Panozzo D, Pietroni N, Cignoni P. Simple quad domains for field aligned mesh parametrization. ACM Trans. on Graphics, 2011,30(6):142:1-142:11 . |
| [24] | Floater M. Parameterization and smooth approximation of surface triangulations. Computer Aided Geometric Design, 1997,14(3): 231-250 . |
| [25] | Floater M. Mean value coordinates. Computer Aided Geometric Design, 2003,20(1):19-27 . |
| [26] | Zayer R, Lévy B, Seidel HP. Linear angle based parameterization. In: Proc. of the 5th Eurographics Symp. on Geometry Processing. Barcelone: Eurographics Association, 2007. 135-141. |
| [27] | Myles A, Zorin D. Global parametrization by incremental flattening. ACM Trans. on Graphics, 2012,31(4):109:1-109:11 . |
| [28] | Myles A, Zorin D. Controlled distortion constrained global parametrization. ACM Trans. on Graphics, 2013,32(4):105:1-105:14 . |
| [29] | Myles A, Pietroni N, Zorin D. Robust field-aligned global parametrization. ACM Trans. on Graphics, 2014,33(4):135:1-135:14 . |
| [30] | Lee A, Sweldens W, Schroder P, Cowsar L, Dobkin D. MAPS: Multiresolution adapative parameterization of surfaces. In: Proc. of the ACM SIGGRAPH. ACM Press, 1998. 95-104 . |
| [31] | Khodakovsky A, Litke N, Schroder P. Globally smooth parameterizations with low distortion. ACM Trans. on Graphics, 2003, 22(3):350-357 . |
| [32] | Daniels J, Silva C, Cohen E. Semiregular quadrilateral-only remeshing from simplified base domains. Computer Graphics Forum, 2009,28(5):1427-1435 . |
| [33] | Dong S, Bremer PT, Garland M, Pascucci V, Hart JC. Spectral surface quadrangulation. ACM Trans. on Graphics, 2006,25(3): 1057-1066 . |
| [34] | Zayer R, Rössl C, Seidel HP. Curvilinear spherical parameterization. In: Proc. of the 2006 Int’l Conf. on Shape Modeling and Applications (SMI 2006). IEEE Computer Society, 2006. 57-64 . |
| [35] | Kobbelt L, Vorsatz J, Labisk U. A shrink wrapping approach to remeshing polygonal surfaces. Computer Graphics Forum, 1999, 18(3):119-129 . |
| [36] | Alexa M. Merging polyhedral shapes with scattered features. The Visual Computer, 2000,16(1):26-37 . |
| [37] | Gotsman C, Gu X, Sheffer A. Fundamentals of spherical parameterization for 3D meshes. ACM Trans. on Graphics, 2003,22(3): 358-363 . |
| [38] | Yan HB, Hu SM. Convex combination spherical parameterization using spherical coordinates. Chinese Journal of Computers, 2005, 28(6):927-932 (in Chinese with English abstract). |
| [39] | Gu X, Wang Y, Chan TF, Thompson PM, Yau ST. Genus zero surface conformal mapping and its application to brain surface mapping. IEEE Trans. on Medical Imaging, 2004,23(7):949-958 . |
| [40] | Haker S, Angenent S, Tannenbaum A, Kikinis R, Sapiro G, Halle M. Conformal surface parameterization for texture mapping. IEEE Trans. on Visualization and Computer Graphics, 2000,6(2):181-189 . |
| [41] | Zhou K, Bao HJ, Shi JY. A unified framework for digital geometry processing. Chinese Journal of Computers, 2002,25(9):904-909 (in Chinese with English abstract). |
| [42] | Alexa M. Recent advances in mesh morphing. Computer Graphics Forum, 2002,21(2):173-197 . |
| [43] | Praun E, Sweldens W, Schroder P. Consistent mesh parameterizations. In: Proc. of the ACM SIGGRAPH 2001. Los Angeles: ACM Press, 2001. 179-184 . |
| [44] | Kraevoy V, Sheffer A. Cross-Parameterization and compatible remeshing of 3D models. ACM Trans. on Graphics, 2004,23(3): 861-869 . |
| [45] | Allen B, Curless B, Popovic Z. The space of human body shapes: Reconstruction and parameterization from range scans. ACM Trans. on Graphics, 2003,22(3):587-594 . |
| [46] | Sumner RW, Popovic J. Deformation transfer for triangle meshes. ACM Trans. on Graphics, 2004,23(3):399-405 . |
| [47] | Wu H, Pan C, Zha H, Yang Q, Ma S. Partwise cross-parameterization via nonregular convex hull domains. IEEE Trans. on Visualization and Computer Graphics, 2011,17(10):1531-1544 . |
| [48] | Bennett J, Pascucci V, Joy K. A genus oblivious approach to cross parameterization. Computer Aided Geometric Design, 2008, 25(8):592-606 . |
| [49] | Li X, Gu X, Qin H. Surface mapping using consistent pants decomposition. IEEE Trans. on Visualization and Computer Graphics, 2009,15(4):558-571 . |
| [50] | Aigerman N, Poranne R, Lipman Y. Seamless surface mappings. ACM Trans. on Graphics, 2015,34(4):72:1-72:13 . |
| [51] | Sheffer A, Lévy B, Mogilnitsky M, Bogomyakov A. ABF++: Fast and robust angle based flattening. ACM Trans. on Graphics, 2005,24(2):311-330 . |
| [52] | Zou G, Hu J, Gu X, Hua J. Authalic parameterization of general surfaces using lie advection. IEEE Trans. on Visualization and Computer Graphics, 2011,17(12):2005-2014 . |
| [53] | Tarini M, Hormann K, Cignoni P, Montani C. Polycube maps. ACM Trans. on Graphics, 2004,23(3):853-860 . |
| [54] | Dominitz A, Tannenbaum A. Texture mapping via optimal mass transport. IEEE Trans. on Visualization and Computer Graphics, 2010,16(3):419-433 . |
| [55] | Bommes D, Zimmer H, Kobbelt L. Mixed-Integer quadrangulation. ACM Trans. on Graphics, 2009,28(3):77:1-77:10 . |
| [56] | Ray N, Li W, Lévy B, Sheffer A, Alliez P. Periodic global parameterization. ACM Trans. on Graphics, 2006,25(4):1460-1485 . |
| [57] | Kalberer F, Nieser M, Polthier K. QuadCover-Surface parameterization using branched coverings. Computer Graphics Forum, 2007, 26(3):375-384 . |
| [58] | Kharevych L, Springborn B, Schroder P. Discrete conformal mappings via circle patterns. ACM Trans. on Graphics, 2006,25(2): 412-438 . |
| [59] | Bommes D, Lévy B, Pietroni N, Puppo E, Silva C, Tarini M, Zorin D. Quad-Mesh generation and processing: A survey. Computer Graphics Forum, 2013,32(6):51-76 . |
| [60] | Ben-Chen M, Gotsman C, Bunin G. Conformal flattening by curvature prescription and metric scaling. Computer Graphics Forum, 2008,27(2):449-458 . |
| [61] | Yang YL, Kim J, Luo F, Hu SM, Gu X. Optimal surface parameterization using inverse curvature map. IEEE Trans. on Visualization and Computer Graphics, 2008,14(5):1054-1066 . |
| [62] | Springborn B, Schroder P, Pinkall U. Conformal equivalence of triangle meshes. ACM Trans. on Graphics, 2008,27(3):77:1-77:11 . |
| [63] | Jin M, Kim J, Luo F, Gu X. Discrete surface ricci flow. IEEE Trans. on Visualization and Computer Graphics, 2008,14(5): 1030-1043 . |
| [64] | Lai Y, Jin M, Xie X, He Y, Palacios J, Zhang E, Hu S, Gu X. Metric-Driven rosy field design and remeshing. IEEE Trans. on Visualization and Computer Graphics, 2010,16(1):95-108 . |
| [65] | Gu X, Gortler S, Hoppe H. Geometry images. ACM Trans. on Graphics, 2002,21(3):355-361 . |
| [66] | Fu X, Liu Y, Guo B. Computing locally injective mappings by advanced MIPS. ACM Trans. on Graphics, 2015,34(4):71:1-71:12 . |
| [67] | Lipman Y. Bounded distortion mapping spaces for triangular meshes. ACM Trans. on Graphics, 2012,31(4):108:1-108:12 . |
| [68] | Schuller C, Kavan L, Panozzo D, Sorkine-Hornung O. Locally injective mappings. Computer Graphics Forum, 2013,32(5):125-135 . |
| [69] | Huang J, Zhang M, Ma J, Liu X, Kobbelt L, Bao H. Spectral quadrangulation with orientation and alignment control. ACM Trans. on Graphics, 2008,27(5):147:1-147:9 . |
| [70] | Crane K, Desbrun M, Schröder P. Trivial connections on discrete surfaces. Computer Graphics Forum, 2010,29(5):1525-1533 . |
| [71] | Bommes D, Campen M, Ebke H, Alliez P, Kobbelt L. Integer-Grid maps for reliable quad meshing. ACM Trans. on Graphics, 2013, 32(4):98:1-98:12 . |
| [72] | Liao T, Xu G, Zhang Y. Structure-Aligned guidance estimation in surface parameterization using eigenfunction-based cross field. Graphical Models, 2014,76(6):691-705 . |
| [73] | Kovacs D, Myles A, Zorin D. Anisotropic quadrangulation. Computer Aided Geometric Design, 2011,28(8):449-462 . |
| [74] | Liu Y, Xu W, Wang J, Zhu L, Guo B, Chen F, Wang G. General planar quadrilateral mesh design using conjugate direction field. ACM Trans. on Graphics, 2011,30(6):140:1-140:10 . |
| [75] | Panozzo D, Puppo E, Tarini M, Sorkine-Hornung O. Frame fields: Anisotropic and non-orthogonal cross fields. ACM Trans. on Graphics, 2014,33(4):134:1-134:11 . |
| [76] | Jiang T, Fang X, Huang J, Bao H, Tong Y, Desbrun M. Frame field generation through metric customization. ACM Trans. on Graphics, 2015,34(4):40:1-40:11 . |
| [77] | Ebke HC, Campen M, Bommes D, Kobbelt L. Level-of-Detail quad meshing. ACM Trans. on Graphics, 2014,33(6):184:1-184:11 . |
| [78] | Marcias G, Takayama K, Pietroni N, Panozzo D, Sorkine-Hornung O, Puppo E, Cignoni P. Data-Driven interactive quadrangulation. ACM Trans. on Graphics, 2015,34(4):65:1-65:10 . |
| [79] | Sander P, Wood Z, Gortler S, Snyder J, Hoppe H. Multi-Chart geometry images. In: Proc. of the Eurographics Symp. on Geometry Processing. The Eurographics Association, 2003. 146-155. http://diglib.eg.org/handle/10.2312/SGP.SGP03.146-155 |
| [80] | Eppstein D, Goodrich M, Kim E, Tamstorf R. Motorcycle graphs: Canonical quad mesh partitioning. Computer Graphics Forum, 2008,27(5):1477-1486 . |
| [81] | Myles A, Pietroni N, Kovacs D, Zorin D. Feature-Aligned T-meshes. ACM Trans. on Graphics, 2010,29(4):117:1-117:11 . |
| [82] | Krishnamurthy V, Levoy M. Fitting smooth surfaces to dense polygon meshes. In: Proc. of the ACM SIGGRAPH. ACM Press, 1996. 313-324 . |
| [83] | Tierny J, Daniels J, Nonato LG, Pascucci V, Silva C. Interactive quadrangulation with reeb atlases and connectivity textures. IEEE Trans. on Visualization and Computer Graphics, 2012,18(10):1650-1663 . |
| [84] | Campen M, Bommes D, Kobbelt L. Dual loops meshing: Quality quad layouts on manifolds. ACM Trans. on Graphics, 2012,31(4): 110:1-110:11 . |
| [85] | Bommes D, Lempfer T, Kobbelt L. Global structure optimization of quadrilateral meshes. Computer Graphics Forum, 2011,30(2): 375-384 . |
| [86] | Campen M, Kobbelt L. Dual strip weaving: Interactive design of quad layouts using elastica strips. ACM Trans. on Graphics, 2014, 33(6):183:1-183:10 . |
| [87] | Campen M, Kobbelt L. Quad layout embedding via aligned parameterization. Computer Graphics Forum, 2014,33(8):69-81 . |
| [88] | Pietroni N, Tarini M, Sorkine O, Zorin D. Global parametrization of range image sets. ACM Trans. on Graphics, 2011,30(6): 149:1-149:10 . |
| [89] | Nieser M, Palacios J, Polthier K, Zhang E. Hexagonal global parameterization of arbitrary surfaces. IEEE Trans. on Visualization and Computer Graphics, 2012,18(6):865-878 . |
| [90] | Aigerman N, Poranne R, Lipman Y. Lifted bijections for low distortion surface mappings. ACM Trans. on Graphics, 2014,33(4): 69:1-69:12 . |
| [10] | 胡事民,杨永亮,来煜坤.数字几何处理研究进展.计算机学报,2009,32(8):1-8. |
| [38] | 严寒冰,胡事民.球面坐标下的凸组合球面参数化.计算机学报,2005,28(6):927-932. |
| [41] | 周昆,鲍虎军,石教英.统一的数字几何处理框架.计算机学报,2002,25(9):904-909. |