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

计算机图形学课程设计题目名称:分型理论及其在动画中的应用班级：郑州大学生兼职学号：学生姓名:天空乐园2012年1月分型理论及其在动画中的应用摘要分形作为可视数学的一个新支，是当今科学前沿最有影响的概念之一，同时建立在分形几何学基础之上的分形艺术创作也极大地丰富了现阶段的艺术创作手段。本文对目前文献中基于分形的自然景物的几种常用描述方法，即递归法、L-系统法、IFS法进行了系统的理论分析得出以下结论：(1)IFS法适用面广，不仅模拟的景物效果好，而且可用于图像的压缩等许多领域；L-系统法更适合模拟植物的生长过程；递归法的思想贯穿在基于分形模拟的各种方法中。(2)对具有严格自相似、且精细结构度高的景物，递归法最适合；对生长规律具有较强的拓扑性的景物，L系统模拟效果好；对具有较多细节结构的景物，IFS系统模拟效果较好，逼真度高。(3)3种方法的模拟效果与具体的自然景物的性质有关景物越复杂,说明其越具有更多的精细结构、自相似越强，3种方法的模拟效果就越好，逼真度就越高。关键词分形动画、L-系统法、迭代函数系统(IFS)法、受限扩散凝聚(DLA)法、粒子系统法引言分形理论创始于二十世纪七十年代初期,其研究对象为自然界和现实生活中广泛存在的非规则而具有自相似特性的几何形态。我们所生活的自然界是丰富多彩的,天空中飘浮着的变幻莫测的云团,辽阔无际的地貌,海洋上风起云涌时的巨大海浪,各种犬牙交错的海岸线,以及身边无处不在的花草、树木等等。对于这么多的千变万化的不规则的形态,多少年来,人们习惯于用传统的欧几里得几何理论来描述,主要是用直线段、圆弧、平面及曲面等手段来对他们进行分析。这种用规则的几何理论去描述非规则的几何形态所得到的结果应该说是有巨大差异的,有时甚至是不可能的。一方面是自然界中无处不在的非规则几何形体,另一方面是很难确切地来描述它,这给带来了极大的困惑。分形几何学的创立,为准确地描述非规则的几何形态提供了强有力的工具。“分形”是由BenoitB.Mandelbrot在1975年首次提出的,其原义是“不规则的、分数的、支离破碎的”物体,这个名词是参考了拉丁文fractus(破碎的)后造出来的,它既是英文又是法文,既是名词又是形容词。1977年,他出版了第一本书《分形:形态、偶然性和维数》(Fractal:Form,ChanceandDimension),标志着分形理论的正式诞生。5年后,他出版了著名的专著《自然界的分形几何学》(TheFractalGeometryofNature),至此,分形理论初步形成。目前,分形是非线性科学中的一个前沿课题,在不同的文献中,分形被赋予不同的名称,如“分数维集合”、“豪斯道夫测度集合”、“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,SolitonsandFractals)”和“分形学(Fractals-AnInterdis-ciplinarJournalonthecomplesGeometryofNature)”先后于1991年和1993年正式创刊。许多问题仍然需要深入的研究,诸如如何判断一个对象是分形或多重分形、分形维数的物理意义、分形的动力学机制、分形重构问题、关于Julia集和Mandelbrot集的问题,以及其他如随机多重分形的数学问题、分形曲线的导数问题、分维计算的方法特别是由混沌时序计算分维的可信度问题、多重分形的热力学、相变实质及相变普适性划分判据问题、分形的小波分析及小波变换产生分形的问题、生物膜的分形结构及其与细胞膜病变的关系、原子分子的分形问题包括量子混沌、胖分形(fatfractal)及重正化混沌(renormchaos)问题、自组织临界现象及负幂律问题、图像的分形压缩问题等。3.研究分形的一般方法在自然形成的非规整结构以及在生产实践与科学现象中所涉及的复杂图形中,分形的概念正在得到越来越广泛的应用。分形也即指这些非规则体中的无规程度可以用一非整数维数来加以描述。通过分形结构分析,对这些看起来复杂不规则形态提供了一种数学框从而得以定量描述。而分形结构分析中最具重要性的特征参数即分形维数(简称分维)。一般认为,分维对应于分形体的不规则和复杂性或空间填充度量程度。分维不同则反映了聚集体结构所具有的开放程度。利用分形方法模拟植物形态结构的方法主要有L-系统法、迭代函数系统(IFS)法、受限扩散凝聚(DLA)法、粒子系统法等。3.1迭代函数系统法IFS(IteratedFunctionSystem)法是分形绘制的典型方法。它是Hutchinson(1981)和Barnsley(l985)提出并发展起来的一种研究分形的数学方法,IFS的基本思想并不复杂,它认定几何对象的全貌与局部,在仿射变换的意义下,具有自相似结构。几何对象的整体被定义以后,选定若干仿射变换,将整体形态变换到局部,并且这一过程可以迭代地进行下去,直到满意的造型。其理论依据及应用效果是基于著名的压缩映射不变集定理和拼帖定理。IFS可以定义为由一组满足一定条件的映射函数Wi(例如压缩的仿射变换)及一组变换发生的概率Pi,组成:nIPiWiIFS,2,1|,,利用IFS生成植物图像的方法是对初始植物图像按照己知概率选择函数而实施的一种迭代变换。迭代函数系统用很少的数据就能完成图像的模拟,在图像压缩方面显示了很大优势,也是一个很诱人的研究领域。IFS主要用于分形绘制和图像压缩。这方面的研究主要集中在利用IFS码进行图像绘制和求已知图像的IFS码,以及图像压缩。3