计算机图形学CG10-图形数据结构.pptVIP

§1 图形数据结构 计算机只识别数据，所处理的信息都是数据集合 计算机接受的图形图象信息也是数据集合 －图形信息 －非图形信息 图形信息：点、线、面及其相互位置关系和几何尺寸等 非图形信息：颜色、亮度及其他信息，也称为几何图形的属性 数据结构简介 数据：计算机化的信息。整数、字符、图象等 数据元素：数据的基本单位，即数据集合中的个体 链表中的节点等 数据对象：性质相同的数据元素的集合 C={‘a’,’b’,…,’z’}是一个字母数据对象 结构：数据元素之间的相互关系 数据结构：带有结构的数据元素集合及其运算称为 数据结构。分为逻辑结构和物理结构。 数据结构简介（续） 数据的逻辑结构：只抽象的反映数据元素间的逻辑关系，而不管其在计算机中存储方式。 --线性结构：各数据间的逻辑关系可以用线性 序列表示，如线性表、栈、队列等。 --非线性结构：树、图等。 数据的物理结构：数据的逻辑结构在计算机存储器里的组织形式，也称为存储结构。同一逻辑结构可以映象出不同的物理结构。 --顺序存储结构 --链式存储结构 拓扑 拓扑是研究几何图形在形变与伸缩情况下空间性质不变的数学问题，即相互位置关系不发生改变。 例如，一个圆环面，可以通过几何形变，把它变成一个带柄的茶杯的表面，变形前后的两个表面的点之间的位置关系没有发生改变，数学上称之为同胚。 经常说的网络的拓扑结构，指的是所有节点之间的相互连接关系。 平面图形数据结构 三表：点表、边表、面表（线性表，几何信息） 三维形体的数据结构 几何信息：点、线、面等几何分量在空间的位置，以及他们满足的表达式 拓扑信息：几何分量之间的相互连接关系 对三维图形，只有几何信息不够，能够引起二义：下 图中是只在5个顶点意义下的两个不同的几何实体。 补充：正则形体 正则形体：空间有界闭域，且是连通的，即形体内部的任意两点可以用不通过边界的折线连接起来。 补充：正则集合运算 集合运算（并、交、差）是构造形体的基本方法，正则形体经过集合运算后，可能会产生悬边、悬面等低于三维的形体 正则集合运算保证集合运算的结果仍是一个正则形体，即丢弃悬边、悬面等 顶点（Vertex） 顶点（Vertex）的位置用（几何）点（Point）来表示。一维空间的点用一元组{t}表示；二维空间中的的点用二元组{x,y}或{x(t),y(t)}表示；三维空间中的点用三元组{x,y,z}或{x(t),y(t),z(t)}表示。n维空间中的点在齐次坐标下用n+1维表示。点是几何造型中的最基本的元素，自由曲线、曲面或其它形体均可用有序的点集表示。用计算机存储、管理、输出形体的实质就是对点集及其连接关系的处理。 在正则形体定义中，不允许孤立点存在 边（Edge） 边（Edge）是两个邻面(对正则形体而言)、或多个邻面(对非正则形体而言)的交集，边有方向，它由起始顶点和终止顶点来界定。边的形状（Curve）由边的几何信息来表示，可以是直线或曲线，曲线边可用一系列控制点或型值点来描述，也可用显式、隐式或参数方程来描述。 环（Loop） 环（Loop）是有序、有向边（Edge）组成的封闭边界。环中的边不能相交，相邻两条边共享一个端点。环有方向、内外之分，外环边通常按逆时针方向排序，内环边通常按顺时针方向排序。 面（Face） 面（Face）由一个外环和若干个内环（可以没有内环）来表示，内环完全在外环之内。根据环的定义，在面上沿环的方向前进，左侧总在面内，右侧总在面外。面有方向性，一般用其外法矢方向作为该面的正向。若一个面的外法矢向外，称为正向面；反之，称为反向面。面的形状（Surface）由面的几何信息来表示，可以是平面或曲面，平面可用平面方程来描述，曲面可用控制多边形或型值点来描述，也可用曲面方程（隐式、显式或参数形式）来描述。对于参数曲面，通常在其二维参数域上定义环，这样就可由一些二维的有向边来表示环，集合运算中对面的分割也可在二维参数域上进行。 体（Body） 体（Body）是面的并集。在正则几何造型系统中，要求体是正则的，非正则形体的造型技术将线框、表面和实体模型统一起来，可以存取维数不一致的几何元素，并可对维数不一致的几何元素进行求交分类，从而扩大了几何造型的形体覆盖域。 三维形体的数据结构 常见的表示三维形体的数据结构： 单链三表结构 双链翼边结构 双链三表结构 单链三表结构 将几何实体用三张表的形式表示，并用单链指示他们之间的关系。 --面表 --边表 --顶点表 由面表指针索引到边表，再由边表的指针索引到顶点表。