【硕士论文】分形自然景物模拟图形在包装CAD中的应用与研究.pdf

题目：分形自然景物模拟图形在包装 学科名称： 硕士生： 指导教师： 答辩日期： C A D 中的应用与研究 包装工程 谢利 和克智副教授 2 0 0 5 年3 月 摘要 签名： 签名： 在包装设计中，通常需要用到许多常见的自然景物和材质，例如变幻莫测的 云彩、雄浑壮阔的山脉、回转曲折的海岸线、不断分叉的树枝、各种图案的术纹 及火理石等，以增加包装装潢图形的逼真性羽l 空问效果。而这些自然景物的形状 似乎是毫无规则的，如果采用传统的欧儿里得几何米完成这些物体的几何造型， 生成的图形就会显得生硬，失去视觉上的真实感。为此，便需要寻找一种有效的 生成函数，根据一些反映物体J U o J 特征的参数，生成模拟景物所需要的几何数据。 本文结合包装装潢图形的特点，提出采H j 分形儿何的方法来绘制自然景物图形。 首先，根据模拟对象的不同特点，利用分形儿何理论建立它们各自的几何模型： 然后，依据分形插值理论设计相应的算法，得到模拟对象的儿何数据，绘制出平 面图形；最后，为了得到较好的视觉效果，我们利用O p e n G L 的图形处理及渲染 功能对生成的图形进行色彩、光照、纹理等方面的处理，从而得到具有真实感的 三维自然景物模拟分形图形，以满足包装设计者的需求。 关键词：包装C A D 分形自然景物模拟分形插值算法 A b s t r a c t S u b j e c t ： F R A C T A L N A T U R A LS I M U L A T I O NG R A P H I C S I NB C K A G I N GC A D S p e c i a l t y ： W r i t e r ： I n s t r u c t o r P a c k a g i n gE n g i n e e r i n g X i e L i H e K e z h i A b s t r a c t S i g n a t u r e ：2 ( i 垒L i S i g n a t ur e 趔d 纱 Al o to fn a t u r a ls c e n e r i e sa n dm a t e r i a l ss u c ha sc h a n g e a b l ec l o u d s g r a n d i o s e m o u n t a i n s ，d e v i o u sc o a s t l i n e ，i n c e s s a n t l yf o r f i c a t eb r a n c h e s ，w o o d - t e x t u r ea n d m a r b l e sw i t hv a r i o u sp a t t e r n sa r eo f t e nu s e di np a c k a g i n gd e s i g nt oi n c r e a s et h e r e a l i t ya n ds p a c ee f f e c to ft h eg r a p h i c sd e s i g n e d H o w e v e r , t h es h a p e so ft h e s en a t u r a l s c e n e r i e ss e e mt ob e i r r e g u l a r I tw i l l b ea n g u l a ra n du n r e a li nv i s i o ni fE u c l i d g e o m e t r y i s a d o p t e dt of u l f i l lt h e i rm o d e l i n g T h e r e f o r e ，ak i n d o fe f f i c i e n t b u i l d f u n c t i o nm u s tb el o o k e df o rt of o r mt h eg e o m e t r yd a t at h a tc a nd e s c r i b et h e s e s c e n e r i e sa c c o r d i n gt os o m ep a r a m e t e r st h a t r e p r e s e n tt h e i rg e o m e t r yc h a r a c t c r s F r a c t a lg e o m e t r yi sp r o p o s e di nt h i sp a p e rt op r o t r a c tn a t u r a ls c e n e r yg r a p h i c sb a s e d o nt h ec h a r a c t e r so fp a c k a g i n gd e c o r a t i o n F i r s t l y , t h eg e o m e t r ym o d e l so ft h eo b j e c t s s i m u l a t e da r cb u i l t b yt h ef r a c t a lg e o m e t r yt h e o r ya c c o r d i n g t ot h e i rd i f f e r e n t c h a r a c t e r i s t i c s S e c o n d l y ，t h ec o r r e s p o n d i n ga l g o r i t h m sa r ed e s i g n e d t og a i nt h e g e o m e t r yd a t ao ft h e s eo b j e c t sa c c o r d i n gt of r a c t a li n t e r p o l a t i o na l g o r i t h mt h e o r ys o a st o p r o t r a c tt h e i rp l a n a rg r a p h i c s F i n a l l y ，i no r d e rt og a i nb e t t e r v i s u a le f f e c t ， g r a p h i c sd i s p o s a la n dr e n d e rf u n c t i o n so fO p e n G La r eu s e dt od e a lw i t ht h ea s p e c t so f t h e i rc o l o r ，i l l u m i n a t i o na n dt e x t u r e C o n s e q u e n t l y ，t h r e e - d i m e n s i o n a ln a t u r a ls c e n e r y s i m u l a t i o ng r a p h i c sw i t hr e a l i t ys e n s ea r eo b t a i n e dt os a t i s f yt h en e e d so fp a c k a g i n g d e s i g n e r s 1 l I 西安理工大学项士学位论文 K e y w o r d s ：P a c k a g i n gC A D F r a c t a lN a t u r a ls c e n e r ys i m u l a t i o n F r a c t a li n t e r p o l a t i o na l g o r i t h m 绪论 1 绪论 在以电子计算机为代表的现代信息技术的发展中，计算机辅助设 计和辅助制造( C A D c A M ) 已经成为一个最有实际经济价值的新技术 之一。 当前，C A D C A M 技术发展日新月异，更新迅速，已被普遍应用 于机械制造、汽车、航空、大规模集成电路、工厂设计、铁路、包装 等许多领域中。其中，C A D C A M 在包装工业中的应用已成为包装领 域的一个重要内容，它被广泛应用于包装容器结构设计、缓冲包装结 构设计、包装性能测试、包装机械设计制造、包装装潢设计、印刷图 案的版面设计及智能化包装设计系统等各个方面。 1 1 目前图形软件的现状 现今，用于图形图像处理的C A D 软件，像3 D M a x 、P h o t o s h o p 、 C o r e l D r a w 等都已经非常成熟，并且得到了广泛应用。但是，这些软件 大都是以传统的计算机绘图方法为基础，用欧几里得几何理论来描述 图形，绘制的都是一些表面平滑、形状规则的几何图形，例如，立方 体、锥体、球体等等。 在包装设计中，通常需要用到许多常见的自然景物和材质，例如 变幻莫测的云彩、雄浑壮阔的山脉、回转曲折的海岸线、不断分叉的 树枝、各种图案的木纹及大理石等，以增加包装装潢图形的逼真性和 空间效果。而这些自然景物的形状似乎是毫无规则的，如果采用传统 的欧氏几何来完成这些物体的几何造型，就显得力不从心：如果我们 直接用直线、高次曲线和样条曲线及曲面等对这些自然景物进行模拟， 产生的图形就会显得生硬，失去视觉上的真实感。为此，便需要寻找 种有效的生成函数，根据一些反映物体几何特征的参数，生成模拟 景物所需要的几何数据。 西安J 里_ r - 大学硕士学位论文 本课题就是在此基础上提出的，尝试性地运用分形理论在计算机 上模拟不规则的自然景物，尤其希望将生成的分形图形用于包装装潢 设计和包装容器的材质与纹理的图案设计。 1 2 分形理论简介 分形”均原文F r a c t a l 是美国I B M 的研究人员M a n d e l b r o t 在1 9 7 5 年用拉丁词根拼造的，意思是细片的、破碎的、分数的、分级的【2 】等等。 分形是描述不规则几何形态的工具，不规则几何形态在我们周围处处 可见，诸如花草、山脉、云彩、火焰等举目皆是。至于微观世界复杂 物质的结构，宏观世界浩瀚天体的演变，更展示了层出不穷的不规则 几何形态，它们往往都是分形几何研究的对象。正因为如此，我们说 “分形是大自然的几何学”【3 】，“分形处处可见”1 4 ，5 ，6 1 。 自然界中的景物是丰富多彩、变化万千的。然而，大自然向人类 展示其美丽多变的形态的同时，也提出了难以回答的问题：怎样描述 复杂的自然表象? 如何分析其内在机理? 不论是艺术家，还是科学家， 都在苦苦地寻找它的答案。艺术家把形态分为两类，一类是自然形态， 另一类是几何形态。他们认为：目前还没有哪一种几何学能更好地描 述自然形态，像山峦、云团、火焰这一类的自然形态尚缺少必要的数 学模型。科学家面对这样的现状，一直探索着从欧氏几何体系中解放 出来的道路。在近一二十年间，朦胧地“感觉”到了另一个几何世界， 即关于自然形态的几何学一一分形几何学。这种几何学把自然形态看 作是具有无限嵌套层次的精细结构，并且在不同的尺度之下保持某种 相似的属性，于是在变换与迭代的过程中得到了描述自然形态的有效 方法。虽然分形几何学理论基础的建立还要经过非常艰苦的路程，但 分形这个词，正越来越多的为理论及实际工作者所关注，并对传统的 数学和物理学都产生了强大的冲击。 关于分形，最早的工作可追朔到1 8 7 5 年，德国数学家维尔斯特拉 绪论 斯( K W e i e r e s t r a s s ) 构造了处处连续但处处不可微的函数，集合论创 始人德国数学家康托( ( 7 C a n t o r ) I7 l 构造了具有许多奇异性质的三分康 托集。1 8 9 0 年，意大利数学家皮亚诺( G P e a n o ) 【8 】构造了填充空间的 曲线。1 9 0 4 年，瑞典数学家科赫( H V O I lK o c h ) 1 9 】设计出类似雪花和岛 屿边缘的一类曲线。1 9 1 5 年，波兰数学家谢尔宾斯基( W S i e r p i n s k i ) 设计了象地毯和海绵一样的几何图形。这些都是为解决与分析拓朴学 中的问题而提出的反例，但它们正是分形几何思想的源泉。1 9 1 0 年， 德国数学家豪斯道夫( E H a u s d o r f f ) 1 1 0 】开始了奇异集合性质与量的研究， 提出分数维概念。1 9 2 8 年，布利干( C t B o u l i g a n d ) 将闵可夫斯基容度 应用于非整数维，由此能将螺线作很好的分类。1 9 3 2 年，庞特里亚金 ( L S P o n t r y a g i n ) 【1 l l 等引入盒维数。1 9 3 4 年，贝塞考维奇 ( A S B e s i c o v i t c h ) 更深刻地提示了豪斯道夫测度的性质和奇异集的分 数维，他在豪斯道夫测度及其几何的研究领域中做出了主要贡献，从 而产生了豪斯道夫贝塞考维奇维数概念。以后，这一领域的研究工作 没有引起更多人的注意，先驱们的工作只是作为分析与拓扑学教科书 中的反例而流传开来。 经过多年的研究发现，分形的性质是多样的，例如，在平面上分 形的维数是在1 与2 之间的分数，而在空间里分形维数在2 与3 之问。 在分形的世界里，我们不能把它说成是2 维或3 维的，而应该说它是 1 7 5 维或2 3 维。在分形几何里海岸线的长度被认为是无限的，因为每 个小小的海湾和沙滩都被测量，而这样的海湾和沙滩的数量在不断地 变化。 近2 0 年来，分形的研究受到非常广泛的重视，其原因就在于分形 既有深刻的理论意义，又有巨大的实用价值。它与耗散结构及混沌理 论共称为2 0 世纪7 0 年代中期科学的三大重要发现。现在分形理论已 被应用到物理、化学、地质、矿业、材料、环保、生物、石油、计算 机模拟等各个学科和领域，分形在物理的相变理论、材料的结构与控 西安理工大学硕士学位论文 制、力学中的断裂与破坏、高分子链的聚合、模式识别、自然图形的 模拟、酶的生长等领域都取得了令人注目的成果。分形的数学理论也 得以迅速发展，并且目的更明确，思想更深入。维数的估计与算法、 分形集的生成结构、分形的随机理论、动力系统的吸引子理论与分形 的局部结构都已获得较深入的结果。 分形具有以下性质：它的精细部分不会损失，放大后具有与原先 相同的结构。分形提供了描述自然形态的几何学方法，使得在计算机 上可以从少量数据出发，对复杂的自然景物进行逼真地模拟，并启发 人们利用分形技术对信息作大幅度的数据压缩【1 2 】。美国乔治亚州工学 院数学家巴恩斯利( M E B a m s l e y ) 提出分形图像编码方法并申请了美 国专利，依此成立了一家专门从事分形图像编码研究的公司一一迭代 系统公司。国外从理论研究到应用研究，在分形的许多方面都取得了 富有成效的进展。 国内也有许许多多的科技工作者在分形的理论研究和应用方面作 了一些工作，翻译或自己编撰出版了一些分形几何研究理论和应用方 面的书籍。但国内在整个分形领域的研究总体上还比较落后。 随着人们对分形认识程度的加深，我们逐渐认识到，我们就生活 在一个分形的世界中，我们的身边处处都是分形，分形理论的应用有 着非常广阔的前景。 1 3 本课题的研究意义 一个优秀的包装设计者，常常需要设计比较多的任意图形，有时 更需要一些抽象的图形来满足消费者的审美需求，功能侧重于图形图 像处理及结构设计的软件是不能很好地完成这个任务的。而用分形理 论来绘制图形，不但为包装设计者们提供了一种全新的设计手法，而 且能够让设计者有更大的想象余地和发挥空间；而且，分形图案是变 幻莫测、色彩绚烂而美丽的，我们将分形图形用于产品包装装潢设计 上，可以增加商品的艺术价值，吸引消费者，刺激其购买欲。 分形图形层次丰富、内涵深刻，体现了各种类型的混沌和有序， 并且只有用计算机才能产生出来，任何高明的画家都难以绘制。但是， 由于分形的理论、建模及编程不为一般的设计人员所熟悉，使其使用 受到了很大限制，目前将计算机生成的分形图形直接应用于设计行业 的成果并不多。如果将分形图形的计算机生成实现参数化设计，改变 少量参数就能得到递归层次不同的相似图形，使之从抽象的理论研究 进入到实际设计应用中，可以减少设计人员编制、调试绘图程序的时 间，有利于推广分形技术在包装领域中的应用，具有可观的实用价值。 模拟自然景物的分形图案，可以用作包装容器的材质与纹理以及 包装材料图案等，效果新颖，形象逼真。此外，由计算机产生的分形 图像可以叠加在产品的防伪商标或标识上，甚至也可以作为标识的一 部分，从而达到很好的防伪效果。 另外，由于分形图形具有很高的艺术价值，将它们制作成各种尺 寸的装饰画、挂历、台历、贺卡等，可以获得很好的装饰效果。 目前已有的分形模拟图形主要是二维的，用于包装装潢上时缺少 了空间效果。鉴于以上种种原因，我们相信，用计算机生成的三维分 形自然景物模拟图形在包装领域将会有非常广阔的应用前景。 1 4 本课题的研究内容 本课题的研究目的是利用分形理论设计个模拟自然景物的包装 C A D 辅助系统软件。在此软件平台上，输入一定的参数，如迭代次数、 粗糙度因子等，就可以绘制出相应的自然景物图形。该软件的研究可 以增加和完善包装设计领域专用C A D 辅助设计工具的功能。 为了达到上述目的，在本课题中，我们主要完成以下工作： 1 将山脉和云彩这两种自然景物作为本课题的研究对象； 2 建立山脉和云彩的几何模型： 西安理工大学硕士学位论文 3 在计算机上进行分形山和云的算法实现； 4 用O p e n G L 对分形山和云的图形进行渲染，使其更真实地模拟 自然景物； 5 制作出具有良好效果的中文用户界面。 总体设计 2 总体设计 任何分形最关键的特征是自相似。当一个物体的一部分放大后看起 来仍与整个物体一样，那么这个物体就是自相似。我们观察到，手掌上 的碎岩锯齿状边缘与远处地平线边的山脊有相同的不规则形状，云彩纹 理表面的每点处均有无限的细节，它的整体和局部特性具有自相似性。 因此，山脉和云彩都属于自相似范畴，这就使得我们可以采用分形的方 法对它们进行模拟。 2 1 分形方法概述 关于分形，目前尚无一个一致的定义，我们一般采用K F a l c o n n e r 对 分形F 的描述。该描述如下1 1 3 , 1 4 】： 1 F 具有精细的结构，也就是说在任意小的尺度之下，它总有复杂 的细节： 2 F 是不规整的，它的整体与局部都不能用传统的几何语言来描述； 3 F 通常有自相似形式，这种自相似可以是近似的或是统计意义下 的： 4 一般地，F 的某种定义之下的分形维数大于它的拓扑维数； 5 在大多数情况下，F 以非常简单的方法确定，可能由迭代过程产 生。 根据实现算法的不同，分形可以分为以下几种类型：自相似分形， 复数分形，自然分形等。 2 1 1 自相似分形 一个系统的自相似性是指某种结构或过程的特征从不同的空间尺度 或时间尺度来看都是相似的，或者某种系统或结构的局域性质或局域结 构与整体类似。另外，在整体与整体之间或部分与部分之间，也会存在 西安理工大学硕士学位论文 自相似性。一般情况下，自相似性有比较复杂的形式，而不是局域放大 一定倍数以后简单地和整体完全重合。但是，表征自相似系统或结构的 定量性质，如分形维数，并不会因为放大或缩小等操作而变化，所改变 的只是其外部的表现形式。 确定性自相似分形的最大特点就是分形的每个组成部分是整个图形 的收缩形式。从一个初始形状开始，对整个形体应用缩放因子S 来构造 图形的子部件，同样再对子部件用相同的缩放因子S 构造它的子部件， 如此一直迭代下去。这里，我们把构造这个自相似分形图的初始几何形 状称为初始元，把对初始元的每部分由缩放因子S 构造的子部件称为生 成元f 1 5 】。C a n t o r 集、K o c h 曲线、S i e r p i n s k i 集【1 6 1 都属于自相似分形。 2 1 2 复数分形 非线性函数可以构成混沌动力系统【1 7 】，丽混沌动力系统中的混沌集 可以由迭代产生。设函数或映射Y = ，( x ) 是某一规则，若给定x 一个初值， 记为z 。则由Y = ，0 ) 可得Y 的一个值，记为一，即x ，= f ( x 。) ，将这个 Y z 。作为z 的新值，可得Y 的新值Y = f ( x ) ，记为z ：，即z ：= ，0 。) 。这 样反复迭代的数学反馈过程，使函数或映射的每一次输出作为下一次的 输入，即t 。= f ( x 。) ，n = 0 ，1 ，2 ，从而得到一个序列，_ ，x ：， z 。，这个序列称为z 。，的轨道。混沌动力系统根据每一初始点工。轨道 的稳定性与不稳定性确定其混沌集【1 8 】。当复解析映射被引入混沌动力系 统时，则进入了混沌动力系统中最诱人的研究领域。此时计算机屏幕显 示的混沌集超出了所有的预料，呈现在人们眼前的是千变万化的极为复 杂而美丽的图形。 我们所熟知的J u l i a 集和M a n d e l b r o t 集【1 9 J 就是根据复映射公式： z = z ：+ C( 2 - 1 ) 在计算机上生成的典型的复数分形图形。 总体设计 2 1 3 自然分形 自然分形是模拟自然景物分形结构的方法，其中，L 系统、I F S 迭代 函数系统以及分形插值法是模拟分支结构最有效的几种方法。 1 L 系统 L 系统1 2 0 是美国生物学家A r i s t i dL i n d e n m a y e r 提出的研究植物形态 与生长的描述方法，开始时只着重于植物的拓扑结构，即植物的主干与 旁支之间的相邻关系，后来把几何解释加进描述过程，形成L 系统。 L 系统是一种形式语言。我们一般用它来模拟植物分支拓扑结构。 2 I F S 迭代函数系统 迭代函数系统简记为I F S 2 ”，这是绘制分形图形的典型方法。I F S 的 基本思想是：它认为几何对象的全貌与局部，在仿射变换的意义下，具 有自相似结构。这样一来，几何对象整体被定义之后，选定若干仿射变 换，将整体形态变换到局部，并且这一过程可以迭代地进行下去，直到 得到满意的造型。 3 分形插值法 在实际计算中，我们经常遇到只提供一些离散数掘的函数，要计算 函数在其它点上的值或讨论函数的性质，我们通常采用的方法是构造一 个简单的函数F ( x ) ，使之通过已知的数据点，然后用F ( x ) 的值和性质来 代替上述函数的值和性质，这就是插值法。而一般的插值法，如拉格朗 日插值法、牛顿插值法、厄米特插值法、样条插值法等多种插值方法中 的插值函数，都具有良好的性质( 如光滑性等) ，对描述诸如海岸线、山 脊线、云的轮廓等自然景物并不是一种较好的近似，这是因为海岸线等 表现出来的是连续非光滑、几乎处处不可导的性态。实际上，用传统的 插值方法求不出这样的插值曲线，我们要借助于一种特殊的插值法一一 分形插值法【2 2 】。而分形插值法借助计算机，可对许多自然现象，如树、 云彩、山脊线等进行非常逼真的模拟和再现。 自然景物的产生与绘制已经成为计算机图形学中非常活跃的一个分 9 西安理工大学硕士学位论文 支。分形插值法是美国数学家B a r n s l e y M F 于本世纪八十年代提出来的， 它是数据拟合的一种新方法。分形插值方法的基础是迭代函数系统的迭 代算法【”1 。分形插值不仅为函数逼近论开辟了崭新的研究领域，而且为 计算机图形学提供了有力的工具。 分形插值函数是由一类特殊的迭代函数系统( I F S ) 产生的。给定平 面上一组点集： “，y 1 ) R 2 l = O ，1 ，) ，X o X 1 O ，增量x ( t + ) 一x ( t ) 服从均值是0 ，方 差是 2 。的正态分布。如果用二维 ，y ) 坐标来代替上面的时间变量f ， 则随机函数x ( x ，y ) 可以被认为是二维空间的点0 ，Y ) 处的函数值，。如 果将这一函数值，赋予某一具体含义时，便可用来构造多种自然景物。 当厂被用来表示平面O ，) ，) 点处的高度值时，连接各网格点构成的曲面 分形自然景物模拟软件的算法实现 就是分形布朗曲面。本文中，我们就采用这种原理来模拟山脉，如果 将，设为平面伍，Y ) 点处的颜色值，便可用来生成云彩的纹理图案。 2 基于分形布朗运动的分形山建模方法 分形山建模方法有多种，大致可分为泊松阶跃法( P o i s s o n f a u l t i n g ) 、傅立叶滤波法( F o u r i e rf i l t e r i n g ) 、中点位移法( M i d p o i n t d i s p l a c e m e n t ) 、逐次随机增加法( S u c c e s s i v er a n d o ma d d i t i o n s ) 和带限 噪声累积法( S u m m i n gb a n dl i m i t e dn o i s e s ) 、小波变换【3 7 】等。 ( 1 ) 泊松阶跃法是由M a n d e l b r o t 研究的一种山脉生成算法，它是 将泊松分布用于f B m 的产物，它在服从泊松分布的间隔上，将高斯随 机位移加到一个平面或球面上，其结果具有f B m 特征。这种方法一般 用于复杂山体的生成，也适合用球面生成类似星球的物体。它的主要 缺点是算法的时间复杂度较高，达到了0m 【38 1 。 ( 2 ) 傅立叶滤波法是将一个二维的高斯白噪音进行傅立叶变换， 其结果就是f B m ，可以形成非常逼真的山脉模型。这种方法的优点是 可以获得任意的纹理图像效果，缺点是最终形成的山体结构具有周期 性，效率较低，此算法的时间复杂度是O ( nt o gn ) t 3 9 】。 ( 3 ) 中点位移法是一种分形几何法。它是利用细分过程中，在两 个点或多个点之间进行插值的方法来建立山脉的几何模型。它的缺点 是由于不同细分阶段所产生的点在相邻区域中有不同的统计特性，因 此，常会留下一道明显的裂痕。但是由于它与傅立叶滤波法相比，算 法简单，复杂度降为线性，生成山脉的速度很快，并且具有为已有的 形状增加细节的功能，因而是一种简洁而有效的山脉生成方法。 ( 4 ) 逐次随机增加法是一个灵活的细分方案。它是一种继承法， 新的点可以通过在上一级细分结果的基础上进行线性或非线性插值得 到。具体方法是，将上一级细分过程中确定的点，增加一个服从某种 分布的随机变量即可得到一个新的点。这个算法的时间复杂度依赖于 最终的分辨率和地表l a c u n a r i t y ( 空隙) 化【4 0 】的程度。l a c u n a r i t y 是作 西安J 里y - 大学硕士学位论文 为量化分形地表纹理的一个参数，其取值范围为l a c u n a r i t y ：- 1 。 ( 5 ) 带限噪音累积法( 也称为噪声合成法) 是一种基于函数的建 模方法。它是将频率范围受到严格限制的信号反复叠加，而其中每一 个信号的幅度是随机变化的，即噪声。这种方法的独特之处是，每个 点的确定独立于它的所有邻接点。 ( 6 ) 小波变换：这是近来出现的一种基于小波变换的多分辨率的 分析方法，采用迭代小波变换的算法，能有效地生成更精确的f B m 图 像f 4 1 1 。但算法比中点位移法复杂 4 2 , 4 3 】。 考虑到我们将生成的图形主要用于包装C A D 中，要求图形生成简 便快捷，形象美观，因此我们采用随机中点位移法来模拟山脉。 4 1 2 分形山的算法实现 算法设计是分形山生成的关键和难点。下面我们对其进行详细说 明。 I 分形山一维轮廓图的算法实现 在绘制分形山的一维轮廓图时，我们采用随机中点位移法。这是 一种分形插值算法。 用随机中点位移法模拟山脉时，开始以线段的两个端点为基础找 到这条线段的中点。其过程是这样的( 如图4 - 2 所示) ： 第一步，将一条线段作为初始元； 第二步，让这条线段的中点向上或向下移动一段随机距离，这样 就形成两条线段： 第三步，将这两条线段的中点又分别向上或向下移动一段随机距 离。 这样重复若干次，直到生成满意的山脉轮廓。每迭代一次，我们 都将中点的随机位移量的取值范围减少一些。否则，生成的山脉轮廓 线非常粗糙。这一设计过程的基本原理如下： 分形自然景物模拟软件的算法实现 从一条水平地平线段开始 重复1 1 - 次 对场景中的每条线段做 找到线段的中点 在Y 方向上随机移动中点一段距离 减小随机数的取值范围 r 。二 中点位移 ：=：j：j：二j；二；jP。117=：?：趣。 一一忒、。 厂 图4 - 2 随机中点位移法生成的山脉轮廓 迭代一i j ： 迭代= 次 选代三次 最终生成 其中，随机数值域减小的范围取决于我们要绘制山脉的陡峭程度。 在每次循环中，随机数的值域减少的越多，所得的山脊线就越平滑。 但如果减少的太多，又会有明显的锯齿感。在设计时，我们将粗糙度 的取值范围定为0 O 1 2 之间的浮点数，并称之为H 。因此p o w ( 2 0 ，H ) 是1 0 ( 对应于H = 0 O ) 到0 5 ( 对应于H = 1 O ) 范围内的数。 西安理工大学硕士学位论文 随机数的取值范围在每次循环时都要乘上这个值。如果H 设为1 0 ， 则随机数的取值范围在每次循环中减半，从而生成一个非常平滑的分 形山脉图形：将H 设为O 0 时，随机数的取值范围根本不会减小， 形成的山脉有明显的锯齿感。 图4 3 是在三个不同的粗糙度下绘制的山脊线。 幽4 - 3 不同粗糙度下绘制的山脊线 n = O8 I 卜( 5 H 等O 2 2 三维分形山脉的算法实现 山脉三维图形的设计，是在一维轮廓图形的理论基础上进行的， 其算法采用分形插值法中的D i a m o n d S q u a r e l 2 9 博法。这时我们对随机 中点位移法在构网方式及算法上进行改进，然后用它来模拟三维分形 山隙。 我们首先绘制分形山的线框图，然后用O p e n G L 对图形进行处理， 生成山脉的三维效果图。在程序设计中，通过增加网格中心点的高度 来产生山峰。 我们采用递归的方法生成分形山，具体算法如下： 第一步：在X - Y 平面上绘制一个n x n 的正方形网格，并对四个角 点在z 方向上分别设置初始高度加，肋， c ，榭，得到A ，B ，C ，D 这四个点，用黑点表示( 如图4 - 4 ( a ) 所示) ； 第二步：取相邻四个点组成的正方形A B C D ，在其中点生成一个 2 8 彳，、| 分形自然景物模拟软件的算法实现 随机值 J 。我们平均4 个顶点的高度值再加上这个随机量4 加，得到 中点的高度值。即正方形A B C D 网格中点M 的高度为： ，”= ( n + 6 + c + d ) 4 + 厶 J ( 4 - 1 ) 从而得到M 点( 如图4 - 4 ( b 1 所示) ； 第三步：根据角点A ，B ，c ，D 和中点M 以及网格外一虚拟点( 其 高度为0 ) ，计算边中点的高度，即 h e = ( h a + h b + h m + O ) 4 + Z 3 h l ( 4 - 2 ) h i = ( h b + h c + h m + O ) 4 + A h l ( 4 3 ) h g = ( h c + h d + h m + O ) 4 + A h l( 4 - 4 ) 胁= ( h d + h a + h m + O ) 4 + z 3 h l( 4 5 ) 其中，厶 J 为与第二步相似的随机量，从而得到E ，F ，G ，H 这 4 个点( 如图4 - 4 ( c ) 所示) ： 第四步：递归第二步和第三步，使正方形网格逐步细化，直至达到 预期的递归深度，然后连接每个正方形网格点。 矗C 田孵廉嚣暖 a C b ， ( 亡I C d )C c ) 图4 - 4 三维分形山的算法实现过程 这样，如果己经生成了一个种子正方形并经过单独一次细分过程， 得到4 个正方形，第二次经过该过程得到1 6 个正方形，第三次得到6 4 个正方形，增长得很快。正方形数目等于2 丑，其中，f 为递归经过细分 过程的次数。 经过第一次运算( 如图4 - 4 ( a ) 、( b ) 、( c ) 所示) ， 我们得到A ，B ， 西安理工大学硕士学位论文 C ，D ，M ，E ，F ，G ，H 这9 个点的几何数据。用线将这9 个点连起 来，就可以得到一个线框图，如图4 5 所示。 图4 5 第一遍递归后生成的线框图 下来进行第二遍递归过程。再次从第二步开始。第二遍与第一遍有 些不同：首先，现在有4 个四边形面，它们分别是E B F M ，M F C G ， H M G D ，A E M H ，因此我们要分别计算这四个方面的中心E ，F ，G ， H ( 如图4 - 4 ( d ) 所示) ： h e ，- ( h e + h b + 柏m ) 4 + Z 3 h 2 ( 4 - 6 ) h f = ( h f + h c + h g + h m ) 4 + z S h 2 ( 4 - 7 ) h g = ( h h + h m + h g + h d ) 4 + Z 3 h 2 ( 4 - 8 ) h h = ( h a + h e + h m + h h ) 4 + Z 3 h 2( 4 - 9 ) 然后，分别计算这4 个正方形边中点的高度( 如图4 - 4 ( e ) 所示) 。 其次，也是关键的一点，生成随机数的范围已经减小了。在第三 步中，4 个厶 j 是不一定相等的，因为他们都是随机数，但是它们的 取值范围相同。同样，在第二遍递归过程中，4 个4 2 也不一定相等， 但是它们也有相同的取值范围。A h 2 的取值范围要比A h l 的取值范围 小，我们这样设计是为了满足视觉上的需要，同时也可以使模拟出的自 然景物更加真实。 经过第二遍运算，图中2 5 个元素都已经生成，可以得到分形山的 线框曲面，如图4 - 6 所示。 3 n 分形自然景物模拟软件的算法实现 图4 - 6 第二遍递归后生成的线框图 我们前面提到过，用分形插值算法生成山脉，中点高度值是平均其 相邻4 个顶点的高度值再加上一个随机量得到的。由于不同细分阶段 产生的点在相邻区域中计算时，会得到不同的结果，这样就会留下一 道明显的裂痕。为了解决这一问题，在设计程序时，我们将一个区域 内的边界值拷贝给其相邻区域边界，以实现图形的无缝连接。 正如我们前面所讲，分形插值算法具有为已有形状增加细节的功 能，增加迭代次数，可以给曲面增加细节。迭代次数为5 时，分形山 的线框曲面图如图4 7 所示。 幽4 7 多次使J _ | ；| 分形插值算法的结果 3 分形山立体效果图的设计 现在分形山的线框图已经生成，下面要生成分形山的立体效果图。 首先，要判断山体中每个面的可见性，把可见面显示出来，隐去不可 见面；然后对可见的表面进行纹理映射。 在设计过程中，我们是用三角形来绘制山体表面的，因此利用三 西安理工大学硕士学位论文 角形的三个顶点的数据，可计算出该面的法向量。如图4 8 所示，平面 法向量的计算公式为： N = ( e o 一只) + 一置)( 4 - 1 0 ) P 图4 8 三角形平面法向量计算 表面法向量是垂直于相应平面指向平面外的矢量，观察方向矢量 是一条起始于表面法向量的起点指向观察点的矢量，如图4 9 所示。 P ( 观察点) 图4 - 9 凸多面体可见面的判别 从图中，我们得出 汹一s ( 端) ( 4 _ 1 1 ) 有了三角面的法向量，再求出观察者对该面片构成的方向向量， 根据公式( 4 - 1 1 ) ，通过观察方向向量与表面法向量的数量积的正负， 就可以判断出该面片是否可见：为正即可见，为负不可见。对于不可 见的面片就省去了以后的处理工作，提高了绘图效率。 入 一 N 一 分形自然景物模拟软件的算法实现 在生成了山体表面的消隐图后，用g l T e x C o o r d 2 f ( 1 函数进行纹理映 射，将我们在O p e n G L 中生成的纹理图映射到山体表面，便生成具有 真实感的三维分形山脉效果图。 4 2 云图的设计 云的模型设计可分为基于粒子系统的模型设计【4 4 , 4 5 】、基于物理过 程的模型设计1 46 1 、基于分形理论的模型设计1 4 ”、基于映射技术的模型 设计【4 8 , 4 9 】等等。但是这些云的模型设计方法很难做到既能快速建模， 又能得到真实感较强的云的模型。快速建模只是在一些高档机上实现， 而且利用了各种硬件加速。而在普通P C 机环境下，快速实现真实感较 强的云的模型设计还十分困难，其应用范围受到限制。因此，挖掘现 有的模型设计方法的潜力，在低配置环境下快速建立具有真实感的云 的模型十分必要。 由于云属于气体现象，其外观形状极不规则，没有光滑的表面， 而且极其复杂和随意，这使得用经典的欧几里德几何学对其描述显得 无能为力。考虑到纹理映射技术具有快速建模的优点，我们结合分形 理论和映射技术，用分形插值的方法生成模型的基础数据，通过转换 得到云图纹理，最后利用映射技术将纹理图映射到天空模型上，实现 蓝天白云效果图的绘制。其设计过程如下： 1 云彩纹理图的生成 我们采用递归的方法，通过分形插值算法，生成云的纹理图。具 体算法如下： 第一步：在平面上划分正方形网格n n ( 如图4 - 4 所示) ，随机给出 A ，B ，c ，D 这四个角点的颜色； 第二步：平均这四个角点的颜色，再加上一个随机生成的颜色值， 计算出中点M 的颜色； 第三步：计算正方形四个边中点的颜色：根据A ，B ，M 点和网格 西安理工大学硕士学位论文 外一虚拟点( 颜色值为0 ) 求平均，加上一个随机生成的颜色值，得到 边中点E 的颜色；根据B ，C ，M 点和网格外一虚拟点( 颜色值为O ) 求平均，加上一个随机生成的颜色值，得到边中点F 的颜色；根据c ， D ，M 点和网格外一虚拟点( 颜色值为O ) 求平均，加上一个随机生成 的颜色值，得到边中点G 的颜色：根据A ，D 。M 点和网格外一虚拟 点( 颜色值为O ) 求平均，再加上一个随机生成的颜色值，得到边中点 H 的颜色： 第四步：根据小正方形E B F M 四个角点颜色的平均值，求出小正 方形中点以及小正方形的四个边中点的颜色：然后再沿用上述规则， 分别计算小正方形M F C G ，H M G D ，A E M H 的各个中点和边中点的颜 色； 第五步：递归第四步，使其正方形网格不断细化，直至达到预期 的递归深度。 2 蓝天白云效果图的绘制 纹理贴图的数学过程是十分复杂的，我们运用O p e n G L 来完成纹理 贴图，经过投影变换及真实感效果处理后，得到蓝天白云的最终结果。 绘制过程包括下面两个部分： ( 1 ) 在三维空间中定义八面角锥作为天空模型： g l B e g i n ( G L _ T R I A N G L E _ F A N ) ； g l T e x C o o r d 2 f ( O _ f ，0 耽 g l V e r t e x 3 f ( O f 2 f ，0 D ； g l T e x C o o r d 2 f ( 一T M M A X 4 5 ，一T M M A X 4 5 ) ； g l V e r t e x 3 f ( - 1 0 工一1 5 , 1 0 t 3 ； g l T e x C o o r d 2 f ( 0 C - T M M A X ) ； g l V e r t e x 3 f ( 0 工一1 f 1 5 D ； g l T e x C o o r d 2 f ( T M M A X 4 5 ，- T M M A X 4 5 ) ； g l V e r t e x 3 f ( 1 0 - 1 f ，1 0 f ) ； 分形自然景物模拟软件的算法实现 g l T e x C o o r d 2 f ( T M M A X ，O f ) ； g l V e r t e x 3 f ( 1 5 _ f ，- 1 工0 f ) ； g l T e x C o o r d 2 f ( T M M A X 4 5 ，T M M A X 4 5 ) ； g l V e r t e x 3 f ( 1 0 工一I X , - l O f ) ； g l T e x C o o r d 2 ff o - f T M S 他X ) ； g l V e r t e x 3 f ( 0 工一1 f 一1 5 f ) ； g l T e x C o o r d 2 f ( - T M M A X 4 5 ，T M M A X 4 5 ) ； g l V e r t e x 3 f6 1 0 f ，一l X , 一1 0 D ； g l T e x C o o r d 2 f ( - T M M A X ，O f ) ； g l V e r t e x 3 f ( 一1 5 工一1 f ，0 f ) ； g l T e x C o o r d 2 f ( 一T M M A X 4 5 ，- T M M A X 4 5 ) ； g l V e r t e x 3 f ( - 1 0r f - 1 上1 0 D ； ) g l E n d ( ) ； ( 2 ) 利用O p e n G L 提供的纹理映射功能，将生成的云图纹理映射 到天空模型上，得到云的效果图。 4 3 漫游功畿的实现 在山脉和云彩生成以后，我们还要利用双缓存和坐标的平移及旋 转实现漫游功能。 实现整体效果图的漫游，是利用分形自身的特点，其算法内部的参 数变化会直接影响图形的外观，而且外观对参数的变化也是非常敏感的， 当我们在程序中将坐标进行连续平移及旋转变化时，程序所生成的图形 就会产生漫游的效果。我们利用O p e n G L 支持双缓存的技术，即创建两个 缓冲区，一个用来绘制图形，一个用来显示图形。在任意时刻只有两者 中的一个内容能被显示出来。当前可见