（计算数学专业论文）同构平面三角网格和平面多边形变形的研究.pdf

摘要 变形，是指从初始物体到目标物体的连续、光滑、自然的过渡( 这里的物 体可以是数字图像、曲线、曲面、网格等) 。变形在许多领域有着十分广泛的应 用，如计算机图形学、动画设计、工业造型、科学计算可视化、电影特技等。 本文对同构平面三角网格的变形和平面多边形的变形进行了研究，主要的研究 结果如下： 1 ) 同构平面三角网格的变形：提出了具有不同凸边界的同构平面三角网格 的保凸变形方法。该方法结合了内在解算法和凸组合变形算法，指出并证明了内 在解算法具有保持中间网格边界的凸性这一优良特性。本文方法能够保证网格边 界在变形过程中始终保持凸性，且任意时刻的中问网格与初末网格同构，即不产 生自交现象。同时本文方法实现了两个凸多边形的保凸变形。 2 ) 可避免自交的平面多边形的变形：提出了基于形状特征的嵌入网格的平 面多边形变形方法。该方法将初末多边形嵌入到以其放大凸包为边界的同构平面 三角网格中，采用本文提出的同构平面三角网格的保凸变形方法对所得网格进行 变形。与g o t s m a n 和s u r a z h s k y 的方法相比，本文方法考虑了初末多边形的几何 轮廓及其差异性，故变形更加自然，同时本文的同构剖分算法大大减少了额外顶 点的数目。 3 ) 可局部修改的平面多边形的变形：提出了平面多边形的离散曲率插值变 形方法。该方法引入c a r m e l 和c o h e n 的离散曲率的定义，给出了离散曲率插值 变形的算法。在此基础上，给出了局部修改算法，该算法具有很强的直观性，能 够较好地根据用户的要求和意愿对多边形进行局部修改。本文方法具有简单有 效、多边形边长总长度单调变化和局部可修改性的特点。 关键词：变形，同构平面三角网格，保凸，凸组合，凸多边形，内在解，避 免自交，形状特征，凸包，局部修改，离散曲率 a b s t r a c t m o r p h i n gi st h ec o n t i n u o u ss m o o t ha n d n a t u r a lt r a n s f o r m a t i o no fas o u r c eo b j e c t i n t oat a r g e to b j e c t ，w h e r et h eo b j e c tc a nb ean u m e r i c a li m a g e ，c u r v e ，s u r f a c e ，m e s h ， e t c m o r p h i n gh a sv e r yw i d e u s ei nm a n ya r e a s ，s u c ha sc o m p u t e rg r a p h i c s ，a n i m a t i o n d e s i g n ，i n d u s t r i a lm o d e l i n g ，s c i e n c ec o m p u t a t i o nv i s u a l i z a t i o n ，f i l ms t u n t ，e t c t h i s p a p e rm a k e s r e s e a r c h e so nt h em o r p ho fc o m p a t i b l ep l a n a rt r i a n g u l a t i o n sa n dt h a to f p l a n a rp o l y g o n s ，a n d t h em a i nr e s u l t sa r ea sf o l l o w s ： 1 ) m o r p h o f c o m p a t i b l ep l a n a r t r i a n g u l a t i o n s ：t h i sp a p e rp r e s e n t s a c o n v e x i t y p r e s e r v i n g m e t h o df o rm o r p h i n gc o m p a t i b l ep l a n a rt r i a n g u l a t i o n sw i t h d i f f e r e n tc o n v e xb o u n d a r i e s t h i sm e t h o dc o m b i n e st h ei n t r i n s i cs o l u t i o na l g o r i t h m a n dt h ec o n v e xc o m b i n a t i o nm o r p ha l g o r i t h m ，s h o w i n gt h a tt h ef o r m e rh a sa n e x c e l l e n tp r o p e r t yo fp r e s e r v i n gt h ec o n v e x i t yo ft h ei n t e r m e d i a t et r i a n g u l a t i o n s b o u n d a r i e s ，i tg u a r a n t e e st h a tt h eb o u n d a r yp o l y g o n so ft h et r i a n g u l a t i o n sp r e s e r v e c o n v e x i t ya l lt h et i m ed u r i n gt h em o r p h i n g ，a n dt h a tt h ei n t e r m e d i a t et r i a n g u l a t i o na t a n y t i m ei s c o m p a t i b l e w i t ht h es o u r c ea n d t a r g e tt r i a n g u l a t i o n s ，i e f r e e o f s e l f - i n t e r s e c t i o n a tt h es a m et i m ei tr e a l i z e sac o n v e x i t y - p r e s e r v i n gm o r p ho ft h e t w oc o n v e x p o l y g o n s 2 ) i n t e r s e c t i o n - f r e em o r p ho fp l a n a rp o l y g o n s ：t h i sp a p e rp r e s e n t sas h a p e f e a t u r eb a s e da n dt r i a n g u l a t i o n se m b e d d e dm e t h o df o rm o r p h i n gp l a n a rp o l y g o n s t h i sm e t h o de m b e d st h es o u r c ea n d t a r g e tp o l y g o n s i n c o m p a t i b l ep l a n a r t r i a n g u l a t i o n sw h o s eb o u n d a r i e s a r e t h e m a g n i f i e d c o n v e xh u l lo f p o l y g o n s r e s p e c t i v e l y ，t h e nm o t p ht h ee m b e d d e dt r i a n g u l a t i o n sw i t ht h ec o n v e x i t y p r e s e r v i n g m e t h o df o rm o r p h i n gc o m p a t i b l ep l a n a r t r i a n g u l a t i o n sp r e s e n t e di n t h i sp a p e li n c o n t r a s tw i t ht h em e t h o do fg o t s m a na n ds u r a z h s k y , t h i sm e t h o dc o n s i d e r s t h e g e o m e t r i cc o n t o u r sa sw e l la st h ed i f f e r e n c e so ft h es o u r c ea n d t a r g e tp o l y g o n s ，s ot h e m o r p h i sm o r en a t u r a l o nt h eo t h e rh a n d ，t h ea l g o r i t h mi nt h em e t h o d f o rc o m p a t i b l e t r i a n g u l a t i o nr e d u c e st h en u m b e ro fs t e i n e rv e r t i c e sg r e a t l y 3 ) l o c a l l ym o d i f i a b l em o r p ho fp l a n a rp o l y g o n s ：t h i sp a p e rp r e s e n t sam e t h o d i i f o r m o r p h i n gp l a n a rp o l y g o n s v i ad i s c r e t ec u r v a t u r e i n t e r p o l a t i o n t h i s m e t h o d e m p l o y st h ed e f i n i t i o no fd i s c r e t ec u r v a t u r eo fc a r m e la n dc o h e n ，a n dp r e s e n t st h e a l g o r i t h mf o rm o r p h i n gv i ad i s c r e t ec u r v a t u r ei n t e r p o l a t i o n o nt h eb a s i so ft h i s ，a l o c a l l ym o d i f i a b l ea l g o r i t h mi sg i v e n ，w h i c hi sg r e a t l yi n t u i t i v ea n de n a b l e su s e r st o m o d i f y t h ep o l y g o n sl o c a l l ya c c o r d i n gt ot h e i rr e q u i r e m e n ta n dd e s i r ep r e f e r a b l y t h e m e t h o di sc h a r a c t e r i z e db y s i m p l e n e s s ，a v a i l a b i l i t y , m o n o t o n ec h a n g eo ft o t a ll e n g t h o f p o l y g o n s i d e sa n dl o c a lm o d i f i c a t i o n k e yw o r d s ：m o r p h i n g ，c o m p a t i b l ep l a n a rt r i a n g u l a t i o n s ，c o n v e x i t y p r e s e r v i n g ， c o n v e x c o m b i n a t i o n ，c o n v e xp o l y g o n ，i n t r i n s i c s o l u t i o n ，i n t e r s e c t i o n f r e e ，s h a p e f e a t u r e ，c o n v e xh u l l ，l o c a lm o d i f i c a t i o n ，d i s c r e t ec u r v a t u r e 1 1 1 西i l l 业大学硕士学位论文 第一章绪论 1 1 变形概述与研究背景 变形( m e t a m o r p h o s i s 或m o r p h i n g ) ，也称为形状调配或融合( s h a p eb l e n d i n g ) 、 形状平均( s h a p ea v e r a g i n g ) 等，是指从初始物体到目标物体的连续、光滑、自 然的过渡( 这里的物体可以是数字图象、多边形、多面体等) 。变形技术在许多 领域有着十分广泛的应用，如计算机图形学、动画设计、工业造型设计、虚拟现 实、科学计算可视化、电影特技制作等领域。变形应用于计算机动画，可以减轻 美工师的手工劳动；在产品造型设计中，应用变形可以把不同造型特征相互交融， 产生新的系列造型：变形应用于电影制作，可以产生奇特的电影特技效果，给人 以美的视觉享受。随着现代信息社会和变形技术的不断发展，变形将会有更加广 泛的用途。 变形通常需要解决两个关键问题，第一是建立初末两物体的元素( 如顶点， 边等) 之间的对应关系，称为对应问题( c o r r e s p o n d e n c e p r o b l e m ) ，第二是通过插 值初末两物体的对应元素产生中间状态，称为插值问题( i n t e r p o l a t i o nd r o b l e m ) 。 目前国内外已有许多有关变形的研究成果，给出了解决变形问题的比较有效的算 法，但遗憾的是，变形是一种视觉效果，与人的审美标准密切相关，主观因素很 大，故对于变形的两个问题什么是成功的解决方案，还没有正式明确的定义，但 研究者普遍认为一个令人满意的变形应满足以下三个条件： 1 、变形过程中产生的中间状态的一些特征，如边长、夹角、面积等应保持单 调平滑的变换。 2 、中间状态的边界应尽量保持光滑。 3 、初末物体所共有的一些特征在变形过程中应该保留。 目前已有许多种变形算法，其类型及其复杂性在很大程度上取决于物体的表 示方法和相应的数据结构，因此不同的表示方法所采用的变形算法也不尽相同， 大致分为以下三类： 1 、基于体元表示： 物体的体元表示即一个三维物体表示成定义在整个3 d 空间上的函数的水平 垦鍪三些奎兰墅主兰壁篓苎一 集。暇设镌俸表示受点豢p ，谈褥广( p ) = e ，雯鼙，( p ) = e 帮秀该物体靛体元表示。 2 、纂予e l e v a t i o nm a p 表示： 该表示法在地貌造型和图像变形中有着重要的应用。例如2 d 图像可以看作 怒在豫索格上密e l e v a t i o nm a p 定义瓣颜恕映射。 3 、撼于边界表示： 耪镕静逮赛袋示是攒物落鑫l 多逮影( 多蟊体) 耱参数篷线( 藏瑟) 魏祥条鎏 线( 曲面) 这两个主要模型来构成其边界的表示方法，有相当多的物体是以其边 嚣表示酶。 1 2 国内外研究综述 曩翦翅内辫磺究者逶喾主要磺究变形鹣某一个阕题：或主要磷究变形戆对应 问题，其插值问然则用简单的顶点线性搔值法来解决：或在假设j c 寸应关系已经给 定熬蓑撵下对捶馕润题避 亍疆究，也有一些骚究密瀚时磷究这嚣个阉题。其中对 应问题的研究相对较少，熙多的研究成果则是插值问题方面的。 1 2 对应问题 在变澎对应阏题麴磺炎中，簿一秘篱法郝套有其适蠲蓖疆。【l 】中s e 建e r b e r g 綦于一种物理模测，把平面多边形的边餐作为金属丝，邋过使得初始多边形经过 弯鼗或毒髂臻交舞嚣标多逮形辩掰终豹凌最小慕建立秘寒多这影凌点熬对壅关 系，该方法适用于两个相似的平词多边形；k a n a i 在其文献 2 1 中幂u 用h a r m o n i c 映 麓使彳葶裙始帮鹜搽多萄舔瓣格与糖应静平面网穰襁对应，并将这两个平藤网格羹 懿进而建立初末多面体的对应关系，这种方法适用于两个同胚于3 d 球或2 d 圆盘 的可以不相似的多面体；c 3 】中g r e g o r y 用特征点犯多面体阿格对成分片，通过对 分片的对应，建立两多碟体的对暾关系，该方法遥用于硝个不相似的同联敬篱单 ( 或非简单) 多谳体； 4 】中d e c a r l o 利用初末曲筒上的稀疏控制网格建立亏格不 嗣熬选瑟之闯躲对瘦关系，该方法逶弱予辐蛰绩约虿弱瓣鼗嚣。 1 2 2 插值问题 对交形插俊阏题的研究常常戆在假设对应关系已经确立的前提下进行的。【5 】 中b e i e r 翻n e e l y 提出一种图像变形的方法，该方法基予手申影赡场，遴过在初 西北工业大学硕士学位论文 米图像中使用若干条对应的辅助线来完成图像的对应和插值，从而实现图像变 形。这是一种较成功的图像变形方法，但在有些情况下会出现病态，即某些时刻 的中间图像产生重叠、相交。在解决多边形、多面体、曲线和曲面的插值问题的 方法中，一个最简单的方法是顶点线性插值法，这种方法生成速度快，但变形中 可能引起边界的非正常萎缩，产生自交，一些简单的几何特征如长度、角度等不 能一致的变化，原因是各个顶点在变形过程中缺乏联系，其路径是相互独立的。 【6 中k a u l 和r i o s s i g n a c 同时研究变形的对应问题和插值问题，提出了基于 m i n k o w s k is l l l t l 的算法，使得这两个问题同时得到解决但该方法很容易混淆物 体的相似部分。1 9 9 3 年s e d e r b e r g 和王国瑾等在 7 中提出关于平面多边形变形的 内在解算法，1 9 9 8 年建立了用于空间多边形或多面体变形的新算法m s i ( 见【8 ) 。 该方法首先找出初未多边形或多面体的顶点在局部直角坐标系中的极坐标或者 球面坐标，即内在集，通过线性插值其内在变量重构出中间状态。这种方法能够 体现多边形或多面体的内在结构特征，且生成速度快，取得了很好的变形效果， 但是由于边界的各个部分之间缺乏联系，没有明确的考虑到多边形或多面体的内 部，所以许多情况下边界容易自交，内部面积( 体积) 在变形中易产生扭曲。基 于这种考虑，s h a p i r a 和r a p p o p o r t 9 币l j 用多边形的星骨架表示方法得出一种插值 方法，该方法首先构造初末多边形的同构的星骨架，然后线性插值相应的元素如 边长、角度等得出中间多边形。由于它既考虑到了多边形的边界，也考虑到了其 内部，故减少了变形过程中产生自交的可能性。a l e x a 1 0 将初末物体分解成同构 的单纯复形，在两个对应单纯形之间定义仿射变换，并将其表示威旋转变换和伸 展变换的复合，将这两种变换线性插值得到期望的仿射变换，然后通过使得中间 物体在最小二乘的意义下逗近该期望的仿射变换，从而达到扭曲最小的效果。该 方法考虑了物体的内部，且变形具有刚性，因而变形过程比较自然，且不易产生 自交。 1 1 1 提出了一种平面参数曲线的变形方法它基于曲线微分几何的有关理 论，即以弧长为参数的平面曲线除了一个刚体运动变换外，由其曲率完全决定。 通过线性插值初末曲线的曲率，重构出中间曲线，并以分段插值建立对应关系。 该方法产生的变形过程不仅光滑，而且利用了内在曲率形状特征，因而变形效果 是令人满意的。但是，这种方法仅适用于以弧长为参数的曲线变形，一般参数曲 线须重新参数化为弧长参数，而且其中重构曲线的积分表达式对于一般的曲率没 一 翌苎二、业奎兰堕主兰垡兰兰 一 _h，-_-_-_-_-_一 有解析解，故变形复杂度大，实现比较困难。f l o a t e r 和g o t s m a n 1 2 】基于平面三 角网格的内顶点的凸组合表示方法，提出了具有相同凸边界的同构三角网格的变 形方法，称为凸组合变形，该方法能够使得中间三角网格始终与初末网格同构， 不产生自交，且变形过程连续光滑。受 1 2 1 方法的启发，g o t s m a n 和s u r a z h s k y 1 3 】 给出了可避免自交的平面简单多边形的变形方法，它将初末多边形分别嵌入到两 个具有相同凸边界的同构平面三角网格中，通过采用 1 2 1 的方法对这两个三角网 格进行变形，以此实现多边形的变形。该方法首次彻底的解决了平面多边形的变 形中产生自交的问题，并且应用于图象变形，也可咀保证中间图象不产生折叠。 g o t s m a n 和s u r a z h s k y 在后来的研究中提出了可控制的同构平面三角网格的变形 方法 1 4 ，s t i c kf i g u r e s 的变形方法 1 5 1 ，同构三角网格的内在变形 1 6 ，使得这种 基于同构三角网格变形的方法得到了进一步完善。但是这种嵌入相同凸边界的同 构平面三角网格的变形方法，没有考虑初始和目标多边形或更一般的s t i c kf i g u r e 的几何形状，因面变形效果未必令人满意，而且在同构割分时使用的额外顶点较 多，故算法的复杂度较大。 1 3 论文研究内容及结果 类似于国内外对变形插值问题的研究思路，本文将在假设初末物体的对应关 系已经确立的前提下对变形的插值问题进行研究。本文的若干研究结果，有的综 合了几种已有算法的优点，有的则针对已有算法的缺点与不足，受其启发，另辟 溪径，既克n t 原有算法的缺陷，又得到了一些意外的令人满意的结果。本文的 研究内容及研究结果如下： 同构平面三角网格的变形 提出了具有不同凸边界的同构平面三角网格的保凸变形方法。该方法结合了 两种已有的算法 8 】和 1 2 ，指出并证明了【8 】对于凸多边形的变形具有保持凸性的 性质，利用【8 的这一优良特性对网格边界进行变形，网格的内部顶点则采用f 1 2 】 方法来实现。本文方法能够保证网格边界在变形过程中始终保持凸性，且任意时 刻的中阃网格与初末网格同构，即不产生自交现象。 可避免自交的平面多边形的变形 提出了基于形状特征的嵌入网格的平面多边形变形方法。该方法将初末多边 西北工业大学硕士学位论文 形按一定的算法嵌久到以其放大凸色为逸赛静嗣梅平面三角两袼孛，然舞采雳本 文提出的同构平面三角网格的保凸变形方法对所得网格进行变形，以实现多边形 的变形。本文方法实现了平面多边形的可避免自交的变形，且考虑了视末多边形 的几何轮廓及其茇异性，敬变形盟加自然，同时本文豹凰构割分簿法大大减少了 额外顶点的数目，提高了算法的速度。 胃爱部修改静平藩多逮彩斡交形 提出了平面移边形的离散曲率插值变形方法。该方法弓l 入【1 7 】中的离散曲率 的定义，将参数曲线的交形问题转化为平面多边形的变形问题，给出了平面多边 形的裹散魑率插馕变形箕法。在此基础土，本文绘出了局部修改算法，该算法具 有很强的直观性，能够较好地根据用户的要求和意愿对多边形进行局部修改。本 文方法其蠢麓萃蠢效、“魏线慧弧长”摹落交纯零】羯部可修改瞧熬特熹，鼗褥了 较好的变形效果。 两北t 业大学硕士学位论文 第二章同构平面三角网格的变形研究 如1 2 。0 节所述，目前有关同构平面三角网格的变形研究，有a l e x a 1 0 方法，f l o a t e r 和g o t s m a n 1 2 的凸组合变形方法，g o t s m a n 和s u r a z h s k y 的可控 制的同构平面三角网格的变形方法【1 4 ，同构三角网格的内在变形 1 6 】等。在计 算机图形学中，平面三角网格被用来作为曲面和平面形状的参数和表示方法，因 而研究同构平面三角网格的变形方法，对于这一类物体的变形具有重要的意义。 2 1 同构平面三角网格 两个平面三角网格同构( i s o m o r p h i c ) ，或者龅相容( c o m p a t i b l e ) ，是指它们 是拓扑等价的。下面将介绍同构平面三角网格的相关知识。 2 1 1 同构平面三角网格的判断准则 在图论中，两个简单图g 0 和g 。同构( i s o m o r p h i c ) ，是指g o 和g 的顶点集合 和边的集合之间分别存在一一映射，使得对应边连接对应的顶点。由于本文所涉 及的图都是简单图，故以下都简称为图。 图g = c ( v ，e ) 称为平面( p l a n a r ) 的，如果它可以按以下方式画在平面上： ( i ) 存在一一映射p 将顶点集v 映射到平面上的一个互不重合的点集。 ( i i ) g 的每条边 f ，_ ， e 对应于以p ( i ) 并f l p ( j ) 为端点的简单曲线。 ( i i i ) 这些简单曲线仅在其共同端点处相交。 此时图g 称为平面图( p l a n a rg r a p h ) ，其平面表示称为平图( p l a n eg r a p h ) 。由以上 可以看出，一个平面图与其平图是同构的，且其平图不唯一。 平面三角网格( p l a n a rt r i a n g u l a t i o n ) t = r ( c ，p ) ，是指其每个有界面仅含三 条边且每条边由直线段表示的简单平图。两个平面三角网格瓦= t ( g o ，p o ) 和 正= 丁( g 。，p - ) 同构( i s o m o r p h i c 或c o m p a t i b l e ) ，是指它们是拓扑等价的，其判断 准则如下： ( 1 ) 图g 0 和g ，同构。 ( 2 ) 瓦和互的有界面之间存在一一对应，且对应的有界面连接对应的顶点。 ( 3 ) 边界瞩和a g l 具有相同的方向( o r i e n t a t i o n ) ，即o g o 手1 1 a g i 存在两个相 对应的顶点序列，它们相对于其内部有界面都呈逆时针方向。 ( 3 ) 瓦和五的所有对应的有界面具有相同的方向。 注意：其中( 3 ) 与( 3 ) 是等价的。设有晃面的有序顶点依次为( ，f 2 ，) ，其方向 ( o r i e n t a t i o n ) 有逆时针和顺时针两种：面的方向为逆时针是指其顶点，f 2 ，按 照这样的顺序相对于面的质心呈逆时针方向，面的方向为顺时针是指i ，j ：，i 。相 对于面的质心按顺时针方向排列。图2 1 给出了平面三角网格同构和不同构的例 子。 囟国囟函 图2 1 四个平面三角网格中，( b ) 与( a ) i 司构，( c ) 和( d ) 均不与( a ) i j 构，其中( c ) 和( a ) 不满足判断准则的 ( 1 ) ( d ) 和( a ) 不满足判断准则的( 3 ) 或( 3 。) 。顶点对应关系用数字卜9 来表示。 给定两个平面三角网格，检验其是否同构是比较容易的，只要考察是否符合 上述的判断准则即可，但是，对于给定的两组顶点要寻找其同构三角网格则是比 较困难的，甚至有时是不存在的。已有研究者证明出其同构三角网格的存在性是 一个n p 问题，有时需要添加一定数量的额外顶点才能构成同构三角网格。 2 1 2 凸组合映射 f 矗r y 1 8 用归纳的方法从理论上证明了任何一个平面图在同构的意义下都 可以表示成直线段的形式。因此，对于任何一个其所有有界面都只含三条边的平 面图g ( 称为平面三角图) ，存在一个点序列p ，使得t = r ( g ，p ) 为平面三角网 格。后来，t u t t e 1 9 采用重心映射的方法给出了以上结论的构造性证明。首先将 平面图g 的边界顶点映射到平面上的任意一个凸多边形，该凸多边形与g 的边 7 两北丁业大学硕士学位论文 界具有相同的顶点数目和顶点顺序，然后其内部顶点按这样的方式映射到平面 上：每一个内部顶点的像是其相邻顶点的像所构成的多边形的重心，见图2 2 ( b ) 。对于t u t t e 的这种方法，f l o a t e r 在 2 0 中作了推广：每一个内部顶点的像 可以是其相邻顶点的像所构成的多边形的任意严格凸组合( 所有凸组合系数严格 为正) ( 见图2 2 ( c ) ) ，称为凸组合映射。 & 圆够 瞄22 平血幽( a ) 表不为直线段形式( b ) 与( c ) ，其中( b ) 采用t u t t e 重心映射方法得到，其边界为凸多边形， 内顶点为其相邻顶点的重心，( c ) 采用f l o a t e r 凸组合映射方法其内顶点为相邻顶点的任意凸组合。 2 1 2 1 凸组合映射的数学描述 由于本章主要研究平面三角网格，故这里主要对平面三角图的直线段表示进 行阐述。设g = o ( v ，e ) 为一平面三角图，i v l _ n 。设_ 为其内顶点的集合， 为边界顶点的集合，i 巧l = ，i i = n - n = k ，并设巧= 1 ，2 ，门) ， 2 n + l ，”+ 2 ， a 此时g 的直线段表示即寻找映射p ：p ( o = p ，= ( ，只) ， i v ，使得丁= t ( o ，p ) 为平面三角网格。对于每个边界顶点f ，定义p ( f ) ：a 为一七条边的凸多边形的顶点，且顶点p j 的顺序与掰的相同。对于每个内部顶 a i 巧，选取相对于其相邻顶点任意严格为正的凸组合系数丑，竹( f ) ，”( ，) 为 与i 相邻的顶点的集合，即 。= o ，( f ，) e e ， ， o ，( f ，) e ， 窆丑，：1 ( 2 1 ) ，= i 定义a ，p ：，以为下列线性方程组的解 只= 丑p ， j t l 这样映射p 就找到了，所得的平面三角网格，= t ( g ，p ) 就是g ：o ( v ，e 1 的直线 ， 耍塑王! ! 叁茎麓主兰笪篓苎一 段裂不。 对予摹l o 贰e r 魏凸组会浚瓣方法，s u r a ：z h s k y 稿g o t s 蝴在【l 霹】中采臻了糖邻 矩降的形式来撼述。对予个给铤的平磷三角网格f = r ( o ，p ，定义其相邻矩 簿a 一蠢r ) ： 阪，i = 1 ，2 ，豫y = 1 ，2 ，n a ( i ，) = li 拄，歹。i ( 2 3 ) 1 0i 琢j 毋i 鞠o a = ( 2 4 ) 箕孛五，。为沟顶煮i e i ，2 ，辩 稳对予其褶邻顶患，的凸缀含系魏( 当积歹) 彗e 辩，五，= o ，) ，a 的每一学瓣元豢之和均蔻l e 鞠邻踅蹲臻述了乎嚣三楚蹋褥懿 掭斡结构张内顶点的几何信息。设g = o ( v ，e l 为一平蕊三角圈，g r n n p 将 边器鞭点f 殃瓣为k 条遮熬凸多迭鼯戆顶点，殍尹( f ) = 鼻= 瓴，粥， i g 妇十l ，n + 2 ， 。浚并= 编，毪，知 ，岁一 只+ 致，蜘 分别为掰求予露三角 网格r = r ( o ，p ) 的磺点的横嫩标与级坐据，逸择任窳熬娟邻矩薄a ，冀元素满 足( 2 3 ) ，魏疆辩线性方程缀 a t x * x a ，y = y ( 2 5 ) 这样埂褥到了繇黎黥平瑟三角鼹辏爹。r ( g ，妒) 。 w 戳嚣蹬，上述两耱箍述方式蹩簿价的。事察上，对于般的平面圈，其直 线段凌示璃可碾麓上述蔼耱形式褥蓟，虽葜敷线段表示形式为t i l i n g ( 敖乎瑟三 角阙穰是t i l i n g 的一种特殊情况) ，其中t i l i n g 的逛义由 1 2 】续出，这攫佟筵罄赍 绍。 设v 一( u 1 嗨，翰) 隽乎瑟上一缓嚣举重台瓣点到，令m i ，辩予 9 塑苎三些叁堂塑! ：篓垡竺兰一 j = i ，2 ，m ，设s ( ，t ，t 一) 为集合 l ，2 ，) 中不同元索的序捌，3 s k j n ， 令g = ( ，毛。，j 。) ，对予，= l ，2 ，m ，令 o 。“，小则r = ( ，g ) 称为 蜘 t i l i n g ，如果满足以下条件( 见图2 3 ) ： ( 1 ) 簟，墨，& 均为平面舀多迭影。 蹦2 , 3 台谢匿不重台的9 个】她 ( 2 ) 【冀l n 【只l 为空集戏者一令公共璜点懿强随，萁哮v = 魄鹣，嗡， 。 g m “i ，9 ，玲，( 3 ，4 ，5 ，6 ，1 ) ，( i ，6 ，7 ，习， 或者一条公拭边，i ，。 ( 1 ，2 8 ，9 ) ，( 2 ，7 ，劬 ( 3 ) u ：嘲= 吲。 2 。 ，2 。2 凸2 显合映射麓鬻美证嚣嚣 凸组合映射方法中，当磊；= l 谚( 其中( f ，j ) e e ，为彝顶点i 的度数) 时， 就成为重心映射方法。f l o a t e r 在 2 0 中指出，t u t t e 的重心映射方法的证明建立 在羹心的一个显然的性瓶基础上，鄙：如果一个点w r 2 是列点 心，w 2 ，w j r 2 款鬟心，楚经意一条经过w 戆矗线，嚣么哭可筢露两耱漕况： 所有的都在，上，或者至少有一个点w ，在f 的另边。由于当w 为这剐点蛉任 意严格凸组台时，上述性质依然成立，故可以得出凸缀合映射方法也同样是正确 的。 t u t t e 在 1 9 中对蘑心映射方法( 即t u t t e 定理) 的证明涉及到了相当多的图 论笺漩，诞甓过程笺聚、繁琰，墓予魏，t ! r i c , c o l i nd ev e r d i s r e 等入在 2 2 中给 出了t u t t e 定理的简单证明，f l o a t e r 在 2 3 中则对以下结论给出了一个新的证明， 鄯定义在令平面三热丽格上酶耨溺格透葬映射到一个凸多边形的凸组合缺射 是一一映射，即映射得到的三角网格不会折鬟。该证明比t u t t e 的迁鳃要篱攀蛉 多，且没有使用任何的围论知识，其证明的基本思想鼹基于k n e s e r 对 r a d o 。k n e s e r 。c h o q u e t 定理( 经设多：扫呻露2 怒一个调秘映菇，该获赛孪将d 鹃逸 界锄同胚的映射到某凸区域q c r 2 的边界搬，则是一映射。) 的证明方法。 亘! ! 三些查堂堡兰兰堂堂竺二一 在证明f i o a t e r 的凸组合映射方法时，一个重要的部分是证明线性方程组 ( 2 2 ) 具有唯一解，这里引用f l o a t e r 在e 2 0 l 中的证明方法。 将( 2 2 ) 改写为如下形式： n 一窆 ，p ，：兰丑，n ，j ：1 ，2 ，竹 ( 2 6 ) j = l + l 按a 的两个坐标值x ，y 。，江l ，2 ， ，将( 2 6 ) 写为两个矩阵方程： a x = b 1 a y = b 2 ( 2 7 ) 这里x = ( 五，x ：，) 7 ，y = ( m ，。，n ) 7 ，a = ( a l , j ) ，：j 毛0 0 a , ，= 1 ，a j 。= 一丑， i 。由于线性方程组( 2 2 ) 解的存在性和唯一性等价于矩阵a 的非奇异性 故下面证明是非奇异的。我们知道，矩阵a 非奇异等价于方程组a w = 0 的唯 一解是w ：0 ，由( 2 2 ) 及矩阵a 的形式，方程组a w = 0 可以写为： w = ，j ，i = 1 ，2 ，”， ( 2 8 ) j = 这里+ 。一一h = 0 。令。= m a x w 1 ，w 2 ，h ) ，假设w m 。= 。考虑节点k 的任意相邻节点j ，由于u = w i 。，且由( 2 1 ) 可以得出( 2 8 ) 在i = k 时，即 n = w i 。= 九，。w ，只有当w j = w m 。时才成立a 这样，类似的对于节点七的任意 相邻节点的每一个相邻节点z ，也同样满足w f = w m 。，依次类推，由于g 是连通 的，最后必然可以到达一个边界节点，设为b + 1 ，n + 2 ，) ，满足= w 。 由于+ 。一w n 0 ，得出。= 0 。类似的，同理可证w 。= 0 ，故w = 0 ，矩 阵4 是非奇异的，所以线性方程组( 2 2 ) 具有唯一解。 特别地，对于一个任意的平面三角网格，采用凸组合映射方法可以构造出与 之同构且其边界为凸多边形的平面三角网格，事实上，这正是本章的以下两节中 将要研究的同构平面三角网格变形的理论依据。遗憾的是，凸组合映射方法仅适 用于二维情形，而在三维或三维以上的空间中则不成立，正如f l o a t e r 所指出的， 凸组合映射应用于三维的四面体网格时，未必是一一映射，即映射得到的四面体 西北工业大学硕士学位论文 网格有可能出现折叠相交的现象，l ! r i cc o l i nd ev e r d i e r e 等人在 2 2 中也指出了 t u t t e 定理在三维或三维以上的空间中不成立，并列举了一个反例加以说明。 2 2 相同凸边界的同构平面三角网格变形 正如上一节中所提到的，任惹一个半回三角恻格，采用凸组合映射方法司以 构造出与之同构且边界为凸多边形的平面三角网格。以此为理论依据，文献 1 2 、 1 4 、 1 6 等对相同凸边界的同构平面三角网格的变形进行了研究，其中f l o a t e r 和g o t s m a n 1 2 的研究是开创性的，g 0 t s m a n 和s u r a z h s k y 1 4 1 6 贝j j 在此基础上， 对这种变形的可控制性和内在性质的保留等进行了一些研究工作。 f l o a t e r 和g o t s m a n 1 2 的变形方法也称为凸组合变形。他们研究了t i l i n g 的 变形，由于本章主要研究平面三角网格，故这里仅介绍平面三角网格的凸组合变 形。 设r 。，t 1 为具有相同凸边界的同构平面三角网格，砖为t 。的内顶点相 对于其相邻顶点成的严格为正的凸组合系数，k = 0 ，1 ，i = l ，2 ， ， j = 1 ，2 ，n ，砖显然满足( 2 1 ) 和( 2 2 ) 。在变形过程中，网格边界保持不 变，中间网格内顶点的位置确定如下：对于任意f 【0 ，1 时刻，令 矗) = ( 1 一f ) 砖+ f 硝， ( 2 9 ) 显然 ，( ，) 满足( 2 1 ) ，则下列线性方程组的解就为，时刻中间网格内顶点 只( f ) ，i = l ，2 ，月的坐标值： 丑，) p j ( t ) = b ( f ) ，k1 州2 一，n ( 2 1 0 ) 如果采用相邻矩阵来描述上述凸组合变形，则形式更为简洁 1 4 。设4 ，4 分别为上述丁。，7 1 1 的相邻矩阵，令爿( ，) = ( 1 一t ) a o + t a l ，f 0 ，i i ，解方程组 爿( ) 。( ，) 2 x ( f ) ，爿( f ) y ( f ) = y ( f ) ，便得到了中间网格的内顶点，而网格边界同 样保持不变。 1 2 陟陟莎莎 蹦2 4 对具有相同凸边界的同构平面三角m 格进行凸组合变形。( a ) 初始三角刚格，( e ) 目标三角网格，顶 点对应关系采用不同的颜色来表示( b ) 一( d ) 中间三角瑚格。 采用凸组合变形方法对两个具有相同凸边界的同构平面三角网格进行变形 能够保证任意时刻的中间网格始终与初末网格同构，即不产生自交现象，且变形 过程连续光滑( 见图2 4 ) 。这是由于丑，( f ) 满足( 2 1 ) ，且中间网格边界保持不 变为凸多边形，故由2 1 2 节中的凸组合映射可知，任意时刻的中间状态为与初 末网格同构的平面三角网格，不会产生自交：五，( ，) 关于f 是连续光滑的，故线 性方程组( 2 1 0 ) 的解即网格的内顶点p ，( ，) ，i = l ，2 ，n 关于州3 是连续光滑的， 而任意r o ，1 】时刻网格边界的顶点不变，即p ，( f ) = p , o = ，i = n + l ，”+ 2 ，n ， 所以变形过程连续光滑。 在运用凸组合变形方法时，初末网格内顶点的凸组合系数是需要事先求出 的。设p = ( p 。，p ：，p 。) 为一星形多边形，点p 为p 的核内部的一点， p ，p 。，p ：，p 。互不相同。我们希望能够找到一组严格为正的值 ，如，屯，满 足 乃n = p 和 = 1 ( 2 1 1 ) 如果d = 3 ，则p 关于ap l p ：p 3 的凸组合系数 ，九，屯是唯一确定的，且 丑：竺萼巳里咝，五：竺堕色堕， ：a r e a ( p , p ：, p ) ( 2 1 2 ) “7 e a ( p l ，p 2 ，p 3j a r e a ( p i ，p 2 ，p 3 ) 。 a r e a ( p i ，p 2 ，p 3 ) 如果d 3 ，则 ，如，乃不唯一。 f l o a t e r 和g o t s m a n 在 1 2 中采用了 2 0 的方法来求得内顶点的凸组合系数。 如图2 5 ，对每一个k = l ，2 ，d ，连接既和p 并延长，与p 的一边相交于点吼， 堕! ! 王些查堂婴兰些丝兰一 显然点吼是唯一存在的，且唯一存在下标f ， 使得吼在p 的边【只，p 。1 ( 当i = d 时，1 玻i + 1 为1 ) 上，q k p l 。设，f 2 ，k 3