（计算数学专业论文）三角网格曲面的均匀面积参数化.pdf

大连理工大学硕士学位论文 摘要 三角形网格曲面参数化可以看做是该网格曲面和参数域之间的一个一一映射。近年 来，网格参数化的研究已经取得了一定的进展，出现了很多参数化方法。网格参数化的 理想目标是参数域中的网格和原始网格在拓扑上同构并且不存在任何变形。网格参数化 是计算机图形学的一个重要研究方向，它在纹理映射，网格重新化，c a d 模型的修复 及仿真等领域有着广泛的应用。 由于在计算机中，绝大部分三维网格模型都是不可展的，所以在参数化( 平面图嵌 入) 过程中，存在变形，并且这种变形是不可避免的，因此如何减少参数化过程中的变 形成了三角网格参数化最为关心的问题。此外，一个好的参数化方法除了能减少变形， 在处理大型的三角网格上也应该是有效的，并且计算上应具有鲁棒性。 本文在现有参数化方法的基础上，给出一种新的变形度量：在某一顶点邻域中，采 用相应点所对的面积与整个一环面积和的比值作为变形度量。基于这种变形度量提出了 一种均匀面积参数化，并将其应用到复杂三维形体的纹理映射均匀化中。 我们的方法是：首先通过均值坐标( m e a nv a l u ec o o r d i n a t e s ) 变换将复杂三维网格映 射到平面上；然后基于本文给出的变形度量进行均匀面积变换，就可使平面网格较均匀 地分布。求解其纹理坐标可实现采用单幅图像的纹理映射均匀化。通过典型三维模型的 实验和比较可以看到：采用文中方法所获得的纹理映射均匀化效果较现有的单一参数化 方法有显著改善，而且算法简单、快速、稳定。 关键词：三角网格；参数化；网格变形；纹理映射；均匀面积映射 均匀面积参数化 u n i f o r ma r e ap a r a m e t e r i z a t i o no ft r i a n g u l a t e ds u r f a c em e s h e s 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 nc a l lb ev i e w e da sao n e - t o - o n em a p p i n gf r o mt h es u r f a c et oa s u i t a b l ed o m a i n r e c e n t l y t h e r ea r el o t so fp r o g r e s s e si nt h e3 dm e s hp a r a m e t e r i z a t i o n t h e i d e a lt r i a n g l em e s hp a r a m e t e d z a t i o nt e c h n o l o g yi st h a tt h em e s ho ft h ep a r a m e t e rd o m a i n s h o u l db et o p o l o g i c a l l ye q u i v a l e n tt ot h eo r i g i n a l3 dm e s ha n dw i t h o u ta n yd i s t o r t i o n ( i n c l u d i n gt h ea r e a , a n g l ea n dl e n g t hd i s t o r t i o n ) m e s hp a r a m e t e r i z a t i o ni sac e n t r a li s s u ei n c o m p u t e rg r a p h i c s i th a sm a n ya p p l i c a t i o n s s u c ha st e x t u r em a p p i n g ，r e m e s h i n g ，a n d r e p a i r i n go fc a d m o d e l sa n ds i m u l a t i o n i nc o m p u t e r ，m o s to ft h e3 dm o d e l sa l eu n d e v e l o p a b l e ，s ot h e r ee x i s t sd i s t o r t i o ni nt h e p r o c e s s i n g o fp a r a m e t e r i z a t i o n ( p l a n a re m b e d d i n g ) ，a n dw h i c hi si n e v i t a b l e n l em a i n c o n c e r no fs u r f a c ep a r a m e t e r i z a t i o nm e t h o d si st h er e d u c t i o no fp a r a m e t r i cd i s t o r t i o n b e s i d e s f r o mp r o v i d i n gal e a s t - d i s t o r t e dm a p p i n g ，ag o o dp a r a m e t e r i z a t i o nm e t h o ds h o u l db ee f f i c i e n t f o rp r o c e s s i n gl a r g es u r f a c em e s h e sa n dr o b u s t b a s e do na v a i l a b l ep a r a m e t e r i z a t i o nm e t h o d s an e wd i s t o r t i o nm e a s u r ei sp r o p o s e d ：i t u s e ss u c ham e a s u r ea st l l ed i s t o r t i o nm e a s u r e w h i c hi st h er a t i oo ft h ea r e ao fan e i g h b o r i n g v e r t e xc o r r e s p o n d i n gt oag i v e ni n n e rv e r t e xi nat r i a n g l em e s ha n dt h es u mo ft h eo n e - r i n g a r e a t h e nw eg i v eas o c a l l e du a m ( u n i f o r ma r e am a p p i n g ) b a s e do nt h i sd i s t o r t i o n m e a s u r e ，t h eu a mi su s e di nu n i f o r mt e x t u r em a p p i n go fc o m p l e x3 dm e s h e si nt h ee n d o u rs t e p sa r e ：f i r s t l ym e a nv a l u ec o o r d i n a t e sa r eu s e dt om a pa3 dm e s hi n t oas q u a r e ， a n dt h e nt h eu a m ，w h i c hi sb a s e do no u rp r o p o s e dd i s t o r t i o nm e a s u r e i su s e dt om a pt h e n o n u n i f o r l nm e s hs q u a r et oau n i f o r i l lm e s hs q u a r e a f t e rc a l c u l a t i n gt h et e x t u r ec o o r d i n a t e s i nt h eu n i f o r mm e s h , af a i r l yu n i f o r mt e x t u r em a p p i n gc a nt h e nb er e a l i z e df o rc o m p l e x3 d m e s h e st h a to n l yu s eo n et e x t u r ei m a g e e x p e r i m e n t sa n dc o m p a r i s o n sa r et a k e nw i t h r e p r e s e n t a t i v e3 dm e s h e s ，w h i c hr e v e a l st h a to u rm e t h o d sh a so b v i o u si m p r o v e m e n ti n u n i f o r mt e x t u r em a p p i n gt h a na v a i l a b l es i n g l ep a r a m e t e r i z a t i o nm e t h o d s 1 1 1 ea l g o r i t h mi s s i m p l e ，f a s ta n ds t a b l e k e yw o r d s ：t r i a n g l em e s h ；p a r a m e t e r i z a t i o n ；m e s hd i s t o r t i o n ；t e x t u r em a p p i n g ；u n i f o r m a r e am a p p m g i i 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：鱼王凰日期：熟塞：笸：q 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位 论文版权使用规定，同意大连理工大学保留并向国家有关部门或机构送 交学位论文的复印件和电子版，允许论文被查阅和譬阅。本人授权大连理 工大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也 可采用影印、缩印或扫描等复制手段保存和汇编学位论文。 作者签名： 鲍五凰 导师签名：之笾出导师签名：冬匕2 垄 二墨掣 2 煎年月j 卫日 夫连理t 大学硕十学忾论文 1 绪论 11三维网格曲面参数化技术与应用 随着数字化技术的进步和f 、泛应用r 维几何数据成为继卢音、图像和视频之后的 第四代多媒体数据类型。与文字、声菏、图像和视频等其他媒体相比，一维图形的真实 性干交互性更强，更符合人们的视觉刊侵，能给用户带来图像、视频等媒伴衍小具有的 沉浸式视觉体验。事实上，这几年兰维几何数据在影视工业、游戏工业和制造工业的广 泛使川已经验证了返一点。目11 反映了多媒体技术发展的历程。 掣鲨圆 r广衅。 颤& 譬叠- 量e ：j r 。m m 磷k 潮 1 _ 。 目l _ l 数宁化时代的一维儿倒 f i g 113 dg e o m e t 叫i nd i g i t a la g e s 三维几何数据凭借以往媒体数据无可比拟的逼真性和交互性在许多领域扮演着越 来越重要的角色，发挥越i = j 乏越重要的作用，其应用领域托白盖了科学探索、i 柙设计、机 械制造、模拟仿真、医药卫生、城市枷- t j 、环境保护、文物保护、教育培训、艺术创造、 以及游成娱乐等许多方而。 任计算机图形学中，一维几何模型通常包含两部分内容：一部分是儿何模型的形体， 另一部分足儿何模型的外观属性。描述物体形体的方法有很多种，从川户角度看，形 体表小以特征表, t u 9 0 造实体几何表示( c s g ) 较为方便；从计算机对形体的存储管理和 操作运算角度看，以边界( bp - e p ) 表示最为实用。在边界表示法l 】一角形网格足毋通用的 表示力；_ 、。三角形网格模型具有以下优点：( 】) 二角形形状简单，便丁计算和处婵：( 2 ) 大量的小j 角形可以很精确地逼近任何曲【n j 物体，并，以表示拓扑非常复杂的物体；( 3 ) 只需存储符个二角形顶j _ 的何置坐标及届| 生即n j 表示物体的几何信息。幽12 给出了几 个= 舶形网格的倒子。几何模型外观描述厂物体表向上入剁光线和出射光线之问的相_ 瓦 均匀面积参数化 作用关系，是物体本身吲有的一种物理性质，比如物体的颜色，纹理等信息。本文只是 针对儿何模型的形体进行参数化，即二角形网格参数化。 目l2角形阿格模7 i _ i f i g i2 f r l a n g l em e s hm o d e l s 三角形网格通常是通过3 d 扫拙仪柬获取三维模型的复杂表面采样点的几何信息， 并通过拓扑重建得到。曲而参数化( 三角形网格参数化) 是对这些三角形网格的几何和 拓扑信息做进一步处理的基础。角形嘲格参数化的目的在于获得_ 维网格| f f i 丽与二维 平向域的个一一映射关系。这种一对应的映射将一些对三维网格的操作转换成对平 面网格的操作，人大减少了操作的复杂度。 曲面】参数化( 三维网格曲面参数化) 足计算机图形学的一个重要问题。它的研究涉 及到算机图形学、拓扑学、微分几何等学科。三角形刚格参数化在计算机图形学、计 算机辅助儿何设汁和数字儿何处理等方而有着广泛的席用1 “。i l 女d ：纹坪映射利用网 格表皿参数化信息，把幅纹理图像映射到乏维删格l 使得表面刚格看上去更加生 都逼真i ；曲面拟合通过参数化把离散的数据点刚一个光滑的参数i m 而米拟合岬】；重 网格化则利用参数化把不规则的三角形网格转化成具有细分连通性的规则网格，并进一 步做多分辨牢分析”；此外，二维刚格编辑有时需要把网格参数化到个容易交互处 理的参数域旧。冈此，本课题具有较大的学术价值。 12 三角形网格数据的表示 二角形网格模型足由许多三角形j _ j f 接而成( 见图1 2 ) 。p 司格所包含的信息包括几 何信息，连接信息和属性信息。其中，几何信息足指三角形顶点的坐标，包括x 、v 、z 二个分量；连接信息描述顶点l 剞的连接关系；而属性信息描述顶点的各种属性，丰要包 人连理【。大学硕- k 学 奇论文 括法讯颜色、纹理啦标等信息。本文的参数化方法主要是引对网格的几何信息和连接 信息进行参数化。 三角形网格模型的几何信息和连接信息可以用两个维数组表示，个是顶点数组 v ：( f l o a tx ，y ，z ) m 】，另个足三角形数组f ：( m t v 0 ，v l ，v 2 ) n 。顶点数矧v 【j 的每个 元素表示一个顶点的几何信息，包括x 、y 、z 二个华标分晕：i 角形数组t n 的每个儿 索表示一个= 角形，它由三个顶点确定，矩中v 0 ，v 1 ，v 2 为这i 个顶点在巧! 点数组v n 中的索引；i 1 1 ，n 分别表小顶点数和三角形数。人多数表示嘲格信息的文件格式都使用 了以r 的数组表示方法，如常用的p l y 2 ，o f f 等文件。 1 3 参数化算法相关研究工作 三角网格参数化的研究_ f 处于发展阶段，新的成果不断m 现。目前，有很多研究机 构在做这方面的上作，其中研究成果比较显著的闰外研究机构主要有：微软亚洲研究院 ( m s p a ) 、t h eu n i v e r s i t yo f o s l o ，m a x p l a n c k i n s t i t u t e f i ) n n a t i k ，t h eu n i v e r s i t yo f b r i t i s h c o l u m b i a ，c a l i f o m i a i n s t i m t eo f t e c h n o l o g y ，t h es t o n yb o o k u n i v e r s i t y 等；围内研究参 数化的机构土要有：浙江大学c a d & c g 国家重点实验室和西北工业大学现代设计与凭 成制造技术教育部蓖点实验窜。 蛰 剀l3 一堆蚺惜度共列i q | _ 维恻惜 f i g i3 a3 dm e s ha n di t si s o m o r p h i c2 dm e s h i 三角形网格曲l h j 参数化可以归结为这样一个问题：给定一个由空间点集p er 3 组成 的二角形删格m = r ) 和一个参数域n 。( 这个参数域通常是球面或者平面) ，寻求 个在原始刚格巾的点尸m 到参数域上的点p t n 。的一一映射( 见图13 ) ，使得参数 域上的网格与原始网格在拓扑卜刚构，并日舟保计参数域卜一角形不重叠的同时，哥求 某种与原始网格之叫的几何度量( 如角上篮、变k 和面积等) 变形的最小化。 聱 均匀面积参数化 从数学角度看，满足参数化有效性( 参数域上的网格与原始网格在拓扑上同构) 的 函数是很多的。寻求这样的函数并不是一件很难的事情，问题在于如何在这么多映射中 找到一个相对比较“好”的映射? 人们通常使用一些几何的内在属性( 如长度、角度和 面积等) 的变形程度来度量参数化的好坏。事实上，由于曲面的复杂性，人们对是否存 在最优的参数化方法的答案还是未知的。早在2 0 世纪6 0 年代研究人员就开始研究三角 形网格参数化问题，直到9 0 年代，该问题才得到深入而广泛的研究，并发表了很多关 于参数化的文献，这些技术都是为了解决一个几何变量的变形最小化问题( d i s t o r t i o n m i n i m i z a t i o n ) 。通常，可利用微分几何、弹性理论、等积映射、调和映射、保角映射和 等测度映射等理论来对变形最小化问题建模，并应用有限元分析以及数值分析等数学物 理工具来求解变形最小化问题。 根据分析问题的角度不同，三角形网格参数化方法基本上有以下几种分类：( 1 ) 根 据参数域的不同可以分为平面参数化和球面参数化；( 2 ) 根据网格的拓扑信息可以分为 带边界的网格参数化和封闭的网格参数化，甚至是任意拓扑的三角形网格参数化；( 3 ) 根 据考察的内在几何变量的变形，可以分为保面积参数化，保角参数化和等距参数化；( 4 ) 根据计算复杂度不同可以分为线性方法和非线性方法；( 5 ) 根据操作的部位不同可以分 为局部参数化和整体参数化等。 本文的主要工作是对原始三维网格进行平面参数化，因此本章重点将介绍平面参数 化的相关研究工作。直观上讲，平面参数化是把一个三维三角形网格平摊成平面三角形 网格，在保证平面三角形网格有效性的同时最小化变形。平面参数化方法的研究主要集 中在带边界的网格上( 该网格只有一条封闭的边界曲线) ，因为封闭网格甚至任意拓扑 结构的网格都可以通过切割的方法转化成多个单边界的网格。 1 3 1凸边界参数化方法 凸边界参数化方法的基本思想是事先把原始三维网格的边界映射到一个平面凸集 的边界，然后在此基础上把原始网格的内点映射到该凸集的内部。这类方法主要有凸组 合方法和能量最小化方法。 凸组合方法是由t u t t e 1 3 】在1 9 6 0 年提出的，其基本思想是把原始网格的边界映射到 一个平面上的凸多边形上，而内点取以它为中心点的一环的平均值。t u r e 证明了该方 法所得到的三角形不会相互重叠，如图1 4 所示但基于图论给出的这个嵌入图( g r a p h e m b e d d i n g ) 方法没有充分考虑到原始网格的几何信息，使得参数化结果的变形较大。 大连理工大学硕士学位论文 图1 4 三维网格中一内点及其一环邻域点 f i g 1 4 a ni n t e r i o rv e r t e xi n3 dm e s ha n di t s1 - r i n gn e i g l = l b o r h o o d s 在t u t t e 的基础上，f l o a t e r 提出了保形参数化方法【1 4 j ( 保持了原始网格的一环形状 不变性) 。该方法首先对原始网格的边界点按弧长参数化到单位正方形上，接着对每个 内点及其一环邻接点进行局部参数化，在局部参数化的基础上通过每个由三个邻接点组 成的三角形计算一次权值，全部计算完毕后，将每个领接点在一环邻域计算过程中得到 的所有权值平均后作为该邻接点的最终权值。虽然该方法会产生较大的角度变形，但是 具有保持原始网格的一环邻域形状不变性。另外，该方法将求解问题转化为一个大型的 稀疏线性方程组，使得整个参数化过程成为求解线性方程组，因此是相当快速的。由于 该方法在求解过程中具有高效性，所以它被广泛地应用在其他参数化方法中，比如后面 会讲到的虚拟边界参数化，凸组合球面参数化以及下面两种参数化方法。 y o s h i z a w a 等人提出一种快速低变形的网格参数化方法【1 5 】，该方法的主要思想是： 首先对原始网格采用文献 1 4 】中的方法进行平面参数化，接着计算原始网格和平面网格 之间的几何变形，然后在此基础上对内点的权值进行逐步优化从而得到最优的参数化结 果。 在y o s h i z a w a 的基础上，z a y e r 提出了离散张量准调和映射参数化【1 6 】。该方法也是 事先需要对原始网格采用一种参数化方法( 比如文献 1 4 】) 进行平面参数化，然后在此 基础上对平面网格进行平面参数化，从而得到最优的参数化效果。 凸组合方法在参数化过程中需要事先把原始网格的所有边界都固定到参数域中的 一个凸多边形上。这个凸多边形如何选取以及边界点如何分布在该边界上都会直接影响 到参数化的效果。如果原始网格的边界是非凸的，该类方法在参数域中根本就不能体现 原始网格的非凸边界结构。 能量最小化参数化方法的关键在于寻找一个目标函数，并且适当地给出该目标函数 的边界约束，然后求该目标函数的极值来得到原始网格参数化的结果。一个典型的方法 是引入弹性理论的胡克定律，把网格的各条边视为具有弹性的弹簧，运用弹性势能定义 原始网格参数化后的变形能量。 均匀面积参数化 p i n k a l l f l 。7 】等在数学上证明了调和映射与微分几何中的保角映射关系密切，并且在连 续d i r i c h l e t 积分基础上定义了离散能量函数，此能量函数的权值与调和映射方法1 1 8 】中所 得的方程组的系数相同。 e c k 提出的调和映射方法【l8 】就是将原始三角形中的每条边均看做一个弹簧，先将原 始三角网格的边界映射到预先定义好的凸多边形上，然后通过最小化三角形网格的弹性 势能来参数化内点。通过定义在多边形网格上的离散调和映射对三维网格进行参数化， 此离散调和映射函数是连续调和映射函数的一个逼近。并且他指出，在所有满足边界条 件的映射函数中，调和映射函数能使得变形能量最小。他进一步指出最小化该能量能减 少网格三角形在映射过程中的变形，从而保证三角形在二维参数域的形状。该算法将最 小化调和能量问题定义成一个最小二乘问题，通过求解一个稀疏线性方程组得到三维点 对应的参数坐标。该方法的能量权值( 弹性系数) 不仅取决于边长，还取决于和每条边 相邻的两个面的面积。这样可以尽可能的反映初始网格中每条边的长度和相邻面的形 状。由于调和映射是一个离散的准保角映射，它是连续保角映射的一个线性逼近，因此 该方法在局部区域具有较小的角度变形。 d e s b r u n 等人从离散微分几何出发，提出了网格的内禀参数化方法【1 9 】。该方法综合 考虑了两种能量( d i r i c h l e t 能量和c h i 能量) ，通过这两种能量方程的线性组合平衡角 度和面积变形从而得到较理想的参数化结果。这种方法对原始网格的边界进行参数化 时，可以不用把所有的边界点都固定到参数域中的凸多边形上，它只需要固定两个边界 点，然后采用边界约束条件对原始网格的边界进行参数化。这种方法的参数化结果可以 很好地体现原始网格的边界结构，即使原始网格的边界是非凸的。 奶一l 图1 5 星形多形 f i g 1 5 s t a r - s h a p e dp o l y g o n 上面这三种能量最小化方法都不能保证所有的能量权值都为正值，即不能保证参数 化的有效性。当原始网格中存在星形多边形，即原始网格中的某一内点的一环邻域中某 大迕理上人学硕j ，学忙论文 条边的相邻两个= 角形的两个内角的和火j 或等于”( 见罔15 ，d + 口”) ，此时相 关的能量权值就会为负值。日能量权值为负位，那么参数域中一f 能会出现三角形苹叠 现象，从而破坏原始网格的拓扑结构。文献1 9 1 的参数化方法还不具有缩放不变性：对 原始嘲格进行存向旧性缩放( 对原始刚格所有丁【j ! 点坐标的三个分量x 、y 、z 缩放桐_ r 4 的 倍数) ，相j 、t 的参数化结果都会随之改变。 f l o a t e r 提出了适用于星形多边形的均值坐标系办法口。蝮方法避免了能量系数出现 负值的情况，侗由r 均值芎心坐标是根掘多边形的内点推导山米的，所以当内点趋近于 多边形的某个顶点时，相应的权值会产牛溢m 现象，从而使这种方法变得不稳定。 能量最小化方法的关键叫题在r 能量权值的选取，其最大优点是只需求解一个线性 方程纽，具有很小的时间和空间复杂度，计儿实现起来比较容易。 山于凸边界参数化方法在对原始网格进行参数化叫，事先都需要把原始m 格的所有 边界顶点都固定到参数域中的一个凸多边形上( 文献1 9 1 除外) ，因此该类方法f y , j 参数 化结果不能很好地体现原始嘲格的“：凸边界结构( 如果原始网格的边界是非凸的) 。 132 非凸边界参数化方法 针对凸边界参数化方法存在的利z 种缺陷，丁是有人提出了非 “| 边界参数化方法。该 黄方法不需要事先把原始网格的边界映射到个凸集的边界，边界点的参数值在参数化 过程中求得。这类方法主要有虚拟边界法和分割艇平法。 l e e 等人提出的虚拟边界法口“土要是通过改变原始网格的边界来碱小参数化的变形 和保持原始网格的边界结构。该方沾的主要思想足通过对原始网格增加一层或者多层虚 拟边界生成一个新的刚格( 见图16 ，其中虚线为虚拟边界) ，此时原始网格的边界点 在新的网格下被视为内点，然后利用文献 1 4 1 的凸组合法对新的网格进行参数化。原始 网格绎藏方法参数化后，参数域中的结果能很好地保持原始网格的边界结构。但足该方 法需要人量的额外空叫来存储虚拟顶点和虚拟边。 吲16 原始网格及其层虚拟边界“ f i g 16t h eo r i g i n a lm e s ha n di t so n e - l a y e r e dv i r t u a lb o u n d a r y l 2 均匀面积参数化 h o r m a n n 提出了一个全局的非线性不定边界的参数化方法田1 ( 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 ) 。该方法事先不需要给出边界，只是需要对原始网格三角形和参数域中 相对应的三角形引进原子线性映射：g j = a x + b ，并求出g ，的j a c o b i a n 矩阵，通过与此 j a c o b i a n 矩阵的奇异值相关的f r o b e n i u s 范数来衡量g ，的保角性。当g ，为保角映射时， 此范数最小。将此能量函数定义为原始网格上所有三角形对应的f r o b e n i u s 范数的和， 最小化此能量函数就可以得到一个尽可能的保角映射。此方法无需固定边界，边界在计 算参数化时自然得到，然而该方法需要求解一个带约束的非线性系统 k = 芝：( g ，) ， = 型蝗掣 需要付出很高的计算代价，速度比较慢，而且在求解时可能得到的是局部最优解而不是 全局最优解。 分割展平法的主要思想是把复杂的三角形网格分割成多个可展的( d e v e l o p a b l e ) 网格 曲面，然后展平。s o r k i n e 提出了局部分割展平法【2 3 1 。该方法的主要思想是：首先在原 始网格中任意选取一个三角形作为种子三角形，并且将该三角形毫无变形地平摊到平 面，然后从该三角形出发，每次选取一个变形最小的相邻三角形展平，展平时保证所有 三角形不会重叠，直到没有可展平的三角形，最后重新选取种子三角形进行新一轮的展 平，每一此展平操作就生成一个新的可展面片。 s h e f f e r 提出了基于角度( a b f ：a n g l e b a s e df l a 地m n g ) 的整体展平法【2 4 j 。该方法给出 了一系列防止展平重叠的约束条件，并且证明了这些条件是保证参数化有效性的充分必 要条件。虽然a b f 方法无需固定边界，并且在纹理映射时都取得了比凸组合和调和能 量更好的结果，但是用l a g r a n g e 乘子法求解非线性系统的代价是很高的，并且a b f 方 法不能解决多边界问题。 1 3 3 其他平面参数化方法 多分辨率方法，也称为累进参数化方法，该方法建立在网格简化 2 5 - 2 6 1 和多分辨率表 示的基础上，在各个层次对网格进行参数化。该方法首先对原始网格通过半边折叠方法 建立简化网格，接着对简化后的网格进行参数化，最后在参数域中进行分裂点操作，并 参数化这些分裂点从而得到原始网格的参数化结果1 2 7 - 2 8 j 。 一8 一 大连理工大学硕士学位论文 在平面参数化中对于封闭网格的参数化通常是采用分而治之的方法，即首先把一个 封闭的原始网格切割成与圆盘同胚的网格曲面，然后对这些网格曲面进行参数化。 1 3 4 球面参数化方法 对于封闭网格，平面参数化需要将其分割成多个单边界的网格进行参数化，而球面 参数化可以避免这种不必要的分割。大多数球面参数化都建立在平面参数化的基础之上 2 9 - 3 2 1 ，但是平面上的线性参数化方法在球面直角坐标系下会变成非线性的方法。 g o t s m a n 2 9 在球面直角坐标系下运用文献【1 3 】的参数化方法进行球面参数化，该方 法需要求解一个非线性方程组，需要很高的计算代价。 g u 和y a u 等人提出了一个逼近调和映射的迭代算法对曲面进行全局参数化【3 8 】，此 算法不需要剖分曲面，通过求解一个非线性方程组来得到参数化结果。 k a n a i 等提出了一个简单的球面参数化方法【3 9 1 ，类似于平面域情况的能量方程，他 们模拟气球的膨胀将三角形网格黏附在球面上，但是该方法在理论上并不严谨，也不能 保证参数化的有效性。 a l e x a 提出了基于弹性理论的松弛参数化方法刚，该方法首先把网格的所有顶点投 影到模型的最小包围球面上，然后保持球面上6 个顶点的位置不动，用离散l a p l a c e 平 。均算子来松弛球面的其他顶点，从而达到球面参数化的目的。 h a k e 等人提出了球面保角参数化方法 4 1 】。该方法首先将与球面同胚的曲面映射到 平面上，然后通过立体投影( s t e r e o g r a p h i ep r o j e c t i o n ) 再将平面映射到球面上，这个立体 投影本身是一个保角映射。在将曲面映射到平面时，此方法采用与文献【1 8 】类似的离散 调和映射。 1 4 论文研究内容及方法 本文主要研究对原始三维网格进行平面参数化，直观上讲，平面参数化是把一个三 维三角形网格平摊成平面三角形网格，在保证平面三角形网格有效性的同时最小化变 形。平面参数化方法的研究主要集中在带边界的网格上( 该网格只有一条封闭的边界曲 线) ，因为封闭网格甚至任意拓扑结构的网格都可以通过切割的方法转化成多个单边界 的网格。 在平面参数化中能量最小化方法只需求解一个稀疏线性方程组，因而具有高效性。 该类参数化方法关键在于能量权值的选取，能量权值在参数化过程中具有重要作用，它 直接影响了参数化的有效性。好的能量权值应确保参数化的有效性，避免参数域中三角 形重叠，从而使参数域中的网格和原始网格在拓扑上同构，并且还应具有旋转、平移和 均匀面积参数化 缩放不变性，即对原始网格进行平移、旋转一定的角度和进行各向同性缩放，最终的参 数化结果都应保持不变。 本文首先对原始网格采用一种参数化方法( 均值坐标变换方法) 进行平面参数化， 然后在此基础上对平面网格进行平面参数化( 优化) ，即根据平面参数域网格面积密度 做迭代修改，使迭代后参数域网格较均匀分布。该算法用在纹理映射中能有效实现纹理 映射均匀化，并且算法简单、快速、稳定。 1 5 论文结构 本文主要研究如何减小参数化的变形问题。通过分析能量最小化方法的特点，首先 用均值坐标对三维网格进行平面参数化，在此基础上对均值坐标变值做迭代修改，从而 得出最优的参数化结果。此外，本文还将这种参数化方法应用到纹理映射中，实验结果 表明此方法能获得很好的纹理效果。最后，作者讨论了本文的进一步研究方向。 本文组织如下： 第一章绪论 主要介绍了三维网格曲面参数化技术与应用，对国内外关于三维网格参数化的研究 现状进行了综述，并介绍了本文的研究内容和基本的研究方法。 第二章平面参数化的基本理论 本章介绍了平面参数化的微分几何背景和图论知识背景，参数化的有效性以及参数 化的变形度量等基本概念，为后面章节的预备知识。 第三章几种典型的平面参数化算法 本章主要研究对象是带边界的非封闭三角网格曲面的平面参数化方法。重点分析并 实现f l o a t e r 的保形参数化、h a r m o n i c 调和映射、i n t r i n s i c 参数化以及均值坐标参数化方 法，阐述了各算法的基本思想和具体实现过程。 第四章均匀面积参数化算法 本章首先给出一种变形度量，基于这种度量提出一种均匀面积参数化，通过均匀参 数域网格面积，来降低参数化过程中产生的变形( s t r e t c h ) ，避免了传统s t r e t c h 方法中直 接计算矩阵的奇异值，使得算法简洁，提高了计算速度，同时能有效的解决纹理映射不 足问题。最后我们将本文算法、h a r m o n i c 调和映射、i n t r i n s i c 参数化以及均值坐标参数 化方法的变形大小做出比较，并且给出了纹理映射的应用实例。 最后结论部分对本文的主要工作和创新点进行了总结，并给出了本文今后的研究方 向。 大连理工大学硕士学位论文 2 平面参数化的基本理论 2 1引言 三角形网格参数化是对于给定的一个三角形网格曲面和一个参数域，寻求一个从三 角形网格上的点到参数域上的点的一一映射，在保持参数域上的拓扑信息与原始网格同 构的同时谋求某种几何度量的变形最小化。因此三角形网格参数化可以看作是该网格曲 面到某个适当的参数域空间的一个一一映射。本文主要研究的是平面参数化，即将原始 网格一一映射到一个平面参数域。 本章将介绍参数化的微分几何背景，平面参数化的相关图论定义及概念，给出三角 形网格在参数化时所需的一些概念和定义，参数化有效性的充要条件并且介绍参数化变 形的度量。 2 2 参数化的微分几何背景 下面引入一些参数化的微分几何相关知识，详细论述请参见微分几何口3 。4 1 。 假设曲面scr 3 相对某个平面区域dcr 2 上的点 ，) 的参数表达式为： r ( u ，1 ，) = ( x ，v ) ，y ( u ，v ) ，z ( u ，v ” 如果该表达式满足： ( 1 ) 函数x ，y ，z 都是光滑的，即连续可微； ( 2 ) 向量 却打 l 2 i ， 2i d“dv 在每一点都是线性独立的( 即它们的叉积lx r , 为非零) 这两个条件。则我们称这样的 表达式是正则的。网格参数化的曲面都为正则曲面。 曲面s 的第一基本形式是曲面s 中曲线弧长微分的平方，该二次方形式为： d s 2 = 阿1 2 = d r d r = ( l 幽+ r v 西) ( r 。d u + r f l v ) = l l ( 咖) 2 + 2 l r j u d y + r ，r a d v ) 2 = e d u 2 + 2 f d u d v + g d v 2 ( 2 1 ) 一 塑塑重堡叁鍪些 一 - - _ - _ _ _ _ - _ i _ _ 一一一一 其中e = l l ，f = l r v ，g = r v r v ，并且占，f ，g 称为曲面s 的第一基本形式的系 数。可以用一个对称矩阵来表示曲面的第一基本形式的系数： j = 瑚 则有： 出2 ：( a u ，d ( u ) 这个对称矩阵，在通常情况下代表着曲面的第一基本形式。 曲面s 的许多属性由它的第一基本形式描述，包括该曲面的弧长、面积和曲线间的 角度等属性。 设c 为曲面s 中的一条曲线，它的方程为： r = r ( 甜o ) ，1 ，( r ) ) ， 口sr b 这里f ：口，6 分别对应于曲线c 的端点彳，b 。从式( 2 1 ) 可知，沿曲线c 从彳到口的弧长工 为： 三：裟凼= f e c 警2 + 2 f 考老+ g c 老，2 衍 c 2 设曲面s 上两条曲线c ，c 的参数方程分别为： c ：u = 甜( f ) ，1 ，= 1 ，( f ) c ：秘- - - - u ( ) ，v = ，。) 它们在交点处p = ( u ，1 ，) 的切向量分别为： l 警+ r v 西d v 及l 等+ l 茅 l i + l 西及lj f + l 万 则它们在交点p 的夹角为它们在该点的切向量之间的夹角0 ，于是有： 大连理工大学硕士学位论文 ，幽咖、，咖西、 s p ：孚五二! 五挲亚二三鸾! i 出咖li 咖。咖i l l 石乜瓦肾万乜万i e d d u td 矩u ， + d t 期t - - 期t - - d t ) + g - - 前一d t 。 一dt饿1 d t 饿c l td t僦d t 属e(_警t)2+2fdud v + g ( ) 2 e ( ) 2 + 2 f 葶d 雾v + g 虿( ) 2 设q 的参数域是似，1 ，) 平面中的区域d ，则曲面s 上的区域q 一的面积么为： 彳= 舻仃= 仰毛r v i 幽咖 q d 因为存在： 所以有 l l 1 2 = i l l 2l r v l 2s i n 2 0 = j 匕1 2i l l 2 ( 1 一c o s 2 p ) = ( l l ) ( r v ) 一( l l ) 2 = e g f 2 = d e t ( i ) 彳= l l f f e g - f 2d u d v = d e t ( ) d ( 2 3 ) ( 2 4 ) 从式( 2 2 ) 、( 2 3 ) 以及( 2 4 ) 我们可知曲面s 的弧长，面积以及曲线间的夹角都是由该曲面 的第一基本形式决定。 2 2 1等距映射 若两个曲面s 和s 之间存在一个一一映射关系厂，使得它们上面对应曲线的弧长总 是相等，则称这两个曲面等距对应，映射厂称为等距映射。 定理2 1 t 1 1 若映射厂：s 专s 是等距映射，当且仅当曲面s 和的第一基本形式系数都 相等，即： i = r 2 2 2 保角映射 若两个曲面s 和之间存在一个一一映射关系厂，使得它们上面对应曲线间的夹角 总是相等，则称这两个曲面等角对应，映射厂称为等角映射或保角映射。 均匀面积参数化 定理2 2 【1 】若映射：s s 是等角映射，当且仅当曲面s 和s 。的第一基本形式系数成 定理2 3 【1 】若映射厂：s s 是等面映射，当且仅当曲面s 和s 的第一基本形式系数矩 若映射，：r 3 一r 2 ，r ( u ，d = ( x ( u ，) ，y ( u ，v ) ，z ( u ，v ) ) 其第一基本形式为： 其中，= 蒌三 是，的雅克比矩阵。，的奇异值q 和仃：分别是矩阵，的特征值a 。和允： c ，如果，是等距映射营，= 三： 九，= a ：营仃。= 仃：= ； ( 2 ) 如果，是保角映射，= 岛： 允，允：= 1 q 仃：= l ； ( 3 ) 如果，是保面积映射营d e t ( ，) = 1 允1 允2 = 1 仃l 仃2 = 1 从这里可知奇异值0 1 和仃：可以用来衡量映射，- 所引起的面积，边长，角度变形。比 大连理工大学硕士学位论文 2 3 参数化的图论相关概念和定义 首先引入图论中的一些标准定义，详细论述请参见图论p 5 。7 】，然后在此基础上引入 一些三角形网格的概念和定义。 2 3 1 图和简单图 一个图g 是一个三元组，这个三元组包含一个定点集y ( g ) ，一个边集e ( g ) 和一个 关系，该关系使得每一条边和两个顶点( 不一定是不同的点) 相关联，并将这两个顶点成 为这条边的端点。其中，e 是所有无序点对( f ，_ ，) 所组成的集合的子集，如果顶点是顶 点f 的邻接点，则( f ，歹) e 。度d ，为点f 的邻接点个数。 在一个图g 中，一个圈是一条边，它的两个端点是相同的；重边是具有同一对端点 的多条边。 简单图是不含有圈和重边的图。三角形网格都是属于简单图。 2 3 2 平面图 如果图g 可以在满足下列条件的情况下被嵌入到平面上，则称图g 是平坦的： ( 1 ) 每一个顶点f 映射到平面r 2 上的一点； ( 2 ) 每一条边o ，) e 被映射到端点为i 和的曲线上； ( 3 ) 各条曲线只能在端点处相交。 图g 这样的平面嵌入图称为一个平面图。三维网格的平面参数化过程是一个平面嵌 入的过程。 2 3 3 同构 如果两个简单图g = ( y ，e ) 和日= ( 矿，e ) 的拓扑连接