（计算数学专业论文）基于圆模式的球面参数化方法.pdf

大连理t 大学硕十学位论文 摘要 随着3 d 扫描测量技术的不断发展，三维几何数据成为继声音、图像和视频之后的 第四代多媒体数据类型，而三角网格表示成为现在主流的复杂表面三维模型表示方法之 一 三角网格的参数化是图论、微分几何、计算机图形学、计算机辅助几何设计、数字 几何处理、算法设计以及程序设计等学科的交叉研究领域。随着计算机的飞速发展和多 媒体娱乐应用的推动，三角网格参数化在计算机图形学领域已占有举足轻重的地位。 根据参数域的不同，三角网格参数化方法分为平面域参数化方法和球面域参数化方 法。平面参数化是目前应用极为广泛的一类参数化方法，相比之下球面参数化方法的研 究显得较少。这一方面是因为目前球面参数化应用较少；另一方面是球面参数化问题比 平面参数化问题难。但是对于很多数字几何处理的应用来说，把封闭网格分割成面片进 行平面参数化方法不仅困难而且不合理，为此近几年出现了很多球面参数化的方法，避 免这种不必要的拓扑分割。本文研究了几种典型的网格参数化方法，分别从平面域和球 面域对各种参数化方法的保面积性、保角性和等距性进行了分析和讨论，并从算法的理 论基础、运算时间复杂度、适用范围和数值实现方法等方面进行了详细的比较和论述。 另外，介绍了l i l i y ak h a r e v y c h 等提出的基于圆模式的平面参数化算法，并把这一算法 推广到了球面域。基于圆模式的平面参数化算法是一种保角参数化算法，该算法利用三 角形的外接圆和外接圆的夹角构造空间网格到平面的映射，能有效地处理多种边界条 件，算法实现中的数值处理相对简单。本文把这一算法推广到球面域扩充了这一算法的 适用范围，文章通过对不同的模型进行实验，并分析实验结果，验证了本文提出的基于 圆模式的球面参数化算法的有效性。最后分析了算法的不足和需要改进的地方。 关键词；三角网格；参数化；圆模式；立体投影；平面参数化；球面参数化 基于圆梭式的球面参数化方法 t h e s p h e d c a lp a r a m e t e r i z a t i o nv i ac i r c l ep a t t e r n s a b s t r a c t w i t ht h ed e v e l o p m e n to f3 ds c a n n i n gt e c h n i q u e s ，3 dm o d e li sb e c o m i n gan e wt y p eo f m u l t i m e d i aa l o n gw i t hs o u n d ，i m a g e sa n dv i d e og r a d u a l l y i nt h em o s tc o m m o nf o r m ，t h e3 d d i m e n s i o n a ld a t as e t sa r er e p r e s e n t e da st r i a n g l em e s h e s p a r a m e t e r i z a t i o no f t r i a n g u l a rm e s h e s w h i c hi st h ef o u n d a t i o nf o rt h ef i l r t h e rp r o c e s so f t r i a n g u l a rm e s hg e o m e t r ya n dt o p o l o g i c a li n f o r m a t i o n ，h a sw i d e s p r e a da p p l i c a t i o n i n c o m p u t e rg r a p h i c s ，c o m p n t e ra i d e dg e o m e t r yd e s i g n ，d i g i t a lg e o m e t r yp r o c e s sa n ds oo n i ti sb e c o m i n go n eo ft h em o s tp o p u l a rr e s e a r c hf i e l d si nt h ed o m a i no fg r a p h i c ss t u d i e s n o w a d a y s w i t l lt h ed i f i e r e n e eo fp a r a m e t e r i z a t i o nd o m a i n t h e r ea r ep l a n a rp a r a m e t e r i z a t i o na n d s p h e r i c a lp a r a m e t e r i z a t i o n n i ep l a n a rp a r a m e t e r i z a t i o n h a sw i d ea p p l i c a t i o n w h i l et h e s p h e r i c a lp a r a m e t e r i z a t i o nh a sl e s sr e s e a r c h i no r d e l t op a r a m e t e r i z ec l o s e dm e s h e so n t ot h e p l a n e , t h em e s h e sa 糟p a r t i t i o n e d i n t o m u l t i p l e c h a r t st h a ta r es u i t a b l ef o r p l a n a r p a r a m e t e r i z a t i o n n ep a r t i t i o nu s u a l l y i n c u r ss e v e r ed i s t o r t i o n 。s ot h e s p h e r i c a l p a r a m e t e r i z a t i o ni sm o r er e a s o n a b l e t _ i i i st h e s i sb e g i n sw i t has u r v e yo ft h em o s tn o t a b l e a v a i l a b l ea l g o r i t h m so fp a r a m e t e r i z a t i o no ft r i a n g u l a rm e s h e s d i s c u s s i o no fv a r i o u s a l g o r i t h m so nt h e i rt h e o r e t i c a lb a s i s , t i m ea n ds p a c ec o m p l e x i t ya r ep r e s e n t e d s e c o n d l y ，a n o v e ls p h e r i c a lp a r a m e = t e r i z a t i o ni sf o r m e db a s e do nc i r c l ep a t t e r n s ，t h a ti s , a r r a n g e m e n t so f c i r c l e s o n ef o re a c hf a c e - w i t hp r e s c r i b e di n t e r s e c t i o na n g l e s g i v e nt h e s ea n g l e s ，t h ec i r c l e r a d i if o l l o wa st h eu n i q u em i n i m i z e ro fac o n v e xe n e r g y t h em e t h o ds u p p o r t sv e r yf l e x i b l e b o u n d a r yc o n d i t i o n s t h ev e r s a t i l i t ya n dp e r f o r m a n c eo f t h ea l g o r i t h mi sd e m o n s t r a t e dw i t ha v a r i e t yo fe x a m p l e s f i n a l l y ，t h ee x p e c t a t i o nf o rt h ef u t u r ej o bi nt h i sf i e l di sg i v e ni nt h i s t h e s i s k e yw o r d s ：t r i a n g u l a rm e s h e s ：p a r a m e t e r i z a t i o n ；c i r c l ep a t t e r n ；s t e r e op r o j e c t i o n ； 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 a lp a r a m e t e r i z a t i o n i i 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意 作者签名：左盛国日期：丝翌二! 兰二兰 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位 论文版权使用规定”，同意大连理工大学保留并向国家有关部门或机构送 交学位论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连理 工大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也 可采用影印、缩印或扫描等复制手段保存和汇编学位论文。 作者签名蕉垂西 导师签名 鲨丑年业月土日 大连理工大学硕士学位论文 1绪论 三维几何作为一种新的数据媒体近l o 年来在工业界得到了广泛应用，这一趋势推 动了学术界对数字几何处理的研究。数字几何处理( d g p ) 即用计算机对三维几何数据进 行处理，主要指三维网格的化简、压缩、细分、优化等，这门从9 0 年代中后期发展起 来的学科属于计算机图形学和数字信号处理的交叉学科。尽管近几年这一方向的研究取 得了激动人心的进展，但与大家熟悉的数字图像处理和数处理等处理传统媒体的学科相 比，数字几何处理还显得非常年轻。正如一些学者指出的那样，数字几何处理还是计算 机图形学研究领域的一个公开问题。而三角网格表示成为现在主流的复杂形状表面三维 模型表示方法之一 三角网格通常是3 d 扫描仪获取复杂表面采样点的几何信息，并通过拓扑重建得到。 三角网格的参数化是对这些三角网格几何和拓扑信息作进一步处理的基础，它在计算机 图形学、计算机辅助几何设计和数字几何处理等方面都有着非常广泛的应用。 1 1 三维数字几何 随着全球信息化的推进，数字技术、网络信息产业的发展，社会正快速进入一个数 字化的世界。 上个世纪7 0 年代以来，多媒体数据已经经历了3 次革命性的创新：声音、图像和 视频。从9 0 年代中后期开始，随着三维扫描技术和计算机图形学的发展以及计算机性 能各方面的提高，我们又迎来了第4 种数字化媒体一三维几何模型。 每一次多媒体数据革新都是由不断增长的数据获取能力、计算机运算能力、存储能 力和传输带宽的引发的。跟随着多媒体技术的发展历程，我们可以看到7 0 年代数字声 音，8 0 年代数字图像和9 0 年代数字视频的出现和普及应用。每种新的多媒体数据都 需要新的处理工具来支持，这就引发了大量关于数字信号处理的研究的出现。对每一种 媒体的研究都产生了一门新的学科，如对研究图像的数字图像处理信号和研究视频的数 字视频处理。比较典型的信号处理应用包括：去噪声、压缩、传输、增强、检测、分析 以及编辑等等。 尽管几何造型技术已经发展了多年，但手工制造几何模型的繁琐过程大大阻碍了三 维几何模型的应用。近几年来，得益于各种低档和高档三维扫描仪提供的三维几何获取 能力的大大发展，把现实世界中的物体数字化成三维几何模型已经不再困难。 另外，计算机运算能力和存储能力的大大提高以及各种图形加速卡出现使得在个人 计算机上处理三维几何数据变得很容易。这些因素再加上i n t e r n e t 的飞速发展使得我们 基于圆模式的球皿参数化方法 有理由相信三维几何将继声音、图像和视频之后掀起新一轮的多媒体数据革新高潮。事 实上，这几年三维几何在影视工业、游戏工业和制造工业的广泛的使用已经验证了这一 点。相应于三维几何数据的广泛应用，一门处理几何数据的学科一数字几何处理也应 运而生。相对于前三种多媒体数据，数字几何处理具有更多的难点和更大的挑战性。 在计算机图形学中，三维几何模型通常包含两部分内容：一部分是几何模型的形状， 另一部分是几何模型的外观属性。描述物体形状的方法有很多种，如体素表示法、c s g 树表示法以及边界表示法等等。其中边界表示法又有隐函数曲面、参数曲面、细分曲面、 多边形网格( m e s h ) 和点几何表示等。在计算机图形学中，由于绝大多数图形绘制流水 线对三角形的绘制具有较好的硬件支持，并且任意多边形可以很方便地被剖分为三角 形，因此，三角形网格被广泛的用以组织几何数据，以实现快速绘制。 从三维计算机图形学发展的初期开始，多边形网格就是最通用的表示物体形状的方 法。多边形网格模型具有以下优点：( 1 ) 多边形形状简单，便于计算和处理；( 2 ) 多边形 可以任意精度逼近一曲面物体，并可以表示拓扑非常复杂的物体；( 3 ) 只需存储各多边形 顶点的位置坐标及属性即可表示物体的几何信息，在计算多边形内任一可见点的光亮度 时，所需的信息可由顶点的信息插值得到，这使得对多边形网格的绘制可采用硬件加速 技术来实现。多边形网格模型可以由各种商用动画软件如a l i a s ，w a v e f r o n t ，s o l , i m a g e ， m a y a 和3 dm a x 生成，或者通过三维激光扫描仪在物体表面测得一系列离散点后由 表面重构算法生成，或者由曲面模型离散得到。图1 1 给出了几个多边形网格模型的例 子 图1 1 多边形网格模型 f 嘻i 1 t h ep o l y g o n a lm e s hm o d e l s 在计算机图形学中，由于绝大多数图形绘制流水线对三角形的绘制具有较好的硬件 支持，并且任意多边形可以很方便地被剖分为三角形，因此，三角形网格被广泛用以组 织几何数据，以实现快速绘制。 大连理t 大学硕士学位论文 广义的数字几何处理包括三维几何数据的获取和处理两部分。获取是指为真实世界 中的物体生成三维几何模型。最常用的获取技术是通过三维激光扫描仪在物体表面测得 一些离散点，然后用散乱点重构算法生成网格模型。另外也有些算法能从物体的多幅深 度图像中重建j 维几何模型。 与数字图像处理类似，三维几何数据处理由理论框架和应用两部分组成。理论框架 研究的目标是试图把经典信号处理领域的线性系统理论推广到三维几何信号处理，为三 维几何信号建立类似于图像处理中的f o u d e r 变化、小波变换等正交分析工具，理论框 架构成了应用的基础；数字几何处理应用则涵盖了所有涉及到几何数据的应用，包括去 噪声、存储和传输、版权保护、编辑、变形和动画等等。 随着三维几何模型在工业界的广泛应用，d g p 的应用领域也越来越广。最为人们所 熟知的是影视行业。为了带给观众在真实世界中无法体验了视觉感受，大量的三维动画 技术被应用到影视制作中，例如终结者中终结者由人化为一滩金属液体，又从液体 渐变成人形。图1 2 显示了马模型变形为兔子模型的过程。 图1 2 马变形为兔子 f i 蓦i 2t h eh o r s et r a n s f o r m e dh n or a b b i t 在制造工业中，我们还通常需要对输入的三维数据去噪声和进行编辑。d g p 的其他 应用领域还包括游戏工业、c a d 、电子商务和制造工业等等。 传统的三种数字多媒体数据都是定义在平坦欧氏空间中的信号。声音是时间的一维 函数，图像是定义在二维平面上的函数，视频是定义在二维平面和时间轴上的三维函数。 数字几何处理的主要困难在于3 d 阿格模型表面通常是任意弯曲、复杂和缺乏连续参数 化的，并且定义在模型表面各种属性( 包括顶点位置坐标、法向量和颜色等) 都是非规 则采样的。这使得经典的正交分析工具无法被直接用来处理3 d 几何信号。如何把传统 基于圆模式的球【酊参数化方法 欧氏几何空间中的信号处理技术推广到3 d 几何是d g p 最大挑战，也是计算机图形领域 的一个公开问题。 1 2 三角网格参数化技术 网格曲面参数化技术作为很多图形学应用( 如纹理映射、网格变形、数字几何处理 等) 的关键技术，一直是计算机图形学的一个重要研究方向，也是目前图形学领域内的 研究热点之一，目前已经有了大量的研究成果，发表了不少参数化的相关文献。 三角网格通常是由3 d 扫描仪获取复杂表面采样点的几何信息，并通过拓扑重建得 到。在数据分析和处理阶段，采用代数或参数描述形式往往可以使问题得以简化。用统 一的代数曲面来表示不规则三角形网格不是一件容易的事，因而人们更多地采用参数化 表示形式，这一过程称为三角形跚格的参数化，即求解三角形网格上的点和参数域内点 的对应关系的过程。有了网格的参数化表示，对网格所需进行的分析和处理就可以在相 应的参数域上进行。 实际上，三角网格参数化可以归结为这样一个问题：给定一个由空间点集只r 3 组 成的二维流行三角网格m = f l ，和一个二维流行参数域q 。，寻求一个在参数域上的点 只q 。到三角网格上的点c m 的一一映射妒，使得参数域上的网格与原始网格拓扑 同构，并在保证参数域上三角形不互相重叠的同时，谋求某种与原始网格之间的几何度 量的变形最小化。 三角网格的参数化是对三角网格几何和拓扑信息作进一步处理的基础，它在计算机 图形学、计算机辅助几何设计和数字几何处理等方面有着广泛的应用。比如，纹理映射 利用表面网格参数化信息。把一幅纹理图像映射到三维网格上，使得表面网格看上去更 加生动逼真；曲面拟合通过参数化把离散的3 d 数据点用一个光顺的参数曲面来拟合； 重网格化( r e m e s h i n g ) 则利用参数化把三角化曲面转化成具有细分连通性的规则网格， 并且在此基础上进一步作多分辨率分析还有很多数字几何处理，如交互式三维绘画、三 维网格编辑、网格m o r p h i n g 等都需要事先把网格参数化到一个容易交互式处理的参数 域。 1 3 本文的工作 三角网格的参数化是图论，微分几何、计算机图形学、计算机辅助几何设计、数字 几何处理、算法设计以及程序设计等学科的交叉研究领域。目前，有很多研究机构在做 大连理t 大学硕十学位论文 这方面的工作，其中包括微软亚洲研究院、 的哈佛人学及以色列科技人学等。 浙江大学c a d & c g 国家重点实验室、美国 平面参数化是目前应用极为广泛的一类参数化方法，相比之下球面参数化方法的研 究显得较少。这一方面是因为网格构造球面参数化作用不明显；另一方面是球面参数化 衙题比平面参数化问题难。但是对于很多数字几何处理的应用来说，把封闭网格分割成 面片进行平面参数化方法不仅困难而且不合理，为此近几年出现了很多球面参数化的方 法，避免这种不必要的拓扑分割。本文分析比较了现有的几种典型的平面参数化和球面 参数化方法，并从理论介绍了l i l i y ak h a r e v y c h 等【l 】提出的基于圆模式的平面参数算法 并把这一算法推广到了球面域，实验结果和数据统计表明这一球面参数化算法具有变形 小、效率高的特点。 本文的主要研究内容如下： 第一章介绍了三角网格参数化技术、应用及其发展历程，并据此引出本文的选题 依据及研究内容。 第二章研究了几种典型的网格参数化方法，分别从平面域和球面域对各种参数化 方法的保面积性、保角性和等距性进行深入的讨论，并从算法的理论基础、运算时间复 杂度、适用范围和数值实现方法等方面进行了详细的比较和论述。 第三章介绍了l i l i y ak h a r e v y c h 等提出的基于圆模式的平面参数化算法，并把这 一算法推广到了球面域。基于圆模式的平面参数化算法是一种保角参数化算法，该算法 利用三角形的外接圆和外接圆的夹角构造空间网格到平面的映射，能有效地处理多种边 界条件，算法实现中的数值处理相对简单。本文把这一算法推广到球面域扩充了这一算 法的适用范围，文章通过对不同的模型进行实验，并分析实验结果，验证了本文提出的 基于圆模式的球面参数化算法的有效性。 在最后一章，给出了对本文研究内容的总结，并对下一步的研究计划作出了展望。 基- t - 圆模式的球由参数化方法 2 三角网格参数化技术 参数化本身是一个很古老的问题，人们最早把这种技术应用在测地学、绘图学等领 域，随着计算机的飞速发展和多媒体娱乐应用的推动，它在计算机图形学领域已占据举 足轻重的地位。并且成为近几年来国际学术界一个前沿研究领域，处于迅速发展阶段。 2 1 参数化方法的历史背景 希腊天文学家c l a u d i u sp t o l e m y ( 公元前1 0 0 一公元前1 6 8 ) 是历史上所知的最早的要 画世界地图的人。在他的著作g e o g r a p h y 2 中，他解释了如何使用栅格线经度线和 纬度线来把一个球投影到一张平面的纸上。就像我们所熟悉的，无法将一个完整的桔子 皮毫无褶皱的摊平在桌面上一样，球体不可能在投影的过程中不产生变形，所以必须要 采取一些折中的办法。图2 1 给出了几个例子。正交投影在两千多年前就为埃及人和希 腊人所知，在这种投影方法中，角度和面积都有改变，但是与投影中心的方向是与实际 相同的；立体投影法是被最广泛使用的一种等角投影法。例如，它保持角度不变( 以面 积的改变为代价) ，也将圆映射到圆上。有时甚至将圆映射到一条直线上，而不管这是 个多大的圆。立体投影法把斜航线画成一个螺旋线，斜航线指的是一条具有恒定方向的 线，在航海上具有重要的意义。1 5 6 9 年，一位佛兰德地图制作师g e r a r d u sm e r c a t o r 希 望制作出来可以让水手们确定航线的地图。他用他的等角网柱墨卡托投影克服这个障 碍。该地图上，每条斜航线都被画成一条直线。然而立体投影和墨卡托投影都不能保持 面积不变。在1 7 7 2 年，j o h a n nh e i n r i c hl a m b e r t 以放弃保角为代价建立了第一个等积投 影。 ( ) 疵交投影 立体投影( c ) 鬟耘矩投影( 由答承投影 图2 1 地球的投影图 f i g 2 it h e e 矾h p r o j e c t i o n c h a l r t 大连理工大学硕士学位论文 这些投影法都可以看作具有这样一个功能，即映射球面上的一部分到一个平面域。 通常，这种映射的逆向过程被称为参数化。 2 2 参数化方法的发展过程 早在2 0 世纪6 0 年代研究人员就开始研究三角网格参数化问题。根据参数化方法在 不同时期的主要特点，我们可以将参数化的研究分为以下几个阶段： 6 0 - 7 0 年代中的萌芽期 这一阶段以s u t h c r | a n d 为代表，他在s k e t c h p a d ( 1 9 6 3 ) 系统中提出利用约束作为辅助 手段进行零件的生成，但没有用约束定义和修改几何模型，对模型的修改只是一个单向 过程，一旦模型生成后约束不能反过来限制模型。 7 0 年代末- 8 0 年代初的开创时期 提出一些参数化设计的基本思想和理论，并逐渐成了不同的参数化方法。以h i l l y a r d 提出变量几何和几何约束思想，并由g o s s a r d 及其研究小组进一步发展完善了这一方法 为标志。i l c h i l l y a r d 等把尺寸和公差视为特征点间约束，通过尺寸和视图指定零部件 的形状，利用给定的尺寸方案来判定零件图是欠约束、过约束还是约束完备的。 8 0 年代中期- 9 0 年代初的发展时期 这一时期的一个重要特征是将a i 技术引入参数化设计中，人们分别将几何推理、 神经网络等人工智能方法应用到设计中去，同时，将参数化技术应用到实体造型形成特 征造型技术，以b a l d e f e l d 、s u z u k i 、a v e r r o u s t 提出的基于专家系统方法为主要代表。 b a l d e f e l d ( 1 9 8 8 ) 提出一种基于符号操作和推理机处理一般几何模型的方法，一维几何模 型被表示成一系列几何元素集和定义约束计划的原子规则集，他将约束分为结构约束与 公制约束，并用一阶谓词表示这些约束，通过构造计划、规则库与推理机进行求解。日 本东京大学s u z u k i 用规则来表示二维尺寸约束，用约束传播等技术来进行模型参数化， 给出了几何模型和约束的逻辑框架，以及几何的推理机制。a v e r r o u s t 等提出基于专家 系统来处理约束等式，将所有约束分为角度约束与距离约束，通过构造规则、三角形规 则、平行规则将求解模型分为简单模型、似解模型与不解模型，并且度图寻找给定尺寸 约束的几何元素的计算序列，同时给出了处理设计的一系列规则集。 9 0 年代中期至今 直到9 0 年代，参数化问题才得到深入而广泛的研究，并发表了很多关于参数化的 文献。基于知识的参数化理论逐渐完善，参数化方法在实践中得到了广泛的应用。国内 近年来对参数化的研究也显示h 较高的热情，相继开发出一些具有较高技术水平的商品 化软件，在几何约束的表示和求解方面，提出了各种新方法和思路。 基于圆模式的球由参数化方法 2 3 基本概念 2 3 1 参数化方法 三角网格的参数化可以定义为：给定个由空问点集只r 3 组成的二维流行三角网 格膨= ，乃，和一个二维流行参数域q ，寻求一个在参数域i - i b 点e , + q ，到三角网格上 的点只e m 的一一映射，使得参数域上的网格与原始网格拓扑同构，并在保证参数域 上三角形不互相重叠的同时，谋求某种与原始网格之间的几何度量的变形最小化。 从数学角度来看，满足这种参数化有效性的函数是很多的寻找这样的函数并不是 一件很难的事情，问题在于如何在这么多映射中找到一个相对比较“好”的映射? 人们 通常使用一些几何的内在属性( 如长度、角度和面积等) 的变形程度来衡量参数化的好 坏。事实上，由于二维流形曲面的复杂性，人们对是否存在最优的参数化方法的答案还 是未知的。 如今，很多关于参数化的技术都是为了解决一个内在几何变量的变形最小化问题 ( d i s t o r t i o nm i n i m i z a t i o n ) 。通常，可利用微分几何、弹性理论、等积映射、调和映射、 保角映射和等测度映射等理论来对变形最小化问题建模，并应用有限元分析以及数值分 析等物理数学工具来求解变形最小化问题。 2 3 2 三角网格 三角形网格模型m 表示为三元组： m ；( ，疋，) ， 其中 = l ，2 ，i m l ) 是m 的顶点集合( m 表示顶点数目) ；是包含m 中所有拓扑连接关系的集合；j 0 为 m 中所有顶点的属性向量集合： = 口( f ) i i ) ， 其中e ( o = ( a l ( 耽a 2 ( i ) ，口。( o ) 表示顶点h 的”个属性值，包括位置坐标，法向量和颜色 等，显然包含了m 的所有几何信息。 j i ，肘的元素分三种类型：顶点叶= f ，趔e , j = “_ ，) 和面厶= f j ，砧。如果p 口e k m ， 则顶点v 和0 被称为邻居顶点h 的l 环邻域被定义为n ( o = v ji ”d 如 ，顶点v ，入 大连理丁大学硕士学位论文 度( v a l e n c e ) 被定义为( d 中的元素个数i ( 叫，边勺的1 环邻域被定义为( 勺) = n 0 9 u ( ，) 一 f ，n 。 2 3 3 同构映射和同形映射 如果两个网格m 和s 的拓扑连接关系相同，即存在从j 0 到岛的一一映射。， 则称m 和s 是拓扑同构的，妒h 一。被称为从m 到s 的同构映射。 类似的，我们可以定义同形映射。如果对网格m 表面上的任意一点，在网格矿表 面上有唯一的一点与其对应，反之亦然，则称这种从网格m 到网格肜的映射九。为同 形映射。例如任意两个单位球面网格之间的投影映射就是同形映射。 2 3 4 参数化的有效性 通常所指的三角网格是一个可定向的二维流形三角网格，所以三角网格参数化的有 效性充分必要条件是： a 原始网格顶点和参数域网格顶点在参数化映射下是一一对应的( 双射) ； b 参数域上的三角网格不互相重叠。 如图2 2 所示，只是p 的有效参数点，而只是无效的。 嘲固蓐 图2 2 参数化的有效性 f i g 2 2 t h ev a l i d i t yo f p a r a m e t e r i z a t i o n 2 3 5 参数化的度量 视觉上的平滑效果好坏是衡量参数化变形的一个直观标准，参数化的变形有以下两 种最常用的定量标准： a 用参数域网格与原始网格之间的面积相对误差和角度相对误差等误差测度来衡 量变形程度【3 】。 基丁：圆模式的球向参数化方法 手踌一别2 ， 。敏咄= 啦隆刳2 其中，为网格的三角形个数指标；s ( o ) 和4 分别是三角形的面积和角度；e 表示三角 形的角盈( 球面域) 。该误差测度是一个整体变形度量，不体现网格的局部三角形变形 b 基于几何变形( g e 啪e m c - s t r e t c h ) 度量空问的方法【4 】。首先定义三角形之问仿射 变换的特征值度量空间。 斤一 工2 ( d = 、寺( r 2 + ，2 ) ，r ( r ) = r ( 2 2 ) 其中r 和，分别为仿射变换的j a c o b i 矩阵的最大特征值和最小特征值。然后在这个度量 空间的基础上定义整体网格的参数化变形 l r ( m ) - ，( r ( 丁) ) 2 s ( 巧) s ( 7 = ) 1! ! z ，“ ( 2 3 ) ir ( m ) 2 搿r ( ) 这种基于纹理扭曲程度的度量既可以反映局部三角形变形又可以衡量整体网格参数化 的变形，是一种更为普遍的度量方法。s a n d e r 等把它拓展到信号的变形( s i g n a l 。s t r e t c h ) 度量。值得注意的是，这些度量首先在平面参数域里被应用，后来被推广到球砸参数域 e 。 2 4 参数化方法的分类 如今，三角网格的参数化已经出现了很多种不同的方法，同时也存在着不同的分类 根据审视问题的角度不同，三角网格参数化方法基本上有以下几种分类： ( 1 ) 根据参数域的不同可以分为平面参数化和球面参数化； ( 2 ) 根据l 习格的拓扑信息可以分为带边界网格参数化和封闭网格参数化，甚至是任 意拓扑的三角网格参数化； ( 3 ) 考察不同的内在几何变量的变形，可以分为保面积参数化，保角参数化和等距 参数化； ( 4 ) 根据计算复杂度不同可以分为线性方法和非线性方法； ( 5 ) 局部参数化和整体参数化方法等。 大连理工大学硕士学位论文 因为参数域的不同和所处理网格的拓扑信息的不同，参数化的方法具有很大的差 异，后面主要以参数域和网格的拓扑信息作为主线来分析各种三角网格参数化方法，并 把它们进行归类比较；介绍各种参数化方法在各个领域中应用。 2 5 平面参数化方法 直观上讲，平面参数化就是把一个空间三角网格平摊成平面三角网格，在保证平面 三角网格有效性的同时最小化变形。参数化方法的研究对象主要集中在带单条边界的二 维流形网格上，因为封闭网格甚至是任意拓扑的网格都可以通过分而治之( d i v i d ea n d c o n q u e r ) 的方法转化为带边界网格。 2 5 1 凸边界方法 凸边界方法的基本思想是把网格的边界映射到一个平面凸集的边界，把网格内点映 射到这个凸集的内点。这类方法主要有凸组合方法和能量最小化方法。 乱凸组合方法 凸组合方法是由t u r e 在1 9 6 0 年提出的【5 】，其基本思想是把网格的边界映射到一个 平面上的凸多边形，而内点取以它为中心点的1 环邻域( 1 - r i n g ) 的平均值。t u t t e 证明了 该方法所得到的三角形不会相互重叠。但基于图论给出的这个嵌入图( g r a p he m b e d d i n g ) 方法【6 】没有充分考虑到原始网格的几何信息，使得参数化的结果变形较大。在t u t t e 的 基础上，f l o a t e r 通过给每条边附加一个与边长相关的权值改进了凸组合方法【7 】。它的基 本思想是固定边界点，内点由它的相邻点的加权凸组合给出( 如图2 3 所示) 。 t e = 气巧 ( 2 4 ) 盹e 蜘 其中 毛= l ，乃= i l f 同时证明了该凸组合方法解的存在性和唯一性。 图2 33 d 三角网格和2 d 三角网格的对应 f i g 2 3 3 dm e s hi sm a p p e dt o2 dm e s h 基于圆模式的球曲参数化方法 虽然该方法产生较大的角度变形，但是由于其具有保持l 环邻域形状不变性，而称 之为保形( s h a p e - p r e s e r v i n g ) 参数化；另外，由于该方法将求解问题转化为一个大型的稀 疏线性方程组，而整个参数化过程只需要求解线性系统，因此是相当快速的，现在它已 成为一个应用非常广的参数化方法。f l o a t e r 将保形凸组合网格参数化方法匆“展到非网格 ( m e s h l e s s ) 点集的参数化上，进行三维离散数据点重建及曲面拟合。p r a u n 等利用保形参 数化进行数字几何处理。l e e 等结合虚拟边界把凸组合方法拓展到非凸边界的平面参数 化处理。浙江大学胡国飞等把该方法拓展到球面上，同样得到一个保形球面参数化。 b 能量方程最小化方法 该类方法关键在于寻找一个能量方程，称为目标函数，并且适当地给出该目标函数 的边界条件，然后求解目标函数的极值得到一个参数化。一个最典型的方法就是引入弹 性理论的h o o k e 法则，把网格的各条边视为具有弹性的弹簧，定义整个网格的能量 居= i 1 毛0 只一巧6 2 ， ( 2 5 ) 。 l j t e d p i 置梯度为0 ，诱导出一个线性方程组 署= 乃( 口- 巧) = o ( 2 6 ) 这类方法的区别在于能量系数九的选取。简单地，推广空间曲线参数化的方法，取 如= 忙一c 旷时就是弦长参数化；取毛= 配一弓盯时就是向心参数化；取乃2 l 时就使 一致参数化。然而，系数的简单取法往往使参数化不具有很好的保角特性。e c k 等提出 调和能量方程，给出另一个系数 九4 = 峨。| + e ，b d - e i 、| p t p | p l 七啮| “七e h - 、- e | p t p 1 p | n 其中，表示边长， 表示三个顶点的面积。调和映射是一个离散的准保角映射，它 是连续保角映射的一个线性逼近，在局部区域保角性( c o n f o r m a l i t y ) 导致它具有很小 的角度变形。另外，p i n k a l l 等从另一个角度 昂= i 1l0 w 0 2 枷 ( 2 7 ) 在连续d i d c h l e t 积分基础上定义离散能量函数，从数学上证明最小化这个能量函数得到 一个离散的最小化曲面和曲面卷积，并且得到和e c k 同样的结果 乃= ( c o t c t r + c o t f l ) 大连理工大学硕士学位论文 同样，该方法具有局部保角的性质。进一步，d e s b m n 等给出基于表示曲面g a u s s 曲率 积分的欧拉示性函数，引进二次能量 e x = c o t y ，+ 。c o t 6 。p 。+ 巧 ( 2 8 ) 最小化二次能量，得到系数为 乃2 半产 虽然调和映射具有很好的性质，但上述方法只是对调和映射的一个线性逼近，并且 在那些网格的尖端处的厶可能为负值。厶非正和边界非凸都可能产生三角形重叠，这 意味着该方法的解不总是存在的。即便如此，它仍比凸组合方法变形要小。对于负值情 况，e c k 用一致参数化来代替而最新的一种方法是中值( m e a n v a l u e ) 方法【8 】： 兰+ t a n 霎) 乃2 芋 该方法不仅避免了负值情况，并且与调和映射的参数化结果相差无几。能量最小化方法 的关键问题在于能量系数的选择，其最大的优点就是只需求解一个线性系统，具有很小 的时问和运算复杂度，并且很容易实现，使得它成为应用最广的参数化算法。 2 5 2 非凸边界方法 现有的非凸边界方法大多数都不需要事先把网格的边界映射到一个凸集的边界，边 界点的参数值在参数化过程中求得，但是这类方法往往需要额外的计算量。 a 虚拟边界法 该类方法主要通过改变参数域的边界来减少参数化变形。f l o a t e r 直接把弦长比例映射到 正方形作为边界【9 】：e c k 等则用单位圆来作边界 1 0 】；而l e e 等【1 l 】甚至引进 e d g e - t w e a k l n g 方法生成更逼近原始网格的边界：它们共同的特点是这些边界围成的区 域必须是凸区域，否则参数化无效。虚拟边界的主要思想是通过对原始网格增加一条或 者多条虚拟的边界生成一个新的网格，然后利用凸边界方法对新的网格进行参数化。原 始网格的边界点在新网格下被视为内点，参数域上的原始网格的边界不再是一个凸边 界。 b m i p s 方法 能量最小化方法在不固定边界的情况下，能量最小将使得所有点收缩为一点，形成 一种病态收敛。h o r m a n n 等提出了一个全局的非线性不定边界的方法( 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 ，m i p s ) 1 2 ，该方法无需事先给出边界，只需对原始网格三角形和对 基于圆模式的球l 丘i 参数化方法 应的参数域三角形之间引进原予线性映射g ，= a x + b ，然后求解一个带约束的非线性系 统 k = k ，旧j ， ( 2 9 ) 步型譬筹学堂 得到包括内部点和边界点在内的所有点的参数值。虽然原子线性映射具有三角形的 平移、正交变换和变比不变性，然而该方法需要求解一个非线性系统，而且未从理论上 证明其选取的特征值相关的f r o b e n i u s 范数是最优的，但m i p s 无需固定边界的整体性 质得到大家的关注，l a b s i k 等把该方法应用到多边形曲面的重网格化【1 3 】。 c 分割展平法 分割展平法的主要思想是把复杂的三角网格分割成多个可展( d e v e l o p a b l e ) 面片。 然后展平。由于可展曲面可以毫无变形地平摊到平面上，因此分割过程自动完成三角网 格的平面参数化。具有代表性的是s o r k i n e 等提出的局部分割展平法，以及s h e f f e r 等提 出的基于a b f ( a n g l e b a s e df l a t t e n i n g ) 的整体展平方法【1 4 】，如图2 4 所示。 图2 4a b f 方法r a b b i t 模型的展开 f i g 2 4r a b b i tm o d e li sd e v e l o p e db ya b f m e t h o d 大连理工大学硕十学位论文 前者首先选取一个种子三角形，把它安置到平面；然后从该三角形出发，依据2 3 5 节中给出的特征值度量，每次选取一个变形最小的相邻三角形展平，展平时保证所有三 角形不会霞叠，直到没有可展平的三角形；最后荤新选取种子三角形进行新一轮的展平， 每一次展平操作就生成一个新的可展面片。局部分割展平法算法相当简单，具有很高的 运算效率，适用于任意拓扑。后者则是一个整体求解带约束的非线性的方法，与s o r k i n e 一样，s h e f f e r 等给出一系列防止展平重叠的约束条件，并且证明了这些条件是保证参数 化有效性的充分必要条件。虽然a b f 方法无需设定边界，并且在纹理映射时都取得了 比凸组合和调和能量更好的结果，但是用l a g r a n g e 乘子法求解非线性系统代价是很高 的，且a b f 方法不能解决多边界问题。 2 5 3 封闭网格参数化方法 对封闭网格通常是采用分而治之的方法，即切割封闭网格成多个与圆盘同胚的面 片。它实质上是一种分段参数化( p i e c e w i s ep a m m e c c r i z a t i o n ) ，其与分割展平法的区别在 于，它的面片不是平面可展曲面，因此必须应用带边界的参数化方法来进一步处理每一 个面片。封闭网格参数化的变形大小的关键在于切割方法的好坏。除了用交互式手工切 割之外，e c k 等用v o r o n o i 图和1 ) e l a u n a y 三角化的技术来分割三角网格【1 5 】；m a i l l o t 等 把一些法向相似的三角面片聚集成一个大面片【1 6 】，另外也有通过网格简化后的基复型 面片( b a s ec o m p l e x ) 来归类；而s a n d e r 等利用三角面片的平坦性( p l a n a r i t y ) 和紧致性 ( c o m p a c t n e s s ) 标准来分割三角网格，并用几何变形来度量这种分割的好坏d 7 。g u 等用 迭代的方法得到一个最小变形的切割生成几何图像【1 8 】。但是在封闭网格的切割线上， 同一个物理点被切割线分