《计算机图形学chap4图形的表示与数据结构ppt课件.ppt》由会员分享，可在线阅读，更多相关《计算机图形学chap4图形的表示与数据结构ppt课件.ppt（78页珍藏版）》请在三一办公上搜索。
1、计算机图形学基础,华东理工大学计算机系 谢晓玲,2,如何在计算机中建立恰当的模型表示不同图形对象。如何组织图形对象的描述数据以使存储这些数据所要的空间最省，检索、处理这些数据的速度较快。,第四章 图形的表示与数据结构,3,基本概念三维形体的表示非规则对象的表示层次建模,图形的表示与数据结构,4,造型技术基本图形元素几何信息与拓扑信息坐标系实体的定义正则集合运算欧拉公式,4.1 基本概念,5,把研究如何在计算机中建立恰当的模型表示不同图形对象的技术称为造型技术。有两类图形对象： 规则对象：几何造型、几何模型。 不规则对象：过程式模拟。,基本概念造型技术,6,规则对象：用欧氏几何描述的对象几何造型
2、：规则对象的造型几何模型：在几何造型中描述的规则对象不规则对象：不能用欧氏几何描述的对象过程式模拟：用一个简单的模型以及少量的参数来表示一类对象,基本概念造型技术,7,基本概念基本图形元素,基本图形元素：图素或图元、体素。图素是指可以用一定的几何参数和属性参数描述的最基本的图形输出元素。在二维图形系统中将基本图形元素称为图素或图元，在三维图形系统中称为体素。常见基本图形元素：点、线、面、环、体、,8,图形信息几何信息：形体在欧氏空间中的位置和大小。拓扑信息：形体各分量（点、边、面）的数目及其相互间的连接关系。非图形信息线性、颜色、亮度、,基本概念几何信息与拓扑信息,图4.3 9种拓扑信息,10
3、,刚体运动：不改变图形上任意两点间的距离，也不改变图形的几何性质的运动。拓扑运动（弹性运动）：在拓扑关系中，对图形可随意地伸张扭曲。但图上各个点仍为不同的点，决不允许把不同的点合并成一个点。,基本概念几何信息与拓扑信息,11,拓扑等价：一个图形作弹性运动可使之与另一个图形重合。拓扑性质：与拓扑等价的图形所具有的性质。,基本概念几何信息与拓扑信息,12,建模坐标系(MC,Modeling Coordinate System)：造型坐标系、局部坐标系用户坐标系(WC,World Coordinate System)：全局坐标系、世界坐标系观察坐标系(VC,Viewing Coordinate Sy
4、stem)：指定裁剪空间、定义观察（投影）平面规格化设备坐标系(NDC,Normalized Device coordinate System)：定义视图区设备坐标系(DC,Device Coordinate System)：通常是像素或位图的坐标系,基本概念坐标系,13,基本概念实体的定义,图4.4 带有悬挂边的立方体是没有意义的形体,实体造型必须保证形体是有效的，即“客观存在”：刚性：即具有一定的形状维数的一致性：在三维空间中，一个物体的各部分均应是三维的有限的空间：体积有限边界的确定：根据边界可以区分物体的内部及外部封闭性：一个有效的实体经刚体运动、集合运算后仍然是有效的实体,14,基本
5、概念实体的定义,三维空间中的物体是一个内部连通的三维点集连通性：位于物体表面上的任意两个点都可以用物体表面的一条路经连接起来有界性：物体表面可将空间分为互不连通的两部分，其中一部分是有界的非自相交性：物体的表面不能自相交可定向性：物体表面的两侧可以定义物体的内侧或外侧闭合性：每一条边有且仅有两个顶点；每一条边连接两个或两个以上的面,15,点集拓扑学的定义：点的领域：如果P是点集S的一个元素，那么点P的以R（R0）为半径的领域指的是围绕点P的半径为R的小球（二维情况下为小圆）。开集的闭包：是指该开集与其所有边界点的集合并集，本身是一个闭集。正则集：由内部点构成的点集的闭包就是正则集，三维空间的正
6、则集就是正则形体。,基本概念实体的定义,16,基本概念实体的定义,组成三维物体的点的集合可以分为两类： 内点为点集中的这样一些点，它们具有完全包含于该点集的充分小的领域。边界点：不具备此性质的点集中的点。,17,基本概念实体的定义,定义点集的正则运算r运算为：iA为A的全体内点的集合，是一个开集。再取闭包的运算c 。ciA为A的全体内点的闭包，是一个闭集。rA称为A的正则集。,18,基本概念实体的定义,图4.5 实体的例子,19,图4.6 正则形体但不是实体模型的描述对象,基本概念实体的定义,实体应具有二维流形性质。二维流形指的是对于实体表面上的任意一点，都可以找到一个围绕着它的任意小的领域，
7、该领域与平面上的一个圆盘是拓扑等价的。,20,即该领域与圆盘之间存在着连续的一一对应关系。如果实体表面上的一条边所连接的面多于两个，那么这条边上任意一个点的小领域都包含来自这些面上的点，因此与圆盘不是拓扑等价的。,基本概念实体的定义,图4.7 正则形体,21,实体：对于一个占据有限空间的正则形体，如果其表面是二维流形，则该正则形体为实体。,基本概念实体的定义,22,有效实体的封闭性。把能够产生正则形体的集合运算称为正则集合运算。,基本概念正则集合运算,23,图4.8 集合运算与正则集合运算（正则交）,基本概念正则集合运算,24,两种方法实现正则运算：间接方式基于点集拓扑学的领域概念，先按通常的
8、集合运算求出集合，然后再用一些规则加以判断直接方式定义正则集合算子的表达式，直接求得正则集合,基本概念正则集合运算,25,间接方式邻域：如果P是点集S的一个元素，那么P点以R(0)为半径的邻域是围绕P点的半径为R的小球（二维为小圆）。当且仅当P的邻域为满时，P在S的之内。当且仅当P的邻域不满不空时，P在S的边界上。,基本概念正则集合运算,26,图4.9 基于点的领域概念生成正则形体取点P和R，点P在集合A上的领域为PA，在集合B上的领域为PB。点R在集合A上的领域为RA，在集合B上的领域为RB。则：PA与PB的交集为空，所以P点不在A*B的边界上； RA与RB的交集不为空，所以R点在A*B的边
9、界上；,基本概念正则集合运算,27,直接方式正则形体是三维空间中的点的正则集S=bS,iS;正则集S可以用边界点集bS和内部点集iS表示如果bS符合正则形体表面的性质，则bS所包围的空间就是iS,基本概念正则集合运算,图4.10 正则集合运算A*B，A*B，A*B的结果（实线表示结果形体的边界）,29,基本概念平面多面体与欧拉公式,简单多面体：与球拓扑等价的多面体。欧拉公式证明简单多面体的顶点数V、边数E和面数F满足如下关系：V-E+F=2。（必要条件）附加条件：每一条边必连接两个点；一条边被而且仅被两个面共享；至少要有三条边交于一个顶点。,图4.11 简单多面体,30,基本概念平面多面体与欧
10、拉公式,非简单多面体需对欧拉公式加以扩展。令H表示多面体表面上孔的个数，G表示贯穿多面体的孔的个数，C表示独立的、不相连接的多面体数，则扩展后的欧拉公式为：V-E+F-H=2(C-G)。,图4.12 非简单多面体,31,线框模型与实体模型（实体造型技术）可以将实体模型的表示大致分为三类：边界表示（Boundary representation, B-reps）构造实体几何表示空间分割（Space-partitioning）表示,4.2 三维形体的表示,32,多边形表面模型扫描表示构造实体几何法空间位置枚举表示八叉树BSP树OpenGL中的实体模型函数,三维形体的表示,33,边界表示(B-rep
11、s)的最普遍方式是多边形表面模型，它使用一组包围物体内部的平面多边形，也即平面多面体，来描述实体。,多边形表面模型,图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
12、)+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=(V2-v1)(V3-V1) (4-4)已知法向量N和任意点P，平面方程为：NP=-D (4-5)根据Ax+By+Cz+D的值可以判断点是否在面上、面外、面内。Ax+By+Cz+D=0点(x,y,z)在面
13、上Ax+By+Cz+D0点(x,y,z)在面外Ax+By+Cz+D0点(x,y,z)在面内,多边形表面模型数据结构,38,多边形表面模型数据结构,拓扑信息：翼边结构表示（Winged Edges Structure）,图4.19 翼边结构表示,39,多边形表面模型数据结构,属性信息 用属性表来存储多边形面的属性，指明物体透明度及表面反射度的参数和纹理特征等等。,40,多边形网格：三维形体的边界通常用多边形网格（polygon mesh）的拼接来模拟。例子,多边形表面模型,图4.20 三角形带与四边形网格,41,扫描表示法（sweep representation）一种基于图元(如一个点、 一条
14、线或一个面)，沿某一个给定轨迹移动而形成特定几何体的方法。包含两个要素一是作扫描运动的基本图形（截面）；二是扫描运动的方式。,扫描表示（sweep representation）,图形B是梯形A绕Z轴作旋转扫描后形成的形体,扫描表示（sweep representation）,43,构造实体几何法（CSG，Constructive Solid Geometry）由两个实体间的并、交或差操作生成新的实体。,构造实体几何法,图4.25 构造实体几何法,44,在构造实体几何法中，集合运算的实现过程可以用一棵二叉树（称为CSG树）来描述。树的叶子是基本体素或是几何变换参数；树的非终端结点是施加于其子结
15、点的正则集合算子（正则并、正则交和正则差）或几何变换的定义。,构造实体几何法,CSG树的形式一般定义为： : =| | ,构造实体几何法,构造实体几何法,47,构造实体几何法,图4.26 由CSG树产生二维形体的实例,48,优点：如果体素设置比较齐全，通过集合运算就可以构造出多种不同的符合需要的实体。缺点一：集合运算的中间结果难以用简单的代数方程表示，求交困难。缺点二：CSG树不能显式地表示形体的边界，因而无法直接显示CSG树表示的形体。,构造实体几何法,49,解决：光线投射算法,构造实体几何法,图4.27 光线投射算法(实体AB取ad，实体AB则取cb,实体A-B则取ab),50,空间位置枚
16、举表示法将包含实体的空间分割为大小相同、形状规则（正方形或立方体）的体素，然后，以体素的集合来表示图形对象。二维情况，常用二维数组存放。三维情况下，常用三维数组pijk来存放。优点：可以表示任何实体、容易实现集合运算和体积计算；缺点：占用空间大、没有边界信息。,空间位置枚举表示,51,分割检索法：将实体所占据的立体空间沿坐标轴方向分割,用一棵三层的树结构表示实体。先分割为二维的片。如片内的编码完全相同，则不需要再分割，否则再分割为一维的条。如条内的编码完全相同，则不需要再分割，否则再分割为单元。,空间位置枚举表示,52,空间位置枚举表示,X,53,八叉树（octrees）又称为分层树结构，它对
17、空间进行自适应划分，采用具有层次结构的八叉树来表示实体，类似二维实体的四叉树（Quadtree）表示。,八叉树,54,八叉树四叉树,将平面对象用矩形包围起来，并分为4个区域（象限）如(a)，作为四叉树的根节点。F(Full)完全被覆盖B(Boundary)部分被覆盖E(Empty)完全没有被覆盖若根节点处于F或E，则四叉树建立完毕。否则，将其等分为4个区域，为第1层子节点。,55,八叉树四叉树,继续考察4个区域的状态是否是B，如(b)。对于状态为B的象限（非均质象限）再细分为4个小象限，形成第2层子节点，直到给定精度下不出现B象限为止。,图4.29 二维平面分成四个象限及其四叉树表示,56,八
18、叉树,图4.30 三维空间分成八个卦限及其节点表示,类似，将三维实体分为8个卦限（Octants），产生8个子节点，每个节点代表一个小三维实体，最后可得八叉树。,57,八叉树,物体之间的集合运算（并、交、差）在八叉树表示中具有十分简单的形式。只需要同时遍历参加集合运算的两物体相应的八叉树，就可以获得拼合体的八叉树，而无需进行复杂的求交运算。很容易计算实体的整体性质，如质量、体积等。容易实现隐藏线和隐藏面的消除。不能精确地表示一个实体的；几何变换也比较困难。所需要的存储容量较大,58,二叉空间分割（Binary Space Partitioning，BSP）树方法是一种类似于八叉树的空间分割方法
19、，它每次将一实体用任一位置和任一方向的平面分为二部分（不同于八叉树方法的每次将实体用平行于笛卡尔坐标平面的三个两两垂直的平面分割）。,BSP树,59,GLUT库中的多面体函数,OpenGL中的实体模型函数,表4.1 GLUT生成规则多面体的函数,60,GLUT库中的二、三次曲面绘制实体或线框球面 void glutSolidSphere/glutWireSphere (GLdouble radius, GLint slices, GLint stacks);绘制实体或线框圆锥面 void glutSolidCone/glutWireCone (GLdouble radius, GLdouble
20、 height, GLint slices, GLint stacks);,OpenGL中的实体模型函数,61,绘制实体或线框圆环 void glutSolidTorus/ glutWireTorus(GLdouble innerRadius, GLdouble outerRadius, GLint slices,GLint stacks);绘制实体或线框茶壶 void glutSolidTeapot/glutWireTeapot (GLdouble size);,OpenGL中的实体模型函数,62,GLU二次曲面函数定义一个二次曲面 GLUquadricObj *sphere;激活二次曲面绘
21、制器 sphere = gluNewQuadric( );指定二次曲面的绘制方式 gluQuadricDrawStyle(sphere, GLU_LINE);,OpenGL中的实体模型函数,63,绘制二次曲面 gluSphere(sphere, radius, slices, stacks); gluCylinder(sphere,baseRadius,topRadius, height, slices, stacks)； gluDisk(sphere,innerRadius,outerRadius, slices, stacks)；,OpenGL中的实体模型函数,64,非规则对象的表示,分形
22、几何形状语法粒子系统基于物理的建模数据场的可视化,65,分形几何物体具有一个基本特征：无限的自相似性。无限的自相似性是指物体的整体和局部之间细节的无限重现。,分形几何(fractal geometry),66,分形维数，又称分数维数,4 = 228 = 23N = KD D=lgN/lgk,K为边长缩小倍数； N为边长缩小后产生的新形体个数。,分形几何(fractal geometry),图4.18 分形维数,67,生成过程：初始生成元（initiator）、生成元（generator）。实例,图4.19 生成过程,分形几何(fractal geometry),68,形状语法,形状语法（sha
23、pe grammars）：给定一组产生式规则，形状设计者可以在从给定初始物体到最终物体结构的每一次变换中应用不同的规则。产生式规则可以用具有图形运算能力的数学式或其他过程性方法结合实现。,69,粒子系统,用于模拟自然景物或模拟其它非规则形状物体展示“流体”性质的一个方法是微粒系统（particle systems）。这一方法尤其擅长描述随时间变化的物体。微粒运动的模拟方式：随机过程模拟、运动路径模拟、力学模拟。,70,基于物理的建模,基于物理的建模方法：描段与层次建模述了物体在内外力相互作用下的行为。通常用一组网格结点来逼近物体。网格结点间取为柔性连接，再考虑贯穿物体网格的力传递。,71,数据
24、场的可视化,科学计算可视化（scientific visualization）指的是运用计算机图形学和图像处理技术，将科学计算过程中及计算结果的数据转换为图形及图像在屏幕上显示出来并进行交互处理的理论、方法和技术。,72,4.4 层次模型,段与层次模型层次模型的实现OpenGL中的层次模型,73,段与层次模型,具有逻辑意义的有限个图素（或体素）及其附加属性的集合称为段，或者称为图段（二维空间中）、结构和对象。段是可以嵌套段与基本图形元素的区别在于，基本图形元素是用数据来描述的，而段是用规则来描述的。,74,段与层次模型,段一般具有三个特性：可见性、醒目性和可选择性（可由交互式输入设备来选择）。
25、利用段的嵌套来构造复杂的对象或系统。,图4.20 自行车及其层次描述,75,存储简单：一个段虽然在图中各处出现，但他的几何和拓扑信息只要保存一次。编辑简单：删除、移动及缩放操作都可以以段为单位。,段与层次模型,76,层次模型的实现,系统的层次模型可以通过将一个图段嵌套到另一个图段中形成图段树来创建。不同的段和基本图形元素在各自的建模坐标系中定义。图层。通过把功能相同的部分归类，并将它们绘制在同一层上，有助于图形的理解和管理。一般图层不再嵌套。,77,OpenGL中层次模型的实现,显示列表的创建 glNewList( listID, listMode );glutSolidCube(2.0); glEndList();显示列表的执行 void glListBase(GLuint offsetValue);,78,OpenGL中层次模型的实现,多级显示列表 OpenGL支持创建多级显示列表，即在glNewList和glEndLsit函数对之间允许调用glCallList函数来执行其他显示列表。显示列表的删除 void glDeleteLists(GLuint listID, GLsizei range);,
