计算机图形学：第3章 图形的表示与数据结构

1、第三章 图形的表示与数据结构3.1 基本概念3.2 三维形体的表示3.3 非规则对象的表示3.4 图形的层次结构引言如何在计算机内构造并表示出该物体如何组织图形对象的描述数据以使存储这些数据所要的空间最省，检索、处理这些数据的速度较快引言造型技术：研究如何在计算机中建立恰当的模 型表示不同图形对象的技术 规则对象(几何造型)不规则对象图形对象能用欧式几何进行描述的形体，如点、直线、曲线、平面、曲面或实体;也称为几何模型。不能用欧式几何进行描述的形体，如山、水、树、草、云、烟等自然界丰富多彩的对象3.1 基本概念3.1.1基本图形单元与段的概念3.1.2几何信息与拓扑信息3.1.3坐标系3.1.

2、4几何元素3.1.5实体的定义3.1.6正则集合运算3.1.7平面多面体与欧拉公式3.1 基本概念3.1.1 基本图形单元与段的概念 基本图形元素：二维：图素(图元)；三维：体素图素(图元)：是指可以用一定的几何参数和属性参数描述的最基本的图形输出元素。例如：点、线、圆、圆弧、椭圆、二次曲线等体素：是三维空间中可以用有限个尺寸参数定位和定形的最基本的单元体。 通常有三种形式的定义如下：(1)从实际形体中选择出来，可用一些确定的尺寸参数控制其最终位置和形状的一组单元实体(2)由参数定义的一条(或一组)轮廓线沿一条(或一组)空间参数曲线作扫描运动而产生的形体。(3)用代数半空间定义的形体复杂网络:

3、 Internet3.1 基本概念段也称为图段、结构和对象段是指具有逻辑意义的有限个图素（或体素）及其附加属性的集合段可以嵌套3.1 基本概念左图中基本图素是直线、圆和文本，但是逻辑电路中最简单的元素是门，所以可以将门定义为最基本的图段，它就是由图素和门电路规则来定义的。左图中的触发器是更高层次的逻辑电路图段。图素和体素是由数据来描述的段是用规则来描述的，由规则最终可以找出形成它的所有的基本元素。3.1 基本概念3.1.2 几何信息与拓扑信息 图形对象的描述图形信息(对象及点、线、面的位置、相互关系和几何尺寸等)几何信息(形体在欧氏空间的位置和大小)拓扑信息(形体各分量的数目及相互连接关系)非

4、图形信息(图形的线型、颜色、亮度、以及对象的质量、比重、体积等)3.1 基本概念1. 几何信息（1）几何分量的数学表示 （2）几何分量之间的相互关系点: (x,y,z）直线：X=(y-y0)/a=(z-z0)/b平面：ax+by+cz+d=0 形体的几何分量之间可以相互转换 相互关系由于几何信息常会出现形体表示上的二义性，所以还应提供拓扑信息。几何分量之间的相互关系拓扑信息平面立体的几何分量之间一共有九种拓扑关系拓扑信息刚体运动：不改变图形上任意两点间的距离，也不改变图形的几何性质的运动。非弹性运动。拓扑运动：允许形体作弹性运动。即在拓扑关系中，对图形可随意地伸张扭曲。但图上各个点仍为不同的点

5、，决不允许把不同的点合并成一个点。拓扑信息拓扑等价：一个图形作拓扑运动与另一个图形重合。拓扑性质：与该图形拓扑等价的图形的性质。3.1 基本概念3.1.3 坐标系 用户坐标系建模坐标系观察坐标系规格化的设备坐标设备坐标系坐标系直角坐标系仿射坐标系圆柱坐标系球坐标系极坐标系图4-4 坐标系的分类建模坐标系(Modeling Coordinate System):定义基本图素和图段，有各自的坐标原点和长度单位。可调用到用户坐标系指定位置。3.1 基本概念3.1.3 坐标系 用户坐标系建模坐标系观察坐标系规格化的设备坐标设备坐标系坐标系直角坐标系仿射坐标系圆柱坐标系球坐标系极坐标系图4-4 坐标系的

6、分类用户坐标系(World Coordinate System WC)： 也叫世界坐标系。总体坐标系，用于定义用户整图或最高层图形结构。3.1 基本概念3.1.3 坐标系 用户坐标系建模坐标系观察坐标系规格化的设备坐标设备坐标系坐标系直角坐标系仿射坐标系圆柱坐标系球坐标系极坐标系图4-4 坐标系的分类观察坐标系(VC,Viewing Coordinate System)：可在用户坐标系任何位置、任何方向定义，确定显示部分；将用户坐标转变为规格化的设备坐标。3.1 基本概念3.1.3 坐标系 用户坐标系建模坐标系观察坐标系规格化的设备坐标设备坐标系坐标系直角坐标系仿射坐标系圆柱坐标系球坐标系极坐

7、标系图4-4 坐标系的分类规格化的设备坐标（NDC,Normalized Device Coordinate System ):定义视图区，取值范围(0.0,0.0,0.0,)到(1.0,1.0,1.0)3.1 基本概念3.1.3 坐标系 用户坐标系建模坐标系观察坐标系规格化的设备坐标设备坐标系坐标系直角坐标系仿射坐标系圆柱坐标系球坐标系极坐标系图4-4 坐标系的分类设备坐标系(DC, Device Coordinate System):输入、输出设备的坐标。3.1 基本概念3.1.4 几何元素 欧氏空间中，形体有点、线、面、环、体等几何元素构成。（1）点点是0维几何元素点是形体最基本的元素用

8、计算机存储管理输出形体的实质就是对点集及其连接关系的处理在自由曲线面的描述中常用三种类型的点：控制点、型值点、插值点3.1 基本概念3.1.4 几何元素 （2）线线是一维几何元素线是两个邻面或多个邻面的交界直线由其端点（起点和终点）定界曲线由一系列的控制点或型值点构成3.1 基本概念3.1.4 几何元素 （3）面面是二维几何元素面是形体上一个有限非零的区域面由一个外环和若干个内环界定其范围面有方向性3.1 基本概念3.1.4 几何元素 （4）环环是有序、有向边（直线段或曲线段）组成的面的封闭边界。环中的边不能相交，相邻两条边共享一个端点确定面的最大外边界的环称之为外环确定面中内孔或凸台边界的环

9、称之为内环在面上沿一个环前进，其左侧总是面内，右侧总是面外。3.1 基本概念3.1.4 几何元素 （5）体体是三维几何元素由封闭表面围成空间，也是欧氏空间R3中非空、有界的封闭子集，其边界是有限面的并集。3.1 基本概念3.1.5 实体的定义 计算机中以数学方法描述的形体可能是无效的，所谓无效是指客观不存在的例如下图表示的三维形体就不是一个有意义的物体3.1 基本概念3.1.5 实体的定义 实体造型中必须保证形体的有效性客观存在的三维形体具有如下性质：(1)刚性：有一定的形状。(2)维数的一致性：三维空间中物体各部分必须是三维的，不能有悬挂的或孤立的边界。(3)占据有限的空间：有固定的体积。(

10、4)边界的确定性：根据边界能区别物体的内部和外部。(5)封闭性：经刚体运动和集合运算后仍是有效物体。3.1 基本概念3.1.5 实体的定义 三维空间中的物体是一个内部连通的三维点集，是由其内部的点集及紧紧包着这些点的表皮组成的。从点集拓扑的角度定义三维有效物体： 三维空间中的正则集，也就是正则形体即是三维有效实体正则集就是由内部点构成的点集的闭包开集的闭包指该开集与其所有边界点的集合的并集3.1 基本概念3.1.5 实体的定义 内点：内点为点集中的这样一些点，它们具有完全包含于该点集的充分小的领域。边界点：不具备内点性质的点集中的点点集的正则运算的定义：可见，正则运算即为先对物体取内点再取闭包

11、的运算。rA称为A的正则集。A-为一点集i- 为取内点运算c- 为取闭包运算3.1 基本概念3.1.5 实体的定义 可见，在取内点集合时就把孤立边去掉了在图（）为得到的正则点集正则运算实例3.1 基本概念3.1.5 实体的定义 并不是所有的正则实体都是实体模型的描述对象如右图中的正则形体，在实体造型中常被处理为两个有效立方体实体模型描述的实体应具有二维流形性质3.1 基本概念3.1.5 实体的定义 二维流形指的是对于实体表面上的任意一点，都可以找到一个围绕着它的任意小的领域，该领域与平面上的一个圆盘是拓扑等价的。 3.1 基本概念3.1.5 实体的定义 对于一个占据有限空间的正则形体，如果其表

12、面是二维流形，则该正则形体为实体。该定义条件是可以检测的，所以可由计算机来衡量一个形体是否为实体3.1 基本概念3.1.6 正则集合运算 集合运算正则运算区别正则集合运算与集合运算3.1 基本概念3.1.6 正则集合运算 （1）间接方式：先按通常的集合运算进行计算，再用一些规则除去不符合正则定义的孤立点、边等。主要基于点集拓扑的领域概念过程演示（2）直接方式：定义出正则集合算子的表达式，用它直接得出符合正则形体定义的结果建立在集合成员分类的基础上具体过程实现正则运算的两种方法3.1 基本概念3.1.6 正则集合运算（领域概念） 如果P是点集S的一个元素，那么点P的以R （R0）为半径的领域指的

13、是围绕点P 的半径为 R的小球（或小园）.如果点P的领域与S的交集是该领域本身，则称该领域为满;如果点P的领域与S的交集是空集，则称该领域为空;如果点P的领域与S的交集非满非空。则称该领域既不满也不空。领域概念可以描述点P附近的几何性质。当且仅当P的领域为满时，P在S内；当且仅当P的领域为空时，P在S外；当且仅当P的领域集不满也不空时，P在S边界上。3.1 基本概念3.1.6 正则集合运算 PA与PB的交集为空所以P点不在它们的正则交集之中， 而RA与RB的交集既不为空也不满，所以R点在边界3.1 基本概念预备知识（一）：一个正则形体可由其边界点集来定义三维空间中给定一个正则形体S后，空间点集

14、就被分为三个子集：S的内部点集S的边界点集S之外的点集给定一个正则形体S及一个有界面G，则G相对于S的分类函数为：C(S,G)=G in S, G out S, G on S 3.1 基本概念预备知识：C(S,G)=G in S, G out S, G on S 其中，3.1 基本概念用-G表示有界面G的反向面。即，如果有界面G在P点的法向为NP(G)，则有界面-G在P点的法向就是-NP(G)。于是：G on S=G shared (bS), G shared (-bS)3.1 基本概念所以G相对于S的分类函数C(S,G)可为： C(S,G)=G in S, G out S, G shared

15、 (bS), G shared (-bS)正则集合算子 3.1 基本概念3.1 基本概念3.1.7 平面多面体与欧拉公式 平面多面体是表面由平面多边形构成的三维物体。简单多面体指与球拓扑等价的那些多面体。 欧拉公式证明简单多面体的顶点数V、边数E和面数F满足如下关系： V-E+F=2。 欧拉公式应用实例非简单多面体的欧拉公式令H表示多面体表面上孔的个数，G表示贯穿多面体的孔的个数，C表示独立的、不相连接的多面体数，则扩展后的欧拉公式为：V-E+F-H=2（C-G）3.2 三维形体的表示几何造型系统中，描述物体的三维模型有三种：线框模型:出现最早，方法简单，但存在很多不足，因此应用不广。表面模型

16、：是一种用包围物体内部的边界面来表示物体的模型，但仍有一些不足实体模型：也叫实体造型技术，是应用最广泛的三维形体的实体模型表示。3.2 三维形体的表示该模型最早用来表示物体的模型，计算机绘图是它的一个重要应用。该模型是由定义一个物体边界的直线和曲线组成，每一条线都是单独构造出来，不存在面的信息线框模型存在许多缺陷(下屏)(1) 线框模型3.2 三维形体的表示(1) 线框模型表示的三维形体常有二义性或多义性容易构造出无效形体不能正确表示曲面信息无法进行图形的线面消隐（包含信息有限）。加重用户的输入负担难以保证数据的统一性和有效性。3.2 三维形体的表示(1) 线框模型二义性示例多义性示例3.2

17、三维形体的表示(1) 线框模型无效形体示例 同一物体各面之间的相互穿透3.2 三维形体的表示(1) 线框模型不能正确表示曲面示例 3.2 三维形体的表示(2) 表面模型表面模型在线框模型的基础上，增加了物体中面的信息，用面的集合来表示物体，而用环来定义面的边界。表面模型扩大了线框模型的应用范围，能够满足面面求交、线面消隐、明暗色彩图、数控加工等需要。3.2 三维形体的表示(2) 表面模型表面模型的缺陷：只有一张张面的信息，物体究竟存在于表面的哪一侧，并没有给出明确的定义，无法计算和分析物体的整体性质，如物体的表面积、体积、重心等不能将物体作为一个整体去考察它与其它物体相互关联的性质，如是否相交

18、等 3.2 三维形体的表示（3） 实体模型实体模型是最高级的三维物体模型，它能完整地表示物体的所有形状信息。它可以无歧义地确定一个点是在物体外部、内部或表面上，这种模型能够进一步满足物性计算、有限元分析等应用的要求。实体模型的分类边界表示即用一组曲面（含平面）来描述物体，这些曲面将物体分为内部和外部。构造表示即将实体表示成立方体、长方体、圆柱体、圆锥体等基本图素的组成。分割表示将包含物体的空间区域划分成一组小的非重叠的连续实体（立方体）3.2 三维形体的表示3.2.1多边形表面模型是边界表示的最普遍方式是利用平面多面体来描述实体，如下图所示能够简化并加速物体的表面绘制和显示3.2 三维形体的表

19、示3.2.1多边形表面模型1.多边形表用多边形数据表来存放多边形的信息多边形数据表分为两组几何表属性表存储几何数据需要：顶点表、边表、多边形表。存储拓扑信息：翼边结构表示检验是否是有效实体的条件 包括顶点坐标和标识多边形空间方向的参数 包括指明物体透明及表面反射度的参数和纹理特征3.2 三维形体的表示四面体的三张表示例x1,y1,z1顶点表ABCDx2,y2,z2x3,y3,z3x4,y4,z4 BCB,D边表ABA,B CAADBDCD B,CC,A A,DC,D多边形表ABCABDBCDACDAB,BC,AC AB,BD,ADBC, CD,BDAC,CD,AD（几何信息）3.2 三维形体的

20、表示翼边结构表示（拓扑信息） 对于一个多面体的每条边指出它的两个相邻面、两个端点、四个相邻边。这四条相邻边好像神展的翅膀，这种表示方法因此叫做翼边结构表示。3.2 三维形体的表示多边形表中数据的检验通常进行以下测试：每个顶点至少是两条边的端点每条边至少是一个多边形的部分每个多边形是封闭的每个多边形至少有一条公共边如果边表包含指向多边形边的指针，则每一个被指针指向的边有一个逆指针指回到多边形3.2 三维形体的表示2.平面方程通过方程对输入的数据表示加以处理，才能显示三维实体通过平面方程可以做：求得平面的法向量鉴别空间上的点与物体平面的位置关系。判别点在面的内部或外部3.2 三维形体的表示3.多边

21、形网格三维形体的边界用曲面描述时通常用多边形网格（polygon mesh）的拼接来近似。多边形网格的类型：三角形带四边形网格高性能的图形系统一般采用多边形网格及相应的几何、属性信息数据库来对三维系统建模应用举例（下一屏）3.2 三维形体的表示3.多边形网格应用3.2 三维形体的表示3.2.2 构造表示构造表示是按照生成过程来定义形体的方法，通常分为：扫描表示构造实体几何表示特征表示 3.2 三维形体的表示1.扫描表示扫描表示法（sweep representation）可以利用简单的运动规则生成有效实体。3.2 三维形体的表示1.扫描表示扫描表示需要两个要素：作扫描运动的基本图形扫描运动的方

22、式扫描运动的方式有：旋转扫描非圆形路径扫描广义扫描法实例形体（下一屏）3.2 三维形体的表示1.扫描表示3.2 三维形体的表示2.构造实体几何法构造实体几何法（CSG，Constructive Solid Geometry）：由两个实体间的并、交或差操作生成新的实体。3.2 三维形体的表示2.构造实体几何法构造实体几何法的优点：可以构造出多种不同的符合需要的实体。构造实体几何法的缺陷：求交困难CSG树不能显式地表示形体的边界 光线投射（Ray-casting）算法3.2 三维形体的表示2.构造实体几何法（光线投射算法）1)将射线与CSG树中的所有基本体素求交，求出所有的交点。2)将所有交点相对

23、于CSG树表示的物体进行分类，确定位于物体边界上的那部分交点。3)对所有位于物体边界上的交点计算它们在射线上的参数值并进行排序，确定距离最近的交点。得到其所在基本体素表面的法矢量。如右图所示实体AB则取ad，实体AB则取cb,实体A-B则取ab3.2 三维形体的表示3.特征表示特征是面向应用、面向用户的。基于特征的造型系统如图，可见特征模型的表示仍然要通过传统的几何造型系统来实现。 3.2 三维形体的表示3.特征表示特征的形状常用若干个参数来定义如图所示，圆柱和圆锥特征用底面直径D和高度H来定义，方块特征用长度L，宽度W和高度H来定义。 HWDHDH3.2 三维形体的表示3.2.3 分割表示分割表示是将形体按某种规则分解为小的、更易于描述的部分，每一小部分又可分为更小的部分，这种分解过程直至每一小部分都能够直接描述为止。常用方法有：空间位置枚举表示八叉树表示BSP树表示 3.2 三维形体的表示1.空间位置枚举表示空间位置枚举表示法将包含实体的空间分割为大小相同、形状规则（正方形或立方体）的体素，然后以体素的集合来表示图形对象。三维情况下，常用三维数组pijk来存放(当CIjk = 1时，表示对应的小立方体被物体占据;当CIjk = 0时，表示对应的小立方体没