（计算机应用技术专业论文）分形图形的变形技术.pdf

磺学铰论文 摘要 分形埋论是菲线性科学的熬沿私重要分支，在分形造型、盘然景物模拟以及 图象压缩等方面具有广阔的应用前景，随着图形学鄹软件技术的迅速发展，分形 理论的研究和戚用酲见受到人们重视。对具有分形特征的圈形图像进行变形也越 来越成为热门，分形变形技术是计算机图形学中重要的研究领域之一。 分形图形的变形要求从慕一原始形状到蹙标形状的光滑、连续、自然变换过 程。作为模拟自然图形的工具，分形迭代函数系统( i f s ) 表现也良好的可操作性。 本文主要研究的是迭代函数系统中，点控制下的二维及三维分形吸引子的变形方 法。 文中简要阐述了分形理论及已有的几种分形系统中的分形凰形的生成方法及 变形原理，分析了现有变形技术的缺陷。在分形、数学、计算机图形学等学科理 论和方法的基础上，提出了基于迭代函数系统顶点控制下的分形造型生成算法即 点变换算法。三维下该算法包括两点变换、三点变换( 其二维情况为仿射变换) 和隧点变换( 其二维情况为双线性变换) 叛及点变换之闻鹩相互转讫( 升级) 。 利用该算法可以生成仿射变换下的实时王黔分影图澎，并对已有麓至糈通过对顶 点的控制，方便、快捷的到薪的i f s 变换码和变形艨的照标分形吸弓l 予。研究了 插值变形过程中，线性插值、样条插值及三次插值等方法。在插值过程中，对羔f s 码的匹配加入连通性等约束条件，保证图形的辐扑属性，使得图形获得更自然、 逼真的变形效渠。 本文算法在自然景物模拟、动画制作、建筑配景、虚拟现实等方面都有重要 的应用价值，能够保证图形的拓扑性质，宥效地缩短了变形时间，迸步充实了 变形理论，丰富了分形图形的变形技术。 关键词：分形，迭代函数系统( 1 f s ) ，变形，点变换，插馕 分形图形的变形技术 a b s t r a c t a sa nl m p o r t a n te m b r a n c h m e n to ft h en o n l i n e a rs c i e n c e ，行a c t 以t h e o d e si sa 稻r e l a n ds u b j e c th a v eb e e na p p l i e dv a s t l yi nt h ea s p e c t so f 詹a c t a l 越o d e l i n g ，瀚糖r e s c e n es i m u l a t i n ga n di m a g ec o m p r e s s i n g w m ll h er a p i d 巷e v e l o p 掰e n to fc o m p u t 汀 g r a p h i c sa n d 也et e e h n o l o g yo f 辩建w 瑟e ，t ks 跑啦a n da p p l i c a t i o no f t h e 靠a c t a l t h e o r i e s i st a k e n 堇魏o f e 毪专e 拄i o na n dt h et e e h n i q u eo ff a c t a im o m h i n gh a v eb e e np o p u l a r r h e 羚s e a r c ho fe a c t a lm e t a m o m b o s i si sa n i m p o r t a n tr e a l mo f t h ec o m p u t e rg r a p h i c s f f a 娃a l 莎a p h 掇。巾h i n gr e q u e 髓sap r o 舒e s sw h i c hi sag r a d u a l ，s m o o t ha i l dn a t u r a l t f 鑫n s 稻r m 雏i o ne o mo n ek e ys h a p ei n t oa n o t h e r a sas c i e n t i f i ct o o l ，i l e r a l e d 凡n 瞧i o 拄 s y s t e m s ( 疆s ) p u tu pag o o dm a n n e rt os i m u l a t et h en a l u f es c e 狂e f y t h i st h e s i sg 瞰d i e s t h ea p p r o a c ho ft h e 触c t a l s 雅r a 戍o f s 。擞。叩h i 褥c o n t m l l e db yav e r t e x 仃a n s f o r m e d t e c h n i q u e si nt w o d 主l 建e n s i q n 鑫王鑫耐t k e e - d 主l n e n s i o n a ls p a c eo nt h ei t e r a t e d b n c t i o n s y 戏e 越s ( 瑾s ) + f i r s t l y ，l h i sp a p e fe x p a t i a t eo nf 魄c t a lt 量l e o 矗e sa n ds o m e 触c t a lg r a p hg e n e r a t i n g s y s t e m s ， 鑫致a l y z et h e 排s a d v a n t a g eo fs o m ec u r r e n t l ya l g o r i t h m 。a n a l y z i n gt h e 玉s 穗v a 躐a g eo fs o m ec u r r e n t l ya l g o r i t h m s ，a ni n t e r a c t i v e 安a c t a lm o d e l i 蕤ga l g o f i t h m - p o i n t st r a n s f o r m a t i o na l g o r i t h mi s p r e s e n t e dg f o 聃d o 珏t h e 蠹a 殴a l t h n e s ， m a t h e m a t i c s c o m p u t e rg r a p h i e se l e t h e 鑫呈g f i t h mi n c l u d e 钾m p o i n tt r a n s f 0 咖a t i o l l t h r e e p o i n tt f 褫s 凡f 瓣a l i o n( a 舔n et 1 a n s f o r m a t i o ni nt w o d i m e n s i o n a l ) ，f o u rp o i n t l f 鞠s f o | 瓣贰i o n ( b i l i n e a rt r a n s f o r m a t i o ni nt h r e e d i m e n s i o n a l ) a n dt h e i rc o r r e s p o n d i n g t r 黼s l a t i o n ( u p 黟a d c ) t a k i n ga d v a n t a g eo ft h i sa l g o “t h m ，y c a ni m p l e 搬e n 专t h e t e c h n o l o g yo fi n t e r a c t i v e v i s u a l i z i n ga n df e a l l i m e 巍l a l 笋a p hg e n e r a t i n gb yu s i n g i t e r a t e d 如n c t i o ns y s t e mb a s e do na 臻热e 礅a p p i n g a n dt h e ny o uc a nm o 叩h i n gt h eg r a p h t og 或l h eo 巧e 髓a 谯1 a 铱) r se x p e d i e n t l yb yc o n t r o lt h ev e r t e x t h ei m e r p 0 1 a t i o nb e c o 轻s i d e 薹e di nt h et h e s i si n e i u d el i n e a r i n t e r p 0 1 a t i o i l t 1 1 r i c ei n t e r p o l a l i o n ，a n ds p l i n e i n t e r p o l a t i o n 1 i h ec o n s t r a i n tc o n d i t i o nb eu s e dl ok e e pl h ec o n n e e t i v i t yo f 鏊r a p h i e sa n d c o l l r e s p o n d i n gm a t c h i n gt om a k e 也es e e n e f ym o f e 瀚协r a l 赫dv e r i s i m i l i t u d e t h er e s u l t si nt h i st h e s i sa r ev e r yu s e 魉lf o fl l a t u f es c e 致es i 黜l a 专i n g ，f l a s hm 呔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 l r e a l i t ye l c ，l h e o | 战i c a l 羚s e a f c h 。i tw i l ls h o n e nt h et i m eo f 珏 硕士学像论文 t h em o 叩h i n ge 毹c t i v e l y ，k e e pt h e n n e c t i v i t yt o p o l o g yo ft h ef i a c t a lg f a p h i c sa n d e n r i c ht h et h e o 哆a j l dt e c h n i q u eo f t h em o 叩h i n gu l t 舒o r l y x e yw o 嘲s ：蠹a c t a l ；i t e r a t e d 如n c t i o ns y s t e m s ( 狃s ) ；m e t a m o 叩h o s i s ； p o i n t o r a n s f o r m a t i o n ；i n t e 叩0 1 a t i o n 分形圈形的变形接术 插图索引 图l ，王分形图形变形技术现状示例图5 图2 1分形海岸线示意图9 图2 2k o c h 曲线i f s 码其极吸引子l 至 图2 3l 系统下的分形树及其变形效果o 1 2 图2 4 黼集与j 集分形图形及其周期对应关系1 4 图2 5 广义m 集上的变形1 5 图2 6 广义j 集上的变形1 5 图2 7d l a 分形模型1 6 图2 8 随即中点位移法示意图l ? 阉2 9 中点偏移法示意图1 8 图2 1 0 中点偏移法生成吸弓l 子“羔8 圈2 1 1 分式布朗运动生成分形示意图j 1 8 豳2 + 1 2 带参量的王f s 生成树及其变形效渠2 5 图3 1 三维两点变换示意图2 8 图3 2 双线性变换示意图3 2 图3 。3 点变换升级示意图3 3 图4 王现霄变形技术示例图3 7 图畦。2 两点变换下的植物变形示意图山4 至 图4 3 两点变换下的植物变形效果图一4 l 图4 4 植物连通性变形效果图4 3 圈4 。5 三点变换下的圣诞树变形，：4 3 圈4 6s i e r p 主n s k 童三角形连通性变形j ”4 3 图4 。7四点双线性变换产生豹变形4 3 图4 ，8k o 娃曲线变形为花篮族示意图哇4 图4 ，9 植物生长示意阉4 4 i 、， 兰州理工大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所里交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其 他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个 入耱集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果 由本人承担。 作者签名：王讷 姆 白期：伽够年月曰 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学 校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权兰州理工大学可以将本学位论文的全部或部分内容 编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文。同时授权中豳科学技术信息研究所将本学位论文收录到中 国学位论文全文数据库，并通过网络向社会公众提供信息服务。 作者签名：王讷p 砷 翮麟：乡气唧 ai 因期：w 口缉 豳期：一霹 月曰 参窍占毯 硕士学位论文 第l 章绪论 被誉为大量然的凡傅学的分形f l 2 l ( f 豫妇1 ) 理论是瑗代数学的一个新分支， 值其本质却是一种新的世界观和方法论。它承认世界的局部可能在一定条件下或 过稷中，在某一方藤( 形态，结构，信息，功缝，时闻，能量等) 表现患与整体 的相似性，宅承认空阆维数溺的变化既可以是离散的也霹馘是连续的，圜丽拓展了 视野。它与动力系统1 4 l 的混涟理论交叉结合，裰辅相成。 盎然器中广泛存在着其鸯囊摆似瞧的各种形态，魏：星云翁分布、出影的起伏、 岩石的断裂口、布朗粒子运动的轨迹【5 】、树冠、城市的噪声、大脑皮层【6 1 、股票的 变动、混沌f 7 l 这些部分与整体数蒹种方式穗羧熬形体称为分形，在就基磁主形 成的研究分形性质及其应用的科学，称为分形理论( f r a c t a i t h e o 哆) 。 分形理论是当今世界十分风靡和活跃豹掰理论、耨学科。 1 1 课题研究的背景及历程 1 重薹分形理论产生的背景 鳃7 年，美鏊籍法罄数学家曼德尔勃罗特( b ，8 。酗a n d e b 糙t ) 袍在美雷权威 的辩学杂志上发表了著鬈论文英国的海岸线有多长? 。这个闻题依赖于测 量时所使鼷的尺度。如果用公墨作测量单位，从几米到几十米酶一些蓝拆会被忽 略；改用米来做单位，测得的总长度会增加，毽是一些厘米量缀以下的就不能反 映出来。使用更长或更小的尺度是没有意义的。在这弧个自然限度之闻，存在着 可黻变讫许多个数量级靛“无标度”区，长度不是海岸线的定量特征，就要用分维拶j 。 欧氏一维测度与海岸线的维数不一致。根据曼德布罗特的计算，英国海岸线的维数 为 。2 6 。有了分维，海岸线酌长度就确定了。这些鸯然现象，特别是物理现象和 分彤有着密切的关系，银河系中的若断若续的星体分蠢，就是具肖分维的吸引子。 这些促使数学家进一步的研究，从两产生了分形几何学。 近年来，分形理论的应用发展远远超过了理论的发展，并且给分形的数学理论 p 挺出了更新更高的要求。在数学理论研究上，维数的理论计算、估计、分形重构 ( 即求一个动力系统，使其吸引集为给定分形集) 、动力学特征及维数研究将会成 分形图形盼变形技术 为数学工作者们十分活跃的研究领域。而在计算机图形学范畴，分形图形的产生 方法和建立其变形模受的实验都在不断被改进和完善，使之理论简便，可操作性 强。丽如何将这些理论来解决实际阂题可能会弓| 起科学家们广泛的兴趣。 重1 2 分形理论的发展历程 1 9 7 5 曼德尔布罗特首先提出了分形几何的概念，但最早的工作可追朔到1 8 7 5 年，德国数学家维尔斯特拉斯( k w b i e r e s l r a s s ) 构造了处处连续但处处不可微的 函数，集合论创始人康托( g e a n t o f ，德国数学家) 构造了有许多奇异性质的三 分康托集。1 8 9 0 年，意大刹数学家皮亚诺( g p e a n o ) 构造了填充空间的龌线。 1 9 0 4 年，瑞典数学家科赫( h v o nk o c h ) 设计出类似雪花和岛屿边缘的一类曲线。 9 o 年，德国数学家豪斯道夫( f h a u s d o 晰) 开始了奇异集合性质与量的研究， 提出分数维概念。1 9 1 5 年，波兰数学家谢尔宾斯基( 姒s i e f - p l n s k ) 设计了象地 毯和海绵一样的几何图形。 这些都是为解决分析与拓朴学中的问题丽提出的反例，但它们芷是分形几何思 想的源泉。 1 9 3 2 年庞特里业金( l s p o n t 叫a g i n ) 等引入盒维数。 1 9 3 4 年，贝 塞考维奇( a s 8 s i c o v i t e h ) 更深刻地提示了豪斯道夫测度的性质稚奇异集的分 数维，他在豪斯道夫测度及其几何的研究领域中作出了主要贡献，从丽产生了豪 斯道夫一贝塞考维奇维数概念。 以后，这一领域的研究工作没有引起更多人的注意，先驱们的工作只是作为分 析与拓扑学教科书中的反例而流传开来。 1 9 7 5 年，曼德尔布罗特创立了分形几何学( f r a c c a l g e o m e t r y ) 。曼德布罗特和伦 依( a r e n y i ) 引入多重分形( m u i f r a c t a f s ) ，它是与动力系统奇异吸引子有关的 另一类重要分形集。法默( j 。d 。陌r 团e l - ) 等在1 9 8 3 年定义了多重分形广义维数。 1 9 8 8 年博尔( t b o h r ) 等人将拓扑熵引入多重分形的动力学描述与热力学类比。 1 9 8 8 年，阿内多( a a m e o d o ) 等人将子波变换用于多重分形研究。费德( i j f e d e r ) 、 特尔( t 强1 ) 等人进行了多重分形子集及标度指数懿研究。阿姆特里卡等研究了 多重分形的逆问题，提出广义配分函数，给出广义超越维数，对过去的维数进行 了修正。李( j l e e ) 等发现了多重分形热力学形式上的相变。1 9 9 0 年，伯克 ( e 8 e 诛) 得到广义维数的上下界和极限并研究了多重分形的均匀性量度。曼德 布罗特研究了随机多重分形及负分维。1 9 9 1 年科维克( z 。k o a c s ) 等引入双变量 迭代系统，最大特征值和吉布斯势导出维数、熵、李雅普洛夫指数，提供了对多 重分形相变分类的一般方案。对于多重分形嚣前虽已提出不少处理方法，但从数 硬学键论文 学的观点上看，还不够严格，部分阀题的数学处理难度也较大l 粥。 分形理论真正发展超来才十余年，并且方兴未艾，很多方面靛理论还有待进一 步研究。在哲学方藤，人们的兴趣在于囱相似性的普适性，复数与实数的统一性， 多重分形相交与变形理论，分形体系内部的各种矛盾的转化等。 1 2 课题研究的意义及前景 近年分形理论的应用发展迅速，给分形的数学理论提出了更教更高的要求f l o 】。 在理论研究主，维数的理论计算、估计、分形夔构、在此形势下，分形图形的变 形理论发展，直观的交互式操作软件能直观的帮助研究人员对各种分形理论更好 豹建立、研究、改进和完善。 传统的分形l f s 迭代系统主要是以仿豺变换等算法来绘制图彤，在对一些自 然景物的模拟中仿射变换存在的实现复杂、计算耗时、只适宜生成静态图像等阚 题。已有变形方法难以实现交互控制，通常用入工试凑法来实现尚譬标的插值变 形，其阏题的本质是盘仿射变换逸身的局限性造成的。仿射变换矩阵内的元素凡 何含义不清晰，其第一个元素d 甚至包食旋转、缩放、错切等几重信息。问题的 其体细节将在 ，毒节中详绷阐簧。在对比分析现有算法屠，本课题力求通过创新赫 点控制和参数变换算法来建立快速生成l f s 分形图形的算法模型，并以分形插值 的方法，以方便、直褒鲶对鹜像操作的方式，寒模拟实现帮裳擞世界孛动态麴图 像，达到良好的交互性和实时性。 此外，在控制连续分形凝聚集的变形中，既可以保持凝聚集的连通性，又能 够在其中添加交影控测的物理因素。如在l f s 熬连续变形中，可以通过连通性约 束生成花草树木的变换集，使其形成花革树木被风吹动的变形效果，这是用传统 的仿射变换参数变形无法很好的模拟实现的。 分形理论酶废爝：在这短短的几十年内，正在许多领域开展应粥探索，有了极 大的发展。自然界的大部分现象都具有分形的构造：地震、河网水系、湍流、摆 变、人体血管系统、气候的激烈变化等现象，都有着耜似的奇妙的稽核结构。于 是，分形很快地进入了自然科学、地理学，生物学、物理学、化学甚至社会科学 的各个领域。尤其在图案设计1 1 1 】、创意制作、计算机动凰l 心1 、实物模拟仿真【m l 、 装饰工程等，谤究都取得了一定的成果。近年来，分影用于压缩图像信息时图像 信息的提取和识别、纹理图像分割，分形图像编码h 4 】等方面，都取得了很好的效 果，具有广泛的赢爱价值，对许多难题徽出独特翡解释，给漱了解决难题麴途径。 分形霭影戆变形技零 所以，分形豳形的变形技术是有菱要意义酶，分形学翡发震前爨是非常巍鳃的。 重。3 课题研究的内容 课题的研究内容主要豳绕着分形至f s 系统对图像的各种生成算法、分形插值方 法及在此基础上熬图形变形郄动裁。研究了图像的生成算法包括已有的仿射变换 法和正在进行的点控锘l 的参数变换法等。分形播值方法包括单参数帮多参数的线 性及嘉次捶值释样条插值等l l 父。研究交换的可视讫、高效的l f s 吸雩| 子生成算法、 吸引子变换与控制的毛f s 构造、i f s 吸引子的连通性、交换的参数化与分形插值方 法、交互式造型系统结构等。 研究了分形理论及邑有的几种分形系统中的分形图形酌生成方法及变形原理， 分析了现有变形技术的缺陷。在分形、数学、计算机图形学等学科理论和方法的 基础上，提出了基于迭代两数系统的交互式分形造型生成算法霹点交换算法。该 算法包括两点变换、三点变换( 其二维情况为仿射变换) 和四点变换( 其二维情 况为双线性变换) 以及点变换之间的褶互转化( 升级) 。幂n 用该算法可以生成仿 射变换下的实时i f s 分形图形，并对已有的i f s 通过对顶点的控制，方便、快捷 的到颓的i f s 变换码和变形后的遐标分形吸譬 子。研究了插德变形过程中，线性 捶值、样条插值及三次捶值等方法。在插值过程中，对i 骼鸸的蓬配热入连通性 等约束条件，保迁图形的季螽扑属性，使得图形获得更裔然、遥真的变形效果。 薹。4 课题国内外研究现状 目前，国内外在基于球s 系统的分形图形生成领域进行了大量的研究工作【1 6 】。 电影中行星起源的演变序列图；理查德沃簸在计算机上制作的分形山等应用已 变于导热门。但是，分形变形技术这项在景象生成、图像处理藕计算机图形学领域 中有着重要应用前景的技术却进展缓慢。这是瘩于仿射变换盘身的髑限性造成的。 爨然界中非欧几里德凡簿体系所能描绘的复杂糕纲图形如：湍流、星云等绝大多 也是变形的、动态的。故此，仅能生成静态图形、只熊以文本形式交互或者缓慢 地生成变形分形匿形是远远不够的，分形变形技术需要更浃鹃发浸。 如下图1 1 ，其中嚣，b ，e 分别为3 辫不弱酶变形技术产生熬分形图形变形效 果。图彩显示，变形硪现了失真、折断等缺陷，距离现实世界有意义的变形较远。 两且计算复杂，不容易通过文本输入懿方式控制图形变形趋势。 硕十学位论文 禹j 遘r - 飞气笃崎 a 孵 b 篷遥嗨螺 g 图l ，1 分形图形变形技术现状示例图 国内一些研究人员在变形技术上做出了研究，已有的成果都集中在对仿射变 换的扩充和改进土：为达到变形效果，对( 打( x ) ，| l ( d ) ) 上的仿射变换， 萨l ，2 ，给定一列概率分量p ( o s p 歹1 j ，岛= 1 ，三元组江x 形七，骘；就 = 0 构成带概率的迭代盛数系统l f s p 。首先从l f s p 规范形式分析各个仿射变换作用效 果，在由线性变换的系数矩阵分解提取内在动力系统参数，得到参量i f s 变化规 律，调整设置参数，生成新的有意义的吸引子，为下一步i f s 分形变形作准备。 比较典型的研究方法是考虑到原始概率向量的影噙，丽不采用统_ 的一致性概率 ，能更好地反映i f s 规范变换的几何性质。对l f s p 规范形式的仿射交换线性部 分矩阵进行适当奇异值分解处理，设i f s 仿射变换线性部分一l “一l ，奇异值分 l 秽d 夕 解得三= 淞阡，其中玩矿是正交矩阵它们都表示了一个旋转变换，它们的形式是 瞄嚣卜l ，2 删角矩豁表示了叶贼变换，尺度系数分别灿，和 葶：，这样得到旋转交换和尺度变换的复合。增加参数s 柳，当吲o ，s 柳= o 否则 s 移产l 来表示是否存在反射。还需加上平移量参量( 露。，蠢。) ，。这样作为i f s 内在动 力系统参数，第i 个仿射变换有内在动力系统参数组： 脚煳俄彩泐0 ) = 慨，秽2 ，墨，s 2 ，s 初，毛，2j ，芦l ，2 ，a 调整内在动力系统参数，重构得到新的个仿射变换，即产生新的i f s ，也就 能生成新的需要的分形吸引子。l f s 仿射变换内在动力系统参数完全刻画了其变换 分形图形的变形技术 的几何性质，但是也有很多条件必须注意： ( 1 ) 、一般不改变仿射变换参数啦卵的值，因为反射变换不易控制； ( 2 ) 、平移向量参数可以改变，但要注意吸引子的有界区域范围； ( 3 ) 、改变参数时要保持s 仿射变换的压缩性和非奇异性。 在对三维迭代函数系统的分形吸引子变形算法的研究中，己有的方法是先根 据仿射变换作用效果，对i f s 分形吸引子建立人工特征对应关系，后进行三维环s p 规范变换，最后通过仿射变换的极值分解插值实现了三维s 分形吸引子的变形 过程。 仿射变换作为三维迭代函数系统的基本特征，有效地插值其基本变换参数即 内在动力系统参数能够获得较好的分形变形效果。通过多种矩阵分解方法如奇异 值分解、极值分解、q r 分解等都能得到基本仿射变换，但比较运算量及其变形效 果，极值分解方法相对来说更好【1 7 】。极值分解只是奇异值分解特殊组合形式，但 可以通过简单迭代算法计算，计算量相对较小，它是唯一的不会影响s 分形变 形效果，但该方法结果中内在动力系统参数发生了重组。与二维情形相比，三维 仿射变换的基本变换也包括旋转变换、尺度变换、平移变换等，但是旋转变换相 对二维要复杂得多，而利用旋转矩阵与四元数的转化关系，将旋转矩阵插值转化 为四元数插值，同时考虑空间向量插值转化，将不动点插值也化为四元数插值， 改良插值路径，可取得较好的巧s 分形变形效果。四元数能够很好地描述三维空 间中物体的旋转，特别是单位球面上的所有四元数最适合应用于计算机动画。三 维空间中的旋转矩阵与单位四元数可以一一对应，由此用四维空间中四元数的插 值代替s 基本变换之一的旋转矩阵插值，这样简化了插值运算，取得了较好的 变形效果，但是计算复杂。 其他最新插值方法还有：真彩s 分形插值即综合分形形状矩阵插值与颜色 矩阵插值【1 8 】，二维迭代函数系统分形吸引子自适应对应变形算法【1 9 】，自动选择插 值路径等国内研究着提出的多种变形方法。 综上所述，仅有现在这些分形理论还是不能满足我们对交互性、实时性的要求。 通过仿射变换控制图形变换已有相当成果但缺陷很多。而通过点控制的参数变换 去控制图形变换这一领域，尚无太多人涉及但很有发展潜力，很值得我们探索和 研究。 硕j j 学位论文 1 5 论文的组织结构 第一章论述了课题的研究背景、回顾了分形的发展历史、研究意义以及国内 外分形图理论研究现状和一些技术缺陷。 第二章论述了分形理论的基本概念，包括分形的定义、分形的特点、分形维 数、几种分形图形生成系统及其上变形理论、分形空间及迭代函数系统理论，包 括随机算法和确定性算法，着重论述了确定性算法 第三章提出了基于顶点控制的i f s 码变换算法，既：点变换，包括三维情况 下的：两点变换、三点变换( 在二维情况下为仿射变换) 和四点变换( 在二维情 况下代表双线性变换) 。及点变换之间的相互转化( 升级) 第四章提出了点变换控制下的分形变形理论及其插值过程中的匹配原则和约 束条件。举出大量实例以验证该算法实现了交互式迭代函数系统的分形造型及连 续变形。包括传统的典型分形吸引子生成及其保证拓扑连通性下的变形的目标图 形生成技术。 总结与展望。 分形图形瓣变形拨术 第2 章分形原理及相关理论 f r a c l a l 一词源于拉丁文形容词f r a c t u s ，对应的拉丁文动词是f r a n g e r e ( “破碎”、 “产生无规则碎片”) ，与英文的仃a c t l o n ( i 碎片”、“分数”) 及f 爆g m e n t ( “碎片”) 具 有相同的词根【2 叭。在7 0 年代中期以前，曼德勃罗一宣使用英文f 穗c t 融n a l 一词来 表示他的分形思想。因此，取拉丁词之头，撷英文之尾的f r a c t a i ，本意是不规则 的、破碎的、分数的。曼德勃罗是想用此词来描述自然界中传统欧几里德几何学 所不能描述的一大类复杂无规则的几何对象。例如，弯弯曲曲的海岸线、起伏不 平的山脉，粗糙不堪的断面，纵横交错的血管，令人眼花绦乱的满天繁星等。它 们的特点是，极不规则或极不光滑。直观而粗略地说，这些对象都是分形。 2 1 分形的定义及原理 2 1 1 分形的定义 分形具有的不规则现象在自然界是普遍存在的，因此分形几何叉称为描述大自 然的几何学犯弱。有许多数学结构也是分形，例如：谢尔宾斯基三角形、科切雪花、 皮距诺曲线、曼德勃罗集、洛仑兹吸引子等。分形同样可以描述许多真实世界的 对象，如云彩阱j 、山脉、湍流和海岸线等，当然它们不是单纯的分形形状。 曼德勃罗曾经为分形下过两个定义： ( 1 ) 满足下式条件 d i m ( a ) d i m ( a ) 的集合a ，称为分形集。其中，d i m a ) 为集合a 的h a u s d 醑维数( 或分维数) ， d i m ( a ) 为其拓扑维数。一般说来，d i m ( a ) 不是整数，而是分数。 ( 2 ) 部分与整体】以某种形式相似的形，称为分形。 然而，经过理论和应用的检验，人们发现这两个定义很难包括分形如此丰富的 内容。实际上，对于什么是分形，到目前为止还不能给出个确切的定义，正如 生物学中对“生命 也没有严格明确的定义一样，人们通常是列出生命体的一系 列特性来加以说明。对分形的定义也可同样的处理。现在一般用法尔科内对分形 集合f 的描述来判定某一对象是否是分形： ( i i i ) f 通常具有某种自相似性，这种自相似性可以是近似的，也可能是统计 意义上的； ( i v ) f 在某种意义下的分形维数通常都大于它的拓扑维数； ( v ) 在多数令人感兴趣的情形下，f 以非常简单的方法定义，或许以递归过 程产生。 图2 1分形海岸线示意图 由该图可以看到第一个框中图像经过逐级放大后，又产生了自相似的细节，这 直观形象地说明了何为“自相似”，分形的含义及上述5 条描述性的概念定义。 2 1 2 分维 分维，作为分形的定量表征和基本参数，是分形理论的又一重要原则。分维又 称分形维或分数维，通常用分数或带小数点的数表示。长期以来人们习惯于将点 定义为零维，直线为一维，平面为二维，空间为三维，爱因斯坦在相对论中引入 时间维，就形成四维时空。对某一问题给予多方面的考虑，可建立高维空问，但都 是整数维。在数学上，把欧氏空间的几何对象连续地拉伸、压缩、扭曲，维数也 分形图形的变形技术 不变，这就是拓扑维数。然两，这种传统的维数观受到了挑战。曼德布罗特曾描 述过一个绳球的维数：从很远的距离观察这个绳球，可看作一点( 零维) ；从较近 的距离观察，它充满了一个球形空间( 三维) ；再近一些，就看到了绳子( 一维) ；再 向微观深入，绳子又变成了三维的柱，三维的柱又可分解成一维的纤维。那么， 介于这些观察点之间的中间状态又如何呢? 显然，并没有绳球从三维对象变成一维对象的确切界限。数学家豪斯道夫 ( h a u s d o f f ) 1 9 1 9 年提出了连续空间的概念，也就是空间维数是可以连续变化的，它 可以是整数也可以是分数，称为豪斯道夫维数。记作d c 一般的表达式为：k = l d 鼻 也作k = ( 1 l ) 一d 鼻取对数并整理得d f = l n k l n l ，其中l 为某客体沿其每个独立方 向皆扩大的倍数，k 为得到的新客体是原客体的倍数。显然，d ，在一般情况下是 一个分数。因此，曼德布罗特也把分形定义为豪斯道夫维数大于或等于拓扑维数 的集合。英囡的海岸线为什么测不准? 因为欧氏一维测度与海岸线的维数不一致。 根据曼德布罗特的计算，英国海岸线的维数为王2 6 。有了分维，海岸线的长度就 确定了。维数是物理学家在研究混淹吸引子等理论时需要弓| 入的重要概念。为了 定量地描述客观事物的“非规则 程度，1 9 1 9 年，数学家从测度的角度引入了维 数概念，将维数从整数扩大到分数，从而突破了一般拓扑集维数为整数的界限。 分维的模型可以从两方面建立：一方面，我们首先画一个线段、正方形和立方 体，它们的边长都是1 。将它们的边长二等分，此时，原圈的线度缩小为原来的 1 ，2 ，丽将原图等分为若干个相似的图形。其线段、正方形、立方体分别被等分为2 1 、 2 2 、和2 3 个相似的子图形，其中的指数1 、2 、3 ，正好等于与图形相应的经验维 数。一般说来，如巢某图形是由把原图缩小为1 内的相似的b 个图形所组成，有： 8 。：抚d ：攀 t o ga 的关系成立，则指数d 称为相似性维数，d 可以是整数，也可以是分数。另一方面， 当我们画一根直线，如果我们用0 维的点来量它，其结果为无穷大，因为直线中 包含无穷多个点；如采我们用一块平面来量它，其结采是o ，因为直线中不包含平 面。那么，篇怎样的尺度来量它才会得到有限值哪? 看来只有用与其同维数的小 线段来量它才会得到有限值，而这里直线的维数为l ( 大于o 、小于2 ) 。与此类似， 如果我们硒一个k o c h 曲线，其整体是一条无限长的线折叠而成，显然，用小直线 段量，其结果是无穷大，而用平面量，其结果是o ( 此曲线中不包含平面) ，那么 只有找一个与k o c h 曲线维数相同的尺子量它才会得到有限值，而这个维数显然大 于1 、小于2 ，那么只能是小数( 即分数) 了，所以存在分维。如图2 。2 ：k o c h 曲 硕l 学位论文 线的维数是1 2 6 1 8 。 “ l 。p o o 、r 、 k o c h 曲线i f s 码k o c h 曲线吸引子 图2 2k o c h 曲线i f s 码其极吸引子 2 2 几种分形图形生成系统 本小节阐述了几种分形图形的产生方法及其上的变形原理，包括l 系统、复动 力系统( 逃逸时间法) 、粒子系统及扩散凝限制聚模型( d l a ) 、布朗运动及随 机中点位移法。 2 2 1l 系统 l 一系统的第一个字母l 源于美国生物学家a l i n d e 眦l a y e 姓氏中的l 字母，开 始是作为描述植物的形态与生长的一种方法，继而发展成计算机图形学中一种模 拟大自然景物的有效方法，当然是一种重要的分形生成方法【2 3 1 。 定义2 3 令y 表示字母表，功是一个非空单词，称为“公理 ；尸是生成规 则的集合，用口山x 表示a 为尸的“前驱 ，j 为尸的“后继 。一个d o l 系 统是一个有序三元组g = ( 以劬辟，规定对每个口矿至少存在一个非空单词x 使 得口寸x ，若某个前驱口矿没有显示的给出x ，则假定口专口恒等变换，这就是 确定性的d o l 系统。 d o l 系统指的是“确定性的上下文无关文法 ，即在生成过程中与前后相邻元 素无关；d l l 系统指的是左相关或右相关文法，即在生成过程中与左或右相邻元 素相关；d 2 l 系统既考虑左边语法关系又考虑右边语法关系，即在生成过程中与 左右相邻元素都相关。 l 系统对植物造型能力较强阱】。主要是基于串复写原理，用链式语言描述。 定义以下命令： 分形图形的变形技术 f 一在当前方向向前走一步 一将系统的当前状态压栈保存 一将栈中状态弹出，即恢复系统的原来状态 + 一向左转一给定的角度 一一向右转一给定的角度 l 一系统作图的基本原理是“字符串改写”。在具体生成分形图形的过程中，要 同时结合使用“改写规则”和“龟形图法”两种方法晗3 3 。“改写规则”是形式化的 描述，首先从初始字符串集合中任选出一个字符串，并在产生式集中选择一个适 当的产生式，即改写规则，以初始字符串为前导代入产生式进行字符串改写，得 到一个新的字符串后继，并以此新字符串为前导重新代入产生式生成下一个后继 字符串，以此迭代改写多次，直到产生最后的字符串，由这个字符串生成对应的 图形就是l 系统产生的分形图。图2 3 为l 系统下的分形树及对其变形的效果。 图2 3l 系统下的分形树及其变形效果 例：如上图分形树的l 系统初始元及生成规则为： $ s t e p s = 1 0( 迭代次数：1 0 ；$ 为将当前方向滚动到水平方向，下同) $ r 1 = 0 9( 步长1 ) $ r 2 = 0 7( 步长2 ) $ a l = l o( 角度1 ) $ a 2 = 6 0( 角度2 ) $ w r = 0 7 0 7( 缩放因子) a ( 1 ，1 0 )( 初始元) a ( 1 ，w ) 一一 ! ( w 木0 0 1 ) f ( 1 ) ( a 1 ) b ( 1 术r 1 ，w 丰w r ) ( 1 8 0 ) & ( a 2 ) b ( 1 冰r 2 ，w 术w r ) ( 替换规则1 ) b ( 1 ，w ) 一一 ! ( w 木0 0 1 ) f ( 1 ) + ( a 1 ) $ b ( 1 木r 1 ，w 水w r ) 一( a 2 ) $ b ( 1 木r 2 ，w 木w r ) ( 替换规则2 ) 硕l ：学位论文 对其变形后初始元及生成规则为：( 备注同上) $ s t e p s = l o $ r 王= 0 9 $ r 2 = 0 8 $ a l = 2 0 $ a 2 = 5 0 $ w r = 0 7 0 7 馘( 王，1 0 ) a ( 1 ，w ) 一一 ! ( w 木o 0 1 ) f ( 1 ) ( a 1 ) b ( 1 术r 1 ，w 栅) ( 1 8 0 ) ( a 2 ) b ( 1 ，i c r 2 ，w 棚r ) 8 ( 1 ，鬻) 一- ! 如枣o 0 1 ) f ( 1 ) + ( a 1 ) $ 8 ( 1 零r l ，w 蜘r ) 一( a 2 ) $ b ( 1 钳2 ，餮：l c 程r ) 3 2 。2 。2 复动力系统( 逃逸时间法) 动力系统中的分形集是近年分形几何中最活跃和引入入胜的一个研究领域。 动力系统的奇异吸引子通常都是分形集，它们产生予非线性函数的迭代和非线性 微分方程中【2 5 1 。动力系统中另一类分形集来源于复平面上解析映射的迭代，即复 动力系统。朱利亚( g j u 王童a ) 和法图( p f a t o 毽) 予羔9 1 8 一1 9 王9 年闻开创这一研究。 解析映射的迭代把复平面划分成两部分，一部分为法图集，另一部分为朱利亚集 ( j 集) 。 绘制复动力系统中的分形吸引子用到逃逸时间法【2 6 】f 2 7 1 。它的主要思想是对于 一个二维平面主的不变集袁，选取迭代步数为一个充分大的整数n ，个估计包 含a 的区域w 及一个以原点为圆心，以充分大的r 为半径且包含区域w 的圆( 把 圆外区域记为v ) 。对w 中的每一点进行计算规迭代计算，蓉点x 霹的轨道经 小于或等于n 次的迭代就达到了区域v ，则x 为逃逸点，而如果达到n 次迭代后x 的轨道仍未到达v ，则认为x 是a 上的点，此类点集构成了混沌吸引子。主要应 用在复平面上分形图的绘制。即：在复平面上可分为两个区域，一个区域使落在 其中的点向某个吸引子逼近，为收敛区域a ：而另个区域使落在其中的点向 逃逸，为逃逸区。 初始点离a 越近，其轨道趋于无穷所霈的时间越长；而离a 越远的点， 经过较少次数的迭代，轨道就会趋于无穷。假设有一个充分大的整数m 当未逃 逸区域m 中的初始点a 经过小于n 次迭代就达到来逃逸区域m 的边界，甚至 超出了边界，则认为点8 逃逸出去了：两如果经过冀次迭代蜃8 的孰道仍 未到达m 的边界，则认为a 是a 上的点。用这种方法描绘出a 的边界图形， 分形图彤的变形技术 这便是逃逸时间算法的基本思想。 图2 4m 集与j 集分形图形及其周期对应关系 定义2 4 ：设，是一个变换，的向前迭代变换厂”定义为：厂og ) = x ， 1b ) = x ，厂川g ) = 厂”= 厂杪”g ) ) 刀= o ，1 ，2 ，。逃逸时间法：设z c ，其 中c 是全体复数集合，令( a ，b ) 和( c ，d ) 分别表示坐标图上左下方和右上方闭区 域w 的两个点，m 是正整数，定义w 中的点： 铲( 唧詈