第9讲三维几何建模-1

1、第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、常见几何形体定义方法本章目的 1了解CAD系统中几何形体的计算机内部表示形式2、熟练掌握CSG、BREP表达方法及数据结构3、掌握CAD中常用的形体定义方法 几何造型技术是研究在计算机中，如何表达物体模型形状的技术。几何造型通过对点、线、面、体等几何元素的数学描述，经过平移、旋转、变比等几何变换和并、交、差等集合运算，产生实际的或

2、想象的物体模型。 9.1 几何造型技术概述几何造型的作用9.2 几何形体的计算机内部表达9.2.1 形体表达的基本概念在CG和CAD中，形体的边界是由面的并集来表示，每个面又由它的数学定义加上其边界来表示，面的边界是环边的并集，而边又是由点来表示的。点用三维坐标表示，是最基本的元素边是相邻面的交界，可为有向直线或曲线环是由有序、有向的边组成的封闭边界，环有内、外环之分，外环最大且只有一个，内环的方向和外环相反。面是一个单连通区域，可以是平面或曲面，由外环和若干个内环组成；面的方向用垂直于面的法矢表示，法矢向外为正向面。体是由若干个面组成的闭包，实体的边界是有限个面的集合。在CG和CAD中，点、

3、线、环、面、体通常用一个具有层次描述的数据结构来表达定义。 形体描述示意图形体描述示意图 形体的层次数据结构示意图形体的层次数据结构示意图正则形体：正则形体：形体表面上任一点的足够小的邻域在拓扑上应是一个等价的封闭圆，即围绕该点的形体邻域在二维空间中可构成一个单连通域。我们把满足该定义的形体称为正则形体，否则为非正则形体。例如，存在悬面、悬边的长方体为非正则形体（如右图）。 计算机中表示形体，通常用线框模型（如图a）、表面模型（如图b）和实体模型（如图c）等表达方法。图图a 线框模型线框模型图图b 表面模型表面模型图图c 实体模型实体模型9.2.2 形体表达方法1）形体表达方法概述 实体模型的

4、表示方法中又可以分为：空间分解类（如单元枚举、八叉树分解、单元分解等）、构造类（如扫描、CSG、特征参数化体素等）和边界表达类（如BREP、欧拉操作等）三大类。 其中CSG、BREP表示是当前CAD系统广泛采用的方法。形体表示方法线框模型表面模型实体模型空间分解构造表示边界表示单元枚举八叉树分解单元分解扫描方法CSG方法特征体素BREP欧拉操作线框、表面与实体模型的比较模型表示模型表示应用范围应用范围局限性局限性二维线框二维线框画二维线框图（工程图）画二维线框图（工程图）无法观察参数的变化，不可无法观察参数的变化，不可能产生有实际意义的形体能产生有实际意义的形体三维线框三维线框画二、三维线框图

5、画二、三维线框图不能表示实体、图形会有不能表示实体、图形会有二义性二义性表面模型表面模型艺术图形、形体表面的艺术图形、形体表面的显示、数控加工显示、数控加工不能表示实体不能表示实体实体模型实体模型物性计算、有限元分析物性计算、有限元分析用集合运算构造形体用集合运算构造形体只能产生正则形体只能产生正则形体抽象形体的层次较低抽象形体的层次较低2）形体表达的线框模型线框模型用顶点和棱边表示三维形体，其棱边可以为直线直线、圆弧圆弧、二二次曲线次曲线及样条曲线样条曲线组成 。 线框模型组成 ：线框模型数据结构线框模型数据结构： 顶点表记录各顶点坐标值； 棱线表记录每条棱线所连接的顶点顶点及走向走向。cl

6、ass POINT class EDGE double v3; /坐标值 int start_point_no; /边的起点 int pointtype; /点的属性 int end_point_no; /边的终点 CURVE cur； /边方程定义； . . 例：立方体线框模型数据结构如下：线框模型优点：线框模型优点： 1）结构简单，计算机内部易于表达，绘制快速； 2）形体三维数据可以产生任意视图，为生成工程图带来了方便。线框模型缺点：线框模型缺点：1）有二义性，缺少表面轮廓信息，当形状复杂、棱线过多时，会引起模糊理解。 2）在数据结构中缺少边与面、面与体之间关系的信息。从原理上讲，此种模型

7、不能消除隐藏线、计算物性、生成数控加工刀具轨迹、有限元网格剖分、物体干涉检验等。3）形体表达的表面模型表面模型是用有连接顺序的棱边围成的有限区域来定义形体的表面,再由表面的集合来定义形体。表面可以是平面，也可以是柱面、球面等类型的二次曲面，也可是样条曲面构成的自由曲面。1） 顶点坐标值存放在顶点表顶点表中；2）含有指向顶点表指针的边表边表，用来为多边形的每条边标识顶点；边有方向，从起点到终点为正方向从起点到终点为正方向；3）面表面表有指向边表的指针，用来为每个表面标识其组成边。表面模型数据结构采用三表结构，即：面表、边表和顶点表。只需在线框模型的基础上增加有关面边信息以及表面特征、棱边连接方向

8、等。表面模型的数据结构：表面模型的数据结构：面号class POINT class EDGE class FACE 同线框模型 同线框模型 int edge_num； /边数 int *edge_no; /边链表 int face_type; /面类型 SURFACE sur；/面方程 . . . 例：多面体表面模型数据结构缺点：没有解决形体究竟在表面的哪一侧的问题。在物性计算、有限元分析等应用中，表面模型在形体的表示上仍然缺乏完整性。优点：可满足面面求交，线面消隐、明暗处理和数控加工的要求。 表面模型的特点：表面模型的特点：4）形体表达的实体模型为了解决形体存在于表面的哪一侧的问题，可采用实

9、体模型来描述三维立体。在表面模型的基础上可用三种方法来定义表面的哪一侧存在实体。1）给出实体存在一侧的一点；2）直接用表面的外法矢来指明实体存在的一侧；3）用有向棱边隐含地表示表面的外法矢方向，该方 法为CAD系统广泛采用。思考问题：思考问题：表示法矢为什么用有向棱边，而不直接法矢 ? ?用有向棱边有向棱边表示表面的外法矢方向时，规定有向棱边按右手法则右手法则取向：沿着闭合的沿着闭合的棱边所得的方向与表面外法矢方向一致。棱边所得的方向与表面外法矢方向一致。千万注意：千万注意：例：多面体实体模型数据结构如下：例：多面体实体模型数据结构如下：class POINT class EDGE class

10、 FACE 同线框模型 同线框模型 int edge_num； /边数 EDGE * edge; /边链表 int face_type; /面类型 SURFACE sur； /面方程 . . . 有矛盾 !增加“环” 的定义解决矛盾。思考问题：思考问题：相邻两个面的公共棱边的方向不会矛盾吗？? ?class POINT class LOOP class FACE 同线框模型 int lop_typ;/ 环类型 int loop_num； /环数 int *eno; /边索引 LOOP * lop; /环链表 LOOP *nxt;/下一环 int face_type; /面类型 . SURFAC

11、E sur； /面方程class EDGE . 同线框模型 用用“、”标识边的方向标识边的方向改进的数据结构如下：实体模型表达的特点：根据实体模型，可以进行物性计算（如体积、质量，惯量）、有限元分析等应用。一个有趣的问题：一个有趣的问题：一个表面的正反两面都是确定的吗? ?MObius曲面曲面 9.3、形体的BREP、CSG表达方法 9.3.1、形体的BREP表达方法边界表示(Boundary Representation，缩写Brep)通过描述实体的边界来表示实体。实体的边界将该实体分为实体内点集和实体外点集，是实体与环境之间的分界面。定义了实体的边界，实体就被唯一定义，如右图所示。 边界表

12、示是用一组曲面（或平面）来描述三维物体，这些曲面（或平面）将物体分为内部和外部。典型例子是平面立体和曲面立体。 BREP 、 CSG 表示是当前CAD系统广泛采用的形体表达方法。1）基本概念Brep表示方法必须表达的信息分为两类: 一类是几何信息：描述形体的大小、位置、形状等基本信息，如顶点坐标，边和面的数学表达式等。 另一类是拓扑信息：拓扑信息描述形体上的顶点、边、面的连接关系。 拓扑信息形成物体边界表示的“骨架”，形体的几何信息犹如附着在“骨架”上的“皮肤”。 在Brep中，拓扑信息是指用来说明体、面、边及顶点之间连接关系的这一类信息，例如面与哪些面相邻；面由那些边组成等。 描述形体拓扑信

13、息的根本目的是便于直接对构成形体的各面、边及顶点的参数和属性进行存取和查询，便于实现以面、边、点为基础的各种几何运算和操作。例如：多面体的面、边和顶点间的九种拓扑关系：例如：多面体的面、边和顶点间的九种拓扑关系：面面邻接关系面面邻接关系面上点的关系面上点的关系面上边的关系面上边的关系点与面连接关系点与面连接关系点点连接关系点点连接关系点与边连接关系点与边连接关系边面邻接关系边面邻接关系边点连接关系边点连接关系边边连接关系边边连接关系2）形体的拓扑关系在这九种不同类型的拓扑关系中，有些关系冗余，因此计算机内部并不需要所有拓扑关系都直接表达。但至少需表达两种以上拓扑关系才能构成一个完全的拓扑信息。

14、存储更多的拓扑关系，花费的代价是存储量大了，以冗余来换计算工作量的节省和某些算法的易于实现。 例如，在Brep表达中，简单实体的数据结构可用体、面、边、点四个层次的表描述如下：对复杂实体的数据结构则采用更多的层次表来描述！对复杂实体的数据结构则采用更多的层次表来描述！ 边界表达强调实体的外表细节，把面、边、顶点的信息分层描述，并建立了层与层之间边界表示。 没有统一的数据结构，为了有效地表示几何体的拓扑关系，斯坦福大学BGBaumgart在1972年提出的以棱边为中心的多面体表示的翼边结构(Winged Edge Data Structure，WED)及改进后的对称结构等。3）BREP表示的数据

15、结构翼边结构以边为核心组织数据，如右图：棱边数据结构中包含两个点指针，指向该边的起点和终点，棱边为一有向线段。当棱边为曲线段时，还需增加一指针指向曲线表示的结构。 现在的现在的CADCAD系统数据结构都是翼边结构的变种系统数据结构都是翼边结构的变种WED中另设两个环指针，分别指向棱边所邻接的两个环(左环和右环)。由边环关系可确定棱边与邻面之间的拓扑关系。为了从棱边搜索到它所在的任一闭环上的其它棱边，数据结构中还增设四个指向邻边的指针，分别为左上边、左下边、右上边、右下边，左上边为棱边左边环中沿逆时针方向所连接的下一条边，其余类推。一种基于WED数据结构的BREP表示示例优点：（1)表示形体的点

16、、线、面等几何元素是显式表示、使得形体的显示很快并且很容易确定几何元素之间的连接关系；（2)可对Brep法的形体进行多种操作和局部修改；（3)能快速有效支持多种图形学、CAD系统的关键核心算法，为大多数商业化CG、CAD系统所采用。缺点：（1)数据结构复杂，需要大量存储空间，维护内部数据结构及一致性的程序较复杂；（2)对形体的修改操作较难实现；（3)其表达方法繁琐，尤其精确的边界难以人工定义；与工 程技术人员的操作习惯有较大差距，不适合直接交互。4）Brep表示法的优缺点简单形体BREP表达的数据结构手工填写实例： 边的方向定义后，其左右外环、左右面的连接关系唯一确定（右手法则），如右图：填表

17、注意事项：填表注意事项：先对点、边、环、面进行编号，编号顺序自定，但最好有利于编程实现；边的方向自定。左外环左外环左面左面右外环右外环右面右面环是由有序、有向的边组成的封闭边界，按右手法则，外环逆时针方向（确定面的外法矢方向），内环顺时针。面可以是平面或曲面，由一个外环和若干内环组成；法矢向外为正向面（由外环方向确定，确保指向实体外侧）。思考问题：思考问题：填写Brep表十分繁琐，对于复杂形体人工无法完成，如何完成复杂的BREP数据结构? ?3个面3个环3条边2个顶点4个面4个环6条边4个顶点注意：一个实体的BREP表达不唯一，如下图圆柱体表示； 不同CAD系统表达不同，不同建模方法也导致不一

18、致； 但都并不影响形体表达的完整性。3个面：顶平面（法矢向上）、底平面（法矢向下） 、 圆柱面（外法矢方向由外环确定）NN图（图（a） 圆柱的边、顶圆柱的边、顶点点图（图（b） 圆柱的面、环圆柱的面、环圆柱面方程表示：圆柱面方程表示：轴的起止点、半径，局部坐标。轴的起止点、半径，局部坐标。3个环：顶面外环、底面外环、侧面外环3条边：顶部圆、底部圆、侧面边（直母线）2个顶点：顶面1个点、底面1个点思考问题：圆的方程如何表示？思考问题：圆的方程如何表示？值得注意：对于更为复杂的形体、更多的应用需求，则需要采用更复杂的数据结构。（事实上，商业化CAD系统的数据结构较为复杂，不同CAD系统其应用范围及

19、目的不同，其内部数据结构也不完全相同）CSG中物体形状的定义以集合论为基础，先定义集合本身，其次是集合之间运算。所以，CSG表示先定义有界体素(如立方体、圆柱、球、锥、圆环等)，然后将这些体素进行并()、交()、差()运算（如图）。9.3.2、形体的CSG表达方法构造实体几何表示(Constructive Solid Geometry，缩写为CSG)的含义是任何复杂的形体都可用简单形体通过正则集合运算组合，并配合几何变换来表示。1977年由罗切斯特(Rochester)大学的Voelcker和Requicha等人首先提出的。1）CSG表达的基本概念基于CSG方法的形体生成过程可用一个有序的二叉

20、树数据结构来记录。二叉树的叶子节点是体素或几何变换的参数，非叶节点则是布尔运算的操作符或几何变换操作。任何子树表示其下两个节点的组合或变换的结果，树根表示最终的形体。 2）CSG表达的数据结构3）形体生成运算规则：完全遵循二叉树运算规则。前序遍历算法：自上而下，自左而右例：一个典型零件的CSG表达 用CSG树表示一个形体是无二义性的，但一个形体可以有不同的CSG树表示，取决于使用的体素、构造操作方法和操作顺序。 CSG表示依赖稳定可靠的布尔运算算法支撑。优点：(1) 数据结构比较简单，信息量小，易于管理；(2) 每个CSG都和一个实际的有效形体相对应；(3) CSG树记录了形体的生成过程，可修

21、改形体生成的各环节以改变形体的形状。缺点：(1) 不能进行形体的局部修改，如面、边、点等；(2) 直接基于CSG表达形体，其组合运算及显示效率很低。 4）CSG表达方法的特点CSGBREP的混合表示 从用户进行造型的角度看，CSG方法比较方便。但从对形体的存储管理和计算显示等角度看，Brep法更为实用。 CSG表示比较“宏观”， “战略” 掌控更容易，易人机交互； BREP表示注重“细节”，“战术”实施易落实，需编程实现。 目前大多数CAD系统都以CSGBrep的混合表示作为形体数据表示的基础。其中： 以CSG模型表示几何造型的特征历史过程及其特征设计参数； 用Brep模型维护详细的几何信息和

22、显示、查询等操作，同时也为布尔运算提供基础。 例如：例如： 商用商用CADCAD几何引擎几何引擎ACISACIS数据结构简介（选学）数据结构简介（选学） ACIS是美国Spatial Technology公司的三维几何造型引擎，它集线框、曲面和实体造型于一体，并允许这三种表示共存于统一的数据结构中，为各种3D造型应用开发提供几何造型平台，其数据结构如下:图中的黑虚线框中是几何信息，蓝虚线框中是拓扑信息。几何（Geometry）、拓扑(Topology)和属性(Attribute)构成了ACIS模型，三者统一由最基础的抽象类ENTITY所派生。ENTITY本身不代表任何对象，但在ENTITY中定

23、义了所有子类应具有的数据和方法（如存储、恢复、回溯等）。ACIS采用CSGBREP混合数据结构，其中拓扑信息包括 BODY（体）、LUMP（块）、SHELL（壳）、SUBSHELL（子壳）、FACE（面）、LOOP（环）、WIRE（线框）、COEDGE（共边）、EDGE（边）和VERTEX（顶点）。ACIS把线框（WIREFRAME）、曲面（SURFACE）和实体（SOLID）模型存储在统一的数据结构中，这种共存机制使ACIS支持混合维模型和各种非闭合模型的统一建模。几何信息几何信息拓扑信息拓扑信息形体表示方法线框模型表面模型实体模型空间分解构造表示边界表示单元枚举八叉树分解单元分解扫描方法C

24、SG方法特征体素BREP欧拉操作9.4 常见几何形体定义方法对CAD系统来说，形体定义就是用少量的参数描述几何形体的大小、形状和位置。几何造型的优劣首先取决于是否提供好的形体定义能力，既要有良好的用户界面以外，又要提供多种造型方法，这样不仅能扩大造型系统的几何覆盖率，而且能提高工程师的设计效率。在CAD系统中，常用几类形体输入方法： 1）基本体素法 2）扫描变换法 3）局部操作 4）特征表示 对于设计师而言，所关心的是如何快捷、方便地设计一个满足需求的零件结构（即零件形体）。1） 基本体素法常用的基本体素有方盒、锥、柱、球、环等。绝大多数商用CAD系统都提供该功能，尤其是游戏系统应用更广泛。用

25、户仅需输入一些简单的参数便可以定义这些体素的大小、形状和位置。因此商用系统提供自定义体素功能，为用户定义专用的特征库提供方便。 值得注意：用户仅需按提示交互定义（对话框或简单草图）形体，计算机内部用CSG表达数据结构记录定义参数及历史，同时自动生成定义形体的BREP表达模型数据。CAD系统中，基本体素法已与特征表达融合组成特征体素。2） 扫描变换法 扫描变换是基于一条曲线或表面或形体沿某一路径运动而产生形体，现有CAD使用广泛。 平行扫和旋转扫变换是最基本的方法。如果在平扫过程中引入缩放参数，还可以得到截面变化的锥形形体，如果扫描方向与z轴成一夹角，扫出的形体将是一个错切体。类似于曲面造型，还

26、有自由扫、变截面扫、蒙皮放样技术等生成实体的定义方法。思考问题：在此与曲面造型中的蒙皮放样有何区别？思考问题：在此与曲面造型中的蒙皮放样有何区别？值得说明的是：用户仅需按提示交互定义扫描截线及扫描轨迹，计算机内部用CSG数据结构记录定义参数及历史，同时自动生成定义形体的BREP表达模型数据。CAD系统中，扫描表达已与特征表达融合形成特征扫描方法。平行扫实例平行扫实例旋转扫实例旋转扫实例自由扫实例自由扫实例变截面扫实例变截面扫实例3）局部操作 局部操作从宏观上来看不改变形体的整体结构，只作局部修改。如圆角过渡、倒角等。 造型系统提供局部操作功能，目的是为用户提供更直观方便的定义形体局部信息的方法

27、。注意：局部操作功能多基于欧拉操作，比在整体意义下形体间的布尔运算具有更高的效率和稳定性 。倒圆角倒圆角倒直角倒直角圆角过渡圆角过渡4）实体的特征表示 实体模型仅提供产品的几何形状信息，但不能显式地标注尺寸，未提供公差、表面粗糙度、材料性能和加工要求等重要的产品制造信息。实体的特征表示方法是以上述几种几何表示方法为基础，通过CAD系统属性机制将工程特征信息添加于形体的几何（或拓扑）表示之上。在CAD系统中，这些几何和特征信息融合为一体，共同构成实体的特征表示，能有效表示设计人员的工程意图。（基于特征的定义方法将在后续内容中作更详细的介绍）5）形体的八叉树表示 八叉树表示通过对空间进行自适应划分，采用具有层次结构的八叉树来表示物体