第九章 三维形体的表示
? 表示形体的两种模型
? 实体的定义
? 正则集合运算
? 特征表示
? 空间分割表示
? 推移表示
? 边界表示
? 构造实体几何表示
? 不规则形体的建模方法
? L系统
9, 1 引 言
? 三维图形在科学研究和工程技术中有着广泛的
应用。在 CAD中，需要对所设计的作品从不同
的角度进行审视。计算机几何造型就是用计算
机系统来表示、控制、分析和输出三维形体。
所以几何造型是计算机图形学中一个十分重要
的应用领域，它是 CAD/CAM和 CIMS系统的
核心技术，也是用来实现计算机辅助设计的基
本手段。几何造型的功能：
– 形体输入,即把形体从用户格式转换成计算
机内部格式；
– 图形数据的 存储和管理 ；
– 图形控制,如对形体进行平移、缩放、旋转
等几何变换；
– 图形修改,如应用集合运算、欧拉运算、有
理 B样条操作及其交互手段实现对形体局部
或整体修改；
– 图形分析,如形体的容差分析，物质特性分
析等；
– 图形显示输出，如消隐、光照、颜色的控制
等；
– 询问 形体的属性 及其 有关参数
9, 2 形 体
? 在计算机形体一般
定义为六层拓扑结
构，首先介绍在三
维空间中基本术语
的定义。
形体 (object)
外壳 (shell)
面 (face)
环 (loop)
边 (loop) 顶点 (vertex)
曲线和直线
方程
点的
几何坐标
形 体
? 体
由封闭表面围成的有效空间称为体 ；一个形体 Q是 R3空
间中非空、有界的封闭子集。其 边界（记为 ?Q） 是有
限个面的并集，而外壳是形体的最大边界。一个单位立
方体可定义为：
{(x,y,z)∈R 3|0≤x≤1,0≤y≤1,0≤z≤1}
其中一个表面可表示为：
{(1,y,z)∈R 3|0≤y≤1,0≤z≤1}
必须注意：并没有规定形体必须是一个连续的
封闭集合，目的是用这样的定义来扩大几何造型的域，
使得形体可以由不连续的体素，或是仅有某些相交的形
体组成。
x
z
y
形 体
? 面
R3中非空、连续、共面且封闭的子集称
为面 F，
其边界 (记为 ?F)是有限条线段的并集，
Pt表示含有 F的唯一平面。
面是形体表面的一部分，且具有方向性,
F
Pt
形 体
? 环
由有序、有向边组成的面的封闭边界
称为环，环中任意边都不能自交，相
邻两条边共享一个端点，环又分为内
环和外环。内环是在已知面中的内孔
或凸台面边界的环，其边按逆时针方
向。外环是已知面的最大外边界的环，
其边按顺时针方向，按这种方式定义，
在面上沿着边的方向前进，面的内部
始终在走向的右侧。
形 体
? 边
形体内两个相邻面的交界称为边，一条边有且仅有两
个相邻面。两个端点确定一条边，这两个端点分别称
为该边的起点和终点。假设 Q是一个形体,E(Q)是形体
边的集合，则在 ?Q(形体的边界 )中 E(Q)满足下属条件
的所有线段的集合：
– 边 e的两个端点属于 V(Q)；
– 边 e中没有一个内部点属于 V(Q)（所有顶点的集合）
– 边 e上每个点，都有两个不同的面，即存在两个面 fi，
fi≤ ?Q使得边 e∈f i∩f j；
– 形体 Q的边框线 WF(Q)是由有序对 (V(Q),E(Q))所组
成。
v1
v2
ef1 f2
形 体
? 点
边的端点称为点，点不能出现在边的内部，也不能孤
立地位于物体内、物体外或面内，顶点又是 ?F(面边界 )
中两条不共线的线段的交点。
v1
v2
ef1 f2
形 体
? 体素
具有有限个参数定义，且简单
的连续封闭的形体称为体素，
如长方体、圆柱体、圆锥、球、环等。
? 半空间
集合 {P|F(P)≤0} 成为半空间，其中 P为 R3中的一点,F为一个平面，
当 F=0时，表示一个平面，这个平面的半空间可以由
F(P)=ax+by+cz+d定义的平面加上在平面某一侧的所有点组成。显
然一个长方体可以看成是 6个平面半空间的交。
? 几何信息
用来表示形体的几何性质和度量关系称为几何信息。
? 拓扑信息
用来表示形体之间的连接关系称为拓扑信息。
表示形体的两种模型
? 数据模型
– 完全以数据描述
– 例如
? 用以 8个顶点表示的立方体
? 以中心点和半径表示的球
– 以数据文件的形式存在
– 包括 ----特征表示、空间分割表示、推移表示、边
界表示、构造实体几何表示等
– 进一步分为
?线框模型
?表面模型
?实体模型
线框模型
线框模型：将形体表示成
一组轮廓线的集合。
– 一般地，画出了形体的棱线与
轮廓线就能唯一地表示出来。
如图，八个顶点可以定义一个
长方体，但还不足以识别它，
如果定义了棱线，则无论如何
放置长方体都能唯一地表示了。
对于多面体由于其轮廓线和棱
线通常是一致的，所以多面体
的线模型更便于识别，且简单。
e12
v4
v8
s3
e2
e4
e6
e8
e2e
7
e11
e10 e9e3
e1
v2
v3
v1
v7
v5v
6 s2
s6
s5
s1 s4
线框模型
– 优点,简单、处理速度快
– 缺点,
1、对于非平面多面体，如圆柱、球等形体，
其轮廓线随观察方向的改变而改变，无法用
一组固定的轮廓线来表示它们。
2、线框模型与形体之间不存在一一对应关系：
它仅仅通过给定的轮廓线约束所表示形体的
边界面，而在轮廓线之间的地方，形体的表
面可以任意变化。
3、没有形体的表面信息，不适于真实感显示，
由此导致表示的形体可能产生二义性。
表面模型
? 表面模型
– 将形体表示成一组表面的集合
– 如果把线框模型中的棱线包围的部分定义为
面，所形成的模型便是表面模型。其数据结
构是在线模型的基础上附加一些指针，有序
地连接棱线。下图中表面编号表示第几个表
面，表面特征表面是平面还是曲面。
– 形体与其表面一一对应，适合于真实感显示
4顶点个数
1起始指针
0表面特征
5表面编号
14
043
032
021
连接指针属
性
顶点
号
1
4
2
3
2
3
4
1
表面模型
? 缺点：
? 不能有效的用来表示实体
? 原因：
? 1、表面模型中的所有面未必形成一个封
闭的边界
? 2、各个面的侧向没有明确定义，即不知
道实体位于面的哪一侧
实体模型
– 实体模型
? 用来描述实体，主要用于 CAD/CAM
? 包含了描述一个实体所需的较多信息，如几何信
息、拓扑信息，可以支持多种运算，如欧拉运算
等。
表示形体的两种模型
? 过程模型
– 以一个过程和相应的控制参数描述
– 例如
? 用一些控制参数和一个生成规则描述的植物
– 以一个数据文件和一段代码的形式存在
– 包括 ----粒子系统,L系统、迭代函数系统等
表示形体的两种模型
? 模型分类
实体的定义
? 抽象带来的问题
– 计算机中表示的物体是无效的
– 不能够客观存在
? 为什么要求客观存在
– CAD/CAM的需求
? 什么是客观存在（有效） — 实 体的定义
– 具有一定的形状
– 具有封闭的边界（表面 )
– 内部连通
– 占据有限的空间
– 经过运算后，仍然是有效的物体
实体的定义
? 将三维物体看做一个点集，它由内点和
边界点共同组成。
? 内点：具有完全包含于该点集的充分小
的邻域
? 边界点：不具有内点性质的点集
实体的定义
A是一个点集，定义点集的正则运算如下：
? i：取内点运算
? c,取闭包运算
? 正则运算 r
? i A,A的全体内点组成的集合，称为 A
的内部
? c i A为 A的内部的闭包的运算，是
i A与其边界点的并集。
AicAr ????
?
??
?
实体的定义
? 正则点集
– 称为 A的正则点集
– 称 A为正则点集，如果它满足
? 问题：正则点集是实体？
Ar?
AAr ??
实体的定义 -举例说明
? 阴影部分：物体的内部区域
? 黑色部分：边界
? (a)图取内点 ->(b)图求闭包 ->(c)图
? 正则运算：去除与物体维数不一致的悬挂部分
或孤立部分。
实体的定义
? 实体的定义 — 可 计算的条件
– 正则点集
– 表面是二维流形
? 二维流形
– 其上任意一点存在充分小的领域与圆盘同构
（存在连续的一一映射）
9, 3 正 则 集 合 运 算
? 为什么需要正则集合运算
– 正则集合运算是构造复杂物体的有效方法
– 普通的集合运算会产生无效物体
– (b),A ∩ B
– ( c ), 普通 A ∩ B
– ( d ),正则 A ∩ B
正则集合运算
? 集合运算（并、交、差）是构造形体的
基本方法。正则形体经过集合运算后，
可能会产生悬边、悬面等低于三维的形
体。
? Requicha在引入正则形体概念的同时，
还定义了正则集合运算的概念。正则集
合运算保证集合运算的结果仍是一个正
则形体，即丢弃悬边、悬面等。
正则集合运算
? 正则集合运算的定义
– 正则并
– 正则交
– 正则差
)(* BopArBopA ??
)(* BArBA ?? ??
)(* BArBA ?? ??
)(* BArBA ????
任一实体 S可以用它的边界 bS和它的内部 iS来表示，即
S=bS ∪ iS
由实体的定义可知,bS是封闭的，它将整个三维空间分成了
三个区域,S的内部 iS,S的边界 bS,S的外部 eS。边界 bS与实
体 S是一一对应的。确定了边界，也就唯一确定了一个实体。
因此，为了求实体 A,B的正则集合运算结果 A op* B，只要
求出其边界 b（ A op* B）即可。
正则集合 运算
正则集合 运算
考察 A,B两物体的交所形成拼合体的边界，
由于 A,B为正则点集，它们均可表示为边界点与体
内点的集合，即 A=bA ∪ iA ; B=bB ∪ iB
A物体的边界 bA可按其位于 B物体内,B物体上、
B物体外而分别表示为
bA = (bA∩iB)∪(bA∩bB) ∪(bA∩eB)
同理,bB = (bB∩iA)∪(bB∩bA)∪(bB∩eA)
A
正则集合 运算
其中 bA ∩ bB = bB ∩ bA 是 A与 B的公
共边界，它可以分成两部分,
（ bA ∩bB ）同侧,(bA ∩bB) 异侧
(bA ∩bB) 同侧由这样一些边界构成,A、
B位于边界的同侧
(bA ∩bB) 异侧由这样一些边界构成,A、
B位于边界的异侧
正则集合 运算
? 对于 A ∩* B,由交的定义可知：
? 1） A,B两物体的边界位于对方内部的部分，即 bA ∩
iB 和 bB ∩ iA 是 b(A ∩* B ) 的组成部分。
? 2） A,B两物体的边界位于对方外部的部分，即 bA
∩ eB 和 bB ∩ eA 不是 b(A ∩* B ) 的组成部分。
? 3）对于 A,B的重合边界有,(bA ∩bB) 同侧属于 b(A
∩* B ); (bA ∩bB) 异侧不属于 b(A ∩* B ) 因此：
? b(A∩*B)=(bA ∩ iB) ∪(bB ∩ iA)∪(bA∩ bB) 同侧
正则集合 运算
? 同理：
? b(A∪ *B)=(bA ∩ eB) ∪ (bB ∩ eA)∪ (bA∩bB)同
侧
? b(A－ *B)=(bA ∩ eB) ∪ (bB ∩ iA)∪ (bA∩bB)异侧
一些非正则形体的实例
? 一些非正则形体的实例
( a ) 有悬面 ( b ) 有悬边
（c ）一条边有两个以上
的邻面（不连通）
图3, 2, 1 非正则形体实例
? 为了能够处理非正则形体, 产生了非正
则造型技术 。
? 九十年代以来, 基于约束的参数化, 变
量化造型和支持线框, 曲面, 实体统一
表示的非正则形体造型技术已成为几何
造型技术的主流 。
9, 4 形 体 表 示 模 型
?在实体模型的表示中，基本上可以分
为分解表示、构造表示和边界表示三
大类。
?1、分解表示
将形体按某种规则分解为小的更易于描述的部
分，每一小部分又可分为更小的部分，这种
分解过程直至每一小部分都能够直接描述为
止。
9.4.1 分解表示 -空间位置枚举表示
– 形体空间细分为小的均匀的立方体单元。
– 用三维数组 C[I][J][K]表示物体，数组中的元素与单
位小立方体一一对应
?当 C[I][J][K] = 1时，表示对应的小立方体被物体
占据
?当 C[I][J][K] = 0时，表示对应的小立方体没有被
物体占据
分解表示 -空间位置枚举表示
– 优点
? 简单，可以表示任何物体
? 容易实现物体间的交、并、差集合运算
? 容易计算物体的整体性质，如体积等
– 缺点
? 占用大量的存储空间，如 1024*1024*1024 = 1G
bits
? 物体的边界面没有显式的解析表达式，不适于图
形显示
? 对物体进行几何变换困难，如非 90度的旋转变换
? 是物体的非精确表示
分解表示 -八叉树表示
? 八叉树表示
– 对空间位置枚举表示的空间分割方法作了改进：均
匀分割 自适应分割
– 八叉树建立过程
?八叉树的根节点对应整个物体空间
?如果它完全被物体占据，将该节点标记为 F(Full)，
算法结束；
?如果它内部没有物体，将该节点标记为 E(Empty)，
算法结束；
?如果它被物体部分占据，将该节点标记为 P(Partial)，
并将它分割成 8个子立方体，对每一个子立方体进行
同样的处理
分解表示 -八叉树表示
? 8叉树的表示应用三维形体的分解，
它对一个外接立方体的形体进行
前后、左右、上下等部分 8个小立
方体，如果小立方体单元为满或
为空，表示该立方体完全在形体
中或完全不在形体中，则其停止
分解；对部分形体占有的小立方
体需进一步分解为 8个子立方体，
直至所有小立方体单元要么全部
满，要么全部空，或已分解到规
定的分解精度为止。
2 36 7
2
0 1
3
1
3 7
5
具有子孙的节点 (P)
空节点 (E)
实节点 (F)
分解表示 -八叉树表示
– 优点
? 可以表示任何物体，且形体表示的数据结构简单
? 简化了形体的集合运算。只需同时遍历参加集合
运算的两形体相应的八叉树，无需进行复杂的求
交运算。
? 简化了隐藏线（或面）的消除，因为在八叉树表
示中，形体上各元素已按空间位置排成了一定的
顺序。
? 分析算法适合于并行处理。
– 缺点
? 没有边界信息，不适于图形显示
? 对物体进行几何变换困难
? 是物体的非精确表示
? 占用大量存储。实际上，八叉树表示是以存储空
间换取算法的效率
分解表示 -线性八叉树表示
线性八叉树：用一可变长度
的一维数组来存储一棵八
叉树。数组中仅存储八叉
树的性质为 FULL的终端结
点。并用一个八进制数表
示该结点在八叉树中的位
置。编码方式为：
Q1Q2… Qm,其中 Q1表示该
结点所属的一级父结点的
编号（ 0-7），以此类推。
例右图为：
{1X,30X,31X,323X,33X}
2 36 7
2
0 1
3
1
3 7
5
具有子孙的节点 (P)
空节点 (E)
实节点 (F)
分解表示 -单元分解表示
? 单元分解表示
– 对空间位置枚举表示的空间分割方法作了改进：单
一体素 多种体素
– 三种空间分割方法的比较
? 空间位置枚举表示 ----同样大小 立方体粘合在一起表示物体
? 八叉树表示 ----不同大小的立方体 粘合在一起表示物体
? 单元分解表示 ----多种体素 粘合在一起表示物体
分解表示 -单元分解表示
– 优点
? 表示简单
? 容易实现几何变换
? 基本体素可以按需选择，表示范围较广
? 可以精确表示物体
– 缺点
? 物体的表示不唯一
? 物体的有效性难以保证
9, 4, 2 构造表示
? 扫描表示
? 构造实体几何表示（ CSG）
? 特征表示
构造表示 -推移表示
? 将物体 A沿着轨迹 P推移得到物体 B，称 B
为 sweep体
? 平移 sweep----将一个二维区域沿着一个
矢量方向推移
构造表示 -推移表示
? 旋转 sweep----将一个二维区域绕旋转轴
旋转一周
? 三维形体也能在空间通过扫
描变换生成新的形体：如左
图，一个圆柱体按指定方向
在长方体上运动生成新的形
体，这个过程犹如长方体与
运动者的圆柱体不断的作差
运算操作。
有时经过扫描变换所生成的形体可能会出现维数不一致问题。
构造表示 -推移表示
扫描线方向
U
构造表示 -推移表示
? 广义 sweep
– 任意物体沿着任意轨迹推移
– 推移过程中物体可以变形
构造表示 -推移表示
? 优点
– 表示简单、直观
– 适合做图形输入手段
? 缺点
– 作几何变换困难
– 对几何运算不封闭
– 用扫描变换产生的形体可能出现维数不一致的问题。
– 扫描方法不能直接获取形体的边界信息，表示形体
的覆盖域非常有限。
构造表示 -构造实体几何表示 (CSG)
.通过对体素定义运算而得到新的形体的一种
表示方法。体素可以是立方体、圆柱、圆锥
等，也可以是半空间，其运算为变换或正则
集合运算并、交、差。
CSG表示可以看成是一棵有序的二叉树。
?其终端节点或是体素、或是形体变换参数。
?非终端结点或是正则的集合运算，或是变换（平
移和 /或旋转）操作，这种运算或变换只对其紧
接着的子结点（子形体）起作用。
构造表示 -构造实体几何表示 (CSG)
构造表示 -构造实体几何表示 (CSG)
? CSG树是无二义性的，但不是唯一的,
CSG表示的优点：
?数据结构比较简单，数据量比较小，内部
数据的管理比较容易；
?物体的有效性自动得到保证；
?CSG方法表示的形体的形状，比较容易修
改。
构造表示 -构造实体几何表示 (CSG)
CSG表示的缺点：
?对形体的表示受体素的种类和对体素操作
的种类的限制，也就是说,CSG方法表示
形体的覆盖域有较大的局限性。
?对形体的局部操作不易实现，例如，不能
对基本体素的交线倒圆角；
?由于形体的边界几何元素（点、边、面）
是隐含地表示在 CSG中，故显示与绘制 CSG
表示的形体需要较长的时间。
?表示不唯一
构造表示 -特征表示
? 用一组特征参数表示一组类似的物体
? 特征包括形状特征、材料特征等
? 适用于工业上标准件的表示
构造表示 -特征表示
– 从应用层来定义形体，因而可以较好的表达
设计者的意图。从功能上可分为形状、精度、
材料和技术特征。
– 特征是面向应用、面向用户的。特征模型的
表示仍然要通过传统的几何造型系统来实现。
不同的应用领域，具有不同的应用特征。
– 在几何造型系统中，根据特征的参数我们并
不能直接得到特征的几何元素信息，而在对
特征及在特征之间进行操作时需要这些信息。
– 特征方法表示形体的覆盖域受限于特征的种
类。
构造表示的特点
? 构造表示的特点：
– 构造表示通常具有不便于直接获取形体几何
元素的信息、覆盖域有限等缺点，
– 但是，便于用户输入形体，在 CAD/CAM系统
中，通常作为辅助表示方法。
边界表示
? 边界表示（ BR表示或 BRep表示）
– 按照体－面－环－边－点的层次，详细记录
了构成形体的所有几何元素的几何信息及其相
互连接的拓扑关系。
– 边界表示的一个重要特点是在该表示法中，
描述形体的信息包括几何信息（ Geometry）
和拓扑信息（ Topology）两个方面。
?拓扑信息描述形体上的顶点、边、面的连接关系，
拓扑信息形成物体边界表示的, 骨架, 。
?形体的几何信息犹如附着在, 骨架, 上的肌肉。
边界表示
? 边界模型表达形体的基本拓扑实体包括：
– 1,顶点
– 2,边。边有方向，它由起始顶点和终止顶
点来界定。边的形状（ Curve）由边的几何
信息来表示，可以是直线或曲线，曲线边可
用一系列控制点或型值点来描述，也可用显
式、隐式或参数方程来描述。
边界表示
– 3,环。环（ Loop）是有序、有向边
（ Edge）组成的封闭边界。环有方向、内
外之分，外环边通常按逆时针方向排序，内
环边通常按顺时针方向排序。
– 4.面。面（ Face）由一个外环和若干个内
环（可以没有内环）来表示，内环完全在外
环之内。
?若一个面的外法矢向外，称为正向面；反之，称
为反向面。
边界表示
?面的形状可以是平面或曲面。平面可用平面方程
来描述，曲面可用控制多边形或型值点来描述，
也可用曲面方程（隐式、显式或参数形式）来描
述。对于参数曲面，通常在其二维参数域上定义
环，这样就可由一些二维的有向边来表示环，集
合运算中对面的分割也可在二维参数域上进行。
– 5.体。体（ Body）是面的并集。
边界表示
? 边界表示模型是一种采用描述形体表面的方法来描述
的几何表示模型。一个形体一般可以通过其边界拆成
一些有界的, 面, 或, 小片, 的子集来表示，而每一
个面又可以通过其边界的边和顶点来表示。若面的表
示无二义性，则其边界表示模型也无二义性，但通常
不一定只有唯一的表示。
U
图3, 2, 1 0 边界表示
边界表示的数据结构
? 边界表示法的数据结构有四种方法：以面为基
础, 以顶点为基础, 以边为基础和翼边结构；
? 以面为基础的数据结构
? 以面为基础, 按照体, 面, 顶点坐标的树
结构层次组织元素数据；如
? 面 顶点坐标
? F1
(X1Y1Z1,X2Y2Z2,X3Y3Z3,X4Y4Z4)
? F2
(X1Y1Z1,X2Y2Z2,X6Y6Z6,X5Y5Z5)
? …
……,.
? 其中顶点按照外观顺时针顺序；
边界表示的数据结构
? 2,以顶点为基础的数据结构
? 以顶点 /坐标和面 /顶点序列两张关系表表
示, 如：
? 顶点 坐标 面 顶点序列
? V1 X1Y1Z1 F1 V1V2V3V4
? ……………………………………………………
……………,.
? 3.以边为基础的数据结构
? 以边 /顶点, 顶点 /坐标, 面 /边三张关系
表表示；
边界表示模型
? 四棱椎边界表示的例子如右，由 4
个面组成，且这种表示可以看作是
含有体、面、边、顶点为节点的有
向图
? 四棱椎边界表示也可以基于边界的
三角形分解，即把形体的边界拆成
一些互不重叠的三角形。
v1 v
2
v3v
4
v5
v2
v3v4
v5
e1 e2
e3f
1v1
四棱柱
面节点
边节点
顶点坐标
f1 f2 f3 ….
e1 e2 e3 e4 ….
v1 v2 v3….
(x1,y1,z1)
组合
结构
坐标
信息
….
边界表示的数据结构 -翼边数据结构
? 翼边数据结构：在 1972年，由
美国斯坦福大学 Baumgart作为
多面体的表示模式提出。
– 它用指针记录了每一边的两个邻
面（即左外环和右外环）、两个
顶点、两侧各自相邻的两个邻边
（即左上边、左下边、右上边和
右下边），用这一数据结构表示
多面体模型是完备的，但它不能
表示带有精确曲面边界的实体。
左下边
右下边
右上边
左上边
边
左外环 右外环
图3.2.11 翼 边数据结构
边界表示的数据结构 -翼边数据结构
? 翼边结构由四种结点 Solid,Face,edge和
Vertex组成的, 各结点描述如下：
?
? Solid 构成引用的根节点 。
? 在任意时刻, 会存在几个数据结构引用；为了
存取其中的任何一个, 需要指向其 Solid节点
的指针 。 通过指向三个双向链表的指针,
Solid 节点给出对该模型的面, 边和顶点的访
问 。 所有实体被链接到一个双向链表中, 这个
表通过指向该表的后继和前趋实体的指针来实
现的 。 具体包括：
?
边界表示的数据结构 -翼边数据结构
? S o l i d ID;
? 指向 face的链表指针；
? 指向 edge的链表指针；
? 指向 vertex的链表指针；
?
?
边界表示的数据结构 -翼边数据结构
? Face 表示多面体的一个小平面,包括：
? Face ID ；
? 指向 face的链表首元素的指针；
? 指向 face的下一元素的指针；
?
边界表示的数据结构 -翼边数据结构
? Edge 由 Edge节点构成, 是整个数据结构的
核心, 每个 Edge结点代表一条边, 包括：
? Edge ID ;
? Edge的起始顶点指针；
? Edge的终止顶点指针；
? Edge的右邻面的指针；
? Edge的左邻面的指针；
? Edge的右方向向前邻边指针；
? Edge的右方向向后邻边指针；
? Edge的左方向向前邻边指针；
? Edge的左方向向后邻边指针；
?
边界表示的数据结构 -翼边数据结构
? Vertex 由 vertex节点构成, 包括：
? Vertex ID ;
? 顶点坐标 (x,y,z) ;
? 指向与该 vertex相连的第一条边指针；
? 指向下一个 Vertex结点指针；
?
边界表示的数据结构 -半边数据结构
? 半边数据结构，是在 80年代
提出的，作为一种多面体的
表示方法。在构成多面体的
三要素（顶点、边、面）中，
半边数据结构以边为核心。
一条边表示成拓扑意义上方
向相反的两条“半边”，所
以称为半边数据结构。
? 其中各节点的数据结构及含
义如下：
边界表示的数据结构 -半边数据结构
? typedef float vector[4];
? typedef short ID;
? typedef struct solid Solid ;
? typedef struct face Face ;
? typedef struct loop Loop ;
? typedef struct edge Edge ;
? typedef struct halfedge HalfEdge ;
? typedef struct vertex Vertex ;
边界表示的数据结构 -半边数据结构
? 多面体
struct solid
{
ID solidno; //多面体序号
Face *sfaces; //指向多面体的面；
Edge *sedges; //指向多面体的边；
Vertex *sverts;//指向多面体的顶点
Solid *nexts; //指向后一个多面体
Solid *prevs; //指向前一个多面体
}；
边界表示的数据结构 -半边数据结构
? 面 Struct face
{
ID faceno; //面序号
Solid *fsolid;//指向该面所属的多面体
Loop *floops; //指向构成该面的环
Vector feq; //平面方程
Face *prevf; //指向前一个面；
Face *nextf; //指向后一个面；
}；
边界表示的数据结构 -半边数据结构
? 环 struct loop
? {
? HalfEdge *ledge; //指向构成环的半边
? Face *lface ; //指向该环所属的面
? Loop *prevl; //指向前一个环
? Loop *nextl; //指向后一个环
? }
?
边界表示的数据结构 -半边数据结构
? 边 struct edge
? {
? ID edgeno; //边的序号
? HalfEdge *he1; //指向左半边
? HalfEdge *he2; //指向右半边
? Edge *preve; //指向前一条边
? Edge *nexte; //指向后一条边
? }
边界表示的数据结构 -半边数据结构
? 半边 struct halfedge
? {
? Edge *edge; //指向半边的父边
? Vertex *vtx; //指向半边的起始顶点
? Loop *wloop; //指向半边所属的环
? HalEdge *prv; //指向前一条半边
? HalfEdge *nxt; //指向后一条半边
? }
边界表示的数据结构 -半边数据结构
? 顶点 struct vertex
? {
? ID vertexno; //顶点序号
? HalfEdge *vedge; //指向以该顶点为起
点的半边
? Vector vcoord; //顶点坐标
? Vertex *nextv; //指向前一个顶点
? Vertex *prevv; //指向后一个顶点
? }
欧拉运算和正则集合运算
? 在边界表示法中，可以定义一系列运算
来构造或修改三维实体，常用的这类运
算有：
? 欧拉运算
? 正则集合运算
欧拉运算
欧拉运算是三维物体边界表示数据结构的生成操
作。运用欧拉运算，可以正确、有效构建三维
物体边界表示中的所有拓扑元素和拓扑关系。
该运算之所以称为欧拉运算，是因为每一种运算
所构建的拓扑元素和拓扑关系均要满足欧拉公
式 。
欧拉运算
? 欧拉公式
V：顶点数
E：棱线数
F：面数
? 凡是满足欧拉公式的形体
? 均称为欧拉形体
? 欧拉公式是简单多面体
? 的必要条件。
? 附加条件：每边连接两个顶点
? 每条边只被两个面共享等来保证有效性
V-e+f=2
欧拉运算
? 广义欧拉公式
V-e+f-r=2(s-h)
V：顶点数,E：棱线数,F：面数
r,多面体表面上孔的个数
s,相互分离的多面体数
h,贯穿多面体的孔洞个数
欧拉运算
? 若将广义欧拉公式
? 中的 v,e,f,h,r,s分别看作独立的坐标变量，则上式在
六维空间中定义了一张平面（平面是五维的），该平
面通过原点。
? 由于各坐标变量的取值只能是非负的整数，所以上式
实际上对应了一张五维平面上的网格，每个多面体都
对应一个网格点。但并不是每个网格都对应一个有效
的多面体（只是必要条件）。如果要构造的多面体对
应的网格点的坐标是（ v,e,f,h,r,s ），那么构造该
实体的过程就是从原点开始沿网格一步一步向这个坐
标点前进的过程。由于网格上的每点都满足欧拉公式，
最后的多面体也必然满足它。
V-e+f-r=2(s-h)
欧拉运算
? 前进的, 走法, 是多种多样的，因为只有五个自由变
量，所以只需五种基本走法就可以了。要求：每一步
至多只能使某一坐标变量增（减）一个单位。每一步
行走都有明显的几何意义。
? 欧拉运算是对形体进行增加，删除点、边、面而生成
的一个新的欧拉形的处理。最基本的五种欧拉运算是：
– 增加一条边和一个顶点；
– 增加一个面和一条边；
– 增加一条边,一个面和一个顶点；
– 增加一条边和一个顶点；
– 增加一条边,且删除一个孔穴。
欧拉运算
? 相应的五种补运算是：
– 删除一条边和一个顶点；
– 删除一个面和一条顶点；
– 删除一个体,一个面和一个顶点；
– 删除一个孔洞和一个体；
– 删除一条边,且增加一个孔穴；
? 任何一种欧拉形体 (或欧拉运算 )都可以用最基本的欧
拉运算的现行组合来表示。用最基本的欧拉运算操作
生成的形体必定是一个欧拉形体。
正则集合 运算
通过对边界表示的物体做正则集合运算可以构造新的边
界表示的物体。对具有平面边界、曲面边界的物体进
行集合运算的算法有很多，算法的大致步骤如下：
(1)预检查两物体是否相交
第一步：计算两个待求交物体的包围盒，若两
包围盒不相交，则两物体不相交，正则集合运算结束，
否则进行下一层。
第二步：计算两物体每一个表面片的包围盒，
当某个面片的包围盒与另一物体的包围盒相交时，将
该面片与另一物体的所有表面片一一求交，否则该面
片与另一物体的所有表面片都无交。同样，只有在用
边界盒法无法判断时才进行求交计算，从而避免许多
不必要的复杂的求交计算。
正则集合 运算
(2)计算两物体各表面之间的交线。
由于物体表面均为有界表面，因此物体表面之间的
交线是有界的直线或曲线。计算两物体表面之间的交
线的一般步骤如下
a.基于两相交表面的方程，建立交线的方程，确定
出初始交线。初始交线可能为无界。
b.分别确定初始交线位于两相交表面内部的部分。
c.计算位于两相交表面内部的两相交区段的重叠部
分，即为两相交表面之间的真正交线。
(3)对物体的表面进行分类
两物体之间的交线将它们的表面分割成两部分，其中一
部分落在拼合体的表面上，形成新的边界，另一部分位于
拼合体内或拼合体外，应在集合运算最后一步予以删除。
(4)建立结果物体的边界表示。
正则集合 运算
边界表示
? Brep表示覆盖域大，原则上能表示所有的形体，而且
易于支持形体的特征表示等,Brep表示已成为当前
CAD/CAM系统的主要表示方法。
? Brep表示的优点是：
– 表示形体的点、边、面等几何元素是显式表示的，
使得绘制 Brep表示的形体的速度较快，而且比较容
易确定几何元素间的连接关系；
– 容易支持对物体的各种局部操作，比如进行倒角。
– 便于在数据结构上附加各种非几何信息，如精度、
表面粗糙度等。
边界表示
? Brep表示的缺点是：
– 数据结构复杂，需要大量的存储空间，维护内部数据
结构的程序比较复杂；
– Brep表示不一定对应一个有效形体，通常运用欧拉操
作来保证 Brep表示形体的有效性、正则性等。
各种表示方法的比较
? 精确性：能否精确的表示实体。
? 特征表示 -能够精确表示一个实体。
? 构造实体几何表示 -依赖于它所采用的基本体
素，如果基本体素足够丰富，则能精确描述较
大范围内的实体。
? 边界表示 -如果以多面体表示实体，则仅是一
种近似表示；若允许曲面边界，则可以精确表
示实体。
? 推移表示 -与边界表示类似。
? 空间分割表示 -近似表示一个实体。
各种表示方法的比较
? 表示域：指一种表示法所能表示的实体
的范围。表示域越大，表示能力越强。
特征表示法、推移表示法：表示能力有限
空间分割表示法：可以表示任何实体。
边界表示法：理论上说，可以表示所有实体。但
若将边界表示法中的边界限制在某个范围之内
（如平面多边形），则表示能力降低。
实体构造表示法：依赖其基本体素的范围。
各种表示方法的比较
? 唯一性：实体的表示形式唯一。
只有空间位置枚举方法和八叉树具有唯一性。
各种表示方法的比较
? 封闭性：若其表示域内的实体经过某种
运算（如正则集合运算，几何变换）后，
结果实体仍然落在表示域之内。
特征表示：实体之间不能进行集合运算。
简单推移表示，单元分解表示：不封闭。
空间位置枚举表示，八叉树表示,CSG树表示封
闭。
边界表示虽然对正则集合运算不封闭，但可以附
加约束条件避免。
各种表示方法的比较
? 有效性：
通常，边界表示（包括推移表示）物体的有效性
难以检验。
特征表示的物体有效性自动得到保证。
其它表示方法的有效性验证也比较简单。
各种表示方法的比较
? 简洁性：
空间分割表示：占用空间大
特征表示、推移表示,CSG树表示较简洁。边界
表示介于其间。
各种表示方法的比较
? 输入：
特征表示、推移表示,CSG树表示和单元分解表
示都是面向用户的，只需输入少量参数，即可
生成所需实体。
空间位置枚举和八叉树表示很难由用户直接建立，
一般都由其它表示形式转化过来。
若采用边界表示作为输入手段，则一方面用户能
方便的控制实体的形状，另一方面，需输入大
量数据，且数据一致性很难保证。
各种表示方法的比较
? 输出：
实体造型的输出包括图形、计算机辅助制造系统
进行数控加工所需的数据以及实体的性质（重
量、体积等）。
图形显示和数控加工主要要求实体的边界信息，
所以边界表示较好。
若需实体性质等方面的计算，则空间分割表示、
CSG树表示更好。
模型的考虑
? 模型的考虑
必须考虑以下一些问题：
– 根据形体边界给定的信息，是否能自动的获取形体
的几何特征？
– 如何确定对形体操作数据的有效性？
– 形体的表示模型是否唯一？不同的表示模型是否可
以转换？是否最佳表示模型？
? 对于几何造型系统来说，按照不同的目的可以采用不
同的最佳表示模型。
不规则形体的建模方法
? 迭代函数系统
? 基于文法的模型
? 粒子系统
? 动力系统
L系统
? 由生物学家 Lindenmayer创立
? 基本思想：
? 用文法表示植物的拓扑结构
? 通过图形学方法生成逼真的画面
? DOL系统（确定的上下文无关的 L系统）
? 定义为三元组 <V,w,P>，其中
? V----表示字母集合
? V*----表示 V上所有单词的集合
? w----是一个非空单词，称为公理
? P----产生式集合
?,使得
? 如果没有明显的产生式，则令
*,VxVa ????
xa ?
aa ?
L系统
– 例子 ----Koch 雪花曲线
? V,{F,+,-}
? w,F
? P,F->F-F++F-F
?几何解释
– F：向前画一条线
– +：右转
– -：左转
?
?
L系统
? Bracketed L系统
– 增加如下两个字符
[：压栈
]：出栈
– 例子 ----植物
w,F
P,F->F[+F]F[-F]F
L系统
? 表示形体的两种模型
? 实体的定义
? 正则集合运算
? 特征表示
? 空间分割表示
? 推移表示
? 边界表示
? 构造实体几何表示
? 不规则形体的建模方法
? L系统
9, 1 引 言
? 三维图形在科学研究和工程技术中有着广泛的
应用。在 CAD中，需要对所设计的作品从不同
的角度进行审视。计算机几何造型就是用计算
机系统来表示、控制、分析和输出三维形体。
所以几何造型是计算机图形学中一个十分重要
的应用领域，它是 CAD/CAM和 CIMS系统的
核心技术，也是用来实现计算机辅助设计的基
本手段。几何造型的功能：
– 形体输入,即把形体从用户格式转换成计算
机内部格式；
– 图形数据的 存储和管理 ；
– 图形控制,如对形体进行平移、缩放、旋转
等几何变换；
– 图形修改,如应用集合运算、欧拉运算、有
理 B样条操作及其交互手段实现对形体局部
或整体修改；
– 图形分析,如形体的容差分析，物质特性分
析等；
– 图形显示输出，如消隐、光照、颜色的控制
等；
– 询问 形体的属性 及其 有关参数
9, 2 形 体
? 在计算机形体一般
定义为六层拓扑结
构，首先介绍在三
维空间中基本术语
的定义。
形体 (object)
外壳 (shell)
面 (face)
环 (loop)
边 (loop) 顶点 (vertex)
曲线和直线
方程
点的
几何坐标
形 体
? 体
由封闭表面围成的有效空间称为体 ；一个形体 Q是 R3空
间中非空、有界的封闭子集。其 边界（记为 ?Q） 是有
限个面的并集，而外壳是形体的最大边界。一个单位立
方体可定义为：
{(x,y,z)∈R 3|0≤x≤1,0≤y≤1,0≤z≤1}
其中一个表面可表示为：
{(1,y,z)∈R 3|0≤y≤1,0≤z≤1}
必须注意：并没有规定形体必须是一个连续的
封闭集合，目的是用这样的定义来扩大几何造型的域，
使得形体可以由不连续的体素，或是仅有某些相交的形
体组成。
x
z
y
形 体
? 面
R3中非空、连续、共面且封闭的子集称
为面 F，
其边界 (记为 ?F)是有限条线段的并集，
Pt表示含有 F的唯一平面。
面是形体表面的一部分，且具有方向性,
F
Pt
形 体
? 环
由有序、有向边组成的面的封闭边界
称为环，环中任意边都不能自交，相
邻两条边共享一个端点，环又分为内
环和外环。内环是在已知面中的内孔
或凸台面边界的环，其边按逆时针方
向。外环是已知面的最大外边界的环，
其边按顺时针方向，按这种方式定义，
在面上沿着边的方向前进，面的内部
始终在走向的右侧。
形 体
? 边
形体内两个相邻面的交界称为边，一条边有且仅有两
个相邻面。两个端点确定一条边，这两个端点分别称
为该边的起点和终点。假设 Q是一个形体,E(Q)是形体
边的集合，则在 ?Q(形体的边界 )中 E(Q)满足下属条件
的所有线段的集合：
– 边 e的两个端点属于 V(Q)；
– 边 e中没有一个内部点属于 V(Q)（所有顶点的集合）
– 边 e上每个点，都有两个不同的面，即存在两个面 fi，
fi≤ ?Q使得边 e∈f i∩f j；
– 形体 Q的边框线 WF(Q)是由有序对 (V(Q),E(Q))所组
成。
v1
v2
ef1 f2
形 体
? 点
边的端点称为点，点不能出现在边的内部，也不能孤
立地位于物体内、物体外或面内，顶点又是 ?F(面边界 )
中两条不共线的线段的交点。
v1
v2
ef1 f2
形 体
? 体素
具有有限个参数定义，且简单
的连续封闭的形体称为体素，
如长方体、圆柱体、圆锥、球、环等。
? 半空间
集合 {P|F(P)≤0} 成为半空间，其中 P为 R3中的一点,F为一个平面，
当 F=0时，表示一个平面，这个平面的半空间可以由
F(P)=ax+by+cz+d定义的平面加上在平面某一侧的所有点组成。显
然一个长方体可以看成是 6个平面半空间的交。
? 几何信息
用来表示形体的几何性质和度量关系称为几何信息。
? 拓扑信息
用来表示形体之间的连接关系称为拓扑信息。
表示形体的两种模型
? 数据模型
– 完全以数据描述
– 例如
? 用以 8个顶点表示的立方体
? 以中心点和半径表示的球
– 以数据文件的形式存在
– 包括 ----特征表示、空间分割表示、推移表示、边
界表示、构造实体几何表示等
– 进一步分为
?线框模型
?表面模型
?实体模型
线框模型
线框模型：将形体表示成
一组轮廓线的集合。
– 一般地，画出了形体的棱线与
轮廓线就能唯一地表示出来。
如图，八个顶点可以定义一个
长方体，但还不足以识别它，
如果定义了棱线，则无论如何
放置长方体都能唯一地表示了。
对于多面体由于其轮廓线和棱
线通常是一致的，所以多面体
的线模型更便于识别，且简单。
e12
v4
v8
s3
e2
e4
e6
e8
e2e
7
e11
e10 e9e3
e1
v2
v3
v1
v7
v5v
6 s2
s6
s5
s1 s4
线框模型
– 优点,简单、处理速度快
– 缺点,
1、对于非平面多面体，如圆柱、球等形体，
其轮廓线随观察方向的改变而改变，无法用
一组固定的轮廓线来表示它们。
2、线框模型与形体之间不存在一一对应关系：
它仅仅通过给定的轮廓线约束所表示形体的
边界面，而在轮廓线之间的地方，形体的表
面可以任意变化。
3、没有形体的表面信息，不适于真实感显示，
由此导致表示的形体可能产生二义性。
表面模型
? 表面模型
– 将形体表示成一组表面的集合
– 如果把线框模型中的棱线包围的部分定义为
面，所形成的模型便是表面模型。其数据结
构是在线模型的基础上附加一些指针，有序
地连接棱线。下图中表面编号表示第几个表
面，表面特征表面是平面还是曲面。
– 形体与其表面一一对应，适合于真实感显示
4顶点个数
1起始指针
0表面特征
5表面编号
14
043
032
021
连接指针属
性
顶点
号
1
4
2
3
2
3
4
1
表面模型
? 缺点：
? 不能有效的用来表示实体
? 原因：
? 1、表面模型中的所有面未必形成一个封
闭的边界
? 2、各个面的侧向没有明确定义，即不知
道实体位于面的哪一侧
实体模型
– 实体模型
? 用来描述实体，主要用于 CAD/CAM
? 包含了描述一个实体所需的较多信息，如几何信
息、拓扑信息，可以支持多种运算，如欧拉运算
等。
表示形体的两种模型
? 过程模型
– 以一个过程和相应的控制参数描述
– 例如
? 用一些控制参数和一个生成规则描述的植物
– 以一个数据文件和一段代码的形式存在
– 包括 ----粒子系统,L系统、迭代函数系统等
表示形体的两种模型
? 模型分类
实体的定义
? 抽象带来的问题
– 计算机中表示的物体是无效的
– 不能够客观存在
? 为什么要求客观存在
– CAD/CAM的需求
? 什么是客观存在（有效） — 实 体的定义
– 具有一定的形状
– 具有封闭的边界（表面 )
– 内部连通
– 占据有限的空间
– 经过运算后，仍然是有效的物体
实体的定义
? 将三维物体看做一个点集，它由内点和
边界点共同组成。
? 内点：具有完全包含于该点集的充分小
的邻域
? 边界点：不具有内点性质的点集
实体的定义
A是一个点集，定义点集的正则运算如下：
? i：取内点运算
? c,取闭包运算
? 正则运算 r
? i A,A的全体内点组成的集合，称为 A
的内部
? c i A为 A的内部的闭包的运算，是
i A与其边界点的并集。
AicAr ????
?
??
?
实体的定义
? 正则点集
– 称为 A的正则点集
– 称 A为正则点集，如果它满足
? 问题：正则点集是实体？
Ar?
AAr ??
实体的定义 -举例说明
? 阴影部分：物体的内部区域
? 黑色部分：边界
? (a)图取内点 ->(b)图求闭包 ->(c)图
? 正则运算：去除与物体维数不一致的悬挂部分
或孤立部分。
实体的定义
? 实体的定义 — 可 计算的条件
– 正则点集
– 表面是二维流形
? 二维流形
– 其上任意一点存在充分小的领域与圆盘同构
（存在连续的一一映射）
9, 3 正 则 集 合 运 算
? 为什么需要正则集合运算
– 正则集合运算是构造复杂物体的有效方法
– 普通的集合运算会产生无效物体
– (b),A ∩ B
– ( c ), 普通 A ∩ B
– ( d ),正则 A ∩ B
正则集合运算
? 集合运算（并、交、差）是构造形体的
基本方法。正则形体经过集合运算后，
可能会产生悬边、悬面等低于三维的形
体。
? Requicha在引入正则形体概念的同时，
还定义了正则集合运算的概念。正则集
合运算保证集合运算的结果仍是一个正
则形体，即丢弃悬边、悬面等。
正则集合运算
? 正则集合运算的定义
– 正则并
– 正则交
– 正则差
)(* BopArBopA ??
)(* BArBA ?? ??
)(* BArBA ?? ??
)(* BArBA ????
任一实体 S可以用它的边界 bS和它的内部 iS来表示，即
S=bS ∪ iS
由实体的定义可知,bS是封闭的，它将整个三维空间分成了
三个区域,S的内部 iS,S的边界 bS,S的外部 eS。边界 bS与实
体 S是一一对应的。确定了边界，也就唯一确定了一个实体。
因此，为了求实体 A,B的正则集合运算结果 A op* B，只要
求出其边界 b（ A op* B）即可。
正则集合 运算
正则集合 运算
考察 A,B两物体的交所形成拼合体的边界，
由于 A,B为正则点集，它们均可表示为边界点与体
内点的集合，即 A=bA ∪ iA ; B=bB ∪ iB
A物体的边界 bA可按其位于 B物体内,B物体上、
B物体外而分别表示为
bA = (bA∩iB)∪(bA∩bB) ∪(bA∩eB)
同理,bB = (bB∩iA)∪(bB∩bA)∪(bB∩eA)
A
正则集合 运算
其中 bA ∩ bB = bB ∩ bA 是 A与 B的公
共边界，它可以分成两部分,
（ bA ∩bB ）同侧,(bA ∩bB) 异侧
(bA ∩bB) 同侧由这样一些边界构成,A、
B位于边界的同侧
(bA ∩bB) 异侧由这样一些边界构成,A、
B位于边界的异侧
正则集合 运算
? 对于 A ∩* B,由交的定义可知：
? 1） A,B两物体的边界位于对方内部的部分，即 bA ∩
iB 和 bB ∩ iA 是 b(A ∩* B ) 的组成部分。
? 2） A,B两物体的边界位于对方外部的部分，即 bA
∩ eB 和 bB ∩ eA 不是 b(A ∩* B ) 的组成部分。
? 3）对于 A,B的重合边界有,(bA ∩bB) 同侧属于 b(A
∩* B ); (bA ∩bB) 异侧不属于 b(A ∩* B ) 因此：
? b(A∩*B)=(bA ∩ iB) ∪(bB ∩ iA)∪(bA∩ bB) 同侧
正则集合 运算
? 同理：
? b(A∪ *B)=(bA ∩ eB) ∪ (bB ∩ eA)∪ (bA∩bB)同
侧
? b(A－ *B)=(bA ∩ eB) ∪ (bB ∩ iA)∪ (bA∩bB)异侧
一些非正则形体的实例
? 一些非正则形体的实例
( a ) 有悬面 ( b ) 有悬边
（c ）一条边有两个以上
的邻面（不连通）
图3, 2, 1 非正则形体实例
? 为了能够处理非正则形体, 产生了非正
则造型技术 。
? 九十年代以来, 基于约束的参数化, 变
量化造型和支持线框, 曲面, 实体统一
表示的非正则形体造型技术已成为几何
造型技术的主流 。
9, 4 形 体 表 示 模 型
?在实体模型的表示中，基本上可以分
为分解表示、构造表示和边界表示三
大类。
?1、分解表示
将形体按某种规则分解为小的更易于描述的部
分，每一小部分又可分为更小的部分，这种
分解过程直至每一小部分都能够直接描述为
止。
9.4.1 分解表示 -空间位置枚举表示
– 形体空间细分为小的均匀的立方体单元。
– 用三维数组 C[I][J][K]表示物体，数组中的元素与单
位小立方体一一对应
?当 C[I][J][K] = 1时，表示对应的小立方体被物体
占据
?当 C[I][J][K] = 0时，表示对应的小立方体没有被
物体占据
分解表示 -空间位置枚举表示
– 优点
? 简单，可以表示任何物体
? 容易实现物体间的交、并、差集合运算
? 容易计算物体的整体性质，如体积等
– 缺点
? 占用大量的存储空间，如 1024*1024*1024 = 1G
bits
? 物体的边界面没有显式的解析表达式，不适于图
形显示
? 对物体进行几何变换困难，如非 90度的旋转变换
? 是物体的非精确表示
分解表示 -八叉树表示
? 八叉树表示
– 对空间位置枚举表示的空间分割方法作了改进：均
匀分割 自适应分割
– 八叉树建立过程
?八叉树的根节点对应整个物体空间
?如果它完全被物体占据，将该节点标记为 F(Full)，
算法结束；
?如果它内部没有物体，将该节点标记为 E(Empty)，
算法结束；
?如果它被物体部分占据，将该节点标记为 P(Partial)，
并将它分割成 8个子立方体，对每一个子立方体进行
同样的处理
分解表示 -八叉树表示
? 8叉树的表示应用三维形体的分解，
它对一个外接立方体的形体进行
前后、左右、上下等部分 8个小立
方体，如果小立方体单元为满或
为空，表示该立方体完全在形体
中或完全不在形体中，则其停止
分解；对部分形体占有的小立方
体需进一步分解为 8个子立方体，
直至所有小立方体单元要么全部
满，要么全部空，或已分解到规
定的分解精度为止。
2 36 7
2
0 1
3
1
3 7
5
具有子孙的节点 (P)
空节点 (E)
实节点 (F)
分解表示 -八叉树表示
– 优点
? 可以表示任何物体，且形体表示的数据结构简单
? 简化了形体的集合运算。只需同时遍历参加集合
运算的两形体相应的八叉树，无需进行复杂的求
交运算。
? 简化了隐藏线（或面）的消除，因为在八叉树表
示中，形体上各元素已按空间位置排成了一定的
顺序。
? 分析算法适合于并行处理。
– 缺点
? 没有边界信息，不适于图形显示
? 对物体进行几何变换困难
? 是物体的非精确表示
? 占用大量存储。实际上，八叉树表示是以存储空
间换取算法的效率
分解表示 -线性八叉树表示
线性八叉树：用一可变长度
的一维数组来存储一棵八
叉树。数组中仅存储八叉
树的性质为 FULL的终端结
点。并用一个八进制数表
示该结点在八叉树中的位
置。编码方式为：
Q1Q2… Qm,其中 Q1表示该
结点所属的一级父结点的
编号（ 0-7），以此类推。
例右图为：
{1X,30X,31X,323X,33X}
2 36 7
2
0 1
3
1
3 7
5
具有子孙的节点 (P)
空节点 (E)
实节点 (F)
分解表示 -单元分解表示
? 单元分解表示
– 对空间位置枚举表示的空间分割方法作了改进：单
一体素 多种体素
– 三种空间分割方法的比较
? 空间位置枚举表示 ----同样大小 立方体粘合在一起表示物体
? 八叉树表示 ----不同大小的立方体 粘合在一起表示物体
? 单元分解表示 ----多种体素 粘合在一起表示物体
分解表示 -单元分解表示
– 优点
? 表示简单
? 容易实现几何变换
? 基本体素可以按需选择，表示范围较广
? 可以精确表示物体
– 缺点
? 物体的表示不唯一
? 物体的有效性难以保证
9, 4, 2 构造表示
? 扫描表示
? 构造实体几何表示（ CSG）
? 特征表示
构造表示 -推移表示
? 将物体 A沿着轨迹 P推移得到物体 B，称 B
为 sweep体
? 平移 sweep----将一个二维区域沿着一个
矢量方向推移
构造表示 -推移表示
? 旋转 sweep----将一个二维区域绕旋转轴
旋转一周
? 三维形体也能在空间通过扫
描变换生成新的形体：如左
图，一个圆柱体按指定方向
在长方体上运动生成新的形
体，这个过程犹如长方体与
运动者的圆柱体不断的作差
运算操作。
有时经过扫描变换所生成的形体可能会出现维数不一致问题。
构造表示 -推移表示
扫描线方向
U
构造表示 -推移表示
? 广义 sweep
– 任意物体沿着任意轨迹推移
– 推移过程中物体可以变形
构造表示 -推移表示
? 优点
– 表示简单、直观
– 适合做图形输入手段
? 缺点
– 作几何变换困难
– 对几何运算不封闭
– 用扫描变换产生的形体可能出现维数不一致的问题。
– 扫描方法不能直接获取形体的边界信息，表示形体
的覆盖域非常有限。
构造表示 -构造实体几何表示 (CSG)
.通过对体素定义运算而得到新的形体的一种
表示方法。体素可以是立方体、圆柱、圆锥
等，也可以是半空间，其运算为变换或正则
集合运算并、交、差。
CSG表示可以看成是一棵有序的二叉树。
?其终端节点或是体素、或是形体变换参数。
?非终端结点或是正则的集合运算，或是变换（平
移和 /或旋转）操作，这种运算或变换只对其紧
接着的子结点（子形体）起作用。
构造表示 -构造实体几何表示 (CSG)
构造表示 -构造实体几何表示 (CSG)
? CSG树是无二义性的，但不是唯一的,
CSG表示的优点：
?数据结构比较简单，数据量比较小，内部
数据的管理比较容易；
?物体的有效性自动得到保证；
?CSG方法表示的形体的形状，比较容易修
改。
构造表示 -构造实体几何表示 (CSG)
CSG表示的缺点：
?对形体的表示受体素的种类和对体素操作
的种类的限制，也就是说,CSG方法表示
形体的覆盖域有较大的局限性。
?对形体的局部操作不易实现，例如，不能
对基本体素的交线倒圆角；
?由于形体的边界几何元素（点、边、面）
是隐含地表示在 CSG中，故显示与绘制 CSG
表示的形体需要较长的时间。
?表示不唯一
构造表示 -特征表示
? 用一组特征参数表示一组类似的物体
? 特征包括形状特征、材料特征等
? 适用于工业上标准件的表示
构造表示 -特征表示
– 从应用层来定义形体，因而可以较好的表达
设计者的意图。从功能上可分为形状、精度、
材料和技术特征。
– 特征是面向应用、面向用户的。特征模型的
表示仍然要通过传统的几何造型系统来实现。
不同的应用领域，具有不同的应用特征。
– 在几何造型系统中，根据特征的参数我们并
不能直接得到特征的几何元素信息，而在对
特征及在特征之间进行操作时需要这些信息。
– 特征方法表示形体的覆盖域受限于特征的种
类。
构造表示的特点
? 构造表示的特点：
– 构造表示通常具有不便于直接获取形体几何
元素的信息、覆盖域有限等缺点，
– 但是，便于用户输入形体，在 CAD/CAM系统
中，通常作为辅助表示方法。
边界表示
? 边界表示（ BR表示或 BRep表示）
– 按照体－面－环－边－点的层次，详细记录
了构成形体的所有几何元素的几何信息及其相
互连接的拓扑关系。
– 边界表示的一个重要特点是在该表示法中，
描述形体的信息包括几何信息（ Geometry）
和拓扑信息（ Topology）两个方面。
?拓扑信息描述形体上的顶点、边、面的连接关系，
拓扑信息形成物体边界表示的, 骨架, 。
?形体的几何信息犹如附着在, 骨架, 上的肌肉。
边界表示
? 边界模型表达形体的基本拓扑实体包括：
– 1,顶点
– 2,边。边有方向，它由起始顶点和终止顶
点来界定。边的形状（ Curve）由边的几何
信息来表示，可以是直线或曲线，曲线边可
用一系列控制点或型值点来描述，也可用显
式、隐式或参数方程来描述。
边界表示
– 3,环。环（ Loop）是有序、有向边
（ Edge）组成的封闭边界。环有方向、内
外之分，外环边通常按逆时针方向排序，内
环边通常按顺时针方向排序。
– 4.面。面（ Face）由一个外环和若干个内
环（可以没有内环）来表示，内环完全在外
环之内。
?若一个面的外法矢向外，称为正向面；反之，称
为反向面。
边界表示
?面的形状可以是平面或曲面。平面可用平面方程
来描述，曲面可用控制多边形或型值点来描述，
也可用曲面方程（隐式、显式或参数形式）来描
述。对于参数曲面，通常在其二维参数域上定义
环，这样就可由一些二维的有向边来表示环，集
合运算中对面的分割也可在二维参数域上进行。
– 5.体。体（ Body）是面的并集。
边界表示
? 边界表示模型是一种采用描述形体表面的方法来描述
的几何表示模型。一个形体一般可以通过其边界拆成
一些有界的, 面, 或, 小片, 的子集来表示，而每一
个面又可以通过其边界的边和顶点来表示。若面的表
示无二义性，则其边界表示模型也无二义性，但通常
不一定只有唯一的表示。
U
图3, 2, 1 0 边界表示
边界表示的数据结构
? 边界表示法的数据结构有四种方法：以面为基
础, 以顶点为基础, 以边为基础和翼边结构；
? 以面为基础的数据结构
? 以面为基础, 按照体, 面, 顶点坐标的树
结构层次组织元素数据；如
? 面 顶点坐标
? F1
(X1Y1Z1,X2Y2Z2,X3Y3Z3,X4Y4Z4)
? F2
(X1Y1Z1,X2Y2Z2,X6Y6Z6,X5Y5Z5)
? …
……,.
? 其中顶点按照外观顺时针顺序；
边界表示的数据结构
? 2,以顶点为基础的数据结构
? 以顶点 /坐标和面 /顶点序列两张关系表表
示, 如：
? 顶点 坐标 面 顶点序列
? V1 X1Y1Z1 F1 V1V2V3V4
? ……………………………………………………
……………,.
? 3.以边为基础的数据结构
? 以边 /顶点, 顶点 /坐标, 面 /边三张关系
表表示；
边界表示模型
? 四棱椎边界表示的例子如右，由 4
个面组成，且这种表示可以看作是
含有体、面、边、顶点为节点的有
向图
? 四棱椎边界表示也可以基于边界的
三角形分解，即把形体的边界拆成
一些互不重叠的三角形。
v1 v
2
v3v
4
v5
v2
v3v4
v5
e1 e2
e3f
1v1
四棱柱
面节点
边节点
顶点坐标
f1 f2 f3 ….
e1 e2 e3 e4 ….
v1 v2 v3….
(x1,y1,z1)
组合
结构
坐标
信息
….
边界表示的数据结构 -翼边数据结构
? 翼边数据结构：在 1972年，由
美国斯坦福大学 Baumgart作为
多面体的表示模式提出。
– 它用指针记录了每一边的两个邻
面（即左外环和右外环）、两个
顶点、两侧各自相邻的两个邻边
（即左上边、左下边、右上边和
右下边），用这一数据结构表示
多面体模型是完备的，但它不能
表示带有精确曲面边界的实体。
左下边
右下边
右上边
左上边
边
左外环 右外环
图3.2.11 翼 边数据结构
边界表示的数据结构 -翼边数据结构
? 翼边结构由四种结点 Solid,Face,edge和
Vertex组成的, 各结点描述如下：
?
? Solid 构成引用的根节点 。
? 在任意时刻, 会存在几个数据结构引用；为了
存取其中的任何一个, 需要指向其 Solid节点
的指针 。 通过指向三个双向链表的指针,
Solid 节点给出对该模型的面, 边和顶点的访
问 。 所有实体被链接到一个双向链表中, 这个
表通过指向该表的后继和前趋实体的指针来实
现的 。 具体包括：
?
边界表示的数据结构 -翼边数据结构
? S o l i d ID;
? 指向 face的链表指针；
? 指向 edge的链表指针；
? 指向 vertex的链表指针；
?
?
边界表示的数据结构 -翼边数据结构
? Face 表示多面体的一个小平面,包括：
? Face ID ；
? 指向 face的链表首元素的指针；
? 指向 face的下一元素的指针；
?
边界表示的数据结构 -翼边数据结构
? Edge 由 Edge节点构成, 是整个数据结构的
核心, 每个 Edge结点代表一条边, 包括：
? Edge ID ;
? Edge的起始顶点指针；
? Edge的终止顶点指针；
? Edge的右邻面的指针；
? Edge的左邻面的指针；
? Edge的右方向向前邻边指针；
? Edge的右方向向后邻边指针；
? Edge的左方向向前邻边指针；
? Edge的左方向向后邻边指针；
?
边界表示的数据结构 -翼边数据结构
? Vertex 由 vertex节点构成, 包括：
? Vertex ID ;
? 顶点坐标 (x,y,z) ;
? 指向与该 vertex相连的第一条边指针；
? 指向下一个 Vertex结点指针；
?
边界表示的数据结构 -半边数据结构
? 半边数据结构，是在 80年代
提出的，作为一种多面体的
表示方法。在构成多面体的
三要素（顶点、边、面）中，
半边数据结构以边为核心。
一条边表示成拓扑意义上方
向相反的两条“半边”，所
以称为半边数据结构。
? 其中各节点的数据结构及含
义如下：
边界表示的数据结构 -半边数据结构
? typedef float vector[4];
? typedef short ID;
? typedef struct solid Solid ;
? typedef struct face Face ;
? typedef struct loop Loop ;
? typedef struct edge Edge ;
? typedef struct halfedge HalfEdge ;
? typedef struct vertex Vertex ;
边界表示的数据结构 -半边数据结构
? 多面体
struct solid
{
ID solidno; //多面体序号
Face *sfaces; //指向多面体的面；
Edge *sedges; //指向多面体的边；
Vertex *sverts;//指向多面体的顶点
Solid *nexts; //指向后一个多面体
Solid *prevs; //指向前一个多面体
}；
边界表示的数据结构 -半边数据结构
? 面 Struct face
{
ID faceno; //面序号
Solid *fsolid;//指向该面所属的多面体
Loop *floops; //指向构成该面的环
Vector feq; //平面方程
Face *prevf; //指向前一个面；
Face *nextf; //指向后一个面；
}；
边界表示的数据结构 -半边数据结构
? 环 struct loop
? {
? HalfEdge *ledge; //指向构成环的半边
? Face *lface ; //指向该环所属的面
? Loop *prevl; //指向前一个环
? Loop *nextl; //指向后一个环
? }
?
边界表示的数据结构 -半边数据结构
? 边 struct edge
? {
? ID edgeno; //边的序号
? HalfEdge *he1; //指向左半边
? HalfEdge *he2; //指向右半边
? Edge *preve; //指向前一条边
? Edge *nexte; //指向后一条边
? }
边界表示的数据结构 -半边数据结构
? 半边 struct halfedge
? {
? Edge *edge; //指向半边的父边
? Vertex *vtx; //指向半边的起始顶点
? Loop *wloop; //指向半边所属的环
? HalEdge *prv; //指向前一条半边
? HalfEdge *nxt; //指向后一条半边
? }
边界表示的数据结构 -半边数据结构
? 顶点 struct vertex
? {
? ID vertexno; //顶点序号
? HalfEdge *vedge; //指向以该顶点为起
点的半边
? Vector vcoord; //顶点坐标
? Vertex *nextv; //指向前一个顶点
? Vertex *prevv; //指向后一个顶点
? }
欧拉运算和正则集合运算
? 在边界表示法中，可以定义一系列运算
来构造或修改三维实体，常用的这类运
算有：
? 欧拉运算
? 正则集合运算
欧拉运算
欧拉运算是三维物体边界表示数据结构的生成操
作。运用欧拉运算，可以正确、有效构建三维
物体边界表示中的所有拓扑元素和拓扑关系。
该运算之所以称为欧拉运算，是因为每一种运算
所构建的拓扑元素和拓扑关系均要满足欧拉公
式 。
欧拉运算
? 欧拉公式
V：顶点数
E：棱线数
F：面数
? 凡是满足欧拉公式的形体
? 均称为欧拉形体
? 欧拉公式是简单多面体
? 的必要条件。
? 附加条件：每边连接两个顶点
? 每条边只被两个面共享等来保证有效性
V-e+f=2
欧拉运算
? 广义欧拉公式
V-e+f-r=2(s-h)
V：顶点数,E：棱线数,F：面数
r,多面体表面上孔的个数
s,相互分离的多面体数
h,贯穿多面体的孔洞个数
欧拉运算
? 若将广义欧拉公式
? 中的 v,e,f,h,r,s分别看作独立的坐标变量，则上式在
六维空间中定义了一张平面（平面是五维的），该平
面通过原点。
? 由于各坐标变量的取值只能是非负的整数，所以上式
实际上对应了一张五维平面上的网格，每个多面体都
对应一个网格点。但并不是每个网格都对应一个有效
的多面体（只是必要条件）。如果要构造的多面体对
应的网格点的坐标是（ v,e,f,h,r,s ），那么构造该
实体的过程就是从原点开始沿网格一步一步向这个坐
标点前进的过程。由于网格上的每点都满足欧拉公式，
最后的多面体也必然满足它。
V-e+f-r=2(s-h)
欧拉运算
? 前进的, 走法, 是多种多样的，因为只有五个自由变
量，所以只需五种基本走法就可以了。要求：每一步
至多只能使某一坐标变量增（减）一个单位。每一步
行走都有明显的几何意义。
? 欧拉运算是对形体进行增加，删除点、边、面而生成
的一个新的欧拉形的处理。最基本的五种欧拉运算是：
– 增加一条边和一个顶点；
– 增加一个面和一条边；
– 增加一条边,一个面和一个顶点；
– 增加一条边和一个顶点；
– 增加一条边,且删除一个孔穴。
欧拉运算
? 相应的五种补运算是：
– 删除一条边和一个顶点；
– 删除一个面和一条顶点；
– 删除一个体,一个面和一个顶点；
– 删除一个孔洞和一个体；
– 删除一条边,且增加一个孔穴；
? 任何一种欧拉形体 (或欧拉运算 )都可以用最基本的欧
拉运算的现行组合来表示。用最基本的欧拉运算操作
生成的形体必定是一个欧拉形体。
正则集合 运算
通过对边界表示的物体做正则集合运算可以构造新的边
界表示的物体。对具有平面边界、曲面边界的物体进
行集合运算的算法有很多，算法的大致步骤如下：
(1)预检查两物体是否相交
第一步：计算两个待求交物体的包围盒，若两
包围盒不相交，则两物体不相交，正则集合运算结束，
否则进行下一层。
第二步：计算两物体每一个表面片的包围盒，
当某个面片的包围盒与另一物体的包围盒相交时，将
该面片与另一物体的所有表面片一一求交，否则该面
片与另一物体的所有表面片都无交。同样，只有在用
边界盒法无法判断时才进行求交计算，从而避免许多
不必要的复杂的求交计算。
正则集合 运算
(2)计算两物体各表面之间的交线。
由于物体表面均为有界表面，因此物体表面之间的
交线是有界的直线或曲线。计算两物体表面之间的交
线的一般步骤如下
a.基于两相交表面的方程，建立交线的方程，确定
出初始交线。初始交线可能为无界。
b.分别确定初始交线位于两相交表面内部的部分。
c.计算位于两相交表面内部的两相交区段的重叠部
分，即为两相交表面之间的真正交线。
(3)对物体的表面进行分类
两物体之间的交线将它们的表面分割成两部分，其中一
部分落在拼合体的表面上，形成新的边界，另一部分位于
拼合体内或拼合体外，应在集合运算最后一步予以删除。
(4)建立结果物体的边界表示。
正则集合 运算
边界表示
? Brep表示覆盖域大，原则上能表示所有的形体，而且
易于支持形体的特征表示等,Brep表示已成为当前
CAD/CAM系统的主要表示方法。
? Brep表示的优点是：
– 表示形体的点、边、面等几何元素是显式表示的，
使得绘制 Brep表示的形体的速度较快，而且比较容
易确定几何元素间的连接关系；
– 容易支持对物体的各种局部操作，比如进行倒角。
– 便于在数据结构上附加各种非几何信息，如精度、
表面粗糙度等。
边界表示
? Brep表示的缺点是：
– 数据结构复杂，需要大量的存储空间，维护内部数据
结构的程序比较复杂；
– Brep表示不一定对应一个有效形体，通常运用欧拉操
作来保证 Brep表示形体的有效性、正则性等。
各种表示方法的比较
? 精确性：能否精确的表示实体。
? 特征表示 -能够精确表示一个实体。
? 构造实体几何表示 -依赖于它所采用的基本体
素，如果基本体素足够丰富，则能精确描述较
大范围内的实体。
? 边界表示 -如果以多面体表示实体，则仅是一
种近似表示；若允许曲面边界，则可以精确表
示实体。
? 推移表示 -与边界表示类似。
? 空间分割表示 -近似表示一个实体。
各种表示方法的比较
? 表示域：指一种表示法所能表示的实体
的范围。表示域越大，表示能力越强。
特征表示法、推移表示法：表示能力有限
空间分割表示法：可以表示任何实体。
边界表示法：理论上说，可以表示所有实体。但
若将边界表示法中的边界限制在某个范围之内
（如平面多边形），则表示能力降低。
实体构造表示法：依赖其基本体素的范围。
各种表示方法的比较
? 唯一性：实体的表示形式唯一。
只有空间位置枚举方法和八叉树具有唯一性。
各种表示方法的比较
? 封闭性：若其表示域内的实体经过某种
运算（如正则集合运算，几何变换）后，
结果实体仍然落在表示域之内。
特征表示：实体之间不能进行集合运算。
简单推移表示，单元分解表示：不封闭。
空间位置枚举表示，八叉树表示,CSG树表示封
闭。
边界表示虽然对正则集合运算不封闭，但可以附
加约束条件避免。
各种表示方法的比较
? 有效性：
通常，边界表示（包括推移表示）物体的有效性
难以检验。
特征表示的物体有效性自动得到保证。
其它表示方法的有效性验证也比较简单。
各种表示方法的比较
? 简洁性：
空间分割表示：占用空间大
特征表示、推移表示,CSG树表示较简洁。边界
表示介于其间。
各种表示方法的比较
? 输入：
特征表示、推移表示,CSG树表示和单元分解表
示都是面向用户的，只需输入少量参数，即可
生成所需实体。
空间位置枚举和八叉树表示很难由用户直接建立，
一般都由其它表示形式转化过来。
若采用边界表示作为输入手段，则一方面用户能
方便的控制实体的形状，另一方面，需输入大
量数据，且数据一致性很难保证。
各种表示方法的比较
? 输出：
实体造型的输出包括图形、计算机辅助制造系统
进行数控加工所需的数据以及实体的性质（重
量、体积等）。
图形显示和数控加工主要要求实体的边界信息，
所以边界表示较好。
若需实体性质等方面的计算，则空间分割表示、
CSG树表示更好。
模型的考虑
? 模型的考虑
必须考虑以下一些问题：
– 根据形体边界给定的信息，是否能自动的获取形体
的几何特征？
– 如何确定对形体操作数据的有效性？
– 形体的表示模型是否唯一？不同的表示模型是否可
以转换？是否最佳表示模型？
? 对于几何造型系统来说，按照不同的目的可以采用不
同的最佳表示模型。
不规则形体的建模方法
? 迭代函数系统
? 基于文法的模型
? 粒子系统
? 动力系统
L系统
? 由生物学家 Lindenmayer创立
? 基本思想：
? 用文法表示植物的拓扑结构
? 通过图形学方法生成逼真的画面
? DOL系统（确定的上下文无关的 L系统）
? 定义为三元组 <V,w,P>，其中
? V----表示字母集合
? V*----表示 V上所有单词的集合
? w----是一个非空单词，称为公理
? P----产生式集合
?,使得
? 如果没有明显的产生式，则令
*,VxVa ????
xa ?
aa ?
L系统
– 例子 ----Koch 雪花曲线
? V,{F,+,-}
? w,F
? P,F->F-F++F-F
?几何解释
– F：向前画一条线
– +：右转
– -：左转
?
?
L系统
? Bracketed L系统
– 增加如下两个字符
[：压栈
]：出栈
– 例子 ----植物
w,F
P,F->F[+F]F[-F]F
L系统
