（计算数学专业论文）平面多边形变形技术的关键问题研究.pdf

摘要 变形，也称为形状渐变或融合，是指从初始物体到目标物体的连续、光滑、 自然的过渡。变形技术在许多领域有着十分广泛的应用，如计算机图形学、动画 设计、工业造型设计、科学计算可视化、电影特级制作等领域。本文主要针对平 面多边形变形技术中三个关键性问题：图形顶点对应，平面多边形的同构三角网 格剖分和图形顶点插值问题进行研究，研究结果如下： 文章首先给出了一种基于简化多边形类正切空间表示下的图形顶点对应算 法。先采用多边形简化的方法提取出包含源图形主要特征点的多边形。在简化多 边形盼类正切空间表示下，利用图形对应边在渐变过程中所掠过面积总和最小这 一特征构造相似度量函数，由动态规划算法求解实现初始和目标简化多边形之间 的顶点对应，再进一步建立源图形顶点之间的整体对应。该算法简单快速，对应 效果自然合理，相比于已有的算法，它的适用范围更广。 平面多边形的同构三角网格割分对于变形技术的插值问题研究具有重要的 意义，作者首先给出不完全同构剖分和基于凹点演化的同构剖分方法来完成对初 始和目标多边形的同构三角剖分，再利用一系列针对同构三角网格固有特点设计 的网格优化算法对形态较差的同构三角网格进行优化，大大改善了网格的质量。 此方法简单易行，操作性强，能够在降低内部顶点个数的前提下，有效的提高网 格的剖分质量。作者在最后给出了具体的算法流程。 最后文章提出了种基于二次有理b 6 z i e r 曲线的多边形变形方法。该方法 是基于向量插值的思想，采用满足模长单调变化的二次有理b 6 z i e r 曲线来构造 边向量的运动轨迹，使得多边形的各边长在变形过程中满足单调变化，因此产生 的变形中阃序列能较好地避免萎缩现象，变形效果自然流畅。此外，作者在文中 给出了二次有理b 6 z i e r 曲线满足向量模长单调变化的充分条件以及处理中间帧 多边形封闭问题的优化算法。实验表明，该插值方法计算速度快，能够达到实时 的要求。而且对于变形过程可以进行交互性设计。 关键词：形状渐变，多边形变形，顶点对应，顶点插值，特征点，同构三角 网格剖分，有理b 6 z i e r 曲线 a b s t r a c t m o r p h i n g ，a l s oc a l l e ds h a p eb l e n d i n g , i st h ec o n t i n u o u ss m o o t ha n dn a t u r a l w a n s f o r m a t i o no fas o u r c 圮o b j e c ti n t oat a r g e to b j e c t m o r p h i n gh a sv e r yw i ( 1 eu s ei n m 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 nd 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 e t h i sp a p e rm a k e sr e s e a r c h e so nt h e t h r e e k e yt e c h n i q u e s o f m o r p h i n g a s ：v e r t i c e s c o r r e s p o n d e n c e ，c o m p a t i b l e t r i a n g u l a t i o na n dv e r t i c e si n t e r p o l a t i o n , a n dt h em a i nr e s u l t so fr e s e a r c h e sa r ea s f o f l o w s ： i nt h ef i r s tp l a c et h i sp a p e rp r e s e n t sa l le f f e c t i v ea p p r o a c hf o re s t a b l i s h i n gv e r t e x c o r r e s p o n d e n c eb e t w e e nt w op l a n a rs h a p e s c o r r e s p o n d e n c e sa r ef i r s te s t a b l i s h e d b e t w e e nt h em a j o rf e a t u r ep o i n t se x t r a c t e df r o mb o t hs i m p l i f i e dp o l y g o n so fs o l l r c e a n d t a r g e ts h a p e s w eu s et h er e p r e s e n t a t i o no ft h es i m p l i f i e dp o l y g o n si nt h es i m i l a r t a n g e n ts p a c et oc o n s t r u c tan e ws i m i l a r i t ym e t r i cf u n c t i o nb yt h ef a c tt h a tt h e c o r r e s p o n d i n ge d g e st r a n s f o r mt oe a c ho t h e rw i l ht h em i n i m u mt o t a la m o u n to f m o v i n ga r e a t h er e s u l t i n gs o l u t i o nt e n d st oa s s o c i a t er e g i o n so i lt h et w os h a p e s w h i c hl o o ka l i k e t h e nt h eo p t i m a lc o r r e s p o n d e n c ei so b t a i n e db ya ne f f i c i e n t d y n a m i cp r o g r m m n i n gt e c h n i q u e ，m e a n w h i l e ，w ec a l l a t t a i nt h ew h o l ev e r t i c e s c o r r e s p o n d e n c eo f s h a p e sf u r t h e r t h em e t h o di sf a s ta n dr o b u s t ，o f w h i c ht h ee f f e c ti s n a t u r a la n dt h ea d a p t e rr a l l g ei sm o r ee x t e n s i v et h a nt h ef o r m e r s c o m p a t i b l et r i a n g u l a t i o na san e wo b j e c tm o d e l i n gt e c h n i q u ei sv e r yi m p o r t a n tf o r v e r t i c e si n t e r p o l a t i o nt e c h n i q u eo fm o r p h i n g i nt h es e c o n ds e c t i o nw ei n t r o d u c ea n e f f e c t i v ea p p r o a c hf o re s t a b l i s h i n gc o m p a t i b l et r i a n g u l a t i o no ft w os i m p l ep o l y g o n s t h ei n c o m p l e t ec o m p a t i b l et r i a n g u l a t i o nm e t h o da n dt h ec o m p a t i b l et r i a n g u l a t i o n m e t h o db a s e do nc o n c a v ev e r t e xe v o l u t i o np r e s e n t e df i r s ta r cu s e d 协g e tt h e c o m p a t i b l em e s h e so f t h et w os i m p l ep o l y g o n s a st h e s ec o m p a t i b l et r i a n g u l a t i o n sa r c u s u a l l yn o to fh i g hq u a l i t y , w ed e v i s eas e r i e so ft e c h n i q u e sf o rr e m e s h i n ga n dm e s h s m o o t h i n ga c c o r d i n gt ot h ei n t r i n s i cp r o p e r t yo fc o m p a t i b l et r i a n g u l a t i o n s ，t h e nw e a t t a i nh j 曲q u a l i t yc o m p a t i b l em e s h e s ，m e a n w h i l e ，t h en u m b e ro ft h ei n t e r i o rv e r t i c e s i ss m a l l e r w eg i v et h es p e c i f i cp r o c e d u r ea tl a s t f i n a l l yt h i sp a p e rp r e s e n t san e wa p p r o a c ht o2 dp o l y g o nm o r p h i n gb a s e d0 n q u a d r a t i cr a t i o n a lb d z i e rc u r v e t h ea p p r o a c h sb a s i ci d e ai sa ss a n l ea st h ev e c t o r i n t e r p o l a t i o nu s i n gt h eq u a d r a t i cr a t i o n a lb d z i c rc u r v eo fw h i c ht h ev e c t o r sl e n g t h 缸a n s f o r m sm o n o t o n o u s l yt oc o n s t r u c tt h et r a j e c t o r yo ft h em o v e m e n tb e t w e e nt h e c o r r e s p o n d i n ge d g ev e c t o r s t h em o r p h i n gs e q u e n c ep r o d u c e db yt h es o l u t i o nc a n a v o i dt h es h r i n k a g ec o m m e n d a b l ya n dt h ee f f e c ti sn a t u r a l i na d d i t i o n , w eg i v et h e a d e q u a t ec o n d i t i o n so ft h eq u a d r a t i cr a t i o n a lb d z i c rc h g v es a t i s f y i n gt h ef a c tt h a tt h e v e c t o r sl e n g t ht r a n s f o r m sm o n o t o n o u s l ya n dt h eo p t i m a la l g o r i t h mt oc o n s t r u c tt h e c l o s e di n t e r m e d i a t ep o l y g o n si nt h i ss e c t i o n e x p e r i m e n t a lr e s u l t ss h o wt h a t t h i s a l g o r i t h mi se a s ya n df a s te n o u g hi nf u l l yi n t e r a c t i v et i m ea n d t h eu s e c a na l s od e s i g n t h ep r o t c e s $ o f m o r p h i n gi n t e r a e t i v e l y k e yw o r d s ：s h a p eb l e n d i n g ，p o l y g o n i n t e r p o l a t i o n , f e a t u r ep o i n t , c u r v e m o r p h i n g ，v e r t e xc o r r e s p o n d e n c e , v e r t e x c o m p a t i b l et r i a n g u l a t i o n , r a t i o n a l b d z i c r i l l 西北工业大学 学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻 读学位期间论文工作的知识产权单位属于西北工业大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和电子版。本人允许论 文被查阅和借阅。学校可以将本学位论文的全部或部分内窖编入有关 数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编 本学位论文。同时本人保证，毕业后结合学位论文研究课题再撰写的 文章一律注明作者单位为谣北工业大学。 保密论文待解密后适用本声明。 学直论文作者签名：硒盈 沙7 年专月日 艚狮魏位 乒护7 年弓月翁日 西北工业大学 学位论文原创性声明 秉承学校严谨的学风和优良的科学道德，本人郑重声明：所呈交 的学位论文，是本人在导师的指导下进行研究工作所取得的成果。尽 我所知，除文中已经注明引用的内容和致谢的地方外，本论文不包含 任何其他个人或集体已经公开发表或撰写过的研究成果，不包含本人 或他人已申请学位或其它用途使用过的成果。对本文的研究做出重要 贡献的个人和集体，均已在文中以明确方式标明。 本人学位论文与资料若有不实，愿意承担一切相关的法律责任。 学位论文作者签名：盟 沙哆年；月必日 西北工业大学硕士论文 第一章绪论 1 1 变形概述与研究问题 随着计算机硬件技术和图形学理论的高速发展，计算机动画成为了一种具有 巨大潜力的新兴产业，并且渗透到生活的各个角落。在魔戒、金刚和终 结者系列等优秀电影作品中，人们可以深深体会到计算机动画高超技术的魅力。 目前，计算机动画已经被广泛的应用于商业广告，电影特技、动画片、娱乐以及 数字电视视频特效等领域，己产生了图形图像变形，动力学模拟等分支，显示了 广阔的前景和极强的生命力。计算机动画技术有很多类型，而最基本且应用范围 最广的是大量应用于动画片制作的关键帧( k e yf r a m e ) 动画技术。变形技术便是处 理计算机关键帧动画的主要技术。 变形( 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 e b 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 e 圮p r o b l e m ) ，第二是在变 形过程中研究对应元素的变形轨迹，称为轨迹问题( t r a j e c t o r yp r o b l e m ) ，但是不 同的变形轨迹是由于插值不同的变量产生，因此轨迹问题也称为插值闯题 ( i n t e r p o l a t i o np r o b l e m ) 。目前国内外已有许多有关变形的研究成果，给出了解 决变形问题的比较有效的算法，但是由于变形是一种视觉效果，与人的审美标准 密切相关，主观因素很大，因此对于以上两大关键性问题都没有成功的解决方案， 目前还没有正式明确的定义，但是从用户角度来看，我们可以根据实际经验、视 觉效果和应用场合来判断一个变形过程的好坏，因而适当的用户干预是必不可少 茜北工业大学硕士论文 的。研究人员普遍认为理想的变形技术应该具有以下特点： 算法简单快速，能实时的生成结果。 变形过程中产生的中间图形对象的一些特征，如边长、夹角、面积等应保持 单调平滑的变换。 中间图形对象的边界应尽量保持光滑，并且能够保证初末图形的拓扑结构， 不能产生自交现象。 初末物体所共有的一些特征在变形过程中应该保留。 用户干预少，交互手段简单直观，易于操作。 当然，一个形状渐变技术要同时满足上述的所有要求是不太可能的，现有的变形 技术都是尽可能多的满足以上要求，生成让人满意的渐变效果。 1 2 国内外研究综述 对应于上述提到的变形的两大关键性问题，目前国内外的研究也主要分为两 个部分：对应和插值。相比于顶点对应问题，插值问题的研究在早期更为广泛， 研究者一般根据已有的顶点对应算法或是采取手动对应的方式建立顶点之间的 匹配关系，再设计插值路径问题的解决方案：而随着图形匹配技术的发展，变形 的对应问题也引起了研究者的浓厚兴趣，特别是这几年，一些较为有效的图形顶 点对应算法陆续被提出。这里我们介绍一下相关研究成果的主要思想，并简要分 析各算法的优缺点。 1 2 1 对应问题 目前解决图形顶点对应问题的算法主要包括以下几个方面： 1 ) 采用顶点自身的一些简单的几何或是物理信息来建立对应( 文献【l 卜。 5 】) 。 在文献【1 】中，c o h e n 采用顶点处的近似切矢作为估计，利用对应顶点的切矢作内 积来构造相似度量函数，确定顶点之间的最优对应：z h a n g 2 提出了基于相似三 角片方法建立顶点对应关系，他依据初末多边形上对应的三个顶点构造一对对应 的三角形，并为每对对应的三角形按照顶点邻边和夹角等几何信息建立相似度量 函数，将顶点对应问题转化为寻找整体最相似三角形对的优化问题；基于物理做 功的方法f 3 】，将两个多边形看作线框，初末多边形之间的渐变过程被看作初始 线框变化到目标线框过程，而线框之间的变化做功可以分为伸缩和弯曲做功两部 2 西北工业大学硕士论文 分，通过构造做功函数的最小化来建立项点对应关系。缺点：前两种方法考虑的 思路较为简单，包含的信息量不够，对应的效果不好，而且这些方法只适用于点 数较少的多边形( 有可能取得较好的对应效果) ，对于点数较多的情况，效果很 差。最后一种方法，由于考虑到物体在变化过程中的物理做功，因此比较符合物 体在实际变形过程中相关几何量的变化，对应效果较好，但是算法过于复杂，并 且不能保证初末多边形特征相似区域之间的对应。 2 ) 提取初始和目标图形的特征点( 一般是从图像上通过象素扫描提取较为密集 的物体轮廓数据，通过现有的提取特征点的方法确定特征点) ，对得到的初末多 边形的特征点集进行匹配，而对应特征点之间的相似度量函数则采用特征点附近 邻域内点集的相关信息来建立。l i u 6 利用图形特征点附近邻域点的集合所构成 的协方差矩阵，通过计算矩阵的特征值和特征向量给出特征点的相似度量函数， 顶点对应问题被转换为使得总体相似代价函数最小的最优问题；方法 7 】的大体 思路和方法 6 】类似，他采用区域象素构造的矩阵来建立相似度量函数。 优点：方法一包含了丰富的边界信息，对应效果比较理想，且该方法具有旋转不 变性，可以较好的处理变形中旋转部分的对应；方法二同样包含了较为丰富的边 界信息，而且操作简单易行。这两种方法都能较好的建立初末多边形中特征相似 区域的顶点对应关系。缺点：方法一在使用动态规划方法求取相似度量函数最小 值时引入了滑动量c ，将计算复杂度变为o c t 2 7 t i l l ) ，而且采用滑动量的动态规划 图求解不是太好控制。其次在确定特征点集中一部分对应特征点和不对应的特征 点时要掺入一些人为因素，并不能实现自适应性；方法二虽然表面上可以自动完 成，但由于在算法中要引入两个参数，一个是相似度函数参数w 和旋转角度参数， 同样也渗入了人为因素，特别是角度参数，如果选择不当，将导致旋转部分的对 应效果不佳。虽然这两种方法都是采用特征点附近区域的点集信息来建立相似度 量函数，但是方法二的度量函数没有方法一的准确和直观。 此外h u i 和l i 【8 】、【9 】的思路和上述两种方法类似：他们先根据曲线曲率 的变化构造一个判别函数来确定对应的物体( 一般采用曲线表示) 变化较大的顶 点作为特征分段点，从而将曲线分成若干段，再根据这些分段点自身的一些信息 ( 一般是几何信息) 和相邻分段点之闻弦的几何信息来建立这些分段点之间的对 应，对于已经建立匹配关系的子曲线段按照弧长比例一致的原则完成整体顶点对 西北 ：业大学硕士论文 应。缺点：采用几何信息不能很好的描述点的特征。 3 ) 通过图形骨架的匹配来建立轮廓顶点的对应。上述几种方法一般处理的都是 边界信息，缺少内部信息，而骨架能够很好的提取出物体的内部信息。骨架的对 应可以看作是一种动态形式的对应，因为骨架能够准确的描绘图形局部的萎缩， 旋转，凸凹，而基于边界信息的对应算法更像是一种静态形式的对应。基于物理 做功原理的对应方法也算是一种动态的对应方法，本文在第二章提出的方法也是 一种动态的对应方法。m o r t a r a 掣州使用一种近似骨架来描述图形形状，对初末 物体进行近似骨架剖分，对得到的近似骨架按照一定的相似度量函数建立节点之 问的对应，然后再映射到轮廓上确定初末图形的对应顶点，这些顶点一般都是特 征点。在相邻的特征点之间通过添加新顶点来完成整体顶点的匹配。该方法在处 理顶点数目较少，形状较为简单的图形时比较有效，但是由于近似骨架提取方法 的局限性，该算法不适用于复杂的图形。在变形对应问题的研究中，每一种算法 都各有其适用的范围，其有效性需要通过插值方法进行验证。 1 2 2 插值问题 解决平面图形顶点插值问题的思路大体上分为两类：第一类是采用多边形的 边界几何信息量( 有时加入内部信息) 来构造变形的中间关键帧图形；第二类是 将源图形进行同构三角网格剖分，将多边形变形问题转化为两个同构三角网格的 变形问题。下面简要介绍一下已有的算法和研究成果。 1 ) 第一类： 在解决多边形、多面体曲线和曲面的插值问题的方法中，一个简单的方法 是顶点线性插值法：假设4 为初始多边形，b 为目标多边形，4 ，置( 扣1 ，以) 为 多边形的顶点，则定义彳到曰的变形如下： c ( t ) = ( 1 - t ) a + t b = 【( 1 一r ) 4 + 吗，0 一t ) a + t 最】= q ( f ) ，c ：o ) 】t 【o ，l 】 这种算法简单生成速度快，但变形中可能引起边界的非正常萎缩，产生自交，效 果非常不自然。一些简单的几何特征如长度、角度等在变形过程中不能一致的变 化，原因是各个顶点及其它几何信息在变化中缺乏联系，其路径是相互独立的。 1 9 9 3 年s e d e r b e r g 和王国瑾等在 3 9 】中提出关于平面多边形的一个内在解 算法，线性插值相邻边的旋转角度和边的长度，并采用优化的方法避免断口现象。 该方法能够体现多边形的结构特征，而且生成速度快，对很多变形实例取得了很 4 西北工业大学硕士论文 好的效果。但是由于边界的各个部分之间缺乏联系，没有明确的考虑到多边形内 部，所以许多情况下边界容易自交，内部面积在变形过程中易产生扭曲或是膨胀 现象 为了改善上述方法存在的问题，s l l a p i r a 和r a p p o p o r t 4 0 利用多边形的星 骨架( s t a rs k e l e t o n ) 表示方法得出一种新的插值方法。该方法首先构造初末多边形 的同构星骨架，再通过星骨架将多边形分为对应的几个子多边形，对该同构星骨 架变形，利用骨架节点和子多边形顶点的关系线性插值相应的元素如边长、角度 等，最后重组得到中间关键帧多边形。由于该算法即考虑到多边形的边界，也考 虑到其内部联系，故减少了产生自交的可能性，而且变形效果比较自然。由于初 末多边形的同构星骨架提取比较困难，特别是对顶点个数较多的复杂多边形，所 以算法的复杂度很高。文献【4 l 】的思想与上述方法类似，他们采取多边形的特征 分解，根据初始和目标多边形一系列的相似特征点将多边形分解成不同的几个特 征块，再对整体的主特征块应用内在解算法进行变形，最后再重建每个对应的子 特征块并组合重构出中间关键帧多边形。该方法存在的最大问题就是特征点的选 取需要人工指定，降低了算法的自适应性。 ；1 9 9 6 年汪国昭和白宝钢 4 2 】将平面多边形的每一条边按照向量的形式进 行表示，然后针对每一组对应的边向量建立一条满足向量模长单调变化的变形轨 迹，在此基础上可以简单直接的生成中间关键帧多边形。该方法的优点在于：因 为前面介绍的这些工作都未能很好地解决刚体运动时边长变化不单调的问题，而 将多边形的边按照向量的形式进行处理，就可以人为的构造满足向量模长单调变 化的参数曲线作为边向量的变形轨迹，这样在变形过程中，多边形的边长能够保 持单调变化，较好地避免了中间形状的萎缩扭曲，因而更符合人们通常的审美趣 向和事物变化的一般规律。文献 4 2 】是采用b 6 z i e r 曲线来构造变形轨迹，算法简 单易行，且具有一定的交互功能。缺点就是中间参数的设定要满足向量模长单调 变化的充分条件和中间帧多边形的封闭调整条件，有时合理的参数不一定存在： 而且鉴于b 6 z i e r 曲线的缺点，该方法不能处理等模长的向量转化； 4 3 贝1 j 是利用 圆弧的n u r b s 参数形式来构造变形轨迹，计算简单，变形效果也是相当自然， 但是由于该方法涉及的圆弧轨迹是固定的，降低了方法的交互性，并且变形产生 的中间过程可能不是封闭的；【4 4 】采取线性插值对应向量的模长和交角的方法来 5 西北工业大学硕士论文 构造变形轨迹，算法非常简单易于编程，几何意义明确，变形自然流畅，但是同 样存在着变形轨迹固定而不易于修改的问题。 k t a t i a n a s u r a z h s k y 和g e r s h o n e l b e r y 4 5 提出了一种平面参数曲线的变形方 法。该方法基于曲线微分几何的有关理论，即以弧长为参数的平面曲线除了一个 刚体运动变换外，由其曲率完全决定。通过线性插值初末曲线的曲率，重构出中 间曲线，并以分段插值建立对应关系。此算法得到的渐变过程不仅光滑，而且利 用了内部曲率的形状特征，因而变形效果是令人满意的。但是，这种方法仅适用 于以弧长为参数的曲线变形，对于一般参数曲线必须先弧长参数化处理，而且其 中重构曲线的积分表达式对于一般的曲率没有解析解，故变形的复杂度大，实现 比较困难。宋伟杰 4 6 】针对上述方法的缺点和不足，提出了平面多边形的离散曲 率插值变形方法，将参数曲线的变形问题转化为平面多边形的变形问题，针对均 匀多边形和一般多边形两种情况，给出了相应的离散曲率插值变形的算法。 2 ) 第二类： k f l o a t e r 和g o t s m a n 4 7 ( 1 9 9 9 年) 提出基于平面三角网格内部节点的凸组合 表示方法，用来解决具有相同凸边界的同构三角网格的变形方法，称为凸组合方 法。该算法首先对初始和目标多边形进行同构三角形网格剖分，保证生成的中间 关键帧三角网格始终与初末三角网格同构，在此基础上计算每个内部节点关于相 邻节点的凸组合系数，通过线性插值初末多边形上对应内节点的凸组合系数来计 算出中间多边形相应内节点的系数，然后重构出中间多边形。该方法能够保证变 形生成的中间关键帧图形不产生自交现象，且连续光滑。受方法【4 7 】的启发， g o t s m a n 和s u r a z h s k y 2 8 】( 2 0 0 1 年) 给出了可避免自交的平面简单多边形的变 形方法，它将初末多边形分别嵌入到两个具有相同凸边界的同构平面三角网格 中，通过采用【4 7 】的方法对这两个三角网格进行变形，以此实现所嵌入多边形的 渐变过程。该方法首次彻底的解决了平面多边形在渐变过程中产生自交的问题， 并且应用于图像变形，也可以保证中间图像不产生折迭。g o t s m a n 和s u r a z h s k y ( 2 0 0 1 年) 在后来的研究中提出了可控制的同构平面三角网格变形方法【4 8 】； s t i c kf i g u r e s 的变形方法 2 9 】，该算法和方法【2 8 】差不多，也是将s t i c kf i g u r e s 嵌入 到具有相同边界的同构平面三角网格中，然后再进行网格变形；同构三角网格的 内在变形方法 4 9 】，这里采用均值坐标来计算内部节点的凸组合系数，然后用线 6 西北工业大学硕士论文 性插值夹角和边长再计算出均值坐标的方法代替直接线性插值凸组合系数。由于 考虑了多边形网格的一些内在信息，因此该算法的变形效果有了较大的改善，也 使得这种基于同构三角网格的变形方法得到了进一步的完善。但是这种嵌入相同 凸边界的同构平面三角网格的变形方法没有考虑初始和目标多边形或更一般的 s t i c kf i g u r e 的几何形状和相互间的联系，因而变形效果未必令人满意，特别当同 构三角割分的网格形态较差时，渐变的效果差强人意，因此高质量的同构三角网 格剖分方法是采用网格思想有效解决多边形变形的一个重要基础，但是由于在同 构剖分时使用的额外顶点较多，计算中间关键帧多边形时需要解大型方程组，因 此算法的复杂度相当大。 a l e x a 5 0 】( 2 0 0 0 年) 的方法也是建立在同构平面三角网格剖分的基础上，将 初末物体分解成同构的单纯复形，在两个对应的单纯形之间定义仿射变换，并将 其表示成旋转变换和伸展变换的复合，然后将这两种变换线性插值得到期望的仿 射变换，再通过使得中间物体在最j , - 乘意义下逼近该期望的仿射变换，达到扭 曲最小的效果。该方法考虑了物体的内部，且变形具有刚性，因而效果比较自然， 且中间过程不易产生自交，缺点是算法比较复杂。 ；宋伟杰【5 1 】证明了，当初末多边形均为凸多边形时，采用内在解变形方法 可以保证变形产生的中间关键帧多边形也为凸多边形，称之为保凸性，将其应用 在具有凸边界的同构三角网格变形上可以取得较好的变形效果；此外对于不同边 界的初始和目标多边形，可以将其分别嵌入到各自的最小凸包中，通过对对应凸 包作内在解变形，而内部网格顶点采用凸组合的方法计算坐标的方式完成初末多 边形的渐变过程该方法相比于嵌入具有相同边界的平面三角网格的方法，简化 了网格的复杂度，减少了添加的内部顶点个数，相应的算法复杂度也降低了，而 且变形流畅自然，不过额外顶点数目多、运算复杂还是该算法存在的主要问题。 针对第二类方法采用图形同构三角网格剖分的思路对源图形进行渐变处理， 同构三角网格剖分质量的好坏将直接影响变形的效果和复杂度，而目前关于同构 三角网格的剖分方法主要有b o r i s a r o n o v l 2 7 1 、c r a i go o t s m a n v i t a l ys u r a z h s k y u s j 以及g o t s m a n z g 提出的相关算法，这里将不加以介绍。平面图形同构三角网格剖 分技术的相关知识和算法都将在第三章进行介绍。 7 西北工业大学硕士论文 1 3 本文研究的内容及结果 本文探讨了平面多边形变形问题中三个关键性技术：顶点对应、同构三角网 格剖分和顶点插值。本文的若干研究成果，有的综合了几种已有算法的优点，并 针对存在的缺点和不足进行修改、拓展，获得了令人满意的结果；有的另辟蹊径， 采用新的思路和方法迸行探究，得到了一些意外的新收获，从而提供了若干值得 继续研究的途径。由于同构三角网格剖分和顶点插值技术必须先用顶点对应技术 进行预处理，而同构三角网格剖分技术又是顶点插值技术中采用网格处理方法的 基础，所以本文的研究内容和研究结果按照如下方式依次介绍： 图形顶点对应算法 顶点对应问题是研究插值问题的基础，对应关系建立的好坏直接影响变形效 果的质量。本文在第二章提出了一种基于简化多边形类正切空间表示下的图形顶 点对应算法。该方法从建立特征顶点的对应入手，通过多边形简化方法提取出能 包含源图形主要特征点的多边形，对该简化多边形进行类正切空间的表示，并在 该空间表示下利用图形的对应边在渐变过程中所掠过面积总和最小这一特征来 构造顶点之间的相似度量函数，通过动态规划的方法建立特征顶点之间的对应， 再对剩余的顶点按照弧长比例一致的原则补上对应点，最终实现初始和目标图形 顶点间的整体对应。该方法速度快，简单易行，能较好的捕捉到特征点之间的对 应关系，对应效果好，并且能够保证特征点在图形渐变过程中不失真。此外该算 法的适用范围更广，在确定图形的近似多边形的顶点对应和通过象素采集轮廓顶 点数据后建立顶点对应这两方面都可以应用，而且具有一定的自适应性。 平面多边形同构三角网格剖分算法 采用同构三角网格变形技术可以有效地解决平面多边形变形问题，然而初末 图形的同构三角网格剖分质量的好坏决定着网格变形的效果和算法的复杂度。鉴 于此本文在第三章提出了一种有效的平面多边形同构三角网格剖分算法。该方法 给出的不完全同构剖分和基于凹点演化的同构剖分方法能够完成对初始和目标 多边形的同构三角剖分，再利用一系列针对同构三角网格固有特点设计的网格优 化算法对形态较差的同构网格进行优化，大大改善了三角网格的质量。该算法简 单易行，操作性强。与已有的算法 2 7 2 9 相比，该方法能够在降低内部顶点个数 的前提下，有效的提高网格的剖分质量，为同构网格的后期处理打下了好的基础。 8 西北工业大学硕士论文 图形渐变插值算法 自然、光滑、流畅的变形过程是每个动画设计者的设计初衷，相应的图形插 值算法能够合理有效地描绘出图形各种几何属性的变化。本文在第四章提出了一 种基于二次有理b 6 z i e r 曲线的多边形变形方法。该方法将多边形的各条边按照 向量的形式进行处理，采用满足模长单调变化的二次有理b 6 z i e r 曲线来构造边 向量的运动轨迹，使得多边形的各边长在变形过程中满足单调变化。这就克服了 传统动画方法不能保证对应边向量模长变化单调的缺点，很好地避免了中间形状 的萎缩扭曲，因而更符合人们通常的审美趣向和事物交化的般规律。该算法简 单直观，计算速度快，变化自然流畅，而且拥有一定的交互修改能力。相比于文 献 4 2 1 和文献【4 3 】的方法，本文的方法更具有一般性。 9 西北工业大学硕士论文 第二章基于简化多边形类正切空间表示的图形顶点对应 算法 变形需要解决两个关键性问题：顶点对应问题和对应顶点的插值路径问题。 顶点对应问题，即如何建立初始和目标图形的轮廓顶点之间的一一对应关系，是 研究插值问题的基础。对应关系建立的好坏直接影响变形效果，而一个好的顶点 对应关系需要满足如下两个要求： ( 1 ) 初始和目标图形最终的顶点个数必须相同，且一一对应，顶点对应和顶点 排列的顺序必须是一致的； ( 2 ) 具有相似特征的顶点尽量满足对应关系。 对于大部分的图形变形实例，初始和目标图形的顶点个数是不一致的，因此需要 通过添加合适的新顶点来满足条件( 1 ) ； 特征相似部分的变化幅度不是很剧烈， 此外在很多的变形过程中，初末图形的 因此在源图形上保存了很多的特征相似 点，需要通过有效的算法来确定这些点之间的对应关系来满足条件( 2 ) 。本章从 这两点出发，通过简化源图形来获得包含主要特征点的简化多边形，再构造该简 化多边形类正切空间表示下的相似度量函数来建立这些特征顶点之间的对应关 系，然后适当添加新项点来完成源图形的整体顶点对应。 2 1基于简化多边形类正切空间表示的图形顶点对应算法 文献f 1 - 5 是通过图形边界相关的几何信息量构造相似度量函数来完成顶 点对应，而文献【6 9 】提出的方法则是从图形边界的特征顶点入手进行处理。本 章兼顾了上述的思想，从建立特征顶点的对应入手，通过多边形简化方法提取出 能包含源图形主要特征点的多边形，对该简化多边形进行类正切空间的表示，并 在该空间表示下利用图形的对应边在渐变过程中所掠过面积总和最小这一特征 来构造顶点之间的相似度量函数，从而建立特征顶点之间的对应，再对剩余的顶 点按照弧长比例致的原则补上对应点，最终实现初始和目标图形顶点间的整体 对应。此外，方法n - - 5 适用于对初始和目标图形轮廓的近似多边形的顶点( 该 顶点数据是通过手动提取或是给定，一般数据量不是很大) 进行对应，而方法【6 】、 西北工业大学硕士论文 【7 】适用于初始和目标图形通过象素采集得到的数据量较大的轮廓顶点数据进行 对应。本章的方法对于上述两种情形都能适用，下面将依次介绍。 2 1 1 简化多边形 当两个多边形图形进行变形时，有一部分顶点在构 造关键帧图形中起着重要的作用，譬如图2 1 所示的黑 色顶点，这些点在人眼进行图形识别时具有很大的影 响，可以称之为视觉关键点。对于曲线表示的图形，这 些点都是尖点、变形点、曲率极值点等轮廓特征点，它 们对判定目标形状起着决定作用。而在这些轮廓特征点 当中，又可以抽取出一些对形状判定作用更大的点，譬图2 - i 马的特征点和主特征点 如图2 1 中打圈的点，这些点分别是马的关节点，也就是用来区分身体各个部分 的关键点。在变形过程中这些点可以确定图形的大概形状，我们称它们为主特征 点z 丽剩余的点虽然也是特征点，但是作用没有主特征点明显。 二给定初始图形4 包含个顶点 4 ，4 ，4 ，目标图形b 包含肘个顶点 垦，垦，且，) ，这里初始图形和目标图形的顶点坐标是给定的，也可以是手动 主 取定，点的密集度不高，例如，对于图2 1 只需要不超过2 0 0 个点就可以较准确 的完成图形轮廓的描述。将这些点首尾依次相连就形成一个多边形，该多边形是 对源图形的一种近似表示，对于这样的近似多边形想找到特征点比较困难，特别 是点数较少的时候。这里采用文献【1 1 】提出的多边形简化算法来获得含有源图形 较多主特征点，能够合理地反映图形大概轮廓的简化多边形。 依次对多边形爿 4 ，鸣，4 的个顶点计算它们的相关度参数，以4 为 例，相关度参数定义为：k ( ，) = 笪茜紫，其中和墨为顶点4 的 两条相邻边，( 一) 和，( ) 分别表示边的归一化长度，即单个边长除以多边形的 总边长，0 ， 一。) ，( i ) 1 ；( ，) 为两邻边之间的旋转角度取绝对值， o ( 钆，) 石，然后找出这个顶点相关度参数中的最小值，将其对应的顶 点删去，并连接被删除顶点的两个相邻顶点，这样就构造出含有一1 个顶点的 西北- 业大学硕士论文 新多边形，依次类推经过，次简化后的多边形含有j v 一_ ，个顶点。这种多边形简 化算法最初的目的是为了消除图形的噪声影响，而将其应用在图形简化上，可以 逐步去处边缘的细节信息，得到图形的主体信息，而决定这些主体信息的边界关 键点就是主特征点。图2 2 是一个图形简化的例子：2 2 ( a ) 是对一个畸形手提取 了1 1 3 个数据点后得到的近似多边形；2 - 2 ( b ) 是对多边形简化8 9 次后得到的只包 含2 4 个顶点的简化多边形，可以看到，简化多边形包含了原始图形所有的主特 征点，能够很好地描绘出源图形的大致轮廓。 记初始和目标多边形一，曰的简化多边形为彳和。这里要注意：简化的 次数不是越多越好，太高的次数会导致简化多边形丢失主特征点而失真；次数也 不能太低，这样会失去简化的意义，一般简化后的多边形应该包含较多的主特征 点，反映原始图形的大致轮廓，此外我们并不要求a 和所包含的顶点数一致， ( a ) 畸形手( b ) 经过简化后的图形 图2 - 2 手的原始图形和经过简化后的图形 但是不能相差太大。假设含有r 1 个顶点： 岛，a 2 ，a n ，雄 n ；b + 含有m 个 顶点： b t ，b 2 ，b m ，研 肘。一般情况下”，m 的值不是很大( 在本章的实验 中，1 0 n ，m 4 0 ) 。对于此类较为简单的多边形，可以采用基于顶点的相关几 何属性来建立相似度量函数，但是已有的方法1 处理的效果都不是很好，这里 本章提出一种新的相似度量函数形式。 2 1 2 类正切空间表示下的相似度量函数构造 首先介绍类正切空间的概念：给定多边形c