4图形的表示与数据结构ppt课件

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

2、义实体的定义o 正则集合运算正则集合运算o 欧拉公式欧拉公式4.1 4.1 基本概念基本概念4o 把研究如何在计算机中建立恰当的模型表示不同把研究如何在计算机中建立恰当的模型表示不同图形对象的技术称为造型技术。图形对象的技术称为造型技术。o 有两类图形对象：有两类图形对象：o 规则对象：几何造型、几何模型。规则对象：几何造型、几何模型。o 能用欧氏几何加以描述的对象能用欧氏几何加以描述的对象o 不规则对象：过程式模拟。不规则对象：过程式模拟。o 不能用欧氏几何加以描述的对象不能用欧氏几何加以描述的对象基本概念基本概念造型技术造型技术5基本概念基本概念基本图形元素基本图形元素p 基本图形元素：图

3、素或图元、体素。基本图形元素：图素或图元、体素。p 图素是指可以用一定的几何参数和属性参数描图素是指可以用一定的几何参数和属性参数描述的最基本的图形输出元素。述的最基本的图形输出元素。p 在二维图形系统中将基本图形元素称为图素或在二维图形系统中将基本图形元素称为图素或图元，在三维图形系统中称为体素。图元，在三维图形系统中称为体素。6 图形对象的描述离不开大量的图形信息和非图形信息。图形对象的描述离不开大量的图形信息和非图形信息。图形信息图形信息几何信息：形体在欧氏空间中的位置和大小。几何信息：形体在欧氏空间中的位置和大小。拓扑信息：形体各分量点、边、面的数目及其相互间的拓扑信息：形体各分量点、

4、边、面的数目及其相互间的连接关系。连接关系。非图形信息非图形信息基本概念基本概念几何信息与拓扑信息几何信息与拓扑信息包括图形对象，构成对象的包括图形对象，构成对象的点、线、面的位置和几何尺寸，点、线、面的位置和几何尺寸，以及它们相互之间的关系等以及它们相互之间的关系等图形的线性、颜色、亮度以图形的线性、颜色、亮度以及供模拟和分析用的质量、比重、及供模拟和分析用的质量、比重、体积等数据体积等数据图图4.1 4.1 拓扑信息拓扑信息8o 刚体运动：不改变图形上任意两点间的距离，刚体运动：不改变图形上任意两点间的距离，也不改变图形的几何性质的运动。也不改变图形的几何性质的运动。o 拓扑运动：允许形体

5、作弹性运动，即在拓扑关拓扑运动：允许形体作弹性运动，即在拓扑关系中，对图形可随意地伸张扭曲。但图上各个系中，对图形可随意地伸张扭曲。但图上各个点仍为不同的点，决不允许把不同的点合并成点仍为不同的点，决不允许把不同的点合并成一个点。一个点。基本概念基本概念几何信息与拓扑信息几何信息与拓扑信息9o 建模坐标系建模坐标系Modeling Coordinate System）o 用户坐标系用户坐标系o 观察坐标系观察坐标系Viewing Coordinate System）o 规格化设备坐标系规格化设备坐标系Normalized Device coordinate System）o 设备坐标系设备坐标

6、系Device Coordinate System）基本概念基本概念坐标系坐标系10基本概念基本概念实体实体图图4.2 4.2 带有悬挂边的立方体带有悬挂边的立方体11o 点的领域：如果点的领域：如果P是点集是点集S的一个元素，那么点的一个元素，那么点P的以的以RR0为半径的领域指的是围绕点为半径的领域指的是围绕点P的半径为的半径为R的小的小球二维情况下为小圆）。球二维情况下为小圆）。o 开集的闭包：是指该开集与其所有边界点的集合并集，开集的闭包：是指该开集与其所有边界点的集合并集，本身是一个闭集。本身是一个闭集。o 正则集：由内部点构成的点集的闭包就是正则集，三维正则集：由内部点构成的点集的

7、闭包就是正则集，三维空间的正则集就是正则形体。空间的正则集就是正则形体。 基本概念实体基本概念实体12基本概念实体基本概念实体o 组成三维物体的点的集合可以分为两类：组成三维物体的点的集合可以分为两类： o 内点为点集中的这样一些点，它们具有完全包内点为点集中的这样一些点，它们具有完全包含于该点集的充分小的领域。含于该点集的充分小的领域。o 边界点：不具备此性质的点集中的点。边界点：不具备此性质的点集中的点。 13基本概念基本概念实体实体o 定义点集的正则运算定义点集的正则运算r运算为：运算为：AicAro 正则运算即为先对物体取内点再取闭包的运算。正则运算即为先对物体取内点再取闭包的运算。r

8、A称为称为A的正则集。的正则集。14(a)带有孤立点和边的二维点集A(b)内点集合iA(c)正则点集ciA基本概念基本概念实体实体图图4.3 4.3 实体的例子实体的例子15图图4.4 4.4 正则形体正则形体基本概念基本概念实体实体16o 二维流形指的是对于实体表面上的任意一点，二维流形指的是对于实体表面上的任意一点，都可以找到一个围绕着它的任意小的领域，该都可以找到一个围绕着它的任意小的领域，该领域与平面上的一个圆盘是拓扑等价的。领域与平面上的一个圆盘是拓扑等价的。 基本概念基本概念实体实体图图4.5 4.5 正则形体正则形体17o 实体：对于一个占据有限空间的正则形体，如实体：对于一个占

9、据有限空间的正则形体，如果其表面是二维流形，则该正则形体为实体。果其表面是二维流形，则该正则形体为实体。基本概念基本概念实体实体18p 有效实体的封闭性。有效实体的封闭性。p 把能够产生正则形体的集合运算称为正则集合运把能够产生正则形体的集合运算称为正则集合运算。算。基本概念基本概念正则集合运算正则集合运算19图图4.6 集合运算与正则集合运算集合运算与正则集合运算基本概念基本概念正则集合运算正则集合运算20图图4.7 基于点的领域概念生成正则形体基于点的领域概念生成正则形体基本概念基本概念正则集合运算正则集合运算B)(b- sharedA bA),in B(b- B,out A bB)-(A

10、bBb sharedA bA,in Bb B,in A bB)(AbBb sharedA bA,out Bb B,out A bB)(Ab*图图4.8 正则集合运算正则集合运算A*B，A*B，A*B的结果实线表示结果形体的边界）的结果实线表示结果形体的边界）22基本概念基本概念平面多面体与欧拉公平面多面体与欧拉公式式o 欧拉公式证明简单多面体的顶点数欧拉公式证明简单多面体的顶点数V、边数、边数E和面和面数数F满足如下关系：满足如下关系：V-E+F=2。o 非简单多面体需对欧拉公式加以扩展。令非简单多面体需对欧拉公式加以扩展。令H表示表示多面体表面上孔的个数，多面体表面上孔的个数，G表示贯穿多面

11、体的孔表示贯穿多面体的孔的个数，的个数，C表示独立的、不相连接的多面体数，表示独立的、不相连接的多面体数，则扩展后的欧拉公式为：则扩展后的欧拉公式为：V-E+F-H=2C-G）。）。23基本概念基本概念平面多面体与欧拉公平面多面体与欧拉公式式图图4.9 平面多面体与欧拉公式平面多面体与欧拉公式24o 线框模型与实体模型实体造型技术）线框模型与实体模型实体造型技术）o 可以将实体模型的表示大致分为三类：可以将实体模型的表示大致分为三类：o 边界表示边界表示Boundary representation, B-reps）o 构造实体几何表示构造实体几何表示o 空间分割空间分割Space-parti

12、tioning表示表示4.2 4.2 三维形体的表示三维形体的表示25o 多边形表面模型多边形表面模型o 扫描表示扫描表示o 构造实体几何法构造实体几何法o 空间位置枚举表示空间位置枚举表示o 八叉树八叉树o BSPBSP树树o OpenGLOpenGL中的实体模型函数中的实体模型函数三维形体的表示三维形体的表示26o 边界表示边界表示(B-reps)的最普遍方式是多边形表的最普遍方式是多边形表面模型，它使用一组包围物体内部的平面多面模型，它使用一组包围物体内部的平面多边形，也即平面多面体，来描述实体。边形，也即平面多面体，来描述实体。多边形表面模型多边形表面模型图图4.10 4.10 四面体

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

14、表面模型多边形表面模型数据结构数据结构o 属性信息属性信息o 用属性表来存储多边形面的属性，指用属性表来存储多边形面的属性，指明物体透明度及表面反射度的参数和纹理特明物体透明度及表面反射度的参数和纹理特征等等。征等等。30o 多边形网格：三维形体的边界通常用多边形网多边形网格：三维形体的边界通常用多边形网格格polygon mesh的拼接来模拟。的拼接来模拟。o 例子例子多边形表面模型多边形表面模型图图4.12 4.12 三角形带与四边形网格三角形带与四边形网格31o 扫描表示法扫描表示法sweep representation可以利可以利用简单的运动规则生成有效实体。用简单的运动规则生成有效

15、实体。 o 包含两个要素包含两个要素o 一是作扫描运动的基本图形截面）；一是作扫描运动的基本图形截面）；o 二是扫描运动的方式。二是扫描运动的方式。 扫描表示扫描表示sweep representationsweep representation）32o 构造实体几何法构造实体几何法CSG，Constructive Solid Geometry由两个实体间的并、交或差操作由两个实体间的并、交或差操作生成新的实体。生成新的实体。BAAABB(a)A,B形体的并(b)A,B形体的差(c)A,B形体的交构造实体几何法构造实体几何法图图4.13 4.13 构造实体几何法构造实体几何法33o 在构造实体

16、几何法中，集合运算的实现过程可在构造实体几何法中，集合运算的实现过程可以用一棵二叉树称为以用一棵二叉树称为CSG树来描述。树来描述。o 树的叶子是基本体素或是几何变换参数；树的叶子是基本体素或是几何变换参数；o 树的非终端结点是施加于其子结点的正则集合树的非终端结点是施加于其子结点的正则集合算子正则并、正则交和正则差或几何变换算子正则并、正则交和正则差或几何变换的定义。的定义。构造实体几何法构造实体几何法34构造实体几何法构造实体几何法图图4.14 4.14 由由CSGCSG树产生二维形体的实例树产生二维形体的实例35o 优点：如果体素设置比较齐全，通过集合运算优点：如果体素设置比较齐全，通过

17、集合运算就可以构造出多种不同的符合需要的实体。就可以构造出多种不同的符合需要的实体。o 缺点一：集合运算的中间结果难以用简单的代缺点一：集合运算的中间结果难以用简单的代数方程表示，求交困难。数方程表示，求交困难。o 缺点二：缺点二：CSG树不能显式地表示形体的边界，树不能显式地表示形体的边界，因而无法直接显示因而无法直接显示CSG树表示的形体。树表示的形体。构造实体几何法构造实体几何法36o 处置：光线投射算法处置：光线投射算法构造实体几何法构造实体几何法图图4.15 4.15 光线投射算法光线投射算法( (实体实体ABAB取取adad，实体，实体ABAB则取则取cb,cb,实体实体A-BA-

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

19、构的八叉树来表示实体。叉树来表示实体。八叉树八叉树39八叉树八叉树四叉树四叉树图图4.16 4.16 二维图的四叉树表示二维图的四叉树表示40八叉树八叉树图图4.17 4.17 三维空间分成八个卦限及其节点表示三维空间分成八个卦限及其节点表示41o 二 叉 空 间 分 割 二 叉 空 间 分 割 B i n a r y S p a c e Partitioning，BSP树方法是一种类似于树方法是一种类似于八叉树的空间分割方法，它每次将一实体用八叉树的空间分割方法，它每次将一实体用任一位置和任一方向的平面分为二部分不任一位置和任一方向的平面分为二部分不同于八叉树方法的每次将实体用平行于笛卡同于

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

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

22、制实体或线框球面绘制实体或线框球面o void glutSolidSphere/glutWireSphere (GLdouble radius, GLint slices, GLint stacks);o 绘制实体或线框圆锥面绘制实体或线框圆锥面o void glutSolidCone/glutWireCone (GLdouble radius, GLdouble height, GLint slices, GLint stacks);OpenGL中的实体模型函数中的实体模型函数44n 绘制实体或线框圆环绘制实体或线框圆环n v o i d g l u t S o l i d T o r u

23、s / g l u t W i r e T o r u s ( G L d o u b l e i n n e r R a d i u s , G L d o u b l e outerRadius, GLint slices,GLint stacks);n 绘制实体或线框茶壶绘制实体或线框茶壶n void glutSolidTeapot/glutWireTeapot (GLdouble size);OpenGL中的实体模型函数中的实体模型函数45o GLU二次曲面函数二次曲面函数o 定义一个二次曲面定义一个二次曲面o GLUquadricObj *sphere;o 激活二次曲面绘制器激活二次

24、曲面绘制器o sphere = gluNewQuadric( );o 指定二次曲面的绘制方式指定二次曲面的绘制方式o gluQuadricDrawStyle(sphere, GLU_LINE); OpenGL中的实体模型函数中的实体模型函数46n 绘制二次曲面绘制二次曲面n gluSphere(sphere, radius, slices, stacks);n gluCylinder(sphere,baseRadius,topRadius, height, slices, stacks)；n gluDisk(sphere,innerRadius,outerRadius, slices, sta

25、cks)；n OpenGL中的实体模型函数中的实体模型函数47非规则对象的表示非规则对象的表示o 分形几何分形几何o 形状语法形状语法o 粒子系统粒子系统o 基于物理的建模基于物理的建模o 数据场的可视化数据场的可视化48o 分形几何物体具有一个基本特征：无限的自相分形几何物体具有一个基本特征：无限的自相似性。似性。o 无限的自相似性是指物体的整体和局部之间细无限的自相似性是指物体的整体和局部之间细节的无限重现。节的无限重现。分形几何分形几何(fractal geometry)(fractal geometry)49o 分形维数，又称分数维数分形维数，又称分数维数4 = 228 = 23N =

26、 KD D=lgN/lgk K为边长缩小倍数；为边长缩小倍数； N为边长缩小后产为边长缩小后产生的新形体个数。生的新形体个数。分形几何分形几何(fractal geometry)(fractal geometry)图图4.18 4.18 分形维数分形维数50o 生成过程：初始生成元生成过程：初始生成元initiatorinitiator）、生成）、生成元元generatorgenerator）。）。o 实例实例图图4.19 4.19 生成过程生成过程分形几何分形几何(fractal geometry)(fractal geometry)51形状语法形状语法o 形状语法形状语法shape gra

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

28、法尤其擅长描述随时间变化的物体。o 微粒运动的模拟方式：随机过程模拟、运动路微粒运动的模拟方式：随机过程模拟、运动路径模拟、力学模拟。径模拟、力学模拟。53基于物理的建模基于物理的建模o 基于物理的建模方法：描段与层次建模述了基于物理的建模方法：描段与层次建模述了物体在内外力相互作用下的行为。物体在内外力相互作用下的行为。o 通常用一组网格结点来逼近物体。网格结点通常用一组网格结点来逼近物体。网格结点间取为柔性连接，再考虑贯穿物体网格的力间取为柔性连接，再考虑贯穿物体网格的力传递。传递。54数据场的可视化数据场的可视化o 科学计算可视化科学计算可视化scientific visualizati

29、on指指的是运用计算机图形学和图像处理技术，将的是运用计算机图形学和图像处理技术，将科学计算过程中及计算结果的数据转换为图科学计算过程中及计算结果的数据转换为图形及图像在屏幕上显示出来并进行交互处理形及图像在屏幕上显示出来并进行交互处理的理论、方法和技术。的理论、方法和技术。554.4 层次模型层次模型o 段与层次模型段与层次模型o 层次模型的实现层次模型的实现o OpenGL中的层次模型中的层次模型56段与层次模型段与层次模型o 具有逻辑意义的有限个图素或体素及其具有逻辑意义的有限个图素或体素及其附加属性的集合称为段，或者称为图段二附加属性的集合称为段，或者称为图段二维空间中）、结构和对象。维空间中）、结构和对象。o 段是可以嵌套段是可以嵌套o 段与基本图形元素的区