注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

亿能部落格---观察思维比思维本身更重要

我是回来地球补课的!

 
 
 

日志

 
 
关于我

光行者的存在不在于他们真的能唤醒人类或者改变人类,而在于人类世界走向几近崩溃的时候能够站出来建立一套持久永恒的生活模式。

网易考拉推荐

分形景物仿真综述  

2013-04-27 12:34:45|  分类: 分形启示录 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

摘要本文对国内外20多年来利用分形算法对自然景物进行计算机仿真的研究状况进行了文献综述。对分形理论的发展历程进行了简述,并对分形理论中的各种算法和技术在景物仿真中的应用进行了总结和展望。

关键词分形算法; 自然景物; 仿真

中图分类号:TP391.9 文献标识码:A

Overview of the Simulation of the Fractal Scene

Abstract: This paper reviewed the simulation of natural scenes based on fractal algorithm during the last more than 20 years. The developing processes of fractal theory were briefly summarized. And also the application of all kinds of fractal algorithm and techniques, which used in simulation of sense have been summarized and given a look in the future.

Key words: fractal algorithm; natural scenes; simulation

0 前言

在经典的欧氏几何中,我们可以用直线、圆锥、球体等这一类规则的形状去描述诸如墙、道路、建筑物等人造物体,这是因为他们本来就是根据欧氏几何的规则图形生成的。然而在自然界,却存在许多极其复杂的形状,如山,云,闪电,树木,星系分布,金融市场的价格浮动等等,它们不再具有我们早己熟知的数学分析中的连续、光滑等基本性质,很多是实时变化的[1],然而他们的研究对于航空航天、建筑、交通、气象及军事却都具有十分重要的意义[2]。因此,几百年来,人们为了找到一种行之有效的仿真建模方法而孜孜不倦的进行着研究。

20世纪70年代,分形几何学[1]的诞生,为模拟各种自然现象与自然景物注入了强大的生命力。

分形无处不在。分形学科的诞生,使得我们重新审视这个世界。当人们用分形的观点重新审视自然物时,发现自然界的各种各样自然形态本质上都具有分形的结构。例如,地学方面:海岸线,岛屿,国界,山谷,河流,路面等弯弯曲曲凹凸不平的形状;生物方面:人的肺,血管,人脑,表面形状,大多数树木花草地分岔结构[3];在宇宙方面:天体在宇宙空间中的分布,月坑的直径分布以及作为月坑成因地陨石和小行星的大小分布,空中的云块边界[4 5 6]雪花的表面;在物理化学方面:物体的表面由细微粒子集聚成的凝聚体,闪电,多孔吸附材料的表面,蛋白质高分子的结构……

1 分形理论发展概况:

分形理论的发展经历了一百多年的历史,1925年以前,人们认识到有几类典型的分形集:

1827年英国植物学家布朗用显微镜发现微细颗粒在液体中作无规则行走的布朗运动现象[1、8]

1883年Cantor构造了三分集[9]

1904年瑞典数学家H. Von Koch构造出雪花曲线,并尝试对它们与经典几何的差别进行描述和刻划。[16]

1919年豪斯道夫引入了维数的概念,为维数的非整化提供了理论基础。[9]

1918年法国数学家朱丽亚等人研究了复迭代。[1]

在这以后,人们对分形集的性质做了深入的研究,丰富了分形几何理论,维数理论进一步发展并日臻成熟,但研究仍局限于纯数学领域。

20世纪60年代,Manderbrot在研究雪花与自然界的海岸线、山、树等自然景象时,发现它们都具有细节的无穷回归的自相似性,为了定量地描述这种性质,他引入了分数维的概念,并系统、深入、创造性地研究了海岸线的结构、具强噪声干扰的电子通讯、月球的表面、银河系中星体的分布、地貌的生成的几何性质等典型的自然界中的分形现象,并取得了一系列令人瞩目的成果[9]

1967年,曼德尔布罗特在《科学》刊物上发表题为"英国海岸线有多长?统计自相似性与分数维数"的著名论文。

1973年,曼德尔布罗特在法兰西学院讲课时,他首次提出了分维和分形几何的设想[9]

1975年,曼德尔布罗特创造了分形(Fractal)一词,其原意具有不规则、支离破碎等意义,由于不规则现象在自然界是普遍存在的,因此分形几何又称为描述大自然的几何学。曼德尔布罗特先后出版了《分形对象》、《分形:形状、打Lid与维数》等专著。这标志着分形理论的建立[9]

从此以后,分形几何在各个领域的应用取得全面发展,并形成独立学科。Manderbrot将前人的研究结果进行总结,集其大成,第一次系统地阐述了分形几何的思想、内容、意义和方法,从而把分形理论推进到迅速发展的新阶段。

80 年代中期开始分形热了成了科学界叫得最响的名词吸引了几乎所有领域科学家和社会工作者的注意有关分形出版了上百部专著在国际期刊上发表了几千篇专业论文美国物理学家惠勒J.A.Wheeler 说明天谁不熟悉分形谁就不能被认为是科学上的文化人。

分形打开了一个完全崭新和令人兴奋的几何学大门。这一新的数学领域,触及到我们生活的方方面面,诸如自然现象的描述,电影摄影术、天文学、经济学、气象学、生态学等等。它的应用是如此广泛,它的特性是如此迷人。我们拥有的这个新几何,甚至可以描述变化的宇宙。站在这个巨人的肩膀上,我们可以实现许多原来被我们视为奇异或是不可能实现的东西,不觉中人们感叹原来世界可以这样。

2 分形几何与自然景物仿真的关系

寻求能准确地描述客观世界中各种现象与景观的数学模型,并逼真地再现这些现象与景观,是图形学的一个重要研究课题。[8]

伽利略曾宣称,"自然界伟大的书是用数学语言写成的",而且补充说,"其特征为三角形、圆形和其他几何图形,没有这些几何图形人们只能在黑暗的迷宫中做毫无结果的游荡"。然而自然界中的许多植物,如羊齿植物、菜花和硬花甘兰,以及许多其他植物,它们的每一分支和嫩枝都与其整体非常相似。其生成规则保证了小尺度上的特征成长后就变成大尺度上的特征。这些现象需要的几何远远不是三角形和圆。"云团不是球形,山峦不是锥形,海岸线不是圆的,树皮不是光的,闪电不会沿直线行进"。所有这些自然结构都具有不规则形状,它们是自相似的。换言之,我们发现,把整体中的一部分放大便能进一步揭示其深层结构,而它几乎就是我们一开始处理的那种原始结构的复制品。例如,当你测量一个国家的海岸线,测得越精细,海岸线长度便会越长,因为你不得不计入沿海岸线长度越来越小的不规则性。从欧氏几何来看,它们是极不规则的,要对其进行描述建模,就需要一种新的几何学[12,13]

分形几何学的产生对这一领域发展注入了强大的动力. 由于分形关注的是物体的随机性、奇异性和复杂性, 因而具有细节无限以及统计自相似性的典型特征, 而且它用递归算法可使复杂的景物用简单的规则来生成。分形体具有局部与整体的自相似性,对于有规分形,自相似性只存在于一定的范围内或在一定的标度空间中,复杂的分形图不能用传统数学方法描述,但却能用简单的迭代法生成,可以应用迭代函数系统生成诸如植物,丛林,山川,烟云等复杂的自然景物[10,11]。电影《星际旅行Ⅱ:可汗的愤怒》中新行星的诞生以及《吉地的返回》中行星在空间飘浮等壮观的场面,就是由彼克沙公司在一台计算机上完成的。由计算机模拟制作的山峰,也已被IBM公司应用于广告宣传中。

1968年Lindenmayer从生物形态学的角度出发,提出了一种研究植物形态与生长的并行的算法一一L系统方法,并引入了作用在带括号字符串上L一系统[3]的几何解释,用以构造生物组织的结构特征和生长形态,即分枝的植物图形。goo Frijters等人将其应用于产生被模拟植物的分枝拓扑,并在后期处理阶段加入了线段长度和分枝角度等几何属性。Szilard和Quinton提出了解释L一系统的新方法,着重研究了有精确定义几何的图形表示,给出了一种龟标记的字符串图形解释[14,15]

二十世纪80年代,Alvy Ray Smith和P.Prusuikieuicz等人将L系统引入计算机图形学,其基本思想是根据预先定义的重写规则集不断地生成复合形状并用它来取代初始简单物体的某些部分以定义复杂物体,再通过进一步几何解释来形成逼真的画面,从此L系统广为人知。现在,L系统是生成分形图形的最典型方法之一。在国内,常杰等人出版的《植物形态的分形特征及模拟》以及齐东旭等人出版的《分形图形及其计算机生成》等书[1],都将L系统作为重要内容讲解。

1981年Witten和Sander提出著名的DLA分形生长模型[16]

1982年由Fournier等人首先构造了基于给定直线段生成分维曲线的fBm模型[6],它突破了模型依赖于观察距离的局限,以随机过程的采样路径作为构造模型的手段,利用随机中点位移、插值和Fourier滤波等方法,借助方差和分形维数构造分形曲线和分形曲面,模拟了自然界的海岸线、山谷河川、地形地貌等不规则物体[27,28]

80年代初,Fournier, Fussell和Carpenter将分形图形推向好莱坞影视业,主要影片有《星际施行之二:可罕之怒》(Star Trek II: TheWarth of Khan ) ,《最后的星球斗士》( The Last Starfighter )[17]

1985年由美国佐治亚理工学院的M.F.Barnsley等人提出了迭代函数系统IFS模型[22],他认为任何图形都可以表示为其自身的一些仿射复制品,同时指出只有收缩的仿射变换才可用于迭代函数系统,他以迭代函数系统理论作为其数学基础,提出了一整套理论(如压缩映射、度量空间、不变紧缩集的存在性以及测度理论等)和一系列生成计算机图形的算法规则(如拼贴规则、确定性迭代算法和随机迭代算法等),试图解决图形生成的逆问题对己知图象找分形压缩算法[18,]

1986年Peitgen和Richter出版了《分形之美:复动力系统图象》画册,分形图形艺术正式诞生[19,20]

1991年Donald W.Hoock为实现烟云和尘土流动图象的模拟提出了与基于分形的纹理技术,他研究了烟尘图的象分形维数与传输距离或时间的变化关系[21,22]

1993年Nishita等人基于二维分形图象建立了云的模型[24],以生成从空中俯视地球的图象,云的密度用Mandelbrot集表示。

1996年,Nishita和Dobashi等人应用分形理论并结合metaball技术,提出了云的三维模型[23]

 

3 分形景物仿真具体算法

3.1 随机中点位移法[6、9、10](RMD)

中点位移法是标准确的分形几何的方法,它是基于Mandelbrot和Van Ness 于1968 年提出的一类一维高斯随机过程分形布朗运动(Fractional Brownian Motion)而建立的。它是描述分形风景(Fractal landscape)要用到的基本技术。

而随机中点位移法的提出和应用,不是分形理论创立之后的事。早在19世纪20年代,N.Wiener就将其应用于标准的布朗运动中,后来,由于Fournier,Fussell和Carpenter等人的工作,使之在计算机图形学中得到推广。现在看来它的整个算法完全符合分形的思想,可以看成是Koch构造和图形的自然扩充。

利用随机中点位移法构造出的地形模型,具有自然地形的结构特征,具有很强的真实感,现已在自然景物仿真中得到广泛的应用[10,11]

3.2 L系统[3]

美国生物学家A. Lindenmayer1968年提出了一种研究植物形态与生长的描述方法。这种方法称为L系统。L系统不仅研究植物的拓扑结构,而且研究植物形态的几何解释。1984A. R. SmithL系统和计算机图形学结合起来,向人们展示出了L系统在计算机模拟植物方面的能力,为计算机模拟真实感图形提供了一个有用的工具。

L系统是一种形式语言,它需要通过对符号串的意义进行解释并执行相应的操作。L系统又成为LS文法,它是一类独特的迭代过程,其核心概念是重写。作为一种形式语言,LS文法用字母表和符号串来表达生成对象的初始形式,成为公理(Axion),然后根据一组产生式重写规则,将初始形式的每个字符依次替换为新的字符形式,以此过程反复替换重写,最后生成终极图形。

L系统用于植物生长过程的模拟是非常成功的,它不仅局限于植物生长的模拟,它的思想还可以应用到电子线路的设计、自然景物、建筑群体结构等方面。

    利用L系统进行计算机图形绘制的过程是设计L系统的逆过程,从信息学的角度讲,绘制L系统图形的过程实际上是将L系统中压缩的图形信息释放出来。因此,L系统在计算机图形图象以及信息压缩的其它方面必将有着重要的实际意义。

3.3 IFS系统[1,8]

迭代函数系统(Iterated Function System,IFS)是分形理论的重要分支。它也许是分形图形图像处理中最富生命力并具有广阔前景的领域之一。

这一工作最早可以追溯到Hutchinson于1981年对自相似集的研究。美国科学家佐治亚理工学院的M.F.Barnsley于1985年发展了这一分形构型系统,并命名为迭代函数系统(IFS),后来又由Stephen Demko等人将其公式化,并引入到图像合成领域中。

IFS将待生成的图像看成是由许多与整体相似的(自相似)或经过一定变换与整体相似的(自仿射)小块拼贴而成。自相似通过相似变换来实现,自仿射通过仿射变换来实现。相似变换是指在各个方向上变换的比率必须相同的一种比例变换,仿射变换是指在不同的方向上变换的比率可以不同的一种比例变换。

迭代函数系统IFS在一大类物体的建模问题中具有很强的优势,特别是对自然景物的计算机模拟优势更为明显。例如:IFS可以用来产生各种形态的植物、丛林、山川、云烟等。用迭代函数系统可以很容易地对它们进行描述。实际上,只需给出几个仿射变换的参数,就可以基本确定一个物体的迭代函数系统。由于IFS代码可以描述形态各异的对象,意味着可以用少量数据描述复杂的图像。

3.4 分形演化算法

3.4.1 元胞自动机

20世纪50年代,乌尔姆(Stanislaw M.Ulam)和冯.诺依曼(John von Neumann)为了研究机器人自我复制的可能性,提出一种叫做元胞自动机(Cellular Automaton, CA)的算法。该算法采用局部相互作用规则,最终产生整体的自复制构形。元胞自动机现已成为研究复杂系统行为的一个理论框架,也是人工智能的雏形[25,26]

细胞自动机是一个离散系统,它由空间大量相同的相互连接的简单组元组成,离散是指细胞自动机在有限的时空范围中具有有限的状态,细胞自动机不用复杂方程描述系统,而以系统组元的动态为研究基点,通过简单元素以及简单规则产生复杂的现象。

二十世纪四十年代,游戏理论的创始人,集合论的先驱Neumann和从事Monte Carl仿真研究的Ulam为研究生物繁殖和晶体构成首先提出了CA的概念。细胞自动机的核心是一个有限状态的自动机,它通过有限的状态及规则来研究复杂的系统,能够并行地处理局部层次的变化,通过递归的相互作用,能够产生不同规模的复杂的结果。

近年来,CA已取得了长足的发展,并成为复杂系统的建模和仿真的主要方法之一, 1991年Pakeshi等人提出了基于细胞自动机的火焰模型〔PAICE9lJ,认为火焰等气体现象都是由简单的组元构成的。组元虽然简单,但它们的组合形态和系统行为非常复杂,甚至可以产生无法预测的延伸、变形等复杂的运动形式,以至于不能简单地用某种数学模型来描述。

1997年Dobashi等人应用细胞自动机原理计算云密度分布随时间的变化,提出了云的动画算法。

1998年Dobashi等人提出了基于卫星图象生成云图的算法,用metaballs为云建模,通过一组卫星拍摄的照片得到大气的流动,用Bezier曲线表示,控制metaballs沿该曲线运动,并不断改变密度。

2001年,SeongGyu Jeon等人在提出了基于细胞自动机的爆炸模型,空间被分为三维网格,每一网格为一个细胞单元,每一单元具有的状态为能量,初始时,产生一定能量的爆炸物质位于爆炸中心的若干细胞单元中,爆炸用一链式反应描述,在这个反应进行过程中,只发生能量的传输,应用细胞自动机原理实现细胞单元间的能量变化,在绘制时,每一帧都对细胞单元的能量进行修改,单元的能量决定了其颜色。

3.4.2 分形演化的DLA模型

1981年美国埃克森公司的Thomas A.witten和Leunard M.Sander提出了一个模型,用于模拟类似冰花结构的形成过程,这个模型便是著名的DLA模型,即扩散优先凝聚模型(Diffusion Limited Aggregation)。

在DLA模型中,其生长过程是这样的:粒子一次一个地从某一外部区域中释放出来,并使其作无规则的运动,当它与生长着的凝聚体想接触时,便永远地附在其上,也就是被凝聚在生长着的凝聚体之上。在粒子的每一步游动中,其运动方式完全是随机的。这就是有限扩散凝聚模型,即DLA。利用DLA和其修改的模型可以对部分植物的形态结构进行模拟,例如植物根系的生长过程模拟和海藻类植物的形态结构模拟等。

4 应用与展望

在查阅文献过程中,发现分形理论在物理学、化学、地质学、生物学、经济学等领域内,已有很多应用成果。尤其在虚拟场景的模拟中,为了使得实现的场景具有相当的真实感和实时性,虚拟场景中的各种静态和动态自然景物的仿真是非常重要的。包括云雾、水流、海面、波浪、花草、地形、树木、烟尘、火光等许多特殊效应的模拟实现,运用近几年来迅速发展的分形几何学来仿真这些特殊效应,能较好地解决这些不规则形态物体的仿真建模问题,可以从少量的数据生成复杂的自然景物图象,其真实感和实时性效果非常好。我们相信,被称为自然界的几何学的分形理论在景物仿真中一定有广阔的应用前景,将来,必将在影视、地理、军事、气象等领域发挥不可限量的巨大作用。

Mandelbrot曾说"如果我只是证明了少数几个定理的话,那么用这些定理很难发现现在还没有创立的或潜在的研究领域".这足以证明分形的工作充满想象力、十分具有挑战性。

通过以上分析我们发现分形具有广阔的应用前景,在分形的发展过程中,许多传统的科学难题,由于分形的引入而取得显著进展。分形作为一种新的概念和方法,正在许多领域开展应用探索。

P.D.Lax接受记者采访时对分形提出了大致这样的看法:分形无疑是重要的,但目前的研究还远未深入到它的本质。

 

参考文献

[1] 齐东旭. 分形及其计算机生成(第一版) [M ]. 科学出版社,1994 - 11.

[2] 张轩, 杜可亮. 虚拟现实技术 VRML语言(第一版) [M ]. 电子工业出版社,1998.8.

[3]  张树兵王建中. 基于L - 系统的植物建模方法改进[ J ]. 中国图像图形学报. 2002, 7 (5) : 457 - 460.

[4] 童若锋, 陈凌钧. 烟雾的快速模拟[ J ]. 软件学报, 1999, 10(6) : 647 - 651.

[5]  齐越, 沈旭昆. 基于Perlin噪音绘制云的方法[ J ]. 系统仿真学报, 2002, 14 (9) : 1204 - 1207.

[6]  阮鲲,范茵. 基于中点偏移算法的云的模型设计[ J ]. 解放军理工大学学报, 2003, 4 (1) : 99 - 102.

[7]  洪涛,曹华. 用分形理论模拟山峰和云[ J ]. 西北工业大学学报, 1995, 13 (4) : 576 - 580.

[8] Eli 彭群生,鲍虎军,金小刚.计算机真实感图形的算法基础[M].北京:科学出版社1999.

[9] B B Mandelbrot. The Fractal Geometry of Nature[M ]. San Fran2cisco: Freeman Pr, 1982, 233 - 273.

[10] Gavin S P Millier.The Definition and Rendering of TerrainlVlaps[J].Computer Graphics。1986,20(4):3948.

[11] J E Dudgon,R Gopalakrlshnan.Fractal-Based Modeling of 3DTerrain Surfaces[J].Proc of IEEE,1996,84(4):246252.

[12] J F Blinn. Light Reflection Function for Simulation of Clouds and Dusty Surface[ J ].Computer Graphics, 1982, 16 (3) : 21 - 29.

[13]  N Max. The Simulation of Natural Phenomena Panel[ J ]. Computer Graphics, 1983, 17 (3) : 137 - 139.

[14] J T Kajiya, H B P Von. Ray Tracing Volume Densties[ J ]. Computer Graphics, 1984, 18 (3) : 165 - 173.

[15]  Miller, S P Gavin. The definition and rendering of terrain map s[ J]. Computer Graphics, 1986, 20 (4) : 39 - 48.

[16] Novianto S, Suzuki Y, Maeda J. Near optimum estimation of local fractal dimension for image segmentation[J]. Pattern Recognition Letters.2003, 365-74.

[17] Kamejima K. Fractal representation of image feature[C]. IEEE ROMAN 2002. 11th

IEEE International Workshop on Robot and Human Interactive Communication. 2003, 506-511.

[18] Mohd Shahrizal Sunar, Mohammad Azam Rana. VISUALIZING AND MODELING CLOUD FOR VIRTUAL ENVIRONMENT[C]. IASTED(International Association of Science and Technology for Development)International Conference on Applied Simulation and Modelling. Marbella,ES, 2003: 598-603.

[19] Jyo TAKENOUCHI, Shigeo WADA. THREE-DIMENSIONAL RENDERING OF FRACTAL CLOUDS[C]. 6th IASTED International Conference on Computer Graphics and Imaging Honolulu, Hawaii, USA. 2003:6p.

[20] Adi Bar-Lev, Alfred M. Bruckstein,Gershon Elber.Virtual marionettes: a system and paradigm for real-time 3D animation[J]. The Visual Computer ,2005, 21(7):488-501.

[21] Kenji Nagashima. Computer generation of eroded valley and mountain terrains[J]. The Visual Computer. 1998, 13(9-10): 456 – 464.

[22] Iannaccone PM. Fractal geometry in mosaic organs: a new interpretation of mosaic pattern[J]. The FASEB Journal. 1990 Mar: Vol. 4 (5), pp. 1508-12.

[23] Clarkson, Mark Amazing fractals[J]. FamilyPC. Sep95: Vol. 2 Issue 7, p212, 4p, 6 diagrams, 7c

[24] Ruan Kun, Fan Yin, Li Hui-jun, et al. Modeling cloud based on midpoint deflection algorithm [J]. Journal of PLA University of Science and Technology (Natural Science Edition), 2003,4(1): 99-102.

[25] Kan Araki. Imaging of fractal scattering of natural scene in rural field by milliwaveantenna[J]. 電子情報通信学会技術研究報告,2000,100(13):43-46.

[26] Li Changjiang, Zhao Nailiang, Ma Tuhua. Fractal Reconstruction with Unorganized Geochemical Data[J]. Mathematical Geology, 2002,34(7): 809 - 829

[27] Kim, Theodore Won-Hyung. Physically-based simulation of ice formation[D].
THE UNIVERSITY OF NORTH CAROLINA AT CHAPEL HILL, 2006.

[28] Taylor, Tara D. Computational topology and fractal trees[D]. Canada: DALHOUSIE UNIVERSITY,2005.

  评论这张
 
阅读(786)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017