分型理论及其在动画中的应用.doc

计算机图形学课程设计题目名称: 分型理论及其在动画中的应用班 级：郑州大学生兼职学 号：/学生姓名: 天空乐园 2012 年 1 月分型理论及其在动画中的应用摘要分形作为可视数学的一个新支，是当今科学前沿最有影响的概念之一，同时建立在分形几何学基础之上的分形艺术创作也极大地丰富了现阶段的艺术创作手段。本文对目前文献中基于分形的自然景物的几种常用描述方法，即递归法、L-系 统法、IFS法进行了系统的理论分析得出以下结论：(1) IFS 法适用面广，不仅模拟的景物效果好，而且可用于图像的压缩等许多领 域；L-系统法更适合模拟植物的生长过程；递归法的思想贯穿在基于分形模拟的各 种方法中。 (2) 对具有严格自相似、且精细结构度高的景物，递归法最适合；对生长规律具 有较强的拓扑性的景物，L系统模拟效果好；对具有较多细节结构的景物，IFS系统 模拟效果较好，逼真度高。 (3) 3种方法的模拟效果与具体的自然景物的性质有关景物越复杂,说明其越具有更多的精细结构、自相似越强，3种方法的模拟效果就越好，逼真度就越高。关键词 分形动画、L- 系统法、迭代函数系统(IFS)法、 受限扩散凝聚(DLA)法、 粒子系统法引言分形理论创始于二十世纪七十年代初期,其研究对象为自然界和现实生活中广泛存在的非规则而具有自相似特性的几何形态。我们所生活的自然界是丰富多彩的, 天空中飘浮着的变幻莫测的云团,辽阔无际的地貌,海洋上风起云涌时的巨大海浪, 各种犬牙交错的海岸线,以及身边无处不在的花草、树木等等。对于这么多的千变万化的不规则的形态,多少年来,人们习惯于用传统的欧几里得几何理论来描述,主要是用直线段、圆弧、平面及曲面等手段来对他们进行分析。这种用规则的几何理论去描述非规则的几何形态所得到的结果应该说是有巨大差异的,有时甚至是不可能的。一方面是自然界中无处不在的非规则几何形体,另一方面是很难确切地来描述它, 这给带来了极大的困惑。分形几何学的创立,为准确地描述非规则的几何形态提供了强有力的工具。“分形”是由Benoit B.Mandelbrot 在1975年首次提出的,其原义是“不规则的、分数的、支离破碎的”物体,这个名词是参考了拉丁文fractus (破碎的)后造出来的,它既是英文又是法文,既是名词又是形容词。1977年,他出版了第一本书 分形:形态、 偶然性和维数( Fractal :Form ,Chance and Dimension) ,标志着分形理论的正式诞生。 5年后,他出版了著名的专著自然界的分形几何学( The Fractal Geomet ry of Nature) ,至此,分形理论初步形成。目前,分形是非线性科学中的一个前沿课题 ,在不同的文献中,分形被赋予不同的名称 ,如“分数维集合”、“豪斯道夫测度集合”、“S集合”、“非规整集合”、以及“具有精细结构集合”等等。一般地可把分形看作大小碎片聚集的状态,是没有特征长度的图形和构造以及现象的总称。由于在许多学科中的迅速发展,分形已成为一门描述自然界中许多不规则事物及现象的规律性的学科。分形具有的两个重要特征在于自相似性或自仿射性与标度不变性。具有严格自相似性的形体称为有规分形,而只是在统计意义下的自相似性的分形则称为无规分形。分形是非线性系统中通过自组织形成的时空有序结构。分形与混沌关系密不可分,你中有我,我中有你,而含义各不相同。要阐明它们关系的区别是十分困难的,人们常常把它们放在一起加以解释。随着分形理论的产生与发展,逐步地形成了分形几何学,这是近几十年才发展起来的数学的一个分支,又称为非欧氏几何学,与具有2000多年历史的欧氏几何学相比,它们的差异是十分明显的,如下表所示。1. 分形理论的产生和发展分形的发展大致经历了三个阶段:第一阶段是从 1967 年1981 年, 即分形的产生和起步阶段。在这一阶段的标志性人物是 B.B.Mandelbrot 和后来被称为“分形之父”的芒德布罗。可以说分形始于前者, 而后者将其提高到了分形几何的高度。 芒德布罗在其著作中总结了一系列在 19 世纪后期与 20 世纪初曾困惑大量数学家的病态曲线或几何体,他将这一类病态几何体命名为“分形”,并指出它们的共同特点是具有结构上的自相似性与无特征尺度, 它们满足放大与收缩变换下的不变性, 即标度不变性,而它们的维数可以用豪斯多夫维数来表示。进一步,他又将这些几何体与自然界和社会学中的大量现象相联系,如布朗轨迹、流体湍流、不规则的地形地貌、多变的气象记录、动荡的股市和棉花价格的波动；同时又将传统的数学研究方法与计算机图形学相联系, 其最出色的工作就是将朱利亚(G.Julia,1893- 1978)和法图(P.L.Fatou,1878- 1929)在 1918- 1920年研究复迭代所生成的各种朱利亚集总结成一个美丽无比的芒德布罗集。这个阶段可称为分形几何的初创阶段,这时的“分形几何”还只是一种引人赞赏的数学图画,它尚未与真实的自然界相联系。转折点发生在 1981 年 DLA模型的诞生, 从而开创了“分形”发展的第二个阶段。从 1981 年到 1987 年可称为分形发展的第二阶段, 也是它发展的黄金时代。两位美国科学家 T.A.Witten 和 L.M.Sander 于1981年在物理评论快报上发表了一篇论文,文中介绍了他们在微机上所作的一个模拟实验,即将单个粒子在二维方形点阵上作随机行走,然后在点阵的中心处进行凝聚,这时在计算机屏幕上奇迹般地出现了在自然界中最为人们所熟知的树枝状斑图,他们把这称为扩散置限凝聚模型,简称为 DLA模型；同时对这些斑图进行的计算表明,它们是具有自相似性的几何体, 满足标度不变性,它们的维数是一个普适的常数,其值约等于 1.66, 因此这类斑图应该是一种分形。这篇论文的发表引起了大量科学家的兴趣,验证 DLA模型的实验在许多领域像雨后春笋般地涌现。仅仅几年的时间,一连串的实验报道及成果就从各个领域传出, 这就奠定了 DLA模型的科学价值, 同时也开创了研究“分形生长”的热潮。生长问题本来就是科学界的热门话题, 因为它涉及到生命演化、万物生长、物质凝聚和材料断裂等多门学科的内容, 而它又是一个非线性和非平衡态的进化过程, 长期以来在理论上几乎没有什么进展, 而“分形”的兴起与发展给这一古老命题带来了一线曙光, 因此大批的数学、物理、化学、生物、材料科学和地质等学科的学者们都进入了“分形”的研究领域。 他们的进入使“分形”在 80 年代中期空前活跃,促使“分形”学科逐步地向深度与广度方向发展。综上所述,可以看出以新颖的分形概念与传统科学的结合促进了整个学科领域的发展, 同时也促进了“分形”自身的发展，这就是分形发展第二阶段的特征。从 1988 年至今,“分形”入了它的第三个发展阶段。这是一个深入攻坚与开拓应用的阶段。在这段时间里,分形进一步得到了迅速的发展和应用。2. 分形的基本概念到底什么是分形呢? 开始时,Mandelbrot 把那些 Hausdorff维数不是整数的集合称为分形。按这个定义,某些看来应该是分形成员的,例如著名的 Pcano 曲线, 就被排除在外, 于是 Mandelbrot 又修改了原来的定义, 说分形是那些局部和整体按某种方式相似的集合, 这是目前关于分形定义普遍被接受的说法。研究分形, 似乎如同研究生命一样,先弄清楚定义再研究,还是在研究、发展之中给出科学的定义, 看来还是后者更有道理。到目前为止,分形尚无最后的定义。对分形的定义,可以用生物学中对“生命”定义的办法。“生命”是很难定义的, 但却可以给出一系列生命对象的特征, 例如繁殖能力, 运动能力。除了有些对象例外,大部分情形都能因此而得到分类,于是就不会因为暂时没有严格的定义而停步不前。对分形似乎也宜于给出一系列特征性质, 当集合具备这些性质时就可以认为是分形；当因此而排除掉一些自己的同类时, 再作特殊的研究。按这种观点，称集合 F 是分形, 是指它具有下面典型的性质:(1)F 具有精细的结构, 也就是说, 在任意小的尺度下, 它总是有复杂的细下;(2)F 是不规整的, 它的整体与局部都不能用传统的几何语言来描述;(3)F 通常有自相似形式, 这种自相似可以是近似的或统计意义的;(4)一般地, F 的某种定义之下的分形维数大于它的拓扑维数;(5)在大多数令人感兴趣的情形下, F 以非常的方法确定, 可能由迭代过程产生。分形是自然形态的几何抽象, 如同自然界找不到数学上所说的直线和圆周一样,自然界也不存在“真正的分形”。只要注意到分形包含一个无穷小尺度的内涵,便可以知道自然形态只是停留在一定层次内可以合理地按分形模型来考虑。分形几何学的主要内容可以分为两部分:线性分形与非线性分形。线性分形理论的基本观点是维数的变化是连续的 ,研究对象具有自相似性和非规则性。线性分形又称为自相似分形它研究的所有方向上以同一比率收缩或扩展一个几何图形的线性变换群下的图形的性质 ,在一定范围内 ,由一个分形维数就可以加以描述。线性分形又可分为有规分形和无规分形两类非线性分形研究在非均匀线性变换群或非线性变换群下的图形的性质 ,它可以分为三类:自仿射分形(非均匀线性变换群)、(自反演分形非线性变换群)和自平方分形。另外,按数学性质,分形尚可以分为线分形、面分形与体分形。值得一提的是 ,分形理论处于不断发展之中 ,自然科学领域(如物理、 化学、 地球物理学及生物学等)中的分形学术论文不断增加 ,社会科学领域涉及分形的论文和书籍也越来越多。有关分形的国际会议及各种专题讨论会有增无减。国际学术刊物“混沌、 孤子和分形(Chaos ,Solitons and Fractals)” 和 “分形学( Fractals - An Interdis - ciplinarJournal on the comples Geometry of Nature)” 先后于1991 年和1993 年正式创刊。许多问题仍然需要深入的研究,诸如如何判断一个对象是分形或多重分形、分形维数的物理意义、分形的动力学机制、分形重构问题、关于J ulia 集和 Mandelbrot 集的问题 ,以及其他如随机多重分形的数学问题、分形曲线的导数问题、分维计算的方法特别是由混沌时序计算分维的可信度问题、多重分形的热力学、相变实质及相变普适性划分判据问题、分形的小波分析及小波变换产生分形的问题、生物膜的分形结构及其与细胞膜病变的关系、原子分子的分形问题包括量子混沌、胖分形(fat fractal)及重正化混沌( renormchaos)问题、 自组织临界现象及负幂律问题、 图像的分形压缩问题等。3. 研究分形的一般方法在自然形成的非规整结构以及在生产实践与科学现象中所涉及的复杂图形中,分形的概念正在得到越来越广泛的应用。分形也即指这些非规则体中的无规程度可以用一非整数维数来加以描述。通过分形结构分析,对这些看起来复杂不规则形态提供了一种数学框从而得以定量描述。而分形结构分析中最具重要性的特征参数即分形维数(简称分维)。一般认为,分维对应于分形体的不规则和复杂性或空间填充度量程度。分维不同则反映了聚集体结构所具有的开放程度。利用分形方法模拟植物形态结构的方法主要有 L- 系统法、迭代函数系统(IFS)法、受限扩散凝聚(DLA)法、粒子系统法等。3.1迭代函数系统法IFS (Iterated Function System)法是分形绘制的典型方法。它是Hutchinson(1981)和 Barnsley(l985)提出并发展起来的一种研究分形的数学方法,IFS的基本思想并不复杂,它认定几何对象的全貌与局部,在仿射变换的意义下, 具有自相似结构。 几何对象的整体被定义以后,选定若干仿射变换, 将整体形态变换到局部, 并且这一过程可以迭代地进行下去, 直到满意的造型。其理论依据及应用效果是基于著名的压缩映射不变集定理和拼帖定理。IFS可以定义为由一组满足一定条件的映射函数 Wi(例如压缩的仿射变换)及一组变换发生的概率 Pi, 组成:, 利用 IFS生成植物图像的方法是对初始植物图像按照己知概率选择函数而实施的一种迭代变换。迭代函数系统用很少的数据就能完成图像的模拟, 在图像压缩方面显示了很大优势,也是一个很诱人的研究领域。IFS主要用于分形绘制和图像压缩。这方面的研究主要集中在利用 IFS码进行图像绘制和求已知图像的 IFS码,以及图像压缩。3.2受限扩散凝聚法受限扩散凝聚(DLA)法是美国科学家 Witten 和 Sander 提出的, 其基本方法是:在一个平面网格上选定一个静止的微粒作为种子, 然后在距种子较远的格点上产生一个微粒, 令微粒沿网格上下左右的方向随机行走。如果该微粒在行走过程中与种子相碰, 就凝聚在种子上; 如果微粒走到边界上, 就被边界吸收而消失。 如此重复上述步骤, 就会以种子为中心形成一个不断增长的凝聚集团, 利用 DLA或其修改的模型可以对部分植物的形态结构进行计算机模拟, 如植物根系的生长过程模拟和海藻类植物的形态结构模拟等。DLA模型主要用于模拟各种分形生长和凝聚现象。3.3粒子系统法粒子系统法的基本思想是用大量的、具有一定生命的粒子图元来描述自然界不规则的模糊景物。每个粒子在任一时刻都具有随机的形状、大小、颜色、透明度、运动方向和运动速度等属性, 并随时间推移发生位置、 形态的变化。每个粒子的属性及动力学性质均由一组预先定义的随机过程来说明。粒子在系统内都要经过“ 产生” 、“ 活动” 和“ 死亡” 这三个具有随机性的阶段, 在某一时刻所有存活粒子的集合就构成了粒子系统的模型。粒子系统适合用来模拟山、 水、 树丛、 草地等模糊、 随机图像。3.4 L- 系统美国植物学家 Arestid Lindenmayer 提出了著名的 L- 系统法, 成为植物生长建模的主要方法之一。L- 系统是一种字符串重写系统, 通过对植物对象生长过程的经验式概括和抽象, 构造公理与产生式集, 生成字符发展序列, 表现植物的拓扑结构。它以形式化的语言描述植物的结构和生长, 在语言的终结符与植物结构对应时, 由文法生成的句子代表植物, 而句子生成的中间过程是植物生长发育的过程。最简单的 L- 系统简称为 D0L- 系统, D表示确定性, 0 表示与上下文无关。随机 L- 系统克服了确定性 L- 系统只能生成规则分形图形的局限,可构造随机的植物拓扑结构。参数化 L- 系统使 L- 系统能够模拟时延信息。Smith 等人将 L- 系统引入到植物模拟的分枝拓扑研究中, 并称之为文法构图(Graftal)方法。L- 系统法的特点:它能简洁地描述植物的拓扑结构, 例如枝条和花序结构。具有定义简单、结构化程度高、易于实现等特点。4. 分形几何在图形生成技术中，在计算机内定义、表示一个三维物体的方法主要有：体素构造法、边界表示法、八叉树法等方案。这些方法普遍采用的都是欧氏几何方法，即表示的物体具有平滑的表面和规则的形状，可由方程来描述。但自然景物，如山脉和云，是不规则或粗糙的，欧氏方法便不能真实地模拟这些物体。分形几何则提供了一种描述这种不规则复杂现象中的秩序和结构的新方法。分形几何表示的物体具有一个基本的特征：无限的自相似性。所谓无限的自相似是指物体的整体和局部之间细节的无限重现。例如一棵参天大树与它自身上的树枝及树枝上的枝杈，在形状上没什么大的区别，大树与树枝这种关系在几何形状上称之为自相似关系；我们再拿来一片树叶，仔细观察一下叶脉，它们也具备这种性质；动物也不例外，一头牛身体中的一个细胞中的基因记录着这头牛的全部生长信息；还有高山的表面，您无论怎样放大其局部，它都如此粗糙不平等等。这些例子在我们的身边到处可见。分形几何揭示了世界的本质，分形几何是真正描述大自然的几何学。基于分形物体的无限自相似性，分形物体的描述又包含以下两个方面内容：一是分形维数， 二是生成过程。分形维数，又称分数维数，是一个数字，用来描述物体细节的变化， 这也是 “分形” 这一名称的由来。与欧氏维数不同，这一数字不一定是整数！在下面的程序设计里，取的是黄金分割点0.618。 生成过程指的是为产生物体局部细节指定一重复操作。例如，在确定性（非随机）自相似分形几何构造方法中，开始时，给定一个初始生成元的几何形状，然后将初始生成元的每部分用一模型替代，称为生成元，最后通过多次迭代生成分形物体。分形方法在模拟多种自然现象时业已证明是有效的。在图形学应用中，分形表示用于模拟岩层、云、水、树，及其他植物、羽毛、表皮和各种表面纹理等。在其他学科中，分形模型可以用于星体分布、河岸、月球陨石坑、人口资源利用等。甚至在艺术领域，分形几何也显示出非凡的作用。5. 分形技术在计算机动画中的应用基于传统欧几里德几何学基础之上的艺术造型是对有形自然界中各种有序的、稳定的、平衡的和确定的物象进行描绘，凭借这种几何学对事物的理解和当代各种人工技术手段的发展人类曾创造出伟大而美好的视觉空间。随着科学技术水平的不断提高及人们认知水平的不断发展，人们逐渐感觉到用传统几何并不能描述大自然中所有的对象，如海岸线、山形、河川、岩石、树木、森林、云团和闪电等等，需要新的几何学来解释大自然中无序的、不稳定的、非平衡的和随机的状态的物象，分形几何便应运而生。分形作为可视数学的一个新支，是当今科学前沿最有影响的概念之一，同时建立在分形几何学基础之上的分形艺术创作也极大地丰富了现阶段的艺术创作手段。分形图形的研究和使用为现代动画技术的发展起到了推波助澜的作用，提高了运动的复杂性、画面的真实性、操作的便捷性，克服了以往传统绘画艺术仅靠静态图像来传情答意的局限性。分形艺术作品本身所具有的无穷细节，及其在表现自然景物方面的能力，使人们不能不设想若将其运动起来，会产生意想不到的视觉效果。分形几何学用来描述那些不规则而欧氏几何又无法描述的几何现象和物体。通过研究分形与自然的关系，向人们展示了分形广泛的存在于我们身边，用分形来描述树和山等复杂事物。目前,被誉为大自然的几何学的分形理论,已成为现代数学的一个新分支，但其本质却是一种新的世界观和方法论。它与动力系统的混沌理论交叉结合，相辅相成。它承认空间维数的变化既可以是离散的也可以是连续的,因而拓展了视野。分形技术提出后,在世界上引起了广泛重视，在数学、物理、化学、生物、经济学及计算机科学领域展开了分形理论、技术和应用的研究，逐渐发展并完善了分形理论体系。近年来,计算机图形学在蓬勃发展和广泛应用，传统的欧氏几何学为它提供了有力的数学模型，在描述一些抽象图形或人造物体的形态时是非常有力的。但是,随着对CAD逼真程度要求的不断提高， 特别是计算机图形学的一个重要分支自然景物模拟的迅速发展，使得传统图形学越来越显得力不从心。将分形几何学引入到计算机图形学中，为非规整形状图形的计算机描述和处理提供了有利工具，成为目前研究世界物质模型的一个扩展。借助于分形的计算机生成，从少量的数据生成复杂的自然景物图形，使我们在仿真模拟方面前进了一大步。分形以其独特的手段来解决整体与部分的关系问题，利用空间结构的对称性和自相似性,采用各种模拟真实图形的模型，使整个生成的景物呈现出细节的无穷回归的性质，丰富多彩,具有奇妙的艺术魅力。所生成的景物中,可以有结构性较强的树、山峰，也可以是结构性较弱的火、云及烟等。生成图形的关键是要有一个合适的模型来描述对象，根据所选择的分形造型的模型不同，产生分形图形的方法可分为如下4类:基于L-系统的分形图形；迭代函数系统IFS方法； 粒子系统模型方法；随机插值法。随着计算机图形学和计算机硬件的不断发展,人们已经不满足于仅仅生成高质量的静态场景,于是计算机动画就应运而生。事实上计算机动画也只是生成一幅幅静态的图像,但是每一幅都是对前一幅做一小部分修改,如何修改便是计算机动画的研究内容,这样,当这些画面连续播放时,整个场景就动起来了。早期的计算机动画灵感来源于传统的卡通片,在生成几幅被称做“关键帧”的画面后,由计算机对 2 幅关键帧进行插值生成若干“中间帧”,连续播放时2个关键帧就被有机地结合起来了。计算机动画内容丰富多彩,生成动画的方法也多种多样,比如基于特征的图像变形、二维形状混合、轴变形方法、三维自由形体变形( FFD , Free2F ormDeformation) 等。近年来人们普遍将注意力转向基于物理模型的计算机动画生成方法。这是一种崭新的方法,该方法大量运用弹性力学和流体力学的方程进行计算,力求使动画过程体现出最适合真实世界的运动规律。然而要真正到达真实的运动是很难的,比如人的行走或跑步是全身的各个关节协调的结果,要实现很自然的人走路的动画,计算方程非常复杂和计算量极大,基于物理模型的计算机动画还有许多内容需要进一步研究。图形化的用户界面能够大大提高软件的易用性,在 DOS时代,计算机的易用性很差,编写一个图形化的界面要费去大量的劳动,过去传统的软件中有60%的程序是用来处理与用户接口有关的问题和功能的。进入80年代后,随着Xwindow标准的提出,苹果公司图形化操作系统的推出,特别是微软公司Windows 操作系统的普及,标志着图形学已经全面融入计算机的方方面面。如今在任何一台普通计算机上都可以看到图形学在用户接口方面的应用。操作系统和应用软件中的图形、动画比比皆是,程序直观易用。很多软件几乎可以不看任何说明书,而根据它的图形或动画界面的指示进行操作。6. 对云彩进行分形模拟在实际计算中，经常遇到只提供一些离散数据的函数，要计算函数在其它点上的值或讨论函数的性质，通过的方法是构造一个简单的函数F(x)使之通过已知的数据点，用F(x)的值和性质来代替上述函数的值和性质，这就是插值法；而传统的插值函数，对相邻的两插值点之间只能用直线或光滑曲线连接，这样得不到两点之间的局部变化特证。然而实际情况是，在两相邻信息点之间并不是线性变化的或光滑过度的，而是存在局部变化的特征。如:山地的轮廓线、大气压强的变化规律、股票价格的变化规律、浮云的变化无常等。事实上，用分形插值就可以得到两相邻信息点之间的局部变化特征，从而使得插值结果更加符合实际。运用上述分形插值原理，下面对自然界云彩的不规则形态进行分形模拟。云属于气体现象，其外观形状极不规则，没有光滑的表面，而且极其复杂和随 意, 所以用经典的欧几里得几何学对其描述非常困难。考虑到分形理论,可以用分形 插值的方法生成模型的基础数据,通过转换得到云图纹理，实现蓝天白云效果图的绘制。自然云图的模拟，可以用二维空间的分形插值方法实现。由于自然界的彩云形状的不规则性主要反映在颜色变化的不连续性和随意性上，所以在对二维空间细化的过程中，利用分形插值算法不断对网格进行细化，同时得到细化的网格中的颜色值。得到四个小四边形，分别为AEMH、EBFM、FCGM 和GDHM。使用网格外的虚点，是因为在原始正方形边上的某一点(除正方形的四个角点外)只有三个相邻点，为了算法统一不得不补上一个虚点。换句话说,如果某一网格上的点有四个相邻点，就没有必要添加虚点。对虚点的处理，也可以采用其它方法，如随机地将正方形边界上的所有点都涂上颜色等。根据小正方形AEMH 四角点颜色的平均值，求出小正方形AEMH中点以及边中点的颜色；然后再沿用上述规则计算小正方形EBFM的中点及边中点的颜色，以此类推，计算小正方形FCGM,GDHM的中点和边中点的颜色。最后递归上一步骤。这样利用规则进行递归或迭代使正方形网格不断细化，直至达到预期的递归深度。虽然正方形初始点的颜色是随机赋予的，这并不说明正方形网格内的所有点是随机分布的。也就是说,通过采用分形插值算法，使得网格内相邻点之间建立一种联系，从而使生成体内部自然过渡；另外,通过递归可以使得生成体具有自相似和精细结构，这也是分形插值的优点。使用Java语言在二维网格下进行绘制可以得到想要的图形。该图有较强的真实感，可以在虚拟现实中得到广泛的应用。如果上述的结果绘制在x-y平面上，然后在z轴的正方向上,以正方形网格不同点 4 的颜色值对应长出不同的高度，从而产生出连绵起伏的山脉。7. 复平面神奇的迭代Mandelbrot 集合是 Mandelbrot 在复平面中对简单的式子进行迭代产 生的图形。虽然式子和迭代运算都很简单，但是产生的图形出现那么丰富多样的形 态及精细结构简直令人难以置信以至于不可思议。在传统几何学中难以找到如此简 单的规律隐藏着如此复杂而生动的例子。Mandelbrot 集合告诉我们自然界中简单的行为可以导致复杂的结果。例如，大型团体操中每个人穿的衣服只有几种颜色中的一种，每个人的动作也只是导演规定的几种之一。但是整体上可以显示出多种多样的复杂形态。7.1 Julia 集合在复平面上，水平的轴线代表实数，垂直的轴线代表虚数。每个 Julia 集合（有 无限多个点）都决定一个常数 ，它是一个复数。现在您在复平面上任意取一个点，其值是复数。将其代入方程中进行反复迭代运算： 就是说，用旧的 自乘再加上后的结果作为新的。再把新的作为旧的，重复运算。当你不停地做，你将最后得到的值有 3 种可能性：1. 值没有界限增加（趋向无穷）； 2. 值衰减（趋向于零）； 3. 值是变化的，即非 1 或非 2 。 趋向无穷和趋向于零的点叫定常吸引子，很多点在定常吸引子处结束，被定常吸引子所吸引。非趋向无穷和趋向于零的点是“Julia 集合”部分，也叫混沌吸引子。问题是我们怎样才能让计算机知道哪一个点是定常吸引子还是“Julia 集合”。 一般按下述算法近似计算： 其中：为最大迭代次数，为逃离界限退出 while 循环有两种情况： 第一种情况是： 属于这种情况的点相当于“1、值没有界限增加（趋向无穷）”，为定常吸引子,我们把这些区域着成白色。 第二种情况是： 属于这种情况的点相当于“2、 值衰减 （趋向于零） ”或“3、 值是变化的”， 我们把这些区域着成黑色。黑色区域图形的边界处即为“Julia 集合”。“Julia 集 合”有着极其复杂的形态和精细的结构。 黑白两色的图形艺术感染力不强。要想得到彩色图形，最简单的方法是用迭代 返回值 n 来着颜色。要想获得较好的艺术效果，一般对 n 做如下处理：其中：及为修正量。 获得的为 RGB 三基色，着色效果为周期变化，具有较强的艺 术感染力，而且等位线也蕴藏在周期变化的色彩之中。你可以想象得出，屏幕上顺序的试用每个像素点来反复迭代方程要花费很长的时间。一幅 1024768 屏幕尺寸的画面有 786432 个点。其中一些点在计算机上要反复迭代次数达 1000 次（取决于 Nmax 的取值）或更多次才放弃运算。运算产生一幅 Julia 集 合 需 要 花 费 很 长 的 时 间 ， 有 时 产 生 一 幅 做 海 报 用 的 大 图 像 时，如 102407680，要花几天的时间。当然使用高速计算机会缩短这个时间。7.2 Mandelbrot 集合将 Mandelbrot 集合和 Julia 集合联系在一起，Julia 集合有若干类型，都包含在 Mandelbrot 集合之中。Julia 集合中的 C 是一个常量，而 Mandelbrot 集合的 C 是由进入迭代前的 Z 值而定。迭代结果，Z 值同样有 3 种可能性，即：1. Z 值没有界限增加（趋向无穷）；2. Z 值衰减（趋向于零）； 3. Z 值是变化的，即非 1 或非 2。 Mandelbrot 集合是所有的朱莉娅集合的合并，Mandelbrot 集合的某个区域放大后就是这个点的 Julia 集合。Mandelbrot 集合有着一些很异国情调并且古怪的形状。你能不停地永远放大 Mandelbrot 集合，但是受到计算机精度的限制。Newton/Nova 分形 Newton 奠定了经典力学、光学和微积分学的基础。但是除了创造这些自然科学的基础学科外，他还建立了一些方法，这些方法虽然比不上整个学科那么有名，但已被证明直到今天还是非常有价值的。例如，牛顿建议用一个逼近方法求解一个方程的根。你猜测一个初始点，然后使用函数的一阶导数，用切线逐渐逼近方程的根。如方程 有六个根，用牛顿的方法“猜测”复平面上各点最后趋向方程的那一个根，你就可以得到一个怪异的分形图形。和平常的 Julia 分形一样，你能永远放 大下去，并有自相似性。牛顿分形图形中的颜色显示每个答案的种类及性质，即迭 代到目的地花费的时间，如图 6 所示： Paul Derbyshire 研究牛顿分形图形时，他把 Julia 集合的常值 C 加入进去改变了一下算法，并用同样的方法去估算 Z，逼近答案，产生奇特的并称之为“Nova”的分形图形。从理论上讲，不管多么复杂的事物形态，只要我们能够确定其IFS 代码就可以 借助计算机再现事物的复杂形态，而拼贴定理告诉我们，只要选适当的仿射变换，就可以使得迭代产生的目标图像与分形图任意接近，所以IFS方法在模拟分形图像方面具有极重要的意义。IFS 模型的动画仿真在 IFS 代码中，仿射压缩变换的作用是控制所生成的分形图的结构，也就是说，分形结构是由一组仿射变换决定的。由吸引子定理2可知， 只要仿射变换是压缩的，迭代函数系统所生成的分形图像（称为吸引子集或吸引子）总是存在的，而且是惟一的。因而我们可以通过有规律地调整控制IFS 代码值达到有目的地改变分形图的形状，实现分形动画仿真。引理 1：设 ( X , P) 是完备度量空间， IFS ( X : W 1, W 2KWn) 的压缩比为Cn，对参 数连续，这里P 是紧度量空间，则IFS 的吸引子A 相对于Hausdorff 距离 hp 对连续。引理说明，对于带参量的迭代函数系统（即仿射变换中再加进一个参数P），参数的小变化只会引起IFS 吸引子的小变化，因而可以通过调整变换参数达到连续控 制IFS 吸引子的目的，同时也可使图形间进行平滑地过渡，从而实现动画效果。为能得到一棵在风中摇曳的树，我们在该IFS模型中加风力的控制参数wind，由树的物理常识可知，风力对树枝的影响较大，而对树干的影响较小，因而对上面控制树木各部分的四个变换。8. 动画的计算机实现这里我们在JAVA 平台上，运用OpenGL的绘图及显示技术来实现随风而动的树木，其主要算法步骤如下： 选取迭代过程的初始点 ，确定迭代次数n。为保证迭代过程中所产生的点均落在吸引子内，初始点应选为吸引子中的点。 令，绘制动画中第一帧图像。为起点，以依据表2 中的IFS 代码，利用随机迭代法，产生概率随机数，在4个变换中选出一个变换，求出新的坐标，跌代次数加1。调用绘制像数点函数绘制分形树。以为起点再次利用概率随机数选定其中一个变换，进行迭代。直至迭代次数为n，此时便可得到一棵树的分形图。该步中产生概率随机数所用的Math。random()随机函数， 可利用伪随机发生器Rand()生成。 给出的增量，令，重复步骤（2）产生第二帧图像。 重复（3）产生第三帧、第四帧 ，直到最大风力值（该值可由作者在真实物理模型树的摆动范围内自定）。在动画的显示中，对于图像不太复杂，跌代次数n 不太高的分形图像，可以直接利用OpenGL提供的双缓存技术，调用函数glj.gljSwap()来创建过程动画，实现图像间的平滑显示。而对于图像的逼真性以及细节要求较高图像，跌代次数n 就必须相应较高，而此时绘制图像所耗费的时间也较长，为保证动画技术所要求的每秒显示的帧数，我们将OpenGL 提供的纹理贴图与双缓存技术结合使用，并且以JAVA 语言为平台，调用下列函数来更好地实现所有画面连续而平滑地显示，达到动感仿真效果8.1变形动画IFS代码对分形图的决定作用，以及引理1，以度量空间 0,1， 0,1 为 例，通过对“源”图像的仿射变换系数进行连续的线性插值，实现“源”图像到“目 标”图像的变形动画。仿射变换数目相同的两个分形图之间的变形这里我们通过连续调整枫叶的 IFS代码，实现一片叶子到一棵树的变形动画。由模拟枫叶和树的分形图以及两种植物的自身结构特点可知，要使整个变形过程显得更自然，中间的画面应该保证每个分支与主干相连，如果是树，树枝就应该长在树杆上，如果是枫叶，每个叶脉的分支就应该与主叶脉相连。不难得到，为满足这一条件，我们只要改变每个压缩仿射变换参数时，保持映射对应像平行四边形中的点一样不动即可，这样，当第一帧图像满足分支与主干相连时，以后每帧画面都会满足。根据以上分析，变形动画的算法步骤如下： 确定枫叶与树的 IFS 代码，中间帧数n，然后用目标图像与源图像相应的IFS 代码之差除以中途画面数n 计算出每幅画面到其下一幅的参数增量，记为da、db： 将增量加到前一帧 图对应的参数中得到第二帧图像的参量 由等式 及 得到第二帧中其余的两个参量 ,。重复步骤 2，得到第三帧、第四帧图像的IFS 代码。 利用 3。1 中的图形绘制与动画显示技术即可生成植物间的变形动画。 显示了由枫叶变形为树的几个计算机生成的帧画面。 如果想实现两个具有不同变换数目的分形图的变形动画，首先需要将变换较少 的分形图增加一些变换，直到两个IFS 仿射变换数目相同。所增加的变换可以复制 变换数目较少的IFS 的变换，这样可以保证分形图不变，然后运用上述的算法进行变形8.2植物生成模型 L 系统作为分形理论的一个典型实例是由美国的生物学家 ARISTID L 从植物学观点出发,于 1968 年提出的一套用以描述植物树木的系统。自然界中树木是常见的景物,其形状复杂,结构特征强,对其建模是很困难的。一般来说,为生成形态逼真的树木图形,简单的递归方法是不行的。系统可无限嵌套,具有高度简洁性和多级结构,为描述植物树木生长和增殖过程的形态和结构特征,提供了行之有效的理论与方法。L 系统又称为字符串替换法,这种方法的理论根据是利用分形可以由简单的图(生成元)迭代产生这一基本原理,因此可以用字符串表示生成元的构成(如组成的线 段数、转动的角度等) ,再把字符串迭代就能生成希望得到的分形图。L 系统是极其有趣的,第一,用这种方法能够生成许多经典的分形, 象 Von Koch 曲线、Peano 曲 线和 Hilbert 曲线等。第二,用它可以模拟植物形态,特别是像植物枝一样的比较复杂的树状分形。自然界中景物有着许许多多极其复杂的形状,如山、水、云、树、生物等,表面 看它们的生成过程有一定的盲目性,其实是很有规则的,即比例自相似性。对这些具有分形结构的物体,不断显微放大其任何部分,就会发现其不规则程度都是一样的, 这个性质称为比例性;按统计的观点,几乎所有的分形又是置换不变的,即它的每一部分移位、旋转、缩放等在统计的意义下与其他任意部分相似。这两个性质表明分形决不是完全的混乱,在不规则中隐藏着规则。 它同时暗示了自然界中一切形状及现 象都能以较小或部分的细节反映出整体的不规则性。以植物为例,不难推出其生长的一般模型。 一个茎杆破土而出,茎杆向四周长出一些小树枝,长出的地方称为节; 大多数小树枝上又长出一些更小的嫩枝,如此反复; 一个树木上所有各处都有相似的枝节性质。 为了叙述方便,首先作一下记号的约定。1) F :在当前方向向前走一步；2) + :向右(顺时针方向) 转一给定的角度 a ； - :向左(逆时针方向) 转一给定的角度 a ； : 把当前状态压栈(记录当前点的坐标及角度)； : 出栈(取最近一次压入栈内的信息, 同时修改栈指针) 。有了这些记号之后就可以用一个字符串来表示树的分枝结构。而实际的植物从根茎到顶,边缘有数不清的分枝,如果对每个分枝都逐一写出其字符串,无疑是极其繁琐的。借助分形理论,每个特定的植物都有其基本串,植物生长的过程可看作是对基本串的每个变量再用特定的分枝 模型加以替代,如此反