（计算机应用技术专业论文）三角网格参数化的研究.pdf

山东大学硕士学位论文 摘要 三角网格参数化有广泛的应用背景，是计算机图形学、计算机辅助几何设计 等领域中研究的重要问题之一，如曲面拟合，纹理映射，重网格化( r e m e s h i n g ) 等方面都需要参数化的相关工作。还有很多数字几何处理，如交互式三维绘画、 三维网格编辑、网格m o r p h i n g 等都需要事先把网格参数化到一个容易交互式处理 的参数域，所以参数化的工作有着重要的研究意义。 根据参数域的不同，三角网格参数化基本上可以分为两大类，即平面参数化 和球面参数化。下面我们分别介绍对这两类参数化问题的研究成果。 直观上讲，平面参数化就是把一个空间三角网格平摊成平面三角网格，在保 证平面三角网格有效性的同时最小化变形。这种参数化方法的研究对象主要集中 在带单条边界的二维流形网格上，因为封闭网格甚至是任意拓扑的网格都可以通 过分而治之( d i v i d ea n dc o n q u e r ) 的方法转化为带边界网格。 陈中贵提出了一种基于排列局部展平区域来进行参数化的方法。针对这篇文 章中所存在的一些问题，本文提出了两种新的局部投影方法，一种是局部保角和 保面积的展平方式，另一种是局部保角和保周围边界的展平方式。通过对实验结 果的分析，我们发现利用后两种方法所得到的参数结果构造曲面时，能更贴近原 始曲面，误差更小，而且网格整体的面积和角度变形都有了较大的改善，当然算 法的缺点是计算量的增加。 对封闭网格，最直接的想法是参数化到球域上。将亏格为零的三维模型进行 球面参数化的方法大致可以分成3 类：( 1 ) 基于累进网格的方法( 2 ) 球面松弛的 方法( 3 ) 保角参数化方法。三种方法各有优缺点，但基于累进网格的方法是比较 快速的方法。 本文提出了一种新的球面参数化方法，简称为基于累进网格的j m 球面参数化 方法。目标函数是j e r o m em a i l l o t 基于面积和边长的目标函数在球面上的推广。算 法首先对原始三角网格构造一个累进网格，把三角网格简化成最简单的形式，四 面体。参数化过程首先把四面体影射到球面上，然后再根据累进网格逆序把删除 的顶点参数化到球面上，基于的目标函数便是推广的j e r o m em a i l l o t 了标函数。遍 历完整个累进网格，也就完成了球面参数化。 山东大学硕士学位论文 当然，这个算法的执行过程中还存在着一些问题，例如在累进网格的构造过 程中并没有保持原始网格的特征，参数化的整体结果还没有与已有的算法进行具 体的比较，这都是需要我们继续完善的地方。 关键词：三角网格平面参数化球面参数化累进网格变形 a b s t r a c t s u r f a c ep a r a m e t e r i z a t i o ni su s e dw i d e l yi nc o m p u t e rg r a p h i c s ，c a g d ，s u c ha s t e x t u r em a p p i n g ，s u r f a c ef i t t i n g ，r e m e s h i n g t h e r ea r es t i l l m a n ya p p l i c a t i o n si n d i g i t a lg e o m e t r yp r o c e s s i n g ，l i k ed r a w i n gi n3 di n t e r a c t i v e l y , 3 dm e s he d i t i n g ，m e s h m o r p h i n g t h e ya l ln e e dt h e3 dm e s hp a r a m e t e r i z e d s ot h es u r f a c ep a r a m e t e r i z a t i o n h a sg r e a ti m p o r t a n c e b a s i n go nt h ed i f f e r e n tp a r a m e t e rd o m a i n ，t h e3 dm e s hp a r a m e t e r i z a t i o nc a nb e d i v i d e di n t ot w oc a t e g o r i e s ：p l a n a rp a r a m e t e r i z a t i o na n ds p h e r i c a lp a r a m e t e r i z a t i o n t h e nw ew i l li n t r o d u c et h em a i nj o b st h a tid oi nt l l i sf i e l d i n t u i t i v e l yp a r a m e t e r i z a t i o ni np l a n a rd o m a i ni st ot r a n s f e rt h e3 dm e s ht o p l a n a rm e s hw i t ht h eg u a r a n t yt h a tt h ep l a n a rm e s hi sv a l i da n dt h ed i s t o r t i o ni s m i n i m i z e d t h et a r g e to fp l a n a rp a r a m e t e r i z a t i o ni sf o c u s e do n2 dm a n i f o l dm e s h w i t hs i n g l eb o u n d a r y , a n da n yc l o s e dm e s hc a nb ec h a n g e di n t om e s hw i t hb o u n d a r y i nt h ew a yo fd i v i d i n ga n d c o n q u e r i n g z h o n g g u ic h e np r o p o s e dan e wp a r a r n e t e f i z a f i o nm e t h o db a s e do na l i g n i n gt h e o p t i m a ll o c a lf l a t t e n i n g f o c u s i n go nt h ed i s a d v a n t a g ei nt h i sa r t i c l e ，w ep r o p o s e dt w o n e w f l a t t e m n gw a y s ，t h ef i r s tp r e s e r v e sa n g l ea n da r e a , t h eo t h e rp r e s e r v e sa n g l ea n d b o u n d a r yl e n g t h w eh a v ef o u n dt h a ts u r f a c ec o n s t r u c t e dw i t ht h ep a r a m e t e r i z a t i o n t h a tt h ei m p r o v e dm e t h o d sg o ti sm o r ec l o s et ot h es o u r c es u r f a c e ，a n dt h ed i s t o n i o n i sl e s s a tt h es a m et i m et h ed i s t o r t i o no f a n g l ea n da r e ah a sd e c l i n e d t h ef i r s tt h o u g h to f p a r a m e t e r i z i n gc l o s e dm e s hi sd o i n gt h i si nt h es p h e r ed o m a i n t h e s em e t h o d sc a nb ed i v i d e di n t ot h r e e ：( 1 ) m e t h o db a s e do np r o g r e s s i v em e s h ( 2 ) m e t h o db a s e do ns p h e r er e l a x a t i o n ( 3 ) c o n f o r m a lm e t h o d t h et h r e em e t h o d sh a v e t h e i ro w n a d v a n t a g e sa n ds h o r t c o m i n g s b u tt h em e t h o db a s e do np r o g r e s s i v em e s hi s m u c hf a s t e r i nt h i s a r t i c l ew ep r o p o s ean e ws p h e r i c a lp a r a m e t e r i z a f i o nm e t h o d a n dt h i s m e t h o di sj u s tb a s e do np r o g r e s s i v em e s h t h eo b j e c t i v ef u n c t i o ni st h e g e n e r a l i z a t i o n o fw h i c hi su s e db yj e r o m em a i l l o t t h ea l g o r i t h mf i r s tc o n s t r u c ta p r o g r e s s i v em e s h b a s e do nt h es o u r c em e s ha n dc h a n g et h em e s hi n t ot h es i m p l e s tf o r m ，t e t r a h e d r o n d u r i n gt h ep a r a m e t e r i z a t i o n ，w ef i r s tm a pt h et e t r m h e d r o nt oau n i ts p h e r e t h e nw e i n s e r tt h ed e l e t e dv e r t e xt ot h es p h e r eb a s e do nt h ep r o g r e s s i v em e s h a n dn l e 一 l l i 山东大学硕士学位论文 o b je c t i v ef u n c t i o ni st h eg e n e r a l i z e df u n c t i o no fj e r o m em a i l l o t h o w e v e r , t h e r ea r es t i l ls o m ep r o b l e m si nm ym e t h o d ，s u c h 嬲t h em e t h o do f h a n d l i n gt h ep r o g r e s s i v em e s hd o e s n tp r e s e r v et h ef e a t u r e so ft h es o u r c em e s h ，a n d t h er e s u l th a s n tb e e nc o m p a r e d 、枋mo t h e ra l g o r i t h m s t h e s ep r o b l e m sa r et h e d i r e c t i o no fo u rl a t e ri n v e s f i g a t i o n k e yw o r d s ：t r i a n g l em e s h ，p l a n a rp a r a m e t e r i z a t i o n ，s p h e r i c 蚰 p a r a m e t e r i z a t i o n ，p r o g r e s s i v em e s h ，d i s t o r t i o n i v 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均己在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：企基e t 期：乏塑：垒 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 、 ( 保密论文在解密后应遵守此规定) 论文作者签名：诠磐 导师签名： 山东大学硕士学位论文 1 。1 地图投影 第一章绪论 地图投影( m a pp r o j e c t i o n ) 就是试图把地球的全部表面或者某一部分映射到 平面上的操作。这个映射过程总会引起角度，距离，方向，l ：l 侈r j 或者面积的变形。 映射方式在最小化某个形变时总会引起其他性质的变形增大。当然也有方法使得 所有这些性质的变形均有所优化，而不单单追求某一属性的最优化。 就像要把一个桔子皮展平放在桌子上，如果不挤压或者扯碎桔子皮，是不可 能办到的。球面映射也一样，没有变形，是不可能把一个球面映射到平面上的。 下图我们看一些早期的地图投影在处理变形问题上是如何取舍的。 图( a ) 是一个正投影，早在两千多年前，埃及人和希腊人就知道了这种投 影方式，这种方式既不保持角度又不保持面积，但从映射中心开始的方向性是正 确的。图( b ) 是使用最广泛的一种地图，立体投影。这是一种保角映射，即保 持了图形的相对形状，但不保持面积。立体投影把圆仍然映射成为圆，这里绘制 成为斜航线，同一条线上有相同的方向，这一点在航海中非常重要。后来，佛兰 德人m e r c a t o r 为了让水手们在航行中可以确定路线，研究出了m e r c a t o r 投影方 式( c ) 。在这种映射方式里，斜航线被绘制成了直线。立体投影和m e r c a t o r 投影 都是保角映射，而不保面积。兰勃特在1 7 7 2 年，第一个提出了等面积映射，如 图( d ) 所示。投影区域的面积保持与实地“相对相等”，也就是说，如果在地球上 国家么的面积是b 的两倍，那么绘制的地图上，a 的面积也是b 的两倍，而不再 保持角度的不变性。这种投影方式经常被用来映射大面积的区域，像陆地和半球。 ( a ) 正投影( b ) 立体投影 山东大学硕士学位论文 ( c ) 墨 托( m e r c a t o r ) 投影( d ) 兰勃特等面积投影 综上所述，地图映射就是把地球的某一部份表面映射到平面上的函数，映射 的逆操作通常叫做参数化。如果没有变形( d i s t o r t i o n ) 是不可能完成这个映射过 程的。每一种映射都有其自身的优点和缺点，也就是说没有最好的映射。地图的 设计者可以选择一种最适合自己要求的制作方式，以使得最重要特征的变形最 小。从后面的介绍中我们可以看到，虽然参数化的发展越来越科学化，精确化， 应用越来越多，但本质上仍然追求的是某种度量下的变形最小。 1 2 三角网格参数化的研究意义 曲面参数化可以看作是从眭面到合适的域空间的一个一一映射。曲面的表示 方式一般是三角网格，三角网格表示已经成为现在主流的复杂形状表面的三维模 型表示方法之一。三角网格通常是由3 d 扫描仪获取复杂表面采样点的几何信息， 并通过拓扑重建得到。所以这里我们说的曲面参数化实际上就是指的三角网格参 数化。 三角网格的参数化是对这些三角网格几何和拓扑信息作进一步处理的基础， 它在计算机图形学、计算机辅助几何设计和数字几何处理等方面有着广泛的应 用。比如，纹理映射利用表面网格参数化信息，把一幅纹理图像映射到三维网格 上，使得表面网格看上去更加生动逼真，这是参数化发展的最强劲的动力之一； 曲面拟合通过参数化把离散的3 d 数据点用一个光顺的参数曲面来拟合；重网格 化则利用参数化把三角化曲面转化成具有细分连通性的规则网格，并且在此基础 上进一步作多分辨率分析；还有很多数字几何处理，如交互式三维绘画、三维网 格编辑、3 d 变形等都需要事先把网格参数化到一个容易交互式处理的参数域。 2 山东大学硕士学位论文 1 3 研究目的和主要成果 参数化问题由于应用背景不同而分为许多类别，本文主要就平面域和球面域 参数化中一些问题进行了研究。 在平面参数化中，根据陈文章中的优缺点，本文提出了一些改进的措施和方 法，利用新方法所得到的参数结果构造曲面时，能更贴近原始曲面，误差更小， 而且网格整体的面积和角度变形都有了较大的改善。 在球面参数化中，纵观当前基本的参数化方法，结合在平面参数化中所存在 的一些经典影射理论，本文提出了一种新的球面参数化方法，j m 球面参数化。 目标函数是j e r o m em a i l l o t 基于面积和边长的目标函数在球面上的推广。算法首 先对原始三角网格构造一个累进网格，把三角网格简化成最简单的形式，四面体。 参数化过程首先把四面体影射到球面上，然后再根据累进网格逆序把删除的顶点 参数化到球面上，基于的目标函数便是推广的j e r o m em a i l l o t 目标函数。该方法 也是一种比较快速的方法，而且可以对方法继续进行优化，即只要对中间的目标 函数进行处理，就可以达到对整体结果的优化。 1 4 各章节安排 本文第一章介绍了地图映射的一些经典的映射方式。与曲面参数化的相类似 的工作基本上可以追溯到两千多年前，从那时候的地图映射( m a pp r o j e c t i o n ) 的 相关技术中我们可以看到参数化的影子。映射过程中的一些处理问题的方式对后 来我们参数化的工作仍有借鉴的意义。 本文在第二章介绍了平面参数化和球面参数化的相关工作。参数化在计算机 图形学、计算机辅助几何设计和数字几何处理等方面有着广泛的应用，它是同构 网格划分( c o n s i s t e n tm e s h ) 、重网格化( r e m e s h i n g ) 、纹理映射( t e x t u r e m a p p i n g ) 等工作的研究基础。平面参数化是进行参数化工作最直接的想法，即 把三维模型参数化到平面上，就像制作地图时最初的做法便是把地球表面映射到 平面上。在这一领域，已经有大量经典的映射方法。但平面参数化只能解决带边 界网格的参数化问题，对封闭网格需要进行切割分块处理；而分段参数化映射选 择的任意性和映射之间的无相关性，在切割线上往往会引发更多的参数化变形。 山东大学硕士学位论文 因此，把零亏格封闭网格参数化到与它拓扑同胚的球面更为合理。 本文在第三章里简要的介绍了对基于局部切空间排列的网格参数化方法的 改进，我们发现利用改进的方法所得到的参数结果构造曲面时，能更贴近原始曲 面，误差更小，而且网格整体的面积和角度变形都有了较大的改善。 本文在第四章里介绍了如何把j e r o m em a i l l o t 基于面积和边长的目标函数推 广到球面上，提出了一种新的球面参数化方法，简称j m 球面参数化方法。最简 单的球面参数化方法是将模型首先参数化到平面域上，然后将平面域上的参数化 结果再映射到球面上；或者将模型参数化到两个半球域上，再将半球域上的参数 化结果合并到一个球参数化域上。但是显然，这些参数化方法还是要依赖于对 模型的切割。1 9 9 8 年以后，出现了将三维模型直接参数化到球域上的方法。时 至今日，将亏格为零的三维模型进行球面参数化的方法大致可以分成3 类：( 1 ) 基于累进网格的方法( 2 ) 球面松弛的方法( 3 ) 保角参数化方法。三种方法各有优 缺点，但基于累进网格的方法是比较快速的方法。同其他基于累进网格的参数化 方法相似，j m 球面参数化方法仍然是分成三部分。首先基于原始三角网格构造 一个累进网格，这个过程记录下了原始网格如何精简成一四面体，又如何可以从 四面体恢复成原始网格。然后我们把这个四面体参数化到球面上，之后逆序遍历 这个累进网格序列，依次把删除的顶点加入到网格中，同时在球面上插入这个新 加入的点，如何确定新加入点的最优位置，我们利用的就是推广的j e r o m em a i l l o t 的目标函数。遍历完累进网格，球面参数化也就完成了。 在最后一章中，我们回顾了参数化的发展历程，总结了这个过程中所出现的 一些算法的特点以及优缺点，以及本文所提出算法的优缺点，并对未来进行了展 望。 4 山东大学硕士学位论文 第二章三角网格参数化的研究现状 实际上，三角网格参数化可归结为这样一个问题1 ：给定一个由空间点集组 成的三角网格m 和一个二维流形参数域q r 3 ( 通常为平面或者球面) ，寻求 一个在参数域上的点只q 到网格上的点只m 的一一映射m ，使得参数域上的 网格与原始网格拓扑同构，并在保证参数域上三角形不重叠的同时，谋求某种与 原始网格之间的几何度量的变形最小化。从数学角度来看，满足这种参数化有效 性的函数是很多的。寻找这样的函数并不是一件很难的事情，问题在于如何在这 么多映射中找到一个相对比较好的映射。人们通常使用一些几何的内在属性( 如 长度、角度和面积等) 的变形程度来衡量参数化的好坏。事实上，由于二维流形 曲面的复杂性，人们对是否存在最优的参数化方法的答案还是未知的。早在2 0 世纪6 0 年代研究人员就开始研究三角网格参数化问题，直到9 0 年代，该问题才得 到深入而广泛的研究，并发表了很多关于参数化的文献，这些技术都是为了解决 一个内在几何变量的变形最小化问题( d i s t o r t i o nm i n i m i z a t i o n ) 。通常，可利用微分 几何、弹性理论、等积映射、调和映射、保角映射和等测度映射等理论来对变形 最小化问题建模，并应用有限元分析以及数值分析等物理数学工具来求解变形最 小化问题。 参数化的工作根据其看问题的角度不同，可分为如下几类：( 1 ) 根据参数 域的不同可以分为平面参数化和球面参数化：( 2 ) 根据网格的拓扑信息可以分 为带边界网格参数化和封闭网格参数化，甚至是任意拓扑的三角网格参数化；( 3 ) 考察不同的内在几何变量的变形，可以分为保面积参数化、保角参数化和等距参 数化；( 4 ) 根据计算复杂度不同可以分为线性方法和非线性方法：( 5 ) 局部参 数化和整体参数化方法等。在这一章中我们仅介绍一下在平面参数化和球面参数 化领域的一些研究现状。 2 1 三角网格参数化的基本概念 从绪论中我们可以知道，映射总会引起角度或者面积的变形，一个好的映射 应该能够在某种意义上最小化这些变形。 l j i 东大字坝士字位i 仑文 蔓曼量曼皇曼鼍皇曼曼皇j_ n n m 量寰璺鼍曼曼曼鼍 根据心e y s 五2 ，。h 叩m 1 ，我们抽取一些有关映射的一些基本理论。 假设s 是尺3 中的一个曲面，其表达式为叉( ”，) c r 3 。假设云( f ) 是s 上得 一段曲线，f k6 】。所以夏( f ) = 又( z ，( f ) ，v ( f ) ) ， ( f ) ，v ( f ) ) 是尺2 的曲线，它在叉 下的镜像是夏。所以， 品( f ) ：娑一d u + 娑一d v ：甜石+ v 夏 (21)d 锄t西d t 1、。 若以s ( f ) 表示沿着孑的弧长，s 0 ) = 0 ，则 m ) = 舻怯 ( 2 - 2 ) 所以，鲁= 陬仆 ( 鲁) 2 = 眵( f ) | 1 2 = 夏喜= ( 甜石+ v 一x 2 ) 如x l + v 。一x 2 ) ( 2 3 ) 根据g a u s s 表达式，我们记 e = 夏石，f = 石一x 2 ，g = x 一2 一x 2( 2 4 ) 把这些系数写成矩阵的形式，= ( ；三 所以( d 魂s 、1 2 = e ( 幽) 2 + 2 f ( 幽咖) + g ( 咖) 2 = ( 幽咖) ，( ： ( 2 - 5 ) 上式便是曲面s 的第一基本形式，s 的许多性质都依赖于这个表达式。 2 1 1is o m e t ric 睡射 从一个曲面s 到另一个曲面s 的映射是等测度映射，即等距映射，当且仅当 s 上的任意弧的长度和这条弧在s 上的镜像的长度相等。例如，把一个圆柱映射 到一个平面上的变换便是一个等测度映射。 定理1 从曲面s 到曲面s 的映射是等测度映射，当且仅当它们的第一基本形 式的系数相同。即 6 山东大学硕士学位论文 i i 一_ i 曼,i i i 皇皇鼍皇皇皇曼曼曼曼曼曼皇曼曼量曼曼曼曼曼量曼曼曼曼曼曼曼曼量曼皇曼曼 i ：i 等测度的表面在任一对点处有相同的高斯曲率。 2 1 2 保角映射 从曲面s 到益面s 的映射是保角映射，当s 上每一对相交弧的相交角度和 s 上相应弧所形成的角度是相同的时候。例如，在1 1 节中立体投影和m e r c a t o r 投影都是保角度的投影方式。 定理2 从曲面s 到曲面s 的映射是保角映射，当且仅当它们第一基本形式的 系数是成比例的，即 i = 卵( “1 ，u 2 ) ，。 2 1 3 等面积映射 从曲面s 到曲面的映射是等面积映射，当s 的每一部分都映射到上之 后，面积保持不变。例如上一节中的l a m b e r t 投影方式。 定理3 从曲面s 到曲面的映射是等面积映射，当且仅当他们的第一基本形 式的行列式相等。即g = g ，其中 g = d e t i = e g f 2 上式得证明可以在k r e y s z i g t 2 1 中找到。 定理4 任一等测度映射都是保角和等面积的，每一个保角和等面积的映射都是 等测度的。也就是 i s o m e t r i cc ，c o n f o r m a l + e q u i a r e a l 我们可以把等测度映射看作理想的映射，因为它可以保持几乎所有的性质： 角度，面积和长度。然而，我们知道，等测度只在少数的情况下存在。当把s 映 射到平面上的时候，s 必须是可展的，例如圆柱。曲面参数化的许多方法都力图 于寻找一种方法： 1 保角的，也就是没有角度的变形 2 等面积的，没有面积的变形 3 最小化角度和面积变形。 7 山东大学硕士学位论文 2 2 参数化好坏的度量 ( 1 ) 参数化的有效性。通常所指的三角网格是一个可定向的二维流形三角网格， 所以三角网格参数化的有效性充分必要条件是： a 原始网格顶点和参数域网格顶点在参数化映射下是一一对应的( 双射) ； b 参数域上的三角网格不互相重叠 如图2 2 所示，硝是p 的有效参数点，而p ：是无效的，即b 是a 的有效参数化， c 是无效的参数化 勿因 abc 图2 2 参数化的有效性：a 为空间三角网格，b , c 为参数化到平面上的网格 ( 2 ) 参数化的度量。视觉上的平滑效果好坏是衡量参数化变形的一个直观标准， 参数化的变形有以下两种最常用的定量标准： a 用参数域网格与原始网格之间的面积相对误差和角度相对误差等误差测度 来衡量变形程度 r ，、2 珧= 引器一器i 亿6 ， 呶度= 靠厅a i 掣2 z + e ) 2 ( 2 7 ) 其中，j 为网格的某个三角形的索引；s ( ) 和a 分别是三角形面积和角度； e 表示三角形的角盈( 球面域) 。该误差测度是个整体变形度量，不体现 网格的局部三角形变形。 b 基于几何变形( g e o m e t r i c s t r e t c h ) 度量空间的方法啪。首先定义三角形 之间仿射变换的特征值度量空间 山东大学硕士学位论文 叩) = 历磊唧m ( 2 8 ) 其中r 和y 分别为仿射变换的雅克比矩阵的最大特征值和最小特征值。然后在 这个度量空间的基础上定义整体网格的参数化变形 r 似) _ 口( 树s ( 互) s ( z ) 五鲥i 鲥 ( 2 9 ) r 似) = 孵r ( 互) l 廿h 这种基于纹理扭曲程度的度量既可以反映局部三角形变形又可以衡量整体网 格参数化的变形，是一种更为普遍的度量方法。 2 3 平面参数化的各种方法 平面参数化方法的研究对象主要集中在带单条边界的二维流形网格上，因为 封闭网格甚至是任意拓扑的网格都可以通过分而治之的方法转化为带边界网格。 变形是对三角网格和参数域之间映射的第一基本形式变化的度量，也就是由 于引入的参数化，这个矩阵与单位矩阵的偏差。有许多不同的方法基于最小化这 个偏差来得到参数化结果，例如，s a n d e r 等人考虑最小化雅克比矩阵的奇异值的 范数 3 1 ，h o r m a n n 和g r e i n e r 最小化雅克比矩阵的条件数【4 】，s o r k i n e 等人使用了雅 克比矩阵的最大特征值以及它的倒数【5 】。这些方法都涉及到了复杂的算法，并且 参数化的结果也难以保证一定非常好。 一些自由边界的方法主要考虑的是控制角度变形。可以直接构造保角参数 化的算法，包括在自然边界条件下，最小化调和能量。s h e f f e r 和d es t u r l e r l 6 1 提出 了直接最小化角度的变形，他们使用了一个非线性最小化方法。这一类方法集中 于控制角度变形，除t d e s b m n 等人【7 】，他们定义了一个单独的等面积能量来控 制面积的变化。还有一些凸组合的方法 3 8 , 3 9 , 4 0 , 4 1 , 4 2 , 4 3 1 ，我们就不再多做介绍了。 上述的都是对开网格的处理。平面参数化对封闭网格通常是采用分而治之的 方法口6 3 ，即切割封闭网格成多个与圆盘同胚的面片。它实质上是一种分段参数 化( p i e c e w i s ep a r a m e t e r i z a t i o n ) ，其与分割展平法的区别在于，它的面片不是平 面可展曲面，因此必须应用带边界的参数化方法来进一步处理每一个面片。由 于平面参数化的分而治之作法本身就增加了参数化的变形，对于很多数字几何处 9 山东大学硕士学位论文 理的应用来讲( 如三维m o r p h i n g ) ，把封闭网格分割成面片进行平面参数化方法 不仅困难而且不合理，为此，近几年出现了很多球面参数化方法，避免这种不必 要的拓扑分割。 2 4 球面参数化的各种方法 近几年，球面参数化逐渐成为参数化工作的研究热点。对于大量零亏格的三 角模型，更自然的想法是将模型参数化到球面上。最简单的球参数化方法是将模 型首先参数化到平面域上，然后将平面域上的参数化结果再映射到球面上阳1 ；或 者将模型参数化到两个半球域上，再将半球域上的参数化结果合并到一个球参数 化域上瞪1 。但是显然，这些参数化方法还是要依赖于对模型的切割。1 9 9 8 年 以后，出现了将三维模型直接参数化到球域上的方法。到现在为止，将零亏格的 三角模型直接进行参数化的方法大致可以分为三类，下面分别简单的介绍一下。 2 4 1 球面松弛方法 k e n t 等提出了一个简单的球面参数化方法【l0 1 ，类似于平面域情况的能量方 程，他们模拟气球的膨胀将三角网格黏附在球面上，但是该方法在理论上并不严 谨，也不能保证参数化的有效性；a l e x a 提出了基于弹性理论的松弛参数化方法 1 1 - 1 2 1 ，该方法把网格的所有顶点投影到模型的最小包围球面上，然后保持球面上 6 个顶点的位置不动，用离散l a p l a c e 平均算子来松弛球面的其他顶点，达到球面 参数化的目的；k o b b e l t 等也提出了类似局部松弛的方法【1 3 】：但是这些方法都不 是强壮的球面参数化方法，它们都需要有很强的前提假设，并且没有从理论上考 虑参数化角度变形的问题，甚至对很多网格产生非有效参数化结果。 2 4 2 基于累进网格的参数化方法 s h a p i r o 等1 4 1 提出了一个基于网格简化的球面参数化方法，该方法通过删除 1 - r i n g 阶数小于6 的中心点，重新三角化由删除操作形成的空洞，直到原始网格简 化为四面体为止；然后将这个四面体映射为球面，并通过逆操作把被删除的顶点 添加至球面上。这类贪婪算法虽然处理很方便，但是很难进一步对参数化进行优 化。与这种顶点删除方法类似，q u i c k e n 等1 5 埽0 用半边折叠的方法简化网格，并 1 0 山东大学硕士学位论文 引进球面调和映射。在此基础上，周昆等也提出了基于二次误差【1 6 1 的边折叠累进 球面参数化算法 1 7 - 1 8 】，并且把s a n d e r 的几何变形度量从平面域推广到了球面域， 用它来做全局优化。这类算法都是基于网格简化的思想，简化时选择顶点删除或 者边折叠是次要的，关键在于从粗网格到精细网格( c o a r s e t o - f i n e ) 过程中如 何附加在简化过程中被删除的顶点。累进参数化的方法与其他参数化方法相比的 最大优点就是可以快速地处理复杂网格，运算速度非常快。 2 4 3 保角参数化方法 可展曲面( 高斯曲率为o ) 可以找到它到平面的等测度变换使得参数化变形 为0 ，这是最理想的，而一般的网格总是存在变形的问题。由于保角性质使得参 数化在理论上保证局部不变形，保角映射理论在三角网格参数化的应用成为当前 参数化研究的热点之一。g u 等证明了对于零亏格的封闭曲面，调和映射和保角映 射是等价的。因此，调和映射能量和d i r i c h l e t 能量是一种准保角映射啪1 ，l e v y 等提出基于c a u c h y - r i e m a n n 等式的最小二乘逼近准保角映射的参数化方法m 】， 可以处理复杂边界的三角网格。其他球面域的方法，例如w a n g 等扩展调和映射到 球面上，通过最小化调和能量得到球面参数化，并应用到医学大脑核磁共振( 皿i ) 处理上2 。h u r d a l 等2 2 1 和s t e p h e n s o n 2 3 1 用圆填充( c i r c l e p a c k i n g ) 方法来逼 近包括保角映射在内的常规解析函数，同样给出一个准保角的参数化映射。 a n g e n e n t 等通过线性逼近l a p l a c e - b e l t r a m i 算子把与球面同胚拓扑的三角网格 参数化到球面，则是一个整体保角映射方法乜们。h a k e r 等也提出了一种类似的球 面上保角逼近映射乜副，理论上通过删除曲面上的一点可以调和映射到一个无限 伸展的平面上，最后把无限平面用立体投影的方法映射到球面。由微分几何理论 可知，任何r 3 上c 1 曲面都存在保角映射可将它映射到r 2 的固定区域。网格实际上 是一种分段的c 1 曲面，而在c 1 上的双射不一定保证分段c 1 上的性质。 s h e f f e r 【2 6 】等提出了一个强壮球面参数化方法，它实质上是平面a b f 方法在 球面的拓展。由于需要求解一个带约束的非线性系统，对于复杂网格和大型网格 的运算时间都是很长的，因此该方法比较适合对简单网格的球面参数化。上述方 法对复杂网格的参数化都不如累进球面参数化方法运算快。 山东大学硕士学位论文 第三章对基于局部切空间排列的网格参数化方法的改进 陈中贵乜 等利用非线性降维方法局部切空间排列( l o c a lt a n g e n ts p a c e a l i g n m e n t ，简称l t s a ) ，给出了一个新的几何扭曲尽量小的网格参数化方法。 和以往的凸组合方法不同，该方法在每个顶点的1 邻域展开的平面上建立一个局 部坐标系，项点的局部几何结构由局部参数坐标完全决定。通过全局排列这些 局部坐标系，求得网格的整体最优的平面参数坐标。这种方法不需要事先给定参 数化网格的边界，能够处理带多条边界的网格。该方法在局部展平时，采用了局 部保角和保边长的方式。下面我们首先介绍一下改进的局部展平的两种方法，然 后在这个基础上进行全局排列。 3 1 局部展平中用到的基本结构 给定一个三角网格m ，其顶点集合为v = p i ) ，边集合e = g o ，三角形集 合为t = ，对每一个顶点忍，为了在这一部分介绍的方便性，我们用 只= 只，既，玖，巩 表示a 的卜r i n g 域邻点，其中包括只本身。把只既叫做轮 长，龟只叫做中心角，瓴忍叫做中心三角形，多边形 & ，段，既) 叫做 卜r i n g 的边界。把只映射到平面上的方法很多，即把只映射到q ，把只映射到 吼( q i ，q 。为平面上的点) ，如图3 1 所示。下面我们具体介绍- - t n 种展平方 式。 图3 1 顶点b 的1 - r i n g 域展平 山东大学硕士学位论文 3 1 1 保持中心角和边界长度不变 在这种展平方式里，目标是保持只周围的中心角，以及只卜r i n g 的边界长 度尽量不变。首先，使展平之后的中心角与原来的角度保持一个相同的比例因子， 即 么( 毛，仍，) = 2 u l ( p , , ，p i ，以。) 么( 乃，a ，巩h ) ( 3 1 ) 同时，尽量使得 q 我们知道，仅有一个角和一条三角形的对 边不足以完全确定这个三角形。所以，在这里引入两个角度，即( 这里下标均对 k 取模) 哆2 一2 ) 碰， ， 。) “蔷么( 乃，吼，以，) + 丢么( 易，巧) ) 色= 一2 ) 碰( 只，p j , 。，r ) ( 么( 只，吼，邑。) + 么( 只，吼) ) ( 3 2 ) 通常哆+ 辟+ 么g f 劬+ 。万所以，这里的目标是使么( 够，瓯，毛。) 逼近于吁， 么( 吼，气) 逼近于局。 通过么( 气，吼，气。) ，劬劬+ t 以及么( g f ，吒，毛。) 我们可以完全确定包缈，也 就可以得到这个三角形的两条轮长。同理，根据么( 毛，q i ，吼+ ) ，田。以及 么( g f ，) 可以得到两条轮长的另一组解。即一条边g j 毛在一个三角形中会得 到两个值，在b 是内点的情况下，每条边g j 毛存在于两个三角形中，把得到的四 组解加权平均，就可以得到该条边的最终长度。 当然，在这里有可能出现的一种情况是，局+ 么毛绣“万，或者 哆+ 么劬g j 劬+ 。万，这里的处理方式是保持么毋g f 劬+ l 不变，辟或者吩尽量的大。 对于边界点的l - r i n g 展平，采取与陈相同的方式：即保持中心角和轮长不 变。有了只忍展平之后的长度，就可以对办进行局部展平：令缈= ( 0 ，0 ) ， g f ，= ( | g i 岛。i ，o ) ，然后利用各边之间的夹角及边长，依次获得g i ：，吼。 山东大学硕+ 学位论文 3 1 2 保持中心角和中心三角形面积不变 首先，仍然使两相邻边之间的角度保持一个相同的比例因子，即 七 趣，呸，) = 抚妃，眉，吼) 翘，露，吼) 芦 同时保持各个三角形的面积不变。我们知道，三角形的面积公式为 s = l i b s i n 2 ， 其中，口，厶为两条边的长度，口为两边之间的夹角。当有一个角度确定了之 后，只要确定与这个角相邻的两条边，就可以唯一的确定这个三角形。 假设只与卜r i n g 域邻点间的边长为0 ，j = l ，k ，两相邻边之间的角度分别 为哆，j = l ，k 。映射之后，吼与卜r i n g 域邻点间的边长为乃，j = l ，k ，两相邻 边之间的角度分别为房，j = 1 ，k 。要保持相应的面积相等，即 氓n s i n 2 , = y j y h s i n , b ，j = 、，k 其中+ 。= y i ，k l = 。现在的目标便是求乃，歹= 1 ，k 。 ( 3 2 ) 当a 点的度为奇数时候，即k ：2 d + 1 ，可以得到 丝! 竺鱼型! ! 坐堡奉! = 五= ! ! 墨堕= 2 ：丝羔21 竺垒丝些! 坐垒丝= 2 丝= ! ! 坚丛= 2 f 2 ，3s i n 4 s l n 口4i k i l ks i l l 一l儿乃s i l l 岛y 4 弘s m ：4 从一l 儿s i l l 版一l ( 3 3 ) 即生水争墅旦盟：丛串争些坚k( 3 4 ) 厶备s i n a 2 m 儿訇s i n 屈m 而乇7 ls i n g e = 儿咒s i n 屈，所以由这两个方程可以得至l j y i ，儿，利用方程( 3 2 ) 便可以得到所有的参数域内的边长。 当以点的度为偶数时候，推导发现利用上面的方法得不到解，这时候可以首 先确定一条边长，最简单的做法是直接取轮长的平均值，之后便可以利用方程 ( 3 2 ) 得到其他的边长。 得到了保持面积的各边长度以及任意两边之间的角度之后，就可以做局部面 片的投影了。令吼= ( o ，0 ) ，吼。= ( m ，0 ) ，然后利用各边之间的夹角及边长，依次 1 4 山东大学硕士学位论文 曼皇曼篡量皇曼曼曼曼曼曼曼曼曼曼曼毫曼曼曼曼曼曼量曼曼曼曼曼皇曼曼ml _ m 皇皇曼曼皇曼量皇曼曼皇曼兽皇曼曼曼曼曼篡皇 获得绣2 ，缸。 3 2 全局排列 现在，对于每一个局部面片只，我们得到了它的局部展平区域q ，然后利 用全局排列的方法来得到整体的参数域坐标