《计算机图形学4(陈永强)》由会员分享，可在线阅读，更多相关《计算机图形学4(陈永强)（69页珍藏版）》请在金锄头文库上搜索。
1、1,如何在计算机中建立恰当的模型表示不同图形对象。如何组织图形对象的描述数据以使存储这些数据所要的空间最省，检索、处理这些数据的速度较快。,第四章 图形的表示与数据结构,2,基本概念三维形体的表示非规则对象的表示层次建模,图形的表示与数据结构,3,造型技术基本图形元素几何信息与拓扑信息坐标系实体的定义正则集合运算欧拉公式,4.1 基本概念,4,把研究如何在计算机中建立恰当的模型表示不同图形对象的技术称为造型技术。有两类图形对象： 规则对象：几何造型、几何模型。 不规则对象：过程式模拟。,基本概念造型技术,5,4.1.1基本概念基本图形元素,基本图形元素：图素或图元、体素。图素是指可以用一定的几
2、何参数和属性参数描述的最基本的图形输出元素。在二维图形系统中将基本图形元素称为图素或图元，在三维图形系统中称为体素。,4.1.1基本概念基本图形元素,点，0维线，一维面，二维环，二维体，三维,图形信息与非图形信息图形信息：点、线、面的位置和几何尺寸，及相互关系。非图形信息：线型、颜色、亮度及模拟分析用的质量、比重、体积等数据。,4.1.2基本概念几何信息与拓扑信息,8,图形信息几何信息：形体在欧氏空间中的位置和大小。拓扑信息：形体各分量（点、边、面）的数目及其相互间的连接关系。,4.1.2基本概念几何信息与拓扑信息,图4.1 拓扑信息,10,刚体运动：不改变图形上任意两点间的距离，也不改变图形
3、的几何性质的运动。拓扑运动：允许形体作弹性运动，即在拓扑关系中，对图形可随意地伸张扭曲。但图上各个点仍为不同的点，决不允许把不同的点合并成一个点。,基本概念几何信息与拓扑信息,11,建模坐标系（MC，Modeling Coordinate System），造型坐标系，局部坐标系用户坐标系（WC，World Coordinate System），整体坐标系，全局坐标系观察坐标系（VC，Viewing Coordinate System）规格化设备坐标系（NDC，Normalized Device Coordinate System）设备坐标系（DC，Device Coordinate Syste
4、m）,4.1.3基本概念坐标系,12,4.1.4基本概念实体,图4.2 带有悬挂边的立方体,4.1.4基本概念实体,三维形体（客观世界）正则形体（数学）刚性维数的一致性占据有限的空间边界的确定性封闭性,14,点的邻域：如果P是点集S的一个元素，那么点P的以R（R0）为半径的邻域指的是围绕点P的半径为R的小球（二维情况下为小圆）。开集的闭包：是指该开集与其所有边界点的集合并集，本身是一个闭集。正则集：由内部点构成的点集的闭包就是正则集，三维空间的正则集就是正则形体。,基本概念实体,15,基本概念实体,组成三维物体的点的集合可以分为两类： 内点：为点集中的这样一些点，它们具有完全包含于该点集的充分
5、小的邻域。边界点：不具备此性质的点集中的点。,16,基本概念实体,定义点集的正则运算r运算为：,正则运算即为先对物体取内点再取闭包的运算。rA称为A的正则集。,17,基本概念实体,图4.3 实体的例子,18,图4.4 正则形体,基本概念实体,19,正则形体（数学）二维流形实体（计算机）二维流形指的是对于实体表面上的任意一点，都可以找到一个围绕着它的任意小的邻域，该邻域与平面上的一个圆盘是拓扑等价的。,基本概念实体,图4.5 正则形体,20,实体：对于一个占据有限空间的正则形体，如果其表面是二维流形，则该正则形体为实体。,基本概念实体,21,有效实体的封闭性。把能够产生正则形体的集合运算称为正则
6、集合运算。,4.1.5基本概念正则集合运算,22,图4.6 集合运算与正则集合运算,基本概念正则集合运算,正则运算方法间接方式：先按照通常集合运算求出结果，然后再用一些规则加以判断；基于点集拓扑学的邻域概念。直接方式：定义出正则算子的表达式，直接得出符合正则形体定义的结果。,24,图4.7 基于点的邻域概念生成正则形体,基本概念正则集合运算,基本概念正则集合运算,ACISACIS是美国Spatial Technology公司推出的三维几何造型引擎，它集线框、曲面和实体造型于一体，并允许这三种表示共存于统一的数据结构中，为各种3D造型应用的开发提供了几何造型平台。,26,4.1.6基本概念平面多
7、面体与欧拉公式,平面多面体：多面体中最常见的一种，指表面由平面多边形构成的三维物体。欧拉公式证明简单多面体的顶点数V、边数E和面数F满足如下关系：V-E+F=2。非简单多面体需对欧拉公式加以扩展。令H表示多面体表面上孔的个数，G表示贯穿多面体的孔的个数，C表示独立的、不相连接的多面体数，则扩展后的欧拉公式为：V-E+F-H=2（C-G）。,27,基本概念平面多面体与欧拉公式,图4.9 平面多面体与欧拉公式,28,线框模型早期计算机图形生成技术，缺陷：第一，模型有二义性；第二，无面信息，易形成无效形体；第三，无曲面轮廓线，不能表示曲面信息。,4.2 三维形体的表示,29,实体模型（实体造型技术）
8、实体模型大致分为三类：边界表示（B-reps, Boundary representation）构造实体几何表示（CSG，Constructive Solid Geometry）空间分割（Space-partitioning）表示,4.2 三维形体的表示,30,多边形表面模型扫描表示构造实体几何法空间位置枚举表示八叉树BSP树OpenGL中的实体模型函数,三维形体的表示,31,边界表示(B-reps)的最普遍方式是多边形表面模型，它使用一组包围物体内部的平面多边形，也即平面多面体，来描述实体。,4.2.1多边形表面模型,图4.10 四面体及其点、边、面的关系,32,多边形表面模型数据结构,几何
9、信息建立3张表：顶点表、边表和多边形表来存储几何数据。实体模型中，用多边形顶点坐标值以及多边形所在平面方程方式保存实体单个表面部分的空间方向信息,33,多边形表面模型数据结构,拓扑信息：翼边结构表示（Winged Edges Structure）,图4.11 翼边结构表示,34,多边形表面模型数据结构,属性信息 用属性表来存储多边形面的属性，指明物体透明度及表面反射度的参数和纹理特征等等。,35,多边形网格：三维形体的边界通常用多边形网格（polygon mesh）的拼接来模拟。例子,多边形表面模型,图4.12 三角形带与四边形网格,36,扫描表示法（sweep representation）
10、可以利用简单的运动规则生成有效实体。包含两个要素一是作扫描运动的基本图形（截面）；二是扫描运动的方式。,4.2.2扫描表示（sweep representation）,37,构造实体几何法（CSG）由两个实体间的并、交或差操作生成新的实体。,4.2.3构造实体几何法,图4.13 构造实体几何法,38,在构造实体几何法中，集合运算的实现过程可以用一棵二叉树（称为CSG树）来描述。树的叶子是基本体素或是几何变换参数；树的非终端结点是施加于其子结点的正则集合算子（正则并、正则交和正则差）或几何变换的定义。,构造实体几何法,39,构造实体几何法,图4.14 由CSG树产生二维形体的实例,40,优点：如
11、果体素设置比较齐全，通过集合运算就可以构造出多种不同的符合需要的实体。缺点一：集合运算的中间结果难以用简单的代数方程表示，求交困难。缺点二：CSG树不能显式地表示形体的边界，因而无法直接显示CSG树表示的形体。,构造实体几何法,41,解决：光线投射算法,构造实体几何法,图4.15 光线投射算法(实体AB取ad，实体AB则取cb,实体A-B则取ab),42,空间位置枚举表示法将包含实体的空间分割为大小相同、形状规则（正方形或立方体）的体素，然后，以体素的集合来表示图形对象。二维情况，常用二维数组存放。三维情况下，常用三维数组pijk来存放。,4.2.4空间位置枚举表示,43,特点穷举法，可表示任
12、何实体。易实现实体的集合及体积计算等。无明确边界信息，不适合图形显示。需大量存储空间-分割检索法。,4.2.4空间位置枚举表示,44,八叉树（octrees）又称为分层树结构，它对空间进行自适应划分，采用具有层次结构的八叉树来表示实体。对空间位置枚举表示法的空间分割方法的改进，为自适应划分。,4.2.5八叉树,45,八叉树四叉树,图4.16 二维图的四叉树表示,46,八叉树,图4.17 三维空间分成八个卦限及其节点表示,47,二叉空间分割（Binary Space Partitioning，BSP）树方法是一种类似于八叉树的空间分割方法，它每次将一实体用任一位置和任一方向的平面分为二部分（不同
13、于八叉树方法的每次将实体用平行于笛卡尔坐标平面的三个两两垂直的平面分割）。,4.2.6BSP树,48,GLUT库中的多面体函数,4.2.7OpenGL中的实体模型函数,表4.1 GLUT生成规则多面体的函数,49,GLUT库中的二、三次曲面绘制实体或线框球面 void glutSolidSphere/glutWireSphere (GLdouble radius, GLint slices, GLint stacks);绘制实体或线框圆锥面 void glutSolidCone/glutWireCone (GLdouble radius, GLdouble height, GLint slic
14、es, GLint stacks);,OpenGL中的实体模型函数,50,绘制实体或线框圆环 void glutSolidTorus/ glutWireTorus(GLdouble innerRadius, GLdouble outerRadius, GLint slices,GLint stacks);绘制实体或线框茶壶 void glutSolidTeapot/glutWireTeapot (GLdouble size);,OpenGL中的实体模型函数,51,GLU二次曲面函数定义一个二次曲面 GLUquadricObj *sphere;激活二次曲面绘制器 sphere = gluNewQ
15、uadric( );指定二次曲面的绘制方式 gluQuadricDrawStyle(sphere, GLU_LINE);,OpenGL中的实体模型函数,52,绘制二次曲面 gluSphere(sphere, radius, slices, stacks); gluCylinder(sphere,baseRadius,topRadius, height, slices, stacks)； gluDisk(sphere,innerRadius,outerRadius, slices, stacks)；,OpenGL中的实体模型函数,53,4.3非规则对象的表示,分形几何形状语法粒子系统基于物理的建模数据场的可视化,54,分形几何物体具有一个基本特征：无限的自相似性。无限的自相似性是指物体的整体和局部之间细节的无限重现。,4.3.1分形几何(fractal geometry),55,分形物体描述内容：分形维数生成过程,分形几何(fractal geometry),56,分形维数，又称分数维数,4 = 228 = 23N = KD D=lgN/lgk,K为边长缩小倍数； N为边长缩小后产生的新形体个数。,分形几何(fractal geometry),
