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

《计算机图形学图形的表示与数据结构.ppt》由会员分享，可在线阅读，更多相关《计算机图形学图形的表示与数据结构.ppt（98页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1o如如何何在在计算算机机中中建建立立恰恰当当的的模模型型表表示示不不同同图形形对象。象。o如如何何组织图形形对象象的的描描述述数数据据以以使使存存储这些些数数据据所所要要的的空空间最最省省，检索索、处理理这些些数数据据的的速速度度较快。快。第四章第四章 图形的表示与数据结构图形的表示与数据结构2o基本概念基本概念o三三维形体的表示形体的表示o非非规则对象的表示象的表示o层次建模次建模图形的表示与数据结构图形的表示与数据结构3o造型技造型技术o基本基本图形元素形元素o几何信息与拓扑信息几何信息与拓扑信息o坐坐标系系o实体的定体的定义o正正则集合运算集合运算o欧拉公式欧拉公式4.1 4.1 基本

2、概念基本概念4o把把研研究究如如何何在在计算算机机中中建建立立恰恰当当的的模模型型表表示示不不同同图形形对象的技象的技术称称为造型技造型技术。o有两有两类图形形对象：象：规则对象象：几几何何造造型型、几几何何模模型型(几几何何信信息息和拓扑信息和拓扑信息)。不不规则对象：象：过程式模程式模拟。基本概念基本概念造型技术造型技术5基本概念基本概念基本图形元素基本图形元素p基本基本图形元素形元素：图素或素或图元、体素。元、体素。p图素素是指可以用一定的几何参数和属性参数描是指可以用一定的几何参数和属性参数描述的最基本的述的最基本的图形形输出元素（包括点、出元素（包括点、线、面、面、环、体等）。、体等

3、）。p在二在二维图形系形系统中将基本中将基本图形元素称形元素称为图素或素或图元，在三元，在三维图形系形系统中称中称为体素。体素。o1、点：、点：为0维几何元素，是形体最基本的元素，自由曲几何元素，是形体最基本的元素，自由曲线、曲面或其他形体均可用有序的点集来表示。点集及、曲面或其他形体均可用有序的点集来表示。点集及其其连接关系的存接关系的存储。o2、线：一：一维几何元素，是两个几何元素，是两个邻面或多个面或多个邻面的交界面的交界o3、面：二、面：二维几何元素，是形体上一个有限、非零的区域，几何元素，是形体上一个有限、非零的区域，由一个外由一个外环和若干内和若干内环界定其范界定其范围。具有方向性

4、，由其。具有方向性，由其外法外法线矢量方向定矢量方向定义。o4、环：有序、有向：有序、有向边组成的面的封成的面的封闭边界。（外界。（外环中其中其边逆逆时针排序，内排序，内环顺时针排序）排序）o5、体：三、体：三维几何元素，由封几何元素，由封闭表面表面围成的空成的空间。7o图形信息与非形信息与非图形信息形信息n几何信息几何信息：形体在欧氏空：形体在欧氏空间中的位置和大小。中的位置和大小。n拓拓扑扑信信息息：形形体体各各分分量量（点点、边、面面）的的数数目目及其相互及其相互间的的连接关系。接关系。基本概念基本概念几何信息与拓扑信息几何信息与拓扑信息图图4.1 4.1 拓扑信息拓扑信息9o刚体体运运

5、动：不不改改变图形形上上任任意意两两点点间的的距距离离，也不改也不改变图形的几何性形的几何性质的运的运动。o拓拓扑扑运运动：允允许形形体体作作弹性性运运动，即即在在拓拓扑扑关关系系中中，对图形形可可随随意意地地伸伸张扭扭曲曲。但但图上上各各个个点点仍仍为不不同同的的点点，决决不不允允许把把不不同同的的点点合合并并成成一个点。一个点。基本概念基本概念几何信息与拓扑信息几何信息与拓扑信息10o建建模模坐坐标系系（ModelingCoordinateSystem）（局局部部坐坐标系）系）o用用户坐坐标系（全局坐系（全局坐标系、世界坐系、世界坐标系）系）o观察察坐坐标系系（ViewingCoordin

6、ateSystem）（指指定定裁裁剪剪空空间、定定义投投影影平平面面，将将用用户坐坐标转换成成规格格化化的的设备坐坐标）o规格格化化设备坐坐标系系（Normalized Device coordinateSystem）（定）（定义视图区）区）o设备坐坐标系系（DeviceCoordinateSystem）（图形形输入入/输出的出的设备坐坐标系，如屏幕等）系，如屏幕等）基本概念基本概念坐标系坐标系11基本概念基本概念实体实体图图4.2 4.2 带有悬挂边的立方体带有悬挂边的立方体o客客观存在的三存在的三维形体的形体的5条性条性质：n刚性：一个物体必性：一个物体必须具有一定的形状具有一定的形状n维

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

8、性：位于物体表面上的任意两个点都可用实体表体表面上的一条路径面上的一条路径连接起来。接起来。n有界性：物体表面可将空有界性：物体表面可将空间分分为互不互不连通的两部分，通的两部分，其中一部分是有界的其中一部分是有界的n非自相交性：物体的表面不能自相交非自相交性：物体的表面不能自相交n可定向性：物体表面的两可定向性：物体表面的两侧可明确定可明确定义出属于物体的出属于物体的内内侧或外或外侧n闭合性：物体表面的合性：物体表面的闭合性是由表面上多合性是由表面上多边形网格各形网格各元素的拓扑关系决定的，即每一条元素的拓扑关系决定的，即每一条边有且只有两个有且只有两个顶点；每一条点；每一条边连接来年各个或

9、两个以上的面。接来年各个或两个以上的面。14o点点的的领域域：如如果果P是是点点集集S的的一一个个元元素素，那那么么点点P的的以以R（R0）为半半径径的的领域域指指的的是是围绕点点P的的半半径径为R的的小小球球（二（二维情况下情况下为小小圆）。）。o开开集集的的闭包包：是是指指该开开集集与与其其所所有有边界界点点的的集集合合并并集集，本本身身是是一一个个闭集集。（三三维物物体体的的点点的的集集合合可可以以分分为内内部部点点和和边界点来那个部分）界点来那个部分）o正正则集集：由内部点构成的点集的：由内部点构成的点集的闭包就是正包就是正则集，三集，三维空空间的正的正则集就是正集就是正则形体。也就是

10、三形体。也就是三维有效物体有效物体 基本概念基本概念实体（点集拓扑学的角度）实体（点集拓扑学的角度）15基本概念基本概念实体实体o组成三维物体的点的集合可以分为两类：组成三维物体的点的集合可以分为两类：n内部点为点集中的这样一些点，它们具有完内部点为点集中的这样一些点，它们具有完全包含于该点集的充分小的领域。全包含于该点集的充分小的领域。n边界点：不具备此性质的点集中的点。边界点：不具备此性质的点集中的点。16基本概念基本概念实体实体o定义点集的正则运算定义点集的正则运算r运算为：运算为：o正正则则运运算算即即为为先先对对物物体体取取内内点点再再取取闭闭包包的的运运算算。rA称为称为A的正则集

11、。的正则集。17基本概念基本概念实体实体图图4.3 4.3 实体的例子实体的例子18图图4.4 4.4 正则形体正则形体基本概念基本概念实体实体19o二二维流流形形指指的的是是对于于实体体表表面面上上的的任任意意一一点点，都都可可以以找找到到一一个个围绕着着它它的的任任意意小小的的领域域，该领域与平面上的一个域与平面上的一个圆盘是拓扑等价的。是拓扑等价的。基本概念基本概念实体实体图图4.5 4.5 正则形体正则形体20o实体体：对于于一一个个占占据据有有限限空空间的的正正则形形体体，如如果其表面是二果其表面是二维流形，流形，则该正正则形体形体为实体体。基本概念基本概念实体实体21p有效有效实体

12、的封体的封闭性。性。p把把能能够产生生正正则形形体体的的集集合合运运算算称称为正正则集集合合运运算。算。基本概念基本概念正则集合运算正则集合运算22图图4.6 集合运算与正则集合运算集合运算与正则集合运算基本概念基本概念正则集合运算正则集合运算23图图4.7 基于点的领域概念生成正则形体基于点的领域概念生成正则形体基本概念基本概念正则集合运算正则集合运算图图4.8 正则集合运算正则集合运算A*B，A*B，A*B的结果（实线表示结果形体的边界）的结果（实线表示结果形体的边界）25基本概念基本概念平面多面体与欧拉公式平面多面体与欧拉公式o欧欧拉拉公公式式证明明简单多多面面体体的的顶点点数数V、边数

13、数E和和面面数数F满足足如如下下关关系系：V-E+F=2。(简单多多面面体体指指那那些些经过连续的的几几何何形形变可可以以变换成成一一个个球球的的多多面面体体，即即与与球球拓拓扑扑等等价价的的那那些多面体）些多面体）o非非简单多多面面体体需需对欧欧拉拉公公式式加加以以扩展展。令令H表表示示多多面面体体表表面面上上孔孔的的个个数数，G表表示示贯穿穿多多面面体体的的孔孔的的个个数数，C表表示示独独立立的的、不不相相连接接的的多多面面体体数数，则扩展展后后的的欧欧拉拉公公式式为：V-E+F-H=2（C-G）。）。26基本概念基本概念平面多面体与欧拉公式平面多面体与欧拉公式图图4.9 平面多面体与欧拉

14、公式平面多面体与欧拉公式27o线框框模模型型与与实体体模模型型（线框框模模型型由由定定义一一个个物物体体边界的直界的直线和曲和曲线组成）成）o可以将可以将实体模型的表示大致分体模型的表示大致分为三三类：n边界界表表示示（用用一一组曲曲面面（或或平平面面）来来描描述述物物体体，这些曲面将物体分些曲面将物体分为内部和外部内部和外部）n构造构造实体几何表示体几何表示n空空间分分割割（将将包包含含物物体体的的空空间划划分分成成一一组非非常常小的非重叠的小的非重叠的连续实体）表示体）表示4.2 4.2 三维形体的表示三维形体的表示28o多多边边形形表表面面模模型型（使使用用一一组组包包围围物物体体内内部

15、部的的平平面面多边形来描述实体）多边形来描述实体）o扫描表示扫描表示o构造实体几何法构造实体几何法o空间位置枚举表示空间位置枚举表示o八叉树八叉树oBSP树树oOpenGL中的实体模型函数中的实体模型函数三维形体的表示三维形体的表示29o边界界表表示示(B-reps)的的最最普普遍遍方方式式是是多多边形形表表面面模模型型，它它使使用用一一组包包围物物体体内内部部的的平平面面多多边形形，也也即即平平面面多多面面体体，来来描描述述实体体。需需要要设计有有效效的的数数据据结构构来来处理理面、面、边、点、点多边形表面模型多边形表面模型图图4.10 4.10 四面体及其点、边、面的关系四面体及其点、边、

16、面的关系30多边形表面模型多边形表面模型数据结构数据结构o几何信息（几何表）几何信息（几何表）n建建立立3张张表表：顶顶点点表表、边边表表和和多多边边形形表表来来存存储几何数据。储几何数据。n实实体体模模型型中中，用用多多边边形形顶顶点点坐坐标标值值以以及及多多边边形形所所在在平平面面方方程程方方式式保保存存实实体体单单个个表表面面部部分分的空间方向信息的空间方向信息31多边形表面模型多边形表面模型数据结构数据结构o拓拓扑扑信信息息：翼翼边结构构表表示示（WingedEdgesStructure）图图4.11 4.11 翼边结构表示翼边结构表示32多边形表面模型多边形表面模型数据结构数据结构o

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

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

19、onsweep representation）35o构构造造实体体几几何何法法（CSG，ConstructiveSolidGeometry）由由两两个个实体体间的的并并、交交或或差差操操作作生成新的生成新的实体。体。构造实体几何法构造实体几何法图图4.13 4.13 构造实体几何法构造实体几何法36o在在构构造造实体体几几何何法法中中，集集合合运运算算的的实现过程程可可以用一棵二叉以用一棵二叉树（称（称为CSG树）来描述。）来描述。n树的叶子是基本体素或是几何的叶子是基本体素或是几何变换参数；参数；n树的的非非终端端结点点是是施施加加于于其其子子结点点的的正正则集集合合算算子子（正正则并并、正

20、正则交交和和正正则差差）或或几几何何变换的定的定义。构造实体几何法构造实体几何法37图图4.14 4.14 由由CSG树产生二维形体的实例树产生二维形体的实例38o优点点：如如果果体体素素设置置比比较齐全全，通通过集集合合运运算算就可以构造出多种不同的符合需要的就可以构造出多种不同的符合需要的实体。体。o缺缺点点一一：集集合合运运算算的的中中间结果果难以以用用简单的的代代数方程表示，求交困数方程表示，求交困难。o缺缺点点二二：CSG树不不能能显式式地地表表示示形形体体的的边界界，因而无法直接因而无法直接显示示CSG树表示的形体。表示的形体。构造实体几何法构造实体几何法39o解决：光解决：光线投

21、射算法投射算法构造实体几何法构造实体几何法图图4.15 4.15 光线投射算法光线投射算法(实体实体A B取取ad，实体，实体AB则取则取cb,实体实体A-B则取则取ab)40o空空间位位置置枚枚举表表示示法法将将包包含含实体体的的空空间分分割割为大大小小相相同同、形形状状规则（正正方方形形或或立立方方体体）的的体素，然后，以体素的集合来表示体素，然后，以体素的集合来表示图形形对象。象。n二二维情况，常用二情况，常用二维数数组存放。存放。n三三维情况下，常用三情况下，常用三维数数组pijk来存放。来存放。空间位置枚举表示空间位置枚举表示41o八八叉叉树（octreesoctrees）又又称称为

22、分分层树结构构，它它对空空间进行行自自适适应划划分分，采采用用具具有有层次次结构构的的八八叉叉树来表示来表示实体。体。八叉树八叉树42八叉树八叉树四叉树四叉树图图4.16 4.16 二维图的四叉树表示二维图的四叉树表示43八叉树八叉树图图4.17 4.17 三维空间分成八个卦限及其节点表示三维空间分成八个卦限及其节点表示44o二二 叉叉 空空 间 分分 割割（Binary Space Partitioning，BSP）树方方法法是是一一种种类似似于于八八叉叉树的的空空间分分割割方方法法，它它每每次次将将一一实体体用用任任一一位位置置和和任任一一方方向向的的平平面面分分为二二部部分分（不不同同于

23、于八八叉叉树方方法法的的每每次次将将实体体用用平平行行于于笛笛卡卡尔坐坐标平面的三个两两垂直的平面分割）。平面的三个两两垂直的平面分割）。BSP树树45oGLUT库中的多面体函数中的多面体函数OpenGL中的实体模型函数中的实体模型函数函数说明glutSolidTetrahedron()glutWireTetrahedron()绘制中心位于世界坐标系原点的实心四面体和线框四面体，四面体的半径为 。glutSolidCube(size)glutWireCube(size)绘制中心位于世界坐标系原点的实心立方体和线框立方体，立方体的半径为size，size是一个双精度浮点值。glutSolidOc

24、tahedron()glutWireOctahedron()绘制中心位于世界坐标系原点的实心八面体和线框八面体，八面体的半径为1.0。glutSolidDodecahedron()glutWireDodecahedron()绘制中心位于世界坐标系原点的实心12面体和线框12面体，12面体的半径为 。glutSolidIcosahedron()glutWireIcosahedron()绘制中心位于世界坐标系原点的实心20面体和线框20面体，20面体的半径为1.0。表表4.1 4.1 GLUT生成规则多面体的函数生成规则多面体的函数46oGLUT库中的二、三次曲面中的二、三次曲面n绘制制实体或体或

25、线框球面框球面voidglutSolidSphere/glutWireSphere(GLdoubleradius,GLintslices,GLintstacks);n绘制制实体或体或线框框圆锥面面voidglutSolidCone/glutWireCone(GLdoubleradius,GLdoubleheight,GLintslices,GLintstacks);OpenGL中的实体模型函数中的实体模型函数47n绘制制实体或体或线框框圆环voidglutSolidTorus/glutWireTorus(GLdoubleinnerRadius,GLdouble outerRadius,GLin

26、tslices,GLintstacks);n绘制制实体或体或线框茶框茶壶voidglutSolidTeapot/glutWireTeapot(GLdoublesize);OpenGL中的实体模型函数中的实体模型函数48oGLU二次曲面函数二次曲面函数n定定义一个二次曲面一个二次曲面GLUquadricObj*sphere;n激活二次曲面激活二次曲面绘制器制器sphere=gluNewQuadric();n指定二次曲面的指定二次曲面的绘制方式制方式gluQuadricDrawStyle(sphere,GLU_LINE);OpenGL中的实体模型函数中的实体模型函数49n绘制二次曲面制二次曲面gl

27、uSphere(sphere,radius,slices,stacks);gluCylinder(sphere,baseRadius,topRadius,height,slices,stacks)；gluDisk(sphere,innerRadius,outerRadius,slices,stacks)；OpenGL中的实体模型函数中的实体模型函数50非规则对象的表示非规则对象的表示o分形几何分形几何o形状语法形状语法o粒子系统粒子系统o基于物理的建模基于物理的建模o数据场的可视化数据场的可视化51o分分形形几几何何物物体体具具有有一一个个基基本本特特征征：无无限限的的自自相相似性似性。o无无

28、限限的的自自相相似似性性是是指指物物体体的的整整体体和和局局部部之之间细节的无限重的无限重现。分形几何分形几何(fractal geometry)fractal geometry)52o分形分形维维数，又称分数数，又称分数维维数数4=228=23N=KD D=lgN/lgk K为边长缩小倍数；为边长缩小倍数；N为边长缩小后产为边长缩小后产生的新形体个数。生的新形体个数。分形几何分形几何(fractal geometry)fractal geometry)图图4.18 4.18 分形维数分形维数53o生成生成过程：初始生成元（程：初始生成元（initiatorinitiator）、）、生成生成元

29、（元（generatorgenerator）。o实例例图图4.19 4.19 生成过程生成过程分形几何分形几何(fractal geometry)fractal geometry)海岸线长度问题海岸线长度问题o二十世二十世纪纪七十年代，法国数学家曼德七十年代，法国数学家曼德尔尔勃勃罗罗特特在他的著作中在他的著作中讨论讨论英国海岸英国海岸线线的的长长度。他度。他发现发现，这这个个问题问题取决于取决于测测量所使用的尺度。采用公里量所使用的尺度。采用公里做做单单位，一些几米和几十米的曲折会被忽略，位，一些几米和几十米的曲折会被忽略，如果采用米做如果采用米做单单位，位，测测得的得的长长度会曾加，但厘度

30、会曾加，但厘米以下的量仍然无法反映，米以下的量仍然无法反映，测测量量单单位的位的缩缩小使小使测测得的得的长长度曾加，由于在自然尺度之度曾加，由于在自然尺度之间间有有许许多多个数量个数量级级，这这种曾加不会停止，海岸种曾加不会停止，海岸线线的的长长度度会会趋趋于无限于无限长长。也就是。也就是说说，长长度不是海岸度不是海岸线线的的定量特征。定量特征。数学的不规则图形数学的不规则图形o实际上，在曼德上，在曼德尔勃朗特的勃朗特的问题提出提出之前，数学家就曾之前，数学家就曾经构造构造过多种不多种不规则的几何的几何图形，他形，他们具有和海岸具有和海岸线相相似的性似的性质。Cantor集集oCantor在在

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

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

33、段连接在一起的三段Koch曲线构成一个雪花曲曲线构成一个雪花曲线线随机随机Koch曲线曲线对海岸线的模拟对海岸线的模拟Koch曲线的一些基本性质曲线的一些基本性质o Koch曲曲线线具有与具有与Cantor集，集，Sierpinski垫垫片片类类似的性似的性质质.o长长度等于无度等于无穷穷.Sierpinski集集 o首先，将一个等首先，将一个等边边三角形四等分，得到四个小三角形四等分，得到四个小等等边边三角形，去掉中三角形，去掉中间间的一个，保留它的的一个，保留它的边边。将剩下的三个小三角形再分将剩下的三个小三角形再分别进别进行四等分，并行四等分，并分分别别去掉中去掉中间间的一个，保留它的的

34、一个，保留它的边边。重复操作。重复操作直至无直至无穷穷，得到一个面，得到一个面积为积为零，零，线线的欧式的欧式长长度度趋趋于无于无穷穷大的大的图图形。形。这这个个图图形被人形被人们们称称为谢为谢尔尔宾宾斯基斯基缕垫缕垫。Sierpinsk垫片的生成过程垫片的生成过程第第0步、第步、第1步步Sierpinsk垫片的生成过程垫片的生成过程第第2步、第步、第3步步Sierpinsk垫片垫片Sierpinski地毯地毯o其次，将一个正方形九等分，去掉中其次，将一个正方形九等分，去掉中间间的一个，的一个，保留四条保留四条边边，剩下八个小正方形。将，剩下八个小正方形。将这这九个小九个小正方形再分正方形再分

35、别进别进行九等分，各自去掉中行九等分，各自去掉中间间的一的一个保留它个保留它们们的的边边。重复操作直至无。重复操作直至无穷穷。Sierpinski地毯地毯o第三，第三，对对一个正六面体，将它的每条一个正六面体，将它的每条边进边进行三行三等分，即等分，即对对正六面体正六面体进进行行27等分，去掉体心和等分，去掉体心和面心面心处处的的7个小正六面体，剩下个小正六面体，剩下20个小正六面个小正六面体，并保留它体，并保留它们们的表面，重复操作直无的表面，重复操作直无穷穷，得，得到的到的图图形。体形。体积趋积趋于零，而其表面的欧式面于零，而其表面的欧式面积积趋趋于无于无穷穷大。大。Sierpinski海

36、绵海绵Sierpinski集的共同特点集的共同特点o它它们都是都是经典几何无法描述的典几何无法描述的图形，是一种形，是一种“只有皮没有肉只有皮没有肉”的几何集合。的几何集合。o它它们都具有无都具有无穷多个自相似的内部多个自相似的内部结构，任何构，任何一个分割后的一个分割后的图形放大后都是原来形放大后都是原来图形的翻版。形的翻版。问题在哪里？问题在哪里？o以上是一些以上是一些经典几何意典几何意义下的下的“病病态”图形，形，以以Koch曲曲线为例，以一例，以一维来度量它，它的来度量它，它的长度度趋于无于无穷，而以二，而以二维来度量它，它的面来度量它，它的面积为零，那么，它究竟是几零，那么，它究竟是

37、几维图形形?1维？2维？1？维吗？o经典的典的维度定度定义有有问题吗？经典几何的维度定义经典几何的维度定义o在在经经典几何下，点被定典几何下，点被定义义成成0维维的，点没有的，点没有长长度；度；直直线线被定被定义义成成1维维，只有，只有长长度，没有面度，没有面积积，平，平面面图图形被定形被定义义成成2维维的，有面的，有面积积，没有体，没有体积积，立体立体图图形是形是3维维的，有体的，有体积积。o经经典几何典几何讨论讨论的的维维度都是整数，它度都是整数，它们们的数的数值值与与决定几何形状的决定几何形状的变变量个数及自由度是一致的，量个数及自由度是一致的，这这是一个很自然的想法。是一个很自然的想法

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

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

40、.2618oCantor集：集：(2)/(3)=0.6309oSierpinski集集：n缕垫：(3)/(2)=1.5850 n 地毯：地毯：(8)/(3)=1.8927 n 海海绵：(20)/(3)=2.7268o从从以上以上图形的生成方式来看，大体上有两种方式：形的生成方式来看，大体上有两种方式：第一种是从初始第一种是从初始图形形E0按一定原按一定原则往下往下“挖挖”，得到的新得到的新图形的形的维数小于数小于E0 的欧式的欧式维数数,常称常称为降降维生成；第二种是在初始生成；第二种是在初始图形形E0的基的基础上增加上增加一些一些线或面，得到的或面，得到的图形形E的的维数大于数大于E0的欧式

41、的欧式维数，数，这种生成方式常称种生成方式常称为升升维生成。生成。o相似相似维维数的定数的定义义具有很大的局限性，因具有很大的局限性，因为为只用只用对对具有具有严严格的自相似性的分形，才能使用格的自相似性的分形，才能使用这这个个维维数，定数，定义义适用于包括随机适用于包括随机图图形在内的任意的形在内的任意的维维数是很必要的。数是很必要的。o波恩大学数学家豪斯道夫波恩大学数学家豪斯道夫1919年从年从测测量的角量的角度引度引进进了了Hausdorff维维数。数。分形的定义分形的定义o定定义1.如果一个集合在欧式空如果一个集合在欧式空间中的中的Hausdorff维数数DH恒大于其拓扑恒大于其拓扑维

42、数数DT，则称称该集合集合为分形集，分形集，简称分形。称分形。由由Mandelbrot在在1982年提出，四年后，年提出，四年后，他又提出了一个更是他又提出了一个更是实用的定用的定义：o定定义2组成部分以某种方式与整体相似的形体成部分以某种方式与整体相似的形体叫分形。叫分形。分形理论的应用分形理论的应用o生物学：肺（人肺的分形生物学：肺（人肺的分形维数数约为2.17；血管；血管（血管直径分布的分形（血管直径分布的分形维数数约为2.3），人），人脑（人（人脑表面的表面的皱纹的分形的分形维数数约为2.73-2.79）；蛋白）；蛋白质。o地球物理学：海岸地球物理学：海岸线、河流的干流和支流分布、河流

43、的干流和支流分布、地震研究。地震研究。o物理学和化学：超物理学和化学：超导；固体表面；高分子。；固体表面；高分子。o天文学，材料科学，天文学，材料科学，计算机算机图形学，形学，经济学，学，语言学和情言学和情报学学分形的自然观与世界观分形的自然观与世界观o递归递归性，宇宙的性，宇宙的创创生，生命的生成，思生，生命的生成，思维维的生的生成。成。o维维数与空数与空间间，马马赫多赫多维维原子理原子理论论，物理空，物理空间间的的变维变维性。性。o变维变维的中国文化根源。的中国文化根源。分形山分形山分形树叶分形树叶分形树叶分形树叶(续续1)87形状语法形状语法o形形状状语法法（shape grammars

44、）：给定定一一组产生生式式规则，形形状状设计者者可可以以在在从从给定定初初始始物物体体到到最最终物物体体结构构的的每每一一次次变换中中应用用不不同同的的规则。o产生生式式规则可可以以用用具具有有图形形运运算算能能力力的的数数学学式式或其他或其他过程性方法程性方法结合合实现。88粒子系统粒子系统o用用于于模模拟自自然然景景物物或或模模拟其其它它非非规则形形状状物物体体展展示示“流流体体”性性质的的一一个个方方法法是是微微粒粒系系统（particle systems）。o这一方法尤其擅一方法尤其擅长描述随描述随时间变化的物体。化的物体。o微微粒粒运运动的的模模拟方方式式：随随机机过程程模模拟、运运

45、动路路径模径模拟、力学模、力学模拟。89基于物理的建模基于物理的建模o基基于于物物理理的的建建模模方方法法：描描段段与与层次次建建模模述述了了物物体在内外力相互作用下的行体在内外力相互作用下的行为。o通通常常用用一一组网网格格结点点来来逼逼近近物物体体。网网格格结点点间取取为柔柔性性连接接，再再考考虑贯穿穿物物体体网网格格的的力力传递。90数据场的可视化数据场的可视化o科科学学计算算可可视化化（scientific visualization）指指的的是是运运用用计算算机机图形形学学和和图像像处理理技技术，将将科科学学计算算过程程中中及及计算算结果果的的数数据据转换为图形形及及图像像在在屏屏幕

46、幕上上显示示出出来来并并进行行交交互互处理理的的理理论、方法和技、方法和技术。914.4 层次模型层次模型o段与层次模型段与层次模型o层次模型的实现层次模型的实现oOpenGL中的层次模型中的层次模型92段与层次模型段与层次模型o具具有有逻逻辑辑意意义义的的有有限限个个图图素素（或或体体素素）及及其其附附加加属属性性的的集集合合称称为为段段，或或者者称称为为图图段段（二二维维空间中）、结构和对象。空间中）、结构和对象。o段是可以嵌套段是可以嵌套o段段与与基基本本图图形形元元素素的的区区别别在在于于，基基本本图图形形元元素素是用数据来描述的，而段是用规则来描述的。是用数据来描述的，而段是用规则来

47、描述的。93段与层次模型段与层次模型o段段一一般般具具有有三三个个特特性性：可可见见性性、醒醒目目性性和和可可选选择性（可由交互式输入设备来选择）。择性（可由交互式输入设备来选择）。o利用段的嵌套来构造复杂的对象或系统。利用段的嵌套来构造复杂的对象或系统。图图4.20 4.20 自行车及其层次描述自行车及其层次描述94p存储简单：一个段虽然在图中各处出现，但他存储简单：一个段虽然在图中各处出现，但他的几何和拓扑信息只要保存一次。的几何和拓扑信息只要保存一次。p编辑简单：删除、移动及缩放操作都可以以段编辑简单：删除、移动及缩放操作都可以以段为单位。为单位。段与层次模型段与层次模型95层次模型的实

48、现层次模型的实现o系系统统的的层层次次模模型型可可以以通通过过将将一一个个图图段段嵌嵌套套到到另另一一个个图图段段中中形形成成图图段段树树来来创创建建。不不同同的的段段和和基基本图形元素在各自的建模坐标系中定义。本图形元素在各自的建模坐标系中定义。o图图层层。通通过过把把功功能能相相同同的的部部分分归归类类，并并将将它它们们绘制在同一层上，有助于图形的理解和管理。绘制在同一层上，有助于图形的理解和管理。o一般图层不再嵌套。一般图层不再嵌套。96OpenGL中层次模型的实现中层次模型的实现o显示列表的创建显示列表的创建glNewList(listID,listMode);glutSolidCub

49、e(2.0);glEndList();o显示列表的执行显示列表的执行voidglListBase(GLuintoffsetValue);97OpenGL中层次模型的实现中层次模型的实现o多级显示列表多级显示列表OpenGL支支持持创建建多多级显示示列列表表，即即在在glNewList和和glEndLsit函函数数对之之间允允许调用用glCallList函数来函数来执行其他行其他显示列表。示列表。o显示列表的删除显示列表的删除voidglDeleteLists(GLuintlistID,GLsizeirange);第二次课后作业：第二次课后作业：o用用OpenGL 程序，分程序，分别别以直以直线线段和正三角形段和正三角形为为初始生成元，初始生成元，实现实现迭代次数在迭代次数在6次以内的次以内的Kock曲曲线线，要求用，要求用键盘键盘交互控制迭代次数交互控制迭代次数