矢量图形动画的一类中间画生成算法

矢量图形动画的一类中间画生成算法 16 Vol . 2 No 第 2 卷 第 6 期() 广州大学学报 自然科学版 2003 年 12 月 Dec . 2003 ()Journal of Guangzhou UniversityNatural Science Edition () 文章编号 :1671- 4229 200306- 0537- 04 矢量图形动画的一类中间画生成算法 罗晓奔 , 孙开天 , 张红霞 () 广州大学 网络中心 ,广东 广州 510405 摘 要 : 计算机图形学中中间画的产生是计算机动画制作的重要技术之一. 本文提出了一种在两幅以矢量表示 的关键帧之间生成中间画的算法 ,给出了算法中使用的一类插补函数并讨论了其性质 ,描述了算法的实现过程. 本算法的特点是简单 、高效 、稳定和易于实现. 关键词 : 计算机图形学 ; 计算机动画 ; 中间画 ; 算法 中图分类号 : TP 391. 41文献标识码 : A 计算机图形学中运动物体的表现是计算机动,称为矢量图形.及有关参数所描述的计算机图形 画的关键技术. 计算机动画研究物体计算机图形或 在计算机图形中 ,矢量表示法可以顶点表示平 图像在一定条件的控制下 ,从一种形态变换到另一 面和空间的点、线 、面. 还可以表示通过基本型值点 形态的技术. 拟合得到的曲线和曲面. 不失一般性 ,我们将这些 ( ) 控制图形形状的关键坐标点统称为“顶点”计算机动画与电影 及电影动画在表现“动” . 的手段上是一样的 ,即无论物体及其运动形式多么 以下为矢量表示的空间图形的几个示例 : ( ) 复杂 ,物体的运动都是通过一幅幅静止的图片表现 3 点 : x , y , z; 出来 ,再借助人的“视觉暂留”生理及心理特点 ,在 3 直线 : < P, P> , P、P为直线的端点 ;1 2 1 2 人的大脑中形成“连续的”图像. ) ( 3 折线 : P, P, , P, n ?2 , 其中 P为1 2 n i 因此 ,计算机动画的生成是一个离散过程. 如 n ; , 顶点 , i = 1 ,2 , ( ) 果我们将变化开始和结束时的图形 或图像记为( ) ( ) 3 多边形 或面: P, P, , P, n ?3 ,其1 2 n G和 G,则计算机动画技术是寻找从 G到 G中 b e b e 中n . , P为顶点 , i = 1 ,2 ,i G, G, G, , G, 所有中间插图的集合{ G=0 1 2 n - 1 b G= G}的过程. n e 2 计算机动画生成的关键帧技术在计算机动画中表现运动物体的中间状态的 技术非常多 ,如关键帧技术 、过程动画技术 、位移动 关键帧技术是计算机动画生成的一种重要技画技术等. 在这些计算机动画技术中 ,运动物体的 ( ) 术. 所谓“关键帧”key-frame是指对运动物体的中 中间状态是通过不同的算法生成出来的. 因此 ,各 间状态起控制作用的几幅画面. 通过对这些关键帧 种生成算法的研究是计算机动画技术的重要研究 ( ) ( 施加一定的运算 或称为算法,即可求出 或叫做 课题之一. ) (生成一幅幅各关键帧之间的称之为“中间画”in- 本文给出了一种基于关键帧技术的用于矢量 ) between的画面 ,这种动画处理方法称为“关键帧技 表示的图形的动画生成算法. 术”. 关键帧技术在传统动画和计算机动画中都得 到了广泛的应用. 一般地 ,我们可将计算机动画生成的关键帧技 ( 术描述如下 :给出运动物体在运动开始状态 时间 1 计算机图形的矢量表示 ( ) t = 0的关键帧 G和结束状态 不失一般性 ,可设 b ( ) 以平面二维或空间三维的“点”坐标的集合 收稿日期 : 2003 - 07 - 15 ; 修回日期 : 2003 - 09 - 30 () 作者简介 : 罗晓奔1957 - ,男 ,副教授 , 主要从事计算机网络和应用软件研究. ( )) t = 1的关键帧 G,则在任一时刻 t 的中间画 G t G变换到 G的速度 、中间画与 G和 G相似的程e b e b e ( ) ( )是开始关键帧 G、结束关键帧 G以及参数 t 的函 度. 如果在选取和设计函数 f t 时 ,使之满足 5 b e ( ) 数 ,即中间画 G t可表示如下 : 式 ,就可使中间画不会出现大的变形. ( )总而言之 ,从算法的实用角度考虑 ,要求 f t ( ) ( ) ()G t = f G, G, t , 1 0 ? t?1b e 尽量简单 ,易于计算机处理 ;在变换的前期阶段 ,生 且满足 : ( ) 成的中间画 G t应该更“像”开始关键帧 G,在变 b () ( ) ()G 0= f G, G,0= 2 G b e b ( ) 换的后期阶段 ,生成中间画 G t 应该更“像”终结 () ( ) ()G 1= f G, G,1= G3 b e e关键帧 G. 并且在变换中 ,插补函数是稳定的 ,不 e 其中 f 为中间画的插补函数 ,即生成中间画的 会使中间画发生既不像 G又不像 G的变异.b e 计算方法.根据以上的分析 , 可以设计出许多满足性质 () 5的中间画插补函数. 下面给出其中几个简单而 3 中间画插补函数实用的插补函数示例. () 1直线插补变换函数 插补函数是实现中间画的生成的关键 ,它应该 ( ) () 6 f t = t , 0 ? t ?1( 形状简洁 、易于理解、运算简单 、稳定可控 计算不 直线插补函数生成的中间画将从开始关键帧) 会发生异常 ,生成的中间画不会出现大的变形. 为 G,线性而稳定地变换到终结关键帧 G. 在变化过 b e ( ) 此我们设计一类中间画插补函数 f t : (() ) 程中 ,中间画将均匀地改变特征 见图 1 a. 3 3 ( ) (( ) ) ( ) G t= 1 - f tG + f tG = b e () 2抛物线插补变换函数3 ( ) ( ) ()G+ f tG- G, 4 0 ?t ?1b e b ( ) 其中 f t 满足以下性质 : ( ) () 7 f t= t , 0 ? t ?1 ()f 0 = 0 抛物线插补函数所生成的中间画将从开始关 键帧 G,稳定地变换到终结关键帧 G. 但是在变 b e ()()5 f 1 = 1 化过程中 ,中间画将较快地呈现出终结关键帧 Ge ( ) t < 1 0 < 0 ?f t?1 ,(( ) ) 的特征 见图 1 b. () 将符合条件 5的插值函数作用于中间画生成() 2反抛物线插补变换函数() ( )( ) G 0 公式 4,则显然有= G和 G 1= G,满足b e 2 () () 2和 3式. ()( ) 8 f t = t, 0 ? t ?1 在这类插补函数中 , t 为控制插补生成中间画 反抛物线插补函数所生成的中间画将从开始 G, 稳定地变换到终结关键帧 G. 但是在 关键帧 b e 的进度的因子 ,改变 t 的步长 ,可增加或减少中间 变化过程中 , 中间画将较长时间地保留开始关键 ( ) 画的幅数. f t 为控制中间画形状变化程度的函 (() ) 帧 G的特征 见图 1 c. b 数 ,不同的函数 , 可产生不同的变化效果 , 影响从 图 1 几种插补函数的图形 Fig. 1 Graph of several interpolation functions 计算机上实现并具有一般性 , 还必须解决两个问 ( ) ( ) 题 :关键帧对 G, G的顶点 或型值点之间的对b e 4 中间画算法的几个预处理问题 应关系以及二者的顶点数目不同的处理. 4. 1 两关键帧之间的顶点对应关系() ( ) ( ( ) ( )中间画公式 4、 和 5和插补函数 如 67 两关键帧之间按照它们顶点的自然顺序来建 () ) 和8式给出了基于矢量图形表示的中间画生成 的顶点数为 n ,且帧的良好相似性. ()9 G= { P, P, P, , P} b ,1 2 3 m ()G= { Q, Q, Q, , Q} 10 5 中间画生成算法e 1 2 3 n 则对应关系为 : PΖ Q, PΖ Q, PΖ Q, 解决了上述问题之后 ,可以描述基于矢量表示1 1 2 2 3 3 ()11 的图形的关键帧技术的中间画生成算法步骤. 因此 ,在应用本算法时 ,应保证已经建立这种 () 给定关键帧 G= { P, P, P,, P} 和1b 1 2 3 m 对应关系. G= { Q, Q, Q, , Q} , 中间画步数 T , 以及中 e 1 2 3 n 4. 2 两关键帧顶点数目不同的处理 ( ) 间画插补变换函数 f t,要求生成 t = 0 ,1ΠT ,2ΠT , 当两关键帧顶点数目不同时 ,可进行“补点”处 ( () ) 理 ,使两关键帧顶点数目在算法开始时变成相同. T - 1ΠT ,1 时的中间画 含关键帧. () 下面给出几种易于实现的补点方法. 为了讨论的方 2如果 m ?n ,记 H = max{ m , n} ,则按照上 便 ,不失一般性 ,假设两关键帧顶点数有 m < n ,即 节介绍的某种方法对 G或者 G进行补点 ,得到顶 b e ′ ′ ′ ′ ′ 关键帧 G的顶点数比关键帧 G的顶点数少. b e , P } 点数相同的两幅关键帧 G = { P , P , P ,1 2 3 b H ′ ′ ′ ′ ′ () 1始端重复补点法 : 在顶点数较少的关键帧 Q} . , 和 G= { Q, Q, Q,H e 1 2 3 ( G,的始端点 P之前补点 ,将始端点 P重复 n -b 1 1 () ( ) 3当 t = 0 时 , 直接输出 绘制开始关键帧′ ) m 次 ,使两关键帧顶点数相同. 这时 G,变为 G, :b b G. b ′ ′ ′ ′ G, = { P= P, P= P, , P= P, b 1 1 2 1 n - m 1 () 4对于 i = 1 ,2 ,, T - 1 ,重复步骤 ?, ?:′ ′ i ()12 P= P, , P= P} ( ) n - m + 1 2 n m ?求出中间画 G= G iΠT的各顶点 V i k i ′′ ′ 3 () 2: 在顶点数较少的关键帧 末端重复补点法 ( ) ( ) V= P+ f iΠTQ- P, k k k k ( G,的末端点 P之后补点 ,将末端点 P重复 nb m m ()16 k = 1 ,2 ,3 , , H ) - m, 使两关键帧顶点数相同. 这时 次 G, 变为b ) ?清除上次绘制的中间画 G;i - 1 ′ i i i G, : b ) ( ) ?G= { V, V, V, , 输出 绘制中间画 i 1 2 3 ′ ′ ′ ′ iG, = { P= P, P= P, , P= P, b 1 1 2 2 m m V,} . H ′ ′ () ()13 5当 t = 1 时 ,清除上次绘制的中间画 G, P= P, , P= P} H - 1 m + 1 m n m () 3中间重复补点法 : 在顶点数较少的关键帧 直接绘制终结关键帧 G.e ( ) G,的中间的某 n - m 个端点上补点 , 将这些端b () 6算法结束. 点各重复 1 次 ,使两关键帧顶点数相同. 如果我们 实例 :现给出该算法的一个应用实例. 给定两 均匀地抽取补点端点 P,则下标 s 可由下式确定 : s 幅关键帧 G= { < 0 ,0 > , < 2 ,2 > , < 3 ,1 > } 和 G b e m = { < 0 ,1 > , < 1 ,0 > , < 2 ,3 > , < 4 ,2 > , < 2 ,1 > } , ()S = 「 i , 14 1i = 1 ,2 , n - m n - m ( ) 中间画插补步数 T = 5 ,使用线性插补函数f t = t () 4: 在顶点数较少的关键帧 线段中点补点法 () 0 ?t ?1,采用“末端重复补点法”. 按照上述算法 ( ) G的中间的某 n - m个线段上补点 ,将这些线段 b () 可求出各中间画 含关键帧的矢量表示如下 : 的中点作为补充点 ,使两关键帧顶点数相同. 如果 G= G= { < 0 ,0 > , < 2 ,2 > , < 3 ,1 > } ; 0 b () 均匀地抽取补点线段 PP,则下标 s 可由 14式s s + 1 G= { < 0 ,0 . 2 > , < 1. 8 ,1 . 6 > , < 2. 8 ,1 . 4 > , 1 ′ 确定 ,中点 P可由下式确定 :sm < 3. 2 ,1. 2 > , < 2 . 8 ,1 > } ; P+ P s s + 1G= { < 0 ,0 . 4 > , < 1. 6 ,1 . 2 > , < 2. 6 ,1 . 8 > , 2 , S < m ′ 2 ()15 = Psm < 3. 4 ,1. 4 > , < 2 . 6 ,1 > } ; P, S = m s G= { < 0 ,0 . 6 > , < 1. 4 ,0 . 8 > , < 2. 4 ,2 . 2 > , 3 始端重复补点法”和 上述几种补点方法中 “, < 3. 6 ,1. 6 > , < 2 . 4 ,1 > } ; “末端重复补点法”具有简单、易于实现的特点 ,但G= { < 0 ,0 . 8 > , < 1. 2 ,0 . 4 > , < 2. 2 ,2 . 6 > , 4 是中间画的特征将会被“拉”靠向关键帧的始端或 < 3. 8 ,1. 8 > , < 2 . 2 ,1 > } ; 末端.“中点重复补点法”和“线段中点补点法”稍微 G= G= { < 0 ,1 > , < 1 ,0 > , < 2 ,3 > , < 4 ,2 > , 5 e 复杂一点 ,但是可保持所产生的中间画与两幅关键 < 2 ,1 > } . 由此算法所生成的中间画如图 2 所示. 图 2 中间画生成示例 Fig. 2 A sample of the in- between animation 的几个插补函数 ,易于理解 ,易于计算 ,能满足大多 数应用场合的中间画生成要求. 根据这些思想 ,还 6 小结可以设计出各种各样的具有不同特色的插补函数. 本文描述的中间画生成算法 ,可以应用于任何,若放开对插补函数的某些限定 ,如容许插补当然 ( ) 函数| f t| > 0 ,则生成的中间画可能取得某种意 以坐标点即顶点集表示的关键帧图形之间的中间 想不到的特殊变形效果. 算法中对两关键帧顶点不 画的生成. 该算法适用的图形对象较广 ,如二维或 同时所进行的预处理 , 可使中间画生成的程序简 三维空间的点 、直线、折线 、多边形 、平面 、拟合曲 单 ,适应性强. 显然 ,该算法的思想也可以应用于以 线、拟合曲面 、样条曲线 、样条曲面等 ,都是用顶点 () 其它形式 如坐标方程或参数方程表示的关键帧 集表示的. 为了控制中间画生成的过程 ,本文使用 图形之间的中间画生成. 了插补函数 , 并根据人们日常欣赏动画的常规心 理 ,对插补函数的性质作了合理的限定. 文中设计 参考文献 : () 1 黄有度 ,朱功勤. 一种参数多项式曲面片的逐点生成算法J . 中国图像图形学报 , 2002 7:13 - 16. HUANG You- du , ZHU Gong- qin. A point- generating algorithm of the curve slice based on the parameter polynomial function J . () China Image and Graphics J ournal , 2002 7:13 - 16. () 杨怀平 ,胡事民 ,孙家广. 一种实现水波动画的新算法J . 计算机学报 ,2002 6:22 - 25. 2 YANG Huai- ping , HU Shi- min , SUN Jia- guang. A new animation generating algorithm of the water wave J . Computer J ournal , () 2002 6:22 - 25. () 赵 星 ,熊范纶 ,Philippe de Reffye . 一种新的植物枝条弯曲生成算法J . 中国科学技术大学学报 ,2001 6:17 - 21. 3 ZHAO Xing , XIONG Fan- lun , Philippe de Reffye . A new generating algorithm of the plant twigsJ . J ournal of China Science and () Technology University , 2001 6:17 - 21. 齐东旭. 计算机动画原理与应用M . 北京 :科学出版社 ,1998.4 QI Dong- xu. The principal and application of computer animationM . Beijing : The Science Press , 1998. An in- bet ween generating algorithm of the vector gra phic animation LUO Xiao- ben , SUN Kai- tian , ZHANG Hong- xia ( )The Network Center of Guangzhou University , Guangzhou 510405 ,China Abstract : The in- between generating is one of the important technologies in the computer graphic animation. In this paper , an algorithm which generates the in- between between two key-frames presented by vector graph is proposed. Several interpolation functions and their features are discussed ,and , at last , the algorithm procedure is described. Key words : computer graphics ; computer animation ; in- between ; algorithm