（计算机应用技术专业论文）基于图形重写的分形造型系统研究.pdf

硕+ 学位论文 摘要 分形几何被称为“大自然的几何学”，诞生于2 0 世纪7 0 年代，主要用来刻 画不光滑、不规则的几何形体。分形形态广泛存在于自然界。目前分形已经涉及 到数学、物理、化学、材料科学、生物与医学、地质和地理学、地震和天文学以 及计算机科学等领域。随着分形理论的发展，分形造型越来越受到人们的重视， 计算机分形造型已经成为计算机图形学领域重要的研究课题之一。 本文研究的是基于图形重写的分形造型系统。 论文首先回顾了分形理论的诞生，论述了分形理论与计算机图形学相互促进 发展的关系，之后介绍了基本的分形理论，包括自相似性和自仿射性、无标度性、 分维的概念、分形的基本特征，并深入研究了l 系统和迭代函数系统。 最后参照已有的分形造型系统的优点，包括形式语言表达、直观的图形替换 生成过程等，设计了基于图形重写的分形造型系统。根据图形替换图形的原则， 给出了基于符号描述的图形重写系统的定义，并根据符号系统的文法复杂度和从 应用的角度考虑，对图形替换系统进行了分类，对实现图形替换图形的多种可能 性进行了探讨。其中，重点分析了上下文无关的图形替换系统的常见结构、处理 方法，详细论述了图形重写系统与迭代函数系统和l 系统的关系。图形重写系 统与迭代函数系统相比，不要求变换的压缩性质，对再归的控制更加简单，支持 非线性和无限制替换关系；与l 系统的最大区别是使用自定义符号文法替代确 定文法描述，使得替换过程不再限于两点控制格式及相关的几何处理过程，支持 任意仿射变换和特定的非线性变换，支持基本图形集和造型方法。结果表明图形 重写系统是比l 系统和迭代函数系统更简单，造型能力更强，构图过程更为直 观的分形建模系统。 关键词：图形重写系统；图形迭代系统；迭代函数系统；l 系统；分形。 a b s t r a c t f r a c t a lg e o m e t r yi sc a l l e d ”n a t u r e sg e o m e t r y , w h i c hw a sb o r ni nt h e 19 7 0 s i t 1 sm a i n l yu dt od e p i c tg e o m e t r ys h a p e so f i r r e g u l a ro rr o u g h m a n yf a c t ss h o wt h a t i r a c t a lw l d e l ye x i s t si nt h en a t u r e ，a n ds p r e a d sa l lo v e rf i e l d ss u c ha sm a t h e m a t i c s p h y s l c s ，c h e m l s t r y ，m a t e r i a ls c i e n c e ，b i o l o g ya n dm e d i c i n e ，g e o g r a p h y ，e a r t h q u a k e a n da s t r o n o m y ，c o m p u t e rs c i e n c ea n ds oo n w i t ht h e d e v e l o p m e n to ff r a c t a lt h e o r v ， 1 n c r e a s l n g l y1 m p o r t a n c eh a sb e e na t t a c h e dt ot h ef r a c t a lm o d e l i n g n o w a d a y s ，f r a c t a l m o d e l m gh a sb e e no n eo fi m p o r t a n tr e s e a r c hp r o g r a m si nc o m p u t e r g r a p h i cf i e l d ：h e 嫩1 n 舱s e a r c ho b j e c to f t h ep a p e ri saf r a c t a lm o d e l i n gs y s t e m b a s e do n t h i sp a p e rr e v i e w e dt h eb i r t ho ff r a c t a l t h e o r ya n di t 8r e l a t i o nw i t ht h e c o m p u t e rg r a p h i c ，d e s c r i b e dt h eb a s i cf r a c t a lt h e o r yu s e di nt h ef r a c t a l m o d e l i n g ， 1 n c l u d i n gs e l f - s i m i l a r i t ya n ds e l f - a f f i n i t y ，s c a l e l e s s c h a r a c t e r ，f r a c t i o n a ld i m e n s i o n a n dt h eb a s i cc h a r a c t e r i s t i c so ft h e f r a c t a l a n dt w oe x i s t i n gf r a c t a l m o d e l i n g s y s t e m sw e 阳r e s e a r c h e d t h o r o u g h l y ，i n c l u d i n gl s y s t e ma n di t e r a t e df u n c t i o n s y s t e m t 1 n a 儿y ，w ec o n s u l t e dt h e o r i g i n a lf r a c t a l m o d e l i n gs y s t e m s ，i n c l u d i n gt h e e x p r e s s l o no ff o r m a ll a n g u a g e ，t h ev i s i b l em o d e l i n gp r o c e s so f r e p l a c i n gg r a p h i cb y g r a p h l c ，b u i l tt h ef r a c t a lm o d e l i n gs y s t e mb a s e d o ng r a p h i cr e w r i t i n g i nl i n ew i t h t h ep r i n c i p l eo fr e p l a c i n gg r a p h i cb y g r a p h i c ，g r a p h i cr e w r i t i n gs y s t e mb a s e do n s y m b o ii sd e f i n e di nt h i sp a p e r t h e r ea r eac o u p l eo f p o s s i b i l i t i e si nt h ep r o c e s so f 托p l a c i n gg r a p h i cb yg r a p h i co ft h en e ws y s t e m ，a c c o r d i n gt ot h e c o m p l e x i t vo f s y m b o ls y s t e ma n da p p l i c a t i o nr e q u i r e m e n t ，ac l a s s i f i c a t i o no fg r a p h i cr e w r i t i n g s y s t e mi sm a d e t h ep a p e rf o c u so na n a l y z i n gc o n t e x t f r e eg r a p h i c e w r i t i n gs y s t e m , 1 n c j u d l n g i t s u n i v e r s a l s t r u c t u r e s ，p r o c e s s i n gm e t h o d sa n dr e l a t i o n s h i pw i t h l s y s t e ma n di f s c o m p a r e dw l t ht h ei t e r a t e df u n c t i o ns y s t e m ，t h en e w s y s t e md o e sn o tr e q u i r e t h a tt h et r a n s f o r m a t i o nm u s tb ec o m p r e s s e d ，a tt h es a m et i m e ，t h e n e ws v s t e mc a n c o n t r o lt h ef r a c t a lg r a p h i co fr e c u r r e n ti n t e r a t e de a s i l y ，s u p p o r tt h e r e p l a c e m e n to f n o n - l i n e a ra n du n r e s t r i c t e dr e l a t i o n s ；t h eb i g g e s td i f f e r e n c ew i t hl s y s t e mi s t h eu s e o fc u s t o m i z i n gs y m b o l sg r a m m a r ，m a k e st h e r e p l a c e m e n tp r o c e s si sn o1 0 n g e r n m l t e dt ot h ec o n t r o lo f t w o p o i n tg e o m e t r ya n dt h er e l e v a n tp r o c e s s e s ，s u p p o r tf o r i i 硕十学位论文 a r b i t r a r ya f f i n et r a n s f o r m a t i o na n dt h es p e c i f i cn o n l i n e a rt r a n s f o r m a t i o n ，s u p p o r t f o rb a s i cg r a p h i c ss e t sa n dm o d e l i n gm e t h o d s t h er e s u l t ss h o wt h a tg r a p h i c r e w r i t i n gs y s t e mi ss i m p l e rt h a nl s y s t e ma n di f s f u r t h e r m o r e ，i th a ss t r o n g e r m o d e l i n ga b i l i t ya n dm o r ev i s i b l em o d e l i n gp r o c e s s k e yw o r d s ：g r a p h i cr e w r i t i n gs y s t e m ；g r a p h i ci t e r a t e ds y s t e m ；i t e r a t e df u n c t i o n s y s t e m ；l s y s t e m ；f r a c t a l i i i 摹丁图形重写的分形造犁系统研究 图1 1 图1 2 图2 1 图2 2 图2 4 图2 5 图2 6 图3 1 图3 2 图3 3 图3 4 图3 5 图3 6 图3 7 图3 8 图3 9 图3 10 图3 1 1 图3 1 2 图3 13 图3 1 4 插图索引 分形生长集团实例3 随机模型构造海岸线一4 k o c h 曲线的自相似9 s i e r p i n s k i 三角形的自相似10 k o c h 曲线的面积12 l 系统构造植物2 0 三维龟行几何2 0 图形迭代原理图2 3 k o c h 曲线的图形迭代生成2 3 图形迭代构造分形2 4 初始元为三条线段的图形迭代一2 4 k o c h 曲线的代数映射生成：2 6 非压缩变换构造雪花图案2 8 龙曲线的o g r s 表示图形31 含几何常量的0 。g r s 表示和分形集3 2 使用信息控制的图形及等价的产生式3 3 一个简单的艺术图形3 3 多产生式的0 g r s 3 4 相近初始元的图形重写3 5 不同初始元的图形重写3 6 变换不同的图形重写3 6 i v 兰州理工大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其 他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果 由本人承担。 作者签名：硅支枷日期：如如年衫月衫日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学 校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权兰州理工大学可以将本学位论文的全部或部分内容 编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文。同时授权中国科学技术信息研究所将本学位论文收录到中 国学位论文全文数据库，并通过网络向社会公众提供信息服务。 作者签名： 导师签名： 日期：睥f 月日 日期印，年月乡 日 硕十学何论文 1 1 课题的研究背景 第1 章绪论 传统的欧氏几何通过直线、圆、抛物线等简单曲线来建立现实世界中的各种 形状模型，所描述的几何对象是光滑和规则的。然而现实世界中规则理想的对象 少之又少，正如分形的理论创始人m a n d e l b r o t 所说：“浮云不是球形的，山峰不 是锥体的，海岸线不是圆圈，树干不是光溜溜的，闪电也永远不会沿直线行进。 大自然的鬼斧神工造就了随处可见的不规则事物，描述这类事物需要的几何不仅 仅是直线、圆或抛物线，不能再以简单理想的体系去对待。传统的欧式几何在多 姿多彩的大自然面前显得无能为力。我们必须寻求新的数学工具，才能对客观世 界更好地认识和把握。 2 0 世纪7 0 年代，m a n d e l b r o t 把分形维的概念、客观事物固有的自相似与无 限可细分的特性以及计算机强大的递归运算功能结合起来，形成了分形的概念。 分形几何的基本思想是：客观世界的许多事物，都具有自相似的“层次 结构， 无论放大或缩小多少倍，几何尺寸的变化不会改变图形结构，其局部和整体具有 统计意义上的自相似性。 分形的研究对象是不规则而又自相似的几何形状，曲曲折折的海岸线，绵延 起伏的群山，变幻多姿的浮云，九曲回肠的水流，纵横交错的大地褶皱，枝丫横 生的参天大树，分形为真实地再现这些客观事物提供了有效的数学模型，被称为 “大自然的几何学 n 卫1 。 今天，分形已经形成了具有广泛应用价值的理论体系。分形几何学首先被引 用到自然界和物理学中。在显微镜下观察，我们会看到落入溶液中的一粒花粉， 在不间断地作无规则的布朗运动，这是花粉在大量液体分子的无规则的高频率碰 撞下表现的平均行为。布朗粒子的轨迹由各种尺寸的折线连成。只要显微镜有足 够的分辨率，就可以发现布朗粒子轨迹貌似直线段的部分，其实是由大量更小尺 度的折线连成的。布朗粒子轨迹是一种处处连续，但又处处无导数的曲线，这条 曲线的维数为2 ，高于它的拓扑维数l ；在某些电化学反应中，电极附近沉积的 固态物质，像不规则的树枝一样向外生长；受到污染的江河湖泊里的藻类植物上， 不断有新的颗粒和胶状物的沉积和增长，成为带有许多须须毛毛的枝条状。这些 都可以使用到分形几何口】。 除了数学、物理这些基础领域，分形的影响力已经涉及到建筑6 1 、金融7 1 、 材料伯1 、医学阳1 等很众多领域。分形被用来研究天文、地理地质、生命等自然 基丁图形重写的分形造型系统研究 现象；被用来研究股票的涨落、分析企业的发展n 引、预测农作物的价格1 ，自 然科学、人文经济分形的普及无处不在。这就对计算机分形造型提出了更高 的要求，同时也促进了计算机图形学的发展。 分形几何的创建和发展跟计算机图形学密切相关。计算机擅长重复运算的特 性和分形的固有几何特性，使计算机造型技术与分形理论的发展相得益彰。 一方面，计算机图形学为分形几何提供了理想的描述工具，使分形具有无限 细节层次的结构得以完美展现。这种直观的数学美更容易为大众所接受n 2 1 4 1 ，也 为分形在各行各业的渗透、吸引更多的研究者对分形做进一步的研究做了很好的 铺垫。 另一方面，分形纷繁而又有序，为计算机提供了紧凑而又有效的存储复杂对 象详细结构的方法，使计算机能够使用较小的存储空间生成逼真自然的复杂图 形。分形是计算机图形学描述形形色色的复杂事物的有效工具。分形图形形态复 杂，然而如此复杂、具有精细结构的图形却能够通过简单的规则迭代生成。如同 现实世界中的许多真实的客观事物一样，分形构造的实际对象模型可以通过放大 得到更多更详细的内容，这是符合我们生活规律的一种特性。比如描绘一处草坪， 远处看时，我们无需太多细节，只需画出草坪的整体就可以。但当我们走近时， 我们却需要能够看见草坪的叶片。分形提供给我们一种根据距离远近生成恰好数 量的草叶的方法，而不需要巨大的存储量或庞大的数据库。 现在，分形在计算机图形学的应用已经非常普遍，即使是一般的计算机使用 者，也一定多多少少地接触过以日历、海报、杂志封面等形式出现的分形作品。 许多电影公司也越来越注重利用分形方法创造出细致、真实、奇特的场景模拟， 并且已经做了不少开拓性的工作。好莱坞很多为我们大家熟知的影视作品的处理 中都有分形的参与。比如影片杰蒂的轮回以及星际旅程i i ：可汗的愤怒 中就有许多分形风景画。分形在计算机图形学领域的应用领域取得了不错的成 绩，尤其在仿真、数据压缩领域n5 1 6 】，分形的成就是公认和令人瞩目的。 多年来分形造型技术的研究倍受研究者和分形爱好者关注，并且吸引了越来 越多的学者专家投身其中。对分形造型技术的研究已经成为计算机图形学的重要 内容之一。 对分形的建模一般要求逼真地再现客观自然，能够依据距离远近给出相应的 细节，尽可能简单并且具有数据放大能力，能够交互式修改，并且有较高的生成 效率和尽可能宽的适用范围。 多年的研究出现了很多分型造型模型，诸如d l a 模型( d i f f u s i o n l i m i t e d a g g r e g a t i o n ) 、图形迭代系统( g r a p h i ci t e r a t e ds y s t e m ) 、代数映射系统、随 机模型、l 系统、迭代函数系统( it e r a t e df u n c ti0 1 3s y s t e m ) 等等。 2 1 2 分形造型的发展及研究现状 在深入分形造型技术研究之前，考察一下分形造型的发展是非常有必要的。 返些过往理论的出现及演变对我们的研究有着鼋要的启发，足我们深入研究分形 造型的起点。 1 9 8 1 午，阿位美国大学教授w i t t e n 和s a n d e r 介绍了他们所做的计算机模 拟实验。他们将初始粒予作为种子固定在二维网格平面中心，在远离种子的位置 产生一个粒子做随机行走，然后直至该粒子向中心种子凝聚，然后再产生一粒子， 重复上述操作，最终计算机屏幕上显示的模拟结果是自然界的树枝状斑图。他们 把这称作扩散限制凝聚模型( i ) i f f u s i o ni m i t e da g g r e g a t i o n ，简写为d l a ) 。 对这些树枝状斑图研究表明它们的维数是值为1 6 6 的分数维，且具有自相似 性和标度不变性，是一种分形集。 d l a 模型的分形结构在形成过程中都遵从可动边界的拉普拉斯方程。目前， 在自然界中已经发现的物理、化学和生物过程所形成的d l a 模型结构类型有上百 多种m ”1 。 d l a 模型用非常简单的算法抓住了广泛的自然现象的关键成分，通过简单的 运动学和动力学过程产生了具有标度不变性的自相似的分形结构，从而建立分形 理论和实验观察之问的桥梁，在一定程度上揭示出实际体系中分形生长的机理： 但是，利用d l a 模型模拟的图形的分形维数计算复杂，很难直接得到。这也是 d l a 模型的一个严重缺陷。 ( a ) 视网膜血管 ( b ) 多孔介质的化学j 吝解 图11 分形生长集团实倒 i t u t c h i n s o nj 在1 9 8 1 年发表的论文中给出了自相似集合的数学理论基础 ”。次年，m a n d e l b r o t 出版“1 h ef r a c t a lg e o m e t r yo fn a t u r e ”。在这部后来 成为分形里程碑之的著作中，m a n d e l b r o t 使用了图形迭代“”的分形建模系统。 同年，fmd e k k i n g 推广了m a n d e l b r o t 关于图形迭代的思想，使用代数映射系 统构造分形“。 基丁图形重弓的分形造型系统研究 1 9 8 2 年a l a i l lf o u r n i e r 、d o n f u s s e l l 和l o r e nc a r p e n t e r 提出随机插值模 型。该模型擅长模拟山和海岸线等自然景象，通过一个随机过程的采样路径构造。 比如对海岸线的模拟，首先需要选择模拟景物的初始特征点，相邻两点连成线段， 再取相邻特征点的中点，也就是线段中点，并沿其垂直连线随机偏移一个距离， 之后再将偏移的点与两个初始特征点分别连成线段循环下去，可以得到一条 具备无穷细节的曲折的海岸线心引。 图1 2 随机模型构造海岸线 1 9 8 3 年，w t r e e v e s 提出了随机模型，用大量的形态和位置随时间变化的 粒子图元描述景物，用一组预定义的随机过程说明每个粒子的状态和动力性质。 粒子系统是一个有“生命 的系统，这些粒子都有各自的生命周期，在系统中都 要经历“产生 、“生长 及“消亡 的阶段。因此粒子系统适合刻画动态变化的 景物，常用于模拟结构性较弱的跳动的火焰，变换的烟云，被微风吹拂的草以及 自然界中的雨、雪等动态景物乜3 一们。 1 9 8 4 年及1 9 8 6 年，a r s m i t h 和p p r u s i n k i e w i c 分别将l 系统引入计算机 图形学心乳2 引。从此代数映射系统分形造型被l 系统分形造型取代。l 系统理论 原本是美国生物学家l in d e nm a y e r 于1 9 6 8 年提出的用于描述植物形态发生和生 长过程的一种方法阻7 l ，和分形图形学结合以后引起了计算机界人士的极大兴趣， 一时间发表了很多论文和专著。l 系统原理浅显，方法简单，构成分形图快捷， 且在描述植物拓扑结构方面的明显优势，众多的研究者对l 系统的符号定义进 行扩展；e ic h o r s t 等人提出了随机l 系统以避免l 系统构建的图形过于呆板； h e r m a n 等人又将l 系统拓展为d 2 l 系统，以使图形各个模块间产生关联；三维l 系统，参数l 系统等更增强了l 系统的表达能力心8 。3 。 1 9 8 5 年，m ic h a e lf b a r n s l e y 开始应用迭代函数系统来构造分形图形2 3 引。 迭代函数系统程序简单易行，几何含义明了，除了限制压缩变换，迭代函数系统 较l 系统造型功能更为强大。带凝聚的迭代函数系统，再归迭代函数系统，随机 迭代函数系统以及带参数的迭代函数系统的出现4 3 5 1 ，使迭代函数系统理论进一 步完善。 图形迭代系统和代数映射系统昙花一现，在后来的年代里再没有发展。而l 系统和迭代函数系统则后来居上，发展成目前影响深远广泛应用的分形建模系 4 硕十学位论文 统，对l 系统或迭代函数系统的改进也一直是学者们的分形研究的重要工作之 一。 加拿大c a l g a r y 大学的p r u s i n k i e w i c z 等人参与了开发参数化l 系统、微分 l 系统、开放式l 系统6 1 等重要理论的研究，l 系统的表达能力进一步得到增强。 他们根据l - s y s t e m 原理编制了l s t u d i0 软件。使用者需要利用预定义符号，输 入虚拟植物的l s y s t e m 产生式，即可生成虚拟植物的图形口7 | 。 意大利的的一位学者基于迭代函数系统仿射不变理论提出一种新的a i f s 系 统，在仿射不变的情况下，a if s 可以定位吸引子和描述吸引子的整体形状，也 就是吸引子形成的分形图形。对于基本分形，a i f s 是一种可预知的建模；同时， a i f s 可以用于生成与现实世界相似的树，或是其他与自然界中分形形态及生物 属性非常相似的模拟图形a i f s 可以模拟植物的生长，渐变生成自然的不规则图 形3 8 1 。 美国伊利诺斯州立大学计算机系p a u ls h e r m a n 和j o h nc h a r t 给出了一种 分形图形的生成算法口引。根据他们的算法，对于周期迭代函数系统生成的分形 对象，用户可以指定分形吸引子上的特定点，拖曳吸引子上的其他点到用户需要 的位置，通过这样的操作直接改变吸引子的形状。通过扩展的牛顿迭代法，他们 找到了一个等价的满足约束条件的新的迭代参数集。 b u r c h 等通过极值分解的方法分解迭代函数系统仿射变换的线性部分矩阵， 实现了二维及三维迭代函数系统线性分形变形算法n0 i 。t a oj u 研究了仿射变换 迭代函数系统和递归龟图几何生成分形图算法n 。t o m e km a r t y n 提出了吸引子 变形的正确性标准以及新的迭代函数系统分形变形算法引。h s u a nt c h a n g 提出 了分形图形的合成方法h 引。 在国内，魏小鹏通过研究传统的迭代函数系统拼贴建模方法，利用整体和局 部的组合关系及相似关系，提出了两种简化的拼贴建模方法：局部轮廓法和三点 法，并分析了迭代函数系统拼贴建模方法、局部轮廓法和三点法各自适用的不同 的条件，讨论了它们的具体实现技术h 钔。 车明等人找到了一种参数控制方法h5 j ，可以通过对参数的控制改变和影响 迭代函数系统吸引子的形状。该方法首先提供两个初始三角形，通过对两个三角 形位置和形状的改变来影响迭代函数系统的吸引子。 华南理工大学工业设计与图学研究所的李哲林等人尝试了将分形图形贴在 三维物体表面的算法。他们将三维球面作为空间投影面，把经典的m a n d e l b r o t 集投影在球面上，突破了平面上生成分形图形的传统贴图方法。他们还论证了很 多空间实体都能近似分解成球面和柱面，同样也都可以采用类似的方法来处理， 这种算法极具应用价值h 6 1 。 李庆忠、韩金姝对l 系统和迭代函数系统取得的已有成就进行改进，利用l 5 摹丁图形币弓的分形造型系统研究 系统擅长对植物拓扑和生长的特点，以及迭代函数系统擅长刻画植物细节纹理的 特点，提出了l 系统和迭代函数系统相融合的方法，该方法可以自由逼真地模拟 植物的拓扑结构和细节纹理h 引。 王铁红研究了迭代函数系统的符号表示并建立了if s 的符号重写系统。该系 统是根据迭代函数系统生成吸引子的过程及其仅使用压缩仿射变换的特性建立 的。与i f s 一样，受到压缩仿射变换的限制，但其算法比迭代函数系统的确定性 算法和随机迭代算法生成吸引子更加直观。i f s 的符号重写系统有较强的造型能 力和表达能力h 引。 还有其他很多专家学者在迭代函数系统和l 系统以及分形其他领域的研究 和实践n 9 5 。 这些相关的研究探索，对我们的研究有一定参考价值。 分形造型发展到今天，l 系统和迭代函数系统在造型方面各有所长，并且都 取得了不菲的成绩，同时又各自受到一些制约我们从分形造型的历史中受到启 发，结合代数映射系统和图形迭代系统，参照l 系统和迭代函数系统的表达和内 部结构，用更具有一般意义的图形重写( g r a p h i cr e w r i ti n gs y s t e m ，简写为g r s ) 来构造分形，使其既有l 系统构造植物的优势，又不限制压缩，比迭代函数系统 和l 系统具有更普遍的造型意义。 1 3 课题的研究内容 图形重写以图形替换为原则，涉及到以下几个方面的问题： ( 1 ) 图形的自然表示体系与图形变形的控制方法。 何图形都可以当做点的集合。可以选取其中的特征点作为控制对象进行变形 控制。图形也可以用点、线( 含曲线) 、多边形( 含闭曲线的区域类型) 等基本 集合元素来构成，可以建立基本图元集并用基本图元的控制点进行变形控制。也 允许组合图形的整体变形模式。也就是，系统要将几何图形与变换在交互编辑时 视为相同的。 ( 2 ) 变形控制的变换提取。 从几何的基本表示中确定变换或变形的直接对应关系。精简控制的变换控制 与约束条件和组合图形带局部变形的高次变换与约束确定变形控制体系。 ( 3 ) 图形重写系统的内部结构。 对课题所做的工作主要包括有以下几个方面： ( 1 ) 研究已经存在的分形造型方法，包括图形迭代系统、代数映射系统、l 系统、迭代函数系统，对应的构造了图形重写的表示体系，研究了图形重写系统 和l 系统迭代函数系统的关系。 ( 2 ) 研究了l 系统的分类方法，对图形重写做了相应的分类。 6 硕十学位论文 ( 3 ) 研究了图形重写的常见结构和处理方法。 1 4 课题的意义 基于图形重写的分形造型系统研究课题研究意义有： ( 1 ) 自然界中存在大量的非规整的分形结构对象，分形形态是自然界普遍 存在的现象，如同m ic h a e lf b a r n s l e y 所说，分形对象无处不在。而被称为“大 自然的几何学”的分形几何是描述客观世界的有效工具，分形造型系统是分形理 论的一支。对分形造型技术的研究能够丰富分形理论，促进其发展，同时也是对 自然界复杂事物客观规律的一种有意义的探索。 ( 2 ) 分形是一门新兴的科学，近些年来发展很快，已经在生物与医学、材 料科学、工程技术、天文学、气象学、地质与地震学、管理学、计算机科学等领 域得到应用，分形理论的发展以及对分形造型技术的研究都会对相关领域或行业 有着一定程度的影响，很多传统的科学难题，因为分形的介入而取得了显著的进 展。在计算机图形学领域分形造型领域，分形已经具有相当重要的地位，对分形 造型技术的研究必然直接影响计算机图形学的发展。所以，本研究课题有着广泛 的实用价值。 ( 3 ) 现有的分形造型技术都存在一定的缺憾。图形迭代系统是比较早的分 形造型系统，遵循了图形替换图形的原则，但是初始元一般都是一条条的线段。 且因为没有形式语言的介入，构造过程对一般的分形爱好者和程序设计者都比较 费力。代数映射系统采用自定义符号，是最早使用形式语言的分形造型系统，但 是并没有深入地发展下去。迭代函数系统运用压缩仿射变换和不动点定理，使图 形生成依赖于一组仿射变换。该造型方法适用面广，程序实现简单易行，几何含 义明了，但受限于压缩仿射变换，并且i f s 具有严格的自相似性，缺乏对事物拓 扑结构的控制。l 系统是不限制压缩的，对生长规律具有较强的拓扑性的景物， 尤其是植物的模拟，逼真度很高。但是其替换图形只局限于线型，使用变换不够 丰富。 ( 4 ) 图形重写基本思想来源于代数映射系统和图形迭代系统，同时又参考 了l 系统和迭代函数系统的表达及内部结构，与迭代函数系统相比，不要求变换 的压缩性质，对再归的控制更加简单，支持非线性和无限制替换关系；与l 系统 的最大区别是使用自定义符号文法替代确定文法描述，使得替换过程不再限于两 点控制格式及相关的几何处理过程，支持任意仿射变换和特定的非线性变换，支 持基本图形集和造型方法。图形重写系统是比l 系统和迭代函数系统更简单，造 型能力更强，构图过程更为直观的分形建模系统。 7 基丁图形币弓的分形造型系统研究 1 5 论文的组织结构 第一章论述了课题的研究背景、分形造型的发展及研究现状、课题的研究内 容和研究意义。 第二章围绕分形图形的基本特征介绍了分形的基本理论，包括分形中自相似 与自仿射的理论、分形的无标度性、分形维数和对分行的定义的探。最后对目前 应用最为广泛的两种分形造型系统做了较为详细的介绍。 第三章以图形替换图形为原则，定义了基于符号描述的图形重写系统，根据 符号系统的文法复杂度和应用的需求对图形替换系统进行了分类，并重点分析了 上下文无关的图形替换系统的常见结构、处理方法以及与迭代函数系统和l 系统 的关系。并得出图形替换系统是比l 系统和迭代函数系统更简单，造型能力更强， 构图过程更为直观的分形建模系统的结论。 最后是结论与展望。对本文的研究工作进行了总结，并对课题的进一步研 究做了展望。 8 硕+ 学位论文 第2 章分形基本理论 2 1自相似性和自仿射性 分形的自相似性是指分形局部具有整体的特征。自相似性和自仿射性是分形 图形的基本特征。 分形无处不在，大自然中具有自相似特性的分形形态俯拾皆是。繁密树木上 旁逸斜出的一条条树权和整棵树木，弯曲的的支流和整体河川，蜿蜒曲折的海岸 线的一段和整条海岸线，都存在几何特性上的相似性。羊齿树叶也是一个一目了 然的具有自相似分形结构的例子，支配羊凿树树叶的全体的规则同时也支配左右 分开的树枝的一个一个小叶，而且对小叶中的小叶也是如此。 数学上的许多分形构造都具有很明显的自相似性。k o c h 曲线是经典的分形 图形，也是很有代表性的分形自相似的例子之一。其构造初始图形为区间在 o ，1 上的一条线段，第一步以该线段上 1 3 ，2 3 的区间为底，做一个等边的三角形， 方向在 0 ，1 线段的上方；然后将初始图形中 1 3 ，2 3 区间的线段去掉，得到一 条四段的折线；再对新产生的两条折线和初始图形剩下的 0 ，1 3 和 2 3 ，1 区间 的线段分别作与第一步相同的操作，得到一组新的折线，重复上述操作步骤直到 无穷，便得到一条具有自相似几何结构的k o c h 曲线。无论将k o c h 曲线的各个部 分放大多少倍，我们都会看到与整体曲折走向形状相似的、有着更多具体细节的 图形。 图2 1k o c h 曲线的自相似 s ie r p i n s k i 三角形也是自相似的分形图形。考虑一个等边三角形，取三 边中点，连接，则原来的等边三角形被等分成四个小三角形，抛开中间一个三角 形，将其余三个三角形依前法炮制，分别四等分为更小的四个三角形，同样都去 9 基于图形币写的分形造型系统研究 掉中间一个三角形，然后再对剩下的三角形同样四等分，去掉中| 自j 的三角形 如此无尽的四等分下去，最终得到一个s ie r p in s k i 分形垫片( 图见2 2 ) 。同前 面k o c h 雪花的例子一样，将s ie r p in s k i 三角形的任一部分逐级放大，无论放大 多少倍，都会出现和整体一样的结构，并且在这个新出现的结构中有着更多更详 细的结构。 图2 2sie r pin s ki 三角形的自相似 自仿射性拓宽了分形的概念。如果将局部到整体在不同方向上的等比例变换 看作自相似变换，说它们具有自相似性，那么自仿射则是指局部和整体在不同方 向上的不等比变换，变换前后的对象具有的自仿射性。 与欧拉几何对象具有放大极限不同，数学上的分形对象是无穷嵌套的结构 上面的两个例子，无论是将它们放大两倍还是放大十倍、百倍，得到的图形都是 一样的，且与没有放大前的图形一样包含无穷层次的结构。 当然，大自然中存在的分形并不能无穷嵌套，嵌套只发生在有限层次区间中， 当以足够小的比例观测时，自然界中的分形特征就消失了。真实世界中的除了完 全的自相似，在大多数情况下其自相似性有着更为复杂的形式，很多相似只在 统计意义下存在，并不是局部放大一定倍数之后和整体完全地吻合。但在统 计意义下，自然分形对象的结构特征的自相似性同数学上的分形一样，存在 于整体与部分、部分与部分之间。虽然任何现实生活中的事物都不可能是数学 上完全的理想状态，然而这却不会影响分形对客观世界的逼真模拟。实践表明分 形模拟尽管不是最精确的但却能和真实非常接近。很多分形模拟的植物，枝干自 然，纹理细腻，甚至可以和实物的照片相媲美隋朝，甚至能达到以假乱真的效果， 自相似性和自仿射性是分形复杂表面后隐藏的简单。因为存在分形整体和局 部的自相似性，我们才能够通过计算机迭代，从一个简单结构衍生出复杂的图形。 如果没有自相似性，对大部分人来讲，尤其是前面提到数学图形的复杂精细结构， 是没有办法让其如此形象真实地展现的。甚至可以说，对大部分人来讲，一些复 1 0 硕十学何论文 杂的数学构造是没有办法想象的。计算机图形学对分形对象自相似性的利用使数 学更有说服力，从此分形理论真正地打开了局面，开始了对众多领域的普及和渗 透。 2 2 无标度性 计量单位的刻度称为标度，是用一些线或者点表示的间隔标记，用来计量距 离、数额或数量。无标度性也是分形图形的重要特征。 在欧拉几何中，对不同的几何对象，我们可以采用不同的标度去度量。这个 标度可能是长度，质量，或是面积等等。比如长度多少米( m ) 、厘米( c m ) ，质 量多少千克( 堙) 、毫克( m g ) ，或是面积多少平方厘米( c m 2 ) 、平方分米( d m 2 ) 。 不同的物体有不同的特征长度。书本的厚度，人的身高，山的海拔，我们需 要用不同的标度去对应。然而有些对象，比如一个国家的海岸线，潮涨潮落造就 了它们多级层次的不规则特性，是大自然中的分形结构。因为分形的自相似性， 当我们改变标度时，看到的是相似甚至相同的图形哺引。这一方面说明，分形有 它自身的特性存在，标度变换下的分形仍然有其不变性；另一方面也说明，分形 没有确定标度，长度并不能定量地表示它的特征，即不能用长度等标度去描述分 形哺4 删。我们需要从别的角度去把握这种不变性。 2 3 分维 维数是几何形体的重要特征量。 在传统的欧拉几何中，维数只有整数：点是零维的，线段和曲线是一维的， 平面和曲面都是二维的，而几何体是三维的。 我们知道，实施测量必须通过与被测几何具有相同维的几何，才能得到合适 有效的测量值。 例如，我们测一维的一条直线段的长度。当我们用零维的点去测量的时候， 得到一个无穷大的数值，因为直线上包含无穷个点；当我们用二维的平面去测量 的时候，得到的测量值是零，因为线中不包含平面。利用零维的点和二维的平面 都得不到有效值，那么只能用维数介于零维和二维之间的，也就是一维的小线段 去测量，得到的才是可用的数值。 我们前面提到过k o c h 曲线，我们现在采用一维的线段或曲线来测量它的长 度。初始线段长度为1 ，经过第1 步后曲线的长度为三，第二步后曲线长度为1 _ 6 ， 39 当步骤n 趋于无穷时，k o c h 曲线的长度为： 董! ：型：耋垂塑坌! ! 童型耋丝翟圣 l i m 0 ”一 我们再用二维几何来衡量这个图形的面积。 首先用一边为初始线段 0 ，1 ，另两边分别为第21 节k o c h 曲线形成过程中 第步所得的隆起的三角形的最上面的顶点和 o ，1 线段端点的连线的三角彤覆 盖k 0 c h 曲线。根据有关数学知识，这个三角形的面积为鲁，再同同样的方法对 k o c h 曲线的四个小部分用四个小三角形覆盖，由于小三角形的边长均为原来大 的覆盖三角形边长的三分之一，所以四个小三角形的面积为鲁百4 ，同样的方法 再用更小的三角形( 边长为原来小三角形边长的三分之一) 覆盖k o c h 曲线的1 6 个小部分，所得总面积为鲁( ；) 2 ，当循环次数n 趋于无穷时，可以得到 k 0 c h 曲线的面积为鲁唔) k o a 见图23 所示。 八儿n 九 图23k o c h 曲线的面积 综上所述，我们可以得出这样的结论，即k o c h 曲线用一维和二维几何测量 都得不到有限值。那么这个测量只能采用介于一维和二维之间的维数。这也说明 k o c h 曲线不是整数维，分维足存在的。在本次的测量中发现的这个介于一维和 二维之间的维数，就是分维”“。 在用分维解释分形之前之前，数学家们就已经发现了许多像k o c h 曲线这样 的奇怪的曲线。虽然很困惑这类在经典的数学范畴内无从下手的例外，但是他们 并没有意识到现象背后隐藏的巨大的理论背景。长期以来，这些分形一直被冠以 “病态曲线”、“数学怪物”的名称。m a n d e l b r o t 在“f r a c t a lsa n d t h er e b i r t h o fi t e r a t i o nt h e o r y ”中谈到早期数学家们工作：“值得赞扬的是由于他们发明 了如此的结构，使我能