（计算数学专业论文）基于曲面重构的三角网格参数化方法比较.pdf

大连理工大学硕士学位论文 摘要 三角网格参数化有着广泛的应用背景，是计算机图形学、计算机辅助几何设计和数 字几何处理等领域中研究的重要问题之一。三角网格参数化技术也成为近年来几何造型 的研究热点，很多学者提出了不同的参数化方法。因此，衡量各种参数化方法好坏也变 得至关的重要。视觉上的平滑效果好坏是衡量参数化好坏的直观标准，但很多参数化方 法的结果直观上看起来效果很相似，无法直接判断其好坏，因此要通过某种标准来衡量 各种参数化方法的好坏。本文以此为背景，提出一种基于曲面重构的比较参数化方法好 坏的方法。 主要内容如下：首先介绍和分析了几种经典的三角网格参数化方法，然后对不同参 数化方法得到的参数域网格，分别用两种曲面重构方法对其进行曲面重构，得到不同的 重构曲面，对每种重构方法得到的结果定义了相应的误差标准来衡量重构曲面的好坏， 并且通过实验证明重构曲面的好坏也衡量了相应的参数化方法的好坏。其中第一种方法 是基于微分坐标与l a p l a e i a n 矩阵的关系，通过空间三角网格的几何信息与参数域网格 的参数信息来进行曲面重构，得到一个c o 连续的网格曲面。然后通过比较原始网格与重 构曲面之间的顶点相对位置平均偏差和面积平均相对偏差来衡量参数化方法的好坏。另 外一种方法是通过对空间三角网格顶点进行c l o u g h t o e h e r ( c t ) 插值得到一个c 1 连续 的参数曲面。然后通过比较原始网格曲面与重构曲面之间的平均h a u s o d r f f 距离来衡量 参数化方法的好坏。最后用人脸网格和鼻子网格进行了数值试验，实现了几种经典的参 数化方法，并且对这几种参数化方法得到的参数化结果进行了c o 的曲面重构，分析了原 始网格与重构网格之间的误差。实验结果表明，h a r m o n i c 参数化方法和基于能量优化参 数化方法在c o 重构方法有较好的重构结果，而u n i f o r m 参数化方法重构结果最差。 关键词：参数曲面；曲面重构；参数化；微分坐标；三角网格 基于曲面重构的三角网格参数化方法比较 t h ec o m p a r i s o no ft r i a n g u l a rm e s hp a r a m e t e r i z a t i o nm e t h o d sb a s e d o ns u r f a c er e c o n s t r u c t i o n 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 di n c o m p u t e rg r a p h i c s ，c a g da n dd i g i t a l g e o m e t r yp r o c e s s i n g p a r a r n e t e r i z a t i o no ft r i a g u l a rm e s h e sb e c o m e sah o tr e s e a r c ht o p i ci n g e o m e t r ym o d e l i n gr e s e n t l y ，m a n yr e s e a r c h e r sp r e s e n td i f f e r e n tm e t h o d s s oe v a l u a t et h e e f f e c to ft h ed i f f e r e n tp a r a m e t e r i z a t i o nm e t h o d si sv e r yi m p o r t a n t v i s u a lq u a l i t yo ft h em e s h i st h ei n t u i t i v ec r i t e r i o no fm e a s u r i n gt h ee f f e c to f 也ep a r a m e t e r i z a t i o n b u tm a n yr e s u l t so f d i f f e r e n tm e t h o d si ss i m i l a rw i t ho t h e r s ，a n dc a n tn o tm e a s u r et h ee f f e c td i r e c t l y ，s ow em u s t d e f i n es o m ec r i t e r i o nt om e a s u r et h ee f f e c to ft h ep a r a r n e t e r i z a t i o nm e t h o d s f o rt h i s b a c k g r o u n d ，t h i sp a p e rp r e s e n t sam e t h o dt om e a s u r et h ee f f e c to ft h ep a r a m e t e r i z a t i o n m e t h a d so ft r i a n g u l a rm e s h e sb a s e do ns u r f a c er e c o n s t r u c t i o n 1 1 1 em a i nw o r ko ft h i s p a p e r a r ea sf o l l o w s ：f i r s t a n a l y s i s s e v e r a lc l a s s i c a l p a r a m e t e r i z a t i o nm e t h o d so ft r i a n g u l a r m e s h e s f o rd i f f e r e n tm e s h e so nt h e p l a n n a r f i e l d ，r e c o n s t r u c t e dt h es u r f a c eb yt w om e t h o d s ，a n df o rt h ed i f f e r e n ts u r f a c eb yt h et w o r e c o n s t r u c tm e t h o d s ，d e f i n ed i f f e r e n ts t a n d a r dt om e a s u r et h ee f f e c to ft h er e c o n s t r u c t e d s u r f a c e a n dt h ee f f e c to ft h er e c o n s t r u c t e ds u r f a c em e a s l l r e 也ee f f e c to ft h ep a m m e t e f i z a t i o n m e s h o d s n ef i r s tr e c o n s t r u c tm e t h o di sb a s e do nt h er e l a t i o n s h i po ft h ed i f f e r e n tc o o r d i n a t e s a n dl a p l a c i a nm a t r i k l l s i i 培t h e g e o m e t r yi n f o r m a t i o n o ft h et r i a n g u l a rm e s ha n dt h e p a r a m e t e ri n f o r m a t i o no ft h ep a r a m e t r i cf i e l dt or e c o n s t r u c tac ”e o n t i n n o u ss u r f a c e a n d e v a l b a t et h ee f f e c to ft h em e t h o d sb yt h ea v e r a g ed e v i m i o no ft h ep o i n ta n da r e ab e t w e e nt h e p r i m i t i v em e s ha n dt h er e c o n t r u s t e ds u r f a c e a n o t h e rm e t h o di si n t e r p o l a t i n gt h ev e r t i c e so f t h et r i a n g u l a rm e s hb yc l o u g h t o c h e r ( c t ) m e t h o d , a n dt h i ss u r f a c ei sac 1c o n t i n n o u s s u r f a c e 。a n de v a l u a t et h ee f f e c to ft h em e t h a d sb yt h ea v e r a g eh a u s d o r f fd i s t a n to na v e r a g e t r i a n g u l a rp a t c hb e t w e e nt h ep r i m i t i v em e s ha n dt h er e c o n t r u s t e ds u r f a c e t h ee f f e c to ft h e r e c o n s t r u c tr e s u l tr e f l e c tt h ee f f e c to ft h ep a r a m e t e r i z a t i o nm e t h o d s f i n a l l yl i s ef a c em e s ha n d l l o s em e s hi m p l e m e n tt h ep a r a m e t e r i z a t i o nm e t h o d sa b o v ea n dt h er e c o n s t r u c ts u r f a c eo ft h e c um e t h o d , 也ee x p e r i m e n tr e s u l t sd e m o n s t r a t et h a t , t h eh a r m o n i cm e t h o da n dt h ee n e r g y o p t i m i z i n gp a r a m e t e r i z a t i o nm e t h o da r eb e t t e rt h a no t h e r s ，a n dt h eu n i f o r mm e t h o di st h e w o r s t k e yw o r d s ：p a r a m e t r i cs u r f a c e ；s u r f a c er e c o n s t r u c t i o n ：p a r a m e t e r i z a t i o n ； d i f f e r e n t i a lc o o r d i n a t e s ；t r i a n g u l a rm e s h i i 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目： 作者签名： 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目： 作者签名： 导师签名： f 国择蠢謦f 呖以的硷 日期：盈益年月堑日 日期上乒年上月兰日 大连理工大学硕士学位论文 1 绪论 三维几何作为一种新的数据媒体近1 0 年来在工业界得到了广泛应用，这一趋势推 动了学术界对数字几何处理( d g p ：d i g i t a lg e o m e t r yp r o c e s s i n g ) 的研究。顾名思义， 数字几何处理即用计算机对三维几何数据进行处理，主要指三维网格的化简、压缩、细 分、优化等，这门从9 0 年代中后期发展起来的学科属于计算机图形学和数字信号处理 的交叉学科。尽管近几年这一方向的研究取得了激动人心的进展，但与大家熟悉的数字 图像处理和数处理等处理传统媒体的学科相比，数字几何处理还显得非常年轻。正如一 些学者指出的那样，数字几何处理还是计算机图形学研究领域的一个公开问题。 随着现代网络技术的不断发展，以三角网格模型为代表的三维几何模型数据成为继 声音、图像、视频之后的第四代多媒体数据类型。三角网格通常是由3 d 扫描仪获取复 杂表面采样点的几何信息，并通过拓扑重建得到。三角网格模型具有一下优点： f 1 ) 形状简单，便于计算和处理。 ( 2 ) 用三角形网格可以表示复杂拓扑形体，而且可以任意精度的逼近物体曲面。 ( 3 ) 三角网格绘制算法成熟，可硬件加速。 鉴于这些优点，空间实体的三角网格表示成为表示复杂3 d 几何模型形状的主流方 法之一。 1 1三角网格曲面参数化技术与应用 三角网格曲面的参数化是指参数区域与3 d 网格曲面间的一一映射关系。参数区域可 以是平面区域、球面或多面体等。对于参数域为平面的三角网格参数化可归结为这样一 个问题：给定一个由空间点集z ；r 3 组成的三角网格曲面s 和一个二维参数域尸，寻求 一个在参数域上的点尸到工，s 的一一映射，如图1 1 所示，使得参数域上的网格 与原始网格拓扑同构，并在保证参数域上所有三角片之间不相互重叠的同时，谋求某种 与原始网格之间几何度量的变形最小化。这样的一一对应映射可以将一些三维网格曲面 的操作转换成对平面网格的操作，减小操作的复杂度【1 1 。 作为现在主流的复杂形状表面三维模型表示方法之一，三角网格通常是用3 d 扫描 仪、三坐标测量机或光学测量仪等获取复杂表面采样点的几何信息，并通过拓扑重建得 到。三角网格的参数化是对这些三角网格的几何和拓扑信息作进一步处理的基础，它在计 算机图形学、计算机辅助几何设计和数字几何处理等方面有着广泛的应用。比如，纹理 映射【2 0 】利用表面网格参数化信息，把一幅纹理图像映射三维网格上，使得表面网格看 上去更加生动逼真；曲面拟合通过参数化把离散的三维数据点用一个光顺的参数曲面来 基于曲面重构的三角网格参数化方法比较 拟台m 1 ；重新网格化( r c i n e s h i g ) 则利用参数化把三角化曲面转化成具有细分连通性的 规则网格n 8 i ，在此基础上进一步做多分辨率分析m 0 1 ；还有很多数字几何处理，如交互 式三维绘画、三维网格编辑、格m o r p h i n g 旧“培都需要事先把网格参数化到一个 容易交互式处理的参数域”i 。 禽 j 一 、 一一 ：= 图11 三维网格和二维网格的对应 f i g 】j t h ee o n e s p o n d i n g o f 3 d a n d 2 d m e s h 1 2 参数化的研究现状 从数学角度来看，满足这种参数化的函数有很多。寻找这样的函数并不是一件很难 的事情，问题在于如何在这么多映射中找到一个相对比较“好”的映射? 人们通常使用 一些几何的内在属性f 如长度、角度和面积等) 的变形程度来衡量参数化的好坏。事实上， 由于网格曲面的复杂性，人们对是否存在最优的参数化方法的答案还是未知的。早在2 0 世纪6 0 年代研究人员就开始研究三角网格参数化问题，直到9 0 年代，该问题才得到深 入而广泛的研究，并发表了很多关于参数化的文献这些技术都是为了解决一个内在几何 变量的变形最小化问题i s t o r t i o nm i n i m i z a t i o n ) 。通常，可利用微分几何、弹性理论、等 积映射、调和映射、保角映射和等测度映射等理论来对变形最小化问题建模，并应用有 限元分折以及数值分析等物理数学工具来求解变形最小化问题【”。 但是将一个不可展的3 d 网格陆面映射成一个平面的三角化不可避免的要产生长 度、面积、角度上的扭曲变形。网格的参数化就是试图保持这样的几何度量。许多研究 人员采用不同的方法着力于减少参数化造成的扭曲。 m a i l o t 等 3 1 提出了一种基于弹性变形能量的度量，将在平面上参数点的第一基本形 式矩阵和2 2 的恒等矩阵的差的范数作为变形能量的被积分泛函，然后求解一个非线 性的能量极小问题。田于他们的方法是求解一个全局的连续映射函数。这样会使得复杂 物体的纹理变形很大。为此他们把地图中板块分割的思想引入网格，试图通过将整个网 大连理工大学硕士学位论文 格分割成几个小的网格片，并分别对它们进行参数化。但是这样的切割会导致分割线过 多而且很长，从而导致分割处较长的参数不连续，并且他们的分割方法需要人工交互来 完成，并不方便实现。任何同胚于圆盘的网格与平面上的一个凸区域间必然存在着调和 映射。e c k 等【9 】通过使该映射的d m c h l e t m p 量最小，而构造了一个对非线性调和映射的线 性逼近。沿着凸区域边界固定好边界点后，他们只需求解一个最, b - 乘问题，便可获得 所有内点的参数化。该调和映射的d i r i c m e t 能量被视为全局扭曲的度量。然而，他们的 权重并不能够保证都是正值，负的权重可能导致某些三角形的翻转( 无效的三角化) ，因 为这样的映射不是一一映射。 早在1 9 6 0 年t u t t e 就提出了凸组合方法1 1 5 】，其基本思想是把网格的边界映射到一个 平面上的凸多边形，而内点取以它为中心点的1 一r i n g 的平均值。t u a e i a 正明了该方法所 得到的三角形不会相互重叠，但这种基于图论给出嵌, n 匿 ( o r a p he m b e d d i n g ) 的方法没有 充分考虑到原始网格的几何信息，使得参数化结果的变形较大。在t u a e 的基础上， f l o a t e r 1 6 】通过给每条边附加一个与边长相关的权值改进了凸组合方法，提出了具有保形 的凸线性组合参数化。他证明了所得到的参数化结果在增加一些约束后便是一一对应 的。他的参数化方法需要通过b i c g s t a b ( b i c o n j u g a t eg r a d i e n ts t a b i l i z e d ) 求解一个稀疏 的线性方程组系统，并且他证明了该数值解也是稳定的。与调和映射的方法相似，它也 需要预先给定边界的参数值。 f l o a t e r 将保形凸组合网格参数化方法扩展到非网格( m e s h l e s s ) l 约点集参数化上，进行 三维离散数据点重建及曲面拟合【5 , 1 7 】。l e e 等结合虚拟边界把凸组合方法拓展到非凸边界 的平面参数化处理f 1 8 】。f l o a t e r 还提出了一种均值坐标( m e a nv a l u ec o o r d i n a t e s ) 1 1 9 】，并 试图建立均值坐标与调和映射间的联系。文献【1 8 】利用均值定理，给出了将星形多边形 内的任何一点表示成它邻域点的凸线性组合的公式。f l o a t e r 说明了利用均值权重所取得 的参数化效果至少可以和保形参数化的效果一样，并且均值权重更容易求得。 h o r r n a n n 等【2 0 】提出了一个全局的非线性具有自由边界的m i p s ( m o s ti s o m e t r i c p a r a m e t e r i z a t i o n s ) 方法。实际上，他们是通过让约束的边界点成为自由边界来优化参数 化的。他们提出了一种在平移、旋转、缩放变换下均为恒量的度量，并选取保形参数 化作为初始的参数化，迭代优化该度量至最小。虽然可以取得较好的参数化，但是他的 非线性能量的度量需要解非线性的优化问题，因而这一过程十分耗时。 d e s b r u n 等【2 1 】提出了一个保面积和保角度两者线性混合的度量，他提供了一个参数 来平衡两因素对最终扭曲产生的影响，然后最小化线性混合的扭曲能量函数。s a n d e r 等 【2 2 】和p r a t m 等【2 3 】引入了参数化拉伸的度量l 2 和l 。，并从均匀的边弹力为初始条件开始， 优化迭代。另外，b e r m i s 等提出基于微分几何的方法1 2 4 1 ，通过把曲面的等参数曲线映射 基于曲面重构的三角网格参数化方法比较 到参数域完成参数化，并保持测地曲率( g e o d e t i cc u r v a t u r e ) 不变。s h e f f e r - - 等t 2 5 】提出了一个 复合的纹理映射的概念。该方法首先利用带有权重的l a p l a c i a n 光顺算子作用于平面的均 匀网格，得到从平面区域到自身的一个映射，该映射具有较小的边长扭曲。然后利用 a b f ( a n g l e b a s e df l a t t e n i n g ) 将3 d 网格嵌入到平面区域得到参数化。最终的复合纹理映 射就是由所得的参数化和平面到自身的映射复合而成。虽然a b f 方法无需设定边界，并 且在纹理映射时都取得了比凸组合和调和映射更好的结果，但是用l a g r a n g e 乘子法求解 非线性系统代价是很高的，且a b f 方法不能解决多边界问题。 另一个减少扭曲的方法就是将整个模型切割成一个具有最短路径并且同胚于圆盘 的新模型。s h e f f e r f 2 6 】利用她定义的区域扭曲给网格上的每一顶点设立一个代价权重，并 选取具有较大的区域扭曲的顶点作为m s t ( m i n i m a ls t e i n e rt r e e ) 的候选顶点，最后由候 选顶点集生成m s t 。它的切割路径实际上是3 d 图的一个子树，但是因为候选顶点在网 格上分布较广，必然导致分割线过长，从而导致分割处产生参数不连续【1 1 。 1 3 论文选题依据和研究内容 三角网格参数化是图论、微分几何、计算机图形学、计算机辅助几何设计、数字几 何处理、算法设计以及程序设计等众多学科的研究领域。目前，有很多研究机构在做这方 面的工作，其中包括微软亚洲研究院、浙江大学c a d & c g 国家重点实验室、南航 c a d c a m 实验室、美国的哈佛大学及以色列科技大学等。参数化本身是一个很古老的 问题，人们最早把这种技术应用在测地学、绘图学等领域，随着计算机的飞速发展和多 媒体娱乐应用的推动，它在计算机图形学领域拥有举足轻重的地位，并且成为近几年来 国际学术界一个热点研究问题。 尽管已经出现了不少离散曲面的参数化方法，但是每种方法都有各自的优缺点，因 此各种参数化方法好坏的衡量也变得至关的重要。视觉上的平滑效果好坏是衡量参数化 变形好坏的直观标准，另外两种衡量参数化变形最常用的标准是比较参数域网格与原始 网格的面积相对误差和角度相对误差等误差测度，以及基于几何变形空间度量的方法来 衡量参数化方法的好坏，但这两种方法都是基于参数域网格和原始网格之间的比较。 本文基于曲面重构，提出一种衡量三角网格参数化方法好坏的方法。对于参数化后 得到的不同的参数域三角网格，分别用c o 和c 1 的参数曲面对其进行曲面重构，得到不 同的重构曲面。通过比较重构曲面与原始网格曲面之间的误差好坏来衡量参数化方法的 好坏。 大连理工大学硕士学位论文 1 4 论文的组织结构 本文第二章开始首先介绍一些与三角网格参数化相关的基础知识，这些内容都是后 面进行讨论的基础； 第三章介绍文中将要比较的几种经典的三角网格参数化方法算法，并分析了各自的 优缺点； 第四章主要介绍了用c o 和c 1 的参数曲面进行曲面重构的具体算法，并且对不同的 重构方法提出了相应的衡量参数化方法的好坏的标准，最后还通过数值实验得出了几种 经典参数化方法在此重构意义下的重构结果； 第五章总结全文。 一b 一 大连理工大学硕士学位论文 2 三角网格参数化的基础知识 为了便于理解，本章主要介绍一些与三角网格参数化相关的基础知识，如三角网格、 参数化的定义，参数化的变形，参数化的分类以及参数化的应用等。 2 1 图、三角网格和参数化 一般地，将一个三角网格曲面( 简称三角网格) 表示为单连通图的形式：s = s ( g ，x ) ， 其中x = = ( _ ，y i ，毛) ，江l ，n 为网格顶点的几何位置，g = ( v ，e ，f ) 为单联通的三 角平面图。对于一个三角网格曲面，如果忽略其网格顶点的几何位置信息，只考虑它们 之间的拓扑关系，就得到一种抽象的三角网格，称之为单连通的三角平面图。事实上， 单连通的三角平面图是一个单纯复形。为给出三角网格的精确定义，首先引入单纯复形 的概念f 2 7 】。 定义2 1 设集合矿为 l ，2 ，) ，其中为顶点数，记 ( f ，j ) ：v i ，j 乃为y 0v ， ( f ，j ，k ) ：v i ，j ，k v ) 为v o v q v ，则单纯复形是满足条件( 1 ) 一( 3 ) 的三元组g = ( v ，e ，f ) ， 这里，集合矿中的元素称为顶点：e ( ec ( f ，j ) y 0 乃) 中的元素称为边； f ( f c 矿圆v 0 矿) 中的元素为三角面。 ( 1 ) f 中每个面的所有边属于e ； ( 2 )e 中每条边一定属于某个面； ( 3 )v 中每个顶点一定属于某条边。 而三角网格曲面定义为： 定义2 1 2 一个三角网格曲面s = s ( g ，x ) 是一个单连通的三角平面图g = ( v ，e ，f ) 在r 3 空间中的嵌入，并且满足 ( 1 ) v = f ：1 ，册中顶点在尺3 中的几何位置为x = 包= ( 薯，y i ，刁) ，净1 ，奶； ( 2 ) e 中每条边均为直线； ( 3 ) f 中的每个三角面均为三角形。 本文主要考虑三角网格曲面在平面区域上的参数化，下面给出它的具体定义。 定义2 3 对于任意三角网格曲面s = s ( c ，x ) ，户= 尸( g 1 ，扩) 为一平面三角网格， 其中u = u i = ( 甜，) ，净l ，2 ，册为平面节点集。若图g 1 与图g 同构，则称尸为s 的参 数化。 基于曲面重构的三角网格参数化方法比较 z 图2 1图、三角网格和参数化 f i g 2 i ag r a p h ，at r i a n g u l a rm e s h ，a n dp a r a m e t e r i z a t i o n n 2 2 参数化的有效性 三角网格的参数化首先要满足有效性的要求，有效性的充分必要条件是：原始 三角网格和参数化三角网格的顶点、边、面分别是一一对应关系，并且对应的边连接对 应的顶点，对应的面连接对应的顶点和边，两个网格的边界顶点序列按逆时针方向一一 对应。如图2 2 所示，u 是x 的有效参数点，而u 宰则不是。 图2 2 参数化的有效性 f i g 2 2v a l i d i t yo fp a r a m e t e r i z a t i o n 2 3 参数化的变形 对于一个参数化而言，除了要满足有效性的要求外，有时根据人们不同的需求和 目的，需满足一些内在几何度量f 如长度、角度和面积等) 变形最小的要求f 2 8 】。从数学上 来看，可展益面( 高斯曲率为o ) 可以找到它到平面的等距变换，这是最理想的。而将一 般的空间三角网格映射成一个平面三角网格有时不可避免地要产生一些扭曲变形现象。 因此扭曲变形的大小是衡量参数化方法好坏的标准。 视觉上的平滑效果好坏是衡量参数化变形的一个直观标准，但参数化的变形通常还 有以下两种最常用的定量标准： 大连理工大学硕士学位论文 ( 1 ) 用参数域网格与原始网格之间的面积相对误差和角度相对误差等误差测度来衡量 变形程度【2 9 】 d 捃= j f 彳( t )么( z ) 彳( 乃) 彳( t ) 7 ：，e s l e s = 如23 陪l 熹 2 1 ，e f ip l ，二，厶7 1 _ ( jl 式中：- ，为网格的三角形个数指标，么( i ) 是第歹个三角片的面积，以是第j 个三角 片中第稚= l ，2 ，3 ) 个角的角度，e 表示三角形的角盈( 参数域为球面时的情况) 。该误差测 度是一个整体变形度量，不体现网格的局部三角形变形。 ( 2 ) 基于几何变形度量的方法f 2 2 】 给定一三角片丁及其二维参数域坐标u 1 ，u 2 ，u 3 ，u ，= ( ，v ) ，相应的三维坐标为 五，j c 2 ，x 3 ，则唯一的仿射映射s ( u ) = s ( u ，v ) = z 为： s ( u ) = ( a ( u ，u 2 ，u 3 ) 五+ a ( u 1 ，u ，u 3 ) 而+ 么( u 1 ，u 2 ，u ) x o a ( u l ，u 2 ，u 3 ) 其中a ( a ，b ，c ) 代表三角形a b c 的面积。由于是仿射映射，因为对“，v 的偏微分也是常 量： 咒= o s l o u = ( x 1 ( v 2 一v 3 ) + x 2 ( v 3 一k ) + 玛( m - v 2 ) ) ( 2 a ) & = o s l a v = ( 五( 鸭一“2 ) + 恐( 一u 3 ) + x 3 ( u 2 - u 1 ) ) ( 2 a ) 其中a = a ( u f ，u 2 ，u 3 ) = ( ( 地一玛_ ) ( b b ) 一如一) ( 屹一) ) 2 ，雅可比行列式 ，】的 最大和最小奇异值分别为： r = l 2 ( ( 口十c ) + ( 口一c ) 2 + 4 b 2 ) 最大奇异值 7 = 1 2 ( 0 + c ) 一( 口一c ) 2 + 劬2 ) 最小奇异值 其中a = 邑，b = 鼠，c = s 鼠。奇异值r 和7 代表的是将参数域上单位长的一个 向量向网格曲面映射时获得的最大和最小长度，表现为最大和最小的局部拉伸情况。为 此，s a n d e r 定义了三角片丁的两个拉伸标准f 2 2 】： 广一r _ - 一 r ( ，) = ( 、( r 2 + y 2 ) 2 = ( 口+ c ) 2 ，r ( 丁) = f 基于曲面重构的三角网格参数化方法比较 相应的，r ( 丁) 为参数域中各方向上拉伸量的均方根，r ( n 则为最大拉伸量。如果 三角片丁为退化的三角片，则r ( ，) 和p ( n 为无穷大量，因为这是参数域中的面积么趋 于零。 对于整个网格曲面有： p ( s ) - ( r ( 硝( 互) 彳( z ) v7 ：e st , e s r ( s ) - m m a 。x l 。( t , ) 其中彳( z ) 是三角片z 在三维网格曲面中的面积。这种基于纹理扭曲程度的度量既 可以反映局部三角形又可以衡量整体网格参数化的变形，是一种更为普遍采用的度量方 法这种度量方法首先被应用于平面参数域，后来被推广到球面参数域上。 上述这两种衡量标准都是基于比较参数域网格与原始网格之间的误差来衡量参数 化方法好坏的，本文提出的衡量误差的标准是基于比较重构曲面与原始网格之间的误差 来衡量参数化好坏。重构曲面的好坏在一定程度上衡量了参数化方法的好坏，因此我们 用重构曲面与原始网格之间的误差来衡量。 2 4 参数化的分类 如今，三角网格的参数化已经出现了很多种不同的方法，同时也存在着不同的分类。 根据审视问题的角度不同，三角网格参数化方法基本上可以分为以下几类【3 0 】： ( 1 ) 根据参数域的不同可以分为平面参数化和球面参数化： ( 2 ) 根据网格的拓扑信息可以分为带边界网格参数化和封闭网格参数化，甚至任意拓 扑的三角网格参数化； ( 3 ) 考察不同的内在几何变形，可以分为保面积参数化、保角参数化和等距参数化； ( 4 ) 根据计算复杂度不同可以分为线性方法和非线性方法； ( 5 ) 局部参数化和整体参数化方法等。 本文后面主要介绍平面参数化领域的一些研究现状和线性的参数化方法，并且基于 曲面重构的思想，对带边界三角网格的平面参数化方法进行比较。 2 5 参数化的应用 随着计算机的飞速发展和多媒体技术的推动，三角网格的参数化在计算机图形学领 域已占据举足轻重的地位，并且成为近几年国际学术界一个前沿研究领域。参数化的应 用也是多方面的，比如纹理映射、网格变形、网格再划分、曲面匹配、曲面拟合、网格 修复等等，同样广泛地应用于计算机视觉，计算机动画等方面。 大连理工大学硕士学位论文 3 几种经典的参数化算法 给定空间三角网格曲面s ( g ，x ) ，其中g = y ，e ，x = x ，= ( x i ，y i ，z a 净l ，n 为 网格曲面上的点集，v = f ：江1 ，n ) 是点的序号的集合；e 是边的集合，对于任意两 点f ，j ，i j ，如果，是i 的邻近点，则( f ，j ) e 。令z 为点，的邻近点个数，定义参数 化网格曲面s ( g ，x ) 后得到的平面网格为p ( g ，u = u ，= ( 群，v ) ，f - l ，n ) 。 3 1 u nif o r m 参数化方法 u n i f o r m 参数化方法( 均匀参数化方法) 是t u t t e 在19 6 0 年提出的【1 5 1 。该方法主要是 基于凸组合的思想而得到的，因此也称为凸组合方法。 其基本思想是把网格的边界映射到一个平面上的凸多边形上，所有的内部点成为其 一环邻近点的凸组合，其权值取以它为中心点的一环的平均值： ， 1 a , ( f ，歹) e 7 i o ( f ，) 仨e 然后求解线性方程组 卫 = 五，“，f = 1 ，l 尸1 考虑到敞的两个参数“和v ，要解两个线性方程组a u = b , a v = 6 ，t u t t e 证明了该方法所 得到的三角形不会相互重叠，但这种基于图论给出嵌入图( g r a p he m b e d d i n g ) 的方法没 有充分考虑到原始网格的几何信息，使得参数化结果的变形较大。 3 2 s h a p ep r e s e r v e 参数化方法 s h a p ep r e s e r v e 参数化方法【1 6 】是f l o a t e r 在1 9 9 7 年在t u t t e 的基础上根据凸组合的思想 提出的一种方法，该方法也称为保形参数化方法。 假设，砭，为三角网格模型的内部点，h ，靠2 ，h 为边界点。该方法的具体 算法步骤如下： ( 1 ) 对边界点按逆时针方向弦长参数化到正方形上，参数化得到工一，靠：，h ， 作为后来解线性方程组的已知条件。 ( 2 ) 对每个内部点f ，计算权值五 基于曲面重构的三角网格参数化方法比较 乃= 乃，。 乃 3 ，这时对每个由三个邻近点所组成的三角形，如果它包含 点p 在内，则按= 3 的情况计算一次权值，如图2 1 ( c ) 所示。全部计算完毕后，将 每个邻近点在整个计算过程中的所有权值平均后得到最终该邻近点的权值一，。 ( 3 ) 每个内部点都是其邻近点的凸组合： 大连理工大学硕士学位论文 = 矗朋u ji = 1 ，胡 最后解方程组同u n i f o r m 方法类似，如果在计算过程中取五，= 1 4 ，( f ，j ) ee ，则为t u t t e 的均匀参数化方法。f l o a t e r 也证明了所得到的参数化结果在增加一些约束后便是一一对 应的，上述得到的线性方程组系统可以通过b i c g s t a b ( b i c o n j u g a t eg r a d i e n ts t a b i l i z e d ) 求解，并且他证明了该数值解也是稳定的。 3 3m e a n v alu e 参数化方法 m e a nv a l u e 参数化方法【1 9 】是f l o a t e r 在2 0 0 2 年提出的，该方法也是基于凸组合的思 想，其权值是根据调和函数的中值定理诱导得到出的，因此该方法也称为中值坐标参数 化方法。 其权值丑，如下： 屯2 矗一堕嚣严 ) 图3 2m e a nv a l u e 权值对应的角度 f i g 3 2a n g l es u s e df o rm e a nv a l u ew e i g h t s 其中巧和吒如图3 2 所示，0 _ 一圳为顶点v 和_ 之间的距离。最后也通过求解线 性方程组得到参数化结果。利用均值权重所取得的参数化效果可以和保形参数化的效果 一样，并且均值权重更容易求得。 3 4h a r m o nic 参数化方法 h a r m o n i c 参数化方法【9 】是e c k 等1 9 9 5 年提出的，该方法又称调和映射方法。它是一 种典型的最小化能量方程的方法。最小化能量方程方法就是在于寻找一个能量方程，称 为目标函数，并且适当地给出该目标函数的边界条件，然后求解目标函数的极值得到一 个参数化结果。 基于曲面重构的三角网格参数化方法比较 h a r m o n i c 参数化方法的主要思想是将三角网格模型中的每条边均看作一个弹簧，先 将三角网格的边界映射到预先定义好的多边形上，然后通过最小化三角网格的弹性势能 来参数化内部空间点。该算法的具体步骤如下： ( 1 ) 选取三角网格模型s ( g ，x ) 上，7 个边界点而，恐，毛作为映射到平面域上的角 点，分别将这些焦点映射到一个平面，2 边形尸cr 2 的各顶点上。平面多边形尸的选取算 法是：将尸的i v 个顶点置于一个圆周上，并使两相邻定点所对的圆心角与网格曲面边界 上对应的两相邻角点所连的折线长度成正比。也可以更具需要直接将p 取为正方形、正 三角形或其它凸多边形等等。 ( 2 ) 将网格曲面s 看作一个弹簧系统，在边集e 中的每一条边上放置一根弹簧。 三维网格曲面s 上的顶点映射n - 维平面域p 上的变形能为【2 】： 邑册( “) = 去墨，1 1 , - j l l 2 ( 3 2 ) ( ，j ) e e 其中，u j 分别为边( f ，j ) 的两个顶点映射到尸中的位置，边界点的位置已经确定。 露，为边( f ，) 的弹性系数。为了尽可能反映初始网格s 中每个边的长度及相邻面的形状， 七i 取为： 乃2 ( 譬南+ 髟 一譬) 4 小岛+ ( 置如+ 髟2 如一譬) 4 小如 其中毛，k ：为边( f ，歹) 的两个相邻面的另外两个定点，厶。，表示边( f ，) 的长度，a t , j , k 表 示三角片( f ，k ) 的面积。砖，有可能会是一个小于零的负数，这就会导致参数化的不成 功，例如产生重叠的三角片。在这种情况下，七可以取为平均弹性系数。 ( 3 ) 采用拉格朗日乘子法解式( 3 2 ) ，使得邑册( 甜) 最小，得到网格曲面s 中所 有顶点映射到参数域p 中的坐标。 该方法映射后的所有顶点、边、面的连接关系保持不变，是一个基于变形能量最小 的分片线性映射，它同样需要先固定边界参数。 3 5ln t rin sic 参数化方法 i n t n n s i c 参数化方法【2 1 堤d e s b r u n 等在2 0 0 2 年提出的，该方法也是一种能量方程最 小化的方法。 该方法可以固定边界参数化也可以通过边界约束得到自然边界的参数化结果， d e s b r u n 等综合考虑了离散保角度参数化和离散保面积参数化这两种参数化方法，考虑 两种变形能：d i r i c h l e t 能量和c h i 能量。通过最小化这两种变形能得到参数化结果。 一环邻近点的d i r i c h l e t 能量表示为： 大连理工大学硕士学位论文 l = c o t a o u ，一“f ( 3 3 ) j e n ( i ) c h i 能量表示为： 乓= 等立笋( u 1 - - u j ) 2 ( 3 4 ) j e n ( 1 ) j 一一一i 其中n ( i ) 为a i 一环邻近点集合，k 一叶f 为边( f ，) 在平面域尸内的长度，f 五- - x j f 为三维网格曲面s l j 2 2 ( i ，歹) 的长度，口 孱为s 中边( f ，) 所在三角片中边( f ，) 不相邻的 角，岛为s 中边( f ，) 所在三角片中顶点为x ，的角，如图3 3 所示。 图3 3 三维一环邻近点及其相应的平面映射 f i g 3 3 3 d1 - r i n ga n di t sa s s o e i a t e af l a t t e n e dv e r s i o n 鼓小化d i r i c h l e t 就重得剑： 等2 ( ，萎( c o t + c o t f l , ) ( 圹o ( 3 5 ) 最小化c h i 能量得到： 等：咩( u i - - u j ) ：o ( 3 6 ) 艿“，箭，)k x r 、 式中各角度的定义如图3 3 所示，综合考虑这两种能量e = 五色+ 乓，建立线性方程： 柳= 心纠= c 二 = c 7 ， 五，为任意两个实数，可以简单的取为1 。c 为包含所有平面域尸