[高等教育]分形动画毕业设计论文.doc

密级： NANCHANG UNIVERSITY学 士 学 位 论 文THESIS OF BACHELOR题 目 分形动画与自然场景模拟算法研究 学 院： 信息工程学院 系 计算机系 专业班级： 计算机科学与技术 054 学生姓名：李金达 学号： 6103105081 指导教师： 杨承根 职称： 讲师 起讫日期： 2009年1月-2009年6月 30分形动画和自然场景模拟算法研究摘要 自然景物模拟是计算机图形学中的一个重要研究课题。自然景物的随机性和不规则性难以用传统的方法描述,而分形对自然界复杂事物的客观规律及其内在联系提供了新的概念和方法，成为自然景观的模拟的一种独特技术。 本文首先介绍了分形的数学基础理论，讨论了分形图形的叠加与变换和分形插值等算法，并以visual C+为开发平台，实现了摇曳的树、分形云和山等自然场景的模拟。实验结果表明产生的图像自然、逼真。关键词：迭代函数系统 分形场景 分形动画The study of Fractal Animation and Algorithms for Generating Fractal LandscapesAbstract Simulating nature scenery in computer is a basilica subject in the computer， graphics research. The random city and scrambling of nature scenery in formal is difficult to be described by traditional means. Fractal theory supplies the new concept and way to discuss impersonal rule and intrinsic contact of natural complicated things.，the fractal technique shows its single advantage This paper first explains the mathematics basic of fractal.discuss the fractal picture' Superposition and transformation and fractal Interpolation and so on. and the development platform is vs+,achieve the swaying trees, fractal clouds and mountains and other natural scene simulation. The experimental results show that images generated by the natural, life-likeKeyword: Fractal , Fractal Landscapes , Animation目录摘要IABSTRACTII第一章综述11.1分形理论的发展11.2分形的应用与自然场景的生成41.3 本文的工作5第二章分形的理论基础62.1 分形的理论基础62.1.1分维62.1.2 分形原理72.2 分形的数学基础102.2.1 空间及变换102.2.2 迭代函数系统及其吸引子112.2.3局部迭代函数系统LIFS122.2.4 拼贴定理122.3 分形的自相似性13第三章 分形动画与自然场景生成算法的实现153.1分形动画-摇曳的树153.2 分型自然景物模拟算法163.2.1 递归算法生成分形树163.2.2 分形云223.2.3 分形山233.2.4 分形插值法25第四章 参考文献29致谢30第一章综述1.1分形理论的发展 分形在英文中为fractal，是由美籍法国数学家曼德勃罗创造出来的。此词源于拉丁文形容词fractus。对应的拉丁文动词是frangere（破碎，产生无规碎片）。此外，它与英文的franction及fragment具有相同的词根。在20世纪70年代中期以前，曼德勃罗一直使用英文fractional一词来表示他的分形思想。因此取拉丁词之头，撷英文之尾所合成的fractal，本意是不规则的、破碎的、分数的。曼德勃罗是想用此来描述自然界中传统欧式几何学所不能描述的一大类复杂无规的几何对象，例如，蜿蜒曲折的海岸线，起伏不定的山脉，粗糙不堪的断面，变幻无常的浮云，九曲回肠的河流，纵横交错的血管，令人眼花缭乱的漫天繁星等。它们的特点是，极不规则或极不光滑。直观而粗略地说，这些对象都是分形。 1975年，曼德勃罗出版了他的法文专著分形的对象：形、机遇与维数，标志着分形理论正式诞生。1977年他又出版了该书的英译本。1982年曼德勃罗的另一部历史性著作大自然的分形几何学与读者见面，该书虽然是前书的增补本，但在曼德勃罗看来却是分形理论的“宣言书”，而在分形迷的眼中，它无疑是一部“圣经”。该书旁征博引，图文并茂，从分形的角度考察了自然界中的诸多现象，引起了学术界的广泛注意，曼德勃罗也因此一举成名。 此后，一直持续的分形热吸引了全世界众多科学家和学者，他们在各自领域中的研究工作，使分形理论遍地开花。 分形作为几何对象，首先是破碎的、不规则的、但不是所有破碎的、不规则的形状都是分形。曼德勃罗曾经给分形下过这样的一个定义：组成部分与整体以某种方式相似的形。也就是说，分形一般具有自相似性。但分形理论发展到今天，已经不仅限于研究对象的自相似性质了，如果一个对象的部分与整体具有自放射变幻关系，我们也可以称它为分形。今后，条件可能还会进一步拓宽，只要是部分与整体以某种规则联系起来，通过某种变幻使之对应，我们都可以将其看成是分形，因此分形的本质就是标度变换下的不变性，而这层意思是可以拓展的。1、 自相似性 自相似便是局部与整体的相似，或者说，局部是整体的缩影等。2、 自仿射性 是自相似性的一种拓展。如果将自相似性看成是局部到整体在各个方向上的等比例变幻的结果的话，那么，自仿射性就是局部到整体在不同方向上的不等比例变幻的结果。前者成为自相似变换，后者称为自仿射变换。3、 精细结构 分形还有一个更重要的特征，即精细结构。在理论上Koch曲线是按一定规则无限变化的结果，所以，假如用一个数学放大镜来看Koch曲线的话，无论放大多少倍，都能看到里面还有与整体相似的结构。这一点非常接近于自然界中的对象。在这里我们不打算讨论物质是否无限可分，我们只是注意到分形和自然对象都具有极多层次的结构。这是分形的最基本的特征。4、 分形与欧氏几何图形的区别可以看出分形与普通的欧氏几何图形有明显的区别：1) 欧氏图形是规则的，而分形是不规则的。2) 欧氏图形层次是有限的，而分形从数学角度上讲层次是无限的。3) 欧氏图形一般是不会从局部到整体的信息，因为它们不强调局部与整体的关系，而分形强调这种关系，所以，分形往往可以从局部看出整体。4) 欧氏图形越复杂，其背后的规则也必定越复杂，而对于分形图形，虽然看上去十分复杂，但其背后的规则却是相当简单的。分形是一类形状，更是一种方法论。从分形的角度看世界，我们可以发现很多未曾注意的现象与规则。正如沃尔夫奖在颁发给分形理论创始人曼德勃罗时的评语所说的，“分形几何改变了我们对世界的看法”。人类通常习惯于从时间和空间两个方面来考察事物。沿着时间轴，我们可以看到事物的发展状况；面对空间轴，我们可以看到事物的形态和分布状况。而分形方法是人类观察事物的第三轴，它是从纵深的角度看世界。如果我们将被观察对象看成系统的话，而系统又是由多个层次组成的，那么分形是研究这些层次之间关系的一种方法。分形理论是当今十分重要的现代数学的一个新分支，被誉为大自然的几何学。分形的思想研究的开始可以追溯到大约100年前的数学领域。1967美籍数学家曼德布罗特(B.B.Mandelbort)在美国权威的科学杂志上发表了题为英国的海岸线有多长?的著名论文。海岸线作为曲线,其特征是极不规则、极不光滑的,呈现十分蜿蜒复杂的变化。我们不能从形状和结构上区分这部分海岸与那部分海岸有什么本质的不同,这种几乎同样程度的不规则性和复杂性,说明海岸线在形貌上是自相似的,也就是局部形态和整体形态的相似。在没有建筑物或其他东西作为参照物时,在空中拍摄的100公里长的海岸线与放大了的10公里长海岸线的两张照片,看上去会十分相似。事实上,具有自相似性的形态广泛存在于自然界中,如:连绵的山川、飘浮的云朵、岩石的断裂口、布朗粒子运动的轨迹、树冠、花菜、大脑皮层曼德布罗特把这些部分与整体以某种方式相似的形体称为分形。 回到英国海岸线有多长的问题，我们可以看出问题的答案并不像想象中那么简单。测量海岸线长度将完全取决于使用的测量装置的尺度。如果你是以公里为测量单位来测量海岸线长度，你可能会认为它会产生一个合理精确的测量。但是你已经忽略了每公里的所有粗糙的细节。你会发现使用米尺为测量单位，海岸线长度会产生大得多的结果。事实上，无限制地采用更小尺度的每一次测量就得到一个更大的测量结果。问题的答案正是于英国海岸线没有长度，因为它不是一维的。它是一个分数维。1973年，曼德布罗特在法兰西学院讲课时，首次提出了分维和分形几何的设想。1975年,他创立了分形几何学。在此基础上,形成了研究分形性质及其应用的科学,称为分形理论。分形一词，是曼德布罗特创造出来的，其愿意具有不规则、支离破碎等意义，分形几何学是一门以非规则几何形态为研究对象的几何学。由于不规则现象在自然界是普遍存在的，因此分形几何又称为描述大自然的几何学。分形几何建立以后，很快就引起了许多学科的关注，这是由于它不仅在理论上，而且在实用上都具有重要价值。分形几何学的基本思想是：客观事物具有自相似的层次结构，局部与整体在形态、功能、信息、时间、空间等方面具有统计意义上的相似性，称为自相似性。例如，一块磁铁中的每一部分都像整体一样具有南北两极，不断分割下去，每一部分都具有和整体磁铁相同的磁场。这种自相似的层次结构，适当的放大或缩小几何尺寸，整个结构不变。维数是几何对象的一个重要特征量，它是几何对象中一个点的位置所需的独立坐标数目。在欧氏空间中，人们习惯把空间看成三维的，平面或球面看成二维，而把直线或曲线看成一维。也可以稍加推广，认为点是零维的，还可以引入高维空间，对于更抽象或更复杂的对象，只要每个局部可以和欧氏空间对应，也容易确定维数。但通常人们习惯于整数的维数。分形理论认为维数也可以是分数，这类维数是物理学家在研究混沌吸引子等理论时需要引入的重要概念。为了定量地描述客观事物的“非规则”程度，1919年，数学家从测度的角度引入了维数概念，将维数从整数扩大到分数，从而突破了一般拓扑集维数为整数的界限。1.2分形的应用与自然场景的生成分形已经在许多领域中得到了非常有效的实际应用。在物理学上，用分形论来研究基本粒子，在生物学上，分形用于蛋白质的研究，在地震学上，分形可使地震预报水平进一步提高，在信息科学上，分形理论研究通信中噪声结合和模式、语音识别，在社会科学中，将分形用于经济学，可以研究市场商品价格的浮动，也可应用于情报学、管理学、思维科学和音乐等方面的研究。在计算机图像学中，可以用分形理论来描述和显示山脉、海岸线、闪电、湖泊等自然景物的逼真性图形，同时运用在计算机艺术领域，可产生出一幅幅色彩斑斓的美丽图案和图形，这不仅具有观赏价值，还可以进行装潢、花纹设计等。在数字图像处理中，运用分形理论，可进行高压缩比的图像压缩编码和纹理分析等。分形还只是一种有趣的新生事物的萌芽的话，那么今天它已经成为一个令人瞩目的前沿学科。在大量实际应用的同时，分形给科学思想带来的启发，也是十分值得注意的。由于分形的研究，人们对于随机性和确定性的辩证关系有了进一步的理解。同样对于过程和状态的联系，对于宏观和微观的联系，对于层次之间的转化，对于无限性的丰富多彩，也都产生了有益的影响，提供了启发。在这方面的影响也是非常深远，非常重要的。总之，对于从事计算机技术研究的人来说，分形是一个值得注意的前沿学科，有必要了解它的思想与方法。这对于计算机科学与技术的进步和发展，无疑将是十分有益的。自然景物是指那些无规则的、很难用数学表达式描述其几何形状和变化规律的物体，比如山脉、岩石、树木、云彩、水、火、雾及各种植物表皮等。它们的表面呈现出随机的、凹凸不平的情况，因而不能用简单的纹理映射技术得到满意的模拟效果。在实用多媒体动画创作软件中，自然景象模拟部分大多以独立模块的形式出现，如借助特殊效果模块可以制作闪电、烟雾、水波等动画效果。为了用计算机绘制出各种真实的自然景象，需要对景物的不规则表面（几何纹理）进行有效的表示及绘制。目前常用的方法大致可分为两种，一种是对常规景物模型进行随机扰动，从而获得不规则的景物表面形状；另一种方法即所谓的算法模型，它通过使用一种递归模式，引入随机变量，实现对不规则景物的造型。以下针对这两种方法进行介绍。一、法向扰动法法向扰动法主要用于模拟表面细微的凹凸不平的景物。因此在动画创作软件中模拟自然界中植物表皮效果的功能模块大都由法向扰动法来实现。由blinn提出的法向扰动法采用了一个扰动函数（可以解析地定义，也可用一组离散数据非解析地定义）对常规曲面的法向量进行“扰动”，即在表面每一点上沿其表面法向方向附加一个新的向量。这一向量比较小，不影响原表面的大致形状，但对表面该点处的法向产生较大的扰动作用，结果使曲面变得非常粗糙。通过恰当地选择扰动函数，可使生成的图形具有不同的皱折纹理效果。法向扰动法的主要缺点是扰动函数不容易选取，另外，景物的“不规则性”仅局限于给定物体的表面上，而不反映在物体的整体构造上。二、fbm方法fbm方法全称为“分维布朗运动”（fractional brownian motion）方法，是一种使用随机过程来模拟不规则物体方法。它主要用来作为自然界中许多自然时间序列的模型。fbm方法可以很好地描绘地域、星球表面、山脉、丛林等自然景观，其“不规则性”可以通过参数h及方差来控制。fbm方法的主要缺点是计算复杂，因而生成一帧真实感画面要花费大量的计算时间。fournier等人提出了计算近似fbm的算法，使近似fbm的计算趋于线性。三、粒子系统方法粒子系统的基本设计思想是采用许多形状简单的微小粒子作为基本元素来表示不规则模糊物体。这些粒子都赋予一定的“生命”，它们在系统中都要经历“出生”、“运动和生长”及“灭亡”三个阶段。由于粒子系统是一个有“生命”的系统，因而它不像传统方法那样只能生成瞬时静态景物画面，而可以产生一系列运动进化的画面。这使得模拟动态的自然景象成为可能。借助粒子系统可以方便地构造火、雾、烟、云、花炮、树及花草等模型。由于粒子系统是一个生命系统，因而粒子的“出生”、“运动和生长”及“灭亡”都不是确定的，而是采用随机过程来控制。粒子系统已经成功地模拟了电影“星球大战”中的一系列特技镜头。1.3 本文的工作本文首先介绍了分形的原理，数学基础和特性。通过多个分形图形的叠加与变换产生出自然景物图形的方法，并以摇曳的树为例在计算机上实现了此分形图的逼真模拟。以静态分形图形为基础， 利用分形插值算法，随机中点位移法，实现了模拟自然界山云的分形图形。第二章分形的理论基础2.1 分形的理论基础 2.1.1分维在欧氏空间中，人们习惯把空间看成三维的，平面或球面看成二维，而把直线或曲线看成一维。也可以梢加推广，认为点是零维的，还可以引入高维空间，但通常人们习惯于整数的维数。分形理论把维数视为分数，这类维数是物理学家在研究混沌吸引子等理论时需要引入的重要概念。为了定量地描述客观事物的“非规则”程度，1919年，数学家从测度的角度引入了维数概念，将维数从整数扩大到分数，从而突破了一般拓扑集维数为整数的界限。 分维的概念我们可以从两方面建立起来：一方面，我们首先画一个线段、正方形和立方体，它们的边长都是1。将它们的边长二等分，此时，原图的线度缩小为原来的1/2，而将原图等分为若干个相似的图形。其线段、正方形、立方体分别被等分为21、22和23个相似的子图形，其中的指数1、2、3，正好等于与图形相应的经验维数。一般说来，如果某图形是由把原图缩小为1/a的相似的b个图形所组成，有： aD=b, D=logb/loga 的关系成立，则指数D称为相似性维数，D可以是整数，也可以是分数。另一方面，当我们画一根直线，如果我们用0维的点来量它，其结果为无穷大，因为直线中包含无穷多个点；如果我们用一块平面来量它，其结果是0，因为直线中不包含平面。那么，用怎样的尺度来量它才会得到有限值哪？看来只有用与其同维数的小线段来量它才会得到有限值，而这里直线的维数为1（大于0、小于2）。与此类似，如果我们画一个Koch曲线，其整体是一条无限长的线折叠而成，显然，用小直线段量，其结果是无穷大，而用平面量，其结果是0（此曲线中不包含平面），那么只有找一个与Koch曲线维数相同的尺子量它才会得到有限值，而这个维数显然大于1、小于2，那么只能是小数（即分数）了，所以存在分维。其实，它的豪斯多夫维数(分维数)为d=log(4)/log(3)=1.26185950714.2.1.2 分形原理我们看到正方形，圆，球等物体时，不仅头脑里会迅速反映出它是什么，同时，只要我们有足够的数学知识，我们头脑中也反映出它的数学概念，如正方形是每边长度相等的四边形，圆是平面上与某一点距离相等的点的集合，等等。 但是，当我们看到一个山的形状时，我们会想到什么?"这是山"，没错，山是如此的不同于其他景象，以至于你如果绘画水平不高，根本画不出象山的东西。可是，山到底是什么?它既不是三角形，也不是球，我们甚至不能说明山具有怎样的几何轮廓，但为什么我们却有如此直观而又强烈的山的印象? 因为山有自己所遵循的规律，这个规律就是分形(fractal)。 我们沿着大师所指的道路来进入分形世界。 分形的创始人是曼德布洛特，他引入分形的第一篇论文有一个奇怪的名字" 英国的海岸线有多长?"。答案是:取决于你的尺子。详细的解释就是:当你用一把固定长度的直尺(没有刻度)来测量时，对海岸线上两点间的小于尺子尺寸的曲线，只能用直线来近似。因此，测得的长度是不精确的。如果你用更小的尺子来刻画这些细小之处，就会发现，这些细小之处同样也是无数的曲线近似而成的。随着你不停地缩短你的尺子，你发现的细小曲线就越多，你测得的曲线长度也就越大。如果尺子小到无限，测得的长度也是无限。听起来有点象芝诺的战士与乌龟的悖论，但芝诺悖论考虑的是有界的情况，而这里的情况则是无界的。 如果问题仅止于此，那么这个论文不但没什么意义，而且还有点无聊了。但是，海岸线的长度有着极有规律之处。那就是:海岸线长度的某次幂与尺子长度成正比。这里意味着海岸线中蕴藏着无限自相似性。就是说:任意一段海岸线就象是整个海岸线按比例缩小的结果，遵循相似的规律。 无限自相似性就是分形的精髓。 具有无限自相似性的图形并不是曼德布洛特的独创。19世纪就有数学家提出了，但这个东西对数学家来说却是痛苦的回忆，因为它给数学家们精心构造的理论大厦的基础上重重来了一下。以至与数学家们在谈到这些图形时，总称之为"怪物"，"自然界中不存在的"(注)。但曼德布洛特则证明了分形在自然界中是最普遍的规律之一，并且，分形有自己严格而优美的规律，它不是怪物， 还有更多的分形“怪物”。象填满整个平面的不封闭曲线（不在曲线上的平面面积=0），每一点都是分叉点的曲线，个头巨大，质量为零的海绵，填满整个空间的平面，这些东西完全无法纳入经典数学的领域。于是，数学家们就奉行了一种鸵鸟主义，宣称这些东西自然界中不存在，只有少数纯粹数学家们为了理论的优美而去研究它们。 我本来想避开分数维的概念，但看来还是不避开的好。不过，只要大家认真去看，会发现它其实没什么难懂的。 我们知道0维是点，一维是线，二维是面，三维是空间。那么，谁能告诉我1.5维是什么? 一条直线段是一维的，由四条这样的直线段组成的正方形是二维的。六个这样的正方形组成的正方体是三维的。直线的长度数值，正方形的面积数值和立方体的体积数值都和我们测量的单位有关。测量的单位也往往是我们所能分辨的最小单位。假设我们的分辨能力增加了一倍，因此我们把直线段长度单位减小到原单位的一半，直线段长度的计量值就变为原来的两倍，正方形面积就变为原来的四倍，体积则变为原来的八倍。 我们有下式:log4/log2=2log8/log2=3这里的二和三不是巧合，这是另一种维数的定义:测度维的概念。回到海岸线长度的问题。当用直线段来近似曲线时，长度单位减为原来的一半往往意味着我们可以用长度为原来的二分之一的直线段来近似曲线。这时，海岸线长度增加程度近似于一个固定的倍数。对于英国海岸线来说，其值约为2.7，而log2.7/log2=1.41，1.41就是英国海岸线的维数。 1.41由于是一个分式所得出的比值，因此人们称之为分数维。还有其他一些分数维的定义方法，但得出的结果都比较近似。分数维是衡量分形的基本参数之一。以山脉为例，人们发现，自然界山脉的维数都近似于 2.2，因此计算机作图时，选择2.2的分数维就可以做出类似自然界的山脉图形来。 也许人们会感觉分形的计算很困难。但由于分形的无限自相似性，在计算机上实现分形其实很容易。我下次将讲解分形布朗曲面生成山脉的方法。更多的技巧则将在我最后完成随机数发生器后，写一篇"分形应用"。自然界的山,其分形维数在2.2维左右,但从2.1维到2.5维画出来的都有一定的山的效果. 下面介绍分形布朗曲面画山的方法.先从分形布朗曲线说起. 分形布朗曲线需要用到高斯随机数,高斯随机数的说明可以参照我以前写的一篇"随机数在游戏设计中的应用",这里说明一下高斯随机数的生成.简单的生成方法是把随机数用2进制表示,数出二进制表示中1的数目,对于32位随机数来说,二进制表示中1的数目接近于均值为 16,方差为4的高斯分布,如果用几个32位随机数模拟,其分布将更为接近.为了使高斯随机数能尽量广泛地分布,我们可以在产生高斯随机数时,再使用线性随机数(就是最普通的随机数)进行插值.比如,我用两个 32位随机数模拟16位高斯分布随机数,两个32位随机数二进制表示中1的数目为0-64,因此我们每次用这一方法算出一个数后,都把它乘以65535/65=1008,再加上一个取值从0-1008的线性随机数,就可以得到一个相当近似的高斯随机数了,它的方差为8192.但这样的随机数产生速度太慢,可以用我以前所讲的方法,用查预制随机数表来产生高斯随机数,而方差为8192/A的高斯随机数只要把方差为8192的高斯随机数除以A 即可得到. 分形布朗曲线的物理定义是一维布朗运动的位移-时间坐标图,但它们的物理意义和我 们作图无关.分形布朗曲线的作图方法是选择点A(x1,y1)为起点,点 B(x2,y2)为终点,选择分形布朗曲线的 标度因子H(0 整个运算过程好像非常复杂,但我们可以看到它有极大的优化余地. 我们可以用非递归算 法来计算,每次把相同尺度的分形计算全部完成,并可以把2*2H预先算出,这样,每次对相同尺度的分形 进行计算时,我们只需要一次运算就可以知道我们所得到的16bits高斯随机数除以一个怎样的参数后就可 以得到此次可用的随机数,而相同尺度的运算中还有更多的优化方法.在此不一一叙述。 总之,实时计算出地形参数是完全可行的.2.2 分形的数学基础2.2.1 空间及变换 1Hasdorff距离空间定义1 在空间X上定义一个实数函数d：XXR且满足距离公理，则记d(X,d)为以d为距离的距离空间。定理1 如果在距离空间(X，d)上的点列xn，n=1，2，收敛于x X，则xn，n=1，2，是一个柯西序列。定义2 距离空间(X，d)是完备的，如果在X中的所有柯西序列都是收敛序列。 定义3 设(X，d)为距离空间，记H(X)表示由X的非空紧子集的全体组成的空间。xX，BH(X)，定义： d(x,B)=infd(x,y),yB=mind(x,y):yBA，BH(X),定义： d(A,B)=supd(x,B)：xA=maxd(x,B):xA为集合A到B的距离。 设(X，d)为距离空间，则H(X)中的两个点A，B间的Hausdorff距离定义为： 则(H(X)，h(d)为基于Hausdorff距离的距离空间，也称为分形空间。而分形集之间的距离也正是由这种Hausdorff距离度量的。 2仿射变换 定义1 在R上的仿射变换形如： f(x)=ax+b式中a，b为实数，a表示伸缩因子，b表示平移因子。 定义2 在R上最一般变换形如： f(x)=a0+a1x+a2x2+aNxN式中ai为实数，aN0，N是多项式的次。 定义3 变换f：RR,定义为 其中a，b，c，dR，adbc，称为“线性分式变换”，并且 如果c0，f(-d/c)=,f()=a/c,如果c=0,则f()= 。 定义4 在R2上的仿射变换：R2R2，形如： 其中为X轴比例因子，为X轴旋转角度，为Y轴比例因子，为Y轴旋转角度。 定义5 在R2上的仿射变换：R2R2称为相似的，它具有以下仿射变换形式： 定义6 设f：XX是距离空间上的一个变换，如果f(xf)=xf,称xf为f的不动点。 定义7 在距离空间(X，d)上的一个变换：f：XX，如果存在一个常数0s1，使 则称f为压缩映射，s为f的压缩因子。 定理1 压缩映射定理(Banach不动点定理)。设f：XX是完备距离空间(X,d)上的一个压缩映射，则f具有惟一的不动点xfX，且xX，序列f0n(x):n=0,1,2,收敛于xf，即 2.2.2 迭代函数系统及其吸引子 定义1 一个(双曲)迭代函数系统IFS，是由一个完备距离空间(X，d)和一组分别具有压缩因子sn的有限个压缩映射组成， 系统表示为X；1，2，N且具有压缩因子s=maxs1，s2，sN此处双曲的概念是指变换为压缩的。 吸引子定理 设X；1，2，N是一个（双曲）IFS，以sn为压缩因子，则由下式定义的W：H(x)H(x) 是在完备距离空间(H(x)，h(d)上以压缩因子maxs1，s2，sN的压缩映射，即且存在一个惟一不动点H(X)，满足：H(X)，A可通过W的迭代求得： W0n(B)表示变换W的n次复合，即W0n(B)=W(W(W(B)，A称为这组映射下的不变集，A=W(A)。 定义2 吸引子定理中所述的不动点AH(X)称为IFS的吸引子(Attractor)。2.2.3局部迭代函数系统LIFS 定义1 设(X，d)为一紧距离空间，D为X的一个非空紧子集。定义映射：DX，s为一实数，0s1，如果 则称为在(X，d)上的局部压缩映射，其中s为的压缩因子。 定义2 设(X，d)为一紧距离空间，令i：DiX是在(X，d)上具有压缩因子si：0si1的局部压缩映射，则 X：i：DiX，i=1，2，N称为一个局部迭代函数系统LIFS。2.2.4 拼贴定理 拼贴定理：设(X，d)是一完备距离空间，令LH(X)，0是给定的，如果可以找到一个收缩因子为s（0s1）的IFSX；1，2，N，使得下式成立： 其中h(,)为Hausdorff距离，则有： 其中A为该IFS的吸引子，即对任一LH(x)，有： 形象地说，如果试图找一个IFS，使其吸引子与某个给定的集合相似或相近，我们必须在给定的图像空间中找一组收缩仿射变换，使得用给定集合分别对各个收缩映射变换后结果，即其自身的各个小“拷贝”能够拼贴成一个集合，并且使该集合在Hausdorff距离下尽量地接近于原给定集合，我们就可以用这样一组仿射变换的系数作为原集合的编码。在这里，拼贴定理可以理解为集合并的过程，而IFS吸引子与原给定信之间的误差由拼贴的过程确定，并且由拼贴定理定量地给出了。2.3 分形的自相似性在分形编码过程中，各域块之间其实并不是相互独立的，本身存在着相似性。利用好这种相似性，有时能加快编码的速度。定义1 设A，B是大小为mm的两域块，各象素点上灰度值分别以ai，bi（i=1，2，mm）表示，为任意实数，则定义： 为域块A对B的相似度，记为。 在分形编码中，我们关心的是使最小时的情况。通过分别对和求偏导，可以求得，当 时，=0；否则 定义2 设域块A对B的相似度为，若，为使最小的实数，则称此距离为域块A对B的最大相似度，记为dmax(A,B)。第三章 分形动画与自然场景生成算法的实现 许多分形算法自身就显现出动画的特征，例如DLA模型，它是靠粒子的 运动寻找生长点的方法来实现绘图的，你已经看到该图形的绘制过程实质上就是一个生长的过程，非常接近于自然的状态。而针对于其他分形算法来实现动画也不是一件很难的事。由于分形自身的特点，其算法内部的参数变化会直接影响图形的外观，而且外观对参数的变化有时是十分敏感的，当我们在程序中让某些参数进行连续变化时，程序所生成的图形过程就会产生动画的效果。分形树的递归算法3.1分形动画-摇曳的树在递归分形树程序中有几个关键的参数可以明显地改变分形树的形态，可以考虑作为实现动画的参数，比如控制弯曲角度参数，该参数值越大其树的弯曲程度也越大，如果我们连续变化该值，便可以使树的弯曲程度连续变化，从而产生动感。将参数的值作为递归过程drawLeaf()中的一个形式参数，并在run()中反复重画，以实现多次调用递归程序drawLeaf() ，同时将参数在每次调用这个过程时赋值。当然，每次赋给参数的值是不同的，且是连续变化的。 在计算机上实现动画时，程序中使用了双缓存技术，即创建两个缓冲区，一个用来绘制图形，一个用来显示图形，当在显示图形缓冲区中删除旧图的同时，在绘制图形缓冲区中画新图，随后由显示图形缓冲区调出此图，从而提高了显示速度。程序运行图如下：3.2 分型自然景物模拟算法 分形是大自然的几何学，分形几何在模拟自然景物方面有其独到之处。如果说传统的几何学在模拟自然的时候使用拼装的方法硬画上去的，那么分形几何的方法则是利用规则进行递归或迭代而自动生成的。绘制云层，天空和山的具体实现过程3.2.1 递归算法生成分形树（1）基本的分形树递归算法实现首先，以图3 作为分叉树的生成元，利用递归算法生成分叉树，实际上就是将这个生成元在每一个层次上不断重新分裂的过程。图3 基本分叉树的生成元设A点坐标为(x, y),B点坐标为(x0 ,y0 ),C点坐标为 (x1,y1 )，D点坐标为 (x2 ,y2 ),L为树干的长度,为枝干与主干的夹角。绘制主干AB,即(x, y)(x 0 ,y0 )的直线。计算C点坐标，L=2L/3，x1 =x0 +Lcos，y1 =y0 Lsin。计算D点坐标，L=2L/3，x1 =x0 +Lcos()，y1 =y0 Lsin()。将步骤中x0 x,y0 y,x1 x0,y1 y0 ,再绘制(x,y)(x0,y0)的直线,即生成分枝BC。将步骤中x0x,y0y,x2x0,y2y0,再绘制(x,y)(x0,y0) 的直线，即生成分枝BD。重复执行步骤,直到完成递归算法。算法生成效果：由于角的不同，递归算法所生成的树形效果也不同。设定a= 30O,递归10次时,上述算法所产生的分形效果如图4 所示。图4 基本的分形树递归算法所生成效果从上图可以看出，该递归算法所产生的分形树效果，是对自然树的一种标准（或者理想）状态的模拟，具有很强的对称性。由于真实世界中植株个体时刻会受到各种外界因素（如光照强度、土壤环境、大气温度、大气湿度、认为干预等）的影响，其个体的形状千变万化。即使在以上这些因素均完全相同的情况下，由于自然风的物理效应也会使植株体时刻产生不同的形变。所以，这样的算法只是对植株体的理想化模拟仿真，如果要使其具有真实的效果和较强的应用价值，需对其作进一步的改进工作。（2）改进的分形树递归算法原理如果将分叉树的生成元作一些改进，即在主干上再增加两个分叉，成为如图5所示的生成元，最终树的形态会发生较大的变化。图5 改进的分叉树生成元设A点坐标(x, y),B点坐标为(x0 ,y0 ),C点坐标为(x1,y1),L为树干的长度,S1为右侧枝干的长度,S2为左侧枝干的长度。绘制主干AB,即(x,y)(x0,y0)的直线。计算C点坐标,并在此点生成左右两个分枝CD和CE。在CB之间进行第步的分形。在分枝CD和CE上也进行第步的分形。重复进行，直到完成递归次数。算法生成效果：由于在算法中，对分形树左右分枝的长度作了区别，对左右分枝与主干的夹角进行了递归改变，那么基于该算法生成的分形树，它的形态很贴近自然树的动态形态。图6展示了该算法所产生的