计算机图形学第四章教案课件.ppt

《计算机图形学第四章教案课件.ppt》由会员分享，可在线阅读，更多相关《计算机图形学第四章教案课件.ppt（67页珍藏版）》请在三一办公上搜索。

1、2022/12/10,河北农业大学 张玉新,1,第4章 图形表示与数据结构,提出问题,如何在计算机中建立恰当的模型表示不同图形对象如何组织图形对象的描述数据以使存储这些数据所要的空间最省，检索、处理这些数据的速度较快,2022/12/10,河北农业大学 张玉新,2,一般把研究如何在计算机中建立恰当的模型表示不同图形对象的技术称为造型技术。有两类图形对象：规则对象：几何造型、几何模型不规则对象：,2022/12/10,河北农业大学 张玉新,3,4.1.1 基本图形元素与段的概念,4.1 基本概念,基本图形元素：图素或图元、体素。图素是指可以用一定的几何参数和属性参数描述的最基本的图形输出元素。例

2、如点、线、圆等,2022/12/10,河北农业大学 张玉新,4,体素是三维空间中可以用有限个尺寸参数定位和定形的体，常有三种定义形式： (1)从实际形体中选择出来，可用一些确定的尺寸参数控制其最终位置和形状的一组单元实体(2)由参数定义的一条(或一组)轮廓线沿一条(或一组)空间参数曲线作扫描运动而产生的形体。(3)用代数半空间定义的形体,2022/12/10,河北农业大学 张玉新,5,段（也称图段、结构和对象）段是指具有逻辑意义的有限个图素（或体素）及其附加属性的集合，是用基本图素或体素按照一定的结构规则形成的。,2022/12/10,河北农业大学 张玉新,6,图素或体素用数据来描述，段用规则

3、来描述。段可以嵌套段一般具有三个特性：可见性、醒目性、可选择性。,2022/12/10,河北农业大学 张玉新,7,4.1.2 几何信息与拓扑信息,图形对象及构成它的点、线、面的位置、相互间关系和几何尺寸等都是图形信息；表示图形对象的线型、颜色、亮度以及供模拟、分析用的质量、比重、体积等数据，是有关对象的非图形信息。,2022/12/10,河北农业大学 张玉新,8,图形信息又包括：几何信息：形体在欧氏空间中的位置和大小拓扑信息：形体各分量（点、边、面）的数目及其相互间的连接关系。 1. 几何信息 (1)几何分量的数学表示,2022/12/10,河北农业大学 张玉新,9,(2)几何分量之间的相互关

4、系,2022/12/10,河北农业大学 张玉新,10,几何信息的二义性,2. 拓朴信息平面立体的几何分量之间一共有九种拓扑关系,2022/12/10,河北农业大学 张玉新,11,2022/12/10,河北农业大学 张玉新,12,刚体运动：不改变图形上任意两点间的距离，也不改变图形的几何性质的运动。拓扑运动：允许形体作弹性运动，即在拓扑关系中，对图形可随意地伸张扭曲。但图上各个点仍为不同的点，决不允许把不同的点合并成一个点。拓扑等价、拓扑性质,2022/12/10,河北农业大学 张玉新,13,4.1.3 坐标系,2022/12/10,河北农业大学 张玉新,14,建模(造型)坐标系：用来定义基本图

5、素和图段，对于定义的每一个形体和图素都具有各自的子坐标原点和长度单位，这样可以方便形体和图素的定义。这里定义的形体和图素经调用可放在用户坐标系的指定位置。因此造型坐标系又称为局部坐标系。而用户坐标系称为全局坐标系。,用户坐标系：又称为世界坐标系。用来定义用户整图或最高层图形结构，用户可根据相应的情况选择相应的坐标系。,观察坐标系：可在用户坐标系的任何位置、任何方向定义。有两个主要用途，一是用于指定裁剪空间，确定形体的哪一部分要显示输出；二是通过定义观察(投影)平面，把三维形体的用户坐标转换为规格化的设备坐标。,规格化的设备坐标系：用来定义视图区，其取值范围在0,1之间，是GKS内部使用的规范设

6、备坐标。,设备坐标系：是图形输入输出设备的坐标系。,2022/12/10,河北农业大学 张玉新,15,4.1.4 几何元素,点：是0维几何元素，分端点、交点、切点和孤立点等。在自由曲线面的描述中常用三种类型的点：控制点、型值点、插值点 边：是1维几何元素，是两个邻面（正则形体）或多个邻面（非正则形体）的交界。直线边、曲线边,2022/12/10,河北农业大学 张玉新,16,面：是2维几何元素，是形体上一个有限、非零的区域，由一个外环和若干个内环界定其范围。一个面可以无内环，但必须有一个且只有一个外环。面有方向性,2022/12/10,河北农业大学 张玉新,17,环是有序、有向边（直线段或曲线段

7、）组成的面的封闭边界。环中的边不能相交，相邻两条边共享一个端点确定面的最大外边界的环称之为外环确定面中内孔或凸台边界的环称之为内环在面上沿一个环前进，其左侧总是面内，右侧总是面外。,2022/12/10,河北农业大学 张玉新,18,体是3维几何元素，由封闭表面围成空间，也是欧氏空间中非空、有界的封闭子集，其边界是有限面的并集。,2022/12/10,河北农业大学 张玉新,19,4.1.5 实体的定义,2022/12/10,河北农业大学 张玉新,20,客观存在的三维形体具有这样一些性质：(1)刚性：一个物体必须具有一定的形状。(2)维数的一致性：各部分均应是三维的。(3)占据有限的空间：即体积有

8、限。(4)边界的确定性：根据物体的边界能区别出物体的内部和外部。(5)封闭性：经过一系列刚体运动仍为有效实体。三维空间中的物体是一个内部连通的三维点集，是由其内部的点集及紧紧包着这些点的表皮组成的。,2022/12/10,河北农业大学 张玉新,21,利用正则集的概念来定义上述的三维有效物体：点的领域：如果P是点集S的一个元素，那么点P的以R（R0）为半径的领域指的是围绕点P的半径为R的小球（二维情况下为小圆）。内点为点集中的这样一些点，它们具有完全包含于该点集的充分小的领域。边界点,2022/12/10,河北农业大学 张玉新,22,定义点集的正则运算r为：,正则运算即为先对物体取内点再取闭包的

9、运算。rA称为A的正则集。,2022/12/10,河北农业大学 张玉新,23,2022/12/10,河北农业大学 张玉新,24,二维流形指的是对于实体表面上的任意一点，都可以找到一个围绕着它的任意小的领域，该领域与平面上的一个圆盘是拓扑等价的。,2022/12/10,河北农业大学 张玉新,25,实体：对于一个占据有限空间的正则形体，如果其表面是二维流形，则该正则形体为实体。,2022/12/10,河北农业大学 张玉新,26,4.1.6 正则集合运算,实际上就是利用有效实体的封闭性，即一个有效实体经过一系列集合运算后仍为一个有效实体。 把能够产生正则形体的集合运算称为正则集合运算。其相应的正则算

10、子用* 、 *、*表示。,2022/12/10,河北农业大学 张玉新,27,2022/12/10,河北农业大学 张玉新,28,有两种方法实现正则运算间接方式：主要基于点集拓扑的领域概念，即集合S在点P附近的局部几何性质：当且仅当P的领域为满时，P在S之内；当且仅当P的领域为空时，P在S之外；当且仅当P的领域既不满也不空时，P在S的边界上。 利用这一性质就可对普通集合运算得到的结果进行检查。如图,2022/12/10,河北农业大学 张玉新,29,2022/12/10,河北农业大学 张玉新,30,直接方式：建立在集合成员分类的基础上。在三维空间中，给定一个正则形体S，空间点集被分为三个子集：S的内

11、部点集S的边界点集S之外的点集为了产生正则形体，需要决定一个特定的点集属于哪一个子集，也就是集合成员分类问题。,2022/12/10,河北农业大学 张玉新,31,分类函数： 若给定一个正则形体S及一个有界面G，则G被S分割为位于S内、位于S外、位于S边界上的面三部分，则G相对于S的分类函数可为： C(S,G)=G in S, G out S, G on S 其中，,2022/12/10,河北农业大学 张玉新,32,用-G表示有界面G的反向面。即，如果有界面G在P点的法向为NP(G)，则有界面-G在P点的法向就是-NP(G)。于是：G on S=G shared (bS), G shared (

12、-bS)其中，,2022/12/10,河北农业大学 张玉新,33,则G相对于S的分类函数C(S,G)可为：C(S,G)=G in S, G out S, G shared (bS), G shared (-bS)由于一个正则形体可由它的边界来表示，因此只需定义三个正则集合算子关于边界面的表达式：,2022/12/10,河北农业大学 张玉新,34,2022/12/10,河北农业大学 张玉新,35,4.1.7 平面多面体与欧拉公式,平面多面体是表面由平面多边形构成的三维物体。简单多面体指与球拓扑等价的那些多面体。即经过连续的几何形变可以变换成一个球的多面体。欧拉公式证明简单多面体的顶点数V、边数E

13、和面数F满足如下关系：V-E+F=2。,2022/12/10,河北农业大学 张玉新,36,2022/12/10,河北农业大学 张玉新,37,对于非简单多面体：令H表示多面体表面上孔的个数，G表示贯穿多面体的孔的个数，C表示独立的、不相连接的多面体数，则扩展后的欧拉公式为：V-E+F-H=2（C-G）,2022/12/10,河北农业大学 张玉新,38,线框模型线框模型存在着几个缺陷：二义性,4.2 三维形体的表示(造型),2022/12/10,河北农业大学 张玉新,39,容易构造出无效形体,2022/12/10,河北农业大学 张玉新,40,不能正确表示曲面信息。,2022/12/10,河北农业大

14、学 张玉新,41,无法进行图形的线面消隐。加重用户的输入负担难以保证数据的统一性和有效性。,所以目前广泛应用的是三维形体的实体造型技术,2022/12/10,河北农业大学 张玉新,42,实体模型（实体造型技术）可以将实体模型的表示大致分为三类：边界表示（Boundary representation, B-reps）扫描表示法构造实体几何表示空间分割（Space-partitioning）表示,2022/12/10,河北农业大学 张玉新,43,4.2.1 边界表示法,对于一个实体来说，只要定义了形体地边界，那么该实体就被惟一定义了。,2022/12/10,河北农业大学 张玉新,44,边界表示法

15、的一个重要特点就是其按照体面边点的层次，详细记录了构成形体的所有几何元素的几何信息及其相互连接的拓扑关系。拓扑信息描述形体上的顶点、边、面的连接关系，拓扑信息形成物体边界表示的“骨架”。形体的几何信息犹如附着在“骨架”上的肌肉。,2022/12/10,河北农业大学 张玉新,45,2. 边界表示法中最典型的数据结构:翼边结构表示（Winged Edges Structure）:以边为核心来组织数据结构，它用指针记录了每一边的两个邻面（即左外环和右外环）、两个顶点、两侧各自相邻的两个邻边（即左上边、左下边、右上边和右下边），用这一数据结构表示实体模型是完备的。,2022/12/10,河北农业大学

16、张玉新,46,4.2.2 扫描表示（sweep representation）,扫描表示法（sweep representation）可以利用简单的运动规则生成有效实体。包含两个要素：一是作扫描运动的基本图形；基面。二是扫描运动的方式。,2022/12/10,河北农业大学 张玉新,47,扫描运动的方式有：平移扫描法旋转扫描法广义扫描法,2022/12/10,河北农业大学 张玉新,48,4.2.3 构造实体几何法,构造实体几何法（CSG，Constructive Solid Geometry）由两个实体间的并、交或差操作生成新的实体。,2022/12/10,河北农业大学 张玉新,49,在构造实体

17、几何法中，集合运算的实现过程可以用一棵二叉树（称为CSG树）来描述：树的叶子树的非终端结点二叉树根结点,2022/12/10,河北农业大学 张玉新,50,构造实体几何法的优点：数据结构较简单，数据量比较小。每个CSG表示都和一个实际的有效实体相对应，可以构造出多种不同的符合需要的实体。比较容易修改CSG表示形体的形状缺点：基于集合运算对形体的局部操作不易实现由于形体的几何元素是隐含在CSG中，故显示与绘制CSG表示的形体需要较长的时间。,2022/12/10,河北农业大学 张玉新,51,4.2.4 空间位置枚举表示,空间位置枚举表示法将包含实体的空间分割为大小相同、形状规则（正方形或立方体）的

18、体素，然后，以体素的集合来表示图形对象。二维情况，常用二维数组存放。三维情况下，常用三维数组pijk来存放。,2022/12/10,河北农业大学 张玉新,52,4.2.5 八叉树,八叉树（octrees）又称为分层树结构，它对空间进行自适应划分，采用具有层次结构的八叉树来表示实体。三维实体的八叉树表示类似于二维平面图形的四叉树表示。,2022/12/10,河北农业大学 张玉新,53,四叉树,2022/12/10,河北农业大学 张玉新,54,八叉树,2022/12/10,河北农业大学 张玉新,55,2022/12/10,河北农业大学 张玉新,56,4.2.6 BSP树,二叉空间分割（binary

19、 space partitioning，BSP）方法每次将一实体用任一位置和任一方向的平面分为二部分。,2022/12/10,河北农业大学 张玉新,57,4.3 非规则对象的表示,基于分数维理论的随机模型基于文法的模型粒子系统模型,2022/12/10,河北农业大学 张玉新,58,4.3.1 分形几何(fractal geometry)法,分形几何表示的物体具有一个基本特征：无限的自相似性。无限的自相似性是指物体的整体和局部之间细节的无限重现。分形物体的描述又包含：分形维数，又称分数维数 D=生成过程：初始生成元（initiator）、生成元（genenator）,Log N,Log(1/S)

20、,其中N为每一步细分的数目，S为细分时的放大倍数,2022/12/10,河北农业大学 张玉新,59,4.3.2 形状语法,形状语法（shape grammars）：给定一组产生式规则，形状设计者可以在从给定初始物体到最终物体结构的每一次变换中应用不同的规则。该方法主要是用于为模拟植物而引入的。,2022/12/10,河北农业大学 张玉新,60,4.3.3 微粒系统,用于模拟自然景物或模拟其它非规则形状物体展示“流体”性质的一个方法是微粒系统（particle systems）。这一方法尤其擅长描述随时间变化的物体。,2022/12/10,河北农业大学 张玉新,61,4.3.4 基于物理的建模,

21、基于物理的建模方法：描述了物体在内外力相互作用下的行为。通常用一组网格结点来逼近物体。网格结点间取为柔性连接(模型是弹簧)，再考虑贯穿物体网格的力传递。基于力学方程的动画描述比基于运动学方程的描述产生的运动更真实。实例,2022/12/10,河北农业大学 张玉新,62,4.4 图形的层次结构,2022/12/10,河北农业大学 张玉新,63,利用层次结构的优点：,一是存储简单。二是编辑简单。,2022/12/10,河北农业大学 张玉新,64,4.4.2 层次结构的实现,系统的层次式模型可通过将一个图段嵌套到另一个图段中形成树形图段来创建。在层次结构中，需要将在建模坐标系中定义的基本图素和段放在

22、用户坐标系中来建立引用。,2022/12/10,河北农业大学 张玉新,65,习题,1名词解释：造型技术、规则对象、不规则对象、图素、体素、段、刚体运动、拓扑运动、拓扑等价、坐标系、点、二维流形、非二维流形、构造实体几何法、空间位置枚举法、八叉树、BSP树、无限自相似性,2022/12/10,河北农业大学 张玉新,66,2利用正则集的概念简述实体的定义。3用间接方式如何实现正则集合运算，用直接方式呢？4简单多面体的欧拉公式满足何条件？复杂多面体的呢？5简述三维形体的扫描表示方法。6简述如何利用CSG树来表示三维形体。,2022/12/10,河北农业大学 张玉新,67,7举例说明如何用八叉树表示三维形体。8描述不规则物体都有那些方法？特点？9图形系统中为什么要建立图形对象的层次结构。,