（计算机软件与理论专业论文）实时生成烟的卡通动画关键技术的研究与实现.pdf

摘要 计算机动画是计算机图形学中一个重要的领域，而用计算机生成三维的卡通动画又 是计算机动画中一个举足轻重的研究方向。本文在回顾了烟的动态模拟、烟的动态控制 以及烟的非真实感绘制等相关技术的基础上，提出了一个能实时生成烟的卡通动画算 法。 卡通动画具有运动抽象和视觉效果抽象的特征。基于这两个特征，本文提出的算法 相应地分为烟的动态模拟和卡通绘制两部分。 在动态模拟阶段，本文用粒子系统作基于物理规律的模拟。本文采用平滑粒子动力 学( s p h ) 模型将烟建模为1 0 2 1 0 3 数量级个平滑粒子，并根据粒子密度推导出粒子受 到的扩散力。同时，其他物理参数如速度、空气阻力、风力、外界的碰撞力等都直接定 义在烟的粒子上。 在卡通绘制阶段，我们将粒子看成椭球体，并预绘制出椭球体的法向矢量图和深度 图。对法向矢量图进行采样得到像素的法向矢量后，分别与普通光源和位于视点处的辅 助光源发射的光线进行点击，将得到的亮度值作二值量化，于是烟被绘制成含有二值光 照和轮廓线的卡通风格；而对深度图进行采样，并以此调整该像素的深度值消除公告牌 算法带来闪烁现象。整个绘制阶段都在g p u 里完成。 尽管动态模拟和非真实感绘制的算法都很简单、直观，但能很好地满足卡通动画的 抽象性特征。实验结果表明，应用本文提出的算法，仅仅需要1 0 0 0 左右的粒子就能实时 地生成相当好的烟的卡通动画。 关键词：烟，粒子系统，基于物理的模拟，卡通动画，非真实感绘制 a b s t r a c t c o m p u t e ra n i m a t i o ni sa ni m p o r t a n tr e s e a r c hf i e l di nc o m p u t e rg r a p h i c s ，a n d3 d c a r t o o na n i m a t i o ng e n e r a t e db yc o m p u t e r si sah o tt o p i ci nc o m p u t e ra n i m a t i o n i n t h i sp a p e r ，w ep r e s e n tap r a c t i c a lf r a m e w o r kt og e n e r a t ec a r t o o ns t y l ea n i m a t i o n so f s m o k ea tr e a l t i i v i l ef r a m er a t eb a s e do nt h er e l a t e dp r e v i o u sw o r k ti n c l u d i n gs i m u l a t i o n o fs m o k e ，d y n a m i cc o n t r o lo fs m o k ea n dn o n - p h o t o r e a l i s t i cr e n d e r i n go fs m o k e c a r t o o na n i m a t i o nh a st w oc h a r a c t e r i s f i ca b s t r a c t i o n s ：m o t i o na b s t r a c t i o na n dv i - s u a la b s t r a c t i o n b a s e do nt h e s et w of e a t u r e s , o u rf r a m e w o r kc o n s i s t so fas m o k es i m u - l a t o ra n dac a r t o o nr e n d e r e ra c c o r d i n g l y i nt h es i m u l a t i o ns t a g e , w ee m p l o ys m o o t h e dp a r t i c l eh y d r o d y n a m i c s ( s p h ) t o m o d e ls m o k ea sa b o u t1 0 2 1 0 3s m o o t h e dp a r t i d e s ，a n dd e f i n et h er e p u l s i v ef o r c eo n t h e m m e a n w h i l e ，o t h e rp h y s i c a lp a r a m e t e r ss u c ha sv e l o c i t y , a i rf r i c t i o n ，w i n da n d c o l l i s i o nf o r c ea r ea l ld e f i n e do nt h ep a r t i c l e sd i r e c t l y i nt h er e n d e r i n gs t a g e ，w ef i r s tp r e r e n d e re a c h p a r t i c l ea sa ne l l i p s o i dw i t h an o r m a l m a pa n d ad e p t hm a p w es a m p l et h en o r m a lm a pt og e tt h en o r m a lv e c t o ro fap i x e l ， a n dt h e nc a l o f l a t et h ed o tp r o d u c tw i t ht h eo r d i n a r yl i g h ts o u r c ea n da na u x i l i a r yl i g h t s o u r c ea tt h ev i e w i n gp o i n t f i n a l l y , t h ed e p t hm a pi ss a m p l e dt og e tt h ed e p t hv a l u e ， w h i c hi su s e dt om o d i f yt h ed e p t ho fe a c hp i x e lo nt h eb i l l b o a r dt oe l i m i n a t et h ef l i c k e r p r o b l e m t h er e n d e r i n gp r o c e s s i se x e c u t e do nt h eg p u e n t i r e l y a l t h o u g ht h ea l g o r i t h mo fs i m u l a t i o na n dr e n d e r i n gi ss i m p l ea n di n t u i t i v e ，i ts a t - i s f i e st h ef e a t u r e so fc a r t o o na n i m a t i o nq u i t ew e l l i nt h em o s tm o d e r a t es c a l es ce = n e , a n i m p r e s s i v ec a r t o o na n i m a t i o ni sg e n e r a t e dw i t ha b o u t at h o u s a n dp a r t i c l e sa tr e a l - t i m e f r a m er a t e k e yw o r d s ：s m o k e ，p a r t i c l es y s t e m , p h y s i c s - b a s e ds i m u l a t i o n , c a r t o o na n i m a - t i o n ，n o n - p h o t o r e a l i s t i cr e n d e r i n g i i i 第1 章绪论 1 1 论文研究的背景 1 1 1 蓬勃发展的计算机动画产业 1 计算机动画产业在全球经济中的地位 近年来，随着卡通动画片、计算机游戏以及电影特效等领域的飞速发展，计算机动 画产业发展一日千里，已经在全球经济中扮演着举足轻重的角色。据统计，2 0 0 4 年， 全球数字动画产业的产值已达2 2 2 8 亿美元，与动画产业相关的周边衍生产品产值则 在5 0 0 0 亿美元以上。世界动画游戏业产值最大的3 个国家分别为美国、日本、韩国。美 国在上世纪9 0 年代中期，动画游戏产品及其衍生产品出口就超过传统工业，成为重要出 口产品；游戏产业规模连续4 年超过好莱坞电影业，发展速度超过电影业和唱片业，成 为美国目前最大的娱乐产业。日本是世界第二大动画游戏生产国，其动画游戏产品出口 额超过钢铁产业，日本游戏产业每年创造产值2 万亿日元，其生产的各类游戏主机在全 世界总销量达到2 1 4 亿台。韩国是第三大开发经营动画游戏国家。1 9 9 9 - 2 0 0 2 年，韩国文 化产业年均增长率为2 1 1 ，高于6 1 的经济增长率；2 0 0 2 年，韩国企业收益中游戏产 业占3 4 3 ，达到3 4 兆韩元，2 0 0 3 年达到3 9 4 兆韩元：韩国动漫游产业超过汽车工业， 成为韩国第三大支柱产业。从全球及主要国家来看，动画产业已经成为一个庞大的产 业。 2 计算机动画技术促进了卡通动画片的飞速发展 传统的卡通动画片的制作是以纯手工绘制大量二维图片的方式完成，需要耗费大量 的人力物力财力，而且可重复使用率很低，因此其制作成本相当高。自1 9 9 5 年d i s n e y 公 司肃l p i x a r 公司共同出品玩具总动员( 图1 1 ( a ) ) 以来，应用计算机动画技术制作 卡通动画片得到了极大发展。玩具总动员是历史上第一部全长度由电脑技术制作 的3 d 动画长片，1 9 9 5 年在美国一上映就引起了巨大轰动，其制作公司p i x a r 公司也凭借 这部电影而迅速崛起。之后，海底总动员等优秀卡通动画片见证了计算机动画技术 的飞速发展。 3 计算机动画技术促进了电影特效的飞速发展 计算机动画技术的不断进步，极大地促进了电视、电影行业的迅速成长。计算机动 画技术使以前很难甚至根本无法实现的视觉效果成为可能。没有现代化的计算机动画技 术，就不可能有指环王中形象逼真的怪兽和城堡，也不可能有特洛伊：木马屠 城中规模宏大的船队，也很难实现哈里波特中魔幻般的画面效果。而最近上映 】 2 第1 章绪论 囤1 1 ：应用计算机动画技术制作的电影。( a ) ：玩具总动员的电影海报；( b ) 垒w 的电影海报+ 的电影金刚( 图1 , 1 ( b ) ) 中的大猩猩以及大量的恐龙怪蛰，也是计算机动蕊技术 的又次杰作。 4 。计算机幼画产业在中国的发展 避年来，我国包括计算机动画产业在肉的数字娱乐产业发展迅猛。据统计，国 产动潮片产量直线上舞，b k 2 0 0 0 9 的1 3 0 0 0 多分镑增长至n 2 0 。2 年的1 7 3 0 0 分钟，2 0 0 3 年增 至2 9 0 0 0 分钟，我国动漫及相关行业已经发展为一个年产值达5 0 0 亿元的巨大行业。目 前，我国动漫产业发展相对较快的是台湾地区； | 浙江、湖南、北京、上海、广东等省 市。阍时，地方政府西看到动莉及相关行业的发展潜力，国家缀韵画基地相继建立。 我国政府有关部f i n 太了对动画及相关产业发展的扶植力度。国家广电总局制定了 关于发展我困影视动画产业的若干意见，搬影视动灏产业发展作为新的经济增长点 纳入发展规划，省级魄视台、密会城市电视台、计划单刿市电视台，都鬟积极开办动砸 专栏、开辟动画时段，扩大葫溺片播出数量；柱每个播璐动殛片的频道中，国产动画片 与引进动画片每季度播出比例不低于6 ：4 。2 0 0 4 年1 2 月，国家广电总局批准设立9 个动画 产盈簇瑰莉4 个教学磷究基遗；2 0 0 5 年5 ) 1 ，国家广电慧弱叉魏猿设立6 个蓬家动灏产鲎 浙江大学硕士学位论文3 基地。 但对比国际动画产业的发展水平，我国的动画及相关产业只是刚刚起步。国内数字 娱乐业自主研发和原创能力较低，基本以引进、加工、代理运营为主。国内动画市场处 于深度饥渴状态，市场供给远远满足不了需求。到今年年底，全国有4 7 个省市少儿频道 和三个卡通卫视频道开播，动画节目的需求量一年将达到1 0 0 万分钟，而我国2 0 0 3 年全 年国产动画片的产量仅2 9 万分钟，缺口巨大，且大多数企业“一头在外”，以加工日、 韩等国动画片为主。在电影特技方面，国内很多大片的后期制作都是请国外公司制作完 成的。 巨大的市场和薄弱的原创力量导致中国动漫市场8 0 以上的盈利流向了日本、美 国。中国已成为动漫产品的最大输入国。据统计，仅史努比、米老鼠、k i t t y 猫、皮卡丘 和机器猫，每年就从中国卡通市场“掠走”6 亿元。因此，发展中国的计算机动画及其 相关产业任重而道远。 1 1 2 计算机动画领域研究的现状 最近这几年，计算机动画是计算机图形学中非常热门的领域，引起了大量计算机研 究人员的重视，同时也取得了一系列重大的突破。以图形学的顶级会议s i g 铲a p h 为例， 每年计算机动画方面的论文都在s i g g r a p h 当年发表的论文总数中占有相当大的比例。表 1 1 统 t t 2 0 0 0 年以来在s i g g r a p h _ j ：发表的计算机动画方向的论文的数目。 2 0 0 0 2 0 0 12 0 0 2 2 0 0 32 0 0 42 0 0 5 81 02 11 51 61 5 表1 1 ：2 0 0 0 年以来在s i g g r a p h 上发表的计算机动画方向的论文 在s i g g r a p h2 0 0 5 大会上，来a l i a s 公司的高级研究科学家j o ss t a m ，因其在细分 曲面和自然场景仿真，特别是对火、流体和气体方面的开拓性研究工作而荣获本年 度的“计算机图形学成就奖”( c o m p u t e rg r a p h i c sa c h i e v e m e n ta w a r d ) ；来自美 国s t a n f o r d 大学的r o n a l df e d k i w ，因其在计算机流体动力场方面的贡献而荣获本年度 的“重要新人奖”( s i g n i f i c a n t n e w r e s e a r c h e r a w a r d ) 。由此可见计算机动画的研究 在图形学领域已经占据了举足轻重的地位。 计算机动画按照研究对象的不同可以分为模拟人物的动画( 如【1 】【2 】) 以及 模拟自然景观的动画( 如【3 】【4 1 ) ；而按照最终生成的动画的风格的不同，则可 以分为真实感动画和非真实感动画( 如【5 】) 。流体的动态模拟是自然景观模拟 研究中非常具有代表性的一个方向，最近这几年的发展是突飞猛进。王华民博士 4 第1 章绪论 p s p e x s x n m b e r ；i i i j ；i ；：i i i i ；l 靠0 5 # 拍 2 0 1 0 0 擎$ 擎梦擎妒爹移擎梦擎擎擎擎守擎铲妒擎 图1 - 2 ：1 9 8 6 年至2 0 0 4 年在s i g g r a p h 、e u r o g r a p h i c s p a c i f i cg r a p h i c s _ l 舅 表的关于流体 的动态模拟的论文。 ( g v uc e n t e r ，g e o r g i ai n s t i t u t eo ft e c h n o l o g y ，u s a ) 统计t 1 9 8 6 年至2 0 0 4 年期问 在s i g g r a p h 、e u r o g r a p h i c s y f l l p a c i f i cg r a p h i c s 上发表的关于流体的动态模拟的论文的数 目，如1 2 所示。从该图中不难看出，从2 0 0 3 年开始，关于流体动态模拟的研究将迎来新 的”一轮高潮。 本文的研究方向为模拟自然景观的非真实感动画。本文将在下一章里详细介绍该方 向中研究的最新进展。 1 2 论文的主要研究内容及其意义 近年来卡通动画与游戏发展迅速。在这些场景中，除了角色如人物与动物之外，自 然场景如火、烟等也扮演着举足轻重的作用，需要高度重视。由于烟的形状具有高度不 规则性且其运动随机度很大，烟的动态模拟一直是计算机图形学中非常具有挑战性的难 题之一。 在已有的算法中，【6 】只能生成按照类似于正弦曲线上升的简单烟的卡通动画而不能 很好地模拟复杂的场景。【7 】提出的框架需要大量的人机交互，不能自动生成烟的卡通动 画。【8 】基于物理模型生成烟的卡通动画，但时间效率离实时要求还有一段距离：同时只 能生成线条图，其卡通风格单一。【9 】提出了一个实时绘制卡通烟的算法，但只关注烟的 绘制而没有涉及到烟的动态模拟。为了解决以上算法的不足，实时生成不同风格烟的卡 通动画，本文就烟的动态模拟和非真实感绘制两个关键技术进行了研究。 浙江大学硕士学位论文5 受【1 0 】的启发，我们应用平滑粒子动力学模型( s m o o t h e dp a r t i c l eh y d r o d y n a m i c s ，s p h ) 来模拟复杂而多变的烟的运动。当今计算机动画领域中模拟烟的主流方法 如【1 1 】【1 2 】都是将空问分割大量的小网格( g r i d ) 。与此不同的是，s p h 模型与网格无 关，是个基于粒子的模型。在基于粒子的模型如s p h 中，其物理量像速度、加速度都 是直接定义在粒子上，因此其模拟的精度也是由系统中的粒子数直接决定 1 3 】。 文章的研究对象是烟的卡通动画。卡通动画是一门抽象的艺术 1 4 1 ，主要包括以下 两个方面的抽象：运动抽象和视觉效果抽象【1 5 】。由于卡通动画的运动抽象特点，我们 没有必要在卡通动画中模拟烟的所有运动细节，因此我们只需要很少的粒子数就够了。 另一方面根据视觉效果的抽象，我们把每个粒子建模为一个椭球体，并把粒子绘制成一 个含有二值光照和轮廓线的椭圆。我们从本文后续的例子中可以看出，大约1 0 0 0 粒子就 能生成高质量的烟的卡通动画。 本文的主要贡献：本文是计算机动画领域第一次用物理模型实时生成卡通效果的 烟。我们应用s p h 模型模拟烟，该模型能很好地模拟烟的扩散力、重力、空气浮力和摩 擦力。我们在g p u 里面只需要一个通路( p a s s ) 就能将烟绘制成连续稳定的卡通效果。 基于这些直观而又有效的技术，生成一帧动画通常只需要4 0 m s 的时间( 包括动态模拟的 时间和绘制时间) 。 1 3 本文的组织结构 本文一共分为六章，其组织结构为： 第1 章为绪论，介绍了计算机动画领域的背景情况，包括计算机动画产业在全球 和中国的发展，以及它在卡通动画片、电影、计算机游戏等领域的不可替代的作 用。本章最后还概述了本文研究的主要内容及其组织结构。 第2 章综述了计算机动画领域在本文两个相关方向( 烟的动态模拟和烟的卡通绘 制) 的科学研究中的最新进展。这些研究成果是本文研究的基础。 第3 章详细介绍了本文模拟烟所采用的s p h 模型以及在s p h 模型中模拟扩散力、 外力等的若干细节。这个动域领域中第一次将s p h 模型显式地运用到烟地动态模 拟。 第4 章详细介绍了本文把烟在g p u 中绘制为卡通效果的实现细节，包括光照模 型，公告牌( b i l l b o a r d ) 所产生的闪烁现象及其消除算法，并详细讨论了基于可 编程流水线的绘制算法的实现细节。 第5 章展示了本系统所生成的卡通烟动画，并和已有的算法作了详尽的比较。 6 第1 章绪论 第6 章总结了本文的主要研究内容，指出了本文存在的不足并提出了下一步研究 的方向。 1 4 本章小结 本章介绍了本文研究相关的背景情况，包括计算机动画产业的发现现状以及计算机 动画技术的科研现状。本章详细介绍了计算机动画技术在全球经济发展中的地位，并指 出了计算机动画技术在动画片、电影特技、电脑游戏等领域中的巨大作用。接着，本章 概要介绍了本文的研究内容及其意义，并总结了本文的组织结构。 第6 章总结了本文的主要研究内容，指出了本文存在的不足并提出了下一步研究 的与向。 1 4 本章小结 本章介绍了本文研究相关的背景情犹，包括计算机动【回产业的发现现状以及计算机 动画技术的科研现状。本章详细介绍了计算机动画技术存全球经济发展中的地位，并指 出了计算机动画技术在动画片、电影特技、电脑游戏等领域中的巨大作用。接着，本章 概要介绍了本文的研究内容及其意义，并总结了本文的组织结构。 概要介绍了本文的研究内容及其意义，并总结了本文的组织结构。 第2 章计算机生成烟的卡通动画相关算法概述 2 1 烟的动态模拟的相关算法 2 1 1 早期烟的动态模拟算法 最近2 0 年，随着动画及其相关产业的不断发展，也随着计算机软硬件技术的不断进 步以及对流体力学研究的不断深入，烟的动态模拟在图形学领域得到了越来越广泛的关 注，成为计算机动画领域一个非常热门的研究领域。 和所有早期动画一样，最早的生成烟的动画都是靠人工绘制一系列描绘烟的动态过 程的图片，这些图片连续播放时就形成一个动画片断。这种人工绘制的方法需要耗费大 量的人力、物力和财力，而且绘制的图片可重用率相当低。同时，人工绘制烟的动画不 能自动描绘烟的翻滚、漩涡和外界物体的碰撞等效果。 计算机软硬件技术的发展使计算机生成烟及其他类似现象的动画成为可能。最早的 计算机动画的算法都是利用粒子系统 1 6 1 来模拟烟的浓度。这个时候的算法还不能直接 定义粒子的速度。【1 7 】【1 8 】【1 9 1 都是这种类型的算法。由于不能自动控制粒子的速度， 要想生成高质量的烟的动画，仍然需要动画师大量的人工干预以生成烟的动态效果。因 此这些算法对用户在动画、美工等专业知识方面都有很高的要求。粒子系统通常效率都 比较高，但也有两个缺点。烟及其周围的空气是一个连续的环境。而粒子系统只是采样 其中某些特定的点，因此其结果同真实效果有一定的距离。另外，烟的动态效果中最有 趣的现象如翻滚漩涡现象都是烟和周围气体相互作用的结果。这个时候的算法都还不能 有效地模拟这种效果。 早期的模拟烟以及其他气体现象的算法中效果比较好的还有w e j c h e r t 等的【2 0 】。该 算法用手工调整确定性的风力场的超位置( s u p e r p o s i t i o n ) 来模拟气体运动，这就使动 画师通过手工控制漩涡和风力来控制气体运动成为可能。【2 1 】【2 2 1 在傅立叶空间定义杂 乱无章的随机模型，然后再转换到无序但周期性的矢量场，从而模拟烟及其他气体的运 动和同简单障碍物的碰撞现象。这些算法都需要动画师在微观上精确控制烟的运动，而 对动画师来说，精确控制风的参数以及烟在微观上的随机参数都是非常困难的。 为了生成更加逼真、自然的烟的动画，就必须要直接应用流体力学中相关的理 论。2 3 1 是计算机图形学领域中第一篇应用流体力学来模拟动态烟的论文。但由于受到 当时( 1 9 8 4 年) 计算机硬件的限制，v d j i y a 等只能在很稀疏的网格上求解流体公式，其 效果也有很大的改进空间。之后的十几年里，除了一些在用二维模型 2 4 1 【2 5 1 来模拟烟 的算法外，这个领域一直没有得到重大的突破。 7 8 第2 章计算机生成烟的卡通动画相关算法概述 2 1 2 基于流体力学烟的动态模拟算法 基于流体力学模拟烟没有得到重大突破的状况一直持续到1 9 9 7 年。在f o s t e r 等人于 该年发表的 2 6 】中，他们尽管仍然在较稀疏的网格上建模，却能得到非常逼真的三维翻 滚效果。由于在1 2 6 1 中的模型采用显示积分的方法( e x p l i c i ti n t e g r a t i o n ) ，因此该算法 只有当积分的时间步长足够短的时候才稳定。这导致该算法运行相对较慢，特别是当烟 在整个区域里速度都比较大的时候。 为了解决这个流体模拟问题，s t a r e 于1 9 9 9 年1 1 1 提出一个无条件稳定且能以任意 速度运行的算法。该算法有机结合了半拉格朗h 算法( s e m i - l a g r a n g i a n ) 和隐式积分 ( i m p l i c i ts o l v e r ) 方法。基于这个算法，f e d k i w 等【1 2 】等提出的方法是目前烟真实感 模拟最具代表性的算法。他们把空间划分成很多个格子( 如图2 1 ( a ) 所示) ，然后在 这些格子上求解欧拉方程( 公式2 1 、2 2 ) ： v u = 0 ( 2 1 ) 鬻= - ( u - v ) u 一唧+ f ( 2 _ 2 ) 公式2 1 保证流体的质量守恒，同时公式2 2 保证流体动量守恒。公式2 2 中，p 是气体的压 力而f 是外力。 【1 2 】分两步求解欧拉公式。第一步在t 内在没有气体压力时求得中间速度1 1 + ： 1 u * - - r 1 1 = 一( u v ) u + f ( 2 3 ) 第二步减去压力的梯度求解粒子的速度场： u = u + 一a t v p ( 2 4 ) 同时，f e d k i w 毹e 【1 2 1 中还假设标量如密度队温度t 等沿着速度方向转移，并以此求 得每一时刻的密度和温度： 警叫u v ) t ( 2 5 ) 裳= ( u v ) p ( 2 6 ) 公式2 2 、2 5 ；f n 2 6 中都含有因子一( u v ) ，【1 2 】采用【1 1 】中半拉格朗日方法求解。 浙江大学硕士学位论文9 【1 2 1 中最主要的贡献在于通过引入漩涡限制( v o r t i c i t yc o n f i n e m e n t ) 来模拟烟在小 范围内的翻滚，是生成的烟更加逼真。该算法第一步找出需要生成翻滚细节的位置。在 不可压缩流体中，漩涡正好定义了这种小范围内的结构： u = v u ( 2 7 ) 每个漩涡可以看成是在流体中一个试图使流体沿着方向旋转的力场。由于数值计算 时导致旋转的能量衰减，因此就要把能量添加回去。首先把漩涡位置矢量( v o r f i c i t y l o c a t i o nv e c t o r ) 归一化： n = 罱 ( ”2 v ( 2 _ 8 ) 于是漩涡的旋转力的大小和方向为： f 。，= e h ( n u ) ( 2 9 ) 该算法能生成质量非常高的烟的动画，如图2 1 ( b ) 所示。该图中烟的漩涡得 以逼真地模拟，画面效果非常真实。该图用1 0 0 1 0 0 4 0 个网格模拟，其时间效率 为3 0 秒帧。 1 2 】之后，烟的动态模拟朝着更高精度模拟更大规模的烟的方向发展。【2 7 1 在大场景 中烟的模拟方面取得了长足进步。用 1 2 】中算法高精度地模拟如核爆炸等的大型复杂场 景，将需要2 0 0 0 2 0 0 0 2 0 0 0 个网格，这无论在时间上还是在内存空间上都是不可接受 的。为了解决这个问题，【2 7 1 在二维空间高精度进行基于流体力学的模拟然后再插值到 三维空间，最后再和三维k o l m o g o r o v 速度场( k o l m o g o r o vv e l o c i t yf i e l d ) 有机结合起 来生成高精度的三维动画。 【2 8 1 用八叉树来定义空间结构以精确求解烟的细节运动，同时还提出一种新的在八 叉树空间数值化求解泊松方程( p o i s s o ne q u a t i o n ) 的算法。该文除了能模拟烟外，还 能模拟很好地水等流体地运动。 已有的模拟动态烟的算法中，都是用六面体( 通常是正方体，图2 1 ( a ) ) 来分割 空间。2 9 1 提出一个用六面体和四面体的混合分割空间算法。该算法能有效地模拟烟和 具有复杂形状的障碍物碰撞的情形。 【1 2 】中提出的漩涡限制( v o r t i c i t yc o n f i n e m e n t ) 技术只是对已有漩涡的放大， 而s e l l e 等d k 的 3 】结合了拉格朗日漩涡粒子( l a g r a n g i a nv o r t e xp a r t i c l em e t h o d s ) 和 基于欧拉网格模型两者的优点，能生成比单纯只应用漩涡限制更具漩涡细节的烟，如 图2 1 ( c ) 所示。 1 0 第2 章计算机生成烟的卡通动画相关算法概述 ( c ) 图2 1 ：【1 2 1 所用的空间分割模型以致两个计算机生成烟的动画的倒子。( a ) ：【1 2 】中 空闻被分割成大量醵小网格，速度场定义在蹦格上；( b ) ：【1 2 1 生成的烟鲤效暴露； ( c ) ：【3 】生成的烟的效果图。 2 1 3 动态烟静控隶| j 娴的魂态控制最近这几年计算机动灏磅究梭域一个热门方向。鼹e 氆珏e 等f 3 0 l 予2 0 0 3 年 提出一个基于关键帧技术的炯的动态控制算法。在该算法中，关键帧包括密度* 键 帧和速度关键帧，分别表示褒时刻t 用户期特的烟的密度成帮速度l l ；，此时烟的实 际密度p 。和速度u 。烟赢尽可髓与之接近。为了达到这个效果，t r e u i l l e 簿应用发射技 术( s h o o t i n gt e c h n i q u e ) 产生最优化的风把烟吹向由关键帧确定的形状和属性。 图2 2 ( a ) 为f 3 0 】中烟澎成字母“s m o k e ”的毅果图。两于该算法采用商维非线性优讫 技术，其时间复杂度相当高。图2 2 ( a ) 采用5 0 5 0 的控制网格，每生成一个字母需 要2 5 d 靖。 受 3 0 1 的扁发，f a t t a l 等 3 1 1 于2 0 0 4 年提出一个目标驱动的烟的动态控制算法。该冀 法定义了两个特殊的力：驱动力( d r i v i n g f o r c e ) 和聚合力( g a t h e r i n g f o r c e ) 。驱动力 促使烟朝着刚示密度分布运动，面聚合力用来抵消烟的扩散现象。该算法不保证每两个 获态之闻的转移都是簸伉豹，馥因挠也清除了嚣线洼饶纯掰雩 越静时闯酒耗。 浙江大学硕士学位论文1 1 ( a ) ( b ) 图2 2 ：两个烟的动态控制的例子。( a ) ：【3 0 控制烟的形状生成s m o k e 字样 ( b ) ： 3 3 1 控制烟的形状生成一匹马。当风将马头吹散时，马头能重新自动生成。 同年，m c n a m a r a 等 3 2 1 提出一个应用伴随方法( a d j o i n tm e t h o d ) 的动态烟的控 制算法。该算法应用基于梯度的非线性技术来控制烟的运动。为了快速计算的梯 度， 3 2 从最优化控制理论受到启发，运用伴随方法来显著降低系统对控制参数的依赖 性，从而提高控制的时间效率。 与前面方法不同，l i n 等的 3 3 1 提出了一个基于水平集的算法。【3 3 1 把目标形状定义 为一个隐式方程( i m p l i c i tf t m c t i o n ) 并以此来驱动不规则形状的烟，并定义速度限制 ( v e l o c i t yc o n s t r a i n t ) 使烟的浓度分布的某等势面与零水平集很好地匹配。该算法在 控制的时间复杂度、烟的可控性以及烟的视觉效果等方面都取得了显著进步。该算法控 1 2 第2 章计算机生成烟的卡通动画相关算法概述 制烟的效果如图2 ，2 ( b ) 所示。 2 2 烟的非真实感绘制的相关算法 2 2 1 非真实感绘制概述 非真实感图形学的出现和发展丰富了计算机图形学的研究内容，非真实感已 经成为当今图形学的一个重要的领域。近几年计算机图形学的顶级会议s i g g r a p h , e u r o g r a p h i c s ，p a c i f i cg r a p h i c s 等都有非真实感图形学的专栏。而专门研究非真实感绘 制和动画的国际会议n o n - p h o t o r e a l i s t i cr e n d e r i n ga n da n i m a t i o n ( n p a r ) 也已成为 计算机图形学中的项级会议。 非真实感绘制，也称之为风格化绘制( s t y l i s t i cr e n d e r i n g ) ，不是以尽可能使结果 图像与物体相象为目标，而是根据绘制目的的不同将图像绘制成不同的风格效果。非真 实感绘制的一个目的是把物体绘制成工程示意酬3 4 】【3 5 】( 图2 3 ( a ) ) 。在这些图纸 中，只有那些与物体想要表达的特征直接相关的部分才有必要绘制。比如一张闪闪发亮 的法拉力跑车的照片对汽车零售商来说非常有用，但对于引擎的维修人员来说，这样 的照片还不如相关部分的线条图有意义，而且成本也要低得多。非真实感另一个目标 就是生成具有特定艺术风格的图片，如钢笔f 面 3 6 】( 图2 3 ( b ) ) 、木炭画 3 7 1 、水彩 画 3 8 】、国画 3 9 】( 图2 3 ( c ) ) 等等。 非真实感图形学按照其处理对象的不同，也可以分为两种不同的类型。其一为以将 二维的数字图像处理为具有特定艺术风格的图片，女n 4 0 】【4 1 1 。二维数字图像加上时间 轴，就成为把拍摄好的录像处理为卡通动碗， 4 2 1 就是这一领域比较成功的算法。另一 类型是以三维物体为输入对象，并将其绘制成具有某种风格的图片或动画，女n 1 4 3 】【4 4 1 【4 5 】。非真实感图形学的另一个分支就是设计一个笔刷系统，以方便用户快速的画出高 质量的美术图片，女h 3 9 】【4 6 】都从属于这个分支。 2 2 2 烟的卡通风格绘制算法 于金辉等【6 】等提出了一个用计算机生成二维卡通烟的模型。在他们的模型中，烟根 据浓度的不同分为烟团和烟缕两种风格。烟团画成类似于梅花瓣的形状；而烟缕的宽度 下宽上窄，其顶部被分解成若干小段的带状线条。该系统让烟按照类似于正弦曲线的路 径上升。随着烟的上升，曲线的幅度和频率都随着变大( 如图2 4 ( a ) 所示) 。该算法 只能生成线条图，卡通风格单一；跟重要的是，该算法不能模拟复杂运动时烟的卡通动 画。 在f i o r e 等【7 】提出的模型中，动画师先画一系列的随着时间不断变化的二维路径， 浙江大学硕士学位论文 ( a ) ( b ) ( c ) 瑙2 。3 ：三令簿真实感绘钢秘倒予。( a ) 1 3 5 1 中砖瓠械零锌罄：b ) ：1 3 6 # - 蔽麓钢笔 画；( c ) ：【3 9 1 生成的国画。 然衙系统将这些路径扩张成三维的路径并以她生成动硒。圈2 4 ( c ) 酃为【7 】的实验结 果，该模型最突出的优点是能够方便用户控皋4 烟等气体的上升和飘动，但这同时也要求 大登的入机交互。 s e e 等【8 磷! 出一莘申生成卡通烟动厕的方法。他们用f 1 2 】中的算法来模拟动态烟，然 后嗣扩展的深度差值算法【3 6 绘制。农f 3 6 中，通过读取深度缓存( d e p t h b u f f e r ) 中的 值然后比较每个像素和周围其他像素的深度。差值大于某一阈值的像素就是轮廓线上的 像素。由于需要读取深度缓存中的值，该算法可能会使绘南4 流水线停顿。该算法能得到 非嚣好的动馘，但每帧模拟动态烟需嚣3 秒，绘制需鬻1 秒，因此每帧总共需要4 秒。 圈2 + 4 ( d ) 都；0 1 8 囊成的卡遥效采斓的动番序列。阍【6 】一样，该算法也哭能生成烟的 线条图，同时其时间效率离实时还有段距离。 m c g u i r e 等翻提疆一种方法能实时地绘制有二值光照、轮廓和鲁阴影效栗的卡通潮 ! !第2 章计算机生成烟的卡通动画相关算法概述 ( 如图2 4 ( b ) 所示) 。该算法需要生成两块公告牌( b i l l b o a r d ) ，一块是根据法向矢 晕图生成的二值光照，另一个用来生成轮廓。为了在二维公告牌上生成曲线的阴影边 界，他们用 4 7 】中提到的方法根据深度图修改每个像素的深度信息。该算法没有考虑如 何模拟动态烟，而且绘制时需要生成两块公告牌，其时间效率也有提升的空间。 2 3 本章小结 本章回顾了与计算机生成烟的卡通动画相关领域的发展情况。本章先根据相应技术 发展历程的先后顺序，概要叙述了模拟以及控制动态烟生成计算机动画的相关技术，接 着介绍了非真实感绘制的相关概念，并着重介绍与本文主题烟的卡通动画直接相关的四 篇论文的主要算法。 浙江大学硕士学位论文1 5 ( a ) ( c ) ( d ) ( b ) 图2 4 ：已有烟的卡通动画。( a ) ：【6 w 的烟的卡通动画；( b ) ：【9 】中的烟的卡通动 画；( c ) ：【7 】中的烟的卡通动画；( d ) ：【8 1 申的烟的卡通动画。 第3 章生成烟的卡通动画中实时动态模拟算法 3 1 平滑粒子动力学模型 3 1 1 平滑粒子动力学模型的历史 模拟包括烟在内的流体现象，有两种不同的思路，分别称为欧拉方法和拉格朗日方 法。欧拉方法通常把空间分割成大量正方体的方格，研究每个方格内流体的流入流出情 况，并在每个方格内计算其流体的属性如密度、温度和压力的变化。因此应用欧拉方 法，我们最终求得的是作用在每个方格上的力以及该格子内流体的密度。欧拉方法是当 今烟的模拟中的主流方法，在烟的真实感模拟方面取得了巨大的成功。如【1 1 】【1 2 】等都 是基于欧拉方法的算法。 应用欧拉方法为了得到很好的结果，通常要把空间成数量级为百万以上个网格。即 使在对模拟精度要求不是很高的卡通动画中， 8 】中也用了1 2 8 ，0 0 0 ( 4 0 x8 0 4 0 ) 个网 格。由于网格的数目巨大，到目前为止，该方法还不适合于实时模拟。在一些高精度的 模拟中，生成一帧烟的动画，往往需要几十秒甚至更长的时间1 1 2 】。同时，由于欧拉方 法定义的格子中其实有很大一部分格子实际上是空的，从而造成一定量的计算浪费。另 外，由于欧拉方法关注的是格子而不是流体本身，因此这种方法的实现很不直观。 在与欧拉方法相对应的拉格朗日方法中，流体的属性都直接定义在流体的粒 子上。本文用到平滑粒子动力学( s m o o t h e mp a r t i c l eh y d r o d y n a m i c s ，s p h ) 模型是 一个基于粒子( p a r t i c l e - b a s e d ) 的拉格朗日方法。尽管s p h 模型最初是物理学家用 来模拟天文现象的工具 4 8 1 【4 9 】( 1 9 7 7 年) 【5 0 】( 1 9 9 2 年) ，它已经广泛地应用到图 形学领域。s t a m 等【5 1 】于1 9 9 5 年最先用s p h 模型来模拟火和其他气体现象，d e s b r t l n 1 0 于1 9 9 6 年用s p h 模型来模拟可高度变形的物体，都取得了很好的效果，从而引起 了大批图形学研究者的关注。近年来，s p h 模型已经被证明是一种有效的模拟火山 岩1 5 2 、液体1 5 3 】和头发 5 4 】【5 5 】( 如图3 1 ) 的模型。 3 1 2 平滑粒子动力学模型的基本公式 在s p h 模型中，流体用大量的平滑粒子来表示，相应地，每个粒子就是流体的一个 采样点，表示不断运动的小量非弹性流体。在实际计算中，平滑粒子用来近似求解流体 中连续的物理量及其梯度，如密度、压强等。这些物理属性对流体的动态模拟是至关重 要的。s p h j 馍型能保证对流体的动态模拟的有效性和稳定性。 在s p h 模型中，每个粒子i 有不变的质量佻，可变的密度伟，位置r l 和速度v 。 1 7 1 8 第3 章生成烟的卡通动画中实时动态模拟算法 图3 1 ：【5 5 1 0 e 用s p h 模型模拟的头发。 在s p h 模型中，质量代表该粒子表示的烟的多少，而密度由烟的分布决定【5 5 1 。粒子z 还 可以添加其他的物理属性如温度如。 为了有效计算流体的属性以及属性的梯度，s p h 模型定义了平滑长度( s m o o t h i n g l e n g t h ) h ，假设只有距离在2 内的两个粒子相互之间才存在作用力。相应地，s p h 模型 定义一个归一化( 积分等于1 ) 的平滑核( s m o o t h i n g k e r n e l ) w h ，用来表示粒子在 内 其质量分布的特征。在流体中任意一粒子平滑后的连续场q 用公式3 1 求得，而其梯度由 公式3 ，2 求得： g ( k ) = 啊警( | | r i 一i ) ( 3 1 ) v 咖) 2 莩m j 老v w n ( 1 1 n 一。i i ) ( 3 2 ) 将密度p 代入公式3 1 中，就能得到烟在每一粒子处的密度为： p i = ( i l r , 一酬) ( 3 3 ) 3 2 烟的实时动态模拟算法 平滑核w h 的选择在应用平滑粒子动力学模型中起着举足轻重的作用。如果我们把 粒子看成是流体的采用点，那么平滑核就是粒子在空间中的影响范围。事实上，平衡长 度h 定义了粒子相互作用力的影响半径。通过调整h 的取值可以得到流体不同的运动形 式。较小的h 定义了粒子的影响力局限在较小的范围，从而导致流质更容易被拉伸、撕 裂。同时我们不难发现平滑核还和计算的复杂度息息相关。如果粒子在空间中是均匀分 布的，粒子在半径为2 枷球体内m 的平均值正好可以用来计算每个粒子受到的作用力的 平均值。 浙江大学硕士学位论文1 9 d e s b r