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

1如何在计算机中建立恰当的模型表示不同图形对象。如何组织图形对象的描述数据以使存储这些数据所要的空间最省，检索、处理这些数据的速度较快。第四章图形的表示与数据结构2基本概念三维形体的表示非规则对象的表示层次建模图形的表示与数据结构3造型技术基本图形元素几何信息与拓扑信息坐标系实体的定义正则集合运算欧拉公式4.1基本概念4把研究如何在计算机中建立恰当的模型表示不同图形对象的技术称为造型技术。有两类图形对象：规则对象：几何造型、几何模型(几何信息和拓扑信息)。不规则对象：过程式模拟。基本概念——造型技术5基本概念——基本图形元素基本图形元素：图素或图元、体素。图素是指可以用一定的几何参数和属性参数描述的最基本的图形输出元素（包括点、线、面、环、体等）。在二维图形系统中将基本图形元素称为图素或图元，在三维图形系统中称为体素。1、点：为0维几何元素，是形体最基本的元素，自由曲线、曲面或其他形体均可用有序的点集来表示。点集及其连接关系的存储。2、线：一维几何元素，是两个邻面或多个邻面的交界3、面：二维几何元素，是形体上一个有限、非零的区域，由一个外环和若干内环界定其范围。具有方向性，由其外法线矢量方向定义。4、环：有序、有向边组成的面的封闭边界。（外环中其边逆时针排序，内环顺时针排序）5、体：三维几何元素，由封闭表面围成的空间。7图形信息与非图形信息几何信息：形体在欧氏空间中的位置和大小。拓扑信息：形体各分量（点、边、面）的数目及其相互间的连接关系。基本概念——几何信息与拓扑信息面相邻性f:{f}面-顶点包含性f:{v}面-边包含性f:{e}顶点—面相邻性v:{f}顶点相邻性v:{v}顶点-边相邻性v:{e}边-面相邻性e:{f}边-顶点包含性e:{v}边相邻性e:{e:}fffeeffffvevvveeevveffevvvfeevveeee图4.1拓扑信息9刚体运动：不改变图形上任意两点间的距离，也不改变图形的几何性质的运动。拓扑运动：允许形体作弹性运动，即在拓扑关系中，对图形可随意地伸张扭曲。但图上各个点仍为不同的点，决不允许把不同的点合并成一个点。基本概念——几何信息与拓扑信息10建模坐标系（ModelingCoordinateSystem）（局部坐标系）用户坐标系（全局坐标系、世界坐标系）观察坐标系（ViewingCoordinateSystem）（指定裁剪空间、定义投影平面，将用户坐标转换成规格化的设备坐标）规格化设备坐标系（NormalizedDevicecoordinateSystem）（定义视图区）设备坐标系（DeviceCoordinateSystem）（图形输入/输出的设备坐标系，如屏幕等）基本概念——坐标系11基本概念——实体图4.2带有悬挂边的立方体客观存在的三维形体的5条性质：刚性：一个物体必须具有一定的形状维数的一致性：三维空间种，一个物体的各部分均应是三维的，不能有悬挂的或孤立边界占据有限的空间（体积有限）边界的确定性（根据物体的边界可以确定物体内部与外部）封闭性（经过一系列刚体运动及任意序列的集合运算后，依然是有效的物体）三维空间中的物体是一个内部连通的三维点集。三维物体表面必须具有以下5条性质：连通性：位于物体表面上的任意两个点都可用实体表面上的一条路径连接起来。有界性：物体表面可将空间分为互不连通的两部分，其中一部分是有界的非自相交性：物体的表面不能自相交可定向性：物体表面的两侧可明确定义出属于物体的内侧或外侧闭合性：物体表面的闭合性是由表面上多边形网格各元素的拓扑关系决定的，即每一条边有且只有两个顶点；每一条边连接来年各个或两个以上的面。14点的领域：如果P是点集S的一个元素，那么点P的以R（R0）为半径的领域指的是围绕点P的半径为R的小球（二维情况下为小圆）。开集的闭包：是指该开集与其所有边界点的集合并集，本身是一个闭集。（三维物体的点的集合可以分为内部点和边界点来那个部分）正则集：由内部点构成的点集的闭包就是正则集，三维空间的正则集就是正则形体。也就是三维有效物体基本概念－实体（点集拓扑学的角度）15基本概念－实体组成三维物体的点的集合可以分为两类：内部点为点集中的这样一些点，它们具有完全包含于该点集的充分小的领域。边界点：不具备此性质的点集中的点。16基本概念——实体定义点集的正则运算r运算为：AicAr正则运算即为先对物体取内点再取闭包的运算。r·A称为A的正则集。17(a)带有孤立点和边的二维点集A(b)内点集合i·A(c)正则点集c·i·A基本概念——实体图4.3实体的例子18图4.4正则形体基本概念——实体19二维流形指的是对于实体表面上的任意一点，都可以找到一个围绕着它的任意小的领域，该领域与平面上的一个圆盘是拓扑等价的。(a)二维流形(b)二维流形(c)非二维流形基本概念——实体图4.5正则形体20实体：对于一个占据有限空间的正则形体，如果其表面是二维流形，则该正则形体为实体。基本概念——实体21有效实体的封闭性。把能够产生正则形体的集合运算称为正则集合运算。基本概念——正则集合运算22(a)A与B(b)(c)集合运算C=A∩B(d)正则集合运算C*=A∩*BABABCC*图4.6集合运算与正则集合运算基本概念——正则集合运算23PRPARAPBPBRBPARARB图4.7基于点的领域概念生成正则形体基本概念——正则集合运算ABABA∪*BA∩*BA―*BABABb·AoutBb·Asharedb·Bb·BoutAb·BinAb·AinBb·Asharedb·Bb·Ashared-(b·B)b·AoutB-(b·BinA)B)}(b-sharedAbA),inB(b-B,outA{bB)-(AbB}bsharedAbA,inBbB,inA{bB)(AbB}bsharedAbA,outBbB,outA{bB)(Ab***图4.8正则集合运算A∪*B，A∩*B，A―*B的结果（实线表示结果形体的边界）25基本概念——平面多面体与欧拉公式欧拉公式证明简单多面体的顶点数V、边数E和面数F满足如下关系：V-E+F=2。(简单多面体指那些经过连续的几何形变可以变换成一个球的多面体，即与球拓扑等价的那些多面体）非简单多面体需对欧拉公式加以扩展。令H表示多面体表面上孔的个数，G表示贯穿多面体的孔的个数，C表示独立的、不相连接的多面体数，则扩展后的欧拉公式为：V-E+F-H=2（C-G）。26基本概念——平面多面体与欧拉公式5-8+5=28-12+6=26-12+8=224－36＋15－3＝2×（1－1）图4.9平面多面体与欧拉公式27线框模型与实体模型（线框模型由定义一个物体边界的直线和曲线组成）可以将实体模型的表示大致分为三类：边界表示（用一组曲面（或平面）来描述物体，这些曲面将物体分为内部和外部）构造实体几何表示空间分割（将包含物体的空间划分成一组非常小的非重叠的连续实体）表示4.2三维形体的表示28多边形表面模型（使用一组包围物体内部的平面多边形来描述实体）扫描表示构造实体几何法空间位置枚举表示八叉树BSP树OpenGL中的实体模型函数三维形体的表示29边界表示(B-reps)的最普遍方式是多边形表面模型，它使用一组包围物体内部的平面多边形，也即平面多面体，来描述实体。需要设计有效的数据结构来处理面、边、点BCDVABCABDBCDACDABBCCAADBDCDABCD体面边顶点A多边形表面模型图4.10四面体及其点、边、面的关系30多边形表面模型——数据结构几何信息（几何表）建立3张表：顶点表、边表和多边形表来存储几何数据。实体模型中，用多边形顶点坐标值以及多边形所在平面方程方式保存实体单个表面部分的空间方向信息31多边形表面模型——数据结构拓扑信息：翼边结构表示（WingedEdgesStructure）E2E1E3E4F1V2V1F2E图4.11翼边结构表示32多边形表面模型——数据结构属性信息用属性表来存储多边形面的属性，指明物体透明度及表面反射度的参数和纹理特征等等。实体测试条件：1）每个顶点至少是两条边的端点2）每条边至少是一个多边形的部分3）每个多边形式封闭的4）每个多边形至少有一条公共边5）如果多边形表包含指向多边形边的指针，则每一个被指针指向的边有一个逆指针指回到多边形33多边形网格：三维形体的边界通常用多边形网格（polygonmesh）的拼接来模拟。（三角形和四边形）例子多边形表面模型图4.12三角形带与四边形网格34扫描表示法（sweeprepresentation）可以利用简单的运动规则生成有效实体。包含两个要素一是作扫描运动的基本图形（截面）；二是扫描运动的方式（平移、旋转、对称变换）。扫描表示（sweeprepresentation）35构造实体几何法（CSG，ConstructiveSolidGeometry）由两个实体间的并、交或差操作生成新的实体。BAAABB(a)A,B形体的并(b)A,B形体的差(c)A,B形体的交构造实体几何法图4.13构造实体几何法36在构造实体几何法中，集合运算的实现过程可以用一棵二叉树（称为CSG树）来描述。树的叶子是基本体素或是几何变换参数；树的非终端结点是施加于其子结点的正则集合算子（正则并、正则交和正则差）或几何变换的定义。构造实体几何法371234-11-10YXP1410YXP2(a)(b)CUTUUP1△x=2△y=2UT(平移)P1P1△x=2T(平移)P1△x=4P2T△y=2P21234-11-10YXP1(c)CSG树(d)由CSG树产生的形体-2图4.14由CSG树产生二维形体的实例38优点：如果体素设置比较齐全，通过集合运算就可以构造出多种不同的符合需要的实体。缺点一：集合运算的中间结果难以用简单的代数方程表示，求交困难。缺点二：CSG树不能显式地表示形体的边界，因而无法直接显示CSG树表示的形体。构造实体几何法39解决：光线投射算法构造实体几何法xyz投影平面射线射线zxyabcdAB(b)(a)图4.15光线投射算法(实体A∪B取ad，实体A∩B则取cb,实体A-B则取ab)40空间位置枚举表示法将包含实体的空间分割为大小相同、形状规则（正方形或立方体）的体素，然后，以体素的集合来表示图形对象。二维情况，常用二维数组存放。三维情况下，常用三维数组p[i][j][k]来存放。空间位置枚举表示41八叉树（octrees）又称为分层树结构，它对空间进行自适应划分，采用具有层次结构的八叉树来表示实体。八叉树42八叉树——四叉树BBEFB1234BBBEBBBBFBFEFEEEFEEFFEFFFFFEEEF象限2象限3象限4象限1......(a)(b)图4.16二维图的四叉树表示43八叉树xzy1324567857861342图4.17三维空间分成八个卦限及其节点表示44二叉空间分割（BinarySpacePartitioning，BSP）树方法是一种类似于八叉树的空间分割方法，它每次将一实体用任一位置和任一方向的平面分为二部分（不同于八叉树方法的每次将实体用平行于笛卡尔坐标平面的三个两两垂直的平面分割）。BSP树45GLUT库中的多面体函数OpenGL中的实体模型函数函数说明glutSolidTetrahedron()glutWireTetrahedron()绘制中心位于世界坐标系原点的实心四面体和线框四面体，四面体的半径为。glutSolidCube(size)glutWireCube(size)绘制中心位于世界坐标系原点的实心立方体和线框立方体，立方体的半径为size，size是一个双精度浮点值。glutSolidOctahedron()glutWireOctahedron()绘制中心位于世界坐标系原点的实心八面体和线框八面体，八面体的半径为1.