搜索
计算机图形学基础华东理工大学计算机系·谢晓玲2如何在计算机中建立恰当的模型表示不同图形对象。如何组织图形对象的描述数据以使存储这些数据所要的空间最省，检索、处理这些数据的速度较快。第四章图形的表示与数据结构3基本概念三维形体的表示非规则对象的表示层次建模图形的表示与数据结构4造型技术基本图形元素几何信息与拓扑信息坐标系实体的定义正则集合运算欧拉公式4.1基本概念5把研究如何在计算机中建立恰当的模型表示不同图形对象的技术称为造型技术。有两类图形对象：规则对象：几何造型、几何模型。不规则对象：过程式模拟。基本概念——造型技术6规则对象：用欧氏几何描述的对象几何造型：规则对象的造型几何模型：在几何造型中描述的规则对象不规则对象：不能用欧氏几何描述的对象过程式模拟：用一个简单的模型以及少量的参数来表示一类对象基本概念——造型技术7基本概念——基本图形元素基本图形元素：图素或图元、体素。图素是指可以用一定的几何参数和属性参数描述的最基本的图形输出元素。在二维图形系统中将基本图形元素称为图素或图元，在三维图形系统中称为体素。常见基本图形元素：点、线、面、环、体、…8图形信息几何信息：形体在欧氏空间中的位置和大小。拓扑信息：形体各分量（点、边、面）的数目及其相互间的连接关系。非图形信息线性、颜色、亮度、…基本概念——几何信息与拓扑信息面相邻性f:{f}面-顶点包含性f:{v}面-边包含性f:{e}顶点—面相邻性v:{f}顶点相邻性v:{v}顶点-边相邻性v:{e}边-面相邻性e:{f}边-顶点包含性e:{v}边相邻性e:{e:}fffeeffffvevvveeevveffevvvfeevveeee图4.39种拓扑信息10刚体运动：不改变图形上任意两点间的距离，也不改变图形的几何性质的运动。拓扑运动（弹性运动）：在拓扑关系中，对图形可随意地伸张扭曲。但图上各个点仍为不同的点，决不允许把不同的点合并成一个点。基本概念——几何信息与拓扑信息11拓扑等价：一个图形作弹性运动可使之与另一个图形重合。拓扑性质：与拓扑等价的图形所具有的性质。基本概念——几何信息与拓扑信息12建模坐标系(MC,ModelingCoordinateSystem)：造型坐标系、局部坐标系用户坐标系(WC,WorldCoordinateSystem)：全局坐标系、世界坐标系观察坐标系(VC,ViewingCoordinateSystem)：指定裁剪空间、定义观察（投影）平面规格化设备坐标系(NDC,NormalizedDevicecoordinateSystem)：定义视图区设备坐标系(DC,DeviceCoordinateSystem)：通常是像素或位图的坐标系基本概念——坐标系13基本概念——实体的定义图4.4带有悬挂边的立方体是没有意义的形体实体造型必须保证形体是有效的，即“客观存在”：①刚性：即具有一定的形状②维数的一致性：在三维空间中，一个物体的各部分均应是三维的③有限的空间：体积有限④边界的确定：根据边界可以区分物体的内部及外部⑤封闭性：一个有效的实体经刚体运动、集合运算后仍然是有效的实体14基本概念——实体的定义三维空间中的物体是一个内部连通的三维点集①连通性：位于物体表面上的任意两个点都可以用物体表面的一条路经连接起来②有界性：物体表面可将空间分为互不连通的两部分，其中一部分是有界的③非自相交性：物体的表面不能自相交④可定向性：物体表面的两侧可以定义物体的内侧或外侧⑤闭合性：每一条边有且仅有两个顶点；每一条边连接两个或两个以上的面15点集拓扑学的定义：点的领域：如果P是点集S的一个元素，那么点P的以R（R0）为半径的领域指的是围绕点P的半径为R的小球（二维情况下为小圆）。开集的闭包：是指该开集与其所有边界点的集合并集，本身是一个闭集。正则集：由内部点构成的点集的闭包就是正则集，三维空间的正则集就是正则形体。基本概念－实体的定义16基本概念－实体的定义组成三维物体的点的集合可以分为两类：内点为点集中的这样一些点，它们具有完全包含于该点集的充分小的领域。边界点：不具备此性质的点集中的点。17基本概念——实体的定义定义点集的正则运算r运算为：i·A为A的全体内点的集合，是一个开集。再取闭包的运算c。c·i·A为A的全体内点的闭包，是一个闭集。r·A称为A的正则集。18(a)带有孤立点和边的二维点集A(b)内点集合i·A(c)正则点集c·i·A基本概念——实体的定义图4.5实体的例子19图4.6正则形体但不是实体模型的描述对象基本概念——实体的定义实体应具有二维流形性质。二维流形指的是对于实体表面上的任意一点，都可以找到一个围绕着它的任意小的领域，该领域与平面上的一个圆盘是拓扑等价的。20即该领域与圆盘之间存在着连续的一一对应关系。如果实体表面上的一条边所连接的面多于两个，那么这条边上任意一个点的小领域都包含来自这些面上的点，因此与圆盘不是拓扑等价的。(a)二维流形(b)二维流形(c)非二维流形基本概念——实体的定义图4.7正则形体21实体：对于一个占据有限空间的正则形体，如果其表面是二维流形，则该正则形体为实体。基本概念——实体的定义22有效实体的封闭性。把能够产生正则形体的集合运算称为正则集合运算。基本概念——正则集合运算23(a)A与B(b)(c)集合运算C=A∩B(d)正则集合运算C*=A∩*BABABCC*图4.8集合运算与正则集合运算∩（正则交）基本概念——正则集合运算24两种方法实现正则运算：间接方式基于点集拓扑学的领域概念，先按通常的集合运算求出集合，然后再用一些规则加以判断直接方式定义正则集合算子的表达式，直接求得正则集合基本概念——正则集合运算25间接方式邻域：如果P是点集S的一个元素，那么P点以R(0)为半径的邻域是围绕P点的半径为R的小球（二维为小圆）。当且仅当P的邻域为满时，P在S的之内。当且仅当P的邻域不满不空时，P在S的边界上。基本概念——正则集合运算26PRPARAPBPBRBPARARB图4.9基于点的领域概念生成正则形体取点P和R，点P在集合A上的领域为PA，在集合B上的领域为PB。点R在集合A上的领域为RA，在集合B上的领域为RB。则：PA与PB的交集为空，所以P点不在A∩*B的边界上；RA与RB的交集不为空，所以R点在A∩*B的边界上；基本概念——正则集合运算27直接方式正则形体是三维空间中的点的正则集S={bS,iS};正则集S可以用边界点集bS和内部点集iS表示如果bS符合正则形体表面的性质，则bS所包围的空间就是iS基本概念——正则集合运算ABABA∪*BA∩*BA―*BABABb·AoutBb·Asharedb·Bb·BoutAb·BinAb·AinBb·Asharedb·Bb·Ashared-(b·B)b·AoutB-(b·BinA)图4.10正则集合运算A∪*B，A∩*B，A―*B的结果（实线表示结果形体的边界）B)}(b-sharedAbA),inB(b-B,outA{bB)-(AbB}bsharedAbA,inBbB,inA{bB)(AbB}bsharedAbA,outBbB,outA{bB)(Ab***××××=×××××=×××××=×∩∪29基本概念——平面多面体与欧拉公式简单多面体：与球拓扑等价的多面体。欧拉公式证明简单多面体的顶点数V、边数E和面数F满足如下关系：V-E+F=2。（必要条件）附加条件：1.每一条边必连接两个点；2.一条边被而且仅被两个面共享；3.至少要有三条边交于一个顶点。5-8+5=28-12+6=26-12+8=2图4.11简单多面体30基本概念——平面多面体与欧拉公式非简单多面体需对欧拉公式加以扩展。令H表示多面体表面上孔的个数，G表示贯穿多面体的孔的个数，C表示独立的、不相连接的多面体数，则扩展后的欧拉公式为：V-E+F-H=2(C-G)。图4.12非简单多面体24V-36E+15F-3H=2(1C-1G)31线框模型与实体模型（实体造型技术）可以将实体模型的表示大致分为三类：边界表示（Boundaryrepresentation,B-reps）构造实体几何表示空间分割（Space-partitioning）表示4.2三维形体的表示32多边形表面模型扫描表示构造实体几何法空间位置枚举表示八叉树BSP树OpenGL中的实体模型函数三维形体的表示33边界表示(B-reps)的最普遍方式是多边形表面模型，它使用一组包围物体内部的平面多边形，也即平面多面体，来描述实体。BCDVABCABDBCDACDABBCCAADBDCDABCD体面边顶点A多边形表面模型图4.16四面体及其点、边、面的关系34多边形表面模型——数据结构几何信息建立3张表：顶点表、边表和多边形表来存储几何数据。实体模型中，用多边形顶点坐标值以及多边形所在平面方程方式保存实体单个表面部分的空间方向信息线框模型的顶点表、边表和面边表多边形表面模型——数据结构多边形表面模型——数据结构已知三个不共线的点坐标V1(x1,y1)、V2(x2,y2)和V3(x3,y3)，求平面方程（Ax+By+Cz+D=0）的参数A、B、C、DA=y1(z2-z3)+y2(z3-z1)+y3(z1-z2)B=z1(x2-x3)+z2(x3-x1)+z3(x1-x2)(4-3)C=x1(y2-y3)+x2(y3-y1)+x3(y1-y2)D=-x1(y2z3-y3z2)-x2(y3z1-y1z3)-x3(y1z2-y2z1)平面法向量N为(A,B,C)约定：法向量指向面的外侧面。当多边形顶点序列指定为逆时针方向时，法向量方向满足右手法则。N法向量也可以通过向量叉积求得N=(V2-v1)╳(V3-V1)(4-4)已知法向量N和任意点P，平面方程为：N·P=-D(4-5)根据Ax+By+Cz+D的值可以判断点是否在面上、面外、面内。Ax+By+Cz+D=0点(x,y,z)在面上Ax+By+Cz+D0点(x,y,z)在面外Ax+By+Cz+D0点(x,y,z)在面内多边形表面模型——数据结构38多边形表面模型——数据结构拓扑信息：翼边结构表示（WingedEdgesStructure）E2E1E3E4F1V2V1F2E图4.19翼边结构表示39多边形表面模型——数据结构属性信息用属性表来存储多边形面的属性，指明物体透明度及表面反射度的参数和纹理特征等等。40多边形网格：三维形体的边界通常用多边形网格（polygonmesh）的拼接来模拟。例子多边形表面模型图4.20三角形带与四边形网格41扫描表示法（sweeprepresentation）一种基于图元(如一个点、一条线或一个面)，沿某一个给定轨迹移动而形成特定几何体的方法。包含两个要素一是作扫描运动的基本图形（截面）；二是扫描运动的方式。扫描表示（sweeprepresentation）图形B是梯形A绕Z轴作旋转扫描后形成的形体zBAyxO扫描表示（sweeprepresentation）43构造实体几何法（CSG，ConstructiveSolidGeometry）由两个实体间的并、交或差操作生成新的实体。BAAABB(a)A,B形体的并(b)A,B形体的差(c)A,B形体的交构造实体几何法图4.25构造实体几何法44在构造实体几何法中，集合运算的实现过程可以用一棵二叉树（称为CSG树）来描述。树的叶子是基本体素或是几何变换参数；树的非终端结点是施加于其子结点的正则集合算子（正则并、正则交和正则差）或几何变换的定义。构造实体几何法CSG树的形式一般定义为：CSG树::=体素叶子|CSG树集合运算结果CSG树|CSG树几何变换节点变换参数构造实体几何法构造实体几何法47构造实体几何法1234-11-10YXP1410YXP2(a)(b)CUTUUP1