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

1 如何在计算机中建立恰当的模型表示不同图形对象 如何组织图形对象的描述数据以使存储这些数据所要的空间最省 检索 处理这些数据的速度较快 第四章图形的表示与数据结构 2 基本概念三维形体的表示非规则对象的表示层次建模 图形的表示与数据结构 3 造型技术基本图形元素几何信息与拓扑信息坐标系实体的定义正则集合运算欧拉公式 4 1基本概念 4 把研究如何在计算机中建立恰当的模型表示不同图形对象的技术称为造型技术 有两类图形对象 规则对象 几何造型 几何模型 几何信息和拓扑信息 不规则对象 过程式模拟 基本概念 造型技术 5 基本概念 基本图形元素 基本图形元素 图素或图元 体素 图素是指可以用一定的几何参数和属性参数描述的最基本的图形输出元素 包括点 线 面 环 体等 在二维图形系统中将基本图形元素称为图素或图元 在三维图形系统中称为体素 1 点 为0维几何元素 是形体最基本的元素 自由曲线 曲面或其他形体均可用有序的点集来表示 点集及其连接关系的存储 2 线 一维几何元素 是两个邻面或多个邻面的交界3 面 二维几何元素 是形体上一个有限 非零的区域 由一个外环和若干内环界定其范围 具有方向性 由其外法线矢量方向定义 4 环 有序 有向边组成的面的封闭边界 外环中其边逆时针排序 内环顺时针排序 5 体 三维几何元素 由封闭表面围成的空间 7 图形信息与非图形信息几何信息 形体在欧氏空间中的位置和大小 拓扑信息 形体各分量 点 边 面 的数目及其相互间的连接关系 基本概念 几何信息与拓扑信息 图4 1拓扑信息 9 刚体运动 不改变图形上任意两点间的距离 也不改变图形的几何性质的运动 拓扑运动 允许形体作弹性运动 即在拓扑关系中 对图形可随意地伸张扭曲 但图上各个点仍为不同的点 决不允许把不同的点合并成一个点 基本概念 几何信息与拓扑信息 10 建模坐标系 ModelingCoordinateSystem 局部坐标系 用户坐标系 全局坐标系 世界坐标系 观察坐标系 ViewingCoordinateSystem 指定裁剪空间 定义投影平面 将用户坐标转换成规格化的设备坐标 规格化设备坐标系 NormalizedDevicecoordinateSystem 定义视图区 设备坐标系 DeviceCoordinateSystem 图形输入 输出的设备坐标系 如屏幕等 基本概念 坐标系 11 基本概念 实体 图4 2带有悬挂边的立方体 客观存在的三维形体的5条性质 刚性 一个物体必须具有一定的形状维数的一致性 三维空间种 一个物体的各部分均应是三维的 不能有悬挂的或孤立边界占据有限的空间 体积有限 边界的确定性 根据物体的边界可以确定物体内部与外部 封闭性 经过一系列刚体运动及任意序列的集合运算后 依然是有效的物体 三维空间中的物体是一个内部连通的三维点集 三维物体表面必须具有以下5条性质 连通性 位于物体表面上的任意两个点都可用实体表面上的一条路径连接起来 有界性 物体表面可将空间分为互不连通的两部分 其中一部分是有界的非自相交性 物体的表面不能自相交可定向性 物体表面的两侧可明确定义出属于物体的内侧或外侧闭合性 物体表面的闭合性是由表面上多边形网格各元素的拓扑关系决定的 即每一条边有且只有两个顶点 每一条边连接来年各个或两个以上的面 14 点的领域 如果P是点集S的一个元素 那么点P的以R R 0 为半径的领域指的是围绕点P的半径为R的小球 二维情况下为小圆 开集的闭包 是指该开集与其所有边界点的集合并集 本身是一个闭集 三维物体的点的集合可以分为内部点和边界点来那个部分 正则集 由内部点构成的点集的闭包就是正则集 三维空间的正则集就是正则形体 也就是三维有效物体 基本概念 实体 点集拓扑学的角度 15 基本概念 实体 组成三维物体的点的集合可以分为两类 内部点为点集中的这样一些点 它们具有完全包含于该点集的充分小的领域 边界点 不具备此性质的点集中的点 16 基本概念 实体 定义点集的正则运算r运算为 正则运算即为先对物体取内点再取闭包的运算 r A称为A的正则集 17 基本概念 实体 图4 3实体的例子 18 图4 4正则形体 基本概念 实体 19 二维流形指的是对于实体表面上的任意一点 都可以找到一个围绕着它的任意小的领域 该领域与平面上的一个圆盘是拓扑等价的 基本概念 实体 图4 5正则形体 20 实体 对于一个占据有限空间的正则形体 如果其表面是二维流形 则该正则形体为实体 基本概念 实体 21 有效实体的封闭性 把能够产生正则形体的集合运算称为正则集合运算 基本概念 正则集合运算 22 图4 6集合运算与正则集合运算 基本概念 正则集合运算 23 图4 7基于点的领域概念生成正则形体 基本概念 正则集合运算 图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 基本概念 平面多面体与欧拉公式 图4 9平面多面体与欧拉公式 27 线框模型与实体模型 线框模型由定义一个物体边界的直线和曲线组成 可以将实体模型的表示大致分为三类 边界表示 用一组曲面 或平面 来描述物体 这些曲面将物体分为内部和外部 构造实体几何表示空间分割 将包含物体的空间划分成一组非常小的非重叠的连续实体 表示 4 2三维形体的表示 28 多边形表面模型 使用一组包围物体内部的平面多边形来描述实体 扫描表示构造实体几何法空间位置枚举表示八叉树BSP树OpenGL中的实体模型函数 三维形体的表示 29 边界表示 B reps 的最普遍方式是多边形表面模型 它使用一组包围物体内部的平面多边形 也即平面多面体 来描述实体 需要设计有效的数据结构来处理面 边 点 多边形表面模型 图4 10四面体及其点 边 面的关系 30 多边形表面模型 数据结构 几何信息 几何表 建立3张表 顶点表 边表和多边形表来存储几何数据 实体模型中 用多边形顶点坐标值以及多边形所在平面方程方式保存实体单个表面部分的空间方向信息 31 多边形表面模型 数据结构 拓扑信息 翼边结构表示 WingedEdgesStructure 图4 11翼边结构表示 32 多边形表面模型 数据结构 属性信息用属性表来存储多边形面的属性 指明物体透明度及表面反射度的参数和纹理特征等等 实体测试条件 1 每个顶点至少是两条边的端点2 每条边至少是一个多边形的部分3 每个多边形式封闭的4 每个多边形至少有一条公共边5 如果多边形表包含指向多边形边的指针 则每一个被指针指向的边有一个逆指针指回到多边形 33 多边形网格 三维形体的边界通常用多边形网格 polygonmesh 的拼接来模拟 三角形和四边形 例子 多边形表面模型 图4 12三角形带与四边形网格 34 扫描表示法 sweeprepresentation 可以利用简单的运动规则生成有效实体 包含两个要素一是作扫描运动的基本图形 截面 二是扫描运动的方式 平移 旋转 对称变换 扫描表示 sweeprepresentation 35 构造实体几何法 CSG ConstructiveSolidGeometry 由两个实体间的并 交或差操作生成新的实体 构造实体几何法 图4 13构造实体几何法 36 在构造实体几何法中 集合运算的实现过程可以用一棵二叉树 称为CSG树 来描述 树的叶子是基本体素或是几何变换参数 树的非终端结点是施加于其子结点的正则集合算子 正则并 正则交和正则差 或几何变换的定义 构造实体几何法 37 图4 14由CSG树产生二维形体的实例 38 优点 如果体素设置比较齐全 通过集合运算就可以构造出多种不同的符合需要的实体 缺点一 集合运算的中间结果难以用简单的代数方程表示 求交困难 缺点二 CSG树不能显式地表示形体的边界 因而无法直接显示CSG树表示的形体 构造实体几何法 39 解决 光线投射算法 构造实体几何法 图4 15光线投射算法 实体A B取ad 实体A B则取cb 实体A B则取ab 40 空间位置枚举表示法将包含实体的空间分割为大小相同 形状规则 正方形或立方体 的体素 然后 以体素的集合来表示图形对象 二维情况 常用二维数组存放 三维情况下 常用三维数组p i j k 来存放 空间位置枚举表示 41 八叉树 octrees 又称为分层树结构 它对空间进行自适应划分 采用具有层次结构的八叉树来表示实体 八叉树 42 八叉树 四叉树 图4 16二维图的四叉树表示 43 八叉树 图4 17三维空间分成八个卦限及其节点表示 44 二叉空间分割 BinarySpacePartitioning BSP 树方法是一种类似于八叉树的空间分割方法 它每次将一实体用任一位置和任一方向的平面分为二部分 不同于八叉树方法的每次将实体用平行于笛卡尔坐标平面的三个两两垂直的平面分割 BSP树 45 GLUT库中的多面体函数 OpenGL中的实体模型函数 表4 1GLUT生成规则多面体的函数 46 GLUT库中的二 三次曲面绘制实体或线框球面voidglutSolidSphere glutWireSphere GLdoubleradius GLintslices GLintstacks 绘制实体或线框圆锥面voidglutSolidCone glutWireCone GLdoubleradius GLdoubleheight GLintslices GLintstacks OpenGL中的实体模型函数 47 绘制实体或线框圆环voidglutSolidTorus glutWireTorus GLdoubleinnerRadius GLdoubleouterRadius GLintslices GLintstacks 绘制实体或线框茶壶voidglutSolidTeapot glutWireTeapot GLdoublesize OpenGL中的实体模型函数 48 GLU二次曲面函数定义一个二次曲面GLUquadricObj sphere 激活二次曲面绘制器sphere gluNewQuadric 指定二次曲面的绘制方式gluQuadricDrawStyle sphere GLU LINE OpenGL中的实体模型函数 49 绘制二次曲面gluSphere sphere radius slices stacks gluCylinder sphere baseRadius topRadius height slices stacks gluDisk sphere innerRadius outerRadius slices stacks OpenGL中的实体模型函数 50 非规则对象的表示 分形几何形状语法粒子系统基于物理的建模数据场的可视化 51 分形几何物体具有一个基本特征 无限的自相似性 无限的自相似性是指物体的整体和局部之间细节的无限重现 分形几何 fractalgeometry 52 分形维数 又称分数维数 4 228 23N KDD lgN lgk K为边长缩小倍数 N为边长缩小后产生的新形体个数 分形几何 fractalgeometry 图4 18分形维数 53 生成过程 初始生成元 initiator 生成元 generator 实例 图4 19生成过程 分形几何 fractalgeometry 海岸线长度问题 二十世纪七十年代 法国数学家曼德尔勃罗特在他的著作中讨论英国海岸线的长度 他发现 这个问题取决于测量所使用的尺度 采用公里做单位 一些几米和几十米的曲折会被忽略 如果采用米做单位 测得的长度会曾加 但厘米以下的量仍然无法反映 测量单位的缩小使测得的长度曾加 由于在自然尺度之间有许多个数量级 这种曾加不会停止 海岸线的长度会趋于无限长 也就是说 长度不是海岸线的定量特征 数学的不规则图形 实际上 在曼德尔勃朗特的问题提出之前 数学家就曾经构造过多种不规则的几何图形 他们具有和海岸线相似的性质 Cantor集 Cantor在1883年构造了如下一类集合 取一段欧式长度为l的直线段 将该线段三等分 去掉中间的一段 剩下两段 再将剩下的两段分别三等分 各去掉中间的一段 剩下四段 将这个操作进行下去 直至无穷 可得到一个离散的点集 点数趋于无穷多 而长度趋于零 经无限次操作所得到的离散点集称为Cantor集 Koch雪花线 瑞典数学家科赫 H vonKoch 在1904年提出了一种曲线 它的生成方法是把一条直线段分成三段 将中间的一段用夹角为60度的两条等长折线来代替 形成一个生成元 然后再把每个直线段用生成元进行代换 经无穷次迭代后就呈现出一条有无穷多弯曲的Koch曲线 Koch曲线 Koch曲线的生成过程 第0步 第1步 Koch曲线的生成过程 第2步 第3步 Koch曲线与雪花曲线 连接在一起的三段Koch曲线构成一个雪花曲线 随机Koch曲线 对海岸线的模拟 Koch曲线的一些基本性质 Koch曲线具有与Cantor集 Sierpinski垫片类似的性质 长度等于无穷 Sierpinski集 首先 将一个等边三角形四等分 得到四个小等边三角形 去掉中间的一个 保留它的边 将剩下的三个小三角形再分别进行四等分 并分别去掉中间的一个 保留它的边 重复操作直至无穷 得到一个面积为零 线的欧式长度趋于无穷大的图形 这个图形被人们称为谢尔宾斯基缕垫 Sierpinsk垫片的生成过程 第0步 第1步 Sierpinsk垫片的生成过程 第2步 第3步 Sierpinsk垫片 Sierpinski地毯 其次 将一个正方形九等分 去掉中间的一个 保留四条边 剩下八个小正方形 将这九个小正方形再分别进行九等分 各自去掉中间的一个保留它们的边 重复操作直至无穷 Sierpinski地毯 第三 对一个正六面体 将它的每条边进行三等分 即对正六面体进行27等分 去掉体心和面心处的7个小正六面体 剩下20个小正六面体 并保留它们的表面 重复操作直无穷 得到的图形 体积趋于零 而其表面的欧式面积趋于无穷大 Sierpinski海绵 Sierpinski集的共同特点 它们都是经典几何无法描述的图形 是一种 只有皮没有肉 的几何集合 它们都具有无穷多个自相似的内部结构 任何一个分割后的图形放大后都是原来图形的翻版 问题在哪里 以上是一些经典几何意义下的 病态 图形 以Koch曲线为例 以一维来度量它 它的长度趋于无穷 而以二维来度量它 它的面积为零 那么 它究竟是几维图形 1维 2维 1 维吗 经典的维度定义有问题吗 经典几何的维度定义 在经典几何下 点被定义成0维的 点没有长度 直线被定义成1维 只有长度 没有面积 平面图形被定义成2维的 有面积 没有体积 立体图形是3维的 有体积 经典几何讨论的维度都是整数 它们的数值与决定几何形状的变量个数及自由度是一致的 这是一个很自然的想法 换一个角度看维度 根据相似性来看线段 正方形和立方体的维数 首先把线段 正方形和立方体的边两等分 这样 线段成为长度一半的两条线段 正方形变成边长为原来边长1 2的四个小正方形 而立方体而成为八个小立方体 边长为原来边长的1 2 原来的线段 正方形和立方体分别由2 4 8个把全体分成1 2的相似形组成 而2 4 8可改写成2的1 2 3次方 这里的1 2 3分别与其图形的经验维数相一致 相似维度的定义 一般地 如果某图形是由把全体缩小为1 a的aD个相似图形构成的 那么此指数D就具有维度的意义 此维数被称为相似维数 相似维数常用DS表示 按照定义 DS完全没有是整数的必要 如某图形是由全体缩小1 a的b个相似形组成 则DS b a 我们可以以此计算上述几种图形的相似维度 Koch曲线 4 3 1 2618Cantor集 2 3 0 6309Sierpinski集 缕垫 3 2 1 5850地毯 8 3 1 8927海绵 20 3 2 7268 从以上图形的生成方式来看 大体上有两种方式 第一种是从初始图形E0按一定原则往下 挖 得到的新图形的维数小于E0的欧式维数 常称为降维生成 第二种是在初始图形E0的基础上增加一些线或面 得到的图形E的维数大于E0的欧式维数 这种生成方式常称为升维生成 相似维数的定义具有很大的局限性 因为只用对具有严格的自相似性的分形 才能使用这个维数 定义适用于包括随机图形在内的任意的维数是很必要的 波恩大学数学家豪斯道夫1919年从测量的角度引进了Hausdorff维数 分形的定义 定义1 如果一个集合在欧式空间中的Hausdorff维数DH恒大于其拓扑维数DT 则称该集合为分形集 简称分形 由Mandelbrot在1982年提出 四年后 他又提出了一个更是实用的定义 定义2 组成部分以某种方式与整体相似的形体叫分形 分形理论的应用 生物学 肺 人肺的分形维数约为2 17 血管 血管直径分布的分形维数约为2 3 人脑 人脑表面的皱纹的分形维数约为2 73 2 79 蛋白质 地球物理学 海岸线 河流的干流和支流分布 地震研究 物理学和化学 超导 固体表面 高分子 天文学 材料科学 计算机图形学 经济学 语言学和情报学 分形的自然观与世界观 递归性 宇宙的创生 生命的生成 思维的生成 维数与空间 马赫多维原子理论 物理空间的变维性 变维的中国文化根源 分形山 分形树叶 分形树叶 续1 87 形状语法 形状语法 shapegrammars 给定一组产生式规则 形状设计者可以在从给定初始物体到最终物体结构的每一次变换中应用不同的规则 产生式规则可以用具有图形运算能力的数学式或其他过程性方法结合实现 88 粒子系统 用于模拟自然景物或模拟其它非规则形状物体展示 流体 性质的一个方法是微粒系统 particlesystems 这一方法尤其擅长描述随时间变化的物体 微粒运动的模拟方式 随机过程模拟 运动路径模拟 力学模拟 89 基于物理的建模 基于物理的建模方法 描段与层次建模述了物体在内外力相互作用下的行为 通常用一组网格结点来逼近物体 网格结点间取为柔性连接 再考虑贯穿物体网格的力传递