第四章 图形的表示与数据结构 如何在计算机中建立恰当的模型表示不同图形对象。 如何组织图形对象的描述数据以使存储这些数据所要的空间最省，检索、处理这些数据的速度较快。

图形的表示与数据结构 基本概念 三维形体的表示 非规则对象的表示 层次建模

4.1 基本概念 造型技术 基本图形元素 几何信息与拓扑信息 坐标系 实体的定义 正则集合运算 欧拉公式

基本概念——造型技术 把研究如何在计算机中建立恰当的模型表示不同图形对象的技术称为造型技术。 有两类图形对象： 规则对象：几何造型、几何模型。 不规则对象：过程式模拟。

基本概念——基本图形元素 基本图形元素：图素或图元、体素。 图素是指可以用一定的几何参数和属性参数描述的最基本的图形输出元素。 在二维图形系统中将基本图形元素称为图素或图元，在三维图形系统中称为体素。

基本概念——几何信息与拓扑信息 图形信息与非图形信息 几何信息：形体在欧氏空间中的位置和大小。 拓扑信息：形体各分量（点、边、面）的数目及其相互间的连接关系。

图4.1 拓扑信息

基本概念——几何信息与拓扑信息 刚体运动：不改变图形上任意两点间的距离，也不改变图形的几何性质的运动。 拓扑运动：允许形体作弹性运动，即在拓扑关系中，对图形可随意地伸张扭曲。但图上各个点仍为不同的点，决不允许把不同的点合并成一个点。

基本概念——坐标系 建模坐标系（Modeling Coordinate System） 用户坐标系 观察坐标系（Viewing Coordinate System） 规格化设备坐标系（Normalized Device coordinate System） 设备坐标系（Device Coordinate System）

基本概念——实体 图4.2 带有悬挂边的立方体

基本概念－实体 点的领域：如果P是点集S的一个元素，那么点P的以R（R>0）为半径的领域指的是围绕点P的半径为R的小球（二维情况下为小圆）。 开集的闭包：是指该开集与其所有边界点的集合并集，本身是一个闭集。 正则集：由内部点构成的点集的闭包就是正则集，三维空间的正则集就是正则形体。

基本概念－实体 组成三维物体的点的集合可以分为两类： 内点为点集中的这样一些点，它们具有完全包含于该点集的充分小的领域。 边界点：不具备此性质的点集中的点。

基本概念——实体 定义点集的正则运算r运算为： 正则运算即为先对物体取内点再取闭包的运算。r·A称为A的正则集。

基本概念——实体 图4.3 实体的例子

基本概念——实体 图4.4 正则形体

基本概念——实体 二维流形指的是对于实体表面上的任意一点，都可以找到一个围绕着它的任意小的领域，该领域与平面上的一个圆盘是拓扑等价的。 图4.5 正则形体

基本概念——实体 实体：对于一个占据有限空间的正则形体，如果其表面是二维流形，则该正则形体为实体。

基本概念——正则集合运算 有效实体的封闭性。 把能够产生正则形体的集合运算称为正则集合运算。

基本概念——正则集合运算 图4.6 集合运算与正则集合运算

基本概念——正则集合运算 图4.7 基于点的领域概念生成正则形体

图4.8 正则集合运算A∪*B，A∩*B，A―*B的结果（实线表示结果形体的边界）

基本概念——平面多面体与欧拉公式 欧拉公式证明简单多面体的顶点数V、边数E和面数F满足如下关系：V-E+F=2。 非简单多面体需对欧拉公式加以扩展。令H表示多面体表面上孔的个数，G表示贯穿多面体的孔的个数，C表示独立的、不相连接的多面体数，则扩展后的欧拉公式为：V-E+F-H=2（C-G）。

基本概念——平面多面体与欧拉公式 图4.9 平面多面体与欧拉公式

4.2 三维形体的表示 线框模型与实体模型（实体造型技术） 可以将实体模型的表示大致分为三类： 边界表示（Boundary representation, B-reps） 构造实体几何表示 空间分割（Space-partitioning）表示

三维形体的表示 多边形表面模型 扫描表示 构造实体几何法 空间位置枚举表示 八叉树 BSP树 OpenGL中的实体模型函数

多边形表面模型 边界表示(B-reps)的最普遍方式是多边形表面模型，它使用一组包围物体内部的平面多边形，也即平面多面体，来描述实体。 图4.10 四面体及其点、边、面的关系

多边形表面模型——数据结构 几何信息 建立3张表：顶点表、边表和多边形表来存储几何数据。 实体模型中，用多边形顶点坐标值以及多边形所在平面方程方式保存实体单个表面部分的空间方向信息

多边形表面模型——数据结构 拓扑信息：翼边结构表示（Winged Edges Structure） 图4.11 翼边结构表示

多边形表面模型——数据结构 属性信息 用属性表来存储多边形面的属性，指明物体透明度及表面反射度的参数和纹理特征等等。

多边形表面模型 多边形网格：三维形体的边界通常用多边形网格（polygon mesh）的拼接来模拟。 例子 图4.12 三角形带与四边形网格

扫描表示（sweep representation） 包含两个要素 一是作扫描运动的基本图形（截面）； 二是扫描运动的方式。

构造实体几何法 构造实体几何法（CSG，Constructive Solid Geometry）由两个实体间的并、交或差操作生成新的实体。 图4.13 构造实体几何法

构造实体几何法 在构造实体几何法中，集合运算的实现过程可以用一棵二叉树（称为CSG树）来描述。 树的叶子是基本体素或是几何变换参数； 树的非终端结点是施加于其子结点的正则集合算子（正则并、正则交和正则差）或几何变换的定义。

构造实体几何法 图4.14 由CSG树产生二维形体的实例

构造实体几何法 优点：如果体素设置比较齐全，通过集合运算就可以构造出多种不同的符合需要的实体。 缺点一：集合运算的中间结果难以用简单的代数方程表示，求交困难。 缺点二：CSG树不能显式地表示形体的边界，因而无法直接显示CSG树表示的形体。

(实体A∪B取ad，实体A∩B则取cb,实体A-B则取ab) 构造实体几何法 解决：光线投射算法 图4.15 光线投射算法 (实体A∪B取ad，实体A∩B则取cb,实体A-B则取ab)

空间位置枚举表示 空间位置枚举表示法将包含实体的空间分割为大小相同、形状规则（正方形或立方体）的体素，然后，以体素的集合来表示图形对象。 二维情况，常用二维数组存放。 三维情况下，常用三维数组p[i][j][k]来存放。

八叉树 八叉树（octrees）又称为分层树结构，它对空间进行自适应划分，采用具有层次结构的八叉树来表示实体。

八叉树——四叉树 图4.16 二维图的四叉树表示

八叉树 图4.17 三维空间分成八个卦限及其节点表示

BSP树 二叉空间分割（Binary Space Partitioning，BSP）树方法是一种类似于八叉树的空间分割方法，它每次将一实体用任一位置和任一方向的平面分为二部分（不同于八叉树方法的每次将实体用平行于笛卡尔坐标平面的三个两两垂直的平面分割）。

OpenGL中的实体模型函数 GLUT库中的多面体函数 表4.1 GLUT生成规则多面体的函数 函数 说明 glutSolidTetrahedron( ) glutWireTetrahedron( ) 绘制中心位于世界坐标系原点的实心四面体和线框四面体，四面体的半径为 。 glutSolidCube(size) glutWireCube(size) 绘制中心位于世界坐标系原点的实心立方体和线框立方体，立方体的半径为size，size是一个双精度浮点值。 glutSolidOctahedron ( ) glutWireOctahedron ( ) 绘制中心位于世界坐标系原点的实心八面体和线框八面体，八面体的半径为1.0。 glutSolidDodecahedron( ) glutWireDodecahedron( ) 绘制中心位于世界坐标系原点的实心12面体和线框12面体，12面体的半径为 。 glutSolidIcosahedron( ) glutWireIcosahedron( ) 绘制中心位于世界坐标系原点的实心20面体和线框20面体，20面体的半径为1.0。

OpenGL中的实体模型函数 GLUT库中的二、三次曲面 绘制实体或线框球面 绘制实体或线框圆锥面 * 1999年7月07/16/96 OpenGL中的实体模型函数 GLUT库中的二、三次曲面 绘制实体或线框球面 void glutSolidSphere/glutWireSphere (GLdouble radius, GLint slices, GLint stacks); 绘制实体或线框圆锥面 void glutSolidCone/glutWireCone (GLdouble radius, GLdouble height, GLint slices, GLint stacks); *

OpenGL中的实体模型函数 绘制实体或线框圆环 绘制实体或线框茶壶 void glutSolidTorus/ glutWireTorus(GLdouble innerRadius, GLdouble outerRadius, GLint slices,GLint stacks); 绘制实体或线框茶壶 void glutSolidTeapot/glutWireTeapot (GLdouble size);

OpenGL中的实体模型函数 GLU二次曲面函数 定义一个二次曲面 激活二次曲面绘制器 指定二次曲面的绘制方式 * 1999年7月07/16/96 OpenGL中的实体模型函数 GLU二次曲面函数 定义一个二次曲面 GLUquadricObj *sphere; 激活二次曲面绘制器 sphere = gluNewQuadric( ); 指定二次曲面的绘制方式 gluQuadricDrawStyle(sphere, GLU_LINE); *

OpenGL中的实体模型函数 绘制二次曲面 gluSphere(sphere, radius, slices, stacks); * 1999年7月07/16/96 OpenGL中的实体模型函数 绘制二次曲面 gluSphere(sphere, radius, slices, stacks); gluCylinder(sphere,baseRadius,topRadius, height, slices, stacks)； gluDisk(sphere,innerRadius,outerRadius, slices, stacks)； *

非规则对象的表示 分形几何 形状语法 粒子系统 基于物理的建模 数据场的可视化

分形几何(fractal geometry) 分形几何物体具有一个基本特征：无限的自相似性。 无限的自相似性是指物体的整体和局部之间细节的无限重现。

分形几何(fractal geometry) 分形维数，又称分数维数 4 = 22 8 = 23 N = KD D=lgN/lgk K为边长缩小倍数； N为边长缩小后产 生的新形体个数。 图4.18 分形维数

分形几何(fractal geometry) 生成过程：初始生成元（initiator）、生成元（generator）。 实例 图4.19 生成过程

形状语法 形状语法（shape grammars）：给定一组产生式规则，形状设计者可以在从给定初始物体到最终物体结构的每一次变换中应用不同的规则。 产生式规则可以用具有图形运算能力的数学式或其他过程性方法结合实现。

粒子系统 用于模拟自然景物或模拟其它非规则形状物体展示“流体”性质的一个方法是微粒系统（particle systems）。 这一方法尤其擅长描述随时间变化的物体。 微粒运动的模拟方式：随机过程模拟、运动路径模拟、力学模拟。

基于物理的建模 基于物理的建模方法：描段与层次建模述了物体在内外力相互作用下的行为。 通常用一组网格结点来逼近物体。网格结点间取为柔性连接，再考虑贯穿物体网格的力传递。

数据场的可视化 科学计算可视化（scientific visualization）指的是运用计算机图形学和图像处理技术，将科学计算过程中及计算结果的数据转换为图形及图像在屏幕上显示出来并进行交互处理的理论、方法和技术。

4.4 层次模型 段与层次模型 层次模型的实现 OpenGL中的层次模型

段与层次模型 具有逻辑意义的有限个图素（或体素）及其附加属性的集合称为段，或者称为图段（二维空间中）、结构和对象。 段是可以嵌套 段与基本图形元素的区别在于，基本图形元素是用数据来描述的，而段是用规则来描述的。

段与层次模型 段一般具有三个特性：可见性、醒目性和可选择性（可由交互式输入设备来选择）。 利用段的嵌套来构造复杂的对象或系统。 图4.20 自行车及其层次描述

段与层次模型 存储简单：一个段虽然在图中各处出现，但他 的几何和拓扑信息只要保存一次。 编辑简单：删除、移动及缩放操作都可以以段 为单位。

层次模型的实现 系统的层次模型可以通过将一个图段嵌套到另一个图段中形成图段树来创建。不同的段和基本图形元素在各自的建模坐标系中定义。 图层。通过把功能相同的部分归类，并将它们绘制在同一层上，有助于图形的理解和管理。 一般图层不再嵌套。

OpenGL中层次模型的实现 显示列表的创建 glNewList( listID, listMode ); glutSolidCube(2.0); …… glEndList(); 显示列表的执行 void glListBase(GLuint offsetValue);

OpenGL中层次模型的实现 多级显示列表 OpenGL支持创建多级显示列表，即在glNewList和glEndLsit函数对之间允许调用glCallList函数来执行其他显示列表。 显示列表的删除 void glDeleteLists(GLuint listID, GLsizei range);