《4图形的表示与数据结构》由会员分享，可在线阅读，更多相关《4图形的表示与数据结构（61页珍藏版）》请在金锄头文库上搜索。
1、1o如如何何在在计算算机机中中建建立立恰恰当当的的模模型型表表示示不不同同图形形对象。象。o如如何何组织图形形对象象的的描描述述数数据据以以使使存存储这些些数数据据所所要要的的空空间最最省省，检索索、处理理这些些数数据据的的速速度度较快。快。第四章第四章 图形的表示与数据结构图形的表示与数据结构2o基本概念基本概念o三三维形体的表示形体的表示o非非规则对象的表示象的表示o层次建模次建模图形的表示与数据结构图形的表示与数据结构3o造型技造型技术o基本基本图形元素形元素o几何信息与拓扑信息几何信息与拓扑信息o坐坐标系系o实体的定体的定义o正正则集合运算集合运算o欧拉公式欧拉公式4.1 4.1 基本
2、概念基本概念4o把把研研究究如如何何在在计算算机机中中建建立立恰恰当当的的模模型型表表示示不不同同图形形对象的技象的技术称称为造型技造型技术。o有两有两类图形形对象：象： 规则对象象：几何造型、几何模型。：几何造型、几何模型。 能用欧氏几何加以描述的对象 不不规则对象象：过程式模程式模拟。 不能用欧氏几何加以描述的对象基本概念基本概念造型技术造型技术5基本概念基本概念基本图形元素基本图形元素p基本基本图形元素形元素：图素或素或图元、体素。元、体素。p图素素是指可以用一定的几何参数和属性参数描是指可以用一定的几何参数和属性参数描述的最基本的述的最基本的图形形输出元素。出元素。p在二在二维图形系形
3、系统中将基本中将基本图形元素称形元素称为图素或素或图元，在三元，在三维图形系形系统中称中称为体素体素。6 图形形对象的描述离不开大量的象的描述离不开大量的图形信息和非形信息和非图形信息。形信息。o图形信息形信息n几何信息几何信息：形体在欧氏空：形体在欧氏空间中的位置和大小。中的位置和大小。n拓拓扑扑信信息息：形形体体各各分分量量（点点、边、面面）的的数数目目及其相互及其相互间的的连接关系。接关系。o非非图形信息形信息基本概念基本概念几何信息与拓扑信息几何信息与拓扑信息包括图形对象，构成对象的包括图形对象，构成对象的点、线、面的位置和几何尺寸，点、线、面的位置和几何尺寸，以及它们相互之间的关系等
4、以及它们相互之间的关系等图形的线性、颜色、亮度以图形的线性、颜色、亮度以及供模拟和分析用的质量、比重、及供模拟和分析用的质量、比重、体积等数据体积等数据图图4.1 4.1 拓扑信息拓扑信息8o刚体体运运动：不不改改变图形形上上任任意意两两点点间的的距距离离，也不改也不改变图形的几何性形的几何性质的运的运动。o拓拓扑扑运运动：允允许形形体体作作弹性性运运动，即即在在拓拓扑扑关关系系中中，对图形形可可随随意意地地伸伸张扭扭曲曲。但但图上上各各个个点点仍仍为不不同同的的点点，决决不不允允许把把不不同同的的点点合合并并成成一个点。一个点。基本概念基本概念几何信息与拓扑信息几何信息与拓扑信息9o建模坐建
5、模坐标系系（Modeling Coordinate System）o用用户坐坐标系系o观察坐察坐标系系（Viewing Coordinate System）o规格化格化设备坐坐标系系（Normalized Device coordinate System）o设备坐坐标系系（Device Coordinate System）基本概念基本概念坐标系坐标系10基本概念基本概念实体实体图图4.2 4.2 带有悬挂边的立方体带有悬挂边的立方体11o点点的的领域域：如如果果P是是点点集集S的的一一个个元元素素，那那么么点点P的的以以R（R0）为半半径径的的领域域指指的的是是围绕点点P的的半半径径为R的的小
6、球（二小球（二维情况下情况下为小小圆）。）。o开开集集的的闭包包：是是指指该开开集集与与其其所所有有边界界点点的的集集合合并并集集，本身是一个本身是一个闭集。集。o正正则集集：由内部点构成的点集的：由内部点构成的点集的闭包就是正包就是正则集，三集，三维空空间的正的正则集就是正集就是正则形体。形体。 基本概念基本概念实体实体12基本概念基本概念实体实体o组成三维物体的点的集合可以分为两类：组成三维物体的点的集合可以分为两类： n内点为点集中的这样一些点，它们具有完全内点为点集中的这样一些点，它们具有完全包含于该点集的充分小的领域。包含于该点集的充分小的领域。n边界点：不具备此性质的点集中的点。边
7、界点：不具备此性质的点集中的点。 13基本概念基本概念实体实体o定义点集的正则运算定义点集的正则运算r运算为：运算为：o正正则则运运算算即即为为先先对对物物体体取取内内点点再再取取闭闭包包的的运运算算。rA称为称为A的正则集。的正则集。14基本概念基本概念实体实体图图4.3 4.3 实体的例子实体的例子15图图4.4 4.4 正则形体正则形体基本概念基本概念实体实体16o二二维流流形形指指的的是是对于于实体体表表面面上上的的任任意意一一点点，都都可可以以找找到到一一个个围绕着着它它的的任任意意小小的的领域域，该领域与平面上的一个域与平面上的一个圆盘是拓扑等价的。是拓扑等价的。 基本概念基本概念
8、实体实体图图4.5 4.5 正则形体正则形体17o实体体：对于于一一个个占占据据有有限限空空间的的正正则形形体体，如如果其表面是二果其表面是二维流形，流形，则该正正则形体形体为实体体。基本概念基本概念实体实体18p有效有效实体的封体的封闭性。性。p把把能能够产生生正正则形形体体的的集集合合运运算算称称为正正则集集合合运运算。算。基本概念基本概念正则集合运算正则集合运算19图图4.6 集合运算与正则集合运算集合运算与正则集合运算基本概念基本概念正则集合运算正则集合运算20图图4.7 基于点的领域概念生成正则形体基于点的领域概念生成正则形体基本概念基本概念正则集合运算正则集合运算图图4.8 正则集
9、合运算正则集合运算A*B，A*B，A*B的结果（实线表示结果形体的边界）的结果（实线表示结果形体的边界）22基本概念基本概念平面多面体与欧拉公式平面多面体与欧拉公式o欧欧拉拉公公式式证明明简单多多面面体体的的顶点点数数V、边数数E和和面面数数F满足如下关系：足如下关系：V-E+F=2。o非非简单多多面面体体需需对欧欧拉拉公公式式加加以以扩展展。令令H表表示示多多面面体体表表面面上上孔孔的的个个数数，G表表示示贯穿穿多多面面体体的的孔孔的的个个数数，C表表示示独独立立的的、不不相相连接接的的多多面面体体数数，则扩展后的欧拉公式展后的欧拉公式为：V-E+F-H=2（C-G）。）。23基本概念基本概
10、念平面多面体与欧拉公式平面多面体与欧拉公式图图4.9 平面多面体与欧拉公式平面多面体与欧拉公式24o线框模型与框模型与实体模型（体模型（实体造型技体造型技术）o可以将可以将实体模型的表示大致分体模型的表示大致分为三三类：n边界界表表示示（Boundary representation, B-reps）n构造构造实体几何表示体几何表示n空空间分割（分割（Space-partitioning）表示表示4.2 4.2 三维形体的表示三维形体的表示25o多边形表面模型多边形表面模型o扫描表示扫描表示o构造实体几何法构造实体几何法o空间位置枚举表示空间位置枚举表示o八叉树八叉树oBSP树树oOpenGL
11、中的实体模型函数中的实体模型函数三维形体的表示三维形体的表示26o边界界表表示示(B-reps)的的最最普普遍遍方方式式是是多多边形形表表面面模模型型，它它使使用用一一组包包围物物体体内内部部的的平平面面多多边形，也即平面多面体，来描述形，也即平面多面体，来描述实体。体。多边形表面模型多边形表面模型图图4.10 4.10 四面体及其点、边、面的关系四面体及其点、边、面的关系27多边形表面模型多边形表面模型数据结构数据结构o几何信息几何信息n建建立立3张张表表：顶顶点点表表、边边表表和和多多边边形形表表来来存存储几何数据。储几何数据。n实实体体模模型型中中，用用多多边边形形顶顶点点坐坐标标值值以
12、以及及多多边边形形所所在在平平面面方方程程方方式式保保存存实实体体单单个个表表面面部部分分的空间方向信息的空间方向信息28多边形表面模型多边形表面模型数据结构数据结构o拓拓扑扑信信息息：翼翼边结构构表表示示（WingedEdgesStructure）图图4.11 4.11 翼边结构表示翼边结构表示29多边形表面模型多边形表面模型数据结构数据结构o属性信息属性信息 用用属属性性表表来来存存储储多多边边形形面面的的属属性性，指指明明物物体体透透明明度度及及表表面面反反射射度度的的参参数数和和纹纹理理特特征征等等。等等。30o多多边形形网网格格：三三维形形体体的的边界界通通常常用用多多边形形网网格（
13、格（polygonmesh）的拼接来模的拼接来模拟。o例子例子多边形表面模型多边形表面模型图图4.12 4.12 三角形带与四边形网格三角形带与四边形网格31o扫描描表表示示法法（sweep representation）可可以以利利用用简单的运的运动规则生成有效生成有效实体。体。o包含两个要素包含两个要素n一是作一是作扫描运描运动的基本的基本图形（截面）；形（截面）；n二是二是扫描运描运动的方式。的方式。扫描表示（扫描表示（sweep representationsweep representation）32o构构造造实体体几几何何法法（CSG，ConstructiveSolidGeomet
14、ry）由由两两个个实体体间的的并并、交交或或差差操操作作生成新的生成新的实体。体。构造实体几何法构造实体几何法图图4.13 4.13 构造实体几何法构造实体几何法33o在在构构造造实体体几几何何法法中中，集集合合运运算算的的实现过程程可可以用一棵二叉以用一棵二叉树（称（称为CSG树）来描述。）来描述。n树的叶子是基本体素或是几何的叶子是基本体素或是几何变换参数；参数；n树的的非非终端端结点点是是施施加加于于其其子子结点点的的正正则集集合合算算子子（正正则并并、正正则交交和和正正则差差）或或几几何何变换的定的定义。构造实体几何法构造实体几何法34构造实体几何法构造实体几何法图图4.14 4.14
15、 由由CSG树产生二维形体的实例树产生二维形体的实例35o优点点：如如果果体体素素设置置比比较齐全全，通通过集集合合运运算算就可以构造出多种不同的符合需要的就可以构造出多种不同的符合需要的实体。体。o缺缺点点一一：集集合合运运算算的的中中间结果果难以以用用简单的的代代数方程表示，求交困数方程表示，求交困难。o缺缺点点二二：CSG树不不能能显式式地地表表示示形形体体的的边界界，因而无法直接因而无法直接显示示CSG树表示的形体。表示的形体。构造实体几何法构造实体几何法36o解决：光解决：光线投射算法投射算法构造实体几何法构造实体几何法图图4.15 4.15 光线投射算法光线投射算法(实体实体A B
16、取取ad，实体，实体AB则取则取cb,实体实体A-B则取则取ab)37o空空间位位置置枚枚举表表示示法法将将包包含含实体体的的空空间分分割割为大大小小相相同同、形形状状规则（正正方方形形或或立立方方体体）的的体素，然后，以体素的集合来表示体素，然后，以体素的集合来表示图形形对象。象。n二二维情况，常用二情况，常用二维数数组存放。存放。n三三维情况下，常用三情况下，常用三维数数组pijk来存放。来存放。空间位置枚举表示空间位置枚举表示38o八八叉叉树（octreesoctrees）又又称称为分分层树结构构，它它对空空间进行行自自适适应划划分分，采采用用具具有有层次次结构构的的八八叉叉树来表示来表
17、示实体。体。八叉树八叉树39八叉树八叉树四叉树四叉树图图4.16 4.16 二维图的四叉树表示二维图的四叉树表示40八叉树八叉树图图4.17 4.17 三维空间分成八个卦限及其节点表示三维空间分成八个卦限及其节点表示41o二二 叉叉 空空 间 分分 割割 （ Binary Space Partitioning，BSP）树方方法法是是一一种种类似似于于八八叉叉树的的空空间分分割割方方法法，它它每每次次将将一一实体体用用任任一一位位置置和和任任一一方方向向的的平平面面分分为二二部部分分（不不同同于于八八叉叉树方方法法的的每每次次将将实体体用用平平行行于于笛笛卡卡尔坐坐标平面的三个两两垂直的平面分割
18、）。平面的三个两两垂直的平面分割）。BSP树树42oGLUT库中的多面体函数中的多面体函数OpenGL中的实体模型函数中的实体模型函数函数说明glutSolidTetrahedron( )glutWireTetrahedron( )绘制中心位于世界坐标系原点的实心四面体和线框四面体，四面体的半径为 。glutSolidCube(size)glutWireCube(size)绘制中心位于世界坐标系原点的实心立方体和线框立方体，立方体的半径为size，size是一个双精度浮点值。glutSolidOctahedron ( )glutWireOctahedron ( )绘制中心位于世界坐标系原点的实
19、心八面体和线框八面体，八面体的半径为1.0。glutSolidDodecahedron( )glutWireDodecahedron( )绘制中心位于世界坐标系原点的实心12面体和线框12面体，12面体的半径为 。glutSolidIcosahedron( )glutWireIcosahedron( )绘制中心位于世界坐标系原点的实心20面体和线框20面体，20面体的半径为1.0。表表4.1 4.1 GLUT生成规则多面体的函数生成规则多面体的函数43oGLUT库中的二、三次曲面中的二、三次曲面n绘制制实体或体或线框球面框球面voidglutSolidSphere/glutWireSphere
20、(GLdoubleradius,GLintslices,GLintstacks);n绘制制实体或体或线框框圆锥面面voidglutSolidCone/glutWireCone(GLdoubleradius,GLdoubleheight,GLintslices,GLintstacks);OpenGL中的实体模型函数中的实体模型函数44n绘制制实体或体或线框框圆环voidglutSolidTorus/glutWireTorus(GLdoubleinnerRadius, GLdouble outerRadius, GLintslices,GLintstacks);n绘制制实体或体或线框茶框茶壶voi
21、dglutSolidTeapot/glutWireTeapot(GLdoublesize);OpenGL中的实体模型函数中的实体模型函数45oGLU二次曲面函数二次曲面函数n定定义一个二次曲面一个二次曲面GLUquadricObj*sphere;n激活二次曲面激活二次曲面绘制器制器sphere=gluNewQuadric();n指定二次曲面的指定二次曲面的绘制方式制方式gluQuadricDrawStyle(sphere,GLU_LINE);OpenGL中的实体模型函数中的实体模型函数46n绘制二次曲面制二次曲面gluSphere(sphere,radius,slices,stacks);gl
22、uCylinder(sphere,baseRadius,topRadius,height,slices,stacks)；gluDisk(sphere,innerRadius,outerRadius,slices,stacks)；OpenGL中的实体模型函数中的实体模型函数47非规则对象的表示非规则对象的表示o分形几何分形几何o形状语法形状语法o粒子系统粒子系统o基于物理的建模基于物理的建模o数据场的可视化数据场的可视化48o分分形形几几何何物物体体具具有有一一个个基基本本特特征征：无无限限的的自自相相似性似性。o无无限限的的自自相相似似性性是是指指物物体体的的整整体体和和局局部部之之间细节的无
23、限重的无限重现。分形几何分形几何( (fractal geometry)fractal geometry)49o分形分形维维数，又称分数数，又称分数维维数数4 = 228 = 23N = KD D=lgN/lgk K为边长缩小倍数；为边长缩小倍数； N为边长缩小后产为边长缩小后产生的新形体个数。生的新形体个数。分形几何分形几何( (fractal geometry)fractal geometry)图图4.18 4.18 分形维数分形维数50o生成生成过程：初始生成元（程：初始生成元（initiatorinitiator）、）、生成生成元（元（generatorgenerator）。o实例例图
24、图4.19 4.19 生成过程生成过程分形几何分形几何( (fractal geometry)fractal geometry)51形状语法形状语法o形形状状语法法（shape grammars）：给定定一一组产生生式式规则，形形状状设计者者可可以以在在从从给定定初初始始物物体体到到最最终物物体体结构构的的每每一一次次变换中中应用用不不同同的的规则。o产生生式式规则可可以以用用具具有有图形形运运算算能能力力的的数数学学式式或其他或其他过程性方法程性方法结合合实现。52粒子系统粒子系统o用用于于模模拟自自然然景景物物或或模模拟其其它它非非规则形形状状物物体体展展示示“流流体体”性性质的的一一个个
25、方方法法是是微微粒粒系系统（particle systems）。o这一方法尤其擅一方法尤其擅长描述随描述随时间变化的物体。化的物体。o微微粒粒运运动的的模模拟方方式式：随随机机过程程模模拟、运运动路路径模径模拟、力学模、力学模拟。53基于物理的建模基于物理的建模o基基于于物物理理的的建建模模方方法法：描描段段与与层次次建建模模述述了了物物体在内外力相互作用下的行体在内外力相互作用下的行为。o通通常常用用一一组网网格格结点点来来逼逼近近物物体体。网网格格结点点间取取为柔柔性性连接接，再再考考虑贯穿穿物物体体网网格格的的力力传递。54数据场的可视化数据场的可视化o科科学学计算算可可视化化（scie
26、ntific visualization）指指的的是是运运用用计算算机机图形形学学和和图像像处理理技技术，将将科科学学计算算过程程中中及及计算算结果果的的数数据据转换为图形形及及图像像在在屏屏幕幕上上显示示出出来来并并进行行交交互互处理的理理的理论、方法和技、方法和技术。554.4 层次模型层次模型o段与层次模型段与层次模型o层次模型的实现层次模型的实现oOpenGL中的层次模型中的层次模型56段与层次模型段与层次模型o具具有有逻逻辑辑意意义义的的有有限限个个图图素素（或或体体素素）及及其其附附加加属属性性的的集集合合称称为为段段，或或者者称称为为图图段段（二二维维空间中）、结构和对象。空间中
27、）、结构和对象。o段是可以嵌套段是可以嵌套o段段与与基基本本图图形形元元素素的的区区别别在在于于，基基本本图图形形元元素素是用数据来描述的，而段是用规则来描述的。是用数据来描述的，而段是用规则来描述的。57段与层次模型段与层次模型o段段一一般般具具有有三三个个特特性性：可可见见性性、醒醒目目性性和和可可选选择性（可由交互式输入设备来选择）。择性（可由交互式输入设备来选择）。o利用段的嵌套来构造复杂的对象或系统。利用段的嵌套来构造复杂的对象或系统。图图4.20 4.20 自行车及其层次描述自行车及其层次描述58p存储简单：一个段虽然在图中各处出现，但他存储简单：一个段虽然在图中各处出现，但他的几
28、何和拓扑信息只要保存一次。的几何和拓扑信息只要保存一次。p编辑简单：删除、移动及缩放操作都可以以段编辑简单：删除、移动及缩放操作都可以以段为单位。为单位。段与层次模型段与层次模型59层次模型的实现层次模型的实现o系系统统的的层层次次模模型型可可以以通通过过将将一一个个图图段段嵌嵌套套到到另另一一个个图图段段中中形形成成图图段段树树来来创创建建。不不同同的的段段和和基基本图形元素在各自的建模坐标系中定义。本图形元素在各自的建模坐标系中定义。o图图层层。通通过过把把功功能能相相同同的的部部分分归归类类，并并将将它它们们绘制在同一层上，有助于图形的理解和管理。绘制在同一层上，有助于图形的理解和管理。
29、o一般图层不再嵌套。一般图层不再嵌套。60OpenGL中层次模型的实现中层次模型的实现o显示列表的创建显示列表的创建glNewList(listID,listMode);glutSolidCube(2.0);glEndList();o显示列表的执行显示列表的执行voidglListBase(GLuintoffsetValue);61OpenGL中层次模型的实现中层次模型的实现o多级显示列表多级显示列表OpenGL支支持持创建建多多级显示示列列表表，即即在在glNewList和和glEndLsit函函数数对之之间允允许调用用glCallList函数来函数来执行其他行其他显示列表。示列表。o显示列表的删除显示列表的删除voidglDeleteLists(GLuintlistID,GLsizeirange);
