Computer Graphics 第八章 分形几何.

Presentation on theme: "Computer Graphics 第八章 分形几何."— Presentation transcript:

1 Computer Graphics 第八章 分形几何

2 本章内容 8.1 分形和分维 8.2 递归模型 8.3 L系统模型 8.4 IFS迭代函数系统模型

3 8.1分形和分维 真实的世界却并不规则，闪电不是直线，海岸 线不是弧线，云团不是球体，山峦也不是锥体。自 然界的许多对象是如此不规则和支离破碎，以致欧 氏几何学不能真实有效地再现大自然。 为了再现真实世界，必须选择新的工具，分形 几何学应运而生。分形几何是以非规则物体为研究 对象的几何学。由于闪电、海岸线、云团、山峦、 海浪、野草、森林、火光等非规则物体在自然界里 比比皆是，因此分形几何学又被称为描述大自然的 几何学。

4 分形山

5 8.1.1 分形的诞生 8.1.2 分形的基本特征 8.1.3 分形的定义 8.1.4 分形维数的定义

6 8.1.1 分形的诞生 分形（Fractal）这个词，是由美籍法国数学家 曼德尔布罗特（Benoit B.Mandelbrot）自己创造出 来的，此词来源于拉丁文fractus，意为不规则、支 离破碎。1967年曼德尔布罗特在美国《科学》杂志 上发表了划时代的论文《英国海岸线有多长？统计 自相似与分数维》，成为其分形思想萌芽的重要标 志。1973年，在法兰西学院讲学期间，曼德尔布罗 特提出了分形几何学的整体思想，并认为分数维是 个可用于研究许多物理现象的有力工具。1982年曼 德尔布罗特出版了《大自然的分形几何学》，引起 了学术界的广泛重视，曼德尔布罗特也因此一举成 名。

7 英国的海岸线 蕨类植物叶的自相似性

8 8.1.2 分形的基本特征 1.自相似性 自相似性是指局部与整体相似的性质。图 8-3所示的是蕨类植物叶子上的细叶和整体叶 子的相似性。
分形图形都具有细节的无穷回归性，随着 尺度的缩短都会得到更多的细节。分形理论发 展到今天，如果一个对象的部分和整体具有自 仿射变换的关系，也可以称之为分形。

9 2.无标度性 标度是计量单位的刻度。比如长度的 标度是米；重量的标度是公斤；面积的标度 是平方米等。对欧氏几何学内的不同形体， 可以选择不同的标度去度量。 分形却不然，由于分形具有无穷嵌套的 精细结构，自相似性使得其内部结构不存在 特征长度。分形没有特征标度，也就是不能 用标度去度量，成为无标度性。

10 8.1.3 分形的定义 一般认为，满足下列条件的图形称为分形集： 分形集具有任意尺度下的比例细节，或者说具有精细结构；
分形集是不规则的，以致于不能用传统的几何语言来描述。 分形集通常具有某种自相似性，或许是近似的或许是统计意义下的自相似。 分形集在某种方式下定义的“分维数”一般大于它的拓扑维数。 分形集的定义常常是非常简单的，或许是递归的。

11 8.1.4 分形维数的定义 维数是几何对象的一个重要特征量，它是欧氏几 何对学描述点的位置所需的独立坐标数目。为了 定量地刻画分形，引入了分数维数的概念。分数 维数与欧氏几何学中的整数维数相对应。 分形理论认为，维数中可以包含有小数。把分数 维数记为D，一般称为分数维或分维。 分维的定义有很多，有相似维数、容量维数、豪 斯道夫维数等。本章只介绍相似维数。

12 分维的计算公式为： 代表分维 为和整体自相似的局部形体个数 为相似比

13 ⑴对于直线： 将一直线段二等分， 则N=2，S=2，即2=21， 所以，分维D=1

14 ⑵对于平面： 将正方形四等分，则N=4，S=2，即4=22，所 以，分维D=2

15 ⑶对于立体： 将立方体八等分， N=8，S=2，即8=23， 所以，分维D=3

16 ⑷对于典型的分形曲线， 例如Koch曲线，构成方法 如下：
取一直线段，将其三等 分，保留两端的两段，将 中间一段拉起为等边三角 形的两条边。 N=4，S=3 分维D=ln4/ln3=

17 从图中n＝5的递归图形中可以看出koch曲线点 点连续，但点点不可导，属于病态曲线；koch 曲线局部和整体相似，具有自相似性。因此可以 使用koch曲线来模拟海岸线。根据曼德布罗特 的计算，英国海岸线的分形维数为D=1.25。

18 8.2递归模型 分形图形的传统实现模 型是递归模型。在调用一个 函数的过程中，直接或间接 地调用函数自身，称为递归 调用。例如n！可以采用递归 模型实现。即5！＝5×4！， 而4！＝4×3！，……，1！ ＝1，递归公式表示如下： long fac(int n) { long f; if(n==0||n==1) f=1; else f=fac(n-1)*n; return f; }

19 8.2.1 Cantor集 8.2.2 Koch曲线 8.2.3 Peano-Hilbert曲线 8.2.4 Sierpinski垫片、地毯 和海绵 8.2.5 C字曲线 8.2.6 Caley树

20 8.2.1 Cantor集 集合论的创始人康托（G.Cantor，1845～1918） 在1883年曾构造了一种三等分Cantor集，其几何表 示如下： 生成规则：取一段长度为L0的直线段，将其三等分， 保留两端的线段，将中间一段抛弃，如图8-9的n＝1 的操作；再将剩下的两段直线分别三等分，然后将其 中间一段抛弃，如图8-9的n＝2的操作；依此类推， 便形成了无数个尘埃似的散点，所以cantor三分集也 称为cantor灰尘。 “病态”原因：数目无穷多，但长度趋近于零。 分形维数：D＝ln2/ln3=0.6309。

21

22 8.2.2 Koch曲线 1904年，瑞典数学家科和（Koch，1870～1924） 发现一种曲线，其几何表示如下：
生成规则：取一段长度为L0的直线段，如图8-7 n＝0 所示，将其三等分，保留两端的线段，将中间一段改 换成夹角为60°的两个L0/3等长直线段，如图8-7 n ＝1所示；将长度为L0/3的4个直线段分别三等分，并 将它们中间的一段改换成夹角为60°的两个L0/9等长 直线段，如图8-7 n＝2所示。依此类推，便得到具有 自相似结构的折线。如果在等边三角形上按上述规则 在每边的中间各凸起一个小三角形，这样一直进行下 去，则曲线形状近似为似一朵雪花，称为Koch雪花， 如图8-11所示。

23 理论上可以证明这种不断构造的雪花周长是 无穷的，但其面积却是有限的，这和传统的数学 观念是不相符的，采用周长和面积都无法刻划出 这种雪花的特点，欧氏几何学对描述这种雪花无 能为力。
“病态”原因：处处连续，处处不可导。 分形维数：D=ln4/ln3= 。

24

25 生成元：koch曲线是著名的分形曲线，具 有自相似性。其中生成元是图8-12所示的图形。 生成元的第一段直线段和第二段直线段之间的夹 角可以为任意角度（0°<θ<90°），不同的角 度值生成的Koch曲线有很大差异。最常用的角度 是θ＝60°和θ＝85°。生成元的起点和终点坐 标分别为（ax，ay）和（bx，by），Koch曲线共 由四条直线段构成。Koch曲线的递归调用是通过 反复使用生成元来取代每一段直线而进行的。

26 8.2.3 Peano-Hilbert曲线 意大利数学家皮亚诺（Peano，1858～1932） ，通过对一些古代装饰图案的研究，于1890年构 造出一种奇怪的平面曲线，这条曲线蜿蜒向前， 一笔绘成，并能充满整个平面。接着德国数学家 希尔伯特(Hilbert，1862～1943)于1891年也构造 出一种类型相同但比较简单的曲线。这种曲线被 称为Peano-Hilbert曲线。

27 Peano-Hilbert曲线的出现，当时曾令当 时的数学界大吃一惊：
它是一条曲线，但又是一个平面； 皮亚诺曲线的方程只有一个参数，但它 却能确定了一个平面；而在欧氏几何学中，确 定一条曲线需要一个参数，确定一个平面需要 两个参数。

28 生成规则：首先，将一正方形四等分为四个小正 方形，求出各个小正方形的中心并用三条直线连 接起来，如图8-13 n＝0所示，可以使用两种连 接方式：开口向上和开口向左。其次，将各个小 正方形再细分为四个小正方形，用三条直线连接 各个小正方形的中心，也会有两种连接方式，如 图8-13 n＝1所示。依此类推，便形成Peano- Hilbert曲线。 “病态”原因：一维曲线却能充满整个平面。 分形维数：D=ln4/ln2=2。

29 n＝0 n＝1 n＝2

30 8.2.4 Sierpinski垫片、地毯和海绵 年，波兰数学家谢尔宾 斯基(Sierpinski， )将三分 康托尔集的构造思想推广到二维平面和 三维立体，构造出千疮百孔的谢尔宾斯 基垫片、地毯和海绵。

31 1.谢尔宾斯基垫片 生成规则：取一等边三角形，连接各边 中点将原三角形分成四个小三角形，然后舍 弃位于中间的一个小三角形，如图8-16 n＝ 1所示。将剩下的其余三个小三角形按同样 方法继续分割，并舍弃位于中间的那个三角 形，如图8-16 n＝2所示。如此不断地分割 与舍弃，就能得到中间有大量孔隙的 Sierpinski垫片。

32 “病态”原因：总周长趋于无穷，总面 积趋于零。也就是说：当用一维得尺 度去测量时，其值趋于无穷大，当用 二维尺度去度量时，其值趋于零。
分形维数：D=ln3/ln2=1.5849。

33

34 Sierpinski垫片生成元

35 2.谢尔宾斯基地毯 生成规则：取一正方形，将其每条边三 等分，正方形被等分为九个面积相等的小 正方形，舍弃位于中央的一个小正方形， 如图8-18 n＝1所示。将剩下的八个小正方 形按上面同样的方法继续分割，并舍弃位 于中间的那个小正方形，如图8-18 n＝2所 示。如此不断地分割与舍弃，就能得中间 有大量空隙的Sierpinski地毯。

36 “病态”原因：总周长趋于无穷，总面 积趋于零。也就是说：当用一维得尺度 去测量时，其值趋于无穷大，当用二维 尺度去度量时，其值趋于零。
分形维数：D=ln8/ln3=1.8927。

37 n＝2 n＝1 n＝3 n＝4

38 生成元：Sierpinski地毯是平面分形，具有自相似 性。其生成元是把正方形分成九个小正方形，舍 弃中间一个正方形，余下八个小正方形，如图8- 19所示。正方形的左上角点和右下角点是生成元 的设计顶点。Sierpinski地毯的递归调用是通过 反复使用生成元来取代每一个小正方形进行的。 大正方形的左上角点和右下角点为：（x1，y1）， （x2，y2）。

39

40 3.谢尔宾斯基海绵 生成规则：将一个立方体沿其各个面等 分为九个小立方体，舍弃位于体心的一个小 立方体，以及位于立方体六个面心的六个小 立方体，如图8-20 n＝1所示。将二十个小 立方体继续按相同的方法分割并舍弃位于立 方体体心和面心处的更小的立方体，如图8- 19 n＝2所示。如此不断地分割与舍弃，就 能得到中间有大量空隙的Sierpinski海绵。

41 “病态”原因：有限体积具有无限表面积， 也就是说：当用二维得尺度去测量时，其值 趋于无穷大，当用三维尺度去度量时，其值 趋于零。
分形维数：D=ln20/ln3=2.7288。

42 n＝1 n＝2 n＝4 n＝3

43 生成元：Sierpinski海绵是分形立体，具 有自相似性。其生成元是把立方体分成二十七 个小立方体，挖去立方体六个面心的小立方体 以及位于体心的一个小立方体，共挖去七个小 立方体，见图8-21。Sierpinski海绵的递归调 用是通过反复使用生成元来取代每一个小正方 体进行的。

44 每个立方体在图形显示上是由前面、顶面 和右面三个面构成的。设正方形的左上角点为 （x，y），边长为d。对于顶面和右面，由于 其为平行四边形，其夹角为45°的斜边的水平 投影 DX＝d×cos(π/4)， 垂直投影DY＝d×sin(π/4)。因为DX＝DY，所 以全部以DX代替。

45 Sierpinski海绵生成元

46 生成元结构

47 8.2.5 C字曲线 生成规则：以一条直线段为斜边，拉出一个等腰直角 三角形，如图8-25 n＝1所示。以该三角形的两条直 角边分别为斜边，再拉出两个等腰直角三角形，如图 8-25 n＝2所示。依此类推，便形成了类似字母C的图 形，如图8-25 n＝10所示，称为C字曲线。

48 C字曲线

49 生成元：C字曲线具有很强的自相似性，是 分形图形。生成元是等腰直角等边三角形。 如图8-26所示。C字曲线的递归是通过反复 以生成元的直角边作为斜边拉出等腰直角三 角形而建立起来的。

50 8.2.6 Caley树 生成规则：以如图8-27n＝2所示二叉树为 基础，以每个分支为主树干，按照比例递归出另 一个二叉树，如图8-27n＝3所示。依此类推，便 形成了疏密有致的分形树，称为Caley树。

51 生成元：Caley树是完全自相似的分形结构。 生成元是二叉树

52 8.3 L系统模型 L系统是美国生物学家Aristid Lindenmayer提出的 研究植物形态与生长的描述方法，起初只用于描述 植物的拓扑结构，即植物的主干与旁支之间的相邻 关系，后来把几何解释加进描述过程，形成所谓的 L系统。1984年，A.R.Smith首次将L系统与计算机 图形学结合起来，为计算机模拟植物生长提供了一 个有力的工具。

53 8.3.1 L系统文法 1 文法模型 L系统是一种形式语言，包括： （1）字母表：使用到的字母 （2）公理：初识字母
（3）生成规则：字母的变换形式

54 2 绘图规则 设想一只乌龟在海滩爬行，其状态用3个参数 描述 。 (1)F：向前爬行一步 (2)+：逆时针旋转 (3)-：顺时针旋转 (4)[：将当前状态压入堆栈，但不画线 (5)]：从堆栈中弹出一个状态作为当前状态，但不 画线

55 8.3.2 Koch曲线

56 8.3.3 分形草

57

58 8.3.4 Peano-Hilbert曲线 8.3.5 分形灌木丛

59 8.4 IFS迭代函数系统模型 1985年美国佐治亚大学的M.F.Barnsley首先应用一 组仿射变换族模拟自然景物，并将仿射变换集称为 迭代函数系统。IFS的基本思想是，分形具有局部与 整体的自相似性，也就是说局部是整体的一个小复 制品，只是在大小、位置和方向上有所不同而已； 而数学中的仿射变换是一种线性变换，正好具有把 图形放大、缩小旋转和平移的性质。因此，产生一 个复制品的过程就相当于对图形进行一次压缩仿射 变换。

60 8.4.1 仿射变换

61 仿射变换最主要的性质是保留了直线的“平 直性”和“平行性”。
平直性：仿射变换是线性变换，直线段经仿 射变换后仍为直线段，并且保持直线上点的 定比关系不变。 平行性：两条平行直线经仿射变换后，仍然 保持平行。

62 8.4.2 IFS 1.压缩仿射变换 2.IFS码的计算 3.初始值问题

63 压缩映射定理

64 8.4.3 Koch曲线

65

66

67

68 8.4.4 Sierpinski垫片

69 Koch曲线算法 给定不同的递归深度，绘制Koch曲线： 算法设计 (1)输入递归深度n和夹角theta。
(4)先绘制第一段直线，然后改变夹角alpha,分别绘制其 余3段直线。 (5)执行递归子程序，对生成元的各部分进行递归并绘制 曲线。

70 Koch曲线文法模型算法 给定不同的递归深度，使用L系统模型绘制Koch曲线： 算法设计 (1)定义包含结点位置和角度的结点类
代表结点的状态（x,y,alpha） (2)输入递归深度n和夹角theta。 (3)计算生成元递归n次后的最小线元长度 (4)根据n生成规则字符串的替换。 (5)访问最终公理的每一个字母，根据绘图规则绘制图形。

71 Koch曲线的IFS图形算法 算法设计 (1)定义二维数组Code[4][7],读入4个仿射变换的IFS码 (2)设定循环次数为100000
(3)生成随机数R，在0~1之间 (4)分配仿射变换的概率空间。 (5)判断随机数R落在哪一个概率空间，并调用相应的仿射 变换所具有的IFS码，赋给相应的仿射变换系数 (6)进行仿射变换。 (7)根据概率调整RGB函数的分量，绘制点。 (8)循环（2）-（7） (9)完成循环次数结束

72 8.5 本章小结 分形几何是科学与艺术相融合的一门新学科， 是计算机图形学的一个崭新的应用领域。计算机图 形学搭建起了科学和艺术的桥梁，将枯燥的数学公 式表现为具体的视觉感受。本章在介绍分形的基本 原理、分维的计算方法等概念的基础上，主要讲解 了Cantor集、Koch曲线、Peano-Hilbert曲线、 Sierpinski垫片、Sierpinski地毯、Sierpinski海 绵等曲线的递归模型。在L-系统模型中给出了文法 生成规则，绘制了分形植物，L-系统的关键是确定 生成规则。IFS方法是分形的最有特色的领域，确定 了IFS码就可以绘制图形。同时IFS算法也是分形图 形压缩的基础，有兴趣的读者可以参考相关书籍学 习。