（计算机软件与理论专业论文）离散细分骨髓动画的研究与应用.pdf

摘要 摘要 本文针对离散细分方法进行了研究，并在骨骼动画中进行了应用。 计算机动画是计算机图形学和艺术相结合的产物，是伴随着计算机硬件和图 形算法高速发展起来的。而骨骼动画是计算机动画中较新的技术，它应用在复杂 的动画几何体造型中，。大大改进了过去采用的单一网格动画方法的效果。系统是 由骨骼组成的骨架结构，以及表面网格组成。网格顶点的位置和骨架本身相关， 当移动骨架的时候，组成多边形的顶点的位置也相应改变，比起单一网格动画提 高了灵活性。 本文提出了由骨骼动画的给定关键帧( k e y f l a m e ) 生成中间帧的四点法方法。 通过用程序实现了一个“层次结构的人”行走动画的样例，实践了四点法的中间 帧生成方法。并r l - t ；较分析了四点法中间帧生成方法同传统动画中间帧生成方法 的优劣，以及该方法的适用范围。 本文描述了三维骨骼动画生成方法，并且给出了三维骨骼动画的实例。文章 探讨了3 d 骨骼系统的建立过程。包括数据模型的来源，以及程序的实现，重点 探讨了基于骨骼结构下表面造型方法。本章最后提出了用细分方法来实现骨骼动 画的思想，探讨了细分方法实现骨骼动画的应用前景和l o o p 细分的实现方法。 本文提出的细分骨骼动画系统可以应用在游戏引擎系统中。尤其是在网络条 件下和嵌入式设备条件下对动画数据的表示和传输的效率有所提高，因此有较好 的应用前景。 关键词：骨骼动画，细分方法，离散造型方法，关键帧动画 离散细分骨髂动画的研究与应用 a b s t r a c t i nt h i sp a p e r , as u b d i v i s i o nt e c h n i q u eo fs k e l e t a la n i m a t i o ni sp r o p o s e d c o m p u t e ra n i m a t i o ni s t h ec o m p o s i t i o no fc o m p u t e rg r a p h i c sa n da r t a n di ti s t h en e w t e c h n i q u ew i t h t h ed e v e l o p m e n to ft h eh a r d w a r ea n d g r a p h i cm e t h o d s k e l e t a l a n i m a t i o ni sam a i nm e t h o dt or e p l a c et h ei n g l em e s hm o d e la n i m a t i o n s k e l e t a l a n i m a t i o nr o o d e lc o i l s i s t so fs k e l e t o n sa n dt h es u r f a c em e s ka n dt h es k e l e t o l l sd e c i d e t h ev e l l e x e si nt h es u r f a c e t h ek e y f r a m en e e d n ts t o r et h ei n f o r m a t i o no ft h es u r f a c e ， s oi ti sv e r y s i m p l i f i e d s u b d i v i s i o nm e t h o d sa n da n i m a t i o nt e c h n i q u ea l er e v i e w e di nc h a p t e r1a n d c h a p t e r2 i i lc h a p t e r3 。as k e l e t a la n i m a t i o ni sp m d u c e d 。t h es a m p l ei sar a o v i n g m a l la n dan e wi n t e r p o l a t i o nm e t h o di sg i v e nh e m t h eu s u a lm e t h o d so fb u i l d i n g i n - b e t w e e n 矗 a l n e si n c l u d el i n e a l i n t e r p o l a t i o n m e t h o da n d h i g j a c r o r d e r s p i n e i n t e r p o l a t i o n t h ep a p e ru s ef o u r - p o i n tm e t h o dt ob u i l di n - b e t w e e nf r a m e s i nc h a p t e r 4 ，3 ds k e l e t a la n i m a t i o ni sd e s c r i e da n dp r a c t i c e d t h e p m c e s sf r o mt h ec r e a t i o no f t h em o d e lt oo r g a n i z i n gt h ep m g r a r ai sd i s c u s s e d a t l a s t ，as u b d i v i s i o ns k e l e t a l a n i m a t i o ni d e ai sg i v e n a n dl o o ps u b d i v i s i o nm e t h o dw i l lb eu s e dt or e a l i z et h i s m e t h o d s u b d i v i s i o ns k e l e t a la n i m a t i o nw i l lh a v ea s p r e a dp r o s p e c t i nt h ed a t a r e p r e s e n t a t i o na n dt r a n s p o r t a t i o no f n e t w o r kg a m e sa n dm o b i l ed e v i c eg a m e s k e y w o r d s ：k e y f r a m e s a n i m a t i o n ；s k e l e t a la n i m a t i o n ；s u b d i v i s i o n ； - 前言 日u 舌 本课题的来源是广东省关键领域重点突破项目招标中的课题3 ：互联网文化 娱乐软件开发。本项目是由珠海金山软件股份有限公司与中山大学联合开发、研 制和市场推广，目的是研发出一套有自主知识产权、可供第三方使用的网络游戏 通用引擎，并在此基础上开发一系列有示范性的网络文化娱乐软件产品。其中网 络游戏通用引擎将包括一套完整的游戏开发工具与运行基础，形成和完善游戏所 需的最核心的关键技术，打破关键技术被国外垄断的局面，极大缩短游戏产品的 开发周期，降低游戏开发技术难度。我们力争成为国内网络游戏开发和运营的领 先企业，为推动中国网络游戏的开发和运营作出自己的贡献。 以嗣格细分( s u b d i v i s i o n ) 为特征的离散造型，与传统的连续造型相比，大有 后来居上的创新之势。这种曲面造型方法在生动逼真的特征动画和雕塑曲面的设 计加工中得到了高度的运用。 通用游戏引擎系统的一个关键部分就是三维角色实时动画系统。三维动画实 时系统提供游戏角色建模及相应的骨骼动画系统、皮肤动画系统，i k ( i n v e r s c k i n e m a t i c s ，反向动力学) 技术，实现三维角色实时动画工具，并建立面向三维 角色游戏的人体运动数据库，为三维网络游戏中的角色生成建立一个良好的角色 运动数据采集与生成环境。两实现三维角色实时动画系统的技术基础是计算机动 画技术。 计算机动画是计算机图形学和艺术相结合的产物，它是伴随着计算机硬件和 图形算法高速发展起来的一门商新技术，它综合利用计算机科学、人工智能、艺 术、数学、物理学和其它相关学科的知识在计算机上生成绚丽多彩的连续的虚拟 真实画面，给人们提供了一个充分展示个人想象力和艺术才能的新天地。角色模 型在屏幕上看起来的效果如何、怎样容易创建模型、纹理、动画，这些对于现代 游戏试图完成的消除视觉上的不可信因素来说至关重要。角色模型系统因此页逐 渐变得复杂起来，包括较高的多边形数量模型，和让模型在屏幕上移动的更好方 式。为了满足上面的要求，使用一个骨骼模型系统这种有较大优越性的动画系统 是相当必要的。 真骼动画系统是目前流行的游戏引擎系统中重要的一部分。它不同于以往基 离散细分骨骼动画的研究与应用 于网格的系统。在基于网格的系统，对于每一个动画帧，要定义模型网格的每个 点在世界中的位置。对于一个包含2 0 0 个多边形的手的模型，有3 0 0 个顶点， 如果动画有1 0 帧，那么就需要在内存中有3 0 0 个顶点位置的数据。总共有3 0 0 x 1 0 = 3 0 0 0 顶点，每个顶点由x y z 和颜色j a l p h a 信息组成。你能看见这个增 长起来是多么的快。q u a k ei 。i i 和i 都使用了这种系统，这种系统确实有动态 变形网格的能力，比如使裙子摆动，或者让头发飘动。相比之下，在骨骼动画系 统，网格是由骨架组成的骨骼( 骨架是你运动的对象) 。网格顶点和骨架本身相 关，所以它们在模型中的位置都是相对于骨架，而不是网格代表每个项点在世界 中的位置。因此，当移动骨架的时候，组成多边形的顶点的位置也相应改变。因 此只是只要使得骨骼运动，典型情况大约有5 0 个左右的骨架，明显节省了内存。 细分算法目前在计算机动画行业中的应用已经普遍与成熟。大量造型软件都 已实现了细分曲面的造型功能。本文将在第四章给出细分方法实现骨骼动画的分 析。 本文的章节结构是： 第一章，回顾离散的曲面造型方法。 第二章，计算机动画的概述。 第三章，关键帧骨骼动画的一个实例。 第四章，离散细分方法来实现三维骨骼动画。 第五章，结论和总结。 本文的程序实现是本文在v c + + 环境下，通过o p e n g l 技术完成。其中核心 算法在第四章和第五章的章节里面给出。 本文的结果可以应用在游戏引擎系统中，作为骨骼动画子系统部分。其中细 分骨骼动画的思想实现了多分辨率几何数据，将会对动画数据的网络传输以及嵌 入式设备中三维动画数据的表示传输等领域产生实际的应用效果。 第1 章高散曲面遣型方法 第1 章离散曲面造型方法 1 1 曲面造型的发展状况 曲面造型( s u r f a c em o d e l i n g ) 是计算机辅助几何设计( c o m p u t e r a i d e d g e o m e t r i cd e s i g n ，c a g d ) 和计算机图形学( e o m p u t e rg r a p h i c s ) 的一项重要内容。 主要研究在计算机图象系统的环境下对曲面的表示、设计、显示和分析。 伴随着问题和实际需要，曲面造型不断向前推进。1 9 6 4 年美国麻省理工学院 一“ 一，+ 、 、 的c o o n s 发表一种具有一般性的曲厦描述方法，给定围成封闭盐线的四条边界就 可定义一块曲面。但这种方法存在形状控制与连接问题。1 9 7 1 年法国雷诺汽车 公司的b e m e r 提出一种由控制多边形设计曲线的新方法。这种方法不仅简单易 用，而且漂亮地解决了整体形状控制闽题，但仍存在连接问题和局部修改问题。 1 9 7 4 年g o r d o n 和r i e s e n f e l d 提出了b 样条方法。这种方法继承了b e z i c r 方法的 一切优点，克服了b e z i e r 方法存在的缺点，较成功地辑决了局部控制问题，又轻 而易举地在参数连续性基础上解决了连接问题，从而使自由型曲线盐面形状的描 述问题得到较好解决。但b 样条方法不能精确表示圆锥截线及初等解析曲面， 这就造成了产品几何定义的不唯一，使曲线曲面没有统一的数学描述形式，容易 造成生产管理混乱。为了满足工业界进一步的要求，1 9 7 5 年美国s y r a c u s e 大学 的v e r s p r i l l e 首次提出有理b 样条方法。后来由于p i e g l 和t i l l e r 等人的功绩，终 于使非均匀有理b 样条( r a j r b s ) 方法成为现代曲面造型中最为广泛流行的技术。 n o r b s 方法的提出和广泛流行是生产发展的必然结果。 近几年，随着计算机图形显示对。f 真实性、实时性和交互性要求的日益增强。 随着几何设计对象向着多样性、特殊性和拓扑结构复杂性靠拢趋势的日益明显， 随着激光测量扫描等三维数据采样技术和硬件设备的日益完善，曲面造型得到了 长足的发展。这主要表现在研究领域的急剧扩晟和表示方法的开拓创新。 从研究领域来看，曲面造型技术已从传统的研究曲面表示、曲面求交和曲面 拼接，扩充到曲面重建、曲面简化、曲面变形等。 曲面重建( r e c o n s t r u c t i o n ) ：从曲面上的部分采样信息来恢复原始曲面的几何 模型，称为曲面重建。采样工具为激光测距扫描器，医学成象仪等。根据重建曲 面的形式，它可分为函数型曲面重建和离散型曲面重建这两类。前者的代表工作 离散细分骨骼动刨的研究与应用 有e c k 于1 9 9 6 年建立的任意拓扑b 样条曲面自动重建法和s a p i d i s 于1 9 9 5 年创 造的离散点集拟合法。后者的常用方法足建立离散点集的平面片逼近模型，它要 求输出曲面具有正确的拓扑结构并且随着采样密度的增加而收敛到原始曲面。曲 面重建的研究在最近几年形成了热潮，与层出不穷的各种三维采样设备的演示展 销相配合，这几年国际图形学会议s i g g r a p h 上有多篇文章对此进行专题报告。 曲面简化( s i m p l f f i e a t i o n ) ：与曲面重建一样，这一研究领域目前也是国际热 点之一。其基本思想在于从三维重建后的离散曲面或造型软件的输出结果( 主要 是三角网格) 中去除冗余信息而又保证模型的准确度，以利于图形显示的实时性、 数据存储的经济性和数据传输的快速性。 从表示方法来看，以网格细分( s u b d i v i s i o n ) y g 特征的离散造型，与传统的连 续造型相比，大有后来居上的创新之势。而且，这种曲面造型方法在生动逼真的 特征动画和雕塑曲面的设计加工中得到了高度的运用。在1 9 9 8 年的s i g g r a p h 国际图形界盛会中，所报告的十篇关于曲面造型的论文有九篇是关于曲面离散造 型的算法或者在离散型曲面上精确求值及适当参数化的工作。从这里我们可以看 出当今国际图形界在曲面造型理论研究和实际应用中的热点所在。 在1 9 9 8 年荣获奥斯卡大奖的电影作品中，有一个短篇赫然在列，这就是美 国著名的p i x a r 动画电影制片厂选送的作品“g e r i sg a m e ”。动画片描述了一个名 叫g e r i 的老头，在公园里自己对自己下国际象棋，千方百计想取胜的诙谐故事。 动画中人物和景色的造型细致生动，与故事情节浑然一体，使观众得到真正的视 觉美的享受。而g c r i 老头的头壳、手指和衣服，包括茄克衫、裤子、领带和鞋 采用的是c - c 细分曲面造型法。这些都是传统的n u r b s 连续曲面造型所不易做 到的。单一的n u r b s 曲面与其他参数曲面一样，仅限于表示在拓扑上等价于一 张纸、一张圆柱面或一张圆环面的曲面，不能表示任意拓扑结构的曲面。为了表 达特征动画中更复杂的形状，如人的头、手或服饰，我们面临着一场技术挑战。 当然，我们可以用最普通的复杂光滑曲面的造型方法，例如采用n u r b s 的修剪 技术，但是修剪是昂贵的，而且有数值误差：要在曲蔼的接缝处保持光滑，即使 是近似的光滑也是困难的，因为模型是活动的。而细分曲面有潜力克服以上两个 困难，它们无须修剪，活动模型的平滑度被自动地保证。 另外，在网格简化和细分基础上产生的多分辨率模型也是近几年几何造型领 第1 章高散曲面造型方法 域中的一个研究热点。多分辨率模型是一种对物体的多层次表示方法，它通过建 立多个近似简化模型来表示原始模型不同程度的细节。应用多分辨率技术，绘制 程序就可以根据需要选择相应的细节层进行编辑、显示，这样就避免了因绘制那 些意义相对不大的细节而造成的资源浪费，从而可以在有限的硬件条件下取得更 快的绘制速度和更逼真的绘制效果，而且，它可以根据实际需要对模型的编辑区 域进行有效地控制，实现模型的多分辨率编辑。 1 2 曲面细分方法概述 1 2 1 细分算法介绍 细分是基于曲面片和多边形的一种巧妙结合，从而使之一方面可以表示任意 的拓扑结构，另一方面其曲面又满足一定的光滑性要求。细分曲面算法是一种递 归结构，可以非常自然的实现分级渲染和误差范围内的逼近，特别适于多分辨率。 同时它还具有有限元分析所要求的良好特性，适于3 d 曲面的数据重建，以及计 算简单高效等优点。各大涉及造型的软件公司包括m i c r o s o l f t ，i n t e r , m m 等都对 细分造型给以了非常寅的重视l ，绸盐造型鲍原跫已经在商端动画软件和许多商业 造型软件如m a y a ，m k a i , 3 d s t u d i om a x , 1 , i g h t w a v e 等软件中使用。 最早的两个基本细分曲面( s u b d i v i s i o ns u r f a c e s ) 是1 9 7 8 年c a t m u u 和c l a r k 提 出的双三次b 样条曲面c a t m u l l c l a r k 方案 1 4 1 与d o o 和s a b i n 提出的双二次b 样条曲面d o o s a b i n 方案【1 5 】。随后，1 9 8 7 年l o o p 提出了基于箱样条的三角网 格逼近细分算法 1 6 1 。1 9 9 0 年d y n 等提出了基于三角网格的插值b u t t e r f l y 细分 算法【1 7 】。尽管从1 9 7 8 年到1 9 9 5 年一些著名的细分算法被提出，但是细分在曲 面异常点附近性质的一些基本问题一直没有解决，直到1 9 9 5 年r e i f 的关于细分 c 1 连续的工作【1 8 】。从此新的细分理论及实际应用开始盛行，经典的细分方案被 分析，新的细分方案被提出，具有c 1 和c 连续的一般理论得到发展。1 9 9 6 年到 1 9 9 8 年一些权威性的结论被取得。1 9 9 6 年z o r i n 等扩展了d y n 的b u t t e r f l y 方案 提出了修改的b u t t e r f l y 细分1 1 9 。k o b b e l t 提出了插值四边域方案 2 0 1 。1 9 9 8 年 s e d e r g 等提出了非均匀细分曲面( d o o - s a b i n 和c a t m u l l - - c l a r k ) ，特别说明的是， d d e r o s e 采用c a t m u l l - - c l a r k 细分方案用于特征动画，c g a n i m a t i o ns t u d i o s 的 成功运用标志着细分曲面在曲面造型中开始发挥重大的作用。 离散细分骨骼动威的研究与应用 1 2 2 细分算法定义及特点 细分算法定义一个光滑曲面作为对一个任意拓扑的初始控制多边形进行一 系列连续细化的极限1 6 1 。但在实际应用中，我们往往只需执于亍有限的细分步骤 即可满足要求。本质上，细分曲面技术提供了一种多分辨率造型的机制。整个过 程借助于图1 1 描述为：给定一个具有任意拓扑的初始网格 彳”，根据一定的 细分算法插入新的顶点，修改点的连接关系，按一定的几何规则计算插入点的位 置( 如果是逼近细分算法，还需要计算原顶点的位置) ，反复几次操作，可以得 到一个满足一定光滑条件的曲面。所以细分算法可以看作是初始网格+ 拓扑规则 + 几何规则这样一个模式。 其特点为： ( 1 ) 任意拓扑：细分算法对任意拓扑网格都可以产生经典的样条曲面片，不 用考虑曲面片之间的拼接问题。 ( 2 ) 可量测性( s c a l a b i l i t y ) ：由于它的递归结构，细分自然地提供了在误差范 围内的层次细节渲染和自适应逼近，这样算法可以充分地帚j 用有限的硬件资源， ( 3 ) 表达的一致性( u n i f o r m i t yo fr e p r e s e n t a t i o n ) ：传统的大多数模型或者用 多边形鼹格表示或者用样条曲面片表示。细分算法是对两个极端进行了巧妙的结 合。曲面可以看作由许多曲面片构成，也可以看作由许多多边形构成。细分算法 对所有细分层提供了一个一致的曲面表示。 图1 - 1 细分过程 ( 4 ) 数字稳定性( n u m e r i c a ls t a b i l i t y ) ：细分产生的网格有许多有限元方法没 有的性质，细分算法可以很好的适用于许多数字仿真中。这在工程和计算机动画 中是非常重要的。 ( 5 ) 代码简单：细分算法应用简单，执行起来有效，在最终的应用中凡乎不 第1 章高散曲面造型方法 设计到较深的数学分析。 1 2 3 一纽分算法分类 根据产生的网格类型可以分为三角域网格( t r i a n g u l a rm e s h e s ) 和四边域网格 ( q u a dm e s h e s ) 。对一个网格来说，用面来识别是非常自然的。如果面是规则多 边形，则可划分为三角形、四边形和六边形等。根据实际情况前两种比较常见， 这就产生了基于三角域和基于四边域两种规则细分方案。 根据细分规则的类型可以分为顶点插入( v e r t e xi n s e r t i o n ) 和割角 ( c o m e r - c u t t i n g ) 。一旦平面域定下之后，我们就需要对网格进行细化。如果三角 网格或四边网格的每一条边一分为二，旧的网格顶点保留，插入到边的新顶点被 连接；四边域网格的每一个面额外插入一个顶点。这种情况称为顶点插入，如图 1 - - 2 ( a ) ( b ) 所示。如果对每一个旧面，一个新的相似面在旧面内创建而且新 创建的面相互连接。这样，我们可以认为每一条旧边产生四个新点，每个边和顶 点创建一个新面，i t t 的顶点被抛弃。几何上，我们可以认为这个过程是先切除顶 点，然后再切除多边形的边。这种情况称为割角，如图1 - 2 ( c ) 所示。 一 一 i l 1 i 一画 ( a ) 四边域的顶点插入( b ) 三角域的顶点插入( c ) 四边域的割角 图1 - 2 细分规则类型 另外，根据顶点插入方案可以分为插值( i n t e r p o l a t i n g ) 细分与逼近 ( a p p r o x i m a t i n g ) 细分。如果基网格的顶点不在极限曲面上，而且每一次细分，现 存的顶点逐渐靠近极限曲面，生成的最终曲面趋向光顺，这个方案我们称逼近。 否则，基网格的顶点在极限曲面，每细分一次，现存顶点不动，而且从基网格就 可以看出极限曲面的形状这种方案我们称之为插值。由于插值方案定义的曲面 初始控制点也是极限曲面上的点，这样就使曲面具有较好的保形性，而且，可以 离散细分骨骼动画的研究与应用 以一种更直观的方式控制。但是其曲面的质量不如逼近方案的好，收敛于极限曲 面的速度也不如逼近方案快。 表1 1 列出了典型细分算法的分类。 表1 - 1 典型细分算法分类 顶点插入割角 三角阿格四边域网格 插值 m o d b m t e d l y k o b b e l t d o - - s a b i a 逼近 l o o p c a t m u l l - a a r k 细分算法的一些概念和术语： 点的连通度( v a l c c e ) - 与某一顶点相连的边的条数称之为该点的连通度。 规则点和异常点( e x t r a o r d i a r y ) ：基于三角网格的细分方案在内部产生的新 点的连通度为6 。在边界新创建的点的连通度为4 。类似，基于四边域网格，顶 点插入和割角方案在内部创建的新点的连通度为4 ，在边界为3 。因此，经过几 次细分，网格中的大多数顶点的连通度呈现这种情况：对三角网格来说，内部为 6 ，边界为4 。对于四边域网格来说，内部为4 ，边界为3 。这样的顶点称为规则 点，否则为异常点。 奇点( o d d ) 与偶点( e v e n ) ：对任何细分层，我们称在该层创建的新点为奇 点。从前一层继承的顶点称为偶点。 面点与边点：三角域鼹格或四边域两格的每一条边一分为二，插入一个新点， 这样的点我们称为边点；四边域网格的每一个面额外插入一个顶点，这样的点我 们称为面点。 1 2 ，4 细分规贝l j 的标准 最终曲面的形状及光滑性决定了细分规则的定义，细分规则应该至少满足阱 下条件： ( 1 ) 有效性：新点位置的计算应该涉及较少的浮点运算。 ( 2 ) 局部支撑性( c o m p a c ts u p p o r t ) ：一个点对最终曲面形状的影响区域应该 有限。 ( 3 ) 局部定义：模板的分量仅仅依赖于较小邻域的结构。 第1 章高散曲面造型方法 ( 4 ) 仿射不变性：如果初始点集发生变化，例如，比例变换、旋转变换等， 最终曲面应该经历同样的变换。即要求计算顶点时各顶点所占的分量之和为1 。 简单：涉及较少的规则。 连续：最终曲面应该满足一定的连续条件。 1 2 5 经典的细分方法 ( 1 ) l o o p 方案 l o o p 方案是一个基于三角网格的简单逼近的顶点插入方案，由c h a r l e sl o o p 1、v 1 于1 9 8 7 年提出。l o o p 方案基于三次箱样条，对规则网格可以产生c 2 连续的曲 面，而在异常点可以达到c 1 连续，包括边界的情况。该方法适用于任意拓扑的 三角网格。其细分规则如图1 3 所示。 j ( a ) 新插入点 ( b ) 旧规则点重新计算( c ) 异常点的处理 吲1 - 3l o o p 方案细分规则 其中p 。i 1 ( i 5 一唁3 + l e o s 争2 ) 或者当。，3 时，卢一石3 ，当。3 时，卢一丽3 。 即对图1 - - 3 ( a ) p 川。i 3 p “) + i 3 p ( v z ) + ；p “) + i l p 以) ( 1 1 1 对图1 - - 3 ( b ) p 1 。话1 0 p + 去p ( v ，) + 击p 协z ) + 去p 协，) + 去p 小) + 谅1p ( 匕) + 去p _ 。( 1 2 1 对图1 3 ( c ) p 一扣) ( 1 一即扫+ 彦( v ，) + + 彦( y t ) ( 1 3 ) 其中k 为该点的连通度。 离散细分骨 i 占动画的研究与应用 ( 2 ) 蝶形( b u t t e r f l y ) 方案 a 蝶形细分算法 b u t t e r f l y 方案最先是由d y n ，g r e g o r y 和l e v i n 于1 9 7 8 年提出【2 3 】，b u t t e r f l y 细分方案是一种基于张量控制的曲面插值细分，其思想基于局部四点插值细分。 最简单的一元细分曲面是控制点形成的规则四边域网格，在这种情况下可以定义 一元方案的张量积形式。给定控制顶点集镟，四点插值细分的张量积形式可 表示为 p 。k + 。l ，- p i ， 弧k + l 。，t 呸1 + 呐喊，+ m k ，抄w o , l 。，+ p ) p 噎+ 州z ，+ 卜吣如+ p ) ( 1 4 ) b u t t e r f l y 方案是一种基于三角网格的插值细分方案，循环分割控制网格的每 砖 图1 4b u t t e r f l y 细分 个三角面为四个子三角面，四个子面插值旧的控制点。这样，细分网格保留 租糙网格的顶点，新顶点对应于旧三角形的边加入。插入新顶点的规则是八点规 则，由于其形状象蝴蝶，如图1 4 所示，所以称之为蝴蝶方案。 对应于边( p ，p ：) 插入薪的顶点q “，其对称形式的规则为 q “1 一u ( p 卜p d + y 耐+ p ：) 一心：+ p ：+ p ；+ p ：) ns 、 ， 对三角形的每一条边插入一个顶点，并进行拓扑连接，形成新的细分三角形。 整个过程循环进行，每个旧三角形就由四个新三角形替代。 第1 章离散曲面造型方法 考虑到极限曲面的连续性，对于规则网格，c o 连续的曲面必须满足 2 u + 2 v 一4 w 一1 ( 1 6 ) 如果是c ，连续，我们采取u2 主+ “( ”) ，6 ( o ) = o ，选择h 。0 h0 ，有v ：2 w ，则 如果是c 连续，我们采取 2 、” ，选择。，有v 。 ，则 方案为 口“1 。抄+ p ：) + 2 吣；+ p ：) 一w ( p ；+ p ：+ p ；+ p d ( 1 7 ) 其中w 是一个张量参数，它控制极限曲面与控制网格的逼近程度。当w 等于 0 ，则算法就是进行简单的端点线性插值，表面就不光滑。 1 一般情况下我们取 1 6 ，这对规则网格可以产生c 1 光滑。 当用控制点描述三维网格的函数值时该方案很明显是四点方案的扩充。如果 这些值沿某一分量是常数，则所有新插入点沿该方向的分量也为常数，该方案就 简化为沿两个方向的一元方案，也就是四点方案。 ( b ) 改进的蝶形细分算法 然而，尽管初始b u t t e r f l y 方案是定义在任意三角网格，极限曲面在连通度等 于3 或大于7 的异常点不是c 1 连续。1 9 9 6 年z o r i n 等人后来对蝶形算法进行了 进一步的修改，其主要目的就是开发对异常点的使用规则，使表面的每一处都是 c 1 的连续。 由于是基于三角形网格的插值细分算法，因而对网格细分操作时，我们只需 在三角形的每条边上插入新点，其新点的生产规则如下： 一当边的两个端点的连通度都为6 时，插入点的值由周围的1 0 个点来决 定，模板如图1 - - 4 ( a ) 所示，其中a 、b 、c 、d 分别为各点的相应权值： 口- - w , b - i 1 + 2 嵋c 一面1 一w d _ ”；w 的取值范围在。，1 之间，一般我们取 w = o 。 二当边的一个端点的连通度为6 ( 规则点) ，而另一个端点的连通度不为6 时( 异常点) 时，插入点的值只由异常点及异常点的直接邻域点来决定，而与规 离散细分骨骼动画的研究与应用 则点无关。模板如图3 - - 4 ( b ) 所示其中，k 为异常点的连通度，q = o 7 5 ，当k = 3 时，5 。- 5 1 2 ，s i ，2 一1 1 1 2 ；当k ：4 时，s 。3 8 ，5 2 一1 8 ，$ l 3 - 0 ；当k ：5 。生竺丝：竺兰! 时，领域点的权值为5 ，。r 一，i = o ，k - 1 嚼c b c。 ： cb ( a ) 规则点计算( b ) 异常点的计算 图1 5 修改的b u t t e r f l y 方案细分规则 三当边的两个端点都为异常点时，那么对每一个端点都用第2 种情况的方 法计算一次新插入点的值，然后再平均这两次的计算结果。即为新点的最终取值。 由于这种情况只出现在细分的初始层，曲面的最终光滑程度不受这种情况影响。 然而，如果这种情况处理的好，最终形状的光顺会更好。 ( 3 ) c a t m u l l - c l a r k 方案( c c 细分) 1 4 1 c a t m u l l - - c l a r k 方案是基于张量积的双三次样条。该方案产生的蓝面对任意 拓扑的规则网格具有c 2 连续，异常点处具有c 1 连续。 下面我们根据双三次样条函数来推得c a t m u l l - - c l a r k 方案的细分规则，也从 中可以得知张量积形式下细分奴则的由来。 1 三次样条曲面的矩阵 双三次b 样条曲面p ( u ，v ) 用矩阵表示为 其中 p 曩 p o ，叻b h 1 , 1 2 “3 呐i p m 7 吖三 6 1 v v 2 v 3 o 0 o l 1 3 3 o 4 0 缶3 ，0 3 o 肋彤勋m加m 跏础勖甩勋勘肋肺跏琊 第1 章离散曲面造型方法 对这样一个曲面片的控制网格如图1 - 6 所示。 p 叫 l t , o p 2 m 图i - 6 双三次b 样条曲面控制网格 2 细分双三次曲面片 一个双三次b 样条曲面片可以细分为四个子曲面片，它可以从2 5 个唯一的 图1 7 细分后产生的2 5 个控制点 0 “y ! 图1 - 8 参数 2 对应的子控制网格 子控制点产生，图1 7 说明了细分为4 个子曲面片后产生的2 5 个点。我们 0 s 三 对其中的一个子片来分析细分方案，例如对参数( 2 ) 对应的子曲面片 进行分析，如图1 - - 8 所示。其它根据对称关系可得。需要说明的是9 个内部控 离散细分骨骼动画的研究与应用 制点被细分后的4 个子曲面片共用。 “。_ 兰p _ 兰 用变量u ，v 参数化曲面生成子曲面片，其中 2 ， 2 ，代入方程得 蹦) i p ( i u ，【1 ； 。i u u 2 “， v i s p s r m 7 其中p - s p s 7 s i f 一1 1 o o 0 则控制点p p 。- 1 8 1 - 一 8 1 v v 2 p 3 3 m p m 7 。& “z 1 2 4 4 16 0 4 0l 矗， p u b 。 气 o 0 10 4 0 6l 异。 置，2 b j 只z 只。 气 气 气 1 8 ： i 9 睁 “，k m r 4 4 1 6 0 4 ol 1 v v 2 v 3 0 o 10 40 6l 1 8 ) ( 1 ，9 ) 根据每个点与初始控制网格的关系，可以把这些点可以分为三类：面点、边 点和顶点。如图3 8 所示，矗。，e o ：砭。和砭z 为面点，对( 1 9 ) 进行整理可 得， 矗。一塑号鱼堡 矗：一坠半 最。尘鼍鱼堕 乏：尘等粤生 - 1 4 第1 章高散曲面造型方法 即面点的坐标值是其所在面四个顶点的平均值。 r ，只，b ，b ，只，e ，和b ：为边点，由( 1 9 ) 可得其计算为 群，；堡! 墨! ! ! 竖! 立墨：! ! ! 墨：! ! 墨：! 1 6 。墅些兰氅箬出生虫 1 0 只，。墨：! ! 墨! ! 塑! ! ：墨：! ! ! 墨! ! ! 墨：1 1 0 只，墨：! 墨! ! ! ! 亟! 墨! ! ：曼! ! 墨! ! 一墨：! ! 墨：! ! ! 垡：! 二墨! 立墨：! 墨：! 爿，墨! 墨d ! 堡：! 墨! ! ! 墨：! ! 墨：! 一，墨：! ! 墨= 兰! ! 墨：! 墨：! ! ! 墨：! ：墨：! l o 即边点是由该边所在的两个四边形的顶点确定。 e j ，只1 3 ，曩- 和曩，为顶点，由( 1 ) 式可得其计算为 只，生二皇量生些：! ! 坠! ! 堕! 型! 生! 堡! ! 垒 础血：竺：止垒! ! 坠：! ! 堡：! 墨：立! 墨! ：! 生! 垒1 1 0 只，墨! ：堡! 墨! ：! 堡：! ! 堡! ! 刍! ：墨! ! ! 堡：! ：墨1 1 0 爿，曼堡! 墨! ! ! 坠! 堡：! ! 墨：尘! 生! 堡! ! ： 1 0 即面点是由该面所在的四个四边形的顶点确定。 可用图1 9 来表示其计算规则。 - 1 5 - 离散细分骨骆动画的研究与应用 则 n i 一 j 一 ， j jj 丽厂 丽 ，li 宴 三口二 l 6 ( a ) 面点计算规则( b ) 边点计算规则( c ) 顶点计算规 困1 - 9c a t m u l l c l a r k 方案细分规则 另外，还有四边插值细分l 白b b e l t 方案、压细分【2 4 】、组合细分【2 5 】等等。 本章小结； 相对于传统的计算机图形表示方法，细分算法是一种离散的几何模型构造方 法，它对给定的离散几何数据，递归地调用细分规则，从而逐步加密几何数据使 其收敛于一个极限的几何模型。由于曲面细分算法有良好的数值稳定性，运算效 率高和易于实现。在动画领域有着很好的应用前景。本文第4 章的细分骨骼动画 就是利用l o o p 方法实现表面网格细分的。 第2 章计算机动画技术概述 第2 章计算机动画技术概述 计算机动画是计算机图形学和艺术相结合的产物，它足伴随着计算机硬件和 图形算法高速发展起来的一门高新技术，它综合利用计算机科学、人工智能、艺 术、数学、物理学和其它相关学科的知识在计算机上生成绚丽多彩的连续的虚拟 真实画面，给人们提供了一个充分展示个人想象力和艺术才能的新天地。 在侏罗纪公园、失落的世界等很多优秀电影中，我们可以充分领略到 计算机动画的高超魅力。计算机动画不仅可应用于电影特技、商业广告、电视片 头、动画片、游艺场所，还可应用于计算机辅助教育、军事、飞行模拟，甚至于 法院的审理。已成为计算机应用的重要领域之一。 计算机动画技术已有三十年的历史了。它的发展大致经历了三个阶段。 第一阶段是早期阶段。从6 0 年代至7 0 年代初，特点是采用高级语言编程。 代表作品是b e l ll a b s 用f o r t r a n 制作的说明牛顿运动定律的动画片。 第二阶段从7 0 年代初至8 0 年代。此间出现了二维动画系统和用户友好交互 方式。m s g e n 二维动画系统是代表作品之一。 第三阶段从7 0 年代末至今，重点集中于三维动画系统的开发上。优秀作品 有s o f t i m a g e 公司的3 d s t u d i o 等。 简单地讲，计算机动画是指用绘制程序生成一系列的景物画面，其中当前帧 画面是对前一帧画面的部分修改。动画是运动中的艺术，正如动画大师j o h nh a l a s 所讲的，运动是动画的要素。计算机动画所生成的是一个虚拟的世界，画面中的 物体并不需要真正去建造，物体、虚拟摄像机的运动也不会受到什么限制，动画 师可以随心所欲地创造他的虚幻世界。 2 1 关键帧动画技术概述 、关键巾贞技术是计算机动画中最基本且运用最广泛的方法。关键帧的概念来源 于传统的卡通片制作。在早期由熟练的确画师设计卡通片中的送壤画面，也即所 谓的关键帧，然后由一般的动画师设计中间帧。在三维计算机动画中，中间帧的 生成由计算机来完成，插值代替了设计中间帧的动画师。 所有影响画面图象的参数都可成，鹾键犊的参数，如位置、旋转角、纹理的 离散细分骨骼动圆的研究与应用 参数等。而另外一种动画设置方法是样条驱动动画。在这种方法中，用户采用交 互方式指定物体运动的轨迹样条。几乎所有的动画软件如a l i a s 、s o f l i m a g e 、 w a v e f r o n t 、3 d s 等都提供这两种基本的动画设置方法。 无论是样条驱动动画还是关键帧插值方法，都会碰到这个问题：给定物体运 动的轨迹，求物体在某一帧画面中的位置。物体运动的轨迹一般由参数样条来表 示。如果直接将参数和帧频联系起来，对参数空间进行等间隔采样，有可能带来 运动的不均匀性。为了使物体沿一样条匀速运动，必须建立弧长与样条参数的一 一对应关系。 运动路径是用户画出的空间曲线，由关键点控制。而物体的运动快慢由标 出到达路径上某些点的时刻来决定。使用这种方法并不要求物体的运动是均匀 的，因而可以灵活的进行设计：但它并非基于物理规律，所以常常要反复调试才 能得到逼真的图象。 从原理上讲，关键帧插值问题可归结为参数插值问题，传统的插值方法都可 应用到关键帧方法中。但关键帧搔值又与纯数学的插值不同，它有其特殊性。一 个好的关键帧插值方法必须能够产生逼真的运动效果并能给用户提供方便有效 的控制手段。 一个特定的运动从空问轨迹来看可能是正确的，但从运动学或动画设计来看 可能是错误的或者不合适的。用户必须能够控制运动的运动学特性，即通过调整 插值函数来改变运动的速度和加速度。 为了很好地解决插值过程中的时间控制问题，可采用下面的方法。 ( 1 ) 双插值的方法来控制运动参数。其中之一为位置样条，它是位置对关键 帧函数；另一个为运动样条，它是关键帧对时间的函数。 ( 2 ) 三次插值样条，他们把关键帧处的切矢量分成入矢量和出矢量两部分， 并引入三个参数：张量t 、连续量e 和偏移量b 对样条进行控制。该方法已在许多 动画系统中得到了应用。 关键帧插值系统中要解决的另一个问题是物体朝向的插值问题。物体的朝向 一般可由e u l e r 角来表示因此朝向的插值问题可简单地转化为三个欧拉角的插 值闻题。但欧拉角表示又有它的局限性。因为旋转矩阵是不可交换的，基于欧拉 角的旋转一定要按某个特定的次序进行： 第2 章计算机动匾技术概述 等量的欧拉角变化不一定引起等量的旋转变化，从而导致旋转的不均匀；欧 拉角还有可能导致自由度的丧失，即所谓的“g i m b a ll o c k ”现象。 为了解决因采用欧拉角表示引起的缺陷，四元数表示法被引入到动画中四 元数可表示矢量和物体的旋转，并且没有冗余信息，它提供了一种比旋转矩阵更 为有效的方法。在计算机图形学和计算机动画领域中表示物体的旋转和朝向方 面，它显得尤为便利。 计算机插值有两种方法：线形插值和非线形插值，分别采用线形插值算法与 非线形插值算法。使用时视情况而定。帧技术也可视为“关键帧”技术的一种，它 可描述为：在关键帧上选取的不是物体自身而是物体的框架。框架是由一些点和 线组成的简单图形，它描述了动作的形式。利用帧技术，可以创作出一些仅由帧 组成的关键帧，再由计算机自动绘制出较理想的中间画面。四边形法是定义帧的 常用方法，当然也可以采用三角形法。 2 2 其他高级动画技术 2 2 1 物体变