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

发布时间： 2025-09-08 19:00:42

更新时间： 2025-09-08 20:17:36

🕒 阅读时间：27 min read 👀 阅读量：Loading...

前言

第二章直接略过，实在是太水了，老师上课只讲干的，完整 PPT 发在群里留作课后感兴趣的同学查阅。

第三章图形的表示与数据结构

引言

如何在计算机内构造并表示出该物体

如何组织图形对象的描述数据以使存储这些数据所需要的空间最小，检索、处理这些数据的速度较快

造型技术：研究如何在计算机中建立恰当的模型表示不同图形对象的技术

3.1 基本概念

3.1.1 基本图形单元与段的概念

基本图形元素：二维：图素（图元）；三维：体素

图素（图元）：是指可以用一定的几何参数和属性参数描述的最基本的图形输出元素。例如：点、线、圆、圆弧、椭圆、二次曲线等

体素：是三维空间中可以用有限个尺寸参数定位和定形的最基本的单元体。

3.1.2 几何信息与拓扑信息

• 段也称为图段、结构和对象 • 段是指具有逻辑意义的有限个图素（或体素）及其附加属性的集合 • 段可以嵌套

图素和体素是由数据来描述的

段是用规则来描述的，由规则最终可以找出形成它的所有的基本元素。

3.1 基本概念

几何信息

(1) 几何分量的数学表示

点： $(x, y, z)$

直线： $x = (y - y_0) / a = (z - z_0) / b$

平面： $ax + by + cz + d = 0$

(2) 几何分量之间的相互关系

形体的几何分量之间可以相互导出

相互关系

由于几何信息常会出现形体表示上的二义性，所以还应提供拓扑信息。

几何分量之间的相互关系

图 4-2 形体几何分量间的相互关系

拓扑信息

平面立体的几何分量之间一共有九种拓扑关系

刚体运动：不改变图形上任意两点间的距离，也不改变图形的几何性质的运动。非弹性运动。

拓扑运动：允许形体作弹性运动。即在拓扑关系中，对图形可随意地伸张扭曲。但图上各个点仍为不同的点，决不允许把不同的点合并成一个点。

拓扑等价：一个图形作拓扑运动与另一个图形重合。拓扑性质：与该图形拓扑等价的图形的性质。

能否把左图连续地变形为右图？

3.1.3 坐标系

图 4-4 坐标系的分类

建模坐标系 (Modeling Coordinate System): 定义基本图素和图段，有各自的坐标原点和长度单位。可调用到用户坐标系指定位置。

图 4- 4 坐标系的分类

图 4-4 坐标系的分类

图 4- 4 坐标系的分类

3.1.4 几何元素

欧氏空间中，形体由点、线、面、环、体等几何元素构成。

(1) 点

点是 0 维几何元素
点是形体最基本的元素
用计算机存储、管理、输出形体的实质就是对点集及其连接关系的处理
在自由曲线面的描述中常用三种类型的点：

控制点、型值点、插值点

(2) 线

一线是一维几何元素

一线是两个邻面或多个邻面的交界

一直线由其端点（起点和终点）定界

曲线由一系列的控制点或型值点构成

(3) 面

面是二维几何元素
面是形体上一个有限非零的区域
面由一个外环和若干个内环界定其范围
面有方向性

(4) 环

一环是有序、有向边（直线段或曲线段）组成的面的封闭边界。

一环中的边不能交叉，相邻两条边共享一个端点

一确定面的最大外边界的环称之为外环

一确定面中内孔或凸台边界的环称之为内环一外环边按逆时针排序，内环边按顺时针排序一在面上沿一个环前进，其左侧总是面内，右侧总是面外。

(5) 体

一体是三维几何元素

由封闭表面围成空间，也是欧氏空间 R³ 中非空、有界的封闭子集，其边界是有限面的并集。

3.1.5 实体的定义

表面是二维流形的正则形体称为实体。

计算机中以数学方法描述的形体可能是无效的，

所谓无效是指客观不存在的。例如下图表示的三

维形体就不是一个有意义的物体。

图 4- 5 带有悬挂面的立方体

实体造型中必须保证形体的有效性。

客观存在的三维形体具有如下性质：

(1) 刚性：有一定的形状。

(2) 维数的一致性：三维空间中物体各部分必须是三维的，不能有悬挂的或孤立的边界。

(3) 占据有限的空间：有固定的体积。

(4) 边界的确定性：根据边界能区别物体的内部和外部。

(5) 封闭性：经刚体运动和集合运算后仍是有效物体。

三维空间中的物体是一个内部连通的三维点集，是由其内部的点集及紧紧包着这些点的表皮组成的。

从点集拓扑的角度定义三维有效物体：

三维空间中的正则集，也就是正则形体，即三维有效物体。

内点：内点为点集中的这样一些点，它们具有包含于该点集的充分小的邻域。

点 P 的以 R（R>0）为半径的邻域指的是围绕点 P、半径为 R 的开区间的小球（或小圆）。

边界点：不具备内点性质的点集中的点

点集的正则运算的定义：

A- 为一点集

可见，正则运算即为先对物体取内点再取闭包的

运算。 r·A 称为 A 的正则集。

并不是所有的正则形体都是实体模型的描述对象。如右图中的正则形体，在实体造型中常被处理为两个有效立方体。

实体模型描述的实体应具有二维流形性质。

图 4- 7 带有悬挂面的立方体

二维流形指的是对于实体表面上的任意一点，都可以在实体表面找到一个围绕着它的任意小的邻域，该邻域与平面上的一个圆盘是拓扑等价的。

(a)二维流形

(b)二维流形

(c)非二维流形

图 4-8 正则形体

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

该定义条件是可以检测的，所以可由计算机来衡量一个形体是否为实体。

3.1.6 正则集合运算

实现正则运算的两种方法

(1) 间接方式：先按通常的集合运算进行计算，再用一些规则除去不符合正则定义的孤立点、边等。

主要基于点集拓扑的邻域概念

(2) 直接方式：定义出正则集合算子的表达式，用它直接得出符合正则形体定义的结果。

建立在集合成员分类的基础上

正则集合运算（基于邻域概

如果点 P 的邻域与 S 的交集是该邻域本身，则称该邻域为满；

如果点 P 的邻域与 S 的交集是空集，则称该邻域为空；

如果点 P 的邻域与 S 的交集非满非空。则称该邻域既不满也不空。

邻域概念可以描述点 P 附近的几何性质。当且仅当 P 的邻域为满时，P 在 S 内；当且仅当 P 的邻域为空时，P 在 S 外；当且仅当 P 的邻域不满也不空时，P 在 S 边界上。

正则集合运算的间接方式

以 $A \cap B$ 为例, $\mathbf{P}_{A} \cap \mathbf{P}_{B}$ 与 $A \cap B$ 的交集为空, 所以 $\mathbf{P}$ 点不在它们的正则交集之中, 而 $\mathbf{R}_{A} \cap \mathbf{R}_{B}$ 与 $A \cap B$ 的交集既不为空也不满, 所以 $\mathbf{R}$ 点在它们的正则交集的边界上。

Back

正则集合运算的直接方式

一个正则形体可由其边界点集来定义

三维空间中给定一个正则形体 S 后, 空间点集就被分为三个子集:

S 的内部点集

S 的边界点集

S 之外的点集

给定一个正则形体 S 及一个有界面 G , 则 G 相对于 S 的分类函数为:

C(S, G) = {G in S, G out S, G on S}

预备知识:

C(S, G) = {G in S, G out S, G on S}

用 - G 表示有界面 G 的反向面。即, 如果有界面 G 在 P 点的法向为 N P (G), 则有界面 - G 在 P 点的法向就是 - N P (G)。

于是: G on S={G shared (b·S), G shared (- b·S)}

所以 G 相对于 S 的分类函数 C(S,G) 可为:

C(S,G) = $\{G$ in S, G out S, G shared (b·S), G shared (- b·S) $\}$

• 正则集合算子

b· $(A \cup^* B) = \{b \cdot A$ out $B$ , b·B out $A$ , b·A shared $b \cdot B\}$

b· $(A \cap^* B) = \{b \cdot A$ in $B$ , b·B in $A$ , b·A shared $b \cdot B\}$

b· $(A^* B) = \{b \cdot A$ out $B$ , $- (b \cdot B$ in $A$ ), b·A shared $- (b \cdot B)\}$

b·(A ∪*B) = {b·A out B, b·B out A, b·A shared b·B}

b·(A ∩*B) = {b·A in B, b·B in A, b·A shared b·B}

b·(A - *B) = {b·A out B, - (b·B in A), b·A shared - (b·B)}

3.1.7 平面多面体与欧拉公式

平面多面体——是表面由平面多边形构成的三维物体。

简单多面体——指与球拓扑等价的那些多面体。

欧拉公式证明简单多面体的顶点数 V、边数 E 和面数 F 满足如下关系:

\mathbf{V} - \mathbf{E} + \mathbf{F} = 2

V=8

E=12

F=6

E=8

F=5

图 4- 12 简单多面体

令 H 表示多面体表面上孔的个数, G 表示贯穿多面体的孔的个数, C 表示独立的多面体数, 则扩展后的欧拉公式为:

V- E+F- H=2 (C- G)

图 4- 13 非简单多面体

3.2 三维形体的表示

几何造型系统中，描述物体的三维模型有：

线框模型：出现最早，方法简单，但存在很多不足，因此应用不广。

实体模型：也叫实体造型技术，是应用最广泛的三维形体的实体模型表示。

3.2 三维形体的表示

(1) 线框模型

该模型最早用来表示物体的模型，计算机绘图是它的一个重要应用。

该模型是由定义一个物体边界的直线和曲线组成，每一条线都是单独构造出来，不存在面的信息

线框模型存在许多缺陷

3.2 三维形体的表示

(1) 线框模型

表示的三维形体常有二义性或多义性
容易构造出无效形体
不能正确表示曲面信息
无法进行图形的线面消隐（包含信息有限）。
加重用户的输入负担
难以保证数据的统一性和有效性。

3.2 三维形体的表示

多义性示例

3.2 三维形体的表示

3.2.1 概述

三维形体的表示方法有多种，常用的有：

边界表示法（Boundary Representation，简称 B-rep）
构造实体几何法（Constructive Solid Geometry，简称 CSG）
空间分割表示法（Spatial Partitioning Representation）
扫描表示法（Sweep Representation）
八叉树表示法（Octree Representation）
体素表示法（Voxel Representation）

3.2.1.1 线框模型

(a)有效形体

(b)无效形体图 4-15 线框模型表示的三维形体

同一物体各面之间的相互穿透

无效形体示例

3.2.1.2 实体模型

实体模型是最高级的三维物体模型，它能完整地表示物体的所有形状信息。

它可以无歧义地确定一个点是在物体外部、内部或表面上，这种模型能够进一步满足物性计算、有限元分析等应用的要求。

实体模型的分类

小的非重叠的连续实体（立方体）

3.2.2 边界表示法

边界表示法（B-rep）是目前应用最广泛的三维形体表示方法之一。

边界表示法的基本思想是用形体的边界来定义形体。

边界表示法的基本要素：

几何信息：描述形体边界几何形状的点、线、面等几何元素。
拓扑信息：描述形体边界几何元素之间的连接关系。

3.2.2.1 多边形表面模型

多边形表面模型是边界表示的最普遍方式

图线框和实体显示的三角楼梯

3.2.2.2 平面多面体表示

利用平面多面体来描述实体，如下图所示

能够简化并加速物体的表面绘制和显示

图 4- 17 四面体及其点、边、面的关系

3.2.2.3 多边形表

用多边形数据表来存放多边形的信息

多边形数据表分为

几何信息：顶点表、边表、多边形表。
包括顶点坐标和标识多边形空间方向的参数- 拓扑信息：翼边结构表示

属性信息

包括指明物体透明及表面反射度的参数和纹理特征
检验是否是实体的条件

四面体的三张表示例

顶点表
A	x1,y1,z1
B	x2,y2,z2
C	x3,y3,z3
D	x4,y4,z4

边表
AB	A,B
BC	B,C
CA	C,A
AD	A,D
BD	B,D
CD	C,D

(几何信

息)

多边形表
ABC	AB,BC,AC
ABD	AB,BD,AD
BCD	BC,CD,BD
ACD	AC,CD,AD

翼边结构表示 (拓扑信息)

图 4- 18 翼边结构表示

多边形表中数据的检验

通常进行以下测试:

• 每个顶点至少是两条边的端点 • 每条边至少是一个多边形的部分 • 每个多边形是封闭的 • 每个多边形至少有一条公共边 • 如果边表包含指向多边形边的指针, 则每一个被指针指向的边有一个逆指针指回到多边形

3.2.2.4 平面方程

平面方程 $A x + B y + C z + D = 0$

通过方程对输入的数据表示加以处理，才能显示三维实体。

通过平面方程可以做：

求得平面的法向量

鉴别空间上的点与物体平面的位置关系。

判别点在面的内部或外部

3.2.2.5 多边形网格

多边形网格

三维形体的边界用曲面描述时通常用多边形网格（polygon mesh）的拼接来近似。

多边形网格的类型：

三角形带
四边形网格

高性能的图形系统一般采用多边形网格及相应的几何、属性信息数据库来对三维系统建模。

多边形网格应用

图 4- 21 三角形带由 10 个三角形和 12 个顶点相连而成

图 4- 22 四边形网格含 6 个四边形，由 3*4 个顶点形成

3.2.3 构造表示法

构造表示是按照生成过程来定义形体的方法，通常分为：

扫描表示
构造实体几何表示
特征表示

3.2.3.1 扫描表示

扫描表示法（sweep representation）可以利用简单的运动规则生成有效实体。

扫描表示需要两个要素:
作扫描运动的基本图形
扫描运动的方式

扫描运动的方式有:

旋转扫描
非圆形路径扫描
广义扫描法

扫描表示示例

图 4-23 旋转扫描生成三维形体

图 4- 24 平面扫描生成三维形体

图 4- 25 广义扫描生成三维形体

扫描表示应用

利用旋转构造苹果造型

利用放样实现截面的变化

3.2.3.2 构造实体几何法

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

CSG 集合运算

(a)A,B 形体的并

(b)A,B 形体的差

(c)A,B 形体的交

图 4- 26 构造几何实体法生成三维实体

CSG 差运算示例

利用差运算实现打孔

CSG 树

• 在构造实体几何法中，集合运算的实现过程可以用一棵二叉树（称为 CSG 树）来描述。

树的叶子是基本体素或是几何变换参数；
树的非终端结点是施加于其子结点的正则集合算子（正则并、正则交和正则差）或几何变换的定义。

图 4.14 由 CSG 树产生二维形体的实例

CSG 的优缺点

构造实体几何法的优点：

可以构造出多种不同的符合需要的实体。

构造实体几何法的缺陷：

求交困难
CSG 树不能显式地表示形体的边界

CSG 光线投射算法

构造实体几何法（光线投射算
将射线与 CSG 树中的所有基本体素求交，求出所有的交点。2) 将所有交点相对于 CSG 树表示的物体进行分类，确定位于物体边界上的那部分交点。3) 对所有位于物体边界上的交点计算它们在射线上的参数值并进行排序，确定距离最近的交点。得到其所在基本体素表面的法矢量。

如右图所示实体 AUB 则取 ad，实体 A∩B 则取 cb，实体 A- B 则取 ab

3.2.3.3 特征表示

特征是面向应用、面向用户的。基于特征的造型系统如图所示，可见特征模型的表示仍然要通过传统的几何造型系统来实现。

特征的参数定义

特征的形状常用若干个参数来定义。如图所示，圆柱和圆锥特征用底面直径 D 和高度 H 来定义，方块特征用长度 L ，宽度 W 和高度 H 来定义。

3.2.4 分割表示法

分割表示是将形体按某种规则分解为小的、更易于描述的部分，每一小部分又可分为更小的部分，这种分解过程直至每一小部分都能够直接描述为止。

常用方法有：

• 空间位置枚举表示 • 八叉树表示 • BSP 树表示

3.2.4.1 空间位置枚举表示

空间位置枚举表示法将包含实体的空间分割为大小相同、形状规则（正方形或立方体）的体素，然后以体素的集合来表示图形对象。

三维情况下，常用三维数组 p[i][j][k] 来存放（当 C[I][j][k] = 1 时表示对应的小立方体被物体占据；当 C[I][j][k] = 0 时表示对应的小立方体没有被物体占据）。

优点：可以表示任何实体，容易实现实体的集合运算和体积计算

缺陷：存储信息需要大量的存储空间常用的存储策略：分割检索法

占用大量的存储空间，没有边界信息；不适于图形显示对物体进行几何变换困难，如非 90 度的旋转变换；是物体的非精确表示

3.2.4.2 八叉树表示

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

八叉树表示是对空间位置枚举法中的空间分割方法的改进

三维实体的八叉树表示类似于二维实体的四叉树（Quadtree）表示。

平面四叉树

用一个矩形将图形对象包围
将矩形分为四个象限
记录各个象限的状态
判断各个象限的状态

状态为 E 或 F 则不在继续划分

状态为 B 则继续将细分为四个象限

循环执行 3,4,直至给定精度下不出现 B 型象限为止。

例子中的给定精度为图像的 1/128。

三维八叉树

图 4- 31 三维空间分成八个卦限及其节点表示

3.2.4.3 BSP 树表示

二叉空间分割 ( binary space partitioning, BSP) 方法类似于八叉树的空间分割方法，每次将一实体用任一位置和任一方向的平面分为二部分。

二叉树与八叉树比较

八叉树每次将实体用平行于笛卡尔坐标平面的三个两两垂直的平面分割，BSP 树是按更适合于实体的空间属性的分割平面来划分

BSP 树减少了树的高度，也就减少了树的搜索时间。

总结

要素、体素、段

刚性运动、拓扑运动、拓扑等价、拓扑性质

坐标系：建模、用户（全局、世界）、观察、规范化设备、设备

实体：三维有效形体、正则集、二维流形、求实体的直接和间接方法

三维形体表示：线框、表面、实体

实体表示：边界、构造、分割

主要概念总结