（运筹学与控制论专业论文）形式化分形造型技术.pdf

硕十学位论文 摘要 2 0 世纪7 0 年代m a n d l e b r o t 创立了分形几何学，不规则性和无限精细的自相 似结构是分形几何的最重要特征，因此分形可以很好的用来定义和表达传统欧式 几何难以表达的复杂几何形体。 分形几何学的研究热点之一是分形图形的生成算法，其中迭代函数系统和l 系统在分形造型、自然景物模拟等方面具有广阔的应用前景，然而其难以预测的 结果和复杂的表达形式是他们的缺点。 本文回顾了分形几何学的发展历史及迭代函数系统和l 系统生成分形图形 算法，研究了形式化分形造型系统的文法结构，语义学与形式化表达等技术。基 于i f s 和l 系统的基本理论，结合形式化方法，提出了i f s 的符号重写算法，并 实现了i f s 的符号重写分形造型系统。使得i f s 与l 系统建立了联系，并给出 了适合该算法的符号重写系统实例。通过符号重写系统定义、i f s 到该系统的转 换、i f s 符号重写算法描述和实例，能反映出它比常规i f s 和l 系统具有更强的 表达能力、造型能力和直观交互性。 本文成果为分形造型技术的研究提供了新的途径，其公理化方法和形式化方 法的运用大大提高了分形图形的实现效率，在自然景物模拟、动画制作、建筑配 景、虚拟现实等方面都有着重要的应用价值。 关键词：分形；迭代函数系统；l 系统；形式化；吸引子 形式化分形造型技术 a b s t r a c t m a n d l e b r o tc r e a t e df f a c t a li nt h e1 9 7 0 s ，i r r e g u l a ra n du n l i m i t e df i n es t r u c t u r eo f t h es e l f - s i m i l a ra r et h em o s ti m p o r t a n tf e a t u r e so ft h ef r a c t a l ，s ot h ef r a c t a lc a nb e w e l lu s e dt od e f i n ea n de x p r e s st h ec o m p l e xg e o m e t r yw h i c he x p r e s sd i f f i c u l t l yb y c o n t i n e n t a lg e o m e t r i c t h eg e n e r a t i o na l g o r i t h mo ff r a c t a lg r a p h i c si so n eo ft h eh o t t e s tr e s e a r c ho n f r a c t a l ，a n di t e r a t e df u n c t i o ns y s t e m sa n dls y s t e mi nf r a c t a lm o d e l i n g ，s i m u l a t i n g n a t u r ef e a t u r e sh a v eb r o a da p p l i c a t i o np r o s p e c t s ，b u tt h e i rs h o r t c o m i n g sa r ed i f f i c u l t t op r e d i c ta n da r ec o m p l e xt oe x p r e s s t h i st h e s i sr e v i e w st h ef i a c t a ld e v e l o p m e n th i s t o r ya n dt h eg e n e r a t i o na l g o r i t h m o ff r a c t a lg r a p h i c sb yi t e r a t e df u n c t i o ns y s t e m sa n dl s y s t e m ，a n ds t u d i e st h ef o r m a l m o d e l i n gs y s t e mf r a c t a ls t r u c t u r eo ft h eg r a m m a r ，s e m a n t i c sa n df o m a le x p r e s s i o n a c c o r d i n gt oc a l c u l a t i n gp r o c e s sg e n e r a t e db yi f sa t t r a c t o r , w ep r o p o s es y m b o l r e w r i t i n ga l g o r i t h mo fi f sw h i c hm a k e sac o n n c t i o nb e t w e e ni f sa n dls y s t e m ，a n d g i v et h ea l g o r i t h me x a m p l e so fas u i t a b l es y m b o lr e w r i t i n gs y s t e m ，a n da c h i e v e f f a c t a lm o d e l i n gs y s t e mo fs y m b o lr e w r i t i n go fi f s t h ed e f i n i t i o no fs y m b o l r e w r i t i n gs y s t e m ，t h ec o n v e r s i o no fi f ss y s t e m ，t h ed e s c r i p t i o n sa n de x a m p l e so fi f s s y m b o lr e w r i t i n ga l g o r i t h ms h o wt h a t i th a sam o r ec a p a b i l i t i yo fe x p r e s s i o n ， m o d e l i n ga n di n t u i t i v ei n t e r a c t i v i t yt h a nc o n v e n t i o n a li f sa n dls y s t e m t h i st h e s i sr e s u l t sp r o v i d ean e ww a yf o rf r a c t a lm o d e l i n gt e c h n o l o g y t h e a x i o m a t i cm e t h o da n dt h eu s eo ff o r m a lm e t h o d sg r e a t l yi m p r o v et h er e a l i z a t i o no f f r a c t a lg r a p h i c se f f i c i e n c y i ti sv e r yu s e f u lf o rn a t u r es c e n es i m u l a t i n g ，f l a s hm a k i n g ， a r c h i t e c t u r ef o i l i n ga n dv i r t u a lr e a l i t ye t c k e yw o r d s ：f r a c t a l ；i t e r a t e d f u n c t i o ns y s t e m ；ls y s t e m ；f o r m a l ：a t t r a c t o r l l 硕十学位论文 插图索引 图2 1i f s 随机迭代算法生成分形流程图 1 2 图2 2 蕨叶1 3 图2 3d o l 系统生成k o c h 曲线1 6 图2 4 字符随机解释产生的一组植物结构0 0 6 00 1 8 图2 5 随机l 系统产生的一组植物结构1 8 图2 6 由语义相关l 系统生成的植物结构2 0 图2 7 三维海龟爬行解释模型2 1 图2 8 三维空间龟形解释图2 2 图2 9l 系统生成分形流程图2 3 图3 1 迭代第1 次过程0 0 00 00 q o 2 6 图3 2 迭代第2 次过程2 7 图3 3 s i c q f i n s k i 三角形2 7 图3 4i f s 的符号重写系统生成分形流程图g odgom ioooo l 3 0 图3 5 分形脸谱0 00 ”3 1 图3 6 分行树枝3 1 图3 7 分形蘑菇云3 2 图3 8 自定义分形树o o bqoio o 3 2 i i i 兰州理工大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名：易劾久钐z 日期：沙咖6 月c 。日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即： 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许 论文被查阅和借阅。本人授权兰州理工大学可以将本学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存和汇编本学位论文。同时授权中国科学技术信息研究所将本学位论文 收录到中国学位论文全文数据库，并通过网络向社会公众提供信息服 务。 作者签名： 导师签名： 琳钆 刍m 6 月 只 加日 f 矽日年年 呔产一 聊7 期期 日日 硕十学位论文 1 1 课题的研究背景 第1 章绪论 2 0 世纪7 0 年代，美籍法国数学家m a n d e l b r o t 仓l j 立了一种用来描述不规则形体 的几何一分形几何【1 1 。分形几何作为- - f l 以非规则几何形状为研究对象，用来描 述大自然的几何学而在各个学科上得到了广泛应用，包括地质学、现代医学、流 体力学、计算机科学、甚至还有影视作品。 随着分形理论的发展，计算机图形造型技术越来越多的使用到分形技术，与 规则形体的造型技术不同，不规则形体的造型大多采用过程式模拟，即用一个简 单的模型及少量的易于调节的参数来表示一大类物体，通过递归调用这一模型就 能一步一步地产生数据量很大的物体。分形具有整体与部分的自相似性，采用各 种模拟真实图形的模型，使整个生成的景物呈现出细节的无穷回归的性质，具有 奇妙的艺术魅力。所生成的景物中，可以有树、山峰等结构性较强的图形，也可 以是火、云等结构性较弱的图形。生成图形的关键是要有一个合适的模型来描述 对象，根据所选择的分形造型的模型不同，产生分形图形的方法有迭代函数系统 ( 见2 1 ) 、l 系统( 见2 2 ) 、d l a 模型、粒子系统、随机插值法、分形插值、曲 线曲面技术等等【2 】。如果分形图形生成算法不用形式化逻辑思维，而用生活语言 或接近生活语言的表述方式来推理，则每一步都需要严格思考，当问题很复杂时， 考虑的因素会很多，推理过程很长，常人再聪明也没有用。而采取了形式化逻辑 思维，则人的思维只要去判断实际问题遵守哪些原理，每个概念对应公式中什么 符号，按规则变化，这样的推理过程越多则难度越大，但计算机技术可以让我们 推理很复杂的过程，最后得出有用的结果，再把形式化的结果还原成人们容易理 解的正常语言。这种形式化方法和公理化方法作为一种研究手段，特别是在对分 形进行分析时给我们提供了一种新思想，一种新尝试，将其应用到分形图形生成 算法中大大提高了人的大脑效率。 1 2 课题基本理论 1 2 1 分形的产生及其发展过程 分形这个名词来源于拉丁词汇f r a c t u s ，是m a n d e l b r o t 在2 0 世纪7 0 年代为 了表征复杂图形和复杂过程而引进自然科学领域的。它的原意是不规则的、支离 破碎的物体。二十世纪七十年代，m a n d e l b r o t 经过精心研究，于1 9 7 5 年出版了 形式化分形造犁技术 他的专著分形、机遇和维数，这标志着分形( f r a c t a l ) 理论的诞生。到目前 为止还没有一个公认的严格的数学定义，人们也只能给出描述性的定义。一般认 为，分形是对没有特征长度，但具有一定意义下的自相似性的图形和结构的总称。 统观整个分形理论，不难发现，分形可以分为规则分形和不规则分形。规则分形 一般是由科学家们通过一定的规则构造出来的，具有严格自相似性的分形图。不 规则分形很多是随机生成的。它们普遍存在于自然界中，最著名的随机分形的例 子就是变换无穷的布朗运动。 分形的理论产生、发展与应用经历了三个阶段1 3 4 】： 第一个阶段，分形理论产生的萌芽阶段( 1 9 2 5 年以前) 。这期间几种典型的 分形集开始出现。人们力图用传统的几何语言来进行描述、分类或刻画，但不能 实现。当时这些分形集被人们称为病态的，例如k o c h 曲线。1 9 1 9 年h a u s d o r f f 引入了分形维数的概念，以此为基础各种分形维数相继引入。这一阶段是分形理 论发展的第一阶段，其实此时人们已经提出了典型的分形对象及其相关问题并为 讨论这些问题提供了最基本的工具。 第二个阶段，分形理论形成与发展阶段( 1 9 2 5 1 9 7 5 年) 。这一阶段分形理论 逐步形成，而且研究范围也扩大到数学的许多分支中。这一时期，维数的乘积理 论、投影理论、位势方法、网测度技巧、随机技巧均先后建立并成熟，这使得分 形几何的研究具有自己的特色与方法。 第三个阶段，分形理论不断完善和广泛应用阶段( 1 9 7 5 年以来) 。1 9 7 5 年， m a n d e l b r o t 开始发表了一系列有关分形的文章，引进了分形概念，产生了“分形 几何学。从此，结合计算机技术，分形很快成为- f - 跨学科的、非线性的相当 活跃学科，其理论研究和应用深入到了人类活动的方方面面。 随着计算机特别是计算机图形学的迅速发展，人们在使用计算机对一些问题 进行深入探讨的过程中，越来越感觉到用传统的欧氏几何已不能有效地描述自然 界中存在的大量事物。例如曲折的海岸线、喷发的火山、云团、山形、断裂、树 木、闪电等等。它们具有如此复杂精细的结构，以至于用传统的几何学对它们都 不能进行逼真而生动的描述，可以说，分形是无处不在的。鉴于它们的复杂性与 精细性，我们采用分形几何来描述。 分形是一门新发展起来的学科，到目前为止还没有确切的定义，但在现实生 活实践中，人们通常引用k f a l c o n n e r 对分形集合f 的描述1 5 j ： ( 1 ) f 具有精细的结构，即是说在任意一个小的尺度之下，它总有复杂的 细节； ( 2 ) f 是如此的不规则，以至它的整体和局部都不能用传统的几何语言来 描述： ( 3 ) f 通常具有某种自相似性，这种自相似性可以是近似的，也可以是统 计意义上的： 硕士学何论文 ( 4 ) f 在某种意义下的分形维数通常都大于它的拓扑维数； ( 5 ) 在多数令人感兴趣的情况下，f 以非常简单的方法定义，或许以递归过 程产生。 自然界中的大部分事物都不是有序的、稳定的、平衡的和确定性的，而是处 于一种无序、不稳定、非平衡和随机的状态中。在非线性世界里，随机性和复杂 性是主要特征，然而在这些极为复杂的现象背后，存在着某种规律性。近年来发 展起来的分形理论使人们能以新的观念，新的手段来处理这些难题，通过扑朔迷 离的无序的混乱现象和不规则的形态，揭示隐藏在复杂现象背后的规律，局部和 整体之间的本质联系。 1 2 2 形式化方法 形式化方法在古代就运用了，而在现代逻辑中又有了进一步的发展和 完善。这种方法特别在数学、计算机科学、人工智能等领域得到广泛运用。 它能精确地揭示各种逻辑规律，制定相应的逻辑规则，使各种理论体系更 加严密，同时也能正确地训练思维、提高思维的抽象能力。 形式化方法的本质是基于数学的方法来描述目标系统属性的一种技 术。不同的形式化方法的数学基础是不同的，有的以集合论和一阶谓词演 算为基础，有的则以时态逻辑为基础，形式化方法需要形式语言的支持。 形式语言也称代数语言学，它研究一般的抽象符号系统，运用形式模型对 语言( 包括人工语言和自然语言) 进行理论上的分析和描写【6 。形式文法是一 种格式，用来说明什么句子在该语言中是合法的，并指明把词组合成短语 和句子的规则。描述语言有三种途径：穷举、文法和自动机。其中文法看 重产生过程，而自动机强调识别过程。一种语言，如果存在对它的识别过 程，就一定存在对它的产生过程，反之亦然。 现行的形式语法系统是c h o m s k y 于1 9 5 9 年为了描述自然语言而提出的 一种理论模型。严格的定义形式化的语言如下： 1 、形式文法 文法g 是个四元式( 由四部分组成) ，即g 一( ，v ，s ，p ) 。其中， ( 1 ) 是一个有限字符集合，叫做字母表，它的元素称为字母或者终结符； ( 2 ) v 是一个有限字符集合，叫做非终结符集合，它的元素称为变量或者 非终结符( 一般用大写英文字母表示) ； ( 3 ) s 是一个特殊的非终结符，即s e v ，称为文法的开始符号； ( 4 ) p 是有序偶对似，) 的集合，其中口是集合( u v ) 上的字符串，但至 少包含一个非终结符；卢是集合仨u y ) 木的元素。一般，将有序偶对 ，卢) 记为 口呻声，称为产生式( 要注意顺序，口在前，卢在后) 。口称为该产生式的左部， 卢称为该产生式的右部。 形式化分形造型技术 对于文法g ，如果s 辛* t o 则称是文法的一个句型；若中包含的字符全 是终结符，称是句子。 语言的定义：给定文法g ，有开始符号s ，则把s 可以推导出的所有终结符 串的集合( 即所有句子的集合) 称为有文法产生的语言，记为l ( g ) ，即 工( g ) 一 缈is 辛奉，枣】 2 、形式语言的特点 ( 1 ) 高度的抽象化( 采用形式化的手段一专用符号，数学公式一来描述语 言的结构关系，这种结构关系是抽象的) ； ( 2 ) 是一套演绎系统( 形式语言本身的目的就是要用有限的规则来推导 语言中无限的句子，提出形式语言的哲学基础也是想用演绎的方法来研究 自然语言) ； ( 3 ) 具有算法的特点( 比如说句法分析中采用不同的算法来构造句子的 句法推导树) 。 1 3 实际意义 自分形理论建立至今，分形已从一个简单的几何概念发展到一个有着重要应 用价值的理论体系，当前已渗透到图形学、社会科学、艺术等各个领域。在分形 的发展过程中，许多传统的科学难题，由于分形的引入而取得了显著的进展。 本文的研究内容属于形式化方法在分形造型技术中的应用性研究，在对迭代 函数系统和l 系统这两种经典分型造型技术进行详细研究后提出了一种新的分形 造型算法一i f s 的符号重写算法。其采用形式化方法使某些抽象的概念和复杂的 过程形象化，使人们的形象思维和逻辑思维有机结合，从而更有效地探索客观事 物的内在本质和规律性，达到启迪思维，促进科学创作的目的。这种算法较以前 算法具有更强的表达能力、造型能力和直观交互性，而且结合计算机强大的迭代 计算能力，在许多领域开展了分形应用探索，使分形成为非线性学科新的生长点， 它已不限于具体地数理学科，而是具有世界观和方法论的意义。 1 4 国内外研究现状综述 迭代函数系统( i t e r a t e df u n c t i o ns y s t e m ，简记为i f s ) 的产生最早可以追溯到 1 9 8 1 年h u t c h i n s o n 对自相似集的研列7 1 。1 9 8 5 年，m e b a m s l e y 和s d e m p o 将其公 式化，并应用到图像压缩和处理方面【踟。1 9 8 9 年，b a r n s l e y 等提出了“再归迭代 函数系统( r e c u r r e n tw s ) ”方法【9 】，该方法在自相似性生成方面更加灵活多变，植 物局部自相似性之间可以有更多不同。 近年来，国内外学者在基于i f s 的分形图形生成领域都进行了大量的研究工 作，产生了带概率i f s 、带凝聚集i f s 、带参数i f s 等等，并取得了一定的进展。 美国伊利诺斯州立大学计算机系p a u ls h e r m a n 和j o h nc h a r t 给出了一个分 硕士学位论文 形图形生成算法1 1 0 l ，使用户可以直接操作一个由周期迭代函数系统( r i f s ) 生成 的分形对象，这种方法可以让用户指定吸引子上的特定点，然后拖拽其他点到用 户需要的位置。为符合新的位置，吸引子的形状会改变。作者用一个扩展的牛顿 迭代法，找到了一个新的等价的满足约束条件的迭代参数集。 王镝等人讨论了一种参数控制方法1 1 1 】，通过改变参数控制i f s 吸引子的形状， 最终生成不同的计算机图像，该方法首先给出两个原始三角形，通过对两者位置 和形状的改变得到i f s 码，并通过不断引入新的三角形并改变其位置和形状来影 响i f s 吸引子的外观。 张亦舜等人利用i f s 吸引子局部间具有相似性【l 引，提出了由i f s 中可逆仿射变 换的不动点来逐步生成吸引子的原理和方法。 章立亮提出了一种生成分形技术【1 3 l ，即对不动点多边形的调控来实现对原迭 代函数系统分形图形的操作。这种方法可以直观有效的获得大量形态各异的分形 图。 魏小鹏讨论了传统的迭代函数系统拼贴建模方法【1 4 1 ，从整体和局部的组合与 相似关系出发，对传统拼贴建模方法进行简化，给出两种简化方法：局部轮廓法 和三点法，分析了三种建模方法的应用条件和具体实现技术。 贾建等人由职s 的变换构造不动点多边形【1 5 】，根据不动点多边形的匹配关系 得到从源图像到目标图像的中间插值算法，实现了分形图形的渐变过程。 有些学者提出了寻找新的i f s 建模技术【1 2 ，1 5 】或者根据已知的i f s 码通过加入 某些参量再进行调整来生成新的分形图形的方法【临1 s 3 。t a oj u 研究仿射变换i f s 和递归龟图几何生成分形图算法1 1 9 1 ；仲兰芬、李庆忠等研究了基于i f s 的三维树 木模拟方法【刎；方建安、张旭还研究了i f s 模拟植物图像的颜色生成算法【2 l 】；曾 锋等基于迭代函数系统进行了彩色植物模拟研究1 2 2 】；s a r a h 研究分形的快速精确 的生成算法【冽；李庆忠、h s u a nt c h a n g 等分别提出了l 系统与i f s 相融合的方法 和分形图形的合成方法【2 4 乃】；t o m e km a r t y n 提出了吸引子变形的正确性标准及新 的i f s 分形变形算法i 矧，为分形动画的实现奠定了基础；b u r c h 等提出了利用极值 分解方法分解i f s 仿射变换的线性部分矩阵，实现二维i f s 线性分形变形1 2 7 1 ；刘树 群实现了i f s 吸引子图像仿射变换的分形码变换通式幽j ，并讨论了几种常见的吸 引子变换，其为分形图像变换和分形图形设计提供了一种简捷、高效和灵活的处 理方式。 1 9 6 8 年，美国生物学家l i n d e n m a y e r 从植物形态学角度提出的一套用以描述 树木的方法，开始时只着重于植物拓扑结构，即植物组件之间的相邻关系，后来 才将几何解释加进描述过程，形成l 原纠矧。 1 9 8 4 年，a u 也s m i t h 将l 系统应用于计算机图形学中，为模拟植物而引入基 于文法的模型【删。其基本思想是用正则文法生成结构性强的植物的拓扑结构，再 通过进一步几何解释来形成逼真的画面。该模型的工具是基于迭代方法的改写， 形式化分形造刑技术 以及将形式化语言图形化方式。 由于计算机图形学技术让l 系统描述的结构被可视化的展现出来，从而使l 系统从理论概念发展成为程序设计语言，以用于合成不规则图形和真实的植物影 像：这又反过来进一步促进和提高了l 系统强大的建模功能，因此不断的吸引着 越来越多的人投入到模型架构和植物生长的研究中来。 陈敏智等利用参数化l 系统生成植物生长结构模型的方法【3 ，给出了模拟植 物结构模型所需的l 系统的迭代公理和若干产生式参数，并实现了植物形态可视 化模拟。冯宗坚等运用3 d 建模技术及相关编程技术实现对l 系统的三维化【3 2 , 3 3 j ， 并利用正则三叉树模型实现了基于l 系统的三维分形树的生成。 张树兵等用递归结构来表达l 系统生成的表达式i 州，简化了数据结构，使运 行l 系统算法所需的时间和所占的空间减少。丁维龙等采用子结构算法减少了l 系统重复迭代所占用的系统空间【3 5 】。并利用植物学家总结的植物架构模型提炼出 l 系统规则模板库，在此基础上开发出可视化模拟系统v p g 1 。该系统弥补了l 系统在通用性上的缺陷，拓宽了系统的适用面，并且使用方便。 陈昭炯分析了l 系统在表达植物结构形态方面的机制1 3 州，对竹子进行了模 拟，得到了仿真度很高的竹子模型。孙轶红等将l 系统得到的模型层次化处理1 3 7 1 ， 根据视点与树模型的距离确定需要的树木模型数据层次，保证了树木生成的实时 性。 徐杨等在l 系统基础上，考虑树木的分生器官的一些重要现象如顶端分生、 趋光性、向地性等，建立了一个数据量较少，适用于工程设计中自然场景模拟的 树木模型【捌。施干卫等在对林学中的植物生长模型和环境模型综合研究的基础 上，根据植物生长时形态及生理特性与环境之间的相互作用，提出了一个基于环 境敏感的植物动态生长模型【3 9 】，模拟出树种在不同环境下的生长状态。秋林等概 括了植物根系的拓扑结构，发现了植物根系与l 系统理论的相关性，利用l 系统 实现了冬小麦根系生长的动态模拟【矧。同时利用动态数据结构弥* b l 系统灵活性 的不足，使小麦根系的显示方便灵活、更加真实自然。袁可等在l 系统基础上实 现了冬小麦的根系模拟【4 l j ，并引入“管道模型，使系统在模拟的同时，能够计 算根长、根重、根体积等重要参数，实现了生长发育模型与形态发生模型的结合。 李云峰等结合l 系统理论和图像合成技术建、- r e a s y l 系统理论，对叶面进行建模和 重建【4 2 1 。得到了具有良好视觉效果和可控性的叶生长模型，并在此基础上，设计 开发了虚拟植物可视化通用平台i m a g e v p 系统。该系统注重于视觉效果，并能 对花、叶等植物器官进行模拟。 w o j c i e c hp a l u b i c k i 等人提出了“自我组织 的建模方法1 4 3 j ，该方法集成了树 的形成三要素：树枝结构的局部控制、芽和树枝的空间和光线的竞争、通过内部 信号机制规划这种竞争。并展示了依靠自我组织简化了建模过程；自我组织和构 造的一体化提高了树的虚拟现实方法；信号的使用使得顶点发育控制成为可能； 硕十学位论文 量曼曼曼曼曼曼曼量曼量曼曼曼曼皇皇曼曼曼曼曼曼量曼曼曼曼蔓il 曼曼曼曼曼量曼曼曼曼曼皇舅舅舅曼曼曼舅曼曼曼曼曼曼曼皇量曼曼皇曼曼皇曼! 曼量量量曼量曼量 这一系列模拟形式可以进一步扩大使用程序刷，这使用户通过交互操作能够控制 树木产生的环境。 p r z e m y s l a wp r u s i n k i e w i c z 等人引入参数上下文语义相关l 系统的仿射变换几 何解释作为一种替代技术并产生细分曲线【删。l 系统细分算法以直观，简洁，指 数自由的方式，反映了并行和局部性质。此外，l 系统细分曲线算法，可直接进 行计算机执行。p r z e m y s l a wp r u s i n k i e w i c z 和m a r kh a m m e l 提出了语言约束迭代函 数系统( l r i f s ) ，其采用迭代变换坐标系统限制语言的方法1 4 5 】，其中一些l r i f s 相当于参数l 系统的海龟解释。该方法通过加入不同变换顺序的约束条件，能够 比较通用地概括各类不同的i f s 方法。 澳大利亚c p a i 研究中心开发了一款基于l 系统的软件v i r t u a lp l a n t s ，该软件 包含新的植物器官产生规则以及已有器官的大小及形状变化规则。主要用于模拟 棉花、大豆等作物的生长发育过程和害虫对于作物的影响，研究了棉花与害虫之 间的交互作用。该软件目前还只能用于定性研究模拟，距实际应用于农林业生产 还有一定距离。 开发以模拟植物外观形态为主要应用目的的软件不需要对于生长机理的大 量测试数据，也不需要严格符合植物学知识，其目的是简单快速地生成逼真的植 物图形，并可用于自然景观的再现。著名的x f o r g 植物模拟软件就可归为此类， 它是由德 k a r l s r u h e 大学的l i n t e r m a n n 等人开发研制的【矧。该软件运用了基于功 能图符的交互式植物构造模型，该模型以整个枝条为单位构造植物。该软件定义 了一些表示植物器官、植物结构、全局变量和功能函数的小图符，每个图符具有 描述其具体属性的参数表。用户只需要通过与软件简单的人机交互就可以得到相 当逼真的植物图形。其最大的优点就是人机交互方便，还可以模拟光照和重力等 因素对于植物枝条的影响。 德国k u n z f e r n h o u t 公司开发的p l a n ts t u d i o 软件，应用一些图符表示植物的 分枝结构、分生组织、节间、花序、花朵、叶片和果实等属性，用户不需要很多 的植物学知识就能通过人机交互输入植物参数，制作出视觉上逼真的植物图形。 而且其生成的文件格式多种多样，如3 d s 、d f x 、w r l 、p o v 和l w o 等，可以 通过现有的图形工具软件对其生成的植物图形进行修改和润色，增加其视觉上的 真实性。 加拿大的c a l g a r y 大学的p r u s i n k i e w i c z 等人对l 系统进行了扩展，比如提出了 能够与周围环境交互的开放l 系统( o p e nl - s y s t e m ) 1 4 7 】和能够模拟植物生长的随 机性的随机l 系统( s t o c h a s t i cl - s y s t e m ) 4 8 j ，为使l 系统引入了一个“交流符号， 该符号可以实现l 系统与周围的环境的交互。为了模拟植物的连续生长过程， p r u s i n k i e w i c z 等又提出了时变( t i m e d ) l 系统【4 9 1 ，能够生成植物生长过程的计算机 动画。为了能够进一步描述植物生长的连续的过程，p r u s i n k i e w i c z 又把微分方程 引入到了l 系统，从而提出了微分l 系统( d i f f e r e n t i a ll - s y s t e m ) 5 0 l ，该系统能够较 形式化分形造型技术 好的模拟植物的叶序、美丽的花朵、弯曲的枝条等，以及植物在生长过程中相互 影响等情况，比较完美的实现了对植物生长过程的模拟。 l - s t u d i o 是由加拿大的c a l g a r y 大学开发的基于l 系统的植物建模工具【5 l 】，研 究植物与它们所在的外界环境之间的交互性。使用者根据其预先定义的解释符 号，编制所要模拟的植物的l 系统产生式，软件根据产生式生成植物图形。 其内容主要包括： ( 1 ) 两个基于l - s y s t e m 的模拟程序：c p f g 和l p f g ； ( 2 ) 用于提供辅助建模工具的建模环境； ( 3 ) 用于模拟影响植物生长环境的程序库； ( 4 ) 一套建模实例； ( 5 ) 用于组织和存储本地或远端机器中所建模型的图形浏览器。 在使用l - s t u d i o 实际建模的时候，除了对模型作必要的l - s y s t e m 描述以外， 还需要输入一些其他的信息，以便c p 龟和l p f g 用于控制模型的视图和动画过程。 这些信息包括用来建立可视化模型的植物器官的形状、颜色等属性值。 l - s t u d i o 提供给用户一个用于描述这些补充信息，并将这些信息传送给模拟 程序的接口。在l - s t u d i o 的工作窗口中提供了多个编辑器，它们被用于对不同对 象进行编辑。其中包括： ( 1 ) 文本编辑器：用于创建和控制l - s y s t e m 文件和其他构成模型的文本文 件，如视图文件、说明文件等等； ( 2 ) 动画文件编辑器：用于设置动画效果； ( 3 ) 颜色和材质编辑器：在对模型着色时，描述植物的外观； ( 4 ) 图库编辑器：这其中包含了多个编辑器，如：基本高级界面编辑器，用 于定义独立植物器官的形状；植物交叉部位的轮廓编辑器；植物各器官成长函数 编辑器等；这些编辑器都提供了一个图库，这使得可以在一个特定的类里去选择 一个待编辑的对象或属性，例如在植物器官类别里，选取树叶的形状等等。 该软件功能较强，理论上能生成各种植物图形。然而使用复杂，交互性差， 对计算机要求较高。 1 5 当前存在问题及发展前景 分形的研究在上世纪七十年代得到了很大的发展，但这并不意味着分形的研 究已经达到了可以表现任何形式的事物的程度。在这一领域，还有很多尚未被人 们发现和应用的知识存在。随着计算机图形学与形式语言在分形中的应用不断深 入，使得本文的研究具有很高的理论及应用价值，然而一种新算法的提出与应用 都有一些问题伴随着。 传统的迭代函数系统主要以仿射变换等算法绘制分形图，需要寻找i f s 码或 者调整l y s 码来实现分形吸引子的生成或形状调整，实现复杂，不能实现交互的 硕十学位论文 和实时的分形图形生成。随着对逼真程度和审美要求的不断提高，从简单的 m a n d e l b r o t 集和j u l i a 集，到科幻电影上的分形风景，以及近年来印有分形图案的 时装，都显示出了分形正从科学研究领域走进人们的现实生活中。因此，能用尽 可能通俗易懂的方式，如何在一个实时、交互的信息交流界面，用户可以通过简 单操作计算机，修改少量参数生成分形图形，已成为当前一个被众多的学者所关 注的课题。 虽然l 系统描述具有严格分形结构的植物体形态结构非常精炼，但l 系统在 描述植物的生长过程方面，有一定缺陷。一方面，用参数l 系统能描述植物的生 长过程，但这种形式语言的表示方法却非常繁复。另一方面，l 系统具体编程实 现时，在产生式中将植物的几何结构信息和拓扑结构信息同时描述，理解和使用 都比较困难。还有就是现在的l 系统不重视可视化交互，难以设计造型，难懂难 改，文法的造型含义、语义表达不够准确，控制能力弱，应用研究多于理论研究。 本文针对以上问题，研究了形式化分形造型技术，实现了生成分形图形的i f s 的符号重写系统，并取得了较好的效果。 1 6 本课题的研究内容 主要研究内容如下： ( 1 ) 基于l 系统、i f s 和形式化基本理论提出了i f s 的符号重写算法； ( 2 ) 研究了形式化分形造型系统的文法结构，语义学与形式表达等技术； ( 3 ) 实现了i f s 的符号重写分形造型系统； ( 4 ) 研究了符号重写系统的表达能力，几何控制能力和直观交互性； ( 5 ) 对所提出的算法模型用具体的实例实现。 形式化分形造型技术 第2 章迭代函数系统和l 系统 2 1 迭代函数系统 迭代函数系统是普遍用到的一种生成分形吸引子的算法，它是根据不动点原 理采用几个甚至多个仿射变换生成吸引子的。用到的仿射变换主要有：缩放变换、 旋转变换、平移变换等，其中缩放变换控制图形的缩小，放大；平移变换控制图 形在水平以及竖直方向的变换；旋转变换在三维显示中经常用到。 2 1 1 定义 一个迭代函数系统由度量空间僻，d ) 与定义在其上的一组压缩映射变换 ：x 呻x ，n l 2 ，n 所组成( 用i f s 表示) ，记为： x ；，n 一, 2 , - - ，) ；如 果的压缩比为，n ；l 2 ，则称s m a x s , ：刀一l 2 ， 为此i f s 的压缩 比【蚓。 定理1 ( 压缩映射不动点定理)设 x ；o j ，n 一1 ，2 ，) 是完备度量空间 僻，d ) 上的i f s ，压缩比为s ，变换形仁) 由下式定义： 朋一u q ，v b e h ( x ) 则矽是( h ( 均，h 。) 上，压缩比为s 的压缩映射，即缈p ) ，形( c ) ) ss h d 俾，c ) ， v b ，c 日僻) 且存在唯一的不动点( 不变集) a e h ( x ) 满f f ：a - w ( a ) - u 铭似) ， 并且对任意的b e h ( x ) ，a 一m 矿p ) 。不动点a h ( x ) 称为这个i f s 的吸引 子。一般说来，i f s 的吸引子就是分形。 定理2 ( 拼贴定理)设( x ，d ) 为完备度量空间，给定l e h ( x ) 和 0 ，选 定一个i f s x ；，n ；1 2 ，) ，其压缩因子为0ss o ，其中善易。1 。取x x 并且依照递归方式独立的可取 吒似也一1 ) ，也一1 ) ，一、瓴一1 ) ) n - 1 , 2 n 其中事件x = ；( x 厅一1 ) 的概率是见。构造一个序列以，玎= 0 1 1 “册，则序列 似，n - 0 ，p 册在一定条件下收敛与迭代函数系统的吸引子。 根据生成图形的维数来确定可以有6 个( - - 维) ，也可以有1 2 个( 三维) 。 通常二维仿射变换的形式可以表示如下： 形( ；) 2 ( 兰三) ( ；) + ( ；) 其中口，b 参数为x ，y 上的缩放变换参数；c ，d 控制图形的旋转；p ，厂为x ，y 方向上的平移分量。a ，b ，c ，d ，e ，厂均为实数。 圣) 2 ( 至；妻 三) + ( 三 卜6c 、l 式中1 ，刀，m 表示在三个方向上的平移量，矩阵彳= ld 厂gi 产生比例、旋转、 lhj kj 图2 1 if s 随机迭代算法生成分形流程图 在用迭代系统生成吸引子时，为了使生成的吸引子更自然，继而在绘制分形 图采用随机迭代函数系统，正如随机生成算法所描述的一样引入一随机变量p ；。 b 代表各个仿射变换被使用的概率。随机迭代算法绘制的i f s 吸引子实质上按照 概率选取不同的映射，不断映射得到新点和画点的过程。概率a 的求取由下式求 出： b 。牲，f ，l 2 ， | d e t 4 l 式中4 。( ：i ) f 。l 2 ，v 。如果i d e t 4 l = 0 n 可取个极小的实数 例 如以n2 00 0 0 0 1 ，之后调整其他概率，以确保只。l 山e 述可知i f s 生成分形图形算法简单，宴现容易，h 时也可以看到，利用 i f s 牛成分形的核心是确定压缩仿射变换及其系数。 枷i f s 码由表2 1 给出，依据随机迭代算法，叫得蕨叶如图22 所示 表2 1 生成蘸叶i f s 码 印 2 1 4 带参量迭代函数系统 图22 蘸叶 惜参量的i f s 有助于动态的i f s 分形吸引子的牛成。所谓带参量即是在映 射中再加进一个参数p ，使之成为w ( p ，、。 引理21 设( p ，d 。) 是度量空，( j ，d ) 是完备度量空州，w ：p x 冲x 是 卫e 的组压缩因了为s 的压缩映射，即对每个p p ，w ( p ，1 是x 上的雎缩映 射。如果对于每个z x ，w 是p 上的连续函数，则w 的不动点：p 一并是连 续函数。 引理2 2 设( p ，d 。) 足度量空问，( x ，d ) 足完备度量空叫，w ：p x 一工， 月= 1 ，2 ，_ v 是卫上的纽依赖十参数p 的连续变换，h i 埘每个固定的p p ， k ( p ，z ) 是p 卜的连续函数。定义 w ：h ( x ) 呻h 皑) ，w 佃) = w ( b ) u ) uu h 0 ( 口) 对任意的口h 瞄) ，则对于缚个b h ( 爿) ，w 是h ( x ) 上的对于p 的连续函数 形式化分形造型技术 定理设( x ，d ) 是度量空间， x ；( ) ，暇，) 是一个( 带凝聚集) f l j i f s ， 压缩因子s 。m a x $ n ：忍。1 ，2 ， ，如果每个睨都连续依赖于参数p e p ，p 是 紧度量空间，则吸引子彳( 尸) 何( x ) 就是按h a u s d o r f f 度量h ( d ) 连续地依赖于 p e p 。 该定理告诉我们，通过调整变换中的一些参数，可使吸引子得到连续的控制。 2 1 5 再归迭代函数系统 设( k j ，d ，) 为紧度量空间，f 仕2 ，n ) ，( h ；，红) 为相应的以h a u s d o f f f 距 离及k ，上的紧子集组成的紧度量空间。 定义映射雌f ：日f _ h ；，对任意的o ，j ) e i ，此处，表示具有如下性质的目 录对：即对每一个f 仙2 ，) ，总有一个仉2 ， 与之对应，也就是若 o ，j ) e i ，则存在对于任一个f ，有，o ) 一 j io ，j ) e i 一妒成立。同时映射满 足： 魂( ( b )