第9讲 三维几何建模-1

线框模型
单元枚举 八叉树分解 单元分解 …… 扫描方法 CSG方法 特征体素 ……
BREP 欧拉操作 ……
形体表 示方法
表面模型
空间分解
实体模型
构造表示
边界表示
线框、表面与实体模型的比较
模型表示 二维线框 三维线框 表面模型 应用范围 画二维线框图（工程 图） 画二、三维线框图 艺术图形、形体表面 的显示、数控加工
4）Brep表示法的优缺点
优点：
（1) 表示形体的点、线、面等几何元素是显式表示、使得形体 的显示很快并且很容易确定几何元素之间的连接关系； （2)可对Brep法的形体进行多种操作和局部修改； （3)能快速有效支持多种图形学、CAD系统的关键核心算法， 为大多数商业化CG、CAD系统所采用。
缺点：
思考问题： 表示法矢为什么用有向棱边，而不直接法矢 ? ?
千万注意：
用有向棱边表示表面的外法矢方向时，规
定有向棱边按右手法则取向：沿着闭合的
棱边所得的方向与表面外法矢方向一致。
例：多面体实体模型数据结构如下： class POINT
{ 同线框模型 { 同线框模型
class EDGE
{源自文库
class FACE
线框模型优点：
1）结构简单，计算机内部易于表达，绘制快速； 2）形体三维数据可以产生任意视图，为生成工程图带来了方便。
线框模型缺点：
1）有二义性，缺少表面轮廓信息，当形状复杂、棱线过多时，会引起 模糊理解。
2）在数据结构中缺少边与面、面与体之间关系的信息。从原理上讲， 此种模型不能消除隐藏线、计算物性、生成数控加工刀具轨迹、有 限元网格剖分、物体干涉检验等。
对复杂实体的数据结构则采用更多的层次表来描述！！
3）BREP表示的数据结构
边界表达强调实体的外表细节，把面、边、顶点的信息分层描 述，并建立了层与层之间边界表示。 没有统一的数据结构，为了有效地表示几何体的拓扑关系，斯 坦福大学B．G．Baumgart在1972年提出的以棱边为中心的多面 体表示的翼边结构(Winged Edge Data Structure，WED)及改进 后的对称结构等。 翼边结构以边为核心组织数据，如右图： 棱边数据结构中包含两个点指针，指向该 边的起点和终点，棱边为一有向线段。当 棱边为曲线段时，还需增加一指针指向曲 线表示的结构。
class POINT
{ 同线框模型 ……… } { int lop_typ;// 环类型 int *eno; //边索引 LOOP *nxt;//下一环 …………. } } 同线框模型 ………
class LOOP
class FACE
{ int loop_num； LOOP * lop; int face_type; SURFACE sur； …………. //环数 //环链表 //面类型 //面方程
描述形体拓扑信息的根本目的是便于直接对构成形体的各面、
边及顶点的参数和属性进行存取和查询，便于实现以面、边、点 为基础的各种几何运算和操作。
2）形体的拓扑关系
例如：多面体的面、边和顶点间的九种拓扑关系：
面面邻接关系 面上点的关系 面上边的关系
点与面连接关系 点点连接关系 点与边连接关系
边面邻接关系 边点连接关系 边边连接关系
（1) 数据结构复杂，需要大量存储空间，维护内部数据结构及 一致性的程序较复杂； （2)对形体的修改操作较难实现； （3)其表达方法繁琐，尤其精确的边界难以人工定义；与工 程 技术人员的操作习惯有较大差距，不适合直接交互。
简单形体BREP表达的数据结构手工填写实例：
填表注意事项：
先对点、边、环、面进行编号，编 号顺序自定，但最好有利于编程实 现；边的方向自定。
class EDGE
{
}
用“＋、－”标识边的方向
一个有趣的问题： 一个表面的正反两面都是确定的吗? ?
MObius曲面
实体模型表达的特点：
根据实体模型，可以进行物性计算（如体积、质量，惯量）、有限元 分析等应用。
9.3、形体的BREP、CSG表达方法
BREP 、 CSG 表示是当前CAD系统广泛采用的形体表达方法。
第9讲 三维几何建模基础
——几何形体表达
9.1．几何建模技术概述 9.2．几何形体的计算机内部表达
9.2.1 形体表达的基本概念 9.2.2 形体表达模型
9.3．几何形体的CSG、BREP表达方法
9.3.1 形体的BREP表达方法 9.3.2 形体的CSG表达方法
9.4、常见几何形体定义方法
本章目的
现在的CAD系统数据结构都是翼边结构的变种
一种基于WED数据结构的BREP表示示例
WED中另设两个环指针，分别指向棱边所邻接的两个环(左环和右环)。由 边环关系可确定棱边与邻面之间的拓扑关系。
为了从棱边搜索到它所在的任一闭环上的其它棱边，数据结构中还增设 四个指向邻边的指针，分别为左上边、左下边、右上边、右下边，左上 边为棱边左边环中沿逆时针方向所连接的下一条边，其余类推。
面是一个单连通区域，可以是平面或曲面，由外环和若干个内环 组成；面的方向用垂直于面的法矢表示，法矢向外为正向面。 体是由若干个面组成的闭包，实体的边界是有限个面的集合。 在CG和CAD中，点、线、环、面、体通常用一个具有层次描述的 数据结构来表达定义。
形体描述示意图
形体的层次数据结构示意图
正则形体：形体表面上任一点的足够小的邻域在拓扑上应是一 个等价的封闭圆，即围绕该点的形体邻域在二维空间中可构成 一个单连通域。我们把满足该定义的形体称为正则形体，否则 为非正则形体。 例如，存在悬面、悬边的长方体为非正则形体（如右图）。
9.3.1、形体的BREP表达方法
1）基本概念
边界表示(Boundary Representation，缩写Brep)通过描 述实体的边界来表示实体。实体的边界将该实体分为实 体内点集和实体外点集，是实体与环境之间的分界面。 定义了实体的边界，实体就被唯一定义，如右图所示。
边界表示是用一组曲面（或平面）来描述三维物体，这些曲面（或平面） 将物体分为内部和外部。典型例子是平面立体和曲面立体。
物性计算、有限元分析 用集合运算构造形体
局限性
无法观察参数的变化，不可 能产生有实际意义的形体
不能表示实体、图形会有 二义性 不能表示实体 只能产生正则形体 抽象形体的层次较低
实体模型
2）形体表达的线框模型
线框模型组成 ：
线框模型用顶点和棱边表示三维形体，其棱边可以为直线、圆弧、二 次曲线及样条曲线组成 。
int edge_num； EDGE * edge; int face_type; //边数 //边链表 //面类型
SURFACE sur； //面方程
………….
} }
………….
}
………….
思考问题： 相邻两个面的公共棱边的方向不会矛盾吗？? ?
有矛盾 !!! 增加“环” 的定义解决矛盾。
改进的数据结构如下：
int edge_num； //边数 int *edge_no; //边链表 int face_type; //面类型 SURFACE sur；//面方程 …………….
………….
………….
}
}
}
表面模型的特点：
优点：可满足面面求交，线面消隐、明暗处理和数控加工的要求。 缺点：没有解决形体究竟在表面的哪一侧的问题。在物性计算、有限元 分析等应用中，表面模型在形体的表示上仍然缺乏完整性。
3）形体表达的表面模型
表面模型是用有连接顺序的棱边围成的有限区域来定义形体的表面,再 由表面的集合来定义形体。
表面可以是平面，也可以是柱面、球面等类型的二次曲面，也可是样 条曲面构成的自由曲面。
表面模型的数据结构：
表面模型数据结构采用三表结构，即：面表、边表和顶点表。只需在线
框模型的基础上增加有关面边信息以及表面特征、棱边连接方向等。
4）形体表达的实体模型
为了解决形体存在于表面的哪一侧的问题，可采用实体模型来描述三维立 体。在表面模型的基础上可用三种方法来定义表面的哪一侧存在实体。 1）给出实体存在一侧的一点； 2）直接用表面的外法矢来指明实体存在的一侧； 3）用有向棱边隐含地表示表面的外法矢方向，该方 法为CAD系统广泛采用。
Brep表示方法必须表达的信息分为两类: 一类是几何信息：描述形体的大小、位臵、形状等基本信息， 如顶点坐标，边和面的数学表达式等。 另一类是拓扑信息：拓扑信息描述形体上的顶点、边、面的连 接关系。 拓扑信息形成物体边界表示的“骨架”，形体的几何信息犹如
附着在“骨架”上的“皮肤”。
在Brep中，拓扑信息是指用来说明体、面、边及顶点之间连接 关系的这一类信息，例如面与哪些面相邻；面由那些边组成等。
1．了解CAD系统中几何形体的计算机
内部表示形式
2、熟练掌握CSG、BREP表达方法及数
据结构
3、掌握CAD中常用的形体定义方法
9.1 几何造型技术概述
几何造型技术是研究在计算机中，如何表达物体模型形状的技 术。几何造型通过对点、线、面、体等几何元素的数学描述，经过 平移、旋转、变比等几何变换和并、交、差等集合运算，产生实际 的或想象的物体模型。
在这九种不同类型的拓扑关系中，有些关系冗余，因此计算机内部 并不需要所有拓扑关系都直接表达。 但至少需表达两种以上拓扑关系才能构成一个完全的拓扑信息。 存储更多的拓扑关系，花费的代价是存储量大了，以冗余来换计算 工作量的节省和某些算法的易于实现。 例如，在Brep表达中，简单实体的数据结构可用体、面、边、点四 个层次的表描述如下：
线框模型数据结构：
顶点表记录各顶点坐标值； 棱线表记录每条棱线所连接的顶点及走向。 例：立方体线框模型数据结构如下： class POINT { double v[3]; //坐标值 int pointtype; //点的属性 ………….. } class EDGE { int start_point_no; //边的起点 int end_point_no; //边的终点 CURVE cur； //边方程定义； ………….. }
几何造型的作用
9.2 几何形体的计算机内部表达
9.2.1 形体表达的基本概念
在CG和CAD中，形体的边界是由面的并集来表示， 每个面又由它的数学定义加上其边界来表示，面的 边界是环边的并集，而边又是由点来表示的。
点用三维坐标表示，是最基本的元素
边是相邻面的交界，可为有向直线或曲线
环是由有序、有向的边组成的封闭边界，环有内、外环之分，外 环最大且只有一个，内环的方向和外环相反。
3个面：顶平面（法矢向上）、底平面（法矢向下） 、 圆柱面（外法矢方向由外环确定）
思考问题：圆的方程如何表示？？
3个环：顶面外环、底面外环、侧面外环 3条边：顶部圆、底部圆、侧面边（直母线） 2个顶点：顶面1个点、底面1个点
N
N
图（a） 圆柱的边、顶点 图（b） 圆柱的面、环
思考问题： 填写Brep表十分繁琐，对于复杂形体人工无法完成，如何完 成复杂的BREP数据结构? ?
注意：一个实体的BREP表达不唯一，如下图圆柱体表示； 不同CAD系统表达不同，不同建模方法也导致不一致； 但都并不影响形体表达的完整性。
3个面 3个环 3条边 2个顶点
4个面 4个环 6条边 4个顶点
9.2.2 形体表达方法
1）形体表达方法概述
计算机中表示形体，通常用线框模型（如图a）、表面模型 （如图b）和实体模型（如图c）等表达方法。
图a 线框模型
图b 表面模型
图c 实体模型
实体模型的表示方法中又可以分为：空间分解类（如单元枚举、八 叉树分解、单元分解等）、构造类（如扫描、CSG、特征参数化体素等） 和边界表达类（如BREP、欧拉操作等）三大类。 其中CSG、BREP表示是当前CAD系统广泛采用的方法。
1） 顶点坐标值存放在顶点表中；
2）含有指向顶点表指针的边表，用来为多边形的每条边标识顶点；
边有方向，从起点到终点为正方向； 3）面表有指向边表的指针，用来为每个表面标识其组成边。
面号
例：多面体表面模型数据结构
class POINT {
同线框模型
class EDGE {
同线框模型
class FACE {
边的方向定义后，其左右外环、
左右面的连接关系唯一确定（右 手法则），如右图：
左外环 左面
右外环 右面
环是由有序、有向的边组成的封闭边界，按右手法则，外环逆
时针方向（确定面的外法矢方向），内环顺时针。
面可以是平面或曲面，由一个外环和若 干内环组成；法矢向外为正向面（由外
环方向确定，确保指向实体外侧）。