计算机图形学图形数据结构.ppt

《计算机图形学图形数据结构.ppt》由会员分享，可在线阅读，更多相关《计算机图形学图形数据结构.ppt（43页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机图形学图形数据结构现在学习的是第1页，共43页1 图形数据结构图形数据结构l计算机只识别数据，所处理的信息都是数据集合l计算机接受的图形图象信息也是数据集合 图形信息 非图形信息l图形信息：点、线、面及其相互位置关系和几何尺寸等l非图形信息：颜色、亮度及其他信息，也称为几何图形的属性现在学习的是第2页，共43页数据结构简介数据结构简介l数据：计算机化的信息。整数、字符、图象等l数据元素：数据的基本单位，即数据集合中的个体 链表中的节点等l数据对象：性质相同的数据元素的集合 C=a,b,z是一个字母数据对象l结构：数据元素之间的相互关系l数据结构：带有结构的数据元素集合及其运算称为 数据结

2、构。分为逻辑结构和物理结构。现在学习的是第3页，共43页数据结构简介（续）数据结构简介（续）l数据的逻辑结构：只抽象的反映数据元素间的逻辑关系，而不管其在计算机中存储方式。-线性结构：各数据间的逻辑关系可以用线性 序列表示，如线性表、栈、队列等。-非线性结构：树、图等。l数据的物理结构：数据的逻辑结构在计算机存储器里的组织形式，也称为存储结构。同一逻辑结构可以映象出不同的物理结构。-顺序存储结构 -链式存储结构现在学习的是第4页，共43页拓扑拓扑l拓扑是研究几何图形在形变与伸缩情况下空间性质不变的数学问题，即相互位置关系不发生改变。l例如，一个圆环面，可以通过几何形变，把它变成一个带柄的茶杯的

3、表面，变形前后的两个表面的点之间的位置关系没有发生改变，数学上称之为同胚。l经常说的网络的拓扑结构，指的是所有节点之间的相互连接关系。现在学习的是第5页，共43页平面图形数据结构平面图形数据结构l三表：点表、边表、面表（线性表，几何信息）顶点xyV表E表边顶点号1，21，42，33，43，54，512345平面图形F表面顶点号现在学习的是第6页，共43页三维形体的数据结构三维形体的数据结构l几何信息：点、线、面等几何分量在空间的位置，以及他们满足的表达式l拓扑信息：几何分量之间的相互连接关系对三维图形，只有几何信息不够，能够引起二义：下图中是只在5个顶点意义下的两个不同的几何实体。现在学习的是

4、第7页，共43页补充：正则形体补充：正则形体l正则形体：空间有界闭域，且是连通的，即形体内部的任意两点可以用不通过边界的折线连接起来。正则形体非正则形体悬边非正则形体悬面现在学习的是第8页，共43页补充：正则集合运算补充：正则集合运算l集合运算（并、交、差）是构造形体的基本方法，正则形体经过集合运算后，可能会产生悬边、悬面等低于三维的形体l正则集合运算保证集合运算的结果仍是一个正则形体，即丢弃悬边、悬面等 现在学习的是第9页，共43页顶点（顶点（Vertex）l顶点（Vertex）的位置用（几何）点（Point）来表示。一维空间的点用一元组t表示；二维空间中的的点用二元组x,y或x(t),y(

5、t)表示；三维空间中的点用三元组x,y,z或x(t),y(t),z(t)表示。n维空间中的点在齐次坐标下用n+1维表示。点是几何造型中的最基本的元素，自由曲线、曲面或其它形体均可用有序的点集表示。用计算机存储、管理、输出形体的实质就是对点集及其连接关系的处理。l在正则形体定义中，不允许孤立点存在现在学习的是第10页，共43页边（边（Edge）l边（Edge）是两个邻面(对正则形体而言)、或多个邻面(对非正则形体而言)的交集，边有方向，它由起始顶点和终止顶点来界定。边的形状（Curve）由边的几何信息来表示，可以是直线或曲线，曲线边可用一系列控制点或型值点来描述，也可用显式、隐式或参数方程来描述

6、。现在学习的是第11页，共43页环（环（Loop）l环（Loop）是有序、有向边（Edge）组成的封闭边界。环中的边不能相交，相邻两条边共享一个端点。环有方向、内外之分，外环边通常按逆时针方向排序，内环边通常按顺时针方向排序。现在学习的是第12页，共43页面（面（Face）l面（Face）由一个外环和若干个内环（可以没有内环）来表示，内环完全在外环之内。根据环的定义，在面上沿环的方向前进，左侧总在面内，右侧总在面外。面有方向性，一般用其外法矢方向作为该面的正向。若一个面的外法矢向外，称为正向面；反之，称为反向面。面的形状（Surface）由面的几何信息来表示，可以是平面或曲面，平面可用平面方程

7、来描述，曲面可用控制多边形或型值点来描述，也可用曲面方程（隐式、显式或参数形式）来描述。对于参数曲面，通常在其二维参数域上定义环，这样就可由一些二维的有向边来表示环，集合运算中对面的分割也可在二维参数域上进行。现在学习的是第13页，共43页体（体（Body）l体（Body）是面的并集。在正则几何造型系统中，要求体是正则的，非正则形体的造型技术将线框、表面和实体模型统一起来，可以存取维数不一致的几何元素，并可对维数不一致的几何元素进行求交分类，从而扩大了几何造型的形体覆盖域。现在学习的是第14页，共43页三维形体的数据结构三维形体的数据结构常见的表示三维形体的数据结构：l单链三表结构l双链翼边结

8、构l双链三表结构现在学习的是第15页，共43页单链三表结构单链三表结构l将几何实体用三张表的形式表示，并用单链指示他们之间的关系。-面表 -边表 -顶点表l由面表指针索引到边表，再由边表的指针索引到顶点表。每个节点只是单向的索引到下一个节点。现在学习的是第16页，共43页单链三表结构优缺点单链三表结构优缺点l优点：-结构关系清楚 -检索比较容易 -节省存储空间l缺点：-把形体的几何信息和拓扑信息结合在一起，不易频繁的进行交互修改。因此，它适合于速度要求不高，几何实体比较简单的图形处理系统中。英国剑桥大学的BUILD实体造型系统就是采用单链三表数据结构。现在学习的是第17页，共43页双链翼边结构

9、双链翼边结构l美国斯坦福大学提出l从外面观察平面立体时，可以看到楞边的左右两个临面和构成这两个临面周边的四条临边。形状如展开的鸟翼。l五表：形体表、面表、环表、边表和顶点表。l顶点表、边表和面表使用双向链表结构。l需要较多的存储单元。现在学习的是第18页，共43页双链三表结构双链三表结构l点表、面表和体表l点表表示形体的大小和在空间的位置l面表反映了形体的表面、棱边和顶点之间的邻接关系l体表中存放各表面在面中的首地址及其某些属性l采用双向链表现在学习的是第19页，共43页2 三维形体构成三维形体构成l三维形体构成模型 -线框模型 -表面模型 -实体模型l三维形体构成方法 -基于图法模型，-布尔

10、模型 -参数化形状表示法，-扫描表示法 -构造实体几何法，-边界表示法 -空间分割法，-八叉树法 -基于特征的造型方法现在学习的是第20页，共43页线框模型线框模型l也称为框架模型，用顶点和棱边来表示形体。l最早用来表示物体的模型。l数据存储需要顶点表和棱线表。现在学习的是第21页，共43页线框模型优缺点线框模型优缺点优点：l可以从任意方向获得三视图透视图等。缺点：l由于没有面的信息，不能表示表面含有曲面的物体。l它不能明确地定义给定点与物体之间的关系（点在物体内部、外部或表面上）。l不适于处理剖面图、明暗色彩图、消隐图、数控加工等，应用范围受到限制。现在学习的是第22页，共43页表面模型表面

11、模型l用边所围成的封闭部分定义实体的表面，再由面的包络构成实体。l和线框模型相比，多了一张面表，即使用顶点表、边表和面表。现在学习的是第23页，共43页表面模型优缺点表面模型优缺点优点：l表面模型扩大了线框模型的应用范围，能够满足面面求交、线面消隐、明暗色彩图、数控加工等需要。l能够表达复杂的雕刻曲面。缺点：l实体的边界可以确定，但是实体的实心位于边界的哪一侧还不可知，即没有给表面以侧的定义。l无法计算和分析物体的整体性质，如物体的表面积、体积、重心等。l不能将这个物体作为一个整体去考察它与其它物体相互关联的性质，如是否相交等。现在学习的是第24页，共43页实体模型实体模型l在表面模型的基础上

12、，增加了对实体的存在侧给了定义，也就是给表面定义了方向。l实体存在侧的定义：每个面的侧和边满足右手螺旋定则，即四指环绕方向为边的走向，拇指指向就是面的方向，也就是实体的存在侧。P现在学习的是第25页，共43页实体模型优缺点实体模型优缺点优点：l是最高级的三维物体模型，它能完整地表示物体的所有形状信息。l可以无歧义地确定一个点是在物体外部、内部或表面上，这种模型能够进一步满足物性计算、有限元分析等应用的要求。现在学习的是第26页，共43页三维形体构成方法三维形体构成方法现在学习的是第27页，共43页基于图法模型基于图法模型Graph-based modelsl是以拓扑结构为核心的几何模型。l通过

13、数据指针把实体的面、棱边和顶点连接起来。现在学习的是第28页，共43页布尔模型布尔模型Boolean modell由两个或两个以上的简单的几何实体经过布尔运算组合成一个较为复杂的几何实体，这种表示模型的方法称为布尔模型。l布尔模型是一个过程模型，它只是规定了简单的几何形体（体素）的组合方式，没有说明新实体的顶点坐标、棱边和面的信息。l若想知道新实体的更多信息，必须计算交线和交点以确定新的棱边和新顶点；分析连通性以确定模型的拓扑特点。现在学习的是第29页，共43页布尔模型例布尔模型例ABC(A U B)(A U B)-C布尔模型的二叉树现在学习的是第30页，共43页参数化形状表示法参数化形状表示

14、法l又称例图法l通过对已有的几何形体作简单的线性变换得到新的形体。l形体的形状发生改变，但是形体的拓扑关系不变。l参数化形体就是记录实体的几个关键数据，变换时，只针对关键数据作变换即可。l例如对立方体，记录长宽高即可，然后对其作简单的比例变换，就可以得到新的立方体。lCAM技术中成组技术就是基于此思想。现在学习的是第31页，共43页参数化形状表示法例参数化形状表示法例现在学习的是第32页，共43页扫描表示法扫描表示法Sweeping representationl当一点、一条曲线或一个面沿某一轨迹移动，可以形成特定的几何形体，由这种方法产生几何形体的过程称为扫描线方法。扫描表示需要两个分量，一

15、个是被运动的基体，另一个是基体运动的轨迹；如果是变截面的扫描，还要给出截面的变化规律。l生成元素：基体运动后产生的形体l导向元素：基体的运动轨迹l扫描线法是生成三维形体的有效方法。l常用的扫描变换模式 -平移和旋转扫描变换 -刚体运动扫描变换现在学习的是第33页，共43页平移和旋转扫描变换平移和旋转扫描变换ABxzy平移xzy旋转现在学习的是第34页，共43页平移和旋转扫描变换平移和旋转扫描变换现在学习的是第35页，共43页刚体运动扫描刚体运动扫描扫描方向刚体扫描变换刚体扫描变换在生产设计和自动化方面使用较多刚体扫描变换在生产设计和自动化方面使用较多现在学习的是第36页，共43页边界表示法边界

16、表示法(Brep)Boundary representationl是几何形体的边界表示模式，是几何造型中最成熟、无二义的表示法。l一个几何形体可以拆成一些有界的面或片，每个面都可以用它的边界和顶点表示。l在边界表示法中，边界表示按照体面环边点的层次，详细记录了构成形体的所有几何元素的几何信息及其相互连接的拓扑关系。在进行各种运算和操作中，就可以直接取得这些信息。现在学习的是第37页，共43页边界表示法例边界表示法例现在学习的是第38页，共43页构造实体几何法（构造实体几何法（CSG）Construcive Solid Geometryl是通过对体素定义运算而得到新的形体的一种表示方法，体素可以

17、是立方体、圆柱、圆锥等，也可以是半空间，其运算为变换或正则集合并、交、差运算。是通过简单的形体构成复杂形体的一种方法。lCSG表示可以看成是一棵有序的二叉树，其终端节点或是体素、或是形体变换参数。非终端结点或是正则的集合运算，或是变换（平移和旋转、刚体扫描、比例、对称等）操作，这种运算或变换只对其紧接着的子结点（子形体）起作用。每棵子树（非变换叶子结点）表示其下两个节点组合及变换的结果。l在CAD/CAM系统中，通常作为辅助表示方法。现在学习的是第39页，共43页构造实体几何法例构造实体几何法例CSG树结构现在学习的是第40页，共43页CSG常见的体素常见的体素现在学习的是第41页，共43页空

18、间分割法空间分割法Space subdiuision schemesl把复杂的几何形体分解成相邻但不相交的简单几何形体，他们的类型、尺寸、位置、参数及方位可以互不相同，类似各种形状的积木块。现在学习的是第42页，共43页八叉树法八叉树法Octreesl基本思想是将几何形体空间逐渐细分成2的幂次方个子块。l八叉树法表示形体的过程是这样的，首先对形体定义一个外接立方体，再把它分解成八个子立方体，并对立方体依次编号为0，1，2，7。如果子立方体单元完全位于被表示的几何形体内部，则该节点为“满”节点，或者位于被表示形体之外，则该子立方体可停止分解；否则，需要对该立方体作进一步分解，再一分为八个子立方体。在八叉树中，非叶结点的每个结点都有八个分支。现在学习的是第43页，共43页