图形的表示与数据结构.ppt

第第4章章 图形的表示与数据结构图形的表示与数据结构造型技术造型技术: 把研究如何在计算机中建立恰当的模型表示不同图形对象的技术称为造型技术造型技术有两类图形对象：规则对象：规则对象：几何造型、几何模型几何造型、几何模型不规则对象不规则对象4.1.1 基本图形元素与段的概念基本图形元素与段的概念4.1 基本概念基本概念基本图形元素：基本图形元素：图素或图元、体素图图素素是指可以用一定的几何参数和属性参数描述的最基本的图形输出元素包括点、线、圆、圆弧、椭圆、二次曲线等体体素素是三维空间中可以用有限个尺寸参数定位和定形的体.欧氏空间中, 形体由点、线、面、环、体等几何元素构成 点点是0维几何元素，分端点、交点、切点和孤立点等  边边是1维几何元素，是两个邻面（正则形体）或多个邻面（非正则形体）的交界直线边、曲线边直线边、曲线边 面面是2维几何元素，是形体上一个有限、非零的区域，由一个外环和若干个内环界定其范围l一个面可以无内环，但必须有一个且只有一个外环l面有方向性，以其外法线矢量外法线矢量方向为该面的正向环环是有序、有向边（真线段或曲线段）组成的面的封闭边界。

§环中的边不能相交，相邻两条边共享一个端点§确定面的最大外边界的环称之为外环外环§确定面中内孔或凸台边界的环称之为内环内环 体体是3维几何元素，由封闭表面围成空间，也是欧氏空间R3中非空、有界的封闭子集，其边界是有限面的并集4.1.2 几何信息与拓扑信息几何信息与拓扑信息§图形对象及构成它的点、线、面的位置、相互间关系和几何尺寸等都是图形信息图形信息；§表示图形对象的线型、颜色、亮度以及供模拟、分析用的质量、比重、体积等数据，是有关对象的非非图形信息图形信息图形信息往往从几何信息及拓扑信息两方面考虑图形信息往往从几何信息及拓扑信息两方面考虑几几何何信信息息：：形体在欧氏空间中的位置和大小(物体的各部分几何形状及其在空间的位置)拓拓扑扑信信息息：：形体各分量（点、边、面）的数目及其相互间的连接关系 1. 几何信息几何信息 (1)几何分量的数学表示几何分量的数学表示, 如：如： 点点: (x, y, z) 直线：直线：x=(y-y0)/a=(z-z0)/b 平面：平面：ax+by+cz+b=0(2)几何分量之间的相互关系几何分量之间的相互关系(拓扑信息拓扑信息)几何信息的二义性2. 拓朴信息拓朴信息平面立体的几何分量之间一共有九种拓扑关系4.1.3 坐标系坐标系4.1.4 实体的定义实体的定义(a)有悬面(b)有悬边客观存在的三维形体具有这样一些性质客观存在的三维形体具有这样一些性质：(1)刚性(2)维数的一致性(3)占据有限的空间(4)边界的确定性(5)封闭性 三三维维空空间间中中的的物物体体是是一一个个内内部部连连通通的的三三维维点点集集，，是由其内部的点集及紧紧包着这些点的表皮组成的是由其内部的点集及紧紧包着这些点的表皮组成的。

利用利用正则集正则集的概念来定义上述的三维有效物体的概念来定义上述的三维有效物体： 由由内内部部点点构构成成的的点点集集的的闭闭包包就就是是正正则则集集，，三三维维空空间间中中正正则则集集就就是是正正则则形形体体，，也也就就是是三三维维有有效效物物体4.1.4 正则集合运算正则集合运算定义点集的正则运算点集的正则运算r运算为：正则运算即为先对物体取内点再取闭包的运算r·A称为A的正则集正则集 图4-7 正则形体二二维维流流形形指的是对于实体表面上的任意一点，都可以找到一个围绕着它的任意小的领域，该领域与平面上的一个圆盘是拓扑等价的 实实体体：对对于于一一个个占占据据有有限限空空间间的的正正则则形形体体，，如如果果其表面是二维流形，则该正则形体为实体其表面是二维流形，则该正则形体为实体欧拉公式是检查实体有效性的一个必要条件（不是充分条件）4.1.7 平面多面体与欧拉公式平面多面体与欧拉公式简单多面体条件：（1）所在面是单连通的，上面没有洞（2）立体是单连通的，而且没有孔洞（3）每条棱边上恰好邻接两个面（4）每一个顶点处至少有三条棱边相遇其顶点数V、边数E和面数F满足如下关系：                                  V-E+F=2。

v=5E=8F=5v=8E=12F=6v=6E=12F=8图4-12 简单多面体 V-E+F=2V-E+F=2令H表示多面体表面上孔的个数，G表示贯穿多面体的孔的个数，C表示独立的、不相连接的多面体数，则扩展后的欧拉公式扩展后的欧拉公式为：V-E+F-H=2(C-G)V-E+F-H=2(C-G)V=24 E=36V=24 E=36F=16 H=2F=16 H=2C=1 G=0C=1 G=0线框模型线框模型       由定义一个物体的直线和曲线组成，每一条直线和曲线都是单独构造出来的，并不存在面的信息线框模型存在着几个缺陷：§二义性4.2 三维形体的表示三维形体的表示§容易构造出无效形体§不能正确表示曲面信息§无法进行图形的线面消隐 §加重用户的输入负担§难以保证数据的统一性和有效性可以将实体模型的表示可分为以下方法：§边界表示法（边界表示法（BR））§扫描表示法扫描表示法§构造实体几何法（构造实体几何法（CSG））§空间位置枚举表示法空间位置枚举表示法§八叉树法八叉树法§二叉空间分割法（二叉空间分割法（BSP））4.2.1 多边形表面模型多边形表面模型边界表示(B-reps)的最普遍方式是多多边边形形表表面面模模型型，它使用一组包围物体内部的平面多边形，也即平面多面体，来描述实体。

1. 多边形表多边形表•几何表几何表•属性表属性表     例如：顶点表顶点表、边表边表和多边形表多边形表为图4-17所示的四面体建立的三张表如下：顶点表 边表 面表Ax1,y1,z1 ABA,B ABCAB,BC,ACBx2,y2,z2 BCB,C ABDAB,BD,ADCx3,y3,z3 CAC,A BCDBC,CD,BDDx4,y4,z4 ADA,D ACDAC,CD,AD BCB,C  CDC,D 表示其拓扑信息 例如，翼边结构表示翼边结构表示（Winged Edges Structure）2. 平面方程平面方程可以利用平面方程：Ax+By+Cz+D=0•求得平面的法向量•鉴别空间上的点与物体平面的位置关系•判别点在面的内部或外部§实体存在侧方法——平面法向量平面法向量          法向量指向物体外部，当多边形顶点指定为逆时针方向时，法向量方向满足右手定则3. 多边形网格多边形网格三维形体的曲面边界通常用多边形网格（polygon mesh）的拼接来模拟三角形带、四边形网格三角形带、四边形网格4.2.2 扫描表示扫描表示扫扫描描表表示示法法（（sweep representation））可以利用简单的运动规则生成有效实体。

 包含两个要素：§一是作扫描运动的基本图形；§二是扫描运动的方式: 平移、旋转 扫描方向基面回转轴基面基面基面（a）（b）（c）（d）4.2.3 构造实体几何法构造实体几何法构造实体几何法（构造实体几何法（CSG，，Constructive Solid Geometry））由两个实体间的并、交或差操作生成新的实体   在构造实体几何法中，集合运算的实现过程可以用一棵二叉树（称为二叉树（称为CSG树）树）来描述：•树的叶子：树的叶子：体素或形体变换参数•树的非终端结点：树的非终端结点：    正则的集合运算或变换（平移或旋转）操作•二叉树根结点：二叉树根结点：构造的实体构造实体几何法的优点：§可以构造出多种不同的符合需要的实体问题：§求交困难§CSG树不能显式地表示形体的边界解决：光线投射（Ray-casting）算法光线投射（光线投射（Ray-casting））算法算法：具体算法是：1)将射线与CSG树中的所有基本体素求交，求出所有的交点2)将所有交点相对于CSG树表示的物体进行分类，确定位于物体边界上的那部分交点3)对所有位于物体边界上的交点计算它们在射线上的参数值并进行排序，确定距离最近的交点。

得到其所在基本体素表面的法矢量4.2.4 空间位置枚举表示空间位置枚举表示空空间间位位置置枚枚举举表表示示法法将包含实体的空间分割为大小相同、形状规则（正方形或立方体）的体素，然后，以体素的集合来表示图形对象§二维情况，常用二维数组存放§三维情况下，常用三维数组p[i][j][k]来存放P98 图4-294.2.5 八叉树八叉树八八叉叉树树（（octrees））又称为分层树结构，它对空间进行自适应划分，采用具有层次结构的八叉树来表示实体四叉树四叉树八叉树八叉树012356712337（a）（b）z z（c）具有子孙的节点空节点实节点0 1 2 3 4 5 6 70 1 2 3 4 5 6 74.2.6 BSP树树二二叉叉空空间间分分割割（（binary space partitioning，，BSP））方方法法每次将一实体用任一位置和任一方向的平面分为二部分4.3.1 分形几何分形几何(fractal geometry)分形几何物体具有一个基本特征：无限的自相似性无限的自相似性。

无无限限的的自自相相似似性性是指物体的整体和局部之间细节的无限重现分形物体的描述又包含：§分形维数，又称分数维数§生生 成成 过过 程程 ： 初初 始始 生生 成成 元元 （（ initiator）） 、、 生生 成成 元元（（genenator））4.3 非规则对象的表示非规则对象的表示4.3.2 形状语法形状语法形形状状语语法法（（shape grammars））：给定一组产生式规则，形状设计者可以在从给定初始物体到最终物体结构的每一次变换中应用不同的规则4.3.3 微粒系统微粒系统用于模拟自然景物或模拟其它非规则形状物体展示“流体”性质的一个方法是微微粒粒系系统统（（particle systems））§这一方法尤其擅长描述随时间变化的物体§微粒运动的模拟方式：随机过程模拟、运动路径模拟、力学模拟4.3.4 基于物理的建模基于物理的建模基基于于物物理理的的建建模模方方法法：：描述了物体在内外力相互作用下的行为§通常用一组网格结点来逼近物体网格结点间取为柔性连接，再考虑贯穿物体网格的力传递§基于力学方程的动画描述比基于运动学方程的描述产生的运动更真实4.3.5 数据场的可视化数据场的可视化科科技技计计算算可可视视化化（scientific visualization）指的是运用计算机图形学和图象处理技术，将科学计算过程中及计算结果的数据转换为图形及图象在屏幕上显示出来并进行交互处理的理论、方法和技术。

4.4 图形的层次结构图形的层次结构4.4.1 段的层次概念段的层次概念作作业:1.已知八叉树的八等区域分法为下图A所示，请画出以    下图B几何形体的八叉树示意图2. 请检测下列三维形体是否满足欧拉公式.。