计算机图形学-图形的表示与数据结构

1、2021/8/141o 如何在计算机中建立恰当的模型表示不同图形如何在计算机中建立恰当的模型表示不同图形对象。对象。o 如何组织图形对象的描述数据以使存储这些数如何组织图形对象的描述数据以使存储这些数据所要的空间最省，检索、处理这些数据的速据所要的空间最省，检索、处理这些数据的速度较快。度较快。第四章第四章 图形的表示与数据结构图形的表示与数据结构2021/8/142o 基本概念基本概念o 三维形体的表示三维形体的表示o 非规则对象的表示非规则对象的表示o 层次建模层次建模图形的表示与数据结构图形的表示与数据结构2021/8/143o 造型技术造型技术o 基本图形元素基本图形元素o 几何信息与

2、拓扑信息几何信息与拓扑信息o 坐标系坐标系o 实体的定义实体的定义o 正则集合运算正则集合运算o 欧拉公式欧拉公式4.1 4.1 基本概念基本概念2021/8/144o 把研究如何在计算机中建立恰当的模型表示不把研究如何在计算机中建立恰当的模型表示不同图形对象的技术称为造型技术。同图形对象的技术称为造型技术。o 有两类图形对象：有两类图形对象： 规则对象：几何造型、几何模型规则对象：几何造型、几何模型(几何信几何信息和拓扑信息息和拓扑信息)。 不规则对象：过程式模拟。不规则对象：过程式模拟。基本概念基本概念造型技术造型技术2021/8/145基本概念基本概念基本图形元素基本图形元素p 基本图形

3、元素基本图形元素：图素或图元、体素。：图素或图元、体素。p 图素图素是指可以用一定的几何参数和属性参数描是指可以用一定的几何参数和属性参数描述的最基本的图形输出元素（包括点、线、面述的最基本的图形输出元素（包括点、线、面、环、体等）。、环、体等）。p 在二维图形系统中将基本图形元素称为图素或在二维图形系统中将基本图形元素称为图素或图元，在三维图形系统中称为体素。图元，在三维图形系统中称为体素。2021/8/146o 1、点：为、点：为0维几何元素，是形体最基本的元素，自由曲维几何元素，是形体最基本的元素，自由曲线、曲面或其他形体均可用有序的点集来表示。点集及线、曲面或其他形体均可用有序的点集来

4、表示。点集及其连接关系的存储。其连接关系的存储。o 2、线：一维几何元素，是两个邻面或多个邻面的交界、线：一维几何元素，是两个邻面或多个邻面的交界o 3、面：二维几何元素，是形体上一个有限、非零的区、面：二维几何元素，是形体上一个有限、非零的区域，由一个外环和若干内环界定其范围。具有方向性，域，由一个外环和若干内环界定其范围。具有方向性，由其外法线矢量方向定义。由其外法线矢量方向定义。o 4、环：有序、有向边组成的面的封闭边界。（外环中、环：有序、有向边组成的面的封闭边界。（外环中其边逆时针排序，内环顺时针排序）其边逆时针排序，内环顺时针排序）o 5、体：三维几何元素，由封闭表面围成的空间。、

5、体：三维几何元素，由封闭表面围成的空间。2021/8/147o 图形信息与非图形信息图形信息与非图形信息n 几何信息几何信息：形体在欧氏空间中的位置和大小。：形体在欧氏空间中的位置和大小。n 拓扑信息拓扑信息：形体各分量（点、边、面）的数目：形体各分量（点、边、面）的数目及其相互间的连接关系。及其相互间的连接关系。基本概念基本概念几何信息与拓扑信息几何信息与拓扑信息图图4.1 4.1 拓扑信息拓扑信息2021/8/149o 刚体运动刚体运动：不改变图形上任意两点间的距离，：不改变图形上任意两点间的距离，也不改变图形的几何性质的运动。也不改变图形的几何性质的运动。o 拓扑运动拓扑运动：允许形体作

6、弹性运动，即在拓扑关：允许形体作弹性运动，即在拓扑关系中，对图形可随意地伸张扭曲。但图上各个系中，对图形可随意地伸张扭曲。但图上各个点仍为不同的点，决不允许把不同的点合并成点仍为不同的点，决不允许把不同的点合并成一个点。一个点。基本概念基本概念几何信息与拓扑信息几何信息与拓扑信息2021/8/1410o 建模坐标系（建模坐标系（Modeling Coordinate System）（局部坐）（局部坐标系）标系）o 用户坐标系（全局坐标系、世界坐标系）用户坐标系（全局坐标系、世界坐标系）o 观察坐标系（观察坐标系（Viewing Coordinate System）（指定裁）（指定裁剪空间、定义

7、投影平面，将用户坐标转换成规格化的设剪空间、定义投影平面，将用户坐标转换成规格化的设备坐标）备坐标）o 规格化设备坐标系（规格化设备坐标系（Normalized Device coordinate System）（定义视图区）（定义视图区）o 设备坐标系（设备坐标系（Device Coordinate System）（图形输入）（图形输入/输出的设备坐标系，如屏幕等）输出的设备坐标系，如屏幕等）基本概念基本概念坐标系坐标系2021/8/1411基本概念基本概念实体实体图图4.2 4.2 带有悬挂边的立方体带有悬挂边的立方体2021/8/1412o 客观存在的三维形体的客观存在的三维形体的5条性

8、质：条性质：n 刚性：一个物体必须具有一定的形状刚性：一个物体必须具有一定的形状n 维数的一致性：三维空间种，一个物体的各部分均应维数的一致性：三维空间种，一个物体的各部分均应是三维的，不能有悬挂的或孤立边界是三维的，不能有悬挂的或孤立边界n 占据有限的空间（体积有限）占据有限的空间（体积有限）n 边界的确定性（根据物体的边界可以确定物体内部与边界的确定性（根据物体的边界可以确定物体内部与外部）外部）n 封闭性（经过一系列刚体运动及任意序列的集合运算封闭性（经过一系列刚体运动及任意序列的集合运算后，依然是有效的物体）后，依然是有效的物体）三维空间中的物体是一个内部连通的三维点集。三维空间中的物

9、体是一个内部连通的三维点集。2021/8/1413o 三维物体表面必须具有以下三维物体表面必须具有以下5条性质：条性质：n 连通性：位于物体表面上的任意两个点都可用实体表连通性：位于物体表面上的任意两个点都可用实体表面上的一条路径连接起来。面上的一条路径连接起来。n 有界性：物体表面可将空间分为互不连通的两部分，有界性：物体表面可将空间分为互不连通的两部分，其中一部分是有界的其中一部分是有界的n 非自相交性：物体的表面不能自相交非自相交性：物体的表面不能自相交n 可定向性：物体表面的两侧可明确定义出属于物体的可定向性：物体表面的两侧可明确定义出属于物体的内侧或外侧内侧或外侧n 闭合性：物体表面

10、的闭合性是由表面上多边形网格各闭合性：物体表面的闭合性是由表面上多边形网格各元素的拓扑关系决定的，即每一条边有且只有两个顶元素的拓扑关系决定的，即每一条边有且只有两个顶点；每一条边连接来年各个或两个以上的面。点；每一条边连接来年各个或两个以上的面。2021/8/1414o 点的领域点的领域：如果：如果P是点集是点集S的一个元素，那么点的一个元素，那么点P的以的以R（R0）为半径的领域指的是围绕点为半径的领域指的是围绕点P的半径为的半径为R的小球（的小球（二维情况下为小圆）。二维情况下为小圆）。o 开集的闭包开集的闭包：是指该开集与其所有边界点的集合并集，本：是指该开集与其所有边界点的集合并集，

11、本身是一个闭集。（三维物体的点的集合可以分为内部点和身是一个闭集。（三维物体的点的集合可以分为内部点和边界点来那个部分）边界点来那个部分）o 正则集正则集：由内部点构成的点集的闭包就是正则集，三维空：由内部点构成的点集的闭包就是正则集，三维空间的正则集就是正则形体。也就是三维有效物体间的正则集就是正则形体。也就是三维有效物体 基本概念基本概念实体（点集拓扑学的角度）实体（点集拓扑学的角度）2021/8/1415基本概念基本概念实体实体o 组成三维物体的点的集合可以分为两类：组成三维物体的点的集合可以分为两类： n 内部点为点集中的这样一些点，它们具有完内部点为点集中的这样一些点，它们具有完全包

12、含于该点集的充分小的领域。全包含于该点集的充分小的领域。n 边界点：不具备此性质的点集中的点。边界点：不具备此性质的点集中的点。 2021/8/1416基本概念基本概念实体实体o 定义点集的正则运算定义点集的正则运算r运算为：运算为：AicAro 正则运算即为先对物体取内点再取闭包的运算。正则运算即为先对物体取内点再取闭包的运算。rA称为称为A的正则集。的正则集。2021/8/1417(a)带有孤立点和边的二维点集A(b)内点集合iA(c)正则点集ciA基本概念基本概念实体实体图图4.3 4.3 实体的例子实体的例子2021/8/1418图图4.4 4.4 正则形体正则形体基本概念基本概念实体

13、实体2021/8/1419o 二维流形二维流形指的是对于实体表面上的任意一点，指的是对于实体表面上的任意一点，都可以找到一个围绕着它的任意小的领域，该都可以找到一个围绕着它的任意小的领域，该领域与平面上的一个圆盘是拓扑等价的。领域与平面上的一个圆盘是拓扑等价的。 基本概念基本概念实体实体图图4.5 4.5 正则形体正则形体2021/8/1420o 实体：实体：对于一个占据有限空间的正则形体，如对于一个占据有限空间的正则形体，如果其表面是二维流形，则该正则形体为实体果其表面是二维流形，则该正则形体为实体。基本概念基本概念实体实体2021/8/1421p 有效实体的封闭性。有效实体的封闭性。p 把

14、能够产生正则形体的集合运算称为正则集合运把能够产生正则形体的集合运算称为正则集合运算。算。基本概念基本概念正则集合运算正则集合运算2021/8/1422图图4.6 集合运算与正则集合运算集合运算与正则集合运算基本概念基本概念正则集合运算正则集合运算2021/8/1423图图4.7 基于点的领域概念生成正则形体基于点的领域概念生成正则形体基本概念基本概念正则集合运算正则集合运算B)(b- sharedA bA),in B(b- B,out A bB)-(AbBb sharedA bA,in Bb B,in A bB)(AbBb sharedA bA,out Bb B,out A bB)(Ab*图

15、图4.8 正则集合运算正则集合运算A*B，A*B，A*B的结果（实线表示结果形体的边界）的结果（实线表示结果形体的边界）2021/8/1425基本概念基本概念平面多面体与欧拉公式平面多面体与欧拉公式o 欧拉公式证明简单多面体的顶点数欧拉公式证明简单多面体的顶点数V、边数、边数E和面数和面数F满满足如下关系：足如下关系：V-E+F=2。(简单多面体指那些经过连续的简单多面体指那些经过连续的几何形变可以变换成一个球的多面体，即与球拓扑等价几何形变可以变换成一个球的多面体，即与球拓扑等价的那些多面体）的那些多面体）o 非简单多面体需对欧拉公式加以扩展。令非简单多面体需对欧拉公式加以扩展。令H表示多面

16、体表表示多面体表面上孔的个数，面上孔的个数，G表示贯穿多面体的孔的个数，表示贯穿多面体的孔的个数，C表示独表示独立的、不相连接的多面体数，则扩展后的欧拉公式为：立的、不相连接的多面体数，则扩展后的欧拉公式为：V-E+F-H=2（C-G）。）。2021/8/1426基本概念基本概念平面多面体与欧拉公式平面多面体与欧拉公式图图4.9 平面多面体与欧拉公式平面多面体与欧拉公式2021/8/1427o 线框模型与实体模型（线框模型由定义一个物体线框模型与实体模型（线框模型由定义一个物体边界的直线和曲线组成）边界的直线和曲线组成）o 可以将实体模型的表示大致分为三类：可以将实体模型的表示大致分为三类：n

17、 边界表示（用一组曲面（或平面）来描述物体，边界表示（用一组曲面（或平面）来描述物体，这些曲面将物体分为内部和外部这些曲面将物体分为内部和外部）n 构造实体几何表示构造实体几何表示n 空间分割（将包含物体的空间划分成一组非常空间分割（将包含物体的空间划分成一组非常小的非重叠的连续实体）表示小的非重叠的连续实体）表示4.2 4.2 三维形体的表示三维形体的表示2021/8/1428o 多边形表面模型（使用一组包围物体内部的平面多边形表面模型（使用一组包围物体内部的平面多边形来描述实体）多边形来描述实体）o 扫描表示扫描表示o 构造实体几何法构造实体几何法o 空间位置枚举表示空间位置枚举表示o 八

18、叉树八叉树o BSP树树o OpenGL中的实体模型函数中的实体模型函数三维形体的表示三维形体的表示2021/8/1429o 边界表示边界表示(B-reps)的最普遍方式是多边形表面模型，的最普遍方式是多边形表面模型，它使用一组包围物体内部的平面多边形，也即平面它使用一组包围物体内部的平面多边形，也即平面多面体，来描述实体。需要设计有效的数据结构来多面体，来描述实体。需要设计有效的数据结构来处理面、边、点处理面、边、点多边形表面模型多边形表面模型图图4.10 4.10 四面体及其点、边、面的关系四面体及其点、边、面的关系2021/8/1430多边形表面模型多边形表面模型数据结构数据结构o 几何

19、信息（几何表）几何信息（几何表）n 建立建立3张表：顶点表、边表和多边形表来存张表：顶点表、边表和多边形表来存储几何数据。储几何数据。n 实体模型中，用多边形顶点坐标值以及多边实体模型中，用多边形顶点坐标值以及多边形所在平面方程方式保存实体单个表面部分形所在平面方程方式保存实体单个表面部分的空间方向信息的空间方向信息2021/8/1431多边形表面模型多边形表面模型数据结构数据结构o 拓扑信息：拓扑信息：翼边结构表示（翼边结构表示（Winged Edges Structure）图图4.11 4.11 翼边结构表示翼边结构表示2021/8/1432多边形表面模型多边形表面模型数据结构数据结构o

20、属性信息属性信息 用属性表来存储多边形面的属性，指明物体透明用属性表来存储多边形面的属性，指明物体透明度及表面反射度的参数和纹理特征等等。度及表面反射度的参数和纹理特征等等。实体测试条件：实体测试条件：1）每个顶点至少是两条边的端点）每个顶点至少是两条边的端点2）每条边至少是一个多边形的部分）每条边至少是一个多边形的部分3）每个多边形式封闭的）每个多边形式封闭的4）每个多边形至少有一条公共边）每个多边形至少有一条公共边5）如果多边形表包含指向多边形边的指针，则每一个）如果多边形表包含指向多边形边的指针，则每一个被指针指向的边有一个逆指针指回到多边形被指针指向的边有一个逆指针指回到多边形2021

21、/8/1433o 多边形网格：三维形体的边界通常用多边形网多边形网格：三维形体的边界通常用多边形网格（格（polygon mesh）的拼接来模拟。（三角的拼接来模拟。（三角形和四边形）形和四边形）o 例子例子多边形表面模型多边形表面模型图图4.12 4.12 三角形带与四边形网格三角形带与四边形网格2021/8/1434o 扫描表示法扫描表示法（sweep representation）可以利用可以利用简单的运动规则生成有效实体。简单的运动规则生成有效实体。 o 包含两个要素包含两个要素n 一是作扫描运动的基本图形（截面）；一是作扫描运动的基本图形（截面）；n 二是扫描运动的方式（平移、旋转、

22、对称变二是扫描运动的方式（平移、旋转、对称变换）。换）。 扫描表示（扫描表示（sweep representationsweep representation）2021/8/1435o 构造实体几何法构造实体几何法（CSG，Constructive Solid Geometry）由两个实体间的并、交或差操作由两个实体间的并、交或差操作生成新的实体。生成新的实体。BAAABB(a)A,B形体的并(b)A,B形体的差(c)A,B形体的交构造实体几何法构造实体几何法图图4.13 4.13 构造实体几何法构造实体几何法2021/8/1436o 在构造实体几何法中，集合运算的实现过程可在构造实体几何法中

23、，集合运算的实现过程可以用一棵二叉树（称为以用一棵二叉树（称为CSG树）来描述。树）来描述。n 树的叶子是基本体素或是几何变换参数；树的叶子是基本体素或是几何变换参数；n 树的非终端结点是施加于其子结点的正则集树的非终端结点是施加于其子结点的正则集合算子（正则并、正则交和正则差）或几何合算子（正则并、正则交和正则差）或几何变换的定义。变换的定义。构造实体几何法构造实体几何法2021/8/1437图图4.14 4.14 由由CSG树产生二维形体的实例树产生二维形体的实例2021/8/1438o 优点：如果体素设置比较齐全，通过集合运算优点：如果体素设置比较齐全，通过集合运算就可以构造出多种不同的

24、符合需要的实体。就可以构造出多种不同的符合需要的实体。o 缺点一：集合运算的中间结果难以用简单的代缺点一：集合运算的中间结果难以用简单的代数方程表示，求交困难。数方程表示，求交困难。o 缺点二：缺点二：CSG树不能显式地表示形体的边界，树不能显式地表示形体的边界，因而无法直接显示因而无法直接显示CSG树表示的形体。树表示的形体。构造实体几何法构造实体几何法2021/8/1439o 解决：光线投射算法解决：光线投射算法构造实体几何法构造实体几何法图图4.15 4.15 光线投射算法光线投射算法(实体实体AB取取ad，实体，实体AB则取则取cb,实体实体A-B则取则取ab)2021/8/1440o

25、 空间位置枚举表示法空间位置枚举表示法将包含实体的空间分割将包含实体的空间分割为大小相同、形状规则（正方形或立方体）为大小相同、形状规则（正方形或立方体）的体素，然后，以体素的集合来表示图形对的体素，然后，以体素的集合来表示图形对象。象。n 二维情况，常用二维数组存放。二维情况，常用二维数组存放。n 三维情况下，常用三维数组三维情况下，常用三维数组pijk来存来存放。放。空间位置枚举表示空间位置枚举表示2021/8/1441o 八叉树（八叉树（octreesoctrees）又称为分层树结构，它对又称为分层树结构，它对空间进行自适应划分，采用具有层次结构的八空间进行自适应划分，采用具有层次结构的

26、八叉树来表示实体。叉树来表示实体。八叉树八叉树2021/8/1442八叉树八叉树四叉树四叉树图图4.16 4.16 二维图的四叉树表示二维图的四叉树表示2021/8/1443八叉树八叉树图图4.17 4.17 三维空间分成八个卦限及其节点表示三维空间分成八个卦限及其节点表示2021/8/1444o 二 叉 空 间 分 割 （二 叉 空 间 分 割 （ B i n a r y S p a c e Partitioning，BSP）树）树方法是一种类似于方法是一种类似于八叉树的空间分割方法，它每次将一实体用八叉树的空间分割方法，它每次将一实体用任一位置和任一方向的平面分为二部分（不任一位置和任一方

27、向的平面分为二部分（不同于八叉树方法的每次将实体用平行于笛卡同于八叉树方法的每次将实体用平行于笛卡尔坐标平面的三个两两垂直的平面分割）。尔坐标平面的三个两两垂直的平面分割）。BSP树树2021/8/1445o GLUT库中的多面体函数库中的多面体函数OpenGL中的实体模型函数中的实体模型函数函数说明glutSolidTetrahedron( )glutWireTetrahedron( )绘制中心位于世界坐标系原点的实心四面体和线框四面体，四面体的半径为 。glutSolidCube(size)glutWireCube(size)绘制中心位于世界坐标系原点的实心立方体和线框立方体，立方体的半径

28、为size，size是一个双精度浮点值。glutSolidOctahedron ( )glutWireOctahedron ( )绘制中心位于世界坐标系原点的实心八面体和线框八面体，八面体的半径为1.0。glutSolidDodecahedron( )glutWireDodecahedron( )绘制中心位于世界坐标系原点的实心12面体和线框12面体，12面体的半径为 。glutSolidIcosahedron( )glutWireIcosahedron( )绘制中心位于世界坐标系原点的实心20面体和线框20面体，20面体的半径为1.0。3表表4.1 4.1 GLUT生成规则多面体的函数生成规

29、则多面体的函数32021/8/1446o GLUT库中的二、三次曲面库中的二、三次曲面n 绘制实体或线框球面绘制实体或线框球面 void glutSolidSphere/glutWireSphere (GLdouble radius, GLint slices, GLint stacks);n 绘制实体或线框圆锥面绘制实体或线框圆锥面 void glutSolidCone/glutWireCone (GLdouble radius, GLdouble height, GLint slices, GLint stacks);OpenGL中的实体模型函数中的实体模型函数2021/8/1447n 绘

30、制实体或线框圆环绘制实体或线框圆环 void glutSolidTorus/ glutWireTorus(GLdouble innerRadius, GLdouble outerRadius, GLint slices,GLint stacks);n 绘制实体或线框茶壶绘制实体或线框茶壶 void glutSolidTeapot/glutWireTeapot (GLdouble size);OpenGL中的实体模型函数中的实体模型函数2021/8/1448o GLU二次曲面函数二次曲面函数n 定义一个二次曲面定义一个二次曲面 GLUquadricObj *sphere;n 激活二次曲面绘制器激

31、活二次曲面绘制器 sphere = gluNewQuadric( );n 指定二次曲面的绘制方式指定二次曲面的绘制方式 gluQuadricDrawStyle(sphere, GLU_LINE); OpenGL中的实体模型函数中的实体模型函数2021/8/1449n 绘制二次曲面绘制二次曲面 gluSphere(sphere, radius, slices, stacks); gluCylinder(sphere,baseRadius,topRadius, height, slices, stacks)； gluDisk(sphere,innerRadius,outerRadius, slic

32、es, stacks)； OpenGL中的实体模型函数中的实体模型函数2021/8/1450非规则对象的表示非规则对象的表示o 分形几何分形几何o 形状语法形状语法o 粒子系统粒子系统o 基于物理的建模基于物理的建模o 数据场的可视化数据场的可视化2021/8/1451o 分形几何物体具有一个基本特征：分形几何物体具有一个基本特征：无限的自相无限的自相似性似性。o 无限的自相似性是指物体的整体和局部之间细无限的自相似性是指物体的整体和局部之间细节的无限重现。节的无限重现。分形几何分形几何( (fractal geometry)fractal geometry)2021/8/1452o 分形维数

33、，又称分数维数分形维数，又称分数维数4 = 228 = 23N = KD D=lgN/lgk K为边长缩小倍数；为边长缩小倍数； N为边长缩小后产为边长缩小后产生的新形体个数。生的新形体个数。分形几何分形几何( (fractal geometry)fractal geometry)图图4.18 4.18 分形维数分形维数2021/8/1453o 生成过程：初始生成元（生成过程：初始生成元（initiatorinitiator）、）、生成生成元（元（generatorgenerator）。o 实例实例图图4.19 4.19 生成过程生成过程分形几何分形几何( (fractal geometry)

34、fractal geometry)2021/8/1454海岸线长度问题海岸线长度问题o 二十世纪七十年代，法国数学家曼德尔勃罗特二十世纪七十年代，法国数学家曼德尔勃罗特在他的著作中讨论英国海岸线的长度。他发现在他的著作中讨论英国海岸线的长度。他发现，这个问题取决于测量所使用的尺度。采用公，这个问题取决于测量所使用的尺度。采用公里做单位，一些几米和几十米的曲折会被忽略里做单位，一些几米和几十米的曲折会被忽略，如果采用米做单位，测得的长度会曾加，但，如果采用米做单位，测得的长度会曾加，但厘米以下的量仍然无法反映，测量单位的缩小厘米以下的量仍然无法反映，测量单位的缩小使测得的长度曾加，由于在自然尺度

35、之间有许使测得的长度曾加，由于在自然尺度之间有许多个数量级，这种曾加不会停止，海岸线的长多个数量级，这种曾加不会停止，海岸线的长度会趋于无限长。也就是说，长度不是海岸线度会趋于无限长。也就是说，长度不是海岸线的定量特征。的定量特征。2021/8/1455数学的不规则图形数学的不规则图形o实际上，在曼德尔勃朗特的问题提出实际上，在曼德尔勃朗特的问题提出之前，数学家就曾经构造过多种不规之前，数学家就曾经构造过多种不规则的几何图形，他们具有和海岸线相则的几何图形，他们具有和海岸线相似的性质。似的性质。2021/8/1456Cantor集集o Cantor在在1883年构造了如下一类集合：取一年构造了

36、如下一类集合：取一段欧式长度为段欧式长度为l l的直线段，将该线段三等分，去的直线段，将该线段三等分，去掉中间的一段，剩下两段。再将剩下的两段分掉中间的一段，剩下两段。再将剩下的两段分别三等分，各去掉中间的一段，剩下四段。将别三等分，各去掉中间的一段，剩下四段。将这个操作进行下去，直至无穷，可得到一个离这个操作进行下去，直至无穷，可得到一个离散的点集，点数趋于无穷多，而长度趋于零。散的点集，点数趋于无穷多，而长度趋于零。经无限次操作所得到的离散点集称为经无限次操作所得到的离散点集称为CantorCantor集集。2021/8/1457Koch雪花线雪花线o 瑞典数学家科赫（瑞典数学家科赫（H.

37、von Koch)在在1904年年提出了一种曲线，它的生成方法是把一条直线提出了一种曲线，它的生成方法是把一条直线段分成三段，将中间的一段用夹角为段分成三段，将中间的一段用夹角为60度的两度的两条等长折线来代替，形成一个生成元，然后再条等长折线来代替，形成一个生成元，然后再把每个直线段用生成元进行代换，经无穷次迭把每个直线段用生成元进行代换，经无穷次迭代后就呈现出一条有无穷多弯曲的代后就呈现出一条有无穷多弯曲的Koch曲线曲线。2021/8/1458Koch曲线曲线2021/8/1459Koch曲线的生成过程曲线的生成过程第第0步、第步、第1步步2021/8/1460Koch曲线的生成过程曲线

38、的生成过程第第2步、第步、第3步步2021/8/1461Koch曲线与雪花曲线曲线与雪花曲线连接在一起的三段连接在一起的三段Koch曲线构成一个雪花曲曲线构成一个雪花曲线线2021/8/1462随机随机Koch曲线曲线对海岸线的模拟对海岸线的模拟2021/8/1463Koch曲线的一些基本性质曲线的一些基本性质o Koch曲线具有与曲线具有与Cantor集，集，Sierpinski垫片类似的性质垫片类似的性质.o 长度等于无穷长度等于无穷.2021/8/1464Sierpinski集集 o 首先，将一个等边三角形四等分，得到四个小首先，将一个等边三角形四等分，得到四个小等边三角形，去掉中间的一

39、个，保留它的边。等边三角形，去掉中间的一个，保留它的边。将剩下的三个小三角形再分别进行四等分，并将剩下的三个小三角形再分别进行四等分，并分别去掉中间的一个，保留它的边。重复操作分别去掉中间的一个，保留它的边。重复操作直至无穷，得到一个面积为零，线的欧式长度直至无穷，得到一个面积为零，线的欧式长度趋于无穷大的图形。这个图形被人们称为谢尔趋于无穷大的图形。这个图形被人们称为谢尔宾斯基缕垫。宾斯基缕垫。2021/8/1465Sierpinsk垫片的生成过程垫片的生成过程第第0步、第步、第1步步2021/8/1466Sierpinsk垫片的生成过程垫片的生成过程第第2步、第步、第3步步2021/8/1

40、467Sierpinsk垫片垫片2021/8/1468Sierpinski地毯地毯o 其次，将一个正方形九等分，去掉中间的一个其次，将一个正方形九等分，去掉中间的一个，保留四条边，剩下八个小正方形。将这九个，保留四条边，剩下八个小正方形。将这九个小正方形再分别进行九等分，各自去掉中间的小正方形再分别进行九等分，各自去掉中间的一个保留它们的边。重复操作直至无穷。一个保留它们的边。重复操作直至无穷。2021/8/1469Sierpinski地毯地毯2021/8/1470o 第三，对一个正六面体，将它的每条边进行三第三，对一个正六面体，将它的每条边进行三等分，即对正六面体进行等分，即对正六面体进行2

41、7等分，去掉体心和等分，去掉体心和面心处的面心处的7个小正六面体，剩下个小正六面体，剩下20个小正六面个小正六面体，并保留它们的表面，重复操作直无穷，得体，并保留它们的表面，重复操作直无穷，得到的图形。体积趋于零，而其表面的欧式面积到的图形。体积趋于零，而其表面的欧式面积趋于无穷大。趋于无穷大。Sierpinski海绵海绵2021/8/14712021/8/1472Sierpinski集的共同特点集的共同特点o 它们都是经典几何无法描述的图形，是一种它们都是经典几何无法描述的图形，是一种“只有皮没有肉只有皮没有肉”的几何集合。的几何集合。 o 它们都具有无穷多个自相似的内部结构，任它们都具有无

42、穷多个自相似的内部结构，任何一个分割后的图形放大后都是原来图形的何一个分割后的图形放大后都是原来图形的翻版。翻版。2021/8/1473问题在哪里？问题在哪里？o 以上是一些经典几何意义下的以上是一些经典几何意义下的“病态病态”图形，图形，以以Koch曲线为例，以一维来度量它，它的长曲线为例，以一维来度量它，它的长度趋于无穷，而以二维来度量它，它的面积为度趋于无穷，而以二维来度量它，它的面积为零，那么，它究竟是几维图形零，那么，它究竟是几维图形?1维？维？ 2维？维？1？维吗？维吗？o 经典的维度定义有问题吗？经典的维度定义有问题吗？2021/8/1474经典几何的维度定义经典几何的维度定义o

43、 在经典几何下，点被定义成在经典几何下，点被定义成0维的，点没有长维的，点没有长度；直线被定义成度；直线被定义成1维，只有长度，没有面积维，只有长度，没有面积，平面图形被定义成，平面图形被定义成2维的，有面积，没有体维的，有面积，没有体积，立体图形是积，立体图形是3维的，有体积。维的，有体积。o 经典几何讨论的维度都是整数，它们的数值与经典几何讨论的维度都是整数，它们的数值与决定几何形状的变量个数及自由度是一致的，决定几何形状的变量个数及自由度是一致的，这是一个很自然的想法。这是一个很自然的想法。2021/8/1475换一个角度看维度换一个角度看维度o 根据相似性来看线段、正方形和立方体的维数

44、根据相似性来看线段、正方形和立方体的维数。首先把线段、正方形和立方体的边两等分，。首先把线段、正方形和立方体的边两等分，这样，线段成为长度一半的两条线段，正方形这样，线段成为长度一半的两条线段，正方形变成边长为原来边长变成边长为原来边长1/2的四个小正方形，而的四个小正方形，而立方体而成为八个小立方体，边长为原来边长立方体而成为八个小立方体，边长为原来边长的的1/2。原来的线段、正方形和立方体分别由。原来的线段、正方形和立方体分别由2，4，8个把全体分成个把全体分成1/2的相似形组成。而的相似形组成。而2，4，8可改写成可改写成2的的1，2，3次方，这里的次方，这里的1，2，3分别与其图形的经

45、验维数相一致。分别与其图形的经验维数相一致。2021/8/1476相似维度的定义相似维度的定义o 一般地，如果某图形是由把全体缩小为一般地，如果某图形是由把全体缩小为1/a的的aD个相似图形构成的，那么此指数个相似图形构成的，那么此指数D就具有维就具有维度的意义。此维数被称为相似维数。度的意义。此维数被称为相似维数。o 相似维数常用相似维数常用DS表示，按照定义，表示，按照定义，DS完全没完全没有是整数的必要。如某图形是由全体缩小有是整数的必要。如某图形是由全体缩小1/a的的b个相似形组成，则个相似形组成，则 DS=(b)/(a)2021/8/1477o 我们可以以此计算上述几种图形的相似维度

46、。我们可以以此计算上述几种图形的相似维度。o Koch曲线：曲线：(4)/ (3)=1.2618o Cantor集：集： (2)/ (3)=0.6309o Sierpinski集：集：n 缕垫：缕垫： (3)/ (2)=1.5850 n 地毯：地毯： (8)/ (3)=1.8927 n 海绵：海绵： (20)/ (3)=2.72682021/8/1478o 从以上图形的生成方式来看，大体上有两种方式从以上图形的生成方式来看，大体上有两种方式：第一种是从初始图形：第一种是从初始图形E0按一定原则往下按一定原则往下“挖挖”，得到的新图形的维数小于，得到的新图形的维数小于E0 的欧式维数的欧式维数,

47、常称常称为降维生成；第二种是在初始图形为降维生成；第二种是在初始图形E0的基础上增的基础上增加一些线或面，得到的图形加一些线或面，得到的图形E的维数大于的维数大于E0的欧的欧式维数，这种生成方式常称为升维生成。式维数，这种生成方式常称为升维生成。2021/8/1479o 相似维数的定义具有很大的局限性，因为只用相似维数的定义具有很大的局限性，因为只用对具有严格的自相似性的分形，才能使用这个对具有严格的自相似性的分形，才能使用这个维数，定义适用于包括随机图形在内的任意的维数，定义适用于包括随机图形在内的任意的维数是很必要的。维数是很必要的。o 波恩大学数学家豪斯道夫波恩大学数学家豪斯道夫1919

48、年从测量的角年从测量的角度引进了度引进了Hausdorff维数。维数。2021/8/1480分形的定义分形的定义o 定义定义1.如果一个集合在欧式空间中的如果一个集合在欧式空间中的Hausdorff维数维数DH恒大于其拓扑维数恒大于其拓扑维数DT，则称该集合为分形集，简称分形。则称该集合为分形集，简称分形。 由由Mandelbrot在在1982年提出，四年后年提出，四年后，他又提出了一个更是实用的定义：，他又提出了一个更是实用的定义：o 定义定义2组成部分以某种方式与整体相似的形组成部分以某种方式与整体相似的形体叫分形。体叫分形。2021/8/1481分形理论的应用分形理论的应用o 生物学：肺

49、（人肺的分形维数约为生物学：肺（人肺的分形维数约为2.17；血管；血管（血管直径分布的分形维数约为（血管直径分布的分形维数约为2.3），人脑），人脑（人脑表面的皱纹的分形维数约为（人脑表面的皱纹的分形维数约为2.73-2.79）；蛋白质。）；蛋白质。o 地球物理学：海岸线、河流的干流和支流分布地球物理学：海岸线、河流的干流和支流分布、地震研究。、地震研究。 o 物理学和化学：超导；固体表面；高分子。物理学和化学：超导；固体表面；高分子。2021/8/1482o天文学，材料科学，计算机图形学，天文学，材料科学，计算机图形学，经济学，语言学和情报学经济学，语言学和情报学2021/8/1483分形的

50、自然观与世界观分形的自然观与世界观o 递归性，宇宙的创生，生命的生成，思维的生递归性，宇宙的创生，生命的生成，思维的生成。成。o 维数与空间，马赫多维原子理论，物理空间的维数与空间，马赫多维原子理论，物理空间的变维性。变维性。o 变维的中国文化根源。变维的中国文化根源。 2021/8/1484分形山分形山2021/8/1485分形树叶分形树叶2021/8/1486分形树叶分形树叶(续续1)2021/8/1487形状语法形状语法o 形状语法（形状语法（shape grammars）：）：给定一组给定一组产生式规则，形状设计者可以在从给定初始物产生式规则，形状设计者可以在从给定初始物体到最终物体结

51、构的每一次变换中应用不同的体到最终物体结构的每一次变换中应用不同的规则。规则。o 产生式规则可以用具有图形运算能力的数学式产生式规则可以用具有图形运算能力的数学式或其他过程性方法结合实现。或其他过程性方法结合实现。2021/8/1488粒子系统粒子系统o 用于模拟自然景物或模拟其它非规则形状物体用于模拟自然景物或模拟其它非规则形状物体展示展示“流体流体”性质的一个方法是性质的一个方法是微粒系统微粒系统（particle systems）。o 这一方法尤其擅长描述随时间变化的物体。这一方法尤其擅长描述随时间变化的物体。o 微粒运动的模拟方式：随机过程模拟、运动路微粒运动的模拟方式：随机过程模拟、运动路径模拟、力学模拟。径模拟、力学模拟。2021/8/1489基于物理的建模基于物理的建模o 基于物理的建模方法：描段与层次建模述了基于物理的建模方法：描段与层次建模述了物体在内外力相互作用下的行为。物体在内外力相互作用下的行为