图形的表示与数据结构

《图形的表示与数据结构》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1如何在计算机中建立恰当的模型表示不同图形对象。如何组织图形对象的描述数据以使存储这些数据所要的空间最省，检索、处理这些数据的速度较快。第四章图形的表示与数据结构2基本概念三维形体的表示非规则对象的表示层次建模图形的表示与数据结构3造型技术基本图形元素几何信息与拓扑信息坐标系实体的定义正则集合运算欧拉公式4.1基本概念4把研究如何在计算机中建立恰当的模型表示不同图形对象的技术称为造型技术。有两类图形对象：规则对象：几何造型、几何模型。能用欧氏几何加以描述的对象不规则对象：过程式模拟。不能用欧氏几何加以描述的对象基本概念——造型技术5基本概念——基本图

2、形元素基本图形元素：图素或图元、体素。图素是指可以用一定的几何参数和属性参数描述的最基本的图形输出元素。在二维图形系统中将基本图形元素称为图素或图元，在三维图形系统中称为体素。6图形对象的描述离不开大量的图形信息和非图形信息。图形信息几何信息：形体在欧氏空间中的位置和大小。拓扑信息：形体各分量（点、边、面）的数目及其相互间的连接关系。非图形信息基本概念——几何信息与拓扑信息包括图形对象，构成对象的点、线、面的位置和几何尺寸，以及它们相互之间的关系等图形的线性、颜色、亮度以及供模拟和分析用的质量、比重、体积等数据图4.1拓扑信息8刚体运动：不改变图形上

3、任意两点间的距离，也不改变图形的几何性质的运动。拓扑运动：允许形体作弹性运动，即在拓扑关系中，对图形可随意地伸张扭曲。但图上各个点仍为不同的点，决不允许把不同的点合并成一个点。基本概念——几何信息与拓扑信息9建模坐标系（ModelingCoordinateSystem）用户坐标系观察坐标系（ViewingCoordinateSystem）规格化设备坐标系（NormalizedDevicecoordinateSystem）设备坐标系（DeviceCoordinateSystem）基本概念——坐标系10基本概念——实体图4.2带有悬挂边的立方体11点的领

4、域：如果P是点集S的一个元素，那么点P的以R（R>0）为半径的领域指的是围绕点P的半径为R的小球（二维情况下为小圆）。开集的闭包：是指该开集与其所有边界点的集合并集，本身是一个闭集。正则集：由内部点构成的点集的闭包就是正则集，三维空间的正则集就是正则形体。基本概念－实体12基本概念－实体组成三维物体的点的集合可以分为两类：内点为点集中的这样一些点，它们具有完全包含于该点集的充分小的领域。边界点：不具备此性质的点集中的点。13基本概念——实体定义点集的正则运算r运算为：正则运算即为先对物体取内点再取闭包的运算。r·A称为A的正则集。14基本概念——实体

5、图4.3实体的例子15图4.4正则形体基本概念——实体16二维流形指的是对于实体表面上的任意一点，都可以找到一个围绕着它的任意小的领域，该领域与平面上的一个圆盘是拓扑等价的。基本概念——实体图4.5正则形体17实体：对于一个占据有限空间的正则形体，如果其表面是二维流形，则该正则形体为实体。基本概念——实体18有效实体的封闭性。把能够产生正则形体的集合运算称为正则集合运算。基本概念——正则集合运算19图4.6集合运算与正则集合运算基本概念——正则集合运算20图4.7基于点的领域概念生成正则形体基本概念——正则集合运算图4.8正则集合运算A∪*B，A∩*

6、B，A―*B的结果（实线表示结果形体的边界）22基本概念——平面多面体与欧拉公式欧拉公式证明简单多面体的顶点数V、边数E和面数F满足如下关系：V-E+F=2。非简单多面体需对欧拉公式加以扩展。令H表示多面体表面上孔的个数，G表示贯穿多面体的孔的个数，C表示独立的、不相连接的多面体数，则扩展后的欧拉公式为：V-E+F-H=2（C-G）。23基本概念——平面多面体与欧拉公式图4.9平面多面体与欧拉公式24线框模型与实体模型（实体造型技术）可以将实体模型的表示大致分为三类：边界表示（Boundaryrepresentation,B-reps）构造实体几何表

7、示空间分割（Space-partitioning）表示4.2三维形体的表示25多边形表面模型扫描表示构造实体几何法空间位置枚举表示八叉树BSP树OpenGL中的实体模型函数三维形体的表示26边界表示(B-reps)的最普遍方式是多边形表面模型，它使用一组包围物体内部的平面多边形，也即平面多面体，来描述实体。多边形表面模型图4.10四面体及其点、边、面的关系27多边形表面模型——数据结构几何信息建立3张表：顶点表、边表和多边形表来存储几何数据。实体模型中，用多边形顶点坐标值以及多边形所在平面方程方式保存实体单个表面部分的空间方向信息28多边形表面模型—

8、—数据结构拓扑信息：翼边结构表示（WingedEdgesStructure）图4.11翼边结构表示29多边形