（运筹学与控制论专业论文）三角网格参数化的算法研究与应用.pdf

中文摘要 随着3 d 扫描测量技术的发展，三维网格模型正逐渐成为继声音、图像和视频 之后的第四种多媒体数据类型。它在互联网、娱乐和制造工业等领域的应用日益 广泛，这对数字几何处理算法提出了很高的要求。 计算机图形学的特点之一就是广泛地使用三维几何数据来描述场景。三角形 网格是一个标有一些属性信息的三角形的集合，它已经成为主流的复杂形状表面 三维模型表示方法之一。而三角形网格的这些属性包括两部分的内容：1 拓扑信 息，用于描述多边形网格中各顶点和面片之间的相互连接关系；2 几何信息，用 于描述多边形网格的位置坐标、以及附着在网格上的其它信息。 本文主要描述了三角网格的参数化技术。三角网格参数化可归结为这样一个 问题：给定一个由空间点集组成的二维流形三角网格和一个二维流形参数域，寻 求一个从参数域上的点到三角网格上点的一一映射，使得参数域上的网格与原始 网格拓扑同构，并在保证参数域上三角形不重叠的同时，谋求某种与原始网格之 间的几何度量的变形最小化。三角网格的参数化是对三角网格几何和拓扑信息作 进一步处理的基础，它在计算机图形学、计算机辅助几何设计和数字几何处理等 方面有着广泛的应用，也是目前图形学领域内的研究热点之一。 论文分为理论和应用两部分。首先，介绍了当今各种有效的三角网格参数化 算法并分析了它们的优缺点。其次，提出了一种有效的球面参数化算法。根据球 面与平面参数化之间的差异，列出了一个关于角度的有效球面三角化的充要条件 集，通过对非线性优化问题的求解，得到具有期望目标的球面参数化结果。实验 证明这种算法是比较稳定的。接着，本文结合许多已有的算法，对三角网格参数 化的各种应用进行了系统的归纳和总结。最后，对三角网格参数化方法的研究趋 势作了一个展望。 关键词：三角网格，参数化，i 扭曲失真，网格变形，平面参数化，球面参数化 a b s t r a c t w i t ht h ed e v e l o p m e n to f 3 ds e a n l l t n gt e c h n i q u e s , 3 dm e s hm o d e li sb e c o m i n ga n e w t 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 l l l a g e $ a n dv i d e og r a d l l a l l y t h i sm e d i u m i su s e de x t e n s i v ei n c r e a s i n g l yi ni n t e m e t , e n t e r t a i n m e n ta n dm a n u f a c t u r i n gi n d u s t r i e s a sw e l la sm a n yo t h e r 卸r e 勰t h u s , t h en e e df o rd i g i t a lp r o c e s s i n ga l g o r i t h m sh a sb e e n r a i s e dg r e a t l y o n eo f t h ep l q 删e so f c o m p u t e rg r a p h i c si st h a tt h et h r e ed i m e n s i o n a lg e o m e t r y d a t as e t sa r ew i d e l yu s e df o rv a r i o u sp u r p o s e s 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 cr e p r e s e n t e d 嬲l r i a n g l em e s h e s ，i e c o l l e c t i o n so fp o l y g o n s w i t ht h e i ra s s o c i a t e dp r o p e r t i e s r n 把l r i a n g l em e s hi sd i v i d e di n t ot w op a r t s ：t o p o l o g y i n f o r m a t i o n , w h i c hr e f e r st ot h ec o n n e c t i v i t yo ft h ev e r t i c e si nt h em e s h ；g e o m e l r y i n f o r m a t i o n , w h i c hr e f e r st ot h e v e l t c xl o c a t i o na n dt h eo t h e ri n f o r m a t i o na b o u tt h e m e s h e s p 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 , w h i c hi sm a i n l yp r e s e n t e di nt h i st h e s i s ， c a l lb ed e s c r i b e da , st h i sq u e s t i o n ：a s s i g n i n gap l a n a rm a n i f o l dt r i a n g l em e s hw h i c hi s c o m p o s e db yt h es p a t i a ls e to fp o i n t sa n dap l a n a rm a n i f o l dp a r a m e t e rf i e l d , t os e e k f o rao n e - t o - o n em a p p i n gf o rp o i n t sf r o mt h ep a r a m e t e rf i e l dt ot h et r i a n g l em e s h , c a u s e so nt h ep a r a m e t e rf i e l da n dt h ep r i m i t i v em e s ha r et o p o l o g i c a li s o m o r p h i s m w i t hg u a r a n t e e i n gt h et r i a n g l e so nt h ep a r a m e t e rf i e l dn o to v e r l a p , t r i e sf o rt h e s m a l l e s td i s t o r t i o no fg e o m e t r yi l i c a s u i eb c t w e e nt h em e s ha n dt h ep r i m i t i v eo n e s m e a n w h i l e p 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 , w h i c hi st h ef o u n d a t i o nf o rt h e f l l r t h e rp r o c e s so ft 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 sa w i d e s p r e a da p p l i c a t i o ni nc o m p u t e rc r r a p h i e s ，c o m p u 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 i l i t sb e c o m i n g0 1 3 eo ft h em o s tp o p u l a rr e s e a r c h f i e l d si nt h ed o m a i no f g r a p h i c ss t u d i e sn o w a d a y s t h i st h e s i si n c l u d e st w o p a r t s ：t h e o r i e sa n da p p l i c a t i o n s f i r s t , t h i st h e s i sb e g i n s w i t has u r v e yo f t h em o s tn o t a b l ea v a i l a b l ea l g o r i t h m so f p a r a m e t e r i z a t i o no f i r i a n g u l a rm e s h e s s e c o n d , b a s e do nt h ea n a l y s i so f t h ed i f f e r e n c eb e t w e e ns p h e r i c a l a n d p l a n a rm e t h o d s ，as e to f n e c e s s a r ya n d s u f f i c i e n tc o n d i t i o n so i lt h es p h e r i c a l a n g l e so f t h es p h e r i c a lt r i a n g l e si sf o r m u l a t e dt of o r mas 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 p a r a m e t e r i z a d o nr e s u l t sw i t ht a r g e tp r o p e r t i e ss o l v ea 1 1 0 n - l i n e a ro p t i m i z a t i o n t h es t a b i l i t yo f t h i sa l g o r i t h mi sp r o v e db ye x p e r i m e n t t h i r d , t h ea p p l i c a t i o no f 血i a n g u l a rm e s hp a r a m e t e f i z a t i o ni ss u m m a r i z e ds y s t e m a t i c a l l ya l o n gw i t hm a n y a l g o r i t h m sa sw ek n o w 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 e j o bi nt h i sf i e l di sg i v e n i nt h i st 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 , d i s t o r t i o n , m e s hm o r p h i n g , 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 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得鑫鲞盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：卡访硌玮签字日期： 撕r 年，z ，月；7 日 学位论文版权使用授权书 本学位论文作者完全了解鑫鲞盘茎有关保留、使用学位论文的规定。 特授权鑫凄盘鲎可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 栖玮讳 签字日期：沙f 年l 月乃1 日 名：勿毅， 签字日期：力确年f 月矽日 第一章绪论 第一章绪论 三维几何作为一种新的数据媒体近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 扫描仪获取复杂表面采样点的几何信息，并通过拓扑重建得到。 三角网格的参数化是对这些三角网格几何和拓扑信息作进一步处理的基础，它在 计算机图形学、计算机辅助几何设计和数字几何处理等方面都有着非常广泛的应 用。 近几年，球面参数化成为参数化方法研究的热点之一。本文在现有参数化方 法的基础上，根据球面与平面参数化之间的差异，对球面参数化进行了较为深入 的研究，列出了一个关于角度的有效球面三角化的充要条件，使用l m 算法通过 对非线性优化问题的求解，得到具有期望目标的球面参数化结果，通过实例说明 了算法的有效性。 1 1 走进数字化时代的三维几何 随着全球信息化的推进，数字技术、网络信息产业的发展，社会正快速进入 一个数字化的世界。 上个世纪7 0 年代以来，多媒体数据已经经历了3 次革命性的创新：声音、图 像和视频。从9 0 年代中后期开始，随着三维扫描技术和计算机图形学的发展以 及计算机性能各方面的提高，我们又迎来了第4 种数字化媒体一三维几何模 型。 第一章绪论 图卜1 走进数字化时代的三维几何 每一次多媒体数据革新都是由不断增长的数据获取能力、计算机运算能力、 存储能力和传输带宽的引发的。如图1 - 1 所示，跟随着多媒体技术的发展历程， 我们可以看到7 0 年代数字声音，8 0 年代数字图像和9 0 年代数字视频的出现和 普及应用。每种新的多媒体数据都需要新的处理工具来支持，这就引发了大量关 于数字信号处理的研究的出现。对每一种媒体的研究都产生了一门新的学科，如 对研究图像的数字图像处理信号和研究视频的数字视频处理。比较典型的信号处 理应用包括；去噪声、压缩、传输、增强、检测、分析以及编辑等等。 图卜23 dm o d e lo f m i c h e l a n g e l o sd a v i d 尽管几何造型技术已经发展了多年，但手工制造几何模型的繁琐过程大大阻 碍了三维几何模型的应用。近几年来，得益于各种低档和高档三维扫描仪提供的 三维几何获取能力的大大发展，把现实世界中的物体数字化成三维几何模型已经 不再困难。最著名的例子是s t a n f o r d 大学的d i g i t a lm i c h e l a n g e l op r o j e c t “】 ( 图卜2 ) ，该项目通过一整套三维扫描硬件和三维重建软件系统完成了一些大 型雕塑的数字化过程，生成的最复杂的模型三维模型包括2 0 亿个多边形和7 0 0 0 幅彩色图像! 另外，计算机运算能力和存储能力的大大提高以及各种图形加速卡出现使得 第一章绪论 在个人计算机上处理三维几何数据变得很容易。这些因素再加上i n t e r n e t 的飞 速发展使得我们有理由相信三维几何将继声音、图像和视频之后掀起新一轮的多 媒体数据革新高潮。事实上，这几年三维几何在影视工业、游戏工业和制造工业 的广泛的使用已经验证了这一点。相应于三维几何数据的广泛应用，一门处理几 何数据的学私卜_ 一数字几何处理也应运而生。相对于前三种多媒体数据，数字几 何处理具有更多的难点和更大的挑战性。 1 2 三维几何的数据表示 在计算机图形学中，三维几何模型通常包含两部分内容：一部分是几何模型 的形状，另一部分是几何模型的外观属性。 描述物体形状的方法有很多种，如体素表示法( v o x e l ) 、c s g 树表示法以及 边界表示法等等。其中边界表示法又有隐函数曲面、参数曲面、细分曲面、多边 形网格( m a s h ) 和点几何表示等。 从三维计算机图形学发展的初期开始，多边形网格就是最通用的表示物体形 状的方法。多边形网格模型具有以下优点：1 ) 多边形形状简单，便于计算和处 理；2 ) 多边形可以任意精度逼近一曲面物体，并可以表示拓扑非常复杂的物体； 3 ) 只需存储各多边形顶点的位置坐标及属性即可表示物体的几何信息，在计算 多边形内任一可见点的光亮度时，所需的信息可由顶点的信息插值得到，这使得 对多边形网格的绘制可采用硬件加速技术来实现。多边形网格模型可以由各种商 用动画软件如a l i a s ，w a v e f r o n t ，s o f t i m a g e ，m a y a 和3 dm a x 生成，或者通过 三维激光扫描仪在物体表面测得一系列离散点后由表面重构算法生成，或者由曲 面模型离散得到。图卜3 给出了几个多边形网格模型的例子。本文的研究对象就 是多边形网格模型。 图1 - 3 多边形网格模型 在计算机图形学中，由于绝大多数图形绘制流水线对三角形的绘制具有较好 的硬件支持，并且任意多边形可以很方便地被剖分为三角形，因此，三角形网格 被广泛用以组织几何数据，以实现快速绘制。 第一章绪论 几何模型的外观描述了物体表上入射光线和出射光线之间的相互作用关系， 是物体本身固有的一种物理性质。在计算机中，我们通常用一些容易被理解的属 性来描述，如顶点颜色( c o l o r ) 、光泽度( s h i n i n e s s ) 和透明度( t r a n s p a r e n c y ) 等等。对于真实世界中表面细节极其丰富的物体，人们还研究了多种复杂的外观 表示方法，如双向反射函数( b r d f ：b i d i r e c t i o n a lr e f l e c t i o nd i s t r i b u t i o n f u n c t i o n ) 、纹理映射( t e x t u r em a p p i n g ) 、凹凸纹理映射( b u m pt e x t u r em a p p i n g ) 和双向纹理函数( b t f ：b i d i r e c t i o n a lt e x t u r ef u n c t i o n ) 等。图1 - 4 给出了 一些带有颜色属性的三角形网格模型。 图1 q 带有颜色属性的三角形网格模型 1 3 数字几何处理的研究与应用 广义的数字几何处理包括三维几何数据的获取和处理两部分。获取是指为真 实世界中的物体生成三维几何模型。最常用的获取技术是通过三维激光扫描仪在 物体表面测得一些离散点，然后用散乱点重构算法生成网格模型瞳”。另外也有 些算法能从物体的多幅深度图像中重建三维几何模型旧。 与数字图像处理类似，三维几何数据处理由理论框架和应用两部分组成。理 论框架研究的目标是试图把经典信号处理领域的线性系统理论推广到三维几何 信号处理，为三维几何信号建立类似于图像处理中的f o u r i e r 变化、小波变换等 正交分析工具，理论框架构成了应用的基础；数字几何处理应用则涵盖了所有涉 及到几何数据的应用，包括去噪声、存储和传输、版权保护、编辑、变形和动画 等等。 随着三维几何模型在工业界的广泛应用，d g p 的应用领域也越来越广。最为 人们所熟知的是影视行业。为了带给观众在真实世界中无法体验了视觉感受，大 量的三维动画技术被应用到影视制作中，例如终结者中终结者由人化为一滩 金属液体，又从液体渐变成人形。图1 - 5 显示了马模型变形为兔子模型的过程。 第一章绪论 i - 5 马变形为兔子 在制造工业中，我们还通常需要对输入的三维数据去噪声和进行编辑。d g p 的其他应用领域还包括游戏工业、c a d 、电子商务和制造工业等等。 1 4 数字几何处理的挑战 众所周知，传统的三种数字多媒体数据都是定义在平坦欧氏空间中的信号。 声音是时间的一维函数，图像是定义在二维平面上的函数，视频是定义在二维平 面和时间轴上的三维函数。 数字几何处理的主要困难在于3 d 网格模型表面通常是任意弯曲、复杂和缺 乏连续参数化的，并且定义在模型表面各种属性( 包括顶点位置坐标、法向量和 颜色等) 都是非规则采样的。这使得经典的正交分析工具无法被直接用来处理 3 d 几何信号。如何把传统欧氏几何空间中的信号处理技术推广到3 d 几何是d g p 的最大挑战，也是计算机图形领域的一个公开问题。 1 5 三角网格参数化 网格曲面参数化技术作为很多图形学应用( 如纹理映射、网格变形、数字几 何处理等) 的关键技术，一直是计算机图形学的一个重要研究方向，也是目前图 形学领域内的研究热点之一，目前已经有了大量的研究成果，发表了不少参数化 的相关文献。 三角网格通常是由3 d 扫描仪获取复杂表面采样点的几何信息，并通过拓扑 重建得到。在数据分析和处理阶段，采用代数或参数描述形式往往可以使问题得 以简化。用统一的代数曲面来表示不规则三角形网格( t i n s ) 不是一件容易的事， 因而人们更多地采用参数化表示形式，这一过程称为三角形网格的参数化，即求 解三角形网格上的点和参数域内点的对应关系的过程。有了网格的参数化表示， 对网格所需进行的分析和处理就可以在相应的参数域上进行。 第一章绪论 参数域通常是欧氏空间r 。( 这里m 表示网格的维数) 的一个子集，而欧氏 空间又是大家所熟知的一种空间，因此分析数学在其上的许多成果在这里都可以 直接加以应用，从而解决了定义在空同曲面上的信号分析和处理问题。正因为如 此，许多计算机图形学应用都把网格参数化作为其首要的一步，如纹理映射、几 何信号处理、曲面拟合以及网格重采样( r e - m e s h i n g ) 等。 由于亏格为零( g o ) 的三角形网格m = 矿，毋( 这里将m 表示为一个顶点 表v 和面表f 组成的一个二元组，其中y 中存储的是每个顶点的坐标值，f 则 保存了组成面的顶点的索引号) 与q ( - - 维单位球面) 是拓扑同胚的，带孔的m 对应着带孔的q ，因此，一定存在肘和q 之间的同胚映射：f ：m q 将m 上 的每一点唯一地映射到q 上。根据这一原理，可以构造一个分片线性映射 r = f j , j o ，i f 卜1 ，使得 r ( v 1 ) = e l ，v v ，见q ，j o ，i 矿i _ l 其中，一表示第_ ，个三角形上的线性映射，m v 和i f l 分别表示网格的顶点数和面 数。可以证明，若r 是映上的，则r 就是m 与q 之间的同胚映射，广1 称为网格 m 的参数化。参数化过程就是求解映射r 的过程。如图1 _ 6 所示，映射【，_ ) ，z ) 将r 3 上开曲面s 一一对应到二维平面子集( “，d 参数空间。u ( x ，y ，z ) 的逆x ( u ，v ) 即为s 的参数化( p a r a m e t e r i z a t i o n ) 。 图1 - 6 参数化的示意 三角网格的参数化是对三角网格几何和拓扑信息作迸一步处理的基础，它在 计算机图形学、计算机辅助几何设计和数字几何处理等方面有着广泛的应用。比 如，纹理映射利用表面网格参数化信息，把一幅纹理图像映射到三维网格上，使 得表面网格看上去更加生动逼真n “；曲面拟合通过参数化把离散的3 d 数据点 用一个光顺的参数曲面来拟合“”“；重网格化( r e m e s h i n g ) 则利用参数化把三 角化曲面转化成具有细分连通性的规则网格 1 4 , i s , 1 ”p 并且在此基础上进一步作多 分辨率分析“8 ；还有很多数字几何处理，如交互式三维绘画踟、三维网格编辑 第一章绪论 乜1 1 、网格m o r p h i n g 等瞄4 蚓都需要事先把网格参数化到一个容易交互式处理的参 数域。如图卜7 所示。 1 6 本文工作 图1 - 7 参数化在网格处理上的应用 本文提出了一种有效的三角网格球面参数化的方法，其基本思想是在现有参 数化方法的基础上，根据球面与平面参数化之间的差异，列出了一个关于角度的 有效球面三角化的充要条件集，通过对非线性优化问题的求解，得到具有期望目 标的球面参数化结果。 本文后面的内容主要分为理论和应用两部分：理论部分介绍参数化的各种方 法，包括第二章的基础理论概述以及现有的参数化方法和第三章的新的球面参数 化算法。应用部分就是第四章的参数化方法的各种实际应用。 为了描述方便，本文第二章首先定义三角形网格、亏格、同构映射等概念， 然后简要描述参数化方法的研究历史及分类内容。另外，本章还分析讨论了现有 的各种参数化方法。 第三章描述我们提出的球面参数化算法。该算法在s h e f f e r 和d es t a t l e r 平面嵌入的算法基础上，结合球面与平面之间的差异，列出了一个有效球面三 角化的充要条件。利用这些关系式和适当的能量函数，构造了一个关于球面三角 网格参数化的优化问题，通过对优化问题的求解，得到了具有期望目标的球面参 数化结果。实验证明本文的球面参数化算法是比较稳定的。 第四章给出了数据例子说明三角网格参数化算法在计算机图形学、计算机辅 助几何设计和数字几何处理等方面的广泛应用，依此验证其在计算机图形学领域 举足轻重的地位，并通过实例阐明了三角网格参数化算法研究工作的实际意义。 最后总结全文的工作并介绍将来的研究方向。 第二章三角网格的参数化 第二章三角网格的参数化 三角网格的参数化是图论、微分几何、计算机图形学、计算机辅助几何设计、 数字几何处理、算法设计以及程序设计等学科的交叉研究领域。目前，有很多研 究机构在做这方面的工作，其中包括微软亚洲研究院( m s r a ) 、浙江大学c a d c g 国家重点实验室、美国的哈佛大学及以色列科技大学等。 参数化本身是一个很古老的问题，人们最早把这种技术应用在测地学、绘图 学等领域，随着计算机的飞速发展和多媒体娱乐应用的推动，它在计算机图形学 领域已占据举足轻重的地位。并且成为近几年来国际学术界一个前沿研究领域， 处于迅速发展阶段。因此，掌握其发展方向对数字几何处理的研究有着重要的指 导意义。 2 1 参数化方法的发展过程 早在2 0 世纪6 0 年代研究人员就开始研究三角网格参数化问题。根据参数化方 法在不同时期的主要特点，我们可以将参数化的研究分为以下几个阶段： 6 0 一7 0 年代中的萌芽期嘧力 这一阶段以s u t h e r l 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 提出变量几何和几何约束思想，并f h g o s s a r d 及其研究小组进一步发展 完善了这一方法为标志。 r c h i l l y a r d ( 1 9 7 8 ) 等把尺寸和公差视为特征点间约束，通过尺寸和视图指 定零部件的形状，利用给定的尺寸方案来判定零件图是欠约束、过约束还是约束 完备的。 8 0 年代中期- 9 0 年代初的发展时期 这一时期的一个重要特征是将矗i 技术引入参数化设计中，人们分别将几何推 理、神经网络等人工智能方法应用到设计中去，同时，将参数化技术应用到实体 造型形成特征造型技术，以b a l d e f e l d 、s u z u k i 、a y e r r o u s t 提出的基于专家系 统方法为主要代表。 b a 1 d e f e l d ( 1 9 8 8 ) 提出一种基于符号操作和推理机处理一般几何模型的方 第二章三角网格的参数化 法，一维几何模型被表示成一系列几何元素集和定义约束计划的原子规则集，他 将约束分为结构约束与公制约束，并用一阶谓词表示这些约束，通过构造计划、 规则库与推理机进行求解侧。 日本东京大学s u z u k i ( 1 9 9 0 ) 用规则来表示二维尺寸约束，用约束传播等技术 来进行模型参数化，给出了几何模型和约束的逻辑框架，以及几何的推理机制。“。 a v e r r o u s t ( 1 9 9 2 ) 等提出基于专家系统来处理约束等式，将所有约束分为角 度约束与距离约束，通过构造规则、三角形规则、平行规则将求解模型分为简单 模型、似解模型与不解模型，并且度图寻找给定尺寸约束的几何元素的计算序列， 同时给出了处理设计的一系列规则集嘲。 9 0 年代中期至今 直n 9 0 年代，参数化问题才得到深入而广泛的研究，并发表了很多关于参数 化的文献。基于知识的参数化理论逐渐完善，参数化方法在实践中得到了广泛的 应用。国内近年来对参数化的研究也显示出较高的热情，相继开发出些具有较 高技术水平的商品化软件嗡删，在几何约束的表示和求解方面，提出了各种新方 法和思路。 2 2 参数化简介 实际上，三角网格的参数化可以归结为这样一个问题：给定一个由空间点集 k r 3 组成的二维流形三角网格m = 亿) 和一个二维流形参数域q ，寻求一个 在参数域上的点巧q ，到点k m 的一一映射，使得参数域上的网格与原始 网格拓扑同构，并在保证参数域上三角形不重叠的同时，谋求某种与原始网格之 间的几何度量的变形最小化嘲。 从数学角度来看，满足这种参数化有效性的函数是很多的寻找这样的函数 并不是一件很难的事情，问题在于如何在这么多映射中找到一个相对比较“好” 的映射? 人们通常使用一些几何的内在属性( 如长度、角度和面积等) 的变形程 度来衡量参数化的好坏。事实上，由于二维流形曲面的复杂性，人们对是否存在 最优的参数化方法的答案还是未知的。 如今，很多关于参数化的技术都是为了解决一个内在几何变量的变形最小化 闯题( d i s t o r t i o nm i n i m i z a t i o n ) 。通常，可利用微分几何、弹性理论、等积映射、 调和映射、保角映射和等测度映射等理论来对变形最小化问题建模，并应用有限 元分析以及数值分析等物理数学工具来求解变形最小化问题。 2 3 基本概念 第二章三角网格的参数化 一、三角网格 三角形网格模型m 表示为三元组： m = ( ，匕) 其中 珞= 1 , 2 ，i 肘| 是m 的顶点集合( i m l 表示顶点数目) ；玛，是包含m 中所有拓扑连接关系的集 合；兄为m 中所有顶点的属性向量集合： = e ( ) i f 其中口( 0 = “o ) ，正o ) ，五( d ) 表示顶点 0 的厅个属性值，包括位置坐标，法向 量和颜色等，显然毛包含了m 的所有几何信息。 j 0 的元素分三种类型：顶点 矗，边e - - i ，力和面厂= f ，工| | 如果 f ，j j 0 ，则顶点 f 和 以被称为邻居。顶点 f ) 的1 环邻居被定义为 ( f ) = 引犯力蜀， ，顶点 f ) 的入度( v a l e n c e ) 被定义为( d 中的元素个数 i ( 叫，边p = f ， 的1 环邻居被定义为n ( e ) = n ( ) u n ( j ) - i ，力。依此类推，设 共享顶点的 0 所有三角形集合为t ( ) = f l if , f 0 ，则r 0 ) = 丁( f ) u r ( ，) 。 顶点 0 的星形邻域( s t a r ) 被定义为& 甜( o = u ，。嗍，j ， s t a r ( e ) = s t a r ( o u s t a r ( j 、。 和大多数处理网格模型的算法一样，本文也只处理流形网格，即网格中每个 顶点的1 环邻居( f ) 构成一个顶点环( 这样的顶点被称为内部顶点) 或半环( 边 界顶点) 。对于非流形网格，必须先通过预处理转化为流形网格。 顶点 i 处的顶点分布密度被定义为： 洲= 面 ( 2 1 ) _ f ) 其中a r e a ( m ) 表示网格m 的所有三角形面积之和。 二、同构映射和同形映射 如果两个网格m 和s 的拓扑连接关系相同，即存在从j 匕到题的一一映射 r 0 一s ，则称m 和箩是拓扑同构( g r a p h - i s o m o r p h i c ) 的，r o q 被称为从m 到s 的 同构映射。为任意网格肘构造球面参数化就是构造要构造一个与肘拓扑同构的 球面网格。通过拓扑同构映射r 。一。，原来定义在网格竹表面上的几何信号就被 转换为网格s 表面上的信号。 类似的，我们可以定义同形映射( h o m c o m o r p h o u sm a p ) 。如果对网格肘表 面上的任意一点，在网格矿表面上有唯一的一点与其对应，反之亦然，则称这 种从网格m 到网格矿的映射q 。一，为同形映射。例如任意两个单位球面网格之间 的投影映射就是同形映射。通过同形映射，定义在网格m 表面上的几何信号也 第二章三角网格的参数化 可以被转换为网格矿表面上的信号。 三、参数化的有效性 通常所指的三角网格是一个可定向的二维流形三角网格，所以三角网格参数 化的有效性充分必要条件是： a 原始网格顶点和参数域网格顶点在参数化映射下是一一对应的( 双射) ； b 参数域上的三角网格不互相重叠。 如图2 1 所示，日是p 的有效参数点，而e 是无效的。 曲固露 四、参数化的度量 视觉上的平滑效果好坏是衡量参数化变形的一个直观标准，参数化的变形有 以下两种最常用的定量标准： a 用参数域网格与原始网格之间的面积相对误差和角度相对误差等误差测度来 衡量变形程度。 = 爿参一劳 2 协2 ， = 手陲喙一熹) 2 其中，为网格的三角形个数指标；s 和4 分别是三角形的面积和角度；e 表 示三角形的角盈( 球面域) 。该误差测度是一个整体变形度量，不体现网格的局 部三角形变形。 b 基于几何变形( g e o m e t r i c - m e t c h ) 度量空间的方法。”。首先定义三角形之间 仿射变换的特征值度量空间。 厅_ r ( d = 吉( r 2 + ，2 ) ，p ( r ) = r ， ( 2 3 ) 其中r 和，分别为仿射变换的j a e o b i 矩阵的最大特征值和最小特征值。然后在这 个度量空间的基础上定义整体网格的参数化变形 第二章三角网格的参数化 r ( m ) = r ( m ) = m z “a x l 。( z ) ( 2 4 ) 这种基于纹理扭曲程度的度量既可以反映局部三角形变形又可以衡量整体网格 参数化的变形，是一种更为普遍的度量方法。s a n d e r 等把它拓展到信号的变形 ( s i g n a l s t r e t c h ) 度量啪3 。值得注意的是，这些度量首先在平面参数域里被应用， 后来被推广到球面参数域上。我们曾用式( 2 - 2 ) 来度量凸组合球面参数化的变 形嘲，周昆。”和p m u n 等“”分别在球面参数化上引用并发展了式( 2 - 4 ) 。 2 4 参数化方法的分类 如今，三角网格的参数化已经出现了很多种不同的方法，同时也存在着不同 的分类。 根据审视问题的角度不同，三角网格参数化方法基本上有以下几种分类： ( 1 ) 根据参数域的不同可以分为平面参数化和球面参数化； ( 2 ) 根据网格的拓扑信息可以分为带边界网格参数化和封闭网格参数化，甚至 是任意拓扑的三角网格参数化； ( 3 ) 考察不同的内在几何变量的变形，可以分为保面积参数化、保角参数化和 等距参数化； ( 4 ) 根据计算复杂度不同可以分为线性方法和非线性方法； ( 5 ) 局部参数化和整体参数化方法等。 因为参数域的不同和所处理网格的拓扑信息的不同，参数化的方法具有很大 的差异，后面主要以参数域和网格的拓扑信息作为主线来分析各种三角网格参数 化方法。并把它们进行归类比较；介绍各种参数化方法在各个领域中应用。 2 5 平面参数化 直观上讲，平面参数化就是把一个空间三角网格平摊成平面三角网格，在保 证平面三角网格有效性的同时最小化变形。参数化方法的研究对象主要集中在带 单条边界的二维流形网格上，因为封闭网格甚至是任意拓扑的网格都可以通过分 而治之( d i 、，i d ea n dc o n q u e r ) 的方法转化为带边界网格。 2 5 1 凸边界方法 凸边界方法的基本思想是把网格的边界映射到一个平面凸集的边界，把网格 第二章三角网格的参数化 的内点映射到这个凸集的内点。这类方法主要有凸组合方法和能量最小化方法。 2 5 1 1 凸组合方法 凸组合方法是由t u n e 在1 9 6 0 年提出的，其基本思想是把网格的边界映射到 一个平面上的凸多边形，而内点取以它为中心点的1 - r i n g 的平均值。t u t t e 证明了 该方法所得到的三角形不会相互重叠，如图1 所示。但基于图论给出的这个嵌入 图( o r a p he m b e d d i n g ) 方法1 没有充分考虑到原始网格的几何信息，使得参数 化结果的变形较大。在t u t t e 的基础上，f l o a t e r j 通过给每条边附加一个与边长相关 的权值改进了凸组合方法。它的基本思想是固定边界点，内点由它的相邻点的 加权凸组合给出( 如图2 2 所示) 。 巧= 乃巧， u ，j e 触叫 j 其中， 乃= 1 ，九= 7 1 。同时证明了该凸组合方法解的存在性和惟一 i ，l f ，j e 脚日哪 性。 弓- ， 弓 图2 - 23 d 三角网格和2 d - - - 角网格的对应 虽然该方法产生较大的角度变形，但是由于其具有保持1 - r i n g 形状不变性， 而称之为保形( s h a p e p r , s e n ，i n g ) 参数化；另外，由于该方法将求解问题转化为 一个大型的稀疏线性方程组，而整个参数化过程只需要求解线性系统，因此是相 当快速的，现在它己成为一个应用非常广的参数化方法。f l o a t e r 将保形凸组合网 格参数化方法扩展到非网格( m e s h l e s s ) 的点集参数化上，进行三维离散数据点 重建及曲面拟合“。p 饿n 等利用保形参数化进行数字几何处理1 。l e e 等结合 虚拟边界把凸组合方法拓展到非凸边界的平面参数化处理阍。浙江大学胡国飞等 把该方法拓展到球面上，同样得到一个保形球面参数化。 2 5 1 2 雒量方程最小化方法 该类方法关键在于寻找一个能量方程，称为目标函数，并且适当地给出该目 1 3 第二章三角网格的参数化 标函数的边界条件，然后求解目标函数的极值得到一个参数化。一个最典型的方 法就是引入弹性理论的h o o k e 法则，把网格的各条边视为具有弹性的弹簧，定义 整个网格的能量 占= i 1 毛i 彳一巧j f ， 一t l j ) e a g a 置梯度为0 ，诱导出一个线性方程组 箬= 乃一巧) = o 。 这类方法的区别在于能量系数矗的选取。简单地，推广空问曲线参数化的方 法，取如= 忙一弓旷时就是弦长参数化；取乃= 忙一只| r ，2 时就是向心参数化； 取气= l 时就使一致参数化。然而，系数的简单取法往往使参数化不具有很好的 保角特性。e c k 等提出调和能量方程，给出另一个系数“” 乃= 锐+ 错 其中，l 表示边长，晒表示三个顶点的面积。调和映射是一个离散的准保角映 射，它是连续保角映射的一个线性逼近，在局部区域保角性( c o n f o r m a l i t y ) 导 致它具有很小的角度变形。另外，p i n k a l l 等从另一个角度 = 芎1l0 v ，| 1 2 d a ， 在连续d i r i c h l e t 积分基础上定义离散能量函数，从数学上证明最小化这个能量 函数得到一个离散的最小化曲面和曲面卷积，并且得到和e c k 同样的结果 1( c o t 口+ c o t p ) 勺2 广。 同样，该方法具有局部保角的性质。进一步，d c s b m n 等给出基于表示曲面 g a l l s s 率积分的欧拉示性函数，引进二次能量 b = c o t y + ，。c o t d 。u p ；, 一巧0 2 ， t e n ( t ) 最小化二次能量，得到系数为 口( c o t a + c o t s ) 铲丁。 虽然调和映射具有很好的性质，但上述方法只是对调和映射的一个线性逼 近，并且在那些网格的尖端处的乃可能为负值。厶非正和边界非凸都可能产生 三角形重叠，这意味着该方法的解不总是存在的。即便如此，它仍比凸组合方法 变形要小。对于负值情况，e c k 用一致参数化来代替。而最新的一种方法是中值 ( m e a n v a l u e ) 方法： 第二章三角网格的参数化 毛：篷塑， 岛 该方法不仅避免了负值情况，并且与调和映射的参数化结果相差无几。能量最小 化方法的关键问题在于能量系数的选择，其