分形理论在计算机图形学中的应用毕业设计论文.doc

学院理学学士学位论文学院理学学士学位论文 分形理论在计算机图形学中的应用 -位图与矢量图形变换 史华平 二零零五年五月七日 分类号 学校代码 UDC 密级 学 号 学院学院 信息工程学院毕业论文信息工程学院毕业论文 分形理论在计算机图形学中的应用分形理论在计算机图形学中的应用 -位图与矢量图形变换 史华平史华平 指导教师 _詹 棠 森(副教授)_ 申请学位级别 信息与计算科学 论文提交日期 论文答辩日期 学位授予单位和日期 答辩委员会主席 论文评阅人 20 年 月 日 I 目录 目目录录. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .I I 摘摘要要. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .I II I A AB BS ST TR RA AC CT T. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .I II II I 第第一一章章 分分形形概概论论. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1 1 1.1 什么是分形 .1 1.2 分形的应用 .1 1.3 本文选题的背景.2 第第二二章章 分分形形相相关关理理论论问问题题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3 3 2.1 JULIA集 .3 2.2 逃逸时间算法的基本思想 .4 2.3 逃逸时间算法绘制 JULIA集与 MANDELBROT集.4 2.4 分形图形着色方案 .6 2.5 JULIA集与 MANDELBROT集图形的矢量变换.7 2.6 二维元胞自动机生成分形图案 .10 2.7 GUMOWSKI-MIRA公式.11 2.8 分形图形的位图操作 .11 第第三三章章 毕毕业业设设计计结结果果和和分分析析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2 23 3 3.1 程序概况 .23 3.2 程序说明.27 3.3 补充说明 .31 参参考考文文献献 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3 32 2 致致 谢谢. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3 33 3 A AP PP PE EN ND DI IX X. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3 34 4 附附录录. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4 40 0 理学学士学位论文 摘要 II 摘要 分形是一门几何学科，它研究的是欧氏空间的一类子集，但很难对它下一个确切 的定义。可以简单地说，如果一个对象的部分与整体具有自仿射变换关系，我们就可 以称它为分形。自分形之父曼德勃罗（Benoit Mandelbrot）在 1975 年出版专著分 形对象：形、机遇与维数 ，标志着分形理论正式诞生以来。分形已经广泛应用于物理、 化学、生物、医学、计算机科学等诸多领域，而本文着眼于分形理论与计算机知识的 结合。 因为分形图形有极强的艺术性，绘制得当，可以产生非常漂亮的图片，因此可以 用于装饰，包装，服装等需要艺术图案的场所。本文重点介绍了分形图形的重要生成 算法逃逸时间算法，并且详细说明了使用逃逸时间算法生成 Julia 集与 Mandelbrot 集的算法过程。另外，本文也详细说明了分形图形的一种着色方案，它可 以使分形图形的着色过程更富有过渡性，从而使图形具有更强的美感。本文还详细说 明了分形图形在计算机图形学相关理论上的应用，比如分形图形的矢量移动，旋转， 缩放，以及对分形图形进行相关特殊变换，此外，还可修改图形的参数，修改图形的 颜色等等。本文还涉及了元胞机自动图案的生成以及 Gumowski-Mira 分形，生成了经 典的三翅鹰图形，并且实现了对其色彩的编辑功能。 因为分形图形展示的是数学与艺术的成果，它日益受到人们的重视，甚至引发了 分形是不是艺术的讨论，随着时间的流逝，分形是一种艺术已经为人们所承认，分形 与计算机的结合也越来越紧密，计算机图形学中已经专门引入了分形算法，以生成自 然景观等。另外，分形在其它学科的应用也日益广泛，可见，分形在今后会得到更大 的发展，有更广阔的应用空间。 关键词关键词：分形，矢量变换，Julia 集，Mandelbrot 集,逃逸时间算法 理学学士学位论文 Abstract III ABSTRACT Fractal is a geometrical subject. It studies a subset of Euclidean geometry and cant be defined exactly. Say in a simple way, if one part of an object is affine with another part of this, we can say this object is a fractal. From 1975 Benoit Mandelbrot published his works Fractal: Form, Chance and Dimension, the theory of fractal is wildly used in physics, chemistry, biology, medicine, computer science etc. And this topic dedicate for the use of fractal theory in computer. Because the beauty of the fractal picture, if drawing in a good way, you can get a perfect picture, so the picture can be used for dress, porcelain, and so on. This topic point of the escaping time algorithm is the main way of drawing the fractal picture, but also show a new way to render the fractal picture in detail, it can give the picture more smoothly color change, thereby it give the picture more aesthetic feeling. Further, this topic explain the use of computer graphics theory in the fractal pictures creating, for example the vector move, circumvolve, zoom in, zoom out, and other vector transformation. In addition, picture parametric can be changed and picture colour can also be changed .this topic involved the Gumowski-Mira fractal, two dimension Cellular Automata fractal. Fractal unfurl an new world buildup with math and arts, Along with time flying, people think over fractal more and more, even brought an argument that fractal drawing is or not an art. All think fractal picture is an art production today, and also, fractal is used more and more in computer science. The computer graphics even add a new fractal algorithm to create nature sight. Aside, fractal theory used wider and wider in other subjects. We can say, fractal theory will use wider and deeper. Key Words: Fractal, Julia set, Mandelbrot set, Vector transformation, Escaping time algorithm 理学学士学位论文 第一章 分形概论 1 第一章 分形概论 1.1 什么是分形 什么是分形呢？很难给分形下一个确切的定义。严格地而且正式地去定义分形是 一件非常复杂而且困难的事情。但是，有一些不太正规的定义却可以帮助我们理解分 形的含义。在这些定义中，最为流行的一个定义是：分形是一种具有自相似特性的现 象、图像或者物理过程。也就是说，在分形中，每一组成部分都在特征上和整体相似， 只仅仅是变小了一些而已。分形在英文中为 fractal，是由美籍法国数学家曼德勃罗 (Benoit Mandelbrot)创造出来的。这个词意为不规则的，破碎的，分数的。曼德勃罗 想用此词来描述自然界中传统欧氏几何不能描述的一大类复杂不规则的几何对象，例 如，曲折的海岸线，起伏的山脉，变幻的浮云，纵横的血管等，它们有一个共同的特 点就是极不规则或极不光滑，直观而粗略地说，这些对象都是分形。分形作为几何对 象，是破碎的，不规则的，但不是所有破碎的，不规则的形状都是分形，分形一般还 具有自相似性，一个对象的部分与整体有自仿射变换关系，我们也可以称之为分形。 1.2 分形的应用 分形几何学已在自然界与物理学中得到了应用。如在显微镜下观察落入溶液中的 一粒花粉，会看见它不间断地作无规则运动（布朗运动） ，这是花粉在大量液体分子的 无规则碰撞下表现的平均行为。布朗粒子的轨迹，由各种尺寸的折线连成。只要有足 够的分辨率，就可以发现原以为是直线段的部分，其实由大量更小尺度的折线连成。 这是一种处处连续，但又处处无导数的曲线。这种布朗粒子轨迹的分维是 2，大大高于 它的拓扑维数 1。 在某些电化学反应中，电极附近成绩的固态物质，以不规则的树枝形状向外增长。 受到污染的一些流水中，粘在藻类植物上的颗粒和胶状物，不断因新的沉积而生长， 成为带有许多须须毛毛的枝条状，就可以用分维。 自然界中更大的尺度上也存在分形对象。一枝粗干可以分出不规则的枝杈，每个 枝杈继续分为细杈，至少有十几次分支的层次，可以用分形几何学去测量。当然， 理学学士学位论文 第一章 分形概论 2 还有海岸线的长度到底是多少这个问题也用到分形。 有人研究了某些云彩边界的几何性质，发现存在从 1 公里到 1000 公里的无标度区。 小于 1 公里的云朵，更受地形概貌影响，大于 1000 公里时，地球曲率开始起作用。大 小两端都受到一定特征尺度的限制，中间有三个数量级的无标度区。分形存在于这中 间区域。 近几年在流体力学不稳定性、光学双稳定器件、化学震荡反映等试验中，都实际 测得了混沌吸引子，并从实验数据中计算出它们的分维。学会从实验数据测算分维是 最近的一大进展。分形几何学在物理学、生物学上的应用也正在成为有充实内容的研 究领域。 1.3 本文选题的背景 分形几何，这门新的数学分支一创立，就日益受到各国学者的重视，在过去的十 几年里，分形科学已有了很大的发展。她在纯数学、物理学、材料科学、地质勘探、 疾病诊断、股价预测以及计算机和信息科学等许多领域中，都得到了广泛的应用。并 且由于分形几何方法的引入，使一些原已死寂的老学科方向焕发了新的生机，也使一 些正蓬勃发展的新学科获得了巨大的推动力。分形几何与计算机科学的结合就是一个 明显的例证。一方面，分形理论推动了计算机绘图方法的迅速发展，使计算机在信息 压缩及模仿自然现象中的各种奇妙图形发挥了重要的作用；另一方面，计算机的应用 也大大地推动了分形理论的发展，并且由于模拟分形图成功而展现出优美的分形图像， 迅速提高了分形这门新兴科学的声望，扩大了她的影响。目前用计算机绘制分形图是 如此流行，以致不仅使绘制分形的算法理论与程序设计已成为一个独立的研究方向， 同时绘制的分形图也已成了一种相当时髦的艺术形式。并且分形图形已经开始应用在 包装，服装，陶瓷装饰上面。分形理论已经极广泛地应用在计算机图形学中，许多的 计算机游戏与虚拟现实中大量应用到分形理论。 理学学士学位论文 第二章 分形相关理论问题 3 第二章 分形相关理论问题 2.1 Julia 集 Julia 集是分形中的一个经典集合，它的基本函数形式为：，其中 2 ( )F ZZC Z 与 C 都为复数。先考虑 C=0 的情况，Z 是复数，即 Z=x+yi，则有： 222 222 ()()2()2zzzxyixyixy ixyixyxyi 我们还可以定义复数 z=x+yi 的绝对值，即：，而|Z|恰好相反是从 22 | zxy 原点到 Z 的距离。 下面讨论的一些性质，假设此方程以点，且开始迭代， 2 ( )f zz 000 zxy i 0 | 1z 则有： 22 00000 |()| |2|F zxyx y 2222 0000 ()(2)xyx y 442222 000000 24xyx yx y 222 00 ()xy 因此，在区域中，这意味着对的每一个一次 0 0 | 1z 00 |()| |F zz 2 ( )F zz 迭代，即，都会使 z 向靠 0 的方向移动，可以说此时 z 向 0 收敛。 2 1nn zz 当时，通过上面的计算，可以得知，此时 z 会趋向于。 0 | 1z 当时，很显然，z 是平面单位圆上的点。 0 | 1z 于是，我们发现，复平面上可分为两个区域，一个区域合落在其中的点向 0 收 敛，而另一个区域合落在其中的点向逃逸，它们的分界线便是。 0 |()| 1F z 然而，当时，它向一个区域收敛，而不是向一个点收敛，被吸进去的点会0C 遍历整个区间，我们称这个区间为混沌区。与此同时，分割混沌区和向逃逸的分界 线不再是的单位圆，它将是一个不规则、不光滑的分界线。 0 |()| 1F z Julia 集图形：见图 3.1.1。 理学学士学位论文 第二章 分形相关理论问题 4 2.2 逃逸时间算法的基本思想 根据上述想法，我们将吸引域的概念进一步扩展。如图 2.2 所示，假设有一个充分 大的整数 N，当未逃逸区域 M 中的初始点 a 经过小于 N 次迭代就达到未逃逸区域 M 的边界，甚至超出了边界，我们就认为点 a 逃逸出去了；而如果经过 N 次迭代后，a 的轨迹仍未到达 M 的边界，我们就认为 a 是 A 上的点，用这样的方法描绘出 A 的边界 图形，这就是逃逸时间算法的基本思想。 逃逸区 M 收敛区域 A 未逃逸区 M 逃逸边界 图 2.2.1 2.3 逃逸时间算法绘制 Julia 集与 Mandelbrot 集 1，从逃逸时间算法的角度来看，Julia 集的内部收敛于某一个点或者几个点，而 Julia 集的外部随着逃逸时间 t 的增加将发散至，其逃逸边界就是 Julia 集。Julia 集的逃逸时间算法如下： 假设绘图窗口的宽度为 width，高度为 height。 选定参数， 1 Cpqi ，M=100，maxTime=200，令： minmin 1.5xy maxmax 1.5xy maxmin ()/(1)xxxwidth maxmin ()/(1)yyyheight 理学学士学位论文 第二章 分形相关理论问题 5 其中 C 表示复数上一个点，表示参数窗口大小，M 表示逃 min x max x min y max y 逸边界值，maxTime 表示循环可以执行的最大次数。对所有的点 ，完成如下步骤的循环：(,),0,1,2,3.10,1,2,3.1 xyxy n nnwidthnheight及 令，t=0。 2 0min * x xxnx 0min * y yyny 根据下列的迭代过程从算出，计数 t=t+1。 3 ( ,) tt x y 11 (,) tt xy 22 1 1 2 ttt ttt xxyp yx yq 计算： 4 22 tt rxy 如果，则转到步骤。rM 5 如果，且，则转至步骤。rMmaxtTime 3 如果，转到步骤。maxtTime 5 对点着色，并转至下一步，再头从做步骤。着色方案将在下面作详细 5 (,) xy n n 2 介绍。 Julia 集图形：见图 3.1.1。 2，绘制 Mandelbrot 集：设 Z=x+yi，C=p+qi，C 的取值范围为： minmax minmax :, :, ppp qqq 假设绘图窗口的宽度为 width，高度为 height。 1 minmaxminmax p=-2.2,p=1.0,q=-1.1,q=1.4 ，逃逸半径 M=100，maxTime=200，对绘 图窗口中所有的点，完成如下步(,) pq nn0,1,2.1,0,1,2.1 pq nwidthnheight 骤。 令 2 maxmin ()/(1)xxxwidth maxmin ()/(1)yyyheight 利用下式从( ,) kk xy 得到 11 (,) kk xy ，计数 k=k+1 3 22 1 1 2 kkk kkk xxyp yx yq 计算： 4 22 tt rxy 如果，则转到步骤。rM 5 如果，且，则转至步骤。rMmaxtTime 3 理学学士学位论文 第二章 分形相关理论问题 6 如果，转到步骤。maxtTime 5 对点着色，转至下一点，步骤。 5 (,) pq nn 1 读完所有参数空间的点（p,q） ，结束循环。 6 Mandelbrot 集图形：见图 3.1.2。 2.4 分形图形着色方案 RGB 色彩模式是工业界的一种颜色标准，是通过对红(R)、绿(G)、蓝(B)三个颜色 通道的变化以及它们相互之间的叠加来得到各式各样的颜色的，RGB 即是代表红、绿、 蓝三个通道的颜色，这个标准几乎包括了人类视力所能感知的所有颜色，是目前运用 最广的颜色系统之一。目前的显示器大都是采用了 RGB 颜色标准，目前的电脑一般都 能显示 32 位颜色，约有一百万种以上的颜色。在数字视频中，对 RGB 三基色各进行 8 位编码就构成了大约 16.7 万种颜色，这就是我们常说的真彩色。我们对分形图形进 行着色也使用这种色彩模型。 颜色设置：我们根据逃逸时间算法的循环次数来给分形图着色，假定 k 为循环次 数，也就是上面所说的逃逸时间，time 为颜色锐化值，m_nRed，m_nGreen，m_nBlue 为 R，G，B 的初始值，有如下结果： k *= time; red = k + m_nGreen; green = k +m_nBlue; blue = k + m_nRed; 下面对求得的 red，green，blue 三个值进行变换。因为程序绘图时使用 24 位真彩 色，所以 R,G,B 三个值的大小都不应该超过 8 位的最大值，即 255，而这个 8 位的最 大值，用 16 进制表示就是 0 xFF。如果 R,G,B 中的任何一个值大于 0 xFF，就对其进行 0 xFF 的位运算。然后再将根据上述步骤求得的 R、G、B，用函数 RGB(R,G,B)换成色 彩，从而实现对 Julia 集的着色。用计算机语言来表示就是这样： if (red if (green if (blue 上面的 red，green，blue 分别表示 RGB 颜色模型中的 R，G，B。red，green，blue 与 0 x1FF 进行 xMax = xMin + tmpDouble; tmpDouble = yMax - yMin; yMin = yMin - y * (newPoint.y - oldPoint.y); yMax = yMin + tmpDouble; 经过实验证明，这个方法对 Julia 集与 Mandelbrot 集都适用。 图形矢量移动前后效果对比参见图 3.1.1 与图 3.1.8。 2，Julia 集与 Mandelbrot 集的矢量放大:先说明对 Mandelbrot 集的放大, Mandelbrot 集是将参数 C 走遍参数窗口的所有值，经过逃逸时间算法的运算最终 在绘图窗口中画出图来，由此可知，参数窗口的大小和位置就决定了所绘 理学学士学位论文 第二章 分形相关理论问题 8 Mandelbrot 集的放大区域。已知， maxmin ()/(1)xxxwidth ，其中 maxmin ()/(1)yyyheight min * t ppxp min * t qqyq ，可以得出：0,1,2.1 t xn0,1,2.1 t yn min min * * ppxp qqyq 从而可得： 用计算机语言来描述就是： xMin = xMin + x*oldPoint.x; xMax = tmpDouble + x*newPoint.x; tmpDouble = yMin; yMin = yMin + y*oldPoint.y; yMax = tmpDouble + y*newPoint.y; 这样我们只要将得到的(xMin,yMin)，(xMax,yMax)代替原来的参数窗口值就可以 实现对窗口的放大了。 Julia 集的放大原理与 Mandelbrot 集的放大原理相同，就不再赘述了。 图形的矢量放大前后效果对比见图 3.1.1 与图 3.1.9。 3，Julia 集的旋转： 由计算机图形学可知，在二维平面上按指定位置旋转，需要经过三个步骤： rr (x ,y ) 1、平移对象使移动点位置移到坐标原点。 2、绕坐标原点旋转。 3、平移对象使基准点回到其原始位置。将其写成矩阵形式如下： 100cossin010 010 * sincos0 * 01 001001001 cossin(1 cos )sin sincos(1 cos )sin 001 r r r r x y xy yx 转换成式子如下： minminmin minminmin maxmaxmax maxmaxmax * * * * ppxp qqxq ppxp qpxp 理学学士学位论文 第二章 分形相关理论问题 9 rrr rrr x = x + (x-x )*cos - (y-y )*sin y = y + (x-x )*sin + (y-y )*cos 将这个式子应用到 Julia 集绘制算法中，这里假定绕屏幕的中点旋转，屏幕的宽度 为 width，高度为 height，用坐标表示为(width/2，height/2)，从前面绘制 Julia 集的方法中可知下列两个步骤： ，。 1 0min * x xxnx 0min * y yyny 根据下列的迭代过程从算出，计数 t=t+1。 2 ( ,) tt x y 11 (,) nn xy 22 1 1 2 ttt ttt xxyp yx yq 这里只需要修改的值，所以可得：, xy n n x xxy y temp = n n = width/2 + (n - width/2) * cos - (n - height/2) * sin n = height/2 + (temp - width/2) * sin + (ny - height/2) * cos 再将获得的，进行，的运算，得到新的。, xy n n min * tx xxnx min * ty yyny, tt x y 再将进行下一步运算即可实现对 Julia 集的旋转。图形的矢量旋转前后效果对比, tt x y 见图 3.1.1 与图 3.1.12。 4，将 Julia 集压缩到 Mandelbrot 集的收敛区域，要将 Julia 集压缩到 Mandelbrot 集收 敛区域中，需要先对前面绘制 Julia 集算法中提到的进行 Mandelbrot 集(,) nn xy 算法变换，然后再进行 Julia 集算法变换。又因为逃逸时间算法绘制 Julia 集和 绘制 Mandelbrot 集的步骤都是一样的，差别只体现在步骤，即由计算 3 (,) nn xy 出 11 (,) nn xy 这一步。即要在前面提到的绘制 Julia 集的计算机算法步骤后面 2 添加下列几步算法： 令 t1=-0.7,t2=，i=0，t3=t4=0,N=10 进行如下循环。 A 0 x 0 x B 0 0 t3 = t1 * t1 - t2 * t2 + x -0.7 t4 = 2 * t1 * t2 + y t1 = t3 t2 = t4 计数 i=i+1。 如果 itop; pt2.x = lpRect-right; pt2.y = lpRect-bottom; ClientToScreen(hWnd, ClientToScreen(hWnd, lpRect-left = pt1.x; lpRect-top = pt1.y; lpRect-right = pt2.x; lpRect-bottom = pt2.y; / get the DIB of the client area by calling / CopyScreenToDIB and passing it the client rect hDIB = CopyScreenToDIB(lpRect); / return the handle to the DIB return hDIB; HDIB CGlobal:CopyScreenToDIB(LPRECT lpRect) HBITMAP hBitmap; / handle to device-dependent bitmap HPALETTE hPalette; / handle to palette HDIB hDIB = NULL; / handle to DIB / get the device-dependent bitmap in lpRect by calling / CopyScreenToBitmap and passing it the rectangle to grab hBitmap = CopyScreenToBitmap(lpRect); / check for a valid bitmap handle 理学学士学位论文 第二章 分形相关理论问题 14 if (!hBitmap) return NULL; / get the current palette hPalette = GetSystemPalette(); / convert the bitmap to a DIB hDIB = BitmapToDIB(hBitmap, hPalette); / clean up DeleteObject(hPalette); DeleteObject(hBitmap); / return handle to the packed-DIB return hDIB; HBITMAP CGlobal:CopyScreenToBitmap(LPRECT lpRect) HDC hScrDC, hMemDC; / screen DC and memory DC HBITMAP hBitmap, hOldBitmap; / handles to deice-dependent bitmaps int nX, nY, nX2, nY2; / coordinates of rectangle to grab int nWidth, nHeight; / DIB width and height int xScrn, yScrn; / screen resolution / check for an empty rectangle /MessageBox(HWND)AfxGetApp()-GetMainWnd(),122,123,NULL); if (IsRectEmpty(lpRect) return NULL; / create a DC for the screen and create / a memory DC compatible to screen DC hScrDC = CreateDC(DISPLAY, NULL, NULL, NULL); hMemDC = CreateCompatibleDC(hScrDC); / get points of rectangle to grab nX = lpRect-left; nY = lpRect-top; 理学学士学位论文 第二章 分形相关理论问题 15 nX2 = lpRect-right; nY2 = lpRect-bottom; / get screen resolution xScrn = GetDeviceCa