网格参数化是计算机图形学和数字几何处理的基本工具,有着广泛的应用背景.对网格参数化的研究进展进行了综述,主要从参数域和参数化质量两个方面介绍了网格参数化的研究现状.根据参数域的不同,讨论了平面参数化、基网格参数化、球面参数化以及曲面间的交叉参数化;根据参数化质量的不同,介绍了保长度的参数化、保特征的参数化以及致力于参数域简单的参数化.对参数化进行了分类介绍和讨论分析,概括介绍了每类方法的主要思想,讨论了每类方法的主要特性,对其中一些方法进行了比较分析,并对参数化方法存在的难点问题和未来可能的研究方向进行了总结,以期对参数化的研究进展有全面的了解.
Mesh parameterization is a powerful computer graphics and geometry processing tool with applications on numerous computer graphics. In this paper, a survey of recent advances in mesh parameterization is presented. This survey reviews different techniques, classifying them based on parameter domain usage and parameterization quality. Based on different parameter domain, it discusses planar parameterization techniques, parameterization methods for domains such as simplicial complexes and spheres, as well as methods for cross-parameterization between mesh surfaces. Based on different parameterization quality, it describes methods for minimizing metric distortion, maintaining alignment to mesh features and improving domain simplicity. It summarizes the main ideas of different techniques, discusses their core properties and compares some techniques to other techniques available. Also it presents a list of open research problems that require further work. This survey aims to provide the readers with a comprehensive study of mesh parameterization.
网格参数化通常是指镶嵌在三维空间中的一个二维流形曲面与一个简单的参数域之间的一一映射[ 网格参数化的应用 Mesh parameterization applications
最近几十年来,参数化一直是研究的热点,国内外专家、学者和技术人员在网格参数化方面做了大量的研究工作,网格曲面参数化取得了相当程度的进展,但是仍然有很多重要的问题值得进一步研究[
为了适应不同的应用背景和参数化特性,人们开发了不同的参数化方法,这些参数化方法采用的参数域不同,取得参数化的质量也不尽相同.本文首先对文中用到的一些术语进行简单的回顾,然后从参数域和参数化质量两个方面讨论网格参数化的研究现状.
由于几何模型是嵌入在三维空间中的二维流形,它本身不具备规则的参数域,这给三维模型的高效处理带来了很多困难.网格参数化就是研究三维空间中的几何模型和某个更简单、更规则的参数域之间的一个映射,使许多在复杂的二维流形上执行的操作能转换到简单的参数域上执行,从而提高操作的可行性和效率.许多应用程序要求一一映射,也即参数域内点与原始网格上的点一一对应.对于某些应用程序,局部一一映射(没有三角形翻转)就已足够;另外一些应用程序则需要全局一一映射(边界不自交).目前,只有一部分参数化方法能够保证局部或全局一一映射,其他一些方法在输入满足特定条件下才能够保证一一映射.
参数域上三角形 参数化映射 Parameterization
为了更好地理解这种变形,我们从微分几何的角度来考察曲面上的点
把上面的泰勒展式改写为
这里,
其中,奇异值 映射$\tilde f$的奇异值分解[ SVD decomposition of the mapping$\tilde f$[
● 首先,变换
● 然后,变换
● 最后,变换
最后的结果是$\tilde f$将以
标架[
将圆变换到椭圆的变换称为参数化的局部度量失真(local metric distortion),局部度量失真的信息隐藏在奇异值
●
●
●
显然,保长度参数化既保角度又保面积.换句话说,保长度等价于保角度+保面积.
理想参数化是保长度的,也即零失真的参数化.很少一部分网格曲面能够得到保长度的参数化,网格曲面参数化的总体目标就是找到三维空间中的几何模型和某个参数域之间的一个映射,并且最小化不可避免的度量失真[
(1) 调和映射(harmonic map)
早期参数化方法[
(2) 保角映射
保角映射的本质是调和映射[
保角映射也是求解一个线性问题,优点是只需要固定边界上的两个点就可以得到唯一解,缺点是参数化结果依赖这两个点的选择,并且非一一映射的问题依然存在.
显然,当
同时度量了参数化映射
(3) 其他度量扭曲的能量函数
这方面工作比较多,有的基于格林-拉格朗日变形张量(Green-Lagrange deformation tensor)[
文献[
其中,
文献[
文献[
然而,
其中,
文献[
该能量函数可以在保角和保面积中取得较好的平衡[
为了保证局部内射,三角形不能改变方向.这就要求,当
其中,
参数域简单是指组成参数域的面片数量少,每个面片具有规则形状(例如矩形),能够对齐特征,对于非拓扑圆盘需要分片的情形,片与片之间的转换函数简单[
早期,人们主要对平面域上的网格参数化感兴趣.平面参数化的优势在于,平面是二维形式中最简单的,也是纹理、图像等最自然的载体.平面参数化的缺点在于,仅适用于与拓扑圆盘同构的网格曲面,对于亏格大于0的网格曲面,一般需要按照一定的规则将整个网格分片.分片往往会引起参数化结果不连续,一些应用对参数化不连续非常敏感甚至完全不能忍受,于是,当被参数化的对象不是一个拓扑圆盘时,为了避免平面参数化不必要的拓扑分割,一些算法使用非平面参数域,例如基网格域和球面域.
与基网格参数化类似,交叉参数化(cross parameterization)又称作曲面间的映射,通常也需要一个公共基参数域.
文献[
对于亏格大于0的网格曲面,平面参数化往往需要分片,如
由于分片往往会引起参数化结果不连续,有些应用不允许参数化不连续,为此,人们研究了全局参数化,如
近年来,人们研究实现了无缝全局参数化.无缝全局参数化非常有用,因为它能产生无缝纹理映射[
无缝全局参数化[
Seamless global parameterization[
● 如果
● 如果进一步对
基网格参数域是指结构上比较简单的网格,如 基网格 Base mesh
Eck等人[
文献[
Comparison of
文献[ | 文献[ | 文献[ | 文献[ | 文献[ | 文献[ | |
Bunny | 1.04 | 0.80 | 0.92 | - | 1.02 | 0.97 |
Horse | 1.06 | - | - | 1.11 | 1.03 | - |
Venus | 1.03 | - | - | - | 1.02 | - |
David Head | 1.06 | 0.76 | 0.90 | - | - | - |
文献[ 上面一行:文献[ Upper row: The parameterization results of Ref.[
基网格参数化的优势在于适用高亏格的情形,能够保留原始网格的拓扑关系,并且在几何上与原始网格近似,通常参数化变形较小[
球面域如 球面参数化 Spherical parameterization
球面域上的参数化方法基本上可以分成3类[
1) 球面松弛的方法:例如,文献[
2) 基于凸组合的方法:Gotsman等人[
3) 基于累进网格的方法:文献[
文献[ 文献[ Comparison of
Venus Bunny Gargoyle Armadillo Horse Cow Tyrannosaurus 文献[ 0.943 0.706 0.643 0.454 0.363 0.405 0.360
文献[ 0.947 0.717 0.679 0.528 0.398 0.440 0.428
球面参数化适合亏格为0的闭曲面,相对于平面参数化和基网格参数化,球面参数化的研究少得多,这是因为,球面参数化产生的变形扭曲较大并且球面参数化比平面参数化困难.
交叉参数化特别适用于曲面间变形、纹理映射和曲面混合(blending)等等,文献[
与基网格参数化类似,交叉参数化通常需要一个公共的基参数域,虽然有很多构造基参数域和对基参数域优化的方法,例如文献[
有些方法使用目标网格作为公共参数域,例如:Allen等人[
综上可以看出,一个合适的参数域对于交叉参数化至关重要.Wu等人[ 交叉参数化[ Cross parameterization[
与规则参数域相比,网格的复杂形状可以较容易地映射到凸包参数域,可以比较精确地逼近目标的几何形状.方法的缺点在于:对于复杂的网格模型,不同区域有可能嵌入到凸包的相同部分.与文献[ 文献[ Performance comparison between Ref.[
网格 面片数 标记点数 文献[ 文献[ lion/cat 9996/14410 18 105秒 45秒 lion/cat 9996/14410 63 15分 33秒 lion/cat 29988/43230 63 >2小时 251秒 lion/cat 29988/43230 80 失败 242秒 lion/camel 9996/19536 18 4分 69秒 cube/bumpy sphere 12288/11444 8 49秒 84秒
Venus/Planck 16532/20043 27 10分 126秒
还有一些研究主要讨论具有不同拓扑结构模型之间的映射,例如:Zhang等人[
交叉参数化也不可避免地导致参数化前后不同程度的扭曲变形.为了减少变形,文献[ 拉伸能量 Comparison between optimization metrics
Buddha Bunny Cow Dinosaur Dragon Feline Horse Venus Rabbit 1.27 26.80 1.13 3.92 1.11 3.07 1.07 1.55 1.26 13.78 1.10 1.73 1.09 1.65 1.10 2.99 1.12 3.00
1.18 1.56 1.02 0.23 1.03 0.28 1.03 0.25 1.13 0.83 1.02 0.22 1.03 0.22 1.02 0.17 1.03 0.24
除了平面参数化,曲面间一一映射的一种常用方法也是将曲面分片,每片是一个拓扑圆盘,然后将这些拓扑圆盘通过某些优化过程映射到一个公共参数域上.与平面参数化一样,分片往往会引起映射结果不连续,为此,文献[ 曲面间的无缝一一映射[ Seamless surface mappings[
交叉参数化的主要困难在于,很难为具有相似特征和拓扑结构的不同输入模型构造一个合适的公共基参数域.
高质量的网格参数化是许多应用的基础.网格参数化质量的定义取决于应用背景,通常情况下,高质量的参数化需要满足保长度(同时保面积和保角度)、保特征、参数域简单等[
保长度的参数化要求网格曲面是可展的,但是一般网格曲面不满足这个约束,因此人们考虑弱一些的约束,只考虑保角度或者保面积.与保长度不同,从连续曲面到平面的保角映射总是存在,一些工作考虑了保角映射的离散近似,例如文献[
有些方法通过锥状奇异点进一步减轻参数化变形[
最近,文献[
其中,${E_{\det }}({J_f}) = \frac{1}{2}(\det ({J_f}) + \det {({J_f})^{ - 1}}).$在实验中[
这里,
●
●
通过最优化AMIPS能量函数,可以有效抑制最大变形,从而能够紧密控制变形分布,并且AMIPS继承了MIPS方法局部单射的优点.AMIPS与BDM(bounded distortion mapping,简称BDM)[ 对兔子头部模型和Bimba模型分别采用AMIPS,LIM和BDM方法得到的保长度参数化比较[ Isometric parameterizations of a Bunny head and Bimba using AMIPS, LIM and BDM[ MIPS,ABF++,BDM,LIM和AMIPS方法保角参数化比较[ Comparison among conformal parameterizations of models using MIPS, ABF++, BDM, LIM and AMIPS[ AMIPS,LIM和BDM方法得到的保长度参数化比较[ Isometric parameterizations of models using AMIPS, LIM and BDM[
模型 $\delta _{\max }^{iso}/\delta _{avg}^{iso}/\delta _{dev}^{iso}$ $\delta _{\max }^{con}/\delta _{avg}^{con}/\delta _{dev}^{con}$ Time (s) Bunny head(AMIPS) 3.89/2.57/0.56 5.92/3.23/0.97 2.21 Bunny head(BDM(5)) 18.18/3.64/2.08 5.00/3.74/0.87 47.87 Bunny head(BDM(9)) 8.97/2.84/1.14 9.02/4.62/2.01 43.15 Bunny head(LIM) 6.29/2.39/0.99 39.07/6.09/5.32 41.19 Bimba(AMIPS) 4.62/2.20/0.47 6.18/2.44/1.03 4.87 Bimba(BDM(5)) 7.83/2.59/1.10 5.00/3.32/1.12 106.48 Bimba(BDM(9)) 6.99/2.42/0.97 9.00/4.06/2.22 89.49
Bimba(LIM) 6.79/2.29/0.92 27.71/4.05/3.83 16.31
在 MIPS,ABF++,BDM,LIM,AMIPS方法得到的保角参数化方法比较[ Comparison among conformal parameterizations using MIPS, ABF++, BDM, LIM and AMIPS[
MIPS ABF++ BDM LIM AMIPS Isis (4.99,1.21,7.87s) (2140.44,4.20,0.31s) (6.00,1.12,8.80s) (7.53,1.12,8.52s) (4.51,1.09,2.19s) Fandisk (19.47,1.23,11.96s) (1983.90,2.65,0.38s) (2.68,1.08,18.27s) (2.39,1.07,2.07s) (2.08,1.04,2.05s) Male (14.55,1.31,7.32s) (3996.92,4.32,0.30s) (41.98,1.64,12.38s) (69.00,1.47,5.22s) (12.75,1.28,1.21s) Camel (15.72,1.31,7.09s) (1544.19,3.27,0.27s) (26.98,1.52,13.00s) (26.21,1.33,4.03s) (3.96,1.20,1.68s) Bunny (2.45,1.05,99.62s) (33.53,1.02,5.08s) (1.42,1.02,313.26s) (1.47,1.02,744.64s) (1.41,1.02,22.10s)
Dino (11.21,1.05,62.40s) (153.89,1.04,6.71s) (8.00,1.03,371.90s) (29.26,1.03,230.39s) (7.20,1.03,15.29s)
文献[ Triceratops模型:左边采用 Triceratops optimized with 带边界约束优化和不带边界约束优化得到的等距度量 The average error and maximum error using isometric metric
模型 Avg. Max Avg. Max Cow 5.466 14.763 5.843 14.751 Camel 9.203 28.082 9.351 27.216 Triceratops 4.327 17.465 4.455 12.669 Horse 7.280 26.499 7.300 39.890
Head 10.081 75.904 10.097 33.357
Dong等人[ 一些非一一映射参数化的例子(反转的三角形用红色显示)[ Examples of non-bijective parametrizations (inverted triangles shown in red)[
Liao等人[
前面许多工作基于对称方向场,对称方向场是正交、单位长度的标架场,对称方向场不支持各向异性.后来, Kovacs等人[ 文献[ Comparison between uniform quadrangulation of Ref.[
这两种方法使用了相同数量的四边形,采用了同样的约束,使用文献[ 文献[ Comparison between the method of Ref.[
目前,多数方法假设输入的网格都是“好”网格,这里的好网格是指无噪声、分段光滑、不存在太多过于丰富的细节.这些细微的几何和拓扑类型的特征或者噪声会导致出现严重问题:在好的情况下,这些带有细节的输入导致四边形剖分产生扭曲;在坏的情况下,算法会失败,如 好网格和带有噪声的网格比较[ Comparison of well-behaved mesh and the mesh containing noise[
最近,文献[ 数据驱动、交互设计四边形剖分[ Data-Driven interactive quadrangulation[
文献[ 文献[ A comparison between quadrangulations proposed by Ref.[
Gu等人[ 基本概念[ Basic concept[ 简单参数域的比较[ Comparison of simple domains obtained by different methods[ 对偶环产生的四边形布局[ Quad layout induced by dual loops[
文献[
与文献[ 组成参数域的面片数比较[ Patch numbers of parameter domains proposed by different methods[
模型 面片数量 文献[ 文献[ BOTIJO 221 175 BLOCK 76 76 GUY 168 55 ELK 86 62 ROCKETARM 115 74
FERTILITY 98 117
上述许多方法主要讨论了简单参数域的结构或者拓扑方面的问题,而文献[ 上面是算法[ Given a rough layout graph (top), the output of the method of Ref.[ 文献[ Comparison of the method proposed by Ref.[ 文献[ Comparison of conformal energy
模型 文献[ 文献[ TRIHOLE 2.047 2.026 ROCKERARM 2.069 2.085 FERTILITY 2.049 2.066 BLOCK 2.013 2.022 ELK 2.065 2.106 BOTIJO 2.060 2.074
ELEPHANT 2.145 2.109
尽管实验结果表明(如
Campen等人引入对偶带(dual strip)的概念,如
一些文献将现有的网格参数化方法进行扩展,例如:He等人[ 六边形全局参数化[ Hexagonal global parameterization[
本文主要从参数域和参数化质量两个方面来介绍网格参数化的研究现状,概括介绍了每项技术的主要思想,讨论每项技术的主要特性,并对其中一些方法与其他方法进行了比较分析.虽然网格参数化已经取得了丰富的理论成果和应用技术,但是仍然存在如下一些难点问题.
● 目前,只有极少的方法不经过用户的介入就能得到一一映射的网格参数化[
● 高质量的网格参数化需要满足参数域简单,一些致力于简单参数域的方法往往采用从现有三角网格产生粗面片布局,但从三角网格自动产生理想的粗面片布局依然是一个具有挑战性的难题[
● 多立方体参数化(polycube parameterization)采用多立方体作为参数域,是一类特殊的全局参数化方法.该类方法使纹理映射变得简单,还可以生成高质量的四边形网格.虽然近年来涌现了许多关于多立方体参数化的研究,但自动或半自动构造健壮的多立方体参数化,仍然是一个开放性的难题[
网格参数化还有一些重要问题需要进一步深入研究,未来可能的研究方向可有如下几个.
● 参数化质量.
通常情况下,高质量的参数化需要满足保长度、保特征、参数域简单等条件.为了进一步提高参数化质量,由于一般模型不是可展曲面,不可能得到保长度的参数化,因此针对一般模型,需要研究快速获得最接近于零失真或者保长度的参数化方法.参数化应用越来越广泛,需要进一步考虑针对特定应用描述复杂的约束和获得带复杂约束的参数化方法.为了获得简单参数域,需要提升用作参数域的网格质量.特别地,奇异点的位置和数量可以减轻参数化变形和提升用作参数域的网格质量,因此需要研究奇异点的放置问题.许多致力于简单参数域的方法从现有三角网格自动产生粗面片布局,但是,自动方法具有一定的局限性,往往不能处理复杂的结构.在工厂里,粗面片布局往往是由专业设计人员手工创建的,在创建过程中,专业设计人员依据特殊的应用背景,充分运用他们的语义知识和经验.工厂里应用的造型系统允许用户手工绘制点和边,但是手工操作过程过于耗时,并且容易出错,因此需要研究高效的交互创建粗面片布局的方法.
● 健壮性.
一方面,目前只有一部分参数化方法能够保证局部或全局一一映射,其他一些方法在输入满足特定条件下可以保证一一映射;另一方面,目前参数化方法往往假设输入网格没有噪声、分段平滑、没有太多太细的特征,但实际上,输入网格往往不完备、含有噪声,这样的输入网格尤其需要健壮的参数化方法.
● 数学基础.
参数化的许多目标依赖于从理论上深入理解参数化技术,这就需要将参数化与科学计算的其他一些领域,例如逼近理论、应用数学和有限元建模等相关联.这些领域的一些技术从20世纪40年代以来得到了持续的开发,目前已经发展成熟.将这些领域的先进技术引入到几何处理领域中来,有可能导致重大发展[
国家自然科学基金(61202148, 61332015, 61373078, 61272245); 国家自然科学和广东联合基金重点支持项目(U1201258)