第8讲_三维几何建模-1

1、8、几何造型1 本章目的1了解计算机内部是怎样表达三维机械零部件模型2了解几何形体CSG、BREP表达的基本原理3了解几何形体的其它表达方法1几何形体的计算机内部表达2几何形体的CSG、BREP表达3. 几何形体的其它表达方法几何造型技术是研究在计算机中，如何表达物体模型形状的技术。几何造型通过对点、线、面、体等几何元素的数学描述，经过平移、旋转、变比等几何变换和并、交、差等集合运算，产生实际的或想象的物体模型。 几何造型技术概述8、几何造型1 1几何形体的计算机内部表达2几何形体的CSG、BREP表达3. 几何形体的其它表达方法几何形体的计算机内部表达 计算机中表示形体，通常用计算机中表示形

2、体，通常用线框模型线框模型、表表面模型面模型和和实体模型实体模型。 线框模型和表面模型保存的三维形体信息线框模型和表面模型保存的三维形体信息都不完整。都不完整。 只有实体模型才能够完整地、无歧义地表只有实体模型才能够完整地、无歧义地表示三维形体。示三维形体。 在在实体模型实体模型的表示中，出现了许多方法，的表示中，出现了许多方法，基本上可以分为基本上可以分为空间分解表示空间分解表示（单元枚举、（单元枚举、八叉树分解、单元分解等）、八叉树分解、单元分解等）、构造表示（构造表示（CSGCSG）和边界表示（和边界表示（BREPBREP）三大类。构造表示是按三大类。构造表示是按照生成过程来定义形体的方

3、法，构造表示通照生成过程来定义形体的方法，构造表示通常有扫描表示、构造实体几何表示和特征表常有扫描表示、构造实体几何表示和特征表示三种。示三种。 点点用三维坐标表示，是最基本的元素用三维坐标表示，是最基本的元素边边是形体相邻面的交界，可为空间直线或曲线是形体相邻面的交界，可为空间直线或曲线环环是有序、有向的封闭边界，是有序、有向的封闭边界，外环外环仅一个，逆时针方向，仅一个，逆时针方向，内环内环可有可无，也可多个，方向顺时针。可有可无，也可多个，方向顺时针。面面是一个单连通区域，可以是平面或曲面，由一个外环是一个单连通区域，可以是平面或曲面，由一个外环和若干个内环组成；面的方向由面的法矢决定，

4、法矢向和若干个内环组成；面的方向由面的法矢决定，法矢向外为正向面。外为正向面。基本概念及定义实体实体是由若干个面组成的闭包，实体的边界是有限个是由若干个面组成的闭包，实体的边界是有限个面的集合。面的集合。形体表面上任一点的足够小的形体表面上任一点的足够小的邻域邻域在拓扑上应是一个在拓扑上应是一个等价的封闭圆，即围绕该点的形体邻域在二维空间中等价的封闭圆，即围绕该点的形体邻域在二维空间中可构成一个单连通域，我们把满足该定义的形体称为可构成一个单连通域，我们把满足该定义的形体称为正则形体正则形体。否则为。否则为非正则形体非正则形体，如存在悬面、悬边的，如存在悬面、悬边的长方体为非正则形体。长方体为

5、非正则形体。 线框模型线框模型用顶点和棱边表示三维形体，其棱边可以为直线直线、圆弧圆弧、二次曲线二次曲线及样条曲线样条曲线组成 。 线框模型在计算机内存储的数据结构： 顶点表：记录各顶点坐标值； 棱线表：记录每条棱线所连接的两顶点。class POINT class EDGE double v3; /坐标值 int start_point_no; /边的起点 int pointtype; /点的属性 int end_point_no; /边的终点 CURVE cur； /边方程定义； . . 以立方体为例，其线框模型结构如下表：优点优点结构简单，计算机内部易于表达，绘制快速；1. 物体的三维数

6、据可以产生任意视图，为生成工程图带来了方便缺点缺点有二义性，缺少表面轮廓信息，当形状复杂、棱线过多时，会引起模糊理解。 2. 在数据结构中缺少边与面、面与体之间关系的信息。从原理上讲，此种模型不能消除隐藏线、计算物性、生成数控加工刀具轨迹、有限元网格剖分、物体干涉检验等。表面模型 表面模型是用有连接顺序的棱边围成的有限区域来定义形体的表面,再由表面的集合来定义形体。 表面可以是平面，也可以是柱面、球面等类型的二次曲面，也可是样条曲面构成的自由曲面。 表面模型是在线框模型的基础上，增加有关面边信息以及表面特征、棱边的连接方向等内容。 表面模型存储几何信息的方法是建立三表结构，即顶点表、边表和面表

7、。 1）顶点坐标值存放在顶点表顶点表中； 2）含有指向顶点表指针的边表边表，用来为多边形的每条边标识顶点； 3）面表面表有指向边表的指针，用来为每个表面标识其组成边。class POINT class EDGE class FACE 同线框模型 同线框模型 int edge_num； /边数 int *edge_no; /边链表 int face_type; /面类型 SURFACE sur；/面方程 . . . 表面模型唯一没有解决的问题是形体究竟在表面的哪一侧，因而在物性计算、有限元分析等应用中，表面模型在形体的表示上仍然缺乏完整性。 表面模型可以满足面面求交，线面消隐、明暗处理和数控加工

8、的要求。 表面模型的特点表面模型的特点实体模型 为了解决形体存在于表面的哪一侧的问题，可采用实体模型来描述三维立体 在表面模型的基础上可用三种方法来定义表面的哪一侧存在实体。1）给出实体存在一侧的一点；2）直接用表面的外法矢来指明实体存在的一侧；3）用有向棱边隐含地表示表面的外法矢方向，该方用有向棱边隐含地表示表面的外法矢方向，该方 法为法为CADCAD系统广泛采用。系统广泛采用。 （思考：为什么不直接用法矢？） 用有向棱边隐含地表示表面的外法矢方向时，规定有向棱边按右手法则右手法则取向：沿着闭合的棱沿着闭合的棱边所得的方向与表面外法矢方向边所得的方向与表面外法矢方向一致。一致。 思考：相邻两

9、个面的公共棱思考：相邻两个面的公共棱边的方向不会矛盾吗？边的方向不会矛盾吗？ （有矛盾，（有矛盾，CAD系统中增加系统中增加“环环” 的定义解决矛盾）的定义解决矛盾）class POINT class EDGE class FACE 同线框模型 同线框模型 int edge_num； /边数 EDGE * edge; /边链表 int face_type; /面类型 SURFACE sur； /面方程 . . . 数据结构如下：数据结构如下： 根据实体模型，可以进行物性计算（如体积、质量，惯量）、有限元分析等应用。 从前面的实体模型可知，本质上我们仍然采用形体的边界表面的数学描述代替实体描述。

10、 这种典型的描述方法通常称为实体的边界表达方法（BREP）实体模型的特点实体模型的特点线框、表面与实体模型的比较模型表示模型表示应用范围应用范围局限性局限性二维线框二维线框画二维线框图（工程图）画二维线框图（工程图）无法观察参数的变化，不可无法观察参数的变化，不可能产生有实际意义的形体能产生有实际意义的形体三维线框三维线框画二、三维线框图画二、三维线框图不能表示实体、图形会有不能表示实体、图形会有二义性二义性表面模型表面模型艺术图形、形体表面的艺术图形、形体表面的显示、数控加工显示、数控加工不能表示实体不能表示实体实体模型实体模型物性计算、有限元分析物性计算、有限元分析用集合运算构造形体用集合

11、运算构造形体只能产生正则形体只能产生正则形体抽象形体的层次较低抽象形体的层次较低8、几何造型1 1几何形体的计算机内部表达2几何形体的CSG、BREP表达3. 几何形体的其它表达方法实体模型边界表达（BREP） 边界表示边界表示( (Boundary RepresentationBoundary Representation，缩写缩写Brep)Brep)通过描述实体的边界来表示实体。通过描述实体的边界来表示实体。实体的边界将该实体分为实体内点集和实体实体的边界将该实体分为实体内点集和实体外点集，是实体与环境之间的分界面。定义外点集，是实体与环境之间的分界面。定义了实体的边界，实体就被唯一定义，

12、如右图了实体的边界，实体就被唯一定义，如右图所示。所示。 边界表示是用一组曲面（或平面）来描述三维物体，这些曲边界表示是用一组曲面（或平面）来描述三维物体，这些曲面（或平面）将物体分为内部和外部。典型例子是面（或平面）将物体分为内部和外部。典型例子是平面立体平面立体表示表示和和曲面表示曲面表示的立体。的立体。 实体实体的边界通常是由的边界通常是由面面的并集来表示，而每个面又由它的数的并集来表示，而每个面又由它的数学定义加上其学定义加上其边边界来表示，面的边界是界来表示，面的边界是环环边的并集，而边的并集，而边边又是由又是由点点来表示的。来表示的。点点用三维坐标表示，是最基本的元素用三维坐标表示

13、，是最基本的元素边边是形体相邻面的交界，可为空间直线或曲线是形体相邻面的交界，可为空间直线或曲线环环是由有序、有向的边组成的封闭边界，环有是由有序、有向的边组成的封闭边界，环有内内、外环外环之分，外环最大且只有一个，内环的之分，外环最大且只有一个，内环的方向和外环相反。方向和外环相反。面面是一个单连通区域，可以是平面或曲面，由是一个单连通区域，可以是平面或曲面，由外环和若干个内环组成；面的方向用垂直于面外环和若干个内环组成；面的方向用垂直于面的法矢表示，法矢向外为正向面。的法矢表示，法矢向外为正向面。实体实体是由若干个面组成的闭包，实体的边界是是由若干个面组成的闭包，实体的边界是有限个面的集合

14、。有限个面的集合。形体表面上任一点的足够小的邻域在拓扑上形体表面上任一点的足够小的邻域在拓扑上应是一个等价的封闭圆，即围绕该点的形体应是一个等价的封闭圆，即围绕该点的形体邻域在二维空间中可构成一个单连通域，我邻域在二维空间中可构成一个单连通域，我们把满足该定义的形体称为们把满足该定义的形体称为正则形体正则形体。否则。否则为为非正则形体非正则形体，如存在悬面、悬边的长方体，如存在悬面、悬边的长方体为非正则形体。为非正则形体。 Brep中必须表达的信息分为两类中必须表达的信息分为两类: : 一类是一类是几何信息几何信息。描述形体的大小、位置、形状等基。描述形体的大小、位置、形状等基本信息，如顶点坐

15、标，边和面的数学表达式等。本信息，如顶点坐标，边和面的数学表达式等。 另一类是另一类是拓扑信息拓扑信息。拓扑信息描述形体上的顶点、边、。拓扑信息描述形体上的顶点、边、面的连接关系。面的连接关系。 拓扑信息形成物体边界表示的拓扑信息形成物体边界表示的“骨架骨架”，形体的几何，形体的几何信息犹如附着在信息犹如附着在“骨架骨架”上的上的“肌肉肌肉”。 在在BrepBrep中，拓扑信息是指用来说明体、面、边及顶点中，拓扑信息是指用来说明体、面、边及顶点之间连接关系的这一类信息，例如面与哪些面相邻；面由之间连接关系的这一类信息，例如面与哪些面相邻；面由那些边组成等。那些边组成等。 描述形体拓扑信息的根本

16、目的是便于直接对构成形体描述形体拓扑信息的根本目的是便于直接对构成形体的各面、边及顶点的参数和属性进行存取和查询，便于实的各面、边及顶点的参数和属性进行存取和查询，便于实现以面、边、点为基础的各种几何运算和操作。现以面、边、点为基础的各种几何运算和操作。例如：多面体的面、边和顶点间的九种拓扑关系例如：多面体的面、边和顶点间的九种拓扑关系面面邻接关系面面邻接关系面上点的关系面上点的关系面上边的关系面上边的关系点与面连接关系点与面连接关系点点连接关系点点连接关系点与边连接关系点与边连接关系边面邻接关系边面邻接关系边点连接关系边点连接关系边边连接关系边边连接关系 在这九种不同类型的拓扑关系中，有些关

17、系冗余，在这九种不同类型的拓扑关系中，有些关系冗余，因此计算机内部并不需要所有拓扑关系都直接表达。因此计算机内部并不需要所有拓扑关系都直接表达。 但至少需表达两种以上拓扑关系才能构成一个实体但至少需表达两种以上拓扑关系才能构成一个实体完全的拓扑信息。完全的拓扑信息。 存储更多的拓扑关系，花费的代价是存储量大了，存储更多的拓扑关系，花费的代价是存储量大了，以冗余来换计算工作量的节省和某些算法的易于实现。以冗余来换计算工作量的节省和某些算法的易于实现。 例如，在例如，在BrepBrep表达中，简单实体的数据结构可用体、表达中，简单实体的数据结构可用体、面、边、点四个层次的表描述面、边、点四个层次的

18、表描述 对复杂实体的数据结构则采用更多的层次表来描述对复杂实体的数据结构则采用更多的层次表来描述 边界表达强调实体的外表细节，把面、边、顶点的信边界表达强调实体的外表细节，把面、边、顶点的信息分层描述，并建立了层与层之间边界表示。息分层描述，并建立了层与层之间边界表示。 没有统一的数据结构，为了有效地表示几何体的拓扑没有统一的数据结构，为了有效地表示几何体的拓扑关系，斯坦福大学关系，斯坦福大学B BG GBaumgartBaumgart在在19721972年提出的以棱边年提出的以棱边为中心的多面体表示的翼边结构为中心的多面体表示的翼边结构( (Winged Edge Data Winged E

19、dge Data StructureStructure，WED)WED)及改进后的对称结构等。及改进后的对称结构等。边界表示的数据结构翼边结构以边为核心组织数据，如图：翼边结构以边为核心组织数据，如图： 棱边数据结构中包含两个点指针，棱边数据结构中包含两个点指针，指向该边的起点和终点，棱边为一有向指向该边的起点和终点，棱边为一有向线段。当棱边为曲线段时，还需增加一线段。当棱边为曲线段时，还需增加一指针指向曲线表示的结构。指针指向曲线表示的结构。 现在的现在的CADCAD系统数据结构都是翼边结构的变种系统数据结构都是翼边结构的变种WEDWED中另设两个环指针，分别指向棱边所邻接的两个环中另设两个

20、环指针，分别指向棱边所邻接的两个环( (左环和右左环和右环环) )。由边环关系可确定棱边与邻面之间的拓扑关系。由边环关系可确定棱边与邻面之间的拓扑关系。为了从棱边搜索到它所在的任一闭环上的其它棱边，数据结构中为了从棱边搜索到它所在的任一闭环上的其它棱边，数据结构中还增设四个指向邻边的指针，分别为左上边、左下边、右上边、还增设四个指向邻边的指针，分别为左上边、左下边、右上边、右下边，左上边为棱边左边环中沿逆时针方向所连接的下一条边，右下边，左上边为棱边左边环中沿逆时针方向所连接的下一条边，其余类推。其余类推。WEDWED方法拓扑信息完整，查询和修改方便，可很好地应用于正则方法拓扑信息完整，查询和

21、修改方便，可很好地应用于正则布尔运算布尔运算BREP表达数据结构举例 Brep表示法的优点：(1)表示形体的点、线、面等几何元素是显式表示、使得形体的显示很快并且很容易确定几何元素之间的连接关系；(2)可对Brep法的形体进行多种操作和局部修改缺点：(1)数据结构复杂，需要大量存储空间，维护内部数据结构及一致性的程序较复杂；(2)对形体的修改操作较难实现。实体模型的构造实体几何实体模型的构造实体几何表示方法（表示方法（CSGCSG） 构造实体几何表示构造实体几何表示( (Constructive Solid Constructive Solid GeometryGeometry，缩写为缩写为C

22、SG)CSG)的含义是任何复杂的形体都可的含义是任何复杂的形体都可用简单形体通过正则集合运算组合，并配合几何变换用简单形体通过正则集合运算组合，并配合几何变换来表示。来表示。 在在19771977年由罗切斯特年由罗切斯特(Rochester)(Rochester)大学的大学的VoelckerVoelcker和和BequichaBequicha等人首先提出的。等人首先提出的。 CSGCSG中物体形状的定义中物体形状的定义以集合论为基础，先定义集以集合论为基础，先定义集合本身，其次是集合之间运算合本身，其次是集合之间运算。所以，。所以，CSGCSG表示先定义表示先定义有界体素有界体素( (如立方体

23、、圆柱、球、锥、圆环等如立方体、圆柱、球、锥、圆环等) )，然后，然后将这些体素进行并、交、差运算（如图）。将这些体素进行并、交、差运算（如图）。A 体B 体A* BA* BA*B 形体的形体的CSGCSG可看成是一个有序的二叉树，其叶子可看成是一个有序的二叉树，其叶子节点是体素或几何变换的参数，非叶节点则是布尔运节点是体素或几何变换的参数，非叶节点则是布尔运算的操作符或几何变换操作。任何子树表示其下两个算的操作符或几何变换操作。任何子树表示其下两个节点的组合或变换的结果，树根表示最终的形体。节点的组合或变换的结果，树根表示最终的形体。 用用CSGCSG树表示一个形体是无树表示一个形体是无二义

24、性的，但一个形体可以有二义性的，但一个形体可以有不同的不同的CSGCSG树表示，取决于使用树表示，取决于使用的体素、构造操作方法和操作的体素、构造操作方法和操作顺序。顺序。 CSGCSG表示依赖稳定可靠的布表示依赖稳定可靠的布尔运算算法支撑。尔运算算法支撑。优点：(1) 数据结构比较简单，信息量小，易于管理；(2) 每个CSG都和一个实际的有效形体相对应；(3) CSG树记录了形体的生成过程，可修改形体生成的各环节以改变形体的形状。缺点：(1) 不能进行形体的局部修改，如面、边、点等；(2) 直接基于CSG表达形体，其组合运算及显示效率很低。 CSGBREP混合表示 从用户进行造型的角度看，从

25、用户进行造型的角度看，CSGCSG方法比较方便，从方法比较方便，从对形体的存储管理和操作的角度看，对形体的存储管理和操作的角度看，BrepBrep法更为实用。法更为实用。 目前大多数目前大多数CADCAD系统都以系统都以CSGCSGBrepBrep的混合表示作为的混合表示作为形体数据表示的基础：形体数据表示的基础： 以以CSGCSG模型表示几何造型的特征历史过程及其特模型表示几何造型的特征历史过程及其特征设计参数；征设计参数； 用用BrepBrep模型维护详细的几何信息和显示、查询等模型维护详细的几何信息和显示、查询等操作，同时也为布尔运算提供基础。操作，同时也为布尔运算提供基础。 ACISA

26、CIS系统的数据结构系统的数据结构 ACIS是美国Spatial Technology公司推出的三维几何造型引擎，它集线框、曲面和实体造型于一体，并允许这三种表示共存于统一的数据结构中。 几何（Geometry）、拓扑(Topology)和属性(Attribute)构成了ACIS模型，三者统一由最基础的抽象类ENTITY所派生.虽然ENTITY本身不代表任何对象，但在ENTITY中定义了它所有子类应具有的数据和方法（如存储、恢复、回溯等）。 ACIS的拓扑包括BODY（体）、LUMP（块）、SHELL（壳）、SUBSHELL（子壳）、FACE（面）、LOOP（环）、WIRE（线框）、COEDG

27、E（公共边）、EDGE（边）和VERTEX（顶点）。 ACISACIS把线框（把线框（WIREFRAMEWIREFRAME）、曲面（）、曲面（SURFACESURFACE）和实体（）和实体（SOLIDSOLID）存储在统一的数据结构中存储在统一的数据结构中，这种共存机制使ACIS支持混合维模型和各种非闭合模型。一个典型的一个典型的CADCAD几何引擎几何引擎ACISACIS介绍介绍*ACIS中模型的数据结构中模型的数据结构 ACIS中模型的中模型的C+类层次关系类层次关系 ACIS拓扑对象间的关系以及拓扑与几何间的关系8、几何造型1 1几何形体的计算机内部表达2几何形体的CSG、BREP表达3. 几何形体的其它表达方法空间分割表示 将形体按某种规则分解