计算机图形学第四章教案.pptVIP

第4章 图形表示与数据结构 提出问题 如何在计算机中建立恰当的模型表示不同图形对象 如何组织图形对象的描述数据以使存储这些数据所 要的空间最省，检索、处理这些数据的速度较快 Date1河北农业大学 张玉新 一般把研究如何在计算机中建立恰当的模型表示 不同图形对象的技术称为造型技术。 有两类图形对象： 规则对象：几何造型、几何模型 不规则对象： Date2河北农业大学 张玉新 4.1.1 基本图形元素与段的概念 4.1 基本概念 基本图形元素：图素或图元、体素。 图素是指可以用一定的几何参数和属性参数描述 的最基本的图形输出元素。例如点、线、圆等 Date3河北农业大学 张玉新 体素是三维空间中可以用有限个尺寸参数定位和定形的 体，常有三种定义形式： (1)从实际形体中选择出来，可用一些确定的尺寸参数 控制其最终位置和形状的一组单元实体 (2)由参数定义的一条(或一组)轮廓线沿一条(或一组)空 间参数曲线作扫描运动而产生的形体。 (3)用代数半空间定义的形体 Date4河北农业大学 张玉新 段（也称图段、结构和对象） 段是指具有逻辑意义的有限个图素（或体素）及其附 加属性的集合，是用基本图素或体素按照一定的结 构规则形成的。 Date5河北农业大学 张玉新 图素或体素用数据来描述，段用规则来描述。 段可以嵌套 段一般具有三个特性：可见性、醒目性、可选 择性。 Date6河北农业大学 张玉新 4.1.2 几何信息与拓扑信息 图形对象及构成它的点、线、面的位置、相互间关 系和几何尺寸等都是图形信息； 表示图形对象的线型、颜色、亮度以及供模拟、分 析用的质量、比重、体积等数据，是有关对象的非 图形信息。 Date7河北农业大学 张玉新 图形信息又包括： 几何信息：形体在欧氏空间中的位置和大小 拓扑信息：形体各分量（点、边、面）的数目及其相 互间的连接关系。 1. 几何信息 (1)几何分量的数学表示 Date8河北农业大学 张玉新 (2)几何分量之间的相互关系 Date9河北农业大学 张玉新 几何信息的二义性 2. 拓朴信息 平面立体的几何分量之间一共有九种拓扑关系 Date10河北农业大学 张玉新 面相邻性f:f 面-顶点包含性 f:v 面-边包含性f:e 顶点面相邻性v:f 顶点相邻性v:v 顶点-边相邻性v:e 边-面相邻性e:f 边-顶点包含性e:v 边相邻性e:e: f f f e e f f f f v e v v v e e e v v e f f e v v v f e e v v e e e e 图4-3 平面立体的九种拓扑关系 Date11河北农业大学 张玉新 刚体运动：不改变图形上任意两点间的距离，也不 改变图形的几何性质的运动。 拓扑运动：允许形体作弹性运动，即在拓扑关系中 ，对图形可随意地伸张扭曲。但图上各个点仍为不 同的点，决不允许把不同的点合并成一个点。 拓扑等价、拓扑性质 Date12河北农业大学 张玉新 4.1.3 坐标系 Date13河北农业大学 张玉新 建模(造型)坐标系：用来定义基本图素和图段，对于定义 的每一个形体和图素都具有各自的子坐标原点和长度单位 ，这样可以方便形体和图素的定义。这里定义的形体和图 素经调用可放在用户坐标系的指定位置。因此造型坐标系 又称为局部坐标系。而用户坐标系称为全局坐标系。 用户坐标系：又称为世界坐标系。用来定义用户整图或最高 层图形结构，用户可根据相应的情况选择相应的坐标系。 观察坐标系：可在用户坐标系的任何位置、任何方向定义。 有两个主要用途，一是用于指定裁剪空间，确定形体的哪一 部分要显示输出；二是通过定义观察(投影)平面，把三维形 体的用户坐标转换为规格化的设备坐标。 规格化的设备坐标系：用来定义视图区，其取值范围在0,1 之间，是GKS内部使用的规范设备坐标。 设备坐标系：是图形输入输出设备的坐标系。 Date14河北农业大学 张玉新 4.1.4 几何元素 点：是0维几何元素，分端点、交点、切点和孤立点等 。 在自由曲线面的描述中常用三种类型的点： 控制点、型值点、插值点 边：是1维几何元素，是两个邻面（正则形体）或多个 邻面（非正则形体）的交界。直线边、曲线边 Date15河北农业大学 张玉新 面：是2维几何元素，是形体上一个有限、非零的区 域，由一个外环和若干个内环界定其范围。 一个面可以无内环，但必须有一个且只有一个 外环。 面有方向性 Date16河北农业大学 张玉新 环是有序、有向边（直线段或曲线段）组成的面的封 闭边界。 环中的边不能相交，相邻两条边共享一个端点 确定面的最大外边界的环称之为外环 确定面中内孔或凸台边界的环称之为内环 在面上沿一个环前进，其左侧总是面内，右侧总是 面外。 Date17河北农业大学 张玉新 体是3维几何元素，由封闭表面围成空间，也是 欧氏空间中非空、有界的封闭子集，其边界是 有限面的并集。 Date18河北农业大学 张玉新 4.1.5 实体的定义 Date19河北农业大学 张玉新 客观存在的三维形体具有这样一些性质： (1)刚性：一个物体必须具有一定的形状。 (2)维数的一致性：各部分均应是三维的。 (3)占据有限的空间：即体积有限。 (4)边界的确定性：根据物体的边界能区别出物体的内部和外部。 (5)封闭性：经过一系列刚体运动仍为有效实体。 三维空间中的物体是一个内部连通的三维点集，是由其内部 的点集及紧紧包着这些点的表皮组成的。 Date20河北农业大学 张玉新 利用正则集的概念来定义上述的三维有效物体： 点的领域：如果P是点集S的一个元素，那么点P的以 R（R0）为半径的领域指的是围绕点P的半径为R 的小球（二维情况下为小圆）。 内点为点集中的这样一些点，它们具有完全包含于该 点集的充分小的领域。 边界点 Date21河北农业大学 张玉新 定义点集的正则运算r为： 正则运算即为先对物体取内点再取闭包的运算。rA 称为A的正则集。 Date22河北农业大学 张玉新 图4-7 正则形体 Date23河北农业大学 张玉新 二维流形指的是对于实体表面上的任意一点，都可 以找到一个围绕着它的任意小的领域，该领域与平 面上的一个圆盘是拓扑等价的。 Date24河北农业大学 张玉新 实体：对于一个占据有限空间的正则形体 ，如果其表面是二维流形，则该正则形体 为实体。 Date25河北农业大学 张玉新 4.1.6 正则集合运算 实际上就是利用有效实体的封闭性，即一个有效实体 经过一系列集合运算后仍为一个有效实体。 把能够产生正则形体的集合运算称为正则集合运算。其 相应的正则算子用* 、 *、*表示。 Date26河北农业大学 张玉新 Date27河北农业大学 张玉新 有两种方法实现正则运算 间接方式： 主要基于点集拓扑的领域概念，即集合S在点P附近的局部几何 性质： 当且仅当P的领域为满时，P在S之内； 当且仅当P的领域为空时，P在S之外； 当且仅当P的领域既不满也不空时，P在S的边界上。 利用这一性质就可对普通集合运算得到的结果进行检查。如图 Date28河北农业大学 张玉新 Date29河北农业大学 张玉新 直接方式：建立在集合成员分类的基础上。 在三维空间中，给定一个正则形体S，空间点集被分 为三个子集： S的内部点集 S的边界点集 S之外的点集 为了产生正则形体，需要决定一个特定的点集属于哪 一个子集，也就是集合成员分类问题。 Date30河北农业大学 张玉新 分类函数： 若给定一个正则形体S及一个有界面G，则G被S分割 为位于S内、位于S外、位于S边界上的面三部分，则 G相对于S的分类函数可为： C(S,G)=G in S, G out S, G on S 其中， Date31河北农业大学 张玉新 用-G表示有界面G的反向面。即，如果有界面G在P点的 法向为NP(G)，则有界面-G在P点的法向就是-NP(G)。 于是：G on S=G shared (bS), G shared (-bS) 其中， Date32河北农业大学 张玉新 则G相对于S的分类函数C(S,G)可为： C(S,G)=G in S, G out S, G shared (bS), G shared (-bS) 由于一个正则形体可由它的边界来表示，因此只需定 义三个正则集合算子关于边界面的表达式： B)(b- sharedA bA),in B(b- B,out A bB)-(Ab Bb sharedA bA,in Bb B,in A bB)(Ab Bb sharedA bA,out Bb B,out A bB)(Ab * * * =. =. =. Date33河北农业大学 张玉新 B)(b- sharedA bA),in B(b- B,out A bB)-(Ab Bb sharedA bA,in Bb B,in A bB)(Ab Bb sharedA bA,out Bb B,out A bB)(Ab * * * =. =. =. Date34河北农业大学 张玉新 4.1.7 平面多面体与欧拉公式 平面多面体是表面由平面多边形构成的三维物体。 简单多面体指与球拓扑等价的那些多面体。即经过连续的几何 形变可以变换成一个球的多面体。 欧拉公式证明简单多面体的顶点数V、边数E和面数F满足如下 关系：V-E+F=2。 Date35河北农业大学 张玉新 Date36河北农业大学 张玉新 对于非简单多面体：令H表示多面体表面上孔的个数，G表示 贯穿多面体的孔的个数，C表示独立的、不相连接的多面体 数，则扩展后的欧拉公式为：V-E+F-H=2（C-G） Date37河北农业大学 张玉新 线框模型 线框模型存在着几个缺陷： 二义性 4.2 三维形体的表示(造型) Date38河北农业大学 张玉新 容易构造出无效形体 Date39河北农业大学 张玉新 不能正确表示曲面信息。 Date40河北农业大学 张玉新 无法进行图形的线面消隐。 加重用户的输入负担 难以保证数据的统一性和有效性。 所以目前广泛应用的是三维形体的实体造型技术 Date41河北农业大学 张玉新 实体模型（实体造型技术） 可以将实体模型的表示大致分为三类： 边界表示（Boundary representation, B-reps） 扫描表示法 构造实体几何表示 空间分割（Space-partitioning）表示 Date42河北农业大学 张玉新 4.2.1 边界表示法 对于一个实体来说，只要定义了形体地边界，那么该实 体就被惟一定义了。 Date43河北农业大学 张玉新 边界表示法的一个重要特点就是其按照体面边点的层次 ，详细记录了构成形体的所有几何元素的几何信息及其相互连 接的拓扑关系。 拓扑信息描述形体上的顶点、边、面的连接关系，拓扑信息形 成物体边界表示的“骨架”。形体的几何信息犹如附着在“骨 架” 上的肌肉。 Date44河北农业大学 张玉新 2. 边界表示法中最典型的数据结构:翼边 结构表示（Winged Edges Structure）:以边为核心来组织数据 结构，它用指针记录了每一边的两个邻 面（即左外环和右外环）、两个顶点、 两侧各自相邻的两个邻边（即左上边、 左下边、右上边和右下边），用这一数 据结构表示实体模型是完备的。 Date45河北农业大学 张玉新 4.2.2 扫描表示（sweep representation） 扫描表示法（sweep representation）可以利用简 单的运动规则生成有效实体。 包含两个要素： 一是作扫描运动的基本图形；基面。 二是扫描运动的方式。 Date46河北农业大学 张玉新 扫描运动的方式有： 平移扫描法 旋转扫描法 广义扫描法 Date47河北农业大学 张玉新 4.2.3 构造实体几何法 构造实体几何法（CSG，Constructive Solid Geometry） 由两个实体间的并、交或差操作生成新的实体。 Date48河北农业大学 张玉新 在构造实体几何法中，集合运算的实现过程可以用一 棵二叉树（称为CSG树）来描述： 树的叶子 树的非终端结点 二叉树根结点 Date49河北农业大学 张玉新 构造实体几何法的优点： 数据结构较简单，数据量比较小。 每个CSG表示都和一个实际的有效实体相对应，可以构造出多种 不同的符合需要的实体。 比较容易修改CSG表示形体的形状 缺点： 基于集合运算对形体的局部操作不易实现 由于形体的几何元素是隐含在CSG中，故显示与绘制CSG表示的 形体需要较长的时间。 Date50河北农业大学 张玉新 4.2.4 空间位置枚举表示 空间位置枚举表示法将包含实体的空间分割为大 小相同、形状规则（正方形或立方体）的体素 ，然后，以体素的集合来表示图形对象。 二维情况，常用二维数组存放。 三维情况下，常用三维数组pijk来存放。 Date51河北农业大学 张玉新 4.2.5 八叉树 八叉树（octrees）又称为分层树结构，它对空间进行自 适应划分，采用具有层次结构的八叉树来表示实体。 三维实体的八叉树表示类似于二维平面图形的四叉树表 示。 Date52河北农业大学 张玉新 四叉树 Date53河北农业大学 张玉新 八叉树 Date54河北农业大学 张玉新 Date55河北农业大学 张玉新 4.2.6 BSP树 二叉空间分割（binary space partitioning，BSP） 方法每次将一实体用任一位置和任一方向的平面分 为二部分。 Date56河北农业大学 张玉新 4.3 非规则对象的表示 基于分数维理论的随机模型 基于文法的模型 粒子系统模型 Date57河北农业大学 张玉新 4.3.1 分形几何(fractal geometry)法 分形几何表示的物体具有一个基本特征：无限的自相似性。 无限的自相似性是指物体的整体和局部之间细节的无限重现 。 分形物体的描述又包含： 分形维数，又称分数维数 D= 生成过程：初始生成元（initiator）、生成元（genenator ） Log N Log(1/S) 其中N为每一步细分的数目 ，S为细分时的放大倍数 Date58河北农业大学 张玉新 4.3.2 形状语法 形状语法（shape grammars）：给定一组产生式规则 ，形状设计者可以在从给定初始物体到最终物体结构 的每一次变换中应用不同的规则。 该方法主要是用于为模拟植物而引入的。 Date59河北农业大学 张玉新 4.3.3 微粒系统 用于模拟自然景物或模拟其它非规则形状物 体展示“流体”性质的一个方法是微粒系统（ particle systems）。 这一方法尤其擅长描述随时间变化的物体 。 Date60河北农业大学 张玉新 4.3.4 基于物理的建