计算机图形学图形的表示与数据结构.ppt

《计算机图形学图形的表示与数据结构.ppt》由会员分享，可在线阅读，更多相关《计算机图形学图形的表示与数据结构.ppt（98页珍藏版）》请在第壹文秘上搜索。

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

2、义实体的定义o 正则集合运算正则集合运算o 欧拉公式欧拉公式4.1 4.1 基本概念基本概念4o 把研究如何在计算机中建立恰当的模型表示不把研究如何在计算机中建立恰当的模型表示不同图形对象的技术称为造型技术。同图形对象的技术称为造型技术。o 有两类图形对象：有两类图形对象： 规则对象：几何造型、几何模型规则对象：几何造型、几何模型(几何信几何信息和拓扑信息息和拓扑信息)。 不规则对象：过程式模拟。不规则对象：过程式模拟。基本概念基本概念造型技术造型技术5基本概念基本概念基本图形元素基本图形元素p 基本图形元素基本图形元素：图素或图元、体素。：图素或图元、体素。p 图素图素是指可以用一定的几何参

3、数和属性参数描是指可以用一定的几何参数和属性参数描述的最基本的图形输出元素（包括点、线、面述的最基本的图形输出元素（包括点、线、面、环、体等）。、环、体等）。p 在二维图形系统中将基本图形元素称为图素或在二维图形系统中将基本图形元素称为图素或图元，在三维图形系统中称为体素。图元，在三维图形系统中称为体素。o 1、点：为、点：为0维几何元素，是形体最基本的元素，自由曲维几何元素，是形体最基本的元素，自由曲线、曲面或其他形体均可用有序的点集来表示。点集及线、曲面或其他形体均可用有序的点集来表示。点集及其连接关系的存储。其连接关系的存储。o 2、线：一维几何元素，是两个邻面或多个邻面的交界、线：一维

4、几何元素，是两个邻面或多个邻面的交界o 3、面：二维几何元素，是形体上一个有限、非零的区、面：二维几何元素，是形体上一个有限、非零的区域，由一个外环和若干内环界定其范围。具有方向性，域，由一个外环和若干内环界定其范围。具有方向性，由其外法线矢量方向定义。由其外法线矢量方向定义。o 4、环：有序、有向边组成的面的封闭边界。（外环中、环：有序、有向边组成的面的封闭边界。（外环中其边逆时针排序，内环顺时针排序）其边逆时针排序，内环顺时针排序）o 5、体：三维几何元素，由封闭表面围成的空间。、体：三维几何元素，由封闭表面围成的空间。7o 图形信息与非图形信息图形信息与非图形信息n 几何信息几何信息：形

5、体在欧氏空间中的位置和大小。：形体在欧氏空间中的位置和大小。n 拓扑信息拓扑信息：形体各分量（点、边、面）的数目：形体各分量（点、边、面）的数目及其相互间的连接关系。及其相互间的连接关系。基本概念基本概念几何信息与拓扑信息几何信息与拓扑信息图图4.1 4.1 拓扑信息拓扑信息9o 刚体运动刚体运动：不改变图形上任意两点间的距离，：不改变图形上任意两点间的距离，也不改变图形的几何性质的运动。也不改变图形的几何性质的运动。o 拓扑运动拓扑运动：允许形体作弹性运动，即在拓扑关：允许形体作弹性运动，即在拓扑关系中，对图形可随意地伸张扭曲。但图上各个系中，对图形可随意地伸张扭曲。但图上各个点仍为不同的点

6、，决不允许把不同的点合并成点仍为不同的点，决不允许把不同的点合并成一个点。一个点。基本概念基本概念几何信息与拓扑信息几何信息与拓扑信息10o 建模坐标系（建模坐标系（Modeling Coordinate System）（局部坐）（局部坐标系）标系）o 用户坐标系（全局坐标系、世界坐标系）用户坐标系（全局坐标系、世界坐标系）o 观察坐标系（观察坐标系（Viewing Coordinate System）（指定裁）（指定裁剪空间、定义投影平面，将用户坐标转换成规格化的设剪空间、定义投影平面，将用户坐标转换成规格化的设备坐标）备坐标）o 规格化设备坐标系（规格化设备坐标系（Normalized D

7、evice coordinate System）（定义视图区）（定义视图区）o 设备坐标系（设备坐标系（Device Coordinate System）（图形输入）（图形输入/输出的设备坐标系，如屏幕等）输出的设备坐标系，如屏幕等）基本概念基本概念坐标系坐标系11基本概念基本概念实体实体图图4.2 4.2 带有悬挂边的立方体带有悬挂边的立方体o 客观存在的三维形体的客观存在的三维形体的5条性质：条性质：n 刚性：一个物体必须具有一定的形状刚性：一个物体必须具有一定的形状n 维数的一致性：三维空间种，一个物体的各部分均应维数的一致性：三维空间种，一个物体的各部分均应是三维的，不能有悬挂的或孤立

8、边界是三维的，不能有悬挂的或孤立边界n 占据有限的空间（体积有限）占据有限的空间（体积有限）n 边界的确定性（根据物体的边界可以确定物体内部与边界的确定性（根据物体的边界可以确定物体内部与外部）外部）n 封闭性（经过一系列刚体运动及任意序列的集合运算封闭性（经过一系列刚体运动及任意序列的集合运算后，依然是有效的物体）后，依然是有效的物体）三维空间中的物体是一个内部连通的三维点集。三维空间中的物体是一个内部连通的三维点集。o 三维物体表面必须具有以下三维物体表面必须具有以下5条性质：条性质：n 连通性：位于物体表面上的任意两个点都可用实体表连通性：位于物体表面上的任意两个点都可用实体表面上的一条

9、路径连接起来。面上的一条路径连接起来。n 有界性：物体表面可将空间分为互不连通的两部分，有界性：物体表面可将空间分为互不连通的两部分，其中一部分是有界的其中一部分是有界的n 非自相交性：物体的表面不能自相交非自相交性：物体的表面不能自相交n 可定向性：物体表面的两侧可明确定义出属于物体的可定向性：物体表面的两侧可明确定义出属于物体的内侧或外侧内侧或外侧n 闭合性：物体表面的闭合性是由表面上多边形网格各闭合性：物体表面的闭合性是由表面上多边形网格各元素的拓扑关系决定的，即每一条边有且只有两个顶元素的拓扑关系决定的，即每一条边有且只有两个顶点；每一条边连接来年各个或两个以上的面。点；每一条边连接来

10、年各个或两个以上的面。14o 点的领域点的领域：如果：如果P是点集是点集S的一个元素，那么点的一个元素，那么点P的以的以R（R0）为半径的领域指的是围绕点为半径的领域指的是围绕点P的半径为的半径为R的小球（的小球（二维情况下为小圆）。二维情况下为小圆）。o 开集的闭包开集的闭包：是指该开集与其所有边界点的集合并集，本：是指该开集与其所有边界点的集合并集，本身是一个闭集。（三维物体的点的集合可以分为内部点和身是一个闭集。（三维物体的点的集合可以分为内部点和边界点来那个部分）边界点来那个部分）o 正则集正则集：由内部点构成的点集的闭包就是正则集，三维空：由内部点构成的点集的闭包就是正则集，三维空间

11、的正则集就是正则形体。也就是三维有效物体间的正则集就是正则形体。也就是三维有效物体 基本概念基本概念实体（点集拓扑学的角度）实体（点集拓扑学的角度）15基本概念基本概念实体实体o 组成三维物体的点的集合可以分为两类：组成三维物体的点的集合可以分为两类： n 内部点为点集中的这样一些点，它们具有完内部点为点集中的这样一些点，它们具有完全包含于该点集的充分小的领域。全包含于该点集的充分小的领域。n 边界点：不具备此性质的点集中的点。边界点：不具备此性质的点集中的点。 16基本概念基本概念实体实体o 定义点集的正则运算定义点集的正则运算r运算为：运算为：AicAro 正则运算即为先对物体取内点再取闭

12、包的运算。正则运算即为先对物体取内点再取闭包的运算。rA称为称为A的正则集。的正则集。17(a)带有孤立点和边的二维点集A(b)内点集合iA(c)正则点集ciA基本概念基本概念实体实体图图4.3 4.3 实体的例子实体的例子18图图4.4 4.4 正则形体正则形体基本概念基本概念实体实体19o 二维流形二维流形指的是对于实体表面上的任意一点，指的是对于实体表面上的任意一点，都可以找到一个围绕着它的任意小的领域，该都可以找到一个围绕着它的任意小的领域，该领域与平面上的一个圆盘是拓扑等价的。领域与平面上的一个圆盘是拓扑等价的。 基本概念基本概念实体实体图图4.5 4.5 正则形体正则形体20o 实

13、体：实体：对于一个占据有限空间的正则形体，如对于一个占据有限空间的正则形体，如果其表面是二维流形，则该正则形体为实体果其表面是二维流形，则该正则形体为实体。基本概念基本概念实体实体21p 有效实体的封闭性。有效实体的封闭性。p 把能够产生正则形体的集合运算称为正则集合运把能够产生正则形体的集合运算称为正则集合运算。算。基本概念基本概念正则集合运算正则集合运算22图图4.6 集合运算与正则集合运算集合运算与正则集合运算基本概念基本概念正则集合运算正则集合运算23图图4.7 基于点的领域概念生成正则形体基于点的领域概念生成正则形体基本概念基本概念正则集合运算正则集合运算B)(b- sharedA

14、bA),in B(b- B,out A bB)-(AbBb 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的结果（实线表示结果形体的边界）的结果（实线表示结果形体的边界）25基本概念基本概念平面多面体与欧拉公式平面多面体与欧拉公式o 欧拉公式证明简单多面体的顶点数欧拉公式证明简单多面体的顶点数V、边数、边数E和面数和面数F满满足如下关系：足如下关系：V-E+F=2。(简单多面体指那些经过连续的简单多面体指那些经过连续的几何形变可以变换成一个球的多面体，

15、即与球拓扑等价几何形变可以变换成一个球的多面体，即与球拓扑等价的那些多面体）的那些多面体）o 非简单多面体需对欧拉公式加以扩展。令非简单多面体需对欧拉公式加以扩展。令H表示多面体表表示多面体表面上孔的个数，面上孔的个数，G表示贯穿多面体的孔的个数，表示贯穿多面体的孔的个数，C表示独表示独立的、不相连接的多面体数，则扩展后的欧拉公式为：立的、不相连接的多面体数，则扩展后的欧拉公式为：V-E+F-H=2（C-G）。）。26基本概念基本概念平面多面体与欧拉公式平面多面体与欧拉公式图图4.9 平面多面体与欧拉公式平面多面体与欧拉公式27o 线框模型与实体模型（线框模型由定义一个物体线框模型与实体模型（

16、线框模型由定义一个物体边界的直线和曲线组成）边界的直线和曲线组成）o 可以将实体模型的表示大致分为三类：可以将实体模型的表示大致分为三类：n 边界表示（用一组曲面（或平面）来描述物体，边界表示（用一组曲面（或平面）来描述物体，这些曲面将物体分为内部和外部这些曲面将物体分为内部和外部）n 构造实体几何表示构造实体几何表示n 空间分割（将包含物体的空间划分成一组非常空间分割（将包含物体的空间划分成一组非常小的非重叠的连续实体）表示小的非重叠的连续实体）表示4.2 4.2 三维形体的表示三维形体的表示28o 多边形表面模型（使用一组包围物体内部的平面多边形表面模型（使用一组包围物体内部的平面多边形来描述实体）多边形来描述实体）o 扫描表示扫描表示o 构造实体几何法构造实体几何法o 空间位置枚举表示空间位置枚举表示o 八叉树八叉树o BSP树树o OpenGL中的实体模型函数中的实体模型函数三维形体的表示三维形体的表示29o 边界表示边界表示(B-reps)的最普遍方式是多边形表面模型，的最普遍方式是多边形表面模型，它使用一组包围物体内部的平面多边形，也即平面它使用一组包围物体内部的平面多边形