第八讲 实体几何造型

用指针记录了每一边的两个 邻面（即左外环和右外环）、 两个顶点、两侧各自相邻的两 个邻边（即左上边、左下边、 右上边和右下边）
• Brep表示优缺点是： • 优点 容易确定几何元素间的连接关系；
• 缺点： 数据结构复杂，需要大量的存储空间，维护内 部数据结构的程序比较复杂； Brep表示不一定对应一个有效形体，通常运用 欧拉操作来保证Brep表示形体的有效性、正则 性等。
v5
v8
v2
表面模型的优点： 比线框模型立体感强； 形体与其表面一一对应，表达了物体的表面形状， 消除了多义性； 易于计算面积 表面模型存在的问题： 表面模型中的所有面未必形成一个封闭的边界； 各个面的侧向没有明确定义，即不知道实体位于 面的哪一侧。
在面模型上打孔， 内部为“空洞”
• 形体一般定义为六层拓 扑结构，首先介绍在三 维空间中基本术语的定 义。
• 形体（object） 由封闭表面围成的有效空间称为体； 一个体Q是R3空间中非空、有界的封闭子集。 其边界（记为∂Q）是有限个面的并集，而外壳 是形体的最大边界。 例如：一个单位立方体可定义 {(x,y,z)∈R3|0≤x≤1,0≤y≤1,0≤z≤1} y 其中一个表面可表示为： {(1,y,z)∈R3|0≤y≤1,0≤z≤1}
• 构造实体几何表示模型 的构造方法可以看作一 棵有序的二叉树，称为 CSG树。非叶节点可以 是正则集合运算操作， 也可以是形体的几何变 换（平移、旋转或缩放） 操作，所有操作只对其 子树（子形体）起作用。
U*
—
*
—
*
U*
（4）实体的扫描表示 基于一个基体，沿着某一路径运动而产生形体。 “物体” + “运动的轨迹”
X
V5 0 0 0
V6 0 b 0
V7 0 b c
V8 0 0 c
长方体的边表
边号 起点号 E1 V1 E2 V2 E3 V3 E4 V4 E5 V5 E6 V6 E7 V7 E8 V8 E9 V1 E10 V2 E11 V3 E12 V4
终点号
V2
V3
V4
V1
V6
V7
V8
V5
V5
V6
V7
V8
对于多面体由于其轮廓线和棱线通常是一致的，所 以多面体的线模型更便于识别，且简单。对于圆柱体 或球体之类的形体，只画出棱线而不画出轮廓线是不 能完整地表示出这个形体的。
A B A B
悬边
对共同边的取舍： 边的走向相反则无效
C * =A * B
正则集合下的求交运算
C=A∩B
集合论的求交计算
三. 形体（实体）的表示 形体常用的3种表示方法： 线框模型、表面模型 、实体模型 1.线框模型 早期模型。用顶点和棱边来描述物体。 一般地，画出了形体的棱线(边)与轮廓线就能 v1 e2 唯一地表示出来。 v2
• 形 体 — 顶点、棱边、表面之间的拓扑关系
v f e f f
f
f
v f v
v v
e
f e
e
f
f v f
v
v v
e
v e
e
e f f
v e v
e e
e
e
e
•
形体的性质： 1. 具有一定的形状，不变形（刚性） 2. 实体的各个部分均是三维的（维数的一致性） 3. 占据空间有限（有限性） 4. 经过几何变换和集合变换之后，仍然是有效 地实体（封闭性） 5. 实体的边界可以区分出实体的内部和外部。 （边界的确定性）。
3.实体模型 形体为封闭表面围成的有效空 间。 在表面模型的基础上增加： 一个封闭的边界； 实体在表面某一侧的定义 方法。 能够计算体积、面积、重量、 动量、转矩等物理量； 可以赋予材料特性；模拟物理 的运动，受力变形等。
• 在实体模型的表示中，基本上可以分为

y
P
0 7 7 4 5 x 7 5 E
1 E
2 E
3 E
4 E
5 FLeabharlann 6 E7P
0 E
1 E
2 E
3 E
4 F F
5
6 E
7 F
5 5
z
八叉树的根节点对应整个物体空间
(a)
(b)
如果它完全被物体占据，将该节点标记为F(Full)， 如果 它内部没有物体，将该节点标记为E(Empty) 如果它被物 体部分占据，将该节点标记为P(Partial)，并将它分割成 8个子立方体，对每一个子立方体进行同样的处理

z
• 面 R3中非空、连续、共面且封闭的子集称为面F， 其边界(记为∂F)是有限条线段的并集，Pt表示含有 F的唯一平面。 面是形体表面的一部分，且具有方向性.
Pt F
• 环 由有序、有向边组成的面的封闭 边界称为环。 环中任意边都不能自交； 相邻两条边共享一个端点； 环又分为内环和外环。内环边 按顺时针方向。外环是确定面 的最大外边界，其边按逆时针 方向，按这种方式定义，在面 上沿着边的方向前进，面的内 部始终在走向的左侧。
边界表示 分解表示 构造表示 扫描表示
（1）实体的边界表示 • 边界表示BRep 记录形体所有的几何信息和拓扑信息
在边界表示法中，边界表示按照体－面－环－边 －点的层次，详细记录了构成形体的所有几何元 素的几何信息及其相互连接的拓扑关系。
• 比较著名的边界表示的数据结构有半边数据结构、 翼边数据结构、辐射边数据结构等。 翼边数据结构——基于边表示的数据结构
e10 v6 e3 v3 e7 e11 v7 e6 e8 e4 v5 e1 e9 v4
e2 e12 v8
数据结构 存储顶点列表和边列表
V4
Z c V8 E12 E8 E3 V5 E4 V1 a E9 E1
E7 E11 V3 E5 b E2 E10 V2
V7 E6 V6 Y
长方体的顶点表
顶点表 x坐标 y坐标 z坐标 V1 a 0 0 V2 a b 0 V3 a b c V4 a 0 c
线框模型的优缺点:

简单，处理速度快，所占的存贮空间较少；
对于非平面多面体，如圆柱、球等形体，其轮廓 线随观察方向的改变而改变，无法用一组固定的 轮廓线来表示它们。线框模型与形体之间不存在 一一对应关系，定义的形体存在多义性。 难以计算面积、体积、物体重心等物理量

线框图的二义性： 不同的模型显示成线框图的结果一样
多边形网格模型
• 例如：如下图的 三角形网格构成 的曲面，用数组 来存储它的信息 v3
v0 v 1 v6 v4 v7 Vertex 0：x0,y0,z0 1：x1,y1,z1 2：x2,y2,z2 3：x3,y3,z3 4：x4,y4,z4 5：x5,y5,z5 6：x6,y6,z6 7：x7,y7,z7 8：x8,y8,z8 Triangle 0：0,1,3 1：1,4,3 2：1,2,4 3：2,4,1 4：2,5,4 5：3,4,6 6：4,7,6 7：5,8,7
1 5 2 3 4
5
1
2 (a)v=8,e=12,f=6 增加一条边：v=8,e=13,f=7
正则 形体
2 1 4
3
(b) v=9,e=14,f=7 形体的欧拉运算
(c) v=9,e=16,f=9
• 广义欧拉公式 V- E+F - R=2(S-H) • 其中，R为面上的孔穴数，H为贯穿多面体的 孔穴数，S为形体非连通部分总数。
• 几何造型就是用计算机系统来表示、控制、分析 和输出三维形体。 表示形体的两种模型: 数据模型：规则形体的建模方法； 用欧式几何描述。 过程模型：不规则形体的建模方法； 形体表示 用分形几何描述。
数据模型 过程模型 线框模型 表面模型 实体模型
1.数据模型 • 完全以数据描述。通常是欧式几何所能描述的规 则物体。 • 按发展时间：线框模型、表面模型、实体模型； • 以数据文件的形式存在。(静态)
• 优缺点 – 优点 • 可以表示任何物体,数据结构简单 • 容易实现物体间的集合运算 • 容易计算物体的整体性质，如体积等
– 缺点 • 是物体的非精确表示 • 没有边界信息，不适于图形显示 • 对物体进行几何变换困难
（3）实体的构造表示
构造实体几何表示模型 对于复杂的形体都可以 通过正则集合运算或几 何变换操作用简单形体 （体素）组合来表示。
（2）实体的分解表示 八叉树的表示 首先对形体定义一个外接立方体，再把它分解 成八个子立方体，并对立方体依次编号为0，1， 2，…，7。 如果子立方体单元已经一致，即为满（该立方 体充满形体）或为空（没有形体在其中），则 该子立方体可停止分解； 否则，需要对该立方体作进一步分解，再一分 为八个子立方体。在八叉树中，非叶结点的每 个结点都有八个分支。
2. 表面模型 形体表示成一组表面的集合。 把线框模型中的棱线及轮廓线包围的 部分定义为面，所形成的模型便是表 面模型。 数据结构是在线模型的基础上附加一 些指针，有序地连接棱线。
1 2 表面编号 表面特征 起始指针 顶点个数 4 3 5 0 1 4 顶点 号 1 2 3 4 2 3 4 1 属 连接指针 性 0 0 0 0 2 3 4 1
《计算机图形学》
第八讲 实体几何造型
一.概述 • 客观世界中的物体都是三维的，真实地描述和显 示客观世界中的三维物体是计算机图形学研究的 重要内容。 • 一个物体的计算机描述叫做模型，它能被计算机 读懂，并在一定的条件下（变换和投影）被转换 成相应的图形在屏幕显示或在绘图机上输出；
图形是模型的一个具体可见像
• 边 形体内两个相邻面的交界称为边。一条边有且仅 有两个相邻面。 两个端点确定一条边，这两个端点分别称为该边 的起点和终点。
v1 f1 e v2 f2 面2
面1