1、毕业设计文献综述 计算机科学与技术 梵塔动画演示的设计与实现 一、 前言部分 写作目的： 介绍了应用 VB 语言实现动画演示将各个梵塔中各个盘子之间的移动，能够演示梵塔实现的每个步骤。让人从视觉上和思维上建立起梵塔的实现形式。方便大家理解其递归思想，能够加深对递归算法的理解和记忆。让大家能够对计算机在动画的实现上更深刻的了解和实用。 有关概念、综述范围： 什么是动画： 所谓动画，是指利用人的视觉残留特性使连续播放的静态画面相互衔接而形成的动态效果。计算机动画是由传统的卡通动画发展起来的。在传统卡通动画的制作过程中 ，导演首先要将剧本分成一个个分镜头，然后由高级动画师确定各分镜头的角色造型，并绘
2、制出一些关键时刻各角色的造型。最后，由助理动画师根据这些关键形状绘制出从一个关键形状到下一个关键形状的自然过渡，并完成填色及合成工作。最后，依次拍摄这一帧帧连续画面，就得到了一段动画片段。 什么是梵塔：梵塔也叫汉诺塔， 梵塔问题起源于中东地区的一个古老的传说：在梵城（ Hana）地下有一个僧侣的秘密组织，他们有 3 个大型的塔柱，左边的塔柱上由方到小套着 64 个金盘。僧侣们的工作是要把这 64 个金盘从左边塔柱转移到右边塔柱上去。但转移过程 有规定的：每次只能搬动一只盘子，盘 子 只能在 3 个塔柱上安放，不允许放在地上 ； 2、在每个塔柱上，只允许把小盘 子 叠在大盘上，反之不允许 。 什
3、么是递归算法： 一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界 条件满足时，递归返回 。 什么是 VB： VB 是 Visual Basic 的简称，是由美国微软公司于 1991 年开发的一种可视化的、面向对象和采用事件驱动方式的结构化高级程序设计语言，可用于开发 Windows
4、环境下的各类应用程序。它简单易学、效率高，且功能强大可以与 Windows 专业开发工具SDK 相媲美。在 Visual Basic 环境下，利用事件驱动的编程机制、新颖易用的可视化设计工1 具，使用 Windows 内部的广泛应用程序接口（ API）函数，动态链接库（ DLL）、对象的链接与嵌入（ OLE）、开放式数 据 连接（ ODBC）等技术，可以高效、快速地开发 Windows 环境下功能强大、图形界面丰富的应用软件系统。 争论焦点： 梵塔游戏可以通过计算机让其用动画的方式表示出来。在设计其实现方式上，就存在实用递归与非递归的方式将其实现出来。在设计其动画演示上，可以通过各种软件与哪种
5、编译语言将其表达出来。 二、主题部分 历史背景： 动画演示历史背景： 早在 1831 年，法国人约瑟夫 安东尼 普拉特奥 (Joseph Antoine Plateau) 在一个可以转动的圆盘上按照顺序画了一些图片。当圆盘在机器的带动下旋转时， 圆盘上的图片似乎动了起来，可称得上最原始的动画 。 1906 年，美国人户斯泰瓦德（ JStCWard）制作了一部名 叫 “滑稽面孔的幽默形象 (Houmoious Phases of a Funny Face)” 的短片，这部短片非常接近现代动画概念。 1908 年，法国人 Endle Cohl 首创用负片制作动画影片。所谓负片，是影像色彩与实际色彩
6、恰好相反的胶片，如同今天的普通胶卷底片。采用负片制作动画，从概念上解决了影片载体的问题，为今后动画片的发展奠定了基础。 1909 年，美国人 Winsor McCay 用一万张图片表现一段动画故事，这是迄今为止世界上认的第一部真正的动画短片。 1915 年，美国人 Eerl Hurd 创造了新的动画制作工艺。他先在赛珞璐片上画动画片，然后再把赛珞璐片上的图片拍摄成动画影片，这种动画片的制作工艺一直沿用至今。 1928 年开始，世人皆知的华特 迪斯尼 (Walt Disne)逐渐把动画影片的制作推向颠峰。他在完善了动画体系和制作工艺的同时，把动画片的制作与商业价值联系了起来，被人们誉为商业动画影
7、片之父。华特 迪斯尼带领着他的一班人马为世人创造出无以伦比的大量动画精品。例如 ，米老鼠和唐老鸭、木偶奇遇记和白雪公主等。直到今天，华特 迪斯尼创办的迪斯尼公司还在为全世界的人们创造出丰富多样的动画片。 动画的发展经过了一个漫长的历程，从最初的动画雏形到现在的大型豪华动画片，其本质没有太大的变化，而动画制作手段却发生着日新月异地变化。今天 ， “电脑动画 ”、 “电脑动画特技效果 ”不绝于耳，可见电脑对动画制作领域的强烈震撼。 传统动画片的生产过程 主要包括如下的几方面： 一、脚本及动画设计：脚本是叙述一个故事的文字提要及详细的文学剧本，根据该剧本2 要设计出反映动画片大致概貌的各个片断，也
8、即分镜头剧本。然后，对动画片中出现的各种角色的造型、动作、色彩等进行设计，并根据分镜头剧本将场景的前景和背景统一考虑，设计出手稿图及相应的对话和声音。 二、关键帧的设计：关键帧也称为原画，它一般表达某动作的极限位置、一个角色的特征或其它的重要内容，这是动画的创作过程。 三、中间帧生成：中间帧是位于关键帧之间的过渡画，可能有若干张。在关键帧之间可能还会插入一些更详细的动作幅度较小的关键帧，称为小原画，以便于中间帧的生成。有了中间画，动作就流畅自然多了。 四、描线上色：动画初稿通常都是铅笔稿图，将这些稿图进行测 试检查以后就要用手工将其轮廓描在透明胶片上，并仔细地描上墨、涂上颜料。动画片中的每一帧
9、画面通常都是由许多张透明胶片叠合而成的，每张胶片上都有一些不同对象或对象的某一部分，相当于一张静态图像中的不同图层。 五、检查、拍摄：在拍摄前将各镜头的动作质量再检查一遍，然后动画摄影师把动画系列依次拍摄记录到电影胶片上。十分钟的电影动画片，大约需要一万张图画。 六、后期制作：有了拍摄好的动画胶片以后，还要对其进行编辑、剪接、配音、字幕等后期制作，才能最后完成一部动画片。 由此我们可以看出，传统动画的设计制作过程相当复杂。 从设计规划开始，经过设计具体场景、设计关键帧、制作关键帧之间的中间画、复制到透明胶片上、上墨涂色、检查编辑，最后到逐帧拍摄，其消耗的人力、物力、财力以及时间都是巨大的。因此
10、，当计算机技术发展起来以后，人们开始尝试用计算机进行动画创作。 计算机动画的概念、发展和应用 一计算机动画：动画与运动是分不开的，可以说运动是动画的本质，动画是运动的艺术。从传统意义上说，动画是一门通过在连续多格的胶片上拍摄一系列单个画面，从而产生动态视觉的技术和艺术，这种视觉是通过将胶片以一定的速率放映的形式体现出来的。一般说来，动画是 一种动态生成一系列相关画面的处理方法，其中的每一幅与前一幅略有不同。 计算机动画是采用连续播放静止图像的方法产生景物运动的效果，也即使用计算机产生图形、图像运动的技术。计算机动画的原理与传统动画基本相同，只是在传统动画的基础上把计算机技术用于动画的处理和应用
11、，并可以达到传统动画所达不到的效果。由于采用数字处理方式，动画的运动效果、画面色调、纹理、光影效果等可以不断改变，输出方式也多种多样。 二、计算机动画的发展： 随着计算机图形技术的迅速发展，从 60 年代起，计算机动画技术也很快发展和应用起来。计算机动画区别 于计算机图形、图像的重要标志是动画使静态图形、图形产生了运动效果。计算机动画的应用小到一个多媒体软件中某个对象、物体或字幕的运动，大到一段动画演示、光盘出版物片头片尾的设计制作，甚至到电视片的片头片尾、3 电视广告，直至计算机动画片如 “狮子王 ”等。 三、计算机动画的特点：从制作的角度看，计算机动画可能相对较简单，如一行字幕从屏幕的左边
12、移入，然后从屏幕的右边移出，这一功能通过简单的编程就能实现。计算机动画也可能相当复杂，如动画片 “侏罗纪公园 ”。 计算机动画的关键技术体现在计算机动画制作软件及硬件上。动画制作软件是 由计算机专业人员开发的制作动画的工具，使用这一工具不需要用户编程，通过相当简单的交互式操作就能实现计算机的各种动画功能。不同的动画效果，取决于不同的计算机动画软、硬件的功能。虽然制作的复杂程度不同，但动画的基本原理是一致的。从另一方面看，动画的创作本身是一种艺术实践，动画的编剧、角色造型、构图、色彩等的设计需要高素质的美术专业人员才能较好地完成。总之，计算机动画制作是一种高技术、高智力和高艺术的创造性工作 。
13、梵塔历史背景： 在印度，有这么一个古老的传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上 插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的片金片，这就是所谓的 梵塔 。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。 不管这个传说的可信度有多大，如果考虑一下把片金片，由一根针上移到另一根针上，并且始终保持上小下大的顺序。这需要多少次移动呢 ?这里需要递归的方
14、法。假设有 n 片，移动次数是 f(n).显然 f(1)=1,f(2)=3,f(3)=7,且 f(k+1)=2*f(k)+1。此后不难证明 f(n)=2n-1。 n=64 时， f(64)= 264-1=18446744073709551615 假如每秒钟一次，共需多长时间呢？一个平年 365 天有 31536000 秒，闰年 366天有 31622400 秒，平均每年 31556952 秒，计算一下， 18446744073709551615/31556952=584554049253.855 年 这表明移完这些金片需要 5845 亿年以上， 而地球存在至今不过 45 亿年，太阳系的预期寿命
15、据说也就是数百亿年。真的过了 5845 亿年，不说太阳系和银河系，至少地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。 和汉诺塔故事相似的，还有另外一个印度传说：舍罕王打算奖赏国际象棋的发明人 宰相西萨 班 达依尔。国王问他想要什么，他对国王说： “陛下，请您在这张棋盘的第个小格里赏给我一粒麦子，在第个小格里给粒，第个小格给粒，以后每一小格都比前一小格加一倍。请您把这样摆满棋盘上所有格的麦粒，都赏给您的仆人吧！ ”国王觉得这个要求太容易满足了，就命 令给他这些麦粒。当人们把一袋4 一袋的麦子搬来开始计数时，国王才发现：就是把全印度甚至全世界的麦粒全拿来，也满足不了那位宰相的要求。 那么，
16、宰相要求得到的麦粒到底有多少呢？总数为 1+2+22+263=264-1 和移完汉诺塔的次数一样。我们已经知道这个数字有多么大了。 人们估计，全世界两千年也难以生产这么多麦子！ 现状和发展方向： 20 世纪 70 年代后期，随着计算机图形学和硬件技术的发展，计算机造型技术和真实感图形绘制技术得到了长足的进步，出现了与 一般 动画有质的区别的三维计算机动画。自 80年代初 开始，市场上先后推出了多个三维动画软件，这些计算机动画系统以友好的界面提供给用户一系列生成各种动画和视觉效果的手段与工具，用户可组合使用这些工具来生成所需的各种运动和效果。 计算机动画技术的成熟推动了动画软件的发展，其中影响较
17、大的商用软件有以下几种： 美国 Autodesk 公司 1991 年推出的在 Dos 环境下的 3D Studio， 1996 年推出的在 Windows 95/NT 环境下的 3D Studio Max， 1995 年推出的一种集图像处理、动画设计、音乐编辑、音乐合成、脚本编辑和动画播出于一体的二维动画 设计软件 Animator Studio； 法国的 TDI Explore（ SGI 图形工作站 Unix 环境），后被 Wavefront 兼并； 1984 年推出的美国的 Wavefront，后被 Alias 兼并； 1985 年推出的加拿大的 Alias（ SGI 图形工作站 Unix
18、 环境），后被美国的 SGI 公司兼并； 1998 年推出的美国的 maya（ SGI Unix 环境或 Windows NT 环境）； 美国的 lightwave3D； 1988 年推出的加拿大的 softimage（ SGI Unix 环境或 Windows NT 环境）， 1996 年被微软公司收购， 1998 年被 Avid 公司收购； 加拿大的 Sumatra。 随着计算机硬件性能价格比的快速提高和 Open GL 图形标准的广泛应用，商用动画软件公司纷纷推出了动画软件的微机版本。如原来运行于工作站上价格昂贵的动画软件Alias|Wavefront、 maya 和 softimage
19、 现在都已有了 NT 版本，这更进一步推动了计算机动画的应用和发展。近年来， PC 图形加速卡的性能价格比迅速提高，这使得在基于 NT 的微机工作站上制作动画也能与在 SGI 工作站上一样得心应手。目前，商品 化动画软件的功能越来越强大，使用也越来越方便。 后期处理在计算机动画中占据非常重要的位置。后期处理是指动画后期的非线性编辑合成技术，包括抠像、合成、图像 Morphing（渐变）、特殊光效等，从理论上说，它不属于计算机动画的范畴，但它是动画制作中必不可少的过程。特别是视频技术的数字化趋势，使该技术日益受到人们的重视。目前，已有许多优秀的后期合成软件，如 Flint、 Flame、 Jel
20、lio、5 Composer、 Eddie、 Premier、 Aftereffects 等。在这些软件中，大量采用了图像处理和计算机视觉技 术（如摄像机反求），使用户可方便地进行特技效果的处理和运动跟踪、深度合成等复杂操作。 简单地讲，计算机动画是指用绘制程序生成一系列的景物画面，其中当前帧画面是对前一帧画面的部分修改。动画是运动中的艺术，正如动画大师 John Halas 所讲的，运动是动画的要素。一般来说，计算机动画中的运动包括景物位置、方向、大小和形状的变化，虚拟摄像机的运动，景物表面纹理、色彩的变化。计算机动画所生成的是一个虚拟的世界，虚拟景物可以是商标、汽车、建筑物、人体、分子、桥
21、梁、云彩、山脉、恐龙或昆虫等，虚拟景物并不需要真正去建造 ，物体、虚拟摄像机的运动也不会受到什么限制，动画师可以随心所欲地创造他的虚幻世界。计算机动画的制作主要包含以下步骤： (1)创意，根据设计的需要，由导演设计好动画制作的脚本； (2)预处理，扫描外部图像，输入外部资料； (3)场景造型； (4)设定材质和光源； (5)设置动画 ； (6)运动图像的绘制； (7)动画播放 ； (8)后处理； (9)动画的录制； (10)配音（包括背景音乐和台词）。 计算机动画主要研究运动控制技术以及与动画有关的造型、绘制、合成等技术。尽管造型技术在 CAD 和 CAGD 中得到了广泛的研究，但计算机动画对
22、传统的实体、曲面造型提出了一些新的要求。一方面，计算机动画中场景造型的精度不必像工业设计那样高；另一方面，对造型工具的灵活性及景物运动的可控性提出了更高的要求。这导致许多针对动画应用而设计的造型技术，如隐函数曲面造型技术和 Catmull-Clark 离散曲面造型技术等。除此之外，由于其简单性和兼容性，多边形网格模型在计算机动画系统中得到了广泛的重视。绘制本身是真实感图形的主要研究内容，但随着动画技术的发展，传统的真实感图形绘制技术必须予以改造，使之满足动画的需要。动画技术 有很多，要对它们进行细致的分类是困难的。 计算机动画发展到今天，无论在理论上还是在应用上都已取得了巨大的成功，但离人们的
23、期望还有一定的距离，采用计算机动画模拟许多自然界的现象还有困难 ： 1 复杂拓扑曲面的造型和动画研究 动画追求的新奇性和创新性推动了这一方向的发展。物体的造型与动画通常有密切的联系，造型的某些新方法往往同时提供了新的动画控制方法。由于 NURBS 曲面在表示复杂拓扑物体方面存在着许多困难，由 Catmull 和 Clark 提出的根据任意拓扑控制网格生成 B 样条6 曲面的细分曲面方法近几年来在计算机动画中越 来越受到人们的重视，相关的论文不少。在1998 2000 年的 siggraph 中，有近 10 篇与 Catmull-Clark 细分曲面有关的论文，其中 Pixar公司的 DeRos
24、e 等人把细分曲面引入到角色动画中，取得了非常好的效果。在动画软件 maya中，基于 Catmull-Clark 细分曲面的造型和动画已经成为其重要手段。隐式曲面的造型和动画研究也令人关注。 2运动捕获动画数据的处理 运动捕获技术在电影泰坦尼克中取得了非常大的成功，该片中乘客从船上落入水中的许多惊险镜头都是由动画特技来完成的。实际上，运动捕 获已成为现代高科技电影不可缺少的工具。运动捕获的动画数据包括关节运动数据和脸部表情动画数据。怎样把运动捕获动画数据重用和重置目标值得进一步研究。 3基于物理的动力学动画 影视特技要求虚拟的动作画面能以假乱真，基于物理的动力学动画能较好地满足这一要求。这一方
25、面的研究包括怎样建立更具普遍性的数学模型、怎样减少计算量和怎样有效控制动画过程等 。 三、总结部分 本文较为详细地阐述了有动画演示和梵塔方面的知识，回顾历史，立足现实，展望未来。今后随着信息技术的发展和动画应用领域的逐步增加，计算机在动画演示发展将逐步 明显。动画演示的设计将会给程序工作人员带来更多的方便与挑战。我们应注重面对不同编译语言的学习能力和实用能力。这才能使我们能够跟上信息技术的脚步。如何应用计算机实现动画的演示，这是应该我们研究的重点。 四、 参考文献 1 聂黎生 . VB 动画设计原理及其实现 J.电脑学习 , 2006 2 李艳 .VB 中动画效果的实现 J. 福建电脑 , 2
26、008 3 刘炳文，许蔓舒 . Visual Basic 程序设计教程 . 北京：清华大学出版社， 2000 4 Sartaj Sahni . 数据结构、算法与应用 . 北京：机械工业出版社， 2003 5 王颖 ,王正洲 . 汉诺塔问题迭代算法实现和分析 J. 合肥联合大学学报 , 1999, (03) 6 冯丹 .网络存储关键技术的研究及进展 J.移动通信 ,2009(11):35-39。 7 陶世录 . 汉诺塔问题的深入探讨 J. 攀枝花学院学报 , 1994, (01)。 8 马莉莉 ,伊敏 . 利用 Visual Basic实现汉诺塔模型演示 J. 内蒙古农业大学学报 (自然科学版
27、), 2004, (04) 9 崔金玲 , 段新涛 . 汉诺塔问题新解 J. 河南 机电高等专科学校学报 , 2006, (01) 10 龙辉 . 基于 VB的动画设计 J. 科技信息 , 2009, (05) 7 11 周爱民 ,唐闻 . 基于 VB的启动相关程序设计 J. 电脑编程技巧与维护 , 2009, (22) 12 高山 ,杨卓 ,张涛 . Visual Basic中操作指针的技术及应用 J. 计算机工程与设计 , 2009, (24) 13 亓传伟 , 任艳斐 . 递归在程序设计中的应用 J. 濮阳职业技术学院学报 , 2005, (04) 14 陈文 . 汉诺塔非递归算法 J.
28、 电脑编程技巧与维护 , 2009, (14) 15 罗海林 ,金纯 . 浅谈递归算法在程序设计中的运用 J. 电脑知识与技术 , 2009, (09) . 16 杨秀荣 ,王春红 . 递归程序设计方法的分析探讨 J. 电脑知识与技术 , 2009, (06) 17 李志辉 . Visual Basic程序设计课程教学研究 J电脑知识与技术 , 2009,(17) 18 Kim, J., A Web-Based Speaking Test Development Using Visual Basic 6.0. Multimedia Assisted Language Learning, 2006. 9(2): p. 77-98 19 Somma, J., et al., Rapid Development and Validation of a Three-Compartment Non-Linear with Covariate PK Simulator Using Visual Basic 6.0 and the Simulink Component of MatLab. Anesthesiology, 2003. 99(A510): p. A510
