立的、不相连接的多面体数，则扩展后的欧拉公式为：
V-E+F-H=2（C-G）。
25
基本概念——平面多面体与欧拉公式
8-12+6=2
5-8+5=2
6-12+8=2
24－36＋15－3＝2×（1－1）
图4.9 平面多面体与欧拉公式
26
4.2 三维形体的表示
线框模型与实体模型（线框模型由定义一个物体 边界的直线和曲线组成）
A
B
A
B
(a)A与B
C
C*
(b)
(c)集合运算 C=A∩B
(d) 正则集合运算 C*=A∩*B
图4.6 集合运算与正则集合运算
22
基本概念——正则集合运算
PA
PB
P
PA
PB
RA RB RA RB R
图4.7 基于点的领域概念生成正则形体
23
b· out A B A B A B A b· in BB A b· in A B b· out B A b· shared b· A B b· shared b· A B A
可以将实体模型的表示大致分为三类：
边界表示（用一组曲面（或平面）来描述物体， 这些曲面将物体分为内部和外部） 构造实体几何表示 空间分割（将包含物体的空间划分成一组非常 小的非重叠的连续实体）表示
27
三维形体的表示
多边形表面模型（使用一组包围物体内部的平面
多边形来描述实体）
扫描表示
10
基本概念——实体
图4.2 带有悬挂边的立方体
11
客观存在的三维形体的5条性质： 刚性：一个物体必须具有一定的形状 维数的一致性：三维空间种，一个物体的各部分均应 是三维的，不能有悬挂的或孤立边界 占据有限的空间（体积有限） 边界的确定性（根据物体的边界可以确定物体内部与 外部） 封闭性（经过一系列刚体运动及任意序列的集合运算 后，依然是有效的物体） 三维空间中的物体是一个内部连通的三维点集。
基本概念－实体（点集拓扑学的角度）
点的领域：如果P是点集S的一个元素，那么点P的以R（
R>0）为半径的领域指的是围绕点P的半径为R的小球（
二维情况下为小圆）。
开集的闭包：是指该开集与其所有边界点的集合并集，本
身是一个闭集。（三维物体的点的集合可以分为内部点和 边界点来那个部分） 正则集：由内部点构成的点集的闭包就是正则集，三维空 间的正则集就是正则形体。也就是三维有效物体
面-边包含性 f:{e}
e
图4.1 拓扑信息
基本概念——几何信息与拓扑信息
刚体运动：不改变图形上任意两点间的距离， 也不改变图形的几何性质的运动。 拓扑运动：允许形体作弹性运动，即在拓扑关 系中，对图形可随意地伸张扭曲。但图上各个 点仍为不同的点，决不允许把不同的点合并成
一个点。
9
基本概念——坐标系
的体素，然后，以体素的集合来表示图形对
象。
二维情况，常用二维数组存放。
三维情况下，常用三维数组p[i][j][k]来存
放。
40
八叉树
八叉树（octrees）又称为分层树结构，它对 空间进行自适应划分，采用具有层次结构的八 叉树来表示实体。
41
八叉树——四叉树
2）每条边至少是一个多边形的部分
3）每个多边形式封闭的 4）每个多边形至少有一条公共边 5）如果多边形表包含指向多边形边的指针，则每一个 被指针指向的边有一个逆指针指回到多边形
32
多边形表面模型
多边形网格：三维形体的边界通常用多边形网 格（polygon mesh）的拼接来模拟。（三角 形和四边形）
第四章 图形的表示与数据结构
如何在计算机中建立恰当的模型表示不同图形 对象。 如何组织图形对象的描述数据以使存储这些数 据所要的空间最省，检索、处理这些数据的速 度较快。
1
图形的表示与数据结构
基本概念 三维形体的表示 非规则对象的表示 层次建模
2
4.1 基本概念
造型技术
36
Y
Y
1 -1 0 -1
P1 1 2 3 4 X
1 0
P2 4 X
(a)
(b)
C U U U P1 T(平移) U P2 T P1 T △x=2 △y=2
Y
1 -1 0 -1
P1 1 2 3 4 X
T(平移) P1
P1 △x=4
P2
△y=2 -2
△x=2
(c) CSБайду номын сангаас树
(d) 由CSG树产生的形体
图4.14
由CSG树产生二维形体的实例
37
构造实体几何法
优点：如果体素设臵比较齐全，通过集合运算 就可以构造出多种不同的符合需要的实体。 缺点一：集合运算的中间结果难以用简单的代 数方程表示，求交困难。 缺点二：CSG树不能显式地表示形体的边界， 因而无法直接显示CSG树表示的形体。
38
基本图形元素
几何信息与拓扑信息
坐标系
实体的定义 正则集合运算 欧拉公式
3
基本概念——造型技术
把研究如何在计算机中建立恰当的模型表示不 同图形对象的技术称为造型技术。 有两类图形对象： 规则对象：几何造型、几何模型(几何信 息和拓扑信息)。 不规则对象：过程式模拟。
4
14
基本概念－实体
组成三维物体的点的集合可以分为两类： 内部点为点集中的这样一些点，它们具有完 全包含于该点集的充分小的领域。 边界点：不具备此性质的点集中的点。
15
基本概念——实体
定义点集的正则运算r运算为：
r A c i A
正则运算即为先对物体取内点再取闭包的运算。 r· A称为A的正则集。
C 边 顶点 B
AB
BC
CA
AD
BD
CD
A
B
C
D
图4.10 四面体及其点、边、面的关系
29
多边形表面模型——数据结构
几何信息（几何表）
建立3张表：顶点表、边表和多边形表来存
储几何数据。
实体模型中，用多边形顶点坐标值以及多边
形所在平面方程方式保存实体单个表面部分
的空间方向信息
30
多边形表面模型——数据结构
拓 扑 信 息 ： 翼 边 结 构 表 示 （ Winged Edges
Structure）
E1
V1
E2
F1
F2
E
E3
V2
E4
图4.11 翼边结构表示
31
多边形表面模型——数据结构
属性信息
用属性表来存储多边形面的属性，指明物体透明 度及表面反射度的参数和纹理特征等等。
实体测试条件：1）每个顶点至少是两条边的端点
(a)二维流形
(b)二维流形
图4.5 正则形体
(c)非二维流形
19
基本概念——实体
实体：对于一个占据有限空间的正则形体，如
果其表面是二维流形，则该正则形体为实体。
20
基本概念——正则集合运算
有效实体的封闭性。
把能够产生正则形体的集合运算称为正则集合运 算。
21
基本概念——正则集合运算
例子
图4.12 三角形带与四边形网格
33
扫描表示（sweep representation）
扫描表示法（sweep representation）可以利用 简单的运动规则生成有效实体。 包含两个要素 一是作扫描运动的基本图形（截面）； 二是扫描运动的方式（平移、旋转、对称变 换）。
34
构造实体几何法
构造实体几何法（CSG，Constructive Solid
Geometry）由两个实体间的并、交或差操作
生成新的实体。
A B (a)A,B形体的并
A B (b)A,B形体的差
A B (c)A,B形体的交
图4.13 构造实体几何法
35
构造实体几何法
在构造实体几何法中，集合运算的实现过程可 以用一棵二叉树（称为CSG树）来描述。 树的叶子是基本体素或是几何变换参数； 树的非终端结点是施加于其子结点的正则集 合算子（正则并、正则交和正则差）或几何 变换的定义。
基本概念——基本图形元素
基本图形元素：图素或图元、体素。 图素是指可以用一定的几何参数和属性参数描 述的最基本的图形输出元素（包括点、线、面 、环、体等）。 在二维图形系统中将基本图形元素称为图素或 图元，在三维图形系统中称为体素。
5
1、点：为0维几何元素，是形体最基本的元素，自由曲 线、曲面或其他形体均可用有序的点集来表示。点集及 其连接关系的存储。 2、线：一维几何元素，是两个邻面或多个邻面的交界 3、面：二维几何元素，是形体上一个有限、非零的区 域，由一个外环和若干内环界定其范围。具有方向性， 由其外法线矢量方向定义。 4、环：有序、有向边组成的面的封闭边界。（外环中 其边逆时针排序，内环顺时针排序） 5、体：三维几何元素，由封闭表面围成的空间。
基本概念——平面多面体与欧拉公式
欧拉公式证明简单多面体的顶点数V、边数E和面数F满
足如下关系：V-E+F=2。(简单多面体指那些经过连续的
几何形变可以变换成一个球的多面体，即与球拓扑等价 的那些多面体） 非简单多面体需对欧拉公式加以扩展。令H表示多面体表 面上孔的个数，G表示贯穿多面体的孔的个数，C表示独
三维物体表面必须具有以下5条性质：
连通性：位于物体表面上的任意两个点都可用实体表 面上的一条路径连接起来。
有界性：物体表面可将空间分为互不连通的两部分， 其中一部分是有界的 非自相交性：物体的表面不能自相交 可定向性：物体表面的两侧可明确定义出属于物体的 内侧或外侧 闭合性：物体表面的闭合性是由表面上多边形网格各 元素的拓扑关系决定的，即每一条边有且只有两个顶 点；每一条边连接来年各个或两个以上的面。