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

如何在计算机中建立恰当的模型表示不同图形对象。 如何组织图形对象的描述数据以使存储这些数据所要的空间最省，检索、处理这些数据的速度较快。;基本概念 三维形体的表示 非规则对象的表示 层次建模;造型技术 基本图形元素 几何信息与拓扑信息 坐标系 实体的定义 正则集合运算 欧拉公式;把研究如何在计算机中建立恰当的模型表示不同图形对象的技术称为造型技术。 有两类图形对象： 规则对象：几何造型、几何模型(几何信息和拓扑信息)。 不规则对象：过程式模拟??;基本概念——基本图形元素;1、点：为0维几何元素，是形体最基本的元素，自由曲线、曲面或其他形体均可用有序的点集来表示。点集及其连接关系的存储。 2、线：一维几何元素，是两个邻面或多个邻面的交界 3、面：二维几何元素，是形体上一个有限、非零的区域，由一个外环和若干内环界定其范围。具有方向性，由其外法线矢量方向定义。 4、环：有序、有向边组成的面的封闭边界。（外环中其边逆时针排序，内环顺时针排序） 5、体：三维几何元素，由封闭表面围成的空间。;图形信息与非图形信息 几何信息：形体在欧氏空间中的位置和大小。 拓扑信息：形体各分量（点、边、面）的数目及其相互间的连接关系。;图4.1 拓扑信息;刚体运动：不改变图形上任意两点间的距离，也不改变图形的几何性质的运动。 拓扑运动：允许形体作弹性运动，即在拓扑关系中，对图形可随意地伸张扭曲。但图上各个点仍为不同的点，决不允许把不同的点合并成一个点。;建模坐标系（Modeling Coordinate System）（局部坐标系） 用户坐标系（全局坐标系、世界坐标系） 观察坐标系（Viewing Coordinate System）（指定裁剪空间、定义投影平面，将用户坐标转换成规格化的设备坐标） 规格化设备坐标系（Normalized Device coordinate System）（定义视图区） 设备坐标系（Device Coordinate System）（图形输入/输出的设备坐标系，如屏幕等）;基本概念——实体;客观存在的三维形体的5条性质： 刚性：一个物体必须具有一定的形状 维数的一致性：三维空间种，一个物体的各部分均应是三维的，不能有悬挂的或孤立边界 占据有限的空间（体积有限） 边界的确定性（根据物体的边界可以确定物体内部与外部） 封闭性（经过一系列刚体运动及任意序列的集合运算后，依然是有效的物体） 三维空间中的物体是一个内部连通的三维点集。;三维物体表面必须具有以下5条性质： 连通性：位于物体表面上的任意两个点都可用实体表面上的一条路径连接起来。 有界性：物体表面可将空间分为互不连通的两部分，其中一部分是有界的 非自相交性：物体的表面不能自相交 可定向性：物体表面的两侧可明确定义出属于物体的内侧或外侧 闭合性：物体表面的闭合性是由表面上多边形网格各元素的拓扑关系决定的，即每一条边有且只有两个顶点；每一条边连接来年各个或两个以上的面。;点的领域：如果P是点集S的一个元素，那么点P的以R（R0）为半径的领域指的是围绕点P的半径为R的小球（二维情况下为小圆）。 开集的闭包：是指该开集与其所有边界点的集合并集，本身是一个闭集。（三维物体的点的集合可以分为内部点和边界点来那个部分） 正则集：由内部点构成的点集的闭包就是正则集，三维空间的正则集就是正则形体。也就是三维有效物体 ;基本概念－实体;基本概念——实体;基本概念——实体;图4.4 正则形体;二维流形指的是对于实体表面上的任意一点，都可以找到一个围绕着它的任意小的领域，该领域与平面上的一个圆盘是拓扑等价的。 ;实体：对于一个占据有限空间的正则形体，如果其表面是二维流形，则该正则形体为实体。;有效实体的封闭性。 把能够产生正则形体的集合运算称为正则集合运算。;图4.6 集合运算与正则集合运算;图4.7 基于点的领域概念生成正则形体;图4.8 正则集合运算A∪*B，A∩*B，A―*B的结果（实线表示结果形体的边界）;基本概念——平面多面体与欧拉公式;基本概念——平面多面体与欧拉公式;线框模型与实体模型（线框模型由定义一个物体边界的直线和曲线组成） 可以将实体模型的表示大致分为三类： 边界表示（用一组曲面（或平面）来描述物体，这些曲面将物体分为内部和外部） 构造实体几何表示 空间分割（将包含物体的空间划分成一组非常小的非重叠的连续实体）表示;多边形表面模型（使用一组包围物体内部的平面多边形来描述实体） 扫描表示 构造实体几何法 空间位置枚举表示 八叉树 BSP树 OpenGL中的实体模型函数;边界表示(B-reps)的最普遍方式是多边形表面模型，它使用一组包围物体内部的平面多边形，也即平面多面体，来描述实体。需要设计有效的数据结构来处理面、边、点;多边形表面模型