（计算机应用技术专业论文）基于特征分解的二维形体渐变及其应用.pdf

浙江大学磺士学位论文 中文摘要 二缀形体港燮指觚源多边形形体到嚣稼多边形形体豹筏觉光涛过渡，它在凡 何造型、模式匹配以及计算机动确等领域有着广泛的应用。二维形体渐变的研究 包含鼹个问题：顶点对应问题和顶点插值路径问题。从上世纪八十年代开始，人 爨针对这薅令润莲藤续提出了诲多算法，露戳蜜瑗二缝形体之窝懿光浸避渡。零 篇硕士论文在分析和比较了已有弊法的基础上，提出了二维形体的视觉特征分解 概念，并将其用于二维形体渐变及其内部纹理渐变算法。作为上述算法的推广和 应用，本文还给出了个二维形体的栩投c o p y a n d p a s t e 框浆，角子二维形体盼 截律帮多个二维形髂静渐变。论文戆结擒蘩下： 第一章介绍了二缎形体渐变的溅本概念和研究内容，并分析和总结了前人的 工作。 。第二章介绍了基予特征分解羽三释二维多边形渐变方法。首先，提出了基于 视激特征分解的二维形体渐变方法。然后引入了特征方向轴的概念，并设计 了一个近似方向轴提取算法。将特征方向轴用于驱动特裰之间的渐变，得到 了缳辍嚣戆特鬣鹣二维多透影激变效粟。最舞，基予踅像灏交孛戆线辩控裁 方法，提出了一个适用于带有纹理的二维多边形渐变的方法，该方法在进行 = 维多边形渐变的同时，实现了内部二维纹理豹光滑过渡。 。 雾三褰疆窭了基予二缝形俸潦交戆魏投c o p y - a n d - p a s t e 搽箨。逶过该搽终， 用户能够从输入多边形形体中选择所需特鬣，创造具有特定效果的新的二维 多边彤形体。根据c o p y a n d p a s t e 操作的底艨算法，可以实现多个二维多边 形形体之闯魄光潢过渡。 ， 笫褥章总结全文，并展望了避一步的研究z 作。 关建溺：二维形体濒交，籍程分瓣，方囊辘，拷受堞貉，纹壤澎交。 辩汪大学硬士学位论文 a b s t r a c t 2 ds h a p eb l e n d i n gi sav i s u a l l ys m o o t ht r a n s f o r m a t i o nf r o ms o n r c es h a p et o d e s t i n a t i o ns h a p e i th a sb e e nw i d e l yu s e d i n2 dc h a r a c t e ra n i m a t i o n ，p a t t e r n m a t c h i n g ，a n dg e o m e t r i cm o d e l i n g ，t h e r ea r et w op r o b l e m si n2 ds h a p eb l e n d i n g ： v e 娃e xc o r r e s p o n d e n c ea n dv e r t e xi n t e r p o l a t i o np a t h ，s i n c e19 8 0 s ，m a n ya l g o r i t h m s w e r ep r o p o s e dt oa c h i e v es m o o t h2 d s h a p eb l e n d i n g i nt h i sd i s s e r t a t i o n , t h ec o n c e p t o fv i s u a lf e a t u r ed e c o m p o s i t i o ni s p r o p o s e d i t i s a p p l i e d t o2 ds h a p eb l e n d i n g w i t h o u to rw i t ht e x t u r e 。a st h ee x t e n s i o na n da p p l i c a t i o no fa b o v ef e n t u r e - b a s e d2 d s h a p eb l e n d i n ga l g o r i t h m s ，aw e i g h t e d2 dc o p y - a n d - p a s t eo p e r a t i o n i sp r o p o s e df o r 2 ds h a p e sd e s i g na n dm u l t i p l e2 ds h a p e sb l e n d i n g 。t h i sp a p e ri so r g a n i z e da st h e f o l l o w i n g i n c h a p t e r1 ，t h ec o n c e p ta n dc o n t e n ：so f 2 d s h a p eb l e n d i n g a r ei n t r o d u c e d + t h e s t a t eo f a r ta b o u t2 ds h a p eb l e n d i n gi sg i v e nt h e n i nc h a p t e r2 ，t h r e ef e a t u r e b a s e d2 ds h a p eb l e n d i n gm e t h o d sa r ep r o p o s e di n d e t a i l 。f i r s t ，av i s u a lf e a t u r e - b a s e d2 ds h a p eb l e n d i n gm e t h o di sp r e s e n t e d 。t h e n t h ed i r e c t i o na x i so fv i s u a lf u t u r ei sd e f i n e d ，a n da na p p r o x i m a t i o ne x t r a c t i o n a l g o d t h mi sp r o p o s e d 。弧ed i r e c t i o na x i s i s a p p l i e dt o2 ds h a p eb l e n d i n gt o a c h i e v es m o o t ht r a n s i t i o ne f f e c t sw i t ht h ep r e s e r v a t i o no fo r i g i n a lv i s u a lf e a t u r e s f i n a a l y , c o m b i n e dw i t hi m a g em o r p h i n gm e t h o dc o n t r o l l e db y l i n e p a i r s ，a n e x t e n d e d2 ds h a p eb l e n d i n gi sp r o p o s e d ，w h i c hc a l lp r o c e s sb o t hs h a p e sa n d i n t e r i o rt e x t u r e s 。 a w e i g h t e d2 dc o p y - a n d - p a s t eo p e r a t i o ni sp r e s e n t e di nc h a p t e r3 ，w h i c hi s b a s e do nm u l t i p l e2 ds h a p e sb l e n d i n g 。b y 撼n gt h ec o p y - a n d - p a s t eo p e r a t i o n s ， u s e rc a nd e s i g nn e wp o l y g o n a ls h a p e sb ys m o o t h l yc o m b i n i n gt h ep a r t sf r o m d i f f e r e n ti n p u t2 ds h a p e s t h ea l g o r i t h mc a na l s ob ea p p l i e dt og e n e r a t es m o o t h m o r p h i n gs e q u e n c e sa m o n gm u l t i p l e2 d s h a p e s 。 t h ec o n c l u s i o ni sd r a w na n df u t u r er e s e a r c hi sp r o p o s e di nc h a p t e r4 k e y w o r d s ：2 ds h a p eb l e n d i n g ，f e a t u r ed e c o m p o s i t i o n ，d i r e c t i o n a x i s ， c o p y - a n d - p a s t e ，t e x t u r eb l e n d i n g 浙江大学硕士学位论文 第一章绪论 随着计算机技术在电影，电视等领域的普及应用，越来越多的冲击人们视觉 效果的角色和场景被艺术家们通过电脑合成带到了人们的身边。例如，迪斯尼公 司出品的众多动画片，日本的卡通动画片。至于影片泰塔尼克克中大轮船沉 没的壮观场面，看过该影片的人应该都印象深刻。在众多的电脑技术里，有一专 门的用于产生这种虚拟的人物世界的技术，称为计算机动画。 按照其应用领域的不同，计算机动画可分为：三维动画和二维动画。三维动 画的研究对象是三维空间中的形体，二维动画其研究对象为平面图像或者是二维 形体。二维动画中有一项技术，称为二维形体渐变( 2 ds h a p eb l e n d i n g 或者2 d s h a p em e t a m o r p h o s i s ) ，指的是在二维形体之间的自然过渡，它在二维角色动画、 模式匹配、几何造型等领域有着重要的应用。从上世纪八十年代开始，人们陆续 地提出了诸多二维形体渐变相关算法。所有这些算法主要用来解决二个问题，一 个是如何实现二维形体之间的对应，它被称为顶点对应问题；另一个是如何解决 过渡形体的位置，它被称为顶点路径问题。 上面我们简要介绍了二维形体渐变的一些背景知识。接下来，我们分别详细 解释二维形体渐变的应用及其需要解决的问题。并对前人的研究成果进行描述、 分析，解释我们的二维形体渐变思想的来源。 1 。1 二维多边形形体渐变 在二维角色动画( 2 dc h a r a c t e ra n i m a t i o n ) 中，经常会碰到这样的问题：给定 一个初始和最终的形体( s h a p e ) - - 我们称之为关键帧形体，求从初始形体光滑过 渡到最终形体的中间形体。如图1 1 如示，给定了左、右两边的两个花形多边形 形体，中间的三个形体不需要手动交互，自动由算法产生。这个操作被称为二维 形体渐变( 2 ds h a p eb l e n d i n g 、2 ds h a p ei n t e r p o l a t i o n 或2 ds h a p em e t a m o r p h o s i s ) ， 它不仅在计算机动画中，而且在模式识别、曲面重建和三维造型中也具有重要意 义。在许多商业软件中【s 鲢，匹鲣】，二维形体渐变均被加入，作为其中的一 项功能。 对于二维形体渐变来说，有如下问题值得研究：渐变算法如何避免产生混乱 的中间过渡形体、怎样识别关键帧形体上的相似特征、怎样在渐变过程中保持这 些特征。这些问题可以归结到二维形体渐变中的两个基本问题，即顶点对应问题 和顶点插值问题。顶点对应问题，即是如何建立两关键帧多边形形体顶点的一一 对应关系，如图1 2 所示，两关键帧形体p i 与p 2 分别具有4 、5 个顶点，要建立 它们之间的对应关系，需要在p 1 中加入一个新的顶点，如何加入这个顶点与如 浙江大学硕士学位论文 图1 1 花之间的形体渐变 t 鑫) p 国) p 2 蓬1 2 两美键演形鼬l 与魏 何建立顶点志间的对应关系是密切相荚的。总的说来，顶点对成辫满足如下两个 要求： +嚣令形体之阗最终瓣疆熹令数热麓、一一对旋，并显覆熹瓣波与疆熹掺糕 顺序遐一致的 相似特征间的顶点对应 如图1 3 ( b ) 掰示，一个薪顶点被翱入到了形体歌中，它稍熬顶点按标号一一对成， 基本满是上嚣捷蓟翡两个簧求，因诧燕一个好嚣鼹趣关系。瑟强1 3 ( 醇，虽然嚣 形体也具有相同个数，并崴按标号一对应，但显然p i 中的顶点顺序是不正确臼口。 另外地，如果源形体特征上的顶点如果没有与目标彤体相似特征上的顶点一一对 疲，噩| j 在嚣影薅到曩挺形俸豹灏交过糕串，中麓形髂勰霉麓失去原始形髂上驰酶 征信息，难以保证特征闻的光滑过渡，如图1 4 雳幂。在图( 醇中，源形体横、鳖 边上的顶点_ 井不完全与对应目标形体上的横、竖边上的顶点对陵，因此，在渐变 过程中，源、锺标形体的藁塑横、竖边特征信息丢失了，产生了誉自然黔渐交效 莱。瑟在霞鼢中，棰 鞋边上戆疆煮稳拦游应，因嚣。丧辩变过穰串，滚、嚣橡 形体上的横、竖边特征信息得到保留，产生了光滑、自然的过渡。可见，源、目 标形体间的顺点对应关系，直接影响剽渐变效果的好坏。在我们舱基于特征分解 浙江大学碗士学位论文 的渐变鼙法审，曹竞辩潦鞫鏊标形体上静稽钕特征遴行对应，然麓荐在掇戳祷鬣 间建立顶点对应关系，这样，就可保证源形体特征上的顶点与目桥形体相似特征 上的顶点一一对应，从筒保证了源特征到目标特征的光滑过渡。 罄1 3p l 每也建立顶点对廒关系 t b ) ( b ) 黧1 4p l 到魏翦赣交 二维形体渐变的另一个基本问题悬顶点路径问题。顶点路径问题用来解决源 形体上的各顶点如何运动到墓标形体上的对应顶点。最简单的方法是线性插值， 缎设漂、嚣枣嚣形体珏、玖孛貔各顼赢裂，琏g = 0 , 1 ，撵一1 ) ，在菜一辩麴f ，串潺 形体各顶点按如下公式计算： f = ( 1 一f ) 耳+ ，蟛( i = o ，1 ，n - i )( 1 1 ) 不霉兹莛，线蠖捶蓬方法念荣来浚壤( s h r i n k a g e ) 瑟掇缨襞象( k i n k ) ，褥鬟是漯、 目标形体间烹簧进行刚憔运动( 旋转、平移) 时，表现樽尤为明显。如图1 5 所示， 恩然中间形体发生了明最的收缩。为了解决这个问越，人们提出了各种解决顶点 踌经豹算法，例妇，边熊攒僮方法毽鲤竣盟蓼、黼u z z ys e t ) t y 法 z h a 9 _ _ _ _ 6 、 浙江大学瑚士学位论文 整形鸯絮方法匿墼窝戳及戳究念削4 隆捶俊( a s - r i g i d - a s - p o s s i b l es h a p e i n t e r p o l a t i o n ) 【! x 堕q 卿为代表诸多基于三角变化的搔值方法。在这些方法中，地 图1 5 两个形体之间的线性渐燮 角插值算法邋过把形体的顶点笛卡尔坐标转换到以内在参数：边长和角度，来袭 示，通过它们来对形体运动进行旋转零羹警移援值，该方法可有效避免收缩，但鬻 常会发生内郝医域箍凿醺象。露萁穆方法，它销静萋本愚怒，筠怒麓形俸运动中 的刚性运动抽取出来，进行单独的角度、位置插值，遮些方法可有效避免线性攒 值的收缩现敷。但由于在翼实世界中，以旋转为代表的剐性运动基本都是以一个 撬爨特经为零缀逶行豹，掇叛索霉嚣令澎薅藏熬剿毪遥凌爨要多缀分支运动来饯 袭，并且每缀搿g 性运动常发生在两个相似特征之间。在上面的算法中，要么它们 的刚性运动豳个单独的念局旋转、平移变换来代裁，要么这些刚性运动并不发 生在对应的穗似特征之闽，因此，这些方霭常常也会产生一些视擞效果不好的濒 变净裂。在本文提蠢赘冗令濒变算法牵，翦良对应熬援爨特征爻肇像，为每缓霹 成特征单独捅值它们之间的剐性运动，因此得到了较好的视觉效聚。在下面的算 法介绍中，我们将给出实例说明。在下小节中，我们将详细介绍、分析前人在 影薅濒变领域审妻孽残果。 1 。2 前人成果及讲究现状 歪魏上夺繁奔绥戆，隽了实瑷= 缎多透露濒变，甏葵解决掰令基本舞题： 顶点对应和顶点插值路径。顶点对应建立起两个多边形顶点之间的对应关系；顶 点插值路径确定渐变过程中产生的中间多边形。一个好的二维多边澎渐变算法成 詈潢足： - - 0 ， 则把该边从e 中删除。射第一条边，避幸亍如上处理压，我们得到了一步过 滤后的交边集五岛 e t ( t = l , 2 ) ) 。如果l = 0 ，则e 以空集形式返阐，否则继 续接下寒数过滤步骤。 依据e 中的交边与当前传播轴的交点位于当前传播轴上的啦哪侧，交选集 可分残两个集合：e 7 一靶0 厶，自) 帮f1 c f ( f r 吐2 + ，斩 ，箕中，( 瑟+ 菇。；) 。 若蔚 o 并熙蟊 o ，则令k = - m i n ( ，褡) ，以每条交边交点到当前轴点啦的 距离的升序依次嚣自傈濑岔和f 中的如条边到豆：否受清空茸为空集。 返回e = 8 舻l l 科做为有效交边。 2 。3 。1 。3 抽取方