（航空宇航制造工程专业论文）三角网格曲面参数化技术研究.pdf

南京航空航天人学硕十学位论文 摘要 三角网格曲面的参数化是指参数域与三维网格曲面间的一一映射关系， 它在计算机图形学等领域有着广泛的应用，是纹理映射、重新网格化以及曲 面拟合等操作中的重要环节。本文对三角网格曲面的平面参数化技术进行了 研究，主要工作如下： 研究并实现了几种典型的网格曲面参数化方法，比较了各自的参数 化效果和变形大小，给出了纹理映射、曲面拟合的应用实例。 提出了一种网格模型的近似v o r o n o i 图的多边界分块方法，该算法 简便易行，稳定性好，结果便于进一步的参数化操作。 提出了两种网格曲面的分块参数化方法。一种是对网格曲面进行四 边界分块的参数化方法：另一种是对网格曲面进行任意多边界分块 的全局参数化方法。这两种方法均提高了参数化的效率，并且后一 种方法为探索解决带有孔洞的多边界网格模型的参数化提供了一 个新的思路。 为解决多边界曲面块的边界参数化问题，提出了一种新的弧长参数 化方法。 研究了虚拟边界参数化方法，分析了多层虚拟边界层数与变形大小 的关系。 关键词：参数化、三角网格模型、曲面分块、纹理映射、虚拟边界 三角网格曲面参数化搜术研究 a b s t r a c t a p a r a m e t er i z a “o no fs u r f a c et r i a n g u l a t i o n sc a nb ev i e w e da sa ：o f l e t o 。o n e m a p p i n gf r o map a r a m e t r i cd o m a i nt ot h es u r f a c e p a r a m e t e r i z a t i o no fd i s c r e t e s u r f a c e si saf u n d a m e n t a la n dw i d e l y u s e do p e r a t i o ni ng r a p h i e s ，r e q u i r e d ，f o r i n s t a n c e ，f o rt e x t u r em a p p i n g ，r e m e s h i n go rs u r f a c ef i t t i n g i nt h i sp a p e r ，t h e a t t e n t i o ni sm a i n l yp a i dt op a r a m e t e r i z i n gm e s h e st oac e r t a i np a r a m e t e rd o m a i n ， t h em a i na c h i e v e m e n t sa r e a sf o l l o w s ： s e v e r a lt y p i c a lp a r a m e t e r i z a t i o nm e t h o d sw e r es t u d i e d g e o m e t r i cs t r e t c ho f t h e s em e t h o d sw a sc o m p a r e d o n eb e t t e rm e t h o dw a sa p p l i e dt ot e x t u r e m a p p i n ga n ds u r f a c ef i t t i n g an a l g o r i t h mo fp o l y g o n a lr e g i o np a r t i t i o no fa r b i t r a r yt r i a n g l em e s hw a sp u t f o r w a r da n di m p l e m e n t e d t h ea l g o r i t h mi sh i g h l ya u t o m a t i c ，e f f e c t i v e ， r o b u s ta n ds u i t a b l ef o rt h ec o n s e q u e n tp a r a m e t e r i z a t i o n t w op a r a m e t e r i z a t i o n so ft r i a n g l em e s hb a s e do ns u r f a c ep a r t i t i o nw e r e p r e s e n t e d o n ei sb a s e do nq u a d r i l a t e r a lr e g i o np a r t i t i o n ；t h eo t h e ri sb a s e d o n a r b i t r a r yp o l y g o n a lr e g m n p a r t i t i o n t h ea l g o r i t h m s m a k e p a r a m e t e r i z a t i o nm o r eq u i c k l y a n dt h el a t t e rp r o v i d e san e wa p p r o a c hf o r r e s e a r c hong l o b a lp a r a m e t e r i z a t i o no ft r i a n g l em e s hw i t hh o l e s 。 an e wa r c l e n g t hp a r a m e t e r i z a t i o na l g o r i t h mw a sp r e s e n t e df o r s o l v i n g p a r a m e t e r i z a t i o no fb o u n d a r i e sp r o d u c e db yp o l y g o n a lp a r t i t i o n p a r a m e t e r i z a t i o nw i t hv i r t u a lb o u n d a r yw a ss t u d i e d ，a n dt h er e l a t i o n s h i p b e t w e e nt h en u m b e ro fv i r t u a lt a y e r sa n dg e o m e g i cs t r e t c hw a sa n a l y z e d k e yw o r d s ：p a r a m e t e r i z a t i o n ，s u r f a c et r i a n g u l a t i o n s ，s u r f a c ep a r t i t i o n ， t e x t u r em a p p i n g ，v i r t u a lb o u n d a r y 承诺书 本人郑重声明：所呈交的学位沦文，是本人在导师指导下，独 立进行研究工作所取得的成果。尽我所知，除文中已经注明引用的 内容外，本学位论文的研究成果不包含任何他人享有著作权的内容。 对本沦文所涉及的研究工作做出贡献的其他个人和集体，均已在文 中以明确方式标明。 本人授权南京航空航天大学可以有权保留送交论文的复印件， 允许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有 关数据库进行检索，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的学位论文在解密后适用本承诺书) 作者签名 本文受以下项目资助 霍英东教育基金会高校青年教师基金( 编号0 3 9 1 0 5 3 ) 南京航空航大人学硕l 学位论文 第一章绪论 1 1 三角网格曲面参数化技术与应用 二角网格曲面的参数化是指参数区域与3 d 网格曲面问的一一映射关 系。参数区域可以是平面区域、球面或多面体等。对于参数域为平面的三角 网格参数化可归结为这样一个问题：给定一个由空间点集x ，r 3 组成的三角 网格曲面5 和一个二维参数域p ，寻求个在参数域上的点u p 到x s 的一一映射甲，如图1 1 所示，使得参数域上的网格与原始网格拓扑同构， 并在保证参数域上所有三角片之间不相互重叠的同时，谋求某种与原始网格 之问几何度量的变形最小化。这样的对应映射可以将一些三维网格曲面 的操作转换成对平面网格的操作，减小操作的复杂度。 剀1 1 三维网格年一二维网格的对应( 粗线所示二角块为同一个二角块) 作为现在主流的复杂形状表面三维模型表示方法之一，三角网格通常是 用3 d 扫描仪、三坐标测量机或光学测量仪等获取复杂表面采样点的几何信 息，并通过拓扑重建得到。三角网格的参数化是对这些三角网格的几何和拓 扑信息作进一步处理的基础，它在计算机图形学、计算机辅助几何设计和数 字几何处理等方面有着广泛的应用。比如，纹理映射1 1 - 3 1 利用表面网格参数 化信息，把一幅纹理图像映射到三维网格上，使得表面网格看上去更加生动 三角网格曲面参数化技术研究 逼真：曲面拟合通过参数化把离散的三维数据点用一个光顺的参数曲面来拟 合4 一”；重新网格化( r e m e s h i n g ) 则利用参数化把三角化曲面转化成具有细分 连通性的规则网格l8 。1 1 l ，在此基础上进一步做多分辨率分析。1 2 - 1 3 l ；还有很多 数字几何处理，如交互式三维绘画、三维网格编辑1 “、网格m o r p h i n g 【1 6 ” 等都需要事先把网格参数化到一个容易交互式处理的参数域。 1 2 参数化算法相关研究工作 从数学角度来看，满足这种参数化的函数有很多。寻找这样的函数并不 是一件很难的事情，问题在j 二如何在这么多映射中找到一个相对比较“好” 的h 央刺+ ? 人们通常使用些几何的内在属性( 如氏度、角度和面积等) 的变形 程度来衡量参数化的好坏。事实上，由于网格曲面的复杂性，人们对是否存 在最优的参数化方法的答案还是未知的。早在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 ) 。通常，可利用微分几何、 弹性理论、等积映射、调和映射、保角映射和等测度映射等理论来对变形最 小化问题建模，并应用有限元分析以及数值分析等物理数学工具来求解变形 最小化问题。 但是将一个不可展的3 d 网格曲面映射成一个平面的三角化不可避免的 要产生长度、面积、角度上的扭曲变形。网格的参数化就是试图保持这样的 几何度量。许多研究人员采用不同的方法着力于减少参数化造成的扭曲。 m a i l o t 等提出了一种基于弹性变形能量的度量，将在平面上参数点的 第一基本形式矩阵, 1 2 2 的恒等矩阵的差的范数作为变形能量的被积分泛 函，然后求解一个非线性的能量极小问题。由于他们的方法是求解一个全局 的连续映射函数，这样会使得复杂物体的纹理变形很大。为此他们把地图中 板块分割的思想引入网格，试图通过将整个网格分割成几个小的网格片，并 分别对它们进行参数化。但是这样的切割会导致分割线过多而且很长，从而 导致分割处较长的参数不连续，并且他们的分割方法需要人工交互来完成， 并不方便实现。任何同胚于圆盘的网格与平面上的一个凸区域间必然存在着 调和映射。e c k 等i l 引通过使该映射的d i r i c h l e t 能, 量最小，而构造了一个对非线 南京航空航大大学硕十学位论文 性调和陂射的线性逼近。沿着凸区域边界固定好边赛点后，他们只需求解一 个最小二乘问题，便可获得所有内点的参数化。该调和映射的d i r i c h l e t 能量 被税为全蜀扭曲的度量。然而，他们的权重并不能够保证郯是正值，负的戡 重可麓导致某些三熊形的裁转( 无效静三角化) ，因为这捧麓映射不楚一一歌 射。 旱在1 9 6 0 年t u t t e 就提出了曲组合方法【1 ，其基本思想是把网格的边界映 瓣弱一个乎瑟上瓣凸多透形，蠢蠹点褒以它为中心点静l r i n g 浆平均簸。 t u t t e 证明了该方法所得到的三角形不会相互重叠，但这种基于圈论给出嵌入 虱( g r a p he m b e d d i n g ) 的方法没有充分考虑到原始网格的几何信息，使得参数 伲结暴的变形较大。在t u t t e 款蕊勰上，f l o a t e r l 2 ”通过绘每祭边融烟一个与边 长穗荚的权擅改邋了凸组合方法，提出了其有保形承凸线性组合参数化。值 证明了所得到的参数化结果在增加一些约束后便是一一对应的。他的参数化 方法浠要通过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 ) 的点集参 鼗化上，遘行三缀露鼓数据点黧建及夔蟊熬金1 22 。2 3 l 。l e e 嚣缝合虚季l i 边器把 凸组合方法拓襞到非凸边界的平面参数他处理l 。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 ) 2 5 1 ，并试图建立均值坐标与调和映射间 的联系。文献 2 4 刹甩均值定联，给出了将爨影多边形内鲍任何一点寝示成 它邻域点麓凸线性缀合懿公式。f l o a t e r 谎瞬了秘雳殇毽投燕所取蒋戆参数诧 效果至少可以和保形参数化的效果一样，并且均值权重照容易求得。 h o r m a n n 等 2 6 l 提出了一个全局的非线性具有自由边界的m i p s ( m o s t i s o m e t r i cp a r a m e t e r i z a t i o n s ) 方法。实际上，德饲是逶遘谴缝素载边器点戒为 自由边界来优化参数化的。他们提出了一种在平移、旋转、缩放变换f 均为 恒量的度量，并选取保形参数化作为初始的参数化，迭代优化该度量麓晟小。 虽然可以取褥较好款参数化，德是德豹非线性髓量的度豢霞要勰菲线性躲 茏 仡润趣，因丽这一过程中分怒嚣哼。 d e s b r u n 等1 2 7 1 提出了一个僳面积和保角度两者线性混合的度量，他提供 了一个参数来平衡两因素对最终扭益产生的影响，然后最小化线性混合的扭 夔麓餐函数。s a n d e r 等5 ：8 亵p r a u n 等5 2 94 ；| 入了参数纯拉伸戆度藿叠帮f ， 三角网格曲面参数化技术研究 并扶均匀的边弹力为初始条件开始，优纯迭我。h o r m a n n 簿 3 0 通过半边折叠 方法建立累进网格，给出了一个层次参数化的表示和实现。另外，b e n n i s 等 提出基于微分几何的方法，通过把曲面的等参数曲线映射到参数域完成参 鼗纯，著瀑持溺逮| 攮率( g e o d e t i cc u r v a t u r e ) 不交。s h e f f e r 等l 瓢l 鬟出了一个复 合的纹理映射的概念。该方法首先利用带有权重的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 l 3 2 1 利用她定义的区域扭曲给网格上的每一顶点 设立个饯价投重，著选取其鸯较大豹区域警嚣莲鲸颈点馋先m s t ( m i n i m a l s t e i n e r t r e e ) 的候选顶点，最后由候选顶点集生成m s t 。它的切箭路径实际 上是3 d 图的一个子树，但是因为候选顶点在网格上分布较广，必然导致分 割线过长，扶丽导皴分割处产生参数不连续。 鲍外还育球嚣参数纯方法。凌于平面参数讫的分两治之的佟法本身虢缮 加了参数化的变形，对于很多数字几何处理的应用来讲( 如三维m o r p h i n g ) ， 把封闭网格分割成谳片进行平面参数化方法不仅困难而且不合理，为此，近 死年爨瑷了摄多球甏参数讫方法，避受运穆不必要嚣据癸分裁。 1 3 论文选题依据和研究内密 三角网格参数化是圈沦、微分几何、订露祝图形学、计算枫辅助几何没 计、数字几何处理、算法设计以及程序设计等众多学科的研究领域。目前， 有很多研究机构在傲这方面的工作，其中包括微软亚洲研究院、浙江大学 c a d & c g 国家重点实验窒、鸯簸c a d c a 鼙实验室、美莺懿跨绨大学及虢色 列科技大学等。参数化本身是一个很古老的问题，人们最早把这种技术应用 在测地学、绘图学等领域，随着计肄机的飞速发展和多媒体螺乐应用的推动， 宅在诗繁辍匿形学领域羲l 有举懋轻重鼓邋霞，莠显成为远几年来莺舔学术界 南京航空肮大人学硕十学位论文 一个热点研究问题。 尽管己经出现了不少离散曲面的参数化方法，但对于大型网格来说，仍 然需要速度更快，变形更小的参数化方法。许多方法的参数化效果还需要进 一步提高。分析和研究上述各种方法，在此基础上找到更为快速、优化的结 果，对提高曲面拟合、纹理映射和网格重建等过程的质量有着重要的意义。 本文研究工作得到霍英东教育基金会高校青年教师基金( 编号 0 3 9 1 0 5 3 ) 的支持，对三角网格曲面参数化技术进行了研究，分析并比较了 现肯的几种代表性参数化方法，给出了各自的纹理映射效果：提出了綦于网 格曲面分块的参数化方法；研究了虚拟边界参数化技术。 本文主要研究内容如下： 第一章介绍了三角网格曲面参数化技术及其目前的发展状况和研究成 果，并据此引出本文的选题依据及研究内容。 第二章研究了几种典型的网格曲面参数化方法。比较了各自参数化效 果和变形大小，并给出了纹理映射、曲面拟合的应用实例。 第三章提出了两种在网格曲面分块的基础上对网格曲面进行参数化的 方法。一种方法是分块基础上的局部参数化；另一种是分块基础上的全局参 数化。对于第一种方法，本文在对网格曲面进行简化分块的基础上通过交互 操作生成若干个四边界曲面块，然后给出了一种新的参数化方法分别对各曲 面块进行参数化；第二种方法首先在网格曲面的简化分块基础上将网格曲面 自动划分为若干个多边形网格曲面块，然后提出了一种新的弧氏参数化方法 将各个块的边界映射到平面域中得到多个具有凸多边形边界的平面块，接着 将各个块的内部网格映射到平面上相应的块内，最后得到的是整个网格曲面 的全局参数化，这是一种可以直接对带洞的多边界网格模型进行全局参数化 的方法。 第四章研究了虚拟边界参数化方法，分析了多层虚拟边界层数与变形 大小的关系。 第五章对本文工作进行了总结并指出了进一步研究的方向。 二角网格曲面参数化技术研究 21 引言 第二章典型参数化方法的比较与应用 三角网格参数化就是对于给定的一个三角网格曲面和一个参数域，寻求 一个从参数域上的点到三角网格上点的一一对应映射，在保持参数域上的拓 扑信息与原始网格相同的同时谋求某种几何度量的变形最小化。 曲面的参数化问题可以看作是某个适当的参数域空间到曲面的一一映 射。一般来说，如果参数域本身也是曲面的岳，所说的参数化就是将一个曲 面映射到另一个曲面。目前代表性的参数化方法是将一个与圆盘同坯的网格 曲面参数化到平面。由于逆向工程中离散曲面通常表示为三角网格曲面，所 以参数化过程又是一个分片线性映射过程。 根据审视问题的角度不同，三角网格参数化方法基本上有以下几种分 类：( 1 ) 根据参数域的不同可以分为平面参数化和球面参数化等；( 2 ) 根据网 格的拓扑信息可以分为带边界网格参数化和封闭网格参数化，甚至是任意拓 扑的三角网格参数化；( 3 ) 考察不同的内在几何变量的变形，可以分为保面积 参数化、保角参数化和等距参数化等：( 4 ) 根据求解方式的不同可以分为线 性方法和非线性方法：( 5 ) 根据最后得到的参数化结果，可以分为局部参数 化和整体参数化方法等。 本章将介绍参数化的相关背景以及基本概念和定义，主要研究对象是带 边界的非封闭三角网格曲面的平面参数化方法。重点分析并实现f t o a t e r 的 保形参数化、h a r m o n i c 协调映射以及i n t r i n s i c 的固定边界和自由边界参数 化方法，对这几种算法的参数化结果的变形大小做出了比较，给出了纹理映 射和曲面拟合的应用实例。 南京航空肮大人学硕十学位论文 2 2 参数化基本概念 221 历史背景 希腊天文学家c l a u d i u s p t o l e m y ( 公元前1 0 0 一公元前1 6 8 ) 是历史上所知的 最甲的要画世界地图的人。在他的著作g e o g r a p h y 旧引中，他解释了如何使用 栅格线一一经度线和纬度线来把一个球投影到一张平面的纸上。 就像我们所熟悉的，无法将一个完整的桔子皮毫无褶皱的摊平在桌面上 一样，球体不可能在投影的过程中不产生变形，所以必须要采取一些折中的 办法。图2 i 给出了几个例子。正交投影在两干多年前就为埃及人和希腊人所 知，在这种投影方法中，角度和面积都有改变，但是与投影中心的方向是与 实际相同的；立体投影法是被最广泛使用的一种等角投影法。例如，它保持 角度不变( 以面积的改变为代价) ，也将圆映射到圆上。有时甚至将圆映劓 到一条直线上，而不管这是个多大的圆。立体投影法把斜航线画成一个螺旋 线，斜航线指的是一条具有恒定方向的线，在航海j 二具有重要的意义。1 5 6 9 年，一位佛兰德地图制作9 n g e r a r d u sm e r c a t o r ( 1 5 1 2 一1 5 9 4 ) 希望制作出来可以 让水手们确定航线的地图。他用他的等角圆柱墨卡托投影克服这个障碍。该 地图上，每条斜航线都被画成一条直线。然而立体投影和墨卡托投影都不能 保持面积不变。在1 7 7 2 年，j o h a n nh e i n r i c hl a m b e r t ( 1 7 2 8 一1 7 7 7 ) 以放弃保角 为代价建立了第一个等积投影”。 ( a ) 止交投影 ( b ) 立体投影( c ) 墨p 托投影( d ) 等积投影 n 2 1 地球的投影幽侧 这些投影法都可以看作具有这样一个功能，即映射球面上的一部分到一 个平面域。通常，这种映射的逆向过程被称为参数化。许多的参数曲面原理 二角网格曲面参数化技术i j ：f 究 和微分几阿技术由c a r lf r i e d r i c hg a u ( 1 7 7 7 - 1 8 5 5 ) 在文献 3 5 1 中提出。 22 2 几何背景 假设一曲筒s r 3 相对菜个平面腰2 上的点( “，v ) 的参数表达式为 x 妇，v ) = ( j l ( “，v ) ，恐( “，v ) ，屯似，v ) ) 如采该表达式满足( 1 ) 函数薯，x 2 ，玛光滑连续可微：( 2 ) 商蠡 o x x = 一 孔 d x x 12 ” o v 在每一点都是线性独立的( 他们的叉积x x ，非零) 这两个条件。则我们称 这祥静表达式蔑正翻的。 曲面s 的许多属性由它的第一基本形式描述，这种形式裳示的是s 中一 条瀚线的弧微分的平方。该= 次方形式为： 令 办! = x i t x l ( 如) 2 + 2 x l t x ，_ d u d v + x 2 。2 ( 办) 二 g 醪= x 。x 口， 辨l ，2 ， 舻1 ，2 将对称矩阵的系数安排为： 翔有： ，f g l l9 1 2 1 扭e9 2 2 j 船：f 觑西) i f 矗1 、 7 l 咖 通常，矩阵i 本舟所指的就是第一潺本形式。在规则性的假设餐件下，该矩 阵有一令严格为正匏纷烈式。 g = d e t i = g h g ：一交2 3 一旦至堕至堕盔尘兰堕堂垡堡塞 也是二次形式的判别式。在这种情况下，该矩阵是正定的。系数譬。是二阶 共变张鞋的组成部分，称为度景张最，简单地记为g 。 假设现在s 是一个参数坐标为( m ，v ) 的曲面，为5 到s 。的映射。我们 定义s4 的参数化x 8 爿。x ，因此，任意象点f ( x ) s * 与其相对应的前象点 x s 的参数坐标是一样的。见图2 2 所示。如果参数化x * 是正则的，那么 这样的映射就是可行的。这里要说明的其实就是参数化结果的一一对应。 幽22 从s 到s4 的映射与由s 的参数化x 导山的s + 的参数化x 8 - ，。x 22 3 图、三角网格和参数化 首先引入图论中的一些标准定义，详细论述请参见文献 3 6 。一个( 简 单的) 图g = 6 ( v ，e ) 是由一个顶点集合y = i = l ，) 和一个边集合e 组成 的。其中，e 是所有无序点对( f ，n ( f ，) 所组成的集合的子集，如果顶点i 是 顶点f 的邻点，则( j ，) e 。度4 为点i 的邻近点个数。如果图h 的所有顶点 和边都属丁g 则称图h 为图g 的子图。 如果图g 可以在满足下列条件的情况下被嵌入到平面上，则称图g 是 平坦的： ( a ) 每一个顶点i 被映射到平面僻2 上的一点； ( b ) 每一条边( f ，j ) e 被映射到端点为i 和j 的曲线上： ( c ) 各曲线只能在相同的端点处相交。 图g 这样的平面嵌入图称为一个平面图。一个平面图将整个平面分割 二角网格曲面参数化技术研究 减菪予个连逶区域，这些区域的溺包称为瑟。外部无限溪域称为井瀑蕊。 令g 是一个平丽图，a g 魁包含所有与外部面相关联的所有顶点和边的 一个予集。如果a g 是一个简单的平面曲线，则我们称g 怒单连通的并且a g 郅为g 弱边赛。 如果一个平面网中所有的有界面都是三角彤( 外部丽没有要求) ，则我 们称该平面图是三角化的。 定义l 平恧三是圈格p 是擐所有边都为蠹线的单连逐三莛化平露蕊。 令，为0 g 中所有有界( 三角) 蘑鹃集合，剐0 g = g ( v 。e f ) 。 定义2 三角网格曲面s = s ( g ，x ) 指的怒一个嵌入到垠3 中的所有边都 是直线，所有面部是三角片的单连通三危网格平蕊型g ( v ，e ，f ) ， v = f i = 1 一，n ；，其中顶点壤x = x + i r 3 ：i = l 。彭 。 如图2 3 所示，本文时论的都是单连通三角化平面圈( n 3 ) 。 v 幽2 3 幽、三角网格曲面及参数化 定义3 两个肇连通三焦予甄图g 和g ，魏果缱们的患、边稻嚣存在这 样的一一对应的关系：相应的边连接相应的点；相应的面造接相应的点和边； 边界a q 和a g ，上的点有相同的逆时针排列顺序，则称图g i 翘g 是同构的。 定义4 对予任意阏漕莛瑟s = s ( g ，x ) 豹参数就裁爱我嚣一令与g 阉掇 的平丽三角网格p 。 参数化还要满足一个有效性的条件。通常所指的三角网格是一个可定向 鲍二维漉形三角嘲潦，所以三熊网穆参数化有效性的充分毖要条传是：器媲 丽捂联点秘参数域嗣硌顶点在参数化映射下慧一一对应的f 双射) 。如阕2 4 所示，t i 是x 的有效参数点，而u + 是无效的。 0 蓟一 圜一 毫豪靛空航天天学颟十学墩论文 瞄固“ 2 。3 典型参数化算法 2 3 1 凸多边形的重心坐标 蹬2 4 参数他的有效谯 给定平面凸多边形p ，、顶点为u ，对每个顶点u ，构造一个坐标函数 色隧，如鬃这些函鼗满是以下三令祭传，赠豫这些嚣鼗力荚予p 袭重心坐标， 也常被称为凸组合。 ( a ) 所有的坐标函数均非负，即岛嘲2 0 ，r p ； ( b ) 所有丞鼗戆帮为l ，繇露予_ | 舞有豹f p ，煮b j t l = l ； ( c ) 对于给定的一个值f p ，有u ，岛 f 1 = u 。 螽莱p 篷一个鸯d + 1 个傍翁独立静顶点。，u ，诖“维成的凸多边形，粥 称p 是一个单一多边形。则在上述三个条件的限制下，p 仅存在一组重心坐 标函数如渊。这些函数是线性的并可以通过下面两部分体积之比求得。 这里v o l 指的是括号中d 十1 个点所梅戏的单一多边形的体积。 2 32f io a t e r 保形参数化 给定三角网格魏愆s ( g ，x ) ，x 。 x ，= ( ，只，；) 。i = l ，n 】为网格曲面j 二 的点集，g = y ，e ，f ；t 其中v = f ：江l ， ，嫠点麓彦号蕊集合：e 惫边 的集合，对于任意点对( f ，j ) ，( f 啦，) ，如果，是i 的邻近点，则( i ，j ) e ：f 等卷岽祟 p 二角网格曲面参数化技术研究 是网格上所有三角片的集合。令d 为点i 的邻近点个数，定义参数化网格曲 面s ( g ，x ) 后得到的平面网格为p ( g ，) ，u = u ，= ( u i , v ，) ，i = i ，) 。 f l o a t e r 方法让所有的内部点戏为其一环邻近点魄凸缀合2 “，假没 x ，x ，为三角网格模型的内部点，x 。，x 。为边界点。 簿法步骡如下： ( 1 ) 对边界点按逆时针。方向弦长参数化到正方形上。参数化结果得到 x 。，x 。作为后来篇线性方翟组的已知条件。 ( 2 1 对每个内部点i ，计算权倦元，。 f o ，( f ，) 区e ； 五广k 小4 l ，妻 广l ( j 吨 ( a ) 点x 及其一环邻近点( b ) 映射到平面上构中间结果( c ) 税值计算 幽2 ，5f l o a t e r 参数化投使计算过程 首先对每个渴邦点i 及其1 环邻近点点，点，。，矗进行是嚣参数纯，该怒 部参数化过程就是将x | - x ，x ，x n ，t ，x j d i 按照( 2 - 1 ) 式撂到一个中阅参数 化结果p 。= p p i ，p 2 , - - - , p m l 。此局部参数化过程保持了每个径向的弧长不变， 要求所有的三角片都是非退化的。 l i p 。一p l l = 敝- t ，0 a n g ( p 女，p ，p i 十i ) = 2 r r a n g ( x x ，x “+ i ) ，穹 ( 2 - i ) 亘里堕塞壑盔叁堂堕主：篓堡堕茎 熬中：t = i d i ，舅= 羔埘z g ( x j , x i ，x ) kv 1 ) t k , j ，i i + 1 = x j , ，p 。= p a n g ( a ，b ，c ) 为盘一b 到b - c 的角度。应_ | = j 过襁中可以设鼹切始值p = 0 p ，= ( h ，0 。 在局部参数化的结果上计算权值五，。当吐；3 时，p 芙于a p ，p 。p ，只有唯 一盼一个重心坐标，所求五，即： ja r e a ( p ，p 2 ，p 3 ) 矿磊而麓面 ja r e a ( p i ，p ，p 3 j 以瓦石麓茹 ja r e a ( p i ，p ! ，p ) 以矿磊面荔 僚大多数清况下d i 3 ，遮时对于每个国三个邻近点所缀成的三霸形， 如果它包含点p 在内，则按d 。= 3 的情况计算一+ 次权值，如图2 5 ( c ) 所求。全 部计算完毕后，将每个邻近点在艇个许算过稷中磐到的所胄权值平均履褥到 最终该邻迓，墓静投穗焉，。 ( 3 ) 每个内部点都是其邻近点的凸组合： u ：= 磊+ u j ，i = i ( 2 2 考虑到u ，的两个参数比，和_ 1 ) | _ ，要解两个线性方程组a u ；包，a v = ，最 终德裂参数化结袋。翔果计算避程中取玉，= l d i ，( i ，d e ，剐为t u t t e 赡重 心参数化方法，也称均匀参数他方法。 23 3h a r m o n ic 参数化方法 h a r m o n i c 参数诧方法骓曩，又称为诵季漱翡。它将三辩阏捂模型嘻： 翘每 一条边都看作为一个弹簧，先将三角网格的边界映射到预先定义好的多边形 上，然后通过最小化整个三角网格模型的弹性势能来参数化内部空间点。 逡取三爱弼掇模型s ( g ，x ) 上撵令边器患x ，x 。，馋必姨嚣熨平甏域主 的角点，分剐将遮些角点映射别个平面n 边形p c r 2 的备顶点上。平面多 边形p 的选取算法怒：将p 的n 个顶点置于一个圆周上，并使两相邻顶点所 对的圆心蹙与网橇曲面边界上对应酶两耜邻热点所连的折线长度成正比。也 三燮! 塑匣量塑些些查塑窒 可以疆摇需要壹接将尹壤为正方形、正三麓形或其链凸多边形等等。如蘑 2 , 6 所示，割革机的原始三角嗣格模型边界被耿射到一个平面多边形上。 ( a ) 三角耀格模燃 ( b ) h a r m o n i c 姨辩 涮26 割革辘三穗网格摸爨的h a r m o n i c 映射 将网洛盐面s 看成一个弹疑系统，在边壤e 中的每一条边上放疑一根 弹簧。三缝丽撂魏嚣s 上懿琢患映菇至l 二维乎蠢域p 上豹交彩缝荛1 2 1 ： 。( u ) = 专。t l u i - u l82(2-3) 1 ，k e 蒺中h i , l j 分舅为边( ，歹) 鲍两个顶点鼷辩弼产中静位鬻，边赛点豹位置已 经确定。k l , ，为边( f ，) 的弹性系数。为了尽可能反映初始网格s 中每个边的 长度及糟镪亟的形状，蠢。取为： 赶寻( 置q + 巧2 、一置，) ，4 。自+ ( 譬女2 + 譬，女：一t j ) t a i 。： ( 2 4 ) 其中：k l , k ：为边( i ，) 的麟个楣邻蟊的冀外嚣个顶点，岛i 表示边缘，) 的 长发，a i 。t 表示三角片f ( i ， ) 的面积。k i d 有可能会跫个小于零的负数， 这就会导致参数化的不成功，例如产生重叠的三角片。猩这种情况下， 女 可以敬为平鹭津愁蓉数。 采用拉格朗舀乘子法解( 2 3 ) 式使得磊。( u ) 最小，得到网格曲萄s 中所 有顶点映射到p 中腐的坐标位鬣。具体解法示意如下： 假设某三角瞬燎鳆面映射劐平面后如黧2 7 所示。p 憋四个焦点依次为 鸢京航空靛大大学硬士学 ：i = 论文 u l ( “l ，v 1 ) ，u ! ( “2 ，比) ，t l t 6 ( u ，v 6 ) ， “1 ，v i ，v ：，v 6 ，“7 ，v 7 为已知量。 壶予u ，在u 。窝u ，豹连线。至，所戮寄 v 5 一b ，= 0 。其中k 为u 6 、u 。连线的斜率。秘播 式( 2 3 ) ，变形能e 虮。为： t 2 , s u ， 筮2 7 平嚣潮梧示意蚓 毛。川嚣妻 七旧( 髓2 一u i ) 3 + 足l ! ( v ! 一v i ) 2 + 足l ，3 ( 比3 一“i ) ：+ 尼1 3 ( 屹一u ) 2 + 七i 。4 ( 据4 一“i ) 2 十支1 4 ( v 4 一v i ) ：十盘2 3 ( 越3 一“! ) ! + 是! ，3 ( b v ：) 2 + k 3 5 ( k 5 一酣3 ) 2 + 惫j 5 ( 咚一如) 2 + 囊2 、7 掰7 一群：) ：+ 垂2 。7 ( 咚一v ：) ：+ 也4 ( “4 一u 3 ) ：十如4 ( v 4 一b ) 2 十屯7 ( “7 一t t 3 ) 2 十七3 ，7 ( 屿一v 3 ) ：+ ( 2 5 ) k a , 5 ( “5 一“4 ) 2 + 盘4 5 ( v 5 一v 4 ) 2 + 盘4 ，6 陋6 一“；) ：+ 七4 、6 ( 吒一v d 2 + 志5 。6 傅6 一艇5 ) ! 十毛，5 ( 飞- v 5 ) 2 十盘s ，7 ( 挺7 一u s ) 2 十毛，7 ( 码一码) 2 + 1 ( m 6 一a i ) 2 十k 16 ( v 6 v i ) 2 】十 ( ”5 一k u 5 ) 萁中盖为控据鞠蜀黍予，如暴袁多令边器点列嚣弓 入多令控褥赣霜黍予。 将能量函数e 胁，。分别对未知鬣，屹，d 4 u ，1 1 5 v ，五求偏学并令其为零 可得方程姒： 垂 3 + 壶：，3 + 包4 壳3 j 毛，7 ) 王奄一g u i 一垂2 ，3 拦2 一k 3 ，4 啦一意3 j 群s 一毛，7 u 7 = 0 ( 瓠3 十奄2 ，+ 屯4 + 奄3 ，5 + 露3 7 ) 一k i , 3 v i k 2 3 v 2 一惫，4 v 4 一是3 ，5v 5 一凳3 7 v 7 = o ( _ 4 十七3 4 + k 4 5 十七4 6 ) “4 一k i , 4 u i k 3 4 u 3 一5 u 5 一k 4 ，6 h 6 = 0 ( 毛4 十矗3 4 + 垂4 ，+ 盘4 ，6 ) v 4 - k i 。4v 一岛4 毪一七 。5 v 5 一恕，6 = 0 ( 2 6 ) ( 5 + 惫4 5 毛 十如7 ) 5 一东3 5 掰3 一5 拜4 一毫5 魄一7 掰? 一定五；0 ( 女35 + t 4 。5 + 岛6 + 5 7 ) v 5 一k 3 , 5 v 3 一 4 5 p 4 一k 5 6 v 6 一k s 7 v 7 一五2 0 v ；一k u t = 0 解方程缀( 2 6 ) 就可褥到u 3 ，u ；，h s 静位置。 分析方程组( 2 6 ) 可以发现该方程具有明显的规律性。对未知量“，求导数 得到的等式中，毪的系数是u 。的所旃邻接边弹性系数的和，其余各项为顶点 u ，戆墨邻接点夔“分墓，系羲是稳应各留接边翁铎淫系鼗。黧莱滚煮还瀵是 三角网格曲面参数化技术研究 约束方程，则还应有拉格朗日乘子项，系数是约束方程的斜率。对未知量v ， 求导得到的等式的规律与“基本相同，只是拉格朗日乘子项的系数均为l 。 该方法映射后所有顶点、边、面的连接关系保持不变，是一个基于变形 能黾最小的分片线性映射，但它同样需要先固定边界参数。 2 34n tr in s i c 参数化方法 d e s b r u n 等【2 7 i 的i n t r i n s i c 方法既可以固定边界参数化也可以通过边界约 束得到自然边界的参数化结果，该方法综合了离散等角参数化和离散等积参 数化这两种参数化方法，考虑了两种变性能：d i r i c h l e t 能量和k a i 能量。通过 最小化这两种变性能得到参数化结果。 一环邻近点的d i n c h l e t l 范量表示为： e 。= c o t u 。一u ， 居n ( ，1 k a i 能量表示为 ( 2 7 ) ( 2 - 8 ) 其中，( f ) 为点i 的一环邻近点集合，h u ，l 为边( f ，j ) 在平面域p 内的 长度，k - x j i 为三维网格曲面s 上边( f ，j ) 的长度，畅、岛为s 中边( f ，j ) 所 在三角片中与边( i ，) 不相邻的角，、磊为s 巾边( i ，j ) 所在三角片中顶点为 。的角，如图2 8 所示。 幽28 三维一环邻近点及其相应的平面映射 背 南京航空航天人学硕十学位论文 最小化d m c h l ec 能量得到： 鬻= 。，馨。t ”。t 帆一- - 步。 ( 2 - 。) 最小化k a 侑2 量得到 瓦b e z2 磊，警斧1 剐 陋 式巾各角度的定义如图2l o 所示。综合考虑这两种能量e = a e a + 岸乞，建市 线性与程： 0 删i 啦纠。c 概咖 = c 口 iu 幻“，m 叫 l 幻“础9l 五，为两个任意实数，可以简单地取为1 。c 为包含所有平面域p 边界点位置 信息的向量。这是一个稀疏矩阵，其系数为： m u a = c o t ( 。o ) 十c o t ( 羼) 一m ： o ( c o t ( ) + c o t ( 6 0 ) ) 小 - z 。m m o 解( 2 一1 1 ) 的线性方程组得到i n t r i n s i c 的固定边界参数化结果。i n t r i n s i c 参数 化方法可以固定边界参数化，也可以通过边界约束得到自然边界的自然化。 为了得到自然边界的参数化结果，需要对j 二面的线性方程有所更改。 d e s b r u n 等指出：对于三角片上某点的d i r i c h l e t 能量的微分等同于将该点对面 的边旋转9 0 度( 如：( 石，y ) _ ( 一y ，工) ) 。因而，自然边界条件就应该与三角网 格的边界有着相同的属性。对于边界点“将其所有邻接三角片的d i r i c h l e t 能曼微分相加，得到自然边界参数化的边界约束条件式( 2 1 2 ) 加入到( 2 11 ) 式的方程中解得自然边界参数化结果。其中尺”代表逆时针旋转9 0 度。 亘_ 舵 ， ，- x = z u m ， 色 = 虬 ， 三角网格曲面参数化技术研究 c o t c c ( u 一u ) + c o t p ( u i u j ) _ r g o ( u 女 b ka n k 2 4 参数 芑算法跑较 24 1 参数化变形的度量 ( 2 一1 2 ) 参数亿交彤戆大套是囊量参数诧舞蓼敬标漆。褪觉上驹乎潆效栗好坏爱 衡量参数化变形的一个直观