（计算机应用技术专业论文）网格动画编辑算法研究.pdf

浙江大学硕士学位论文 摘要 摘要 基于网格表示的动画设计在诸多领域有着广泛的应用，如计算机视频游戏， 三维动画电影，虚拟现实等。随着数字扫描仪的推广应用，网格业已成为表示 和处理场景几何的标准方式，交互的网格动画的编辑成为近年来计算机图形学 的研究热点之一。 本文提出并实现了一个基于梯度域的网格动画编辑系统。我们首先实现并 探讨了基于m u l t i l e v e l 的编辑算法【l 】。尽管该算法能满足大部分编辑要求，对 于某些特殊模型的编辑效果并不理想。经过研究实验，我们提出了基于拉普拉 斯方程的梯度域网格动画编辑新算法。算法采用关键帧编辑的思想，首先考虑 用户对某些关键帧网络的几何约束，然后将这些约束传播到整个网格动画序列， 从而产生满足用户编辑要求的新的网格动画。在关键帧编辑时，我们提出了交 替最小二乘算法，充分利用子空间变形技术和两步线性法来获得高质量的编辑 效果。同时，我们还提出了一系列实用技巧来帮助用户指定模型变化的约束条 件，简化用户的编辑操作。实验结果表明，我们的网络动画编辑系统对各种场 景都能快速获得令人满意的效果。 关键词：网格动画，多层，梯度域，关键帧，控制网格，局部坐标系 浙江大学硕士学位论文 英文摘要 a b s t r a c t d e f o r m i n gm e s hs e q u a l c e $ h a sb e e nh e a v i l yu s e di nm a n ya r e a so fc o m p u t e r g r a p h i c s ，i n c l u d i n gc o m p u t e rg a m e s ，3 da n i m a t i o nf i l m s ，a n dv i r t u a l r e a l i t y r e c e n t l y , d u et ot h eb o o s t i n gu s a g e so fd i g i t a ls c a n n i n gd e v i c e sa n dm e s h t i l e r e s e a l e ho ne d i t i n go fd e f o r m i n gm e s hs e q u e n c e sh a sb e e np a i dm u c ha t t e n t i o ni n c o m p u t e rg r a p h i c sc o m m u n i t y i nt h i sl l a e s i s w ed e s i g na n dd e v e l o pag r a d i e n td o m a i nb a s e da l g o r i t h mf o r d e f o r m i n gm e s hs e q u c 船e d i t i n g f i r s t ，w ei m p l e m e n ta n da n a l y z et h em u l t i 1 e v e l a l g o r i t h mp r o p o s e di n 【l 】a l t h o u g ht h i sa l g o r i t h mc a l lm e e t m o s te d i t i n g r e q u i r e m e n t s ，i td o e sn o tw o r kf o ras e to fs p e c i a l i z e dm e s hd e f o r m i n gt a s k s w e t h e np r o p o s ean o v e ld e f o r m i n gm e s he d i t i n ga l g o r i l h mt h a ti sb a s e do ng r a d i e n t d o m a i na n dt a k e st h es i m i l a rt e c h n i c a lw a yo f t h ek e y f r a m eb a s e dm e s ha n i m a t i o n g i v e nas e to fs p a r s ea n di r r e g u l a r l yd i s t r i b u t e dc o n s t r a i n t s 砒u n e v e n l ys p a c e k e y f r a m e s ，o u rs o l u t i o nf i r s ta d j u s t st h em e s h e so fk e y f r a m e st os a t i s f yt h e s e c o n s t r a i n t s , 柚dt h e ns m o o t h l yp r o p a g a t e st h e s ec o n s t r a i n t st ot h ew h o l es e q u e n c et o g e n e r a t en e wd e f o r m i n gm e s hs e q u e n c e t oa c h i e v ec o n v e n i e n ta n di n t u i t i v e k e y f r a m ee d i t i n g , w ep r e s e n ta l le f f i c i e n ta l t e r n a t i n gl e a s t - s q u a r e st e c h n i q u e ，w h i c h h a r n e s s e st h ep o w e ro f s u b s p a e ed e f o r m a t i o na n dt w o - p a s sl i n e a rm e t h o d st oa c h i e v e h i 曲q u a l i t yr e s u l t s w eh a v ea l s od e v e l o p e d 锄e f f e c t i v ea l g o r i t h mt oh e l pu s e l s d e f i n et h eb o u n d a r yc o n d i t i o n sf o rm e s h s e q u e n c e ，w h i c ha v o i d s m o s to f u n n e c e s s a r ye d i t i n go p e r a t i o n s o u rm e s hd e f o r m a t i o ns y s t e mh a sb e e ns u c c e s s f u l l y a p p l i e d t o a n u m b e r o f e d i t i n gs c e n a r i o sa n d a c h i e v e d v i s u a l l y p l e a s i n gr e s u l t s k e ? w o r d s ：m e s hd e f o r m a t i o n ，m u l l i - l e v e l ，g r a d i e n td o m a i n ，k e y f r a m e s ，c o n t r o l m e s h e s ，l o c a lf r a m e s 浙江大学硕士学位论文第1 章绪论 第1 章绪论 网格动画在计算机图形学的诸多领域都有着广泛的应用，如计算机游戏， 三维动画电影，虚拟现实等。日常生活中，电视广告的逼真动画，电影大片中 的可爱的角色，计算机游戏中逼真流畅的角色动作等，大部分都建立在网格动 画的基础上。随着这些数字娱乐产业工业的发展，人们对网格动画的需求也越 来越大，对网格动画的质量要求也越来越高。正因为如此，网格动画的编辑算 法越来越受到图形学研究者们的关注。 1 1 几何模型及其表示方法 在英文中，几何( g e o m e t r y ) 一词的词根来源于两个希腊单词“g e o 和 “m e t r o n ，前者是地球的意思，后者是测量的意思，几何一词最初的意思就是 测量地球。随着计算机图形学的发展，虚拟现实和数字娱乐业的发展，几何模 型早已不再是简单的“测量地球”的范畴，它是继声音、图像和视频之后又一类 新的数字媒体【2 】，正走迸人们生活的方方面面，如网格编辑，模拟仿真，辅助 设计，模型制作，互动娱乐，影视特效等，如图ll 所示 3 。 缝勺| i 慕 墨敞艇 图11 几何模型的应用领域。( a ) 网格编辑( 由浙江大学许栋，陈为等提供1 4 】) ，c o ) 模拟 仿真( 由s t a n f o r d 大学r o n f e d k i w 提供) ，( c ) 辅助设计( 来自互联网搜索) ( d ) 模型制作 ( 来自互联网搜索) ，( e ) 互动娱乐( 来自b l i z z a r d 7 “公司游戏产品w o r l do f w a r c r a f t t m 的 浙江大学硕士学位论文第1 章绪论 截屏) ， ( f ) 影视特效( i c e a g e 电影画面，由2 0 世纪福克斯影片公司提供) 。 从计算机图形学的角度看，几何模型是真实世界中各种实体的数字化表达。 几何模型的获取有多种途径，如艺术家创造，c t 断层扫描，正电子成像，对模 拟对象的测量构造以及最近的三维激光扫描等。这里不去深入讨论几何模型的 获取形式，因为我们更关心的是几何模型的表示方法。 几何模型存在着不同的分类准则【5 】。从总体上说，几何模型的表示可分为 实体表示( c o n s t r u c t i v es o l i dg e o m e t r y 。c s g ) 和边界表示( b o u n d a r y r e p r e s e n t a t i o n ，b - r e p ) 。前者描述物体占据的实体空间，后者描述物体的表面 边界。实体表示通常是将实体表示为一些基本体素的运算结果，基本体素包括 立方体，圆柱，圆锥等，运算包括并，交，差等。实体表示的优点是数据结构 简单，易于修改，缺点是形体表示受体素和运算的限制，难以绘制等。边界表 示的是实体的边界，通常由面的并集给出。其中，描述形体的信息包括几何信 息( g e o m e t r y ) 和拓扑信息( t o p o l o g y ) 6 】。几何信息描述物体的大小、形状 和位置，拓扑信息描述几何元素之间的连接关系。边界表示的优点在于方便对 物体的局部操作以及在数据结构中附加非几何信息。缺点是数据结构维护复杂。 多边形网格即是一种典型的边界表示模型，它将物体的表面表示为一系列 多边形面片的交集。而且由于当前图形硬件流水线的设计，三角形网格是当前 几何模型的主流表示方法。本文中提到的网格，如无特别说明，即是指三角形 网格。图12 给出了几何模型网格表示的示例。 除网格外，几何模型的表示还有诸如点云表示，隐示表示和体素表示等分 类方法。读者可参阅相关的文献 7 8 1 1 9 1 1 0 。 图l ，2 网格表示的几何模型。( a ) 人脸模型【1 l 】，( b ) 人体模型1 1 2 1 2 一 浙江大学硕士学位论文第1 章绪论 1 2 网格动画编辑技术简介 自2 0 世纪八十年代以来，网格编辑技术领域曾有三次大的技术突破。八十 年代的自由变形( f r e 圯- f o r md e f o r m a t i o n ) 【1 3 1 技术被称为第一次技术突破，这 个技术以操作代理模型进行网格编辑。代理模型的不同，还可分为基于网格 ( l a t t i c e ) 1 3 的方法，基于控制曲线( c u r v e ) 【1 4 1 1 构1 方法，基于控制点( p o i n t ) 【1 5 】 【1 6 1 的方法。其中根据。九十年代的多分辨率编辑f m d a r e s o l u t i o nf a i t i n g ) 技术 1 1 7 【1 8 】【1 9 】【i i 是第二次技术突破，以构造多层网格为辅助手段进行网格编辑。 近年来基于微分坐标能量方程的变形技术是第三次技术突破，其中代表性的是 拉普拉斯网格编辑算法1 2 0 】【2 1 ，【2 2 ，【2 3 】【2 4 1 等，这个技术首先构造网格变形 能量方程，然后利用线性系统的求解方法得到变形后的网格。 微分网格技术的优势在于，它不将三维网格模型视作欧氏空间中连续或离 散点集，而是将其视作定义在三维网格上的三个标量场。算法将控制空间点集 的直接坐标操作转化为间接的微分属性操作。空间点集的直接坐标虽然有助于 理解操作的几何直观性，却缺乏刻画网格局部特征的能力，而这正是微分坐标 所擅长的。正是因为如此，所以基于微分坐标的编辑算法在编辑过程中可以有 效的保持网格的几何细节特征。下面我们回顾一些主要的算法，它们构成了本 文的算法基础。 1 2 1m u l t i - l e v e l 网格编辑算法 1 1 7 1 【1 8 】【1 9 】等提出了一系列多分辨率网格处理算法。算法核心思想是首先 对原始网格进行处理，生成多层或多分辨率结构，并在此基础上实现对网格的层 次式编辑操作。这种编辑方式提供了算法对网格顶点编辑操作影响范围的选择。 在高层次进行编辑，其编辑影响范围也大，在低层进行编辑，其编辑影响的范 围小。【i i 巧妙地将m u l t i - l e v e l 的思想扩展到了网格动画的编辑算法中，并提出 了一个保持网格运动的光顺性算法，如图1 3 所示。然而，该方法没有采用【1 8 】 和拉普拉斯网格编辑算法的全局求解策略，因此在最高层次上编辑也不能保证 实现对整体网格几何的编辑操作。这意味着，用户需要非常多的交互以实现网 格动作整体编辑的效果。通过我们的实验表明，【l 】算法无法适用于某些特殊的 编辑场合。 3 一 浙江大学硕士学位论文第1 章绪论 图1 3 【i i 算法示意，上图是原始的网格动画，下图是用户编辑后的网格动画。用户在马背 上编辑出个驼峰，驼峰跟随马匹运动。 1 2 2 拉普拉斯网格编辑算法 拉普拉斯网格编辑算法近年来受到很大的关注。算法从输入网格中提取网 格本身固有的几何属性，如微分坐标等。算法将用户的编辑意图转化为对微分 坐标的局部变换。根据变换后的微分坐标，算法重建生成新的网格。在重建过 程中，用户对网格的局部编辑平滑地扩散到整个网格，产生全局的影响，这实 际上是一个非线性处理过程。求解过程可以归结为稀疏线性方程组的解算如线 性化解法 2 0 】或通过多次线性步骤【2 l 】， 2 2 ，【2 3 等，得到方程的近似解。其中， 后者解法需要给出一个旋转约束条件。在 2 4 1 的研究中，该问题可被看作一个 非线性优化问题，并无需额外的旋转约束条件。由于非线性优化往往需要大量 的迭代计算，2 4 提出了子空间( s u b s p a e e ) 的技术来加速，图1 4 。 我们在第三章提出的交替最小均方算法本质上属于非线性拉普拉斯网格编 辑的范畴，但我们的解法更加稳定和有效。 祷 图1 4 【2 4 1 算法编辑结果。网格在变形后仍能保持细节特征。 - - 4 章堵r 【2 3 蒙皮( s k i n n i n g ) 动画编辑算法 a “# 吱时三维视频游戏i 终7 。：乐川蒙皮动世，移：得了 h 好f 门心1 j 。它的最 ，、的缺。r i 足i 需要为网格定义乖球j 造 “骨架”j 氇 现a - 纾开发出目动乍 ， q 1 _ ； 功i 。“骨架”搿j g ? ：i z 2 5 ，妊纠15 ，蒙以动j 鳊蜮鳍，上仍然小能成为 分通j 的m 硌动。酗编辑力泛，坯足h 为：多数舻e l 体m 格动厦j 彳王住堆以计算 ? j 玉抒吲架”， 冬| 】5 2 5j 殚， j ，果。上乃a 使旺】j 此外，歹：丁m e s h i k l 2 6 2 7 投术再：j 必允许嗣印刁、兹供彰e 轼约寐! f j 条化i 技术最、一够：r ：足，。e 编辑过程c ，甜 1 3 研究目的和内容 教尤的动物在一翘舞缒 也有川f z 的进展，m e s h i k 敖术可 冬进行编辩 。虽然a 。j 此，m e s h 。1 k 个已变形的m 格作为参照。 m 格动画的创造是顶繁琐目耗时的艺= 术竹一，列硌动画l _ f j 住往需要耗赞 大量的m 创建 个运龚：n h 格动画不仅虹此，m 穆动：h _ 的町重肿i 件菲常低， 蚓格动碗的数据住往足根据i ) 芷场墨 j 动作构j 笠f - 咴，j ，2 ，很堆对其进行简单 的编辑使其适应，3 个场景或创造另一个动作，如对在平地卜i 奔跑的马匹进行 编辑，牛成弓匹备ij j 坡上奔跑的m 格动l 目! j 凶此，研究，箭效的网格动画编辑算 法，提高里有m 格动画数据的”t 重用性，具有非常重要的现实应用价值， 杆 对r 静态的网拼编辑算洼，网格动画算法小仅需要满足用户对特定帧模 型的编辑要求，而月还要侏汁列，冬动画的动作连蔓性j 而旧格动厕的数据 ；| “矧f 常巨大，这也对编辑算i 之的效孝提出j ，1 z 格的要求。我们在分析二：j 前 叫格动l 画编辑算洼的最莎成泉旗础f ：，设；j 实现，毖 】 m u l t i 1 e v e l 的编辑 浙江大学硕士学位论文第1 章绪论 算法。其分析细节将在第二章中详细论述。第三章中介绍了我们提出的新的基 于梯度域的网格动画编辑算法，解决了第二章m u l t i 1 e v e l 算法的不足。第四章 对全文贡献进行总结并探讨了未来的工作。 一6 一 浙江大学硕士学位论文 第2 章基于m u l t i 1 e v e l 的网格动画编辑算法 第2 章基于m u l t i 1 e v e l 的网格动画编辑算法 由于网格动画的巨大应用价值以及网格动画编辑算法本身的挑战，对网格 动画编辑的研究方兴未艾。其中一个最为新颖有效的技术路线是基于m u l t i 1 e v e l 的网格动画编辑方法。 在a c ms i g h 2 0 0 6 年年会上，【l 】提出了一种非常新颖的算法框架。 算法的核心是一个称为m u l t i 1 e v e l 的网格细节编码方式【2 8 】。这种细节编码方法 根据原始输入的动画信息定义和构造每帧网格模型上的细节向量，即为每个顶 点生成局部坐标系，并在此局部坐标系下将顶点的细节向量编码，其结果细节 向量与模型整体的几何变换无关。 在编辑过程中，用户能对网格动画中的任意帧进行任意编辑操作，算法将 用户对网格帧的编辑操作处理转化成对细节向量的操作。通过对细节向量在局 部坐标系下的转化和传递操作，将用户对单帧的编辑操作应用于网格动画的所 有序列中。 在本章中，我们完整实现并分析t i l l 算法。实验结果表明，在绝大多数网 格动画编辑应用中，算法能够满足用户的编辑要求。然而，在某些特殊的网格 动画的编辑场合，算法无法达到用户预期的编辑效果。 2 1 算法流程 算法首先将用户输入的网格动画数据处理生成m u l t i 1 e v e l 网格结构，然后 保存顶点局部坐标系以及细节向量信息。在编辑过程中，算法将用户的单帧多 分辨率网格编辑操作将应用到整个网格动画，并再结合“动画帧”信息，对模 型动画进行光顺，最后输出编辑结果。具体的算法框架见图2 1 ： 一1 一 浙江大学硕士学位论文第2 章基于m u l t i 1 e v e l 的网格动面编辑算法 输入动一教螂 图2 1 基于m u l t m e v e l 的网格动画编辑算法框架 输绽$ 结啦 2 2m u l t i 1 e v e l 网格结构 给定一个输入网格动画数据，我们首先要解决的问题就是如何表示这些网 格动画数据。这不仅决定了算法应用对象，也影响了算法的框架设计。 网格的动画需要巨大的数据量。为了存储网格动画数据，一种简单的办法 就是将每帧网格转化为三角网格。为了保证动画的连续性，网格动画的三角化 表示一般采用单个的静态三角拓扑结构，即所有动画帧的网格使用同一个三角 拓扑，每帧的三角形连接关系保持不变，网格的三角形顶点也一一对应。这种 方法的缺点是由于网格动画的每帧的细节并不一致，导致每个网格的最佳三角 化结果所需要的三角形数量并不一致。为了保证三角化顶点的对应约束，网格 动画中所有帧的三角化表示的三角形个数必须统一为集合中的最大数量。这种 策略必然造成部分网格的细节冗余。对于进行剧烈变形动作的网格动画，如飘 舞的旗帜，情况更加严重。针对这个问题，2 8 提出了一种新的m u l t i 1 e v e l 的网 格表示方法。 2 2 1m u l t i - l e v e l 网格 假设输入网格序列中的某帧网格为m o 。为了构造m u l t i 1 e v e l 网格，首先采 用网格简化算法( 如【2 9 】的q s l i m 算法) 生成一个简化网格m l ，并在m l 上定 义一系列约束边，用于连接m - 的每个顶点和m o 中的对应顶点集合。本质上， 每条约束边记录了m - 中的各个顶点由m o 中哪些顶点合并生成。重复上述简化 过程，可得一系列网格层，m 2 ，m 3 ，m 。，并同样在每两个相邻网格对之 一8 一 浙江大学硕士学位论文第2 章基于m u l t i 1 e v e l 的网格动画编辑算法 问构造约束边。在简化过程中，为了优化构造算法时间复杂度，算法以顶点个 数作为每层网格的简化目标。 由上述可知，m u l t i l e v e l 网格结构由一系列的网格层所构成，其中网格层之 间由一系列约束边所连接。m u l t i 1 e v e l 结构的每一层依然是一个完整的网格结 构，拥有完整的顶点和网格边等拓扑信息。因此，m u l t i 1 e v e l 结构中有两种不 同类型的边信息，约束边表示上一网格层中顶点与下一网格层中顶点的对应关 系，网格边表示单层网格中的顶点连接关系，如图22 所示。 m 图2 2m u l l i 1 e v e l 网格结构示意图 如果m k 层中有一个顶点p 与m k + t 层的顶点a 由某根约束边连接，则顶点a 被称为顶点v 的父顶点。相应地，顶点v 被称为顶点口的子顶点。顶点a 的所 有子顶点集嗣符号c 。表示。 顶点集信息是m u l t i 1 e v e l 网格结构最重要的信息。由顶点集信息和初始网 格m 。，可以由以下两步恢复整个结构中所有网格的顶点位置和连接关系信息。 第一步恢复网格层中的顶点位置。在采用二次最小方差f 即q e m ) 网格简 化算法时，在m o 的每个顶点v 上都汁算一个二次度量q ，。由于q ，值直接从初 始网格中计算而得，具有唯一性。而m - 层中的顶点口的二次度量值q 。可由 m k _ l 的q 。计算而得，公式如下： 浙江大学硕士学位论文 第2 章基于m u l t i l e v e l 的网格动画编辑算法 q = 。c q _ 进一步地，顶点a 的位置值可由q e m 算法结合q i 计算生成。由此，算法 可逐步恢复网格层中所有顶点位置。 第二步恢复网格层的顶点连接关系。网格层m k 的连接关系可以由网格层 m k - l 中顶点的连接关系和m k - l 和m k 之间的约束边来决定。对于m k - l 中的任意 一个三角形p ，其各个顶点映射到在m k 中的父顶点，如果三个映射后的顶点仍 然构成一个三角形，那么三者之间存在着连接关系。 由上所述，只要给定了初始网格和网格层的顶点集信息，算法可以重建所 有网格层中的顶点位置以及顶点间的连接关系，从而重建整个m u l t i 1 e v e l 结构。 2 2 2 细节向量 在m u l t i l e v e l 结构上，还可以生成网格的多分辨率金字塔结构。与【1 9 】的构 造算法不同的是，金字塔生成算法直接利用了已有的网格m u l t i 1 e v e l 结构。而 且，在网格简化算法中不再简单使用q e m 算法的二次度量值q i ，而是增加了 一个顶点二次项( v e r t e xq n a d r i c s ) 【3 0 ，目的是保证简化生成的网格拥有更规整 的拓扑结构，而网格的规整性对于网格金字塔生成中所需的网格信号处理【1 9 】 非常重要。同时，算法简化了q e m 中新的顶点位置的计算：当任意两个顶点 合并生成新的顶点时，新顶点的位嚣取两个顶点中二次误差值( q u a d r i ce r r o r ) 较小的顶点位置。 由m u l t i l e v e l 结构以及顶点位置的生成算法可知，m k + i 中的顶点“是由m k 中相应的顶点合并生成。特别地，m k 中有一个顶点w ，与m k + l 中的顶点”位 置相同为方便表示，定义两个函数：= ，( v ) ，w = ，+ 扣) 。需要指出的是，并 不是所有定点都满足，( ，( x ) ) = 工。事实上，在任意一个子顶点集合中，只有一 个顶点使得等式成立，如图2 3 所示的w 。 一1 0 一 浙江大学硕士学位论文第2 章基于m u l f i 1 e v e l 的网格动画编辑算法 图2 3r o ，r o 函数示意 为了获得网格的细节向量，需要根据网格信号处理算法，对网格模型进行 细分采样。细分过程自上向下进行，即从最高一层的简化网格进行操作。对 m k 网格层细分算法如下： 首先，调整m k - l 层中的每个顶点的位置而保持其拓扑关系不变，且使m k - t 层中每个顶点v 的位置与m g 层中的顶点，( v 1 相同。 然后，根据m k 1 层中顶点已有的顶点拓扑关系，进行g a u s s - s e i d e l 迭代操 乍0 9 ，更新m k a 层中的顶点位置。在迭代过程中，满足，( ，( x ) ) = x 关系的顶 点x 的位置不变化。 最后进行若干次无约束的j a c o b i 迭代，光顺整个网格。 以上即是对m k 网格的细分操作过程，其结果记为s u b d ( m k ) 。之所以先采 用g a u s s s e i d e l 迭代再采用j a c o b 迭代，是为了令顶点位置快速收敛，然后达到 所需要的光顺效果。 当对所有网格层进行从上向下的细分操作完成后，可以方便计算网格的细 节向量，即m k a 层中每个顶点v 的细节向量，等于v 的原始位置和s u b d ( m 1 1 中 相应顶点的位置的差值向量。 2 2 3 局部坐标系 上文中得到的每个顶点的细节向量，是记录在全局坐标系下的，因而不具 备网格的整体几何变换不变性。当对网格实施旋转和平移操作后，记录在全局 浙江大学硕士学位论文 第2 章基于m u l t i 1 e v e l 的网格动画编辑算法 坐标系下的细节向量将没有几何意义。因此，通常的做法是将细节向量保存于 顶点的局部坐标系中。 顶点“的局部坐标系的构造方法如下。首先，计算”的1 - r i n g 领域的三角 形平均法线n ，作为“的法线。其次，计算1 - r i n g 领域中连接“与两个项点的 向量e l , e z ，并计算平均向量e 。然后，构造一个临时向量x = 0 8 x e + 0 2 n ， 并计算n 与x 的叉积，得到向量y ，再计算向量y 与向量n 的叉积，得到向 量x 。对x ，y ，n 单位化，获得顶点”的局部坐标系，如图2 4 所示。实验表 明，这种方法得到的局部坐标系比直接用两个l o o p 表面切向量定义法线【3 1 】的 算法更加稳定。 e = 隧茎 厶= d o t ( g ，e ( o ) ) 0 = d o t ( g ，e ( 1 ) ) 厶= d o t ( g ，e ( 2 ) ) g = e ( o ) t + e ( 1 ) 厶+ f u ( 2 ) x l ： 其中，e 为顶点 的局部坐标系。t ，l ，t 分别是局部坐标系下的础声三 一1 2 一 茸2 章基于m u l t i 1 e v e l 的网格动画编辑算法 个值的分量。g 是细节向量的全局坐标值。e f o ) 表示矩阵的第一行向量，只( 1 ) 表示矩阵的第二行向量，只( 2 ) 表h ：矩阵的第三行向量。 2 2 4 网格重建 不难发现，根据最项层的简化网格m 。，各网格层之间的r 0 ，以及r + 0 函数 以及所有m u l t i l e v e l 网格层的细节向量，r 以依次构造生成6 d ( m 。) ，根据 m “中保存的细节向量，恢复m 。层模型的信息。 23 多分辨率网格编辑 基于m u l t i l e v e l 的删格编辑首先需要对用户输入的网格动画数据进行预处 理，生成网格结构并保存所需的顶点局部坐标系以及细节向量信息。处理完成 后，用户可咀对网格动画的任意帧进行任意的编辑操作，如拖拉旋转顶点位置 等，如图25 所示。 圈25 颀c 皇自由拖拉的网格编辑方式 算法将用户对网格的编辑操作转化为对细节向量的信号处理，如放大，缩 小等。用户对单帧的网格编辑操作完成后，算法将对它的处理模式应用到网格 动画中的其他所有帧，生成相应的网格信息，从而实现用户对网格动画的编辑 操作。 需要指出的是，用，1 可以在m u l t i 1 e v e l 网格结构的不同层进行操作，从而 1 1 浙江大学硕士学位论文第2 章基于m u l t i i c v c l 的网格动画编辑算法 影响了某个顶点的编辑操作范围。这是由m u l t i 1 e v e l 本身的特性决定，因为简 化网格的顶点由大量的子顶点合并生成。因此，在越高的网格层进行顶点操作， 其对最初网格的影响范围也越大。 2 3 1 编辑算法 编辑算法首先需要解决的问题是如何保存用户的编辑操作。假设用户对某 简化层k 的某顶点“进行了拖拉等编辑操作，直接将用户的操作保存在当前层 的顶点中会造成一个问题。原因是网格简化算法并不保证原始网格按照同样的 方化生成简化网格，这意味着用户当前编辑的顶点在另一帧相应的网格层中 并不一定存在。因此，直接在当前层的顶点中保存用户的编辑操作会对算法将 编辑应用到所有网格动画帧造成困难。 解决办法是将用户的编辑操作统一转换并记录在每帧的原始网格中，由于 输入的原始网格动画的各帧之间的顶点一一对应，因此避免了前述问题。 如图2 6 所示，编辑算法的主要步骤如下所述。当用户对某简化层k 的某顶 点“进行拖拉编辑操作后，算法自动将用户的编辑操作复制，并将其应用到原 始网格m o 中的所有”的子结点。当用户编辑完成后，算法将m 。层中保存的编 辑操作应用到其它帧中，然后进行网格层自底向上更新操作。 i v i k 卜一一 埘 ( r ) i ( 甜 ) 图2 6 编辑操作的转移和记录示意 编辑算法需要解决的第二个闽题是如何保证用户的编辑操作互不影响，这 对于用户的交互式操作非常重要。如果用户的编辑操作互相影响，那么为了达 到某种编辑效果，用户必须按照某种特定顺序进行顶点编辑操作，这将对用户 编辑造成极大不便。尽管我们可以将用户的编辑操作保存在顶点的局部坐标系 中，避免编辑操作与网格整体的几何变换有关，但这种处理方式并不能保证用 户编辑操作之间的独立性。这是因为，一旦用户对某个顶点进行了编辑操作， 一1 4 一 浙江大学硕士学位论文 第2 章基于m u l t i - l e v e l 的网格动画编辑算法 当前顶点以及其1 - r i n g 领域内顶点的局部坐标系将相应变化。 解决办法是对用户的编辑操作赋予一系列坐标系转换。假定用户对m k 层的 顶点“进行了拖拉操作，顶点的平移表示为全局坐标系下的向量e 。算法为每 个顶点引入一个不变的局部坐标系，c ，它可从最初生成的m u l t i l e v e l 网格结 构计算得到。令 2 = f ：f - 、e 由上式可知，e 是保存在全局坐标系中的独立向量。令； 矿= ( ，“) ( ) v 是顶点”在m o 层的子顶点集。对于顶点集矿中的所有顶点h 令 巳= ( 巧) 。口 由此，算法将用户的编辑操作保存到每帧的原始网格中，且保证了用户的 编辑操作互不影响。由于用户在不同网格层的编辑操作会对最终结果造成不同 的影响，因此算法不仅在原始网格中保存了用户的编辑操作，还需要记录用户 的网格编辑层。这些保存的信息足够满足算法对用户的编辑操作后期处理的需 要，生成用户对网格动画最终的编辑结果。 编辑算法的第三个问题是如何生成最终的编辑结果。给定一个在原始网格 层中的顶点集v ，顶点集中每个顶点v 的操作巳以及用户的编辑层k 。重建生 成算法如下所述：令 u = ，o ，) u 为网格层k 中由顶点集矿合并生成的顶点集合。对于u 中的每个顶点4 ， 令 = ( ，。) ( ) 矽即顶点”在原始网格层中的所有子顶点集，计算顶点4 的平均编辑向量a 口= c 。( ( 。，e 气) 1 w f ) 得到了网格层k 中顶点“的最终编辑向量。再通过上文所述的网格重建算 法，算法即可生成最终的编辑结果。 一1 5 - - 浙江大学硕士学位论文第2 章基于m u l t i 1 e v e l 的网格动画编辑算法 由上文论述可知，将用户的编辑操作保存在原始网格中是个非常有用的 特性。它保证了用户的编辑操作各自独立，还可以使用户的编辑操作具有光顺 的效果。即，如果用户在某帧某层上对两个不同顶点进行了编辑，当算法应用 到网格动画的另一帧上，在这一帧中用户的编辑操作影响了简化网格层中同一 个顶点，这时候用户的编辑操作即具有了光顺的效果。这是因为算法将用户的 编辑操作统一保存到原始的网格中，用户所有的操作被视为一个统一的编辑集。 当算法将编辑集应用到网格动画的其它帧上时，根据顶点平均编辑向量的生成 算法，用户的编辑操作被自然地平均应用到顶点”上。 2 3 2 局部约束 局部约束编辑操作是一个非常有用的编辑操作，它使得用户可以指定模型 动画的某个部分固定不动，从而实现一些特殊的操作效果，如固定飘舞布的端 点等，如图2 7 所示。 图2 7 固定布的端点 局部约束操作实际上是上文所述的编辑算法的一个扩展。首先，用户指定 网格动画中的约束点，算法提取约束点的全局坐标系位置。算法将用户设定的 约束点位置转换到原始网格中相对应的子顶点集v 中。与此同时，算法还保存 用户设定的约束点能影响的最高层数，k 。从原始网格的顶点集矿中的顶点v 到 简化模型层中的顶点，( v ) ，都将受到用户设定的约束点影响。如果原始网格中 一1 6 浙江大学硕士学位论文 第2 章基于m u l t i 1 e v e l 的网格动画编辑算法 两个不同的约束点位置最终影响了简化层中的同一个项点，那么这个顶点的最 终约束位置可以由前述光滑方法获得。 由上文所述的可知，选择不同的k 值将决定约束点对最终编辑结果造成影 响的范围。k 值越小，影响越小。一个极端的情况是，如果k 值定为0 ，那么用 户指定的约束点将只能影响最终网格的单个顶点。如果k 值选择最简化的网格 层，那么用户指定的约束点将会影响绝大部分顶点。 用户设定的约束有两种类型，一种是硬约束，即最终生成的网格中顶点的 位置必须与用户指定的位置相同。这种策略可以保证编辑结果的位置精确性， 但由于网格动画的动作可能非常剧烈，所以硬约束可能会造成最终生成的网格 表面不够光滑。一种是软约束，即最终生成的网格中顶点的位置不必与用户指 定位置相同，以使得最终生成的网格足够光滑。用户可以根据编辑的需要，选 择适当的约束类型。 与前文所述的编辑算法不同的是，用户指定的局部约束在网格重建过程中 和顶点的细节向量并没有直接关联。在网格重建过程中，如果用户指定的约束 类型是硬约束，那么受影响的项点，如k 层的顶点”，将忽略顶点本身的细节 向量而被直接移到约束指定的位置。如果用户指定的约束类型是软约束，与硬 约束不同的是，顶点”的最终位置是用户指定的约束位置和网格重建过程中细 分算法计算得到位置的加权平均。 2 4 模型动画光顺 前文所述的m u l t i - l e v e l 的网格结构并没有牵及到网格动画数据整体的光顺 性，因为在构建m u l t i 1 e v e l 网格结构时，算法对输入数据是逐帧处理的。由上 文描述可知，算法的核心构建在m u l t i 1 e v e l 中含有的子节点集信息上。然而， 算法无法保证对不同帧的网格构建生成的子节点集结构一致。特别是输入的网 格动画数据可能会有幅度大的变形。因此，如果不调整网格动画帧之间的节点 集关系，而只是简单地将用户对某帧的操作应用到其它帧，得到的网格动画编 辑效果不够理想。 一1 7 一 浙江大学硕士学位论文第2 章基于m u l t i 1 e v e l 的网格动画编辑算法 2 4 1 基本光顺算法 【2 8 提出了一个节点集调整算法。算法为网格动画中的每帧构建各自的层次 关系，即子节点集信息，然后通过交换调整网格动画帧的层次关系，使得网格 数据的任意简化层都能够实现光顺的动画效果。 2 4 2 改进光顺算法 由m u l t i l e v e l 网格编辑算法的特性可知，算法最终生成的网格严重依赖于 m u l t i - l e v e l 层次关系。由于算法在细分步骤所采用的迭代算法与网格本身的拓 扑结构息息相关，m u l t i 1 e v e l 层次关系的任意一点变化，都会造成最终网格形 状的变化。尽量基于交换的光顺算法可以使这种变化尽量少，但还是可能产生 网格形状局部跳跃的现象。 为了解决这个问题，算法首先提出了“动画帧块”的概念。尽管整个动画 数据包括各种不同动作，但为每帧动画构建不同的层次关系再进行交换操作并 不必要，这是因为在局部连续的几个动画帧中，网格的动作往往并不明显。算 法完全可以为这些“动画帧块”使用相同的层次关系而不影响生成的m u l t i 1 e v e l 结构的质量。为了在网格动画数据中划分出“动画帧块”，算法设计了评价使用 的层次关系的质量的变量，如果变量的值超出系统给定的阈值，系统将自动进 行交换操作，改进网格使用的层次关系，然后将新生成的层次关系作为下一个 “动画帧块”共同使用的层次关系。 “动画帧块”的概念不仅可以改进最终算法生成的动画质量，还可以极大 地改进算法的效率。 “动画帧块”实际上减少了动画数据的帧数，对于动作变 化平缓的情形，“动画帧块”的加速效果更加明显。经过实验表明，算法通常有 5 1 0 倍的加速效果。 迸一步地，算法提出了“块光顺”的技术。在处理动画数据的某帧时，算 法不仅使用当前数据帧的层次关系来生成顶点的位置，还使用当前帧所在“动 画帧块”相邻的几个“动画帧块”的层次关系信息来生成顶点的位置。顶点位 置的最终值由这些计算生成的位置值加权平均得到。请注意，简单地对原始每 帧各自生成的顶点位置进行加权平均的方法虽然简单直观，却会使得网格动画 的动作细节丢失，造成不正确的结果。 一1 8 - 浙江大学硕士学位论文 第2 章基于m u l t i l e v e l 的网格动画编辑算法 “块光顺”技术在获得更高质量的网格动画数据的同时，也会造成性能的 损失。假设网格帧使用 个“动画帧块”的层次关系，算法的速度将会降到原 来的1 厢。在实际应用中，n 值一般为1 5 即可达到满意的光顺效果。 2 5 实验结果及不足 我们在一台普通p c 机上实现了基于 1 】算法的网格动画编辑系统，并且成 功地将算法应用到若干的编辑操作中，如马匹长驼峰，布匹约束编辑等，其结 果见图2 8 ，图29 。 麓飞 输 纛 i 篱；。 蓼i i “” 整 蘩戮i 糍黧 鬻露器黪 k 遥魏 敞 ，下图是编辑后的网格动画 图2 9 布匹约束编辑，上图是三帧原始网格动画，下图是约束编辑后的网格动画 1 9 一 l蠢i 淞淞一急、一 目d 目 浙江大学硕士学位论文 第2 章基于m u l t i 1 e v e l 的网格动画编辑算法 当我们将算法应用到一个特殊的动画场景，如一根本身高度扭曲的长方块 的变形动画时，发现编辑结果并不符合我们的预期，如图21 0 所示。经过分析 研究，可知这是 1 】算法的一个缺点。算法将用户的编辑操作保存在顶点的局部 坐标系中t 而扭曲的长方块各个顶点的局部坐标系非常不规整，坐标系朝向非 常不连续，造成用户保存在这些顶点局部坐标系下的操作不能反应用户整体的 操作意图。因此，当算法尝试将用户的编辑操作应用于整个动画数据帧时，生 成的编辑结果自然不能符合用户的要求。 a 誉尹八、 图21 0 算法的缺点，( a ) 是原始的动画序列。我们将动画的第一帧进行编辑，如( b ) 的左 图所示。( b ) 的中图和右图是【l 】算法自动生成的结果。 浙江大学硕士学位论文 第3 章基于梯度域的网格动画编辑算法 第3 章基于梯度域的网格动画编辑算法 如第二章所述可知，基于m u l t i 1 e v e l 的网格动画编辑算法能够满足大部分 的编辑应用。对于某些特殊模型和场景，算法的编辑效果并不理想。 我们提出的基于梯度域的网格动画编辑算法采用了关键帧技术路线。算法 首先将用户或环境对关键帧网格的编辑意图转换为几何约束，对单帧网格实施 编辑操作，然后将这些约束传播到整个网格动画序列，从而产生令用户满意的 新的网格动画。特别地，我们提出了交替最小二乘求解策略，充分利用了子空 间变形技术和二次线性解法，获得了高质量的编辑效果。我们还开发了一系列 算法辅助用户快速指定模型变化的约束条件，从而简化用户的编辑操作。 我们将新开发的基于梯度域的网格动画编辑系统成功应用于各种动画编辑 场景中，有效克服了【l 】算法的不足。我们还在系统基础上实现开发了一系列的 高级动画应用，如脚印编辑，路径编辑，时域滤波，基于操作柄( h a n d l e ) 的运动 合成，时空变形等。 3 1 设计目标 网格动画的编辑算法比静态网格的编辑算法有更高的要求，不仅需要