《计算机图形学 第3章 图形的表示与数据结构》由会员分享，可在线阅读，更多相关《计算机图形学 第3章 图形的表示与数据结构（52页珍藏版）》请在金锄头文库上搜索。
1、1第第3 3章章 图形的表示与数据结构图形的表示与数据结构提出问题提出问题基本概念如何在计算机中建立恰当的模型表示不同图形对象2造型技术：造型技术：研究如何在计算机中建立恰当的模型表示不同图形对象的技术。有两类图形对象：规则对象：能用欧氏几何进行描述的形体。规则对象：能用欧氏几何进行描述的形体。不规则对象：不能用欧氏几何进行描述的形体。不规则对象：不能用欧氏几何进行描述的形体。第第3章章 图形的表示与数据结构图形的表示与数据结构 引言引言引言引言33 3.1.1 .1.1 基本图形元素与段的概念基本图形元素与段的概念基本图形元素：基本图形元素：图素或图元、体素图图素素：是指可以用一定的几何参数
2、和属性参数描述的最基本的图形输出元素。体体素素：是三维空间中可以用有限个尺寸参数定位和定形的体。第3章 图形的表示与数据结构 3 3 3 3.1 .1 .1 .1 基本概念基本概念基本概念基本概念4段（段（也称图段、结构和对象）段段是指具有逻辑意义的有限个图素（或体素）及其附加属性的集合。第3章 图形的表示与数据结构 3 3 3 3.1 .1 .1 .1 基本概念基本概念基本概念基本概念段的特点：段的特点：图素或体素用数据来描述，段用规则来描述。段可以嵌套段一般具有三个特性：可见性、醒目性、可选择性。53.1.2 几何信息与拓扑信息几何信息与拓扑信息图形对象及构成它的点、线、面的位置、相互间关
3、系和几何尺寸等都是图形信息图形信息；表示图形对象的线型、颜色、亮度以及供模拟、分析用的质量、比重、体积等数据，是有关对象的非图形信息非图形信息。第3章 图形的表示与数据结构 3 3 3 3.1 .1 .1 .1 基本概念基本概念基本概念基本概念6图形信息又包括：几何信息：几何信息：形体在欧氏空间中的位置和大小。拓拓扑扑信信息息：形体各分量（点、边、面）的数目及其相互间的连接关系。 第3章 图形的表示与数据结构 3 3 3 3.1 .1 .1 .1 基本概念基本概念基本概念基本概念刚刚体体运运动动：不改变图形上任意两点间的距离，也不改变图形的几何性质的运动。拓拓扑扑运运动动：允许形体作弹性运动，
4、即在拓扑关系中，对图形可随意地伸张扭曲。但图上各个点仍为不同的点，决不允许把不同的点合并成一个点。72. 2. 拓朴信息拓朴信息（平面立体的几何分量之间一共有九种拓扑关系）第3章 图形的表示与数据结构 3 3 3 3.1 .1 .1 .1 基本概念基本概念基本概念基本概念83.1.3 坐标系坐标系第3章 图形的表示与数据结构 3 3 3 3.1 .1 .1 .1 基本概念基本概念基本概念基本概念93.1.4 几何元素几何元素点点: :是0维几何元素，分端点、交点、切点和孤立点等。控制点、型值点、插值点控制点、型值点、插值点 第4章 图形的表示与数据结构 3 3 3 3. . . .1 1 1
5、1 基本概念基本概念基本概念基本概念边边: :是1维几何元素，是两个邻面（正则形体）或多个邻面（非正则形体）的交界。直线边直线边, ,曲线边曲线边10环环：是有序、有向边（直线段或曲线段）组成的面的封闭边界。环中的边不能相交，相邻两条边共享一个端点确定面的最大外边界的环称之为外环外环确定面中内孔或凸台边界的环称之为内环内环在面上沿一个环前进，其左侧总是面内，右侧总是面外。（外环为逆时针）第3章 图形的表示与数据结构 3 3 3 3.1 .1 .1 .1 基本概念基本概念基本概念基本概念11体体：是3维几何元素，由封闭表面围成空间，也是欧氏空间R3中非空、有界的封闭子集，其边界是有限面的并集。第
6、3章 图形的表示与数据结构3 3.1 .1 .1 .1 基本概念基本概念基本概念基本概念面面：是2维几何元素，是形体上一个有限、非零的区域，由一个外环和若干个内环界定其范围。n一个面可以无内环，但必须有一个且只有一个外环。n面有方向性，一般以外法矢作为面的正向。123.1.5 实体的定义实体的定义第3章 图形的表示与数据结构 4.1 4.1 4.1 4.1 基本概念基本概念基本概念基本概念带有悬挂面的立方体13客观存在的三维形体具有这样一些性质客观存在的三维形体具有这样一些性质：(1)刚性(2)维数的一致性(3)占据有限的空间(4)边界的确定性(5)封闭性 三三维维空空间间中中的的物物体体：是
7、一个内部连通的三维点集，是由其内部的点集及紧紧包着这些点的表皮组成的。第3章 图形的表示与数据结构 3 3 3 3.1 .1 .1 .1 基本概念基本概念基本概念基本概念14利用利用正则集正则集的概念来定义上述的三维有效物体的概念来定义上述的三维有效物体：点点的的领领域域：如果P是点集S的一个元素，那么点P的以R（R0）为半径的领域指的是围绕点P的半径为R的小球（二维情况下为小圆）。内内点点：为点集中的这样一些点，它们具有完全包含于该点集的充分小的领域。边界点：边界点：不具有上述性质的点集中的点。第3章 图形的表示与数据结构 3 3 3 3.1 .1 .1 .1 基本概念基本概念基本概念基本概
8、念15定义点集的正则运算r运算为：正则运算即为先对物体取内点再取闭包的运算。rA称为A的正则集正则集。三维空间的正则集就是正则形体正则形体。 第3章 图形的表示与数据结构 3 3 3 3.1 .1 .1 .1 基本概念基本概念基本概念基本概念16第3章 图形的表示与数据结构 3 3 3 3.1 .1 .1 .1 基本概念基本概念基本概念基本概念正则形体17二二维维流流形形：指的是对于实体表面上的任意一点，都可以找到一个围绕着它的任意小的领域，该领域与平面上的一个圆盘是拓扑等价的。 第3章 图形的表示与数据结构 3 3 3 3.1 .1 .1 .1 基本概念基本概念基本概念基本概念正则形体18实
9、实体体：对对于于一一个个占占据据有有限限空空间间的的正正则则形形体体，如如果果其其表表面面是是二维流形，则该正则形体为实体二维流形，则该正则形体为实体。 第3章 图形的表示与数据结构 3 3 3 3.1 .1 .1 .1 基本概念基本概念基本概念基本概念193.1.6 正则集合运算正则集合运算有效实体的封封闭闭性性：一个有效的实体经过一系列的集合运算之后仍为一个有效实体。 把能够产生正则形体的集合运算称为正则集合运算正则集合运算第3章 图形的表示与数据结构 3 3 3 3.1 .1 .1 .1 基本概念基本概念基本概念基本概念20第3章 图形的表示与数据结构 3 3 3 3.1 .1 .1 .
10、1 基本概念基本概念基本概念基本概念正则集合运算21间接方式：基于点集拓扑的领域概念间接方式：基于点集拓扑的领域概念 当且仅当P的领域为满时，P在S之内；当且仅当P的领域为空时，P在S之外；当且仅当P的领域既不满也不空时，P在S的边界上。第3章 图形的表示与数据结构 3 3 3 3.1 .1 .1 .1 基本概念基本概念基本概念基本概念22第3章 图形的表示与数据结构3 3.1 .1 .1 .1 基本概念基本概念基本概念基本概念直接方式：基于集合成员分类直接方式：基于集合成员分类23数据模型数据模型完全以数据描述进一步分为线框模型表面模型实体模型过程模型过程模型以一个过程和相应的控制参数描述例
11、如：用一些控制参数和一个生成规则描述的植物以一个数据文件和一段代码的形式存在包括-粒子系统、L系统第3章 图形的表示与数据结构3 3.2 .2 .2 .2 三维形体的表示三维形体的表示三维形体的表示三维形体的表示24线框模型线框模型将形体表示成一组轮廓线的集合简单、处理速度快与形体之间不存在一一对应关系，是真实物体的高度抽象由于其不具有面和体的信息，因此不能进行消隐、着色和渲染处理 第3章 图形的表示与数据结构 3 3 3 3.2 .2 .2 .2 三维形体的表示三维形体的表示三维形体的表示三维形体的表示25表面模型表面模型将形体表示成一组表面的集合形体与其表面一一对应，适合于真实感显示但其没
12、有实体的信息，如空心的气球和实心的铅球在表面模型描述下是相同的第3章 图形的表示与数据结构 3 3 3 3.2 .2 .2 .2 三维形体的表示三维形体的表示三维形体的表示三维形体的表示26第3章 图形的表示与数据结构 3 3 3 3.2 .2 .2 .2 三维形体的表示三维形体的表示三维形体的表示三维形体的表示27实体模型实体模型（实体造型技术）可以将实体模型的表示大致分为三类：边界表示（Boundary representation, B-reps）构造实体几何表示（Constructive Solid Geometry, CSG）空间分割表示（Space-partitioning）第3章
13、 图形的表示与数据结构3 3.2 .2 .2 .2 三维形体的表示三维形体的表示三维形体的表示三维形体的表示283.2.1 多边形表面模型多边形表面模型边界表示(B-reps)的最普遍方式是多多边边形形表表面面模模型型，它使用一组包围物体内部的平面多边形，也即平面多面体，来描述实体。第3章 图形的表示与数据结构 3 3 3 3.2 .2 .2 .2 三维形体的表示三维形体的表示三维形体的表示三维形体的表示四面体以及点、线、面、体的关系29多边形表多边形表几何表几何表：顶点表顶点表、边表边表和多边形表多边形表。属性表属性表 第3章 图形的表示与数据结构 3 3 3 3.2 .2 .2 .2 三维
14、形体的表示三维形体的表示三维形体的表示三维形体的表示拓扑信息：拓扑信息：翼边结构表示翼边结构表示（Winged Edges Structure）30第3章 图形的表示与数据结构 3 3 3 3.2 .2 .2 .2 三维形体的表示三维形体的表示三维形体的表示三维形体的表示多边形网格多边形网格三维形体的曲面边界通常用多边形网格（polygon mesh）的拼接来模拟。( 三角形带三角形带 、 四边形网格四边形网格) )31第3章 图形的表示与数据结构 3 3 3 3.2 .2 .2 .2 三维形体的表示三维形体的表示三维形体的表示三维形体的表示多边形网格多边形网格三维形体的曲面边界通常用多边形网
15、格（polygon mesh）的拼接来模拟。( 三角形带三角形带 、 四边形网格四边形网格) )32第3章 图形的表示与数据结构 3 3 3 3.2 .2 .2 .2 三维形体的表示三维形体的表示三维形体的表示三维形体的表示多边形网格多边形网格三维形体的曲面边界通常用多边形网格（polygon mesh）的拼接来模拟。( 三角形带三角形带 、 四边形网格四边形网格) )333.2.2 扫描表示（扫描表示（sweep representation）将空间中的一个点、一条边或一个面沿某一路径扫描时，所形成的轨迹将定义一个一维的、二维的或三维的实体。包含两个要素包含两个要素：一是作扫描运动的基本图形
16、；二是扫描运动的方式。 第3章 图形的表示与数据结构 3 3 3 3.2 .2 .2 .2 三维形体的表示三维形体的表示三维形体的表示三维形体的表示34扫描运动的方式有：旋转扫描非圆形路径扫描广义扫描法第3章 图形的表示与数据结构 3 3 3 3.2 .2 .2 .2 三维形体的表示三维形体的表示三维形体的表示三维形体的表示35第3章 图形的表示与数据结构 3 3 3 3.2 .2 .2 .2 三维形体的表示三维形体的表示三维形体的表示三维形体的表示363.2.3 构造实体几何法构造实体几何法构造实体几何法（构造实体几何法（CSGCSG，Constructive Solid GeometryC
17、onstructive Solid Geometry）由两个实体间的并、交或差操作生成新的实体。第3章 图形的表示与数据结构 3 3 3 3.2 .2 .2 .2 三维形体的表示三维形体的表示三维形体的表示三维形体的表示构造实体几何37在构造实体几何法中，集合运算的实现过程可以用一棵二叉树（称为二叉树（称为CSGCSG树）树）来描述：树的叶子树的叶子树的非终端结点树的非终端结点二叉树根结点二叉树根结点第3章 图形的表示与数据结构 3 3 3 3.2 .2 .2 .2 三维形体的表示三维形体的表示三维形体的表示三维形体的表示38第3章 图形的表示与数据结构 3 3 3 3.2 .2 .2 .2
18、三维形体的表示三维形体的表示三维形体的表示三维形体的表示393.2.4 空间位置枚举表示空间位置枚举表示将包含实体的空间分割为大小相同、形状规则（正方形或立方体）的体素，然后，以体素的集合来表示图形对象。用三维数组PIJK表示物体，数组中的元素与单位小立方体一一对应第3章 图形的表示与数据结构 3 3 3 3.2 .2 .2 .2 三维形体的表示三维形体的表示三维形体的表示三维形体的表示当PIJK = 1时，表示对应的小立方体被物体占据当PIJK = 0时，表示对应的小立方体没有被物体占据403.2.5 八叉树八叉树八八叉叉树树（octreesoctrees）又称为分层树结构，它对空间进行自适
19、应划分，采用具有层次结构的八叉树来表示实体。第4章 图形的表示与数据结构 4.2 4.2 4.2 4.2 三维形体的表示三维形体的表示三维形体的表示三维形体的表示41四叉树四叉树第3章 图形的表示与数据结构 3 3 3 3.2 .2 .2 .2 三维形体的表示三维形体的表示三维形体的表示三维形体的表示四叉树423.2.6 BSP树树 二二叉叉空空间间分分割割（binary binary space space partitioningpartitioning，BSPBSP）方方法法每次将一实体用任一位置和任一方向的平面分为二部分。第3章 图形的表示与数据结构 3 3 3 3.2 .2 .2 .
20、2 三维形体的表示三维形体的表示三维形体的表示三维形体的表示43基于分数维理论的随机模型基于分数维理论的随机模型基于文法的模型基于文法的模型粒子系统模型粒子系统模型第3章 图形的表示与数据结构 3 3 3 3.3 .3 .3 .3 非规则对象的表示非规则对象的表示非规则对象的表示非规则对象的表示443.3.1 分形几何分形几何(fractalgeometry)分形几何物体具有一个基本特征：无限的自相似性。无限的自相似性无限的自相似性是指物体的整体和局部之间细节的无限重现。第3章 图形的表示与数据结构 3 3 3 3.3 .3 .3 .3 非规则对象的表示非规则对象的表示非规则对象的表示非规则对
21、象的表示分形物体的描述又包含：分形维数，又称分数维数生成过程：初始生成元初始生成元( (initiator)initiator)、生成元生成元( (generator)generator)453.3.2 形状语法形状语法形形状状语语法法（shape shape grammarsgrammars）：给定一组产生式规则，形状设计者可以在从给定初始物体到最终物体结构的每一次变换中应用不同的规则。第3章 图形的表示与数据结构 3 3 3 3.3 .3 .3 .3 非规则对象的表示非规则对象的表示非规则对象的表示非规则对象的表示46L L语法：语法：例子-Koch 雪花曲线几何解释F：向前画一条线+：右
22、转-：左转第3章 图形的表示与数据结构 3 3 3 3.3 .3 .3 .3 非规则对象的表示非规则对象的表示非规则对象的表示非规则对象的表示473.3.3 微粒系统微粒系统用于模拟自然景物或模拟其它非规则形状物体展示“流 体 ”性 质 的 一 个 方 法 是 微微 粒粒 系系 统统 （ particle particle systemssystems）。这一方法尤其擅长描述随时间变化的物体。微粒运动的模拟方式：随机过程模拟、运动路径模拟、力学模拟第3章 图形的表示与数据结构 3 3 3 3.3 .3 .3 .3 非规则对象的表示非规则对象的表示非规则对象的表示非规则对象的表示483.3.4
23、基于物理的建模基于物理的建模基于物理的建模方法：基于物理的建模方法：描述了物体在内外力相互作用下的行为。通常用一组网格结点来逼近物体。网格结点间取为柔性连接，再考虑贯穿物体网格的力传递。基于力学方程的动画描述比基于运动学方程的描述产生的运动更真实。第3章 图形的表示与数据结构 3 3 3 3.3 .3 .3 .3 非规则对象的表示非规则对象的表示非规则对象的表示非规则对象的表示493.3.5 数据场的可视化数据场的可视化科科学学计计算算可可视视化化（scientific visualization）指的是运用计算机图形学和图象处理技术，将科学计算过程中及计算结果的数据转换为图形及图象在屏幕上显
24、示出来并进行交互处理的理论、方法和技术。第3章 图形的表示与数据结构 3 3 3 3.3 .3 .3 .3 非规则对象的表示非规则对象的表示非规则对象的表示非规则对象的表示503.4.1 段的层次概念段的层次概念第3章 图形的表示与数据结构 3 3 3 3.4 .4 .4 .4 图形的层次结构图形的层次结构图形的层次结构图形的层次结构由直线、举行等图素和门、窗等图段组成的楼房513.4.2 层次结构的实现层次结构的实现层层次次结结构构的的实实现现：可通过将一个图段嵌套到另一个图段中形成树形图段来创建。层次结构的特点：层次结构的特点：n存储简单：一个段虽然在图中各处出现，但他的几何和拓扑信息只要保存一次。n编辑简单：删除、移动及缩放操作都可以以段为单位。第3章 图形的表示与数据结构 3 3 3 3.4 .4 .4 .4 图形的层次结构图形的层次结构图形的层次结构图形的层次结构52层：层：它把功能相同的部分归类，并把它们绘在一层上。不同的层可用不同的颜色及线型。不同层可一起显示，也可任挑几个层来显示。层不再嵌套。 第3章 图形的表示与数据结构 3 3 3 3.4 .4 .4 .4 图形的层次结构图形的层次结构图形的层次结构图形的层次结构
