（a）
（b）
（c） 图3.2.6 生成扫描体时维数不 一致的情况
（d）
清华大学计算机科学与技术系
计算机图形学基础
(b)构造实体几何表示(CSG).通过对体素定义 运算而得到新的形体的一种表示方法。体素 可以是立方体、圆柱、圆锥等，也可以是半 空间，其运算为变换或正则集合运算并、交、 差。
CSG表示可以看成是一棵有序的二叉树。 • 其终端节点或是体素、或是形体变换参数。 • 非终端结点或是正则的集合运算，或是变换（平 移和/或旋转）操作，这种运算或变换只对其紧 接着的子结点（子形体）起作用。
清华大学计算机科学与技术系 计算机图形学基础
• Brep表示的缺点是：
–数据结构复杂，需要大量的存储空间，维护内部数据 结构的程序比较复杂； –Brep表示不一定对应一个有效形体，通常运用欧拉操 作来保证Brep表示形体的有效性、正则性等。
• Brep表示覆盖域大，原则上能表示所有的形体， 而且易于支持形体的特征表示等，Brep表示已成 为当前CAD/CAM系统的主要表示方法。
清华大学计算机科学与技术系 计算机图形学基础
• 对形体的局部操作不易实现，例如，不能对基 本体素的交线倒圆角； • 由于形体的边界几何元素（点、边、面）是隐含 地表示在CSG中，故显示与绘制CSG表示的形体需 要较长的时间。
(c)特征表示
–从应用层来定义形体，因而可以较好的表达 设计者的意图。从功能上可分为形状、精度、 材料和技术特征。
清华大学计算机科学与技术系
计算机图形学基础
• 3．边界表示（BR表示或BRep表示）
–按照体－面－环－边－点的层次，详细记录 了构成形体的所有几何元素的几何信息及其相 互连接的拓扑关系。 –边界表示的一个重要特点是在该表示法中， 描述形体的信息包括几何信息（Geometry）和 拓扑信息（Topology）两个方面。
清华大学计算机科学与技术系 计算机图形学基础
• 面的形状可以是平面或曲面。平面可用平面方程 来描述，曲面可用控制多边形或型值点来描述， 也可用曲面方程（隐式、显式或参数形式）来描 述。对于参数曲面，通常在其二维参数域上定义 环，这样就可由一些二维的有向边来表示环，集 合运算中对面的分割也可在二维参数域上进行。
• 点是三维空间的一个位置 • 边可以是直线边或曲线边，边的端点可以重合。 • 环是由首尾相接的一些边组成，而且最后一条边的终 点与第一条边的起点重合；环也可以是一个孤立点。 外壳是一些点、边、环、面的集合； • 外壳是一些点、边、环、面的集合。 • 区域由一组外壳组成。 • 模型由区域组成。
清华大学计算机科学与技术系
清华大学计算机科学与技术系 计算机图形学基础
A
B
A
B
A a B b b a
悬边
C=A∩B
集合论的求交计算
C * =A * B
正则集合下的求交运算
图3.2.2 二个二维图形的交产 生一个退化的结果
图3.2.3 集合和正则的交运算
清华大学计算机科学与技术系
计算机图形学基础
• 为了能够处理非正则形体，产生了非正 则造型技术。 • 九十年代以来，基于约束的参数化、变 量化造型和支持线框、曲面、实体统一 表示的非正则形体造型技术已成为几何 造型技术的主流。
清华大学计算机科学与技术系
计算机图形学基础
6 7 2 3 7 2 3 3 5 0 1 1
（b）
（a）
具有子孙的节点 空节点 实节点 （c） 图3.2.4 清华大学计算机科学与技术系 用八叉树表示形体 计算机图形学基础
• 2．构造表示。通常有扫描表示、构造实 体几何表示和特征表示三种。
(a)扫描表示。基于一个基体（一般是一个封 闭的平面轮廓）沿某一路径运动而产生形体。
清华大学计算机科学与技术系 计算机图形学基础
(b)八叉树法表示形体.首先对形体定义一个外接立方 体，再把它分解成八个子立方体，并对立方体依次 编号为0，1，2，„，7。如果子立方体单元已经一 致，即为满（该立方体充满形体）或为空（没有形 体在其中），则该子立方体可停止分解；否则，需 要对该立方体作进一步分解，再一分为八个子立方 体。在八叉树中，非叶结点的每个结点都有八个分 支。 优点主要是： （1）形体表示的数据结构简单。
清华大学计算机科学与技术系 计算机图形学基础
左外环
右外环 边
图3.2.11
左 下 边
翼边数据结构
清华大学计算机科学与技术系
右 边 下 右
上 边
边 上 左
计算机图形学基础
• 辐射边：为了表示非正则形体，1986年， Weiler提出了辐射边（Radial Edge）数据结 构。
– 辐射边结构的形体模型由几何信息和拓扑信息 两部分组成。
清华大学计算机科学与技术系 计算机图形学基础
应用系统
R
用户
特征造型器
特征模型
L W
H
H
H R
几何造型器
几何模型
（a）方块
图3.2.8 基于特征的造型系统
（b）圆柱 图3.2.9 特征形状表示
（c）圆锥
清华大学计算机科学与技术系
计算机图形学基础
• 构造表示的特点：
–构造表示通常具有不便于直接获取形体几何 元素的信息、覆盖域有限等缺点， –但是，便于用户输入形体，在CAD/CAM系统 中，通常作为辅助表示方法。
3.2形体在计算机内的表示 清华大学
• 3.2.1 引言 • 计算机中表示形体，通常用线框、表面 和实体三种模型。 • 对于任一形体，如果它是3维欧氏空间中 非空、有界的封闭子集，且其边界是二 维流形（即该形体是连通的），我们称 该形体为正则形体，否则称为非正则形 体。
清华大学计算机科学与技术系 计算机图形学基础
–5.体。体（Body）是面的并集。
清华大学计算机科学与技术系
计算机图形学基础
3.2.3.2 边界表示的数据结构
• 翼边数据结构：在1972年，由美国斯坦 福大学Baumgart作为多面体的表示模式 提出。
– 它用指针记录了每一边的两个邻面（即左外 环和右外环）、两个顶点、两侧各自相邻的 两个邻边（即左上边、左下边、右上边和右 下边），用这一数据结构表示多面体模型是 完备的，但它不能表示带有精确曲面边界的 实体。
• 拓扑信息描述形体上的顶点、边、面的连接关系， 拓扑信息形成物体边界表示的“骨架”。 • 形体的几何信息犹如附着在“骨架”上的肌肉。
清华大学计算机科学与技术系 计算机图形学基础
U
图3.2.10 边界表示
清华大学计算机科学与技术系
计算机图形学基础
• Brep表示的优点是：
–表示形体的点、边、面等几何元素是显式表 示的，使得绘制Brep表示的形体的速度较快， 而且比较容易确定几何元素间的连接关系； –容易支持对物体的各种局部操作，比如进行 倒角。 –便于在数据结构上附加各种非几何信息，如 精度、表面粗糙度础
3.2.3 形体的边界表示模型
• 3.2.3.1 边界表示的基本实体 • 边界模型表达形体的基本拓扑实体包括：
–1. 顶点 –2. 边。边有方向，它由起始顶点和终止顶 点来界定。边的形状（Curve）由边的几何 信息来表示，可以是直线或曲线，曲线边可 用一系列控制点或型值点来描述，也可用显 式、隐式或参数方程来描述。
（1）采用自顶向下的设计思想。在形体的表示上， 遵循了从大到小，分解表示的原则； （2）支持非流形形体的表示； （3）实体拓扑数据与几何数据双链表连接，存放 紧凑； （4）能够支持特征造型。
清华大学计算机科学与技术系
计算机图形学基础
3.2.3.3 欧拉操作
• 对于任意的简单多面体，其面(f)、边(e)、 顶点(v)的数目满足 欧拉公式 v-e+f=2 • 对于任意的正则形体，引入形体的其它 几个参数：形体所有面上的内孔总数(r)、 穿透形体的孔洞数(h)和形体非连通部分 总数(s)，则形体满足公式： v - e + f = 2(s-h) + r
计算机图形学基础
model region
中心线 剖切平面
shell
中心线
face use loop use edge use vertex use topology 图3.2.12
face loop
实体
edge vertex geometry 辐射边数据结构
图3.2.13 一个用辐射边结构表示的 非正则形体模型
清华大学计算机科学与技术系 计算机图形学基础
–3. 环。环（Loop）是有序、有向边（Edge） 组成的封闭边界。环有方向、内外之分，外 环边通常按逆时针方向排序，内环边通常按 顺时针方向排序。 –4.面。面（Face）由一个外环和若干个内环 （可以没有内环）来表示，内环完全在外环 之内。
• 若一个面的外法矢向外，称为正向面；反之，称 为反向面。
清华大学计算机科学与技术系 计算机图形学基础
差（-）
x
差（-）
平移
1
2
2
x
x

=体素
清华大学计算机科学与技术系
图3.2.7 CSG表示
计算机图形学基础
• CSG树是无二义性的，但不是唯一的.
CSG表示的优点： • 数据结构比较简单，数据量比较小，内部数据 的管理比较容易； • CSG表示可方便地转换成边界（Brep）表示； • CSG方法表示的形体的形状，比较容易修改。 CSG表示的缺点： • 对形体的表示受体素的种类和对体素操作的种 类的限制，也就是说，CSG方法表示形体的覆盖 域有较大的局限性。
清华大学计算机科学与技术系
计算机图形学基础
• 清华大学国家CAD工程中心开发的几何造型系统GEMS5.0中，采 用的数据结构如图 体组
特征表示 线框 面组 单体(零件)