第9讲 三维几何建模-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中常用的形体定义方法几何造型技术是研究在计算机中，如何表达物体模型形状的技术。几何造型通过对点、线、面、体等几何元素的数学描述，经过平移、旋转、变比等几何变换和并、交、差等集合运算，产生实际的或想象的物体模型。

9.1几何造型技术概述几何造型的作用9.2几何形体的计算机内部表达9.2.1形体表达的基本概念在CG和CAD中，形体的边界是由面的并集来表示，每个面又由它的数学定义加上其边界来表示，面的边界是环边的并集，而边又是由点来表示的。点用三维坐标表示，是最基本的元素边是相邻面的交界，可为有向直线或曲线环是由有序、有向的边组成的封闭边界，环有内、外环之分，外环最大且只有一个，内环的方向和外环相反。面是一个单连通区域，可以是平面或曲面，由外环和若干个内环组成；面的方向用垂直于面的法矢表示，法矢向外为正向面。体是由若干个面组成的闭包，实体的边界是有限个面的集合。在CG和CAD中，点、线、环、面、体通常用一个具有层次描述的数据结构来表达定义。形体描述示意图形体的层次数据结构示意图正则形体：形体表面上任一点的足够小的邻域在拓扑上应是一个等价的封闭圆，即围绕该点的形体邻域在二维空间中可构成一个单连通域。我们把满足该定义的形体称为正则形体，否则为非正则形体。例如，存在悬面、悬边的长方体为非正则形体（如右图）。计算机中表示形体，通常用线框模型（如图a）、表面模型（如图b）和实体模型（如图c）等表达方法。图a线框模型图b表面模型图c实体模型9.2.2形体表达方法1）形体表达方法概述实体模型的表示方法中又可以分为：空间分解类（如单元枚举、八叉树分解、单元分解等）、构造类（如扫描、CSG、特征参数化体素等）和边界表达类（如BREP、欧拉操作等）三大类。

其中CSG、BREP表示是当前CAD系统广泛采用的方法。形体表示方法线框模型表面模型实体模型空间分解构造表示边界表示单元枚举八叉树分解单元分解……扫描方法CSG方法特征体素……BREP欧拉操作……线框、表面与实体模型的比较模型表示应用范围局限性二维线框画二维线框图（工程图）无法观察参数的变化，不可能产生有实际意义的形体三维线框画二、三维线框图不能表示实体、图形会有二义性表面模型艺术图形、形体表面的显示、数控加工不能表示实体实体模型物性计算、有限元分析用集合运算构造形体只能产生正则形体抽象形体的层次较低2）形体表达的线框模型线框模型用顶点和棱边表示三维形体，其棱边可以为直线、圆弧、二次曲线及样条曲线组成。

线框模型组成：线框模型数据结构：

顶点表记录各顶点坐标值；

棱线表记录每条棱线所连接的顶点及走向。classPOINTclassEDGE{{doublev[3];//坐标值intstart_point_no;//边的起点intpointtype;//点的属性intend_point_no;//边的终点

CURVEcur；//边方程定义；

…………..

…………..}}例：立方体线框模型数据结构如下：线框模型优点：1）结构简单，计算机内部易于表达，绘制快速；2）形体三维数据可以产生任意视图，为生成工程图带来了方便。线框模型缺点：1）有二义性，缺少表面轮廓信息，当形状复杂、棱线过多时，会引起模糊理解。2）在数据结构中缺少边与面、面与体之间关系的信息。从原理上讲，此种模型不能消除隐藏线、计算物性、生成数控加工刀具轨迹、有限元网格剖分、物体干涉检验等。3）形体表达的表面模型表面模型是用有连接顺序的棱边围成的有限区域来定义形体的表面,再由表面的集合来定义形体。表面可以是平面，也可以是柱面、球面等类型的二次曲面，也可是样条曲面构成的自由曲面。1）顶点坐标值存放在顶点表中；2）含有指向顶点表指针的边表，用来为多边形的每条边标识顶点；边有方向，从起点到终点为正方向；3）面表有指向边表的指针，用来为每个表面标识其组成边。表面模型数据结构采用三表结构，即：面表、边表和顶点表。只需在线框模型的基础上增加有关面边信息以及表面特征、棱边连接方向等。表面模型的数据结构：面号classPOINTclassEDGEclassFACE{{{

同线框模型同线框模型intedge_num；//边数

int*edge_no;//边链表

intface_type;//面类型

SURFACEsur；//面方程

………….………….…………….}}}例：多面体表面模型数据结构缺点：没有解决形体究竟在表面的哪一侧的问题。在物性计算、有限元分析等应用中，表面模型在形体的表示上仍然缺乏完整性。优点：可满足面面求交，线面消隐、明暗处理和数控加工的要求。表面模型的特点：4）形体表达的实体模型为了解决形体存在于表面的哪一侧的问题，可采用实体模型来描述三维立体。在表面模型的基础上可用三种方法来定义表面的哪一侧存在实体。1）给出实体存在一侧的一点；2）直接用表面的外法矢来指明实体存在的一侧；3）用有向棱边隐含地表示表面的外法矢方向，该方法为CAD系统广泛采用。思考问题：表示法矢为什么用有向棱边，而不直接法矢??用有向棱边表示表面的外法矢方向时，规定有向棱边按右手法则取向：沿着闭合的棱边所得的方向与表面外法矢方向一致。千万注意：例：多面体实体模型数据结构如下：classPOINTclassEDGEclassFACE{{{

同线框模型同线框模型intedge_num；//边数

EDGE*edge;//边链表

intface_type;//面类型

SURFACEsur；//面方程

………….………….………….}}}有矛盾!!!增加“环”的定义解决矛盾。思考问题：相邻两个面的公共棱边的方向不会矛盾吗？??classPOINTclassLOOPclassFACE{{{

同线框模型intlop_typ;//环类型intloop_num；//环数………int*eno;//边索引

LOOP*lop;//环链表}LOOP*nxt;//下一环intface_type;//面类型………….SURFACEsur；//面方程classEDGE

}………….{}同线框模型………}用“＋、－”标识边的方向改进的数据结构如下：实体模型表达的特点：根据实体模型，可以进行物性计算（如体积、质量，惯量）、有限元分析等应用。一个有趣的问题：一个表面的正反两面都是确定的吗??MObius曲面9.3、形体的BREP、CSG表达方法

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

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

例如，在Brep表达中，简单实体的数据结构可用体、面、边、点四个层次的表描述如下：对复杂实体的数据结构则采用更多的层次表来描述！！边界表达强调实体的外表细节，把面、边、顶点的信息分层描述，并建立了层与层之间边界表示。没有统一的数据结构，为了有效地表示几何体的拓扑关系，斯坦福大学B．G．Baumgart在1972年提出的以棱边为中心的多面体表示的翼边结构(WingedEdgeDataStructure，WED)及改进后的对称结构等。3）BREP表示的数据结构翼边结构以边为核心组织数据，如右图：棱边数据结构中包含两个点指针，指向该边的起点和终点，棱边为一有向线段。当棱边为曲线段时，还需增加一指针指向曲线表示的结构。

现在的CAD系统数据结构都是翼边结构的变种WED中另设两个环指针，分别指向棱边所邻接的两个环(左环和右环)。由边环关系可确定棱边与邻面之间的拓扑关系。为了从棱边搜索到它所在的任一闭环上的其它棱边，数据结构中还增设四个指向邻边的指针，分别为左上边、左下边、右上边、右下边，左上边为棱边左边环中沿逆时针方向所连接的下一条边，其余类推。一种基于WED数据结构的BREP表示示例优点：（1)表示形体的点、线、面等几何元素是显式表示、使得形体的显示很快并且很容易确定几何元素之间的连接关系；（2)可对Brep法的形体进行多种操作和局部修改；（3)能快速有效支持多种图形学、CAD系统的关键核心算法，为大多数商业化CG、CAD系统所采用。缺点：（1)数据结构复杂，需要大量存储空间，维护内部数据结构及一致性的程序较复杂；（2)对形体的修改操作较难实现；（3)其表达方法繁琐，尤其精确的边界难以人工定义；与工程技术人员的操作习惯有较大差距，不适合直接交互。4）Brep表示法的优缺点简单形体BREP表达的数据结构手工填写实例：边的方向定义后，其左右外环、左右面的连接关系唯一确定（右手法则），如右图：填表注意事项：先对点、边、环、面进行编号，编号顺序自定，但最好有利于编程实现；边的方向自定。左外环左面右外环右面环是由有序、有向的边组成的封闭边界，按右手法则，外环逆时针方向（确定面的外法矢方向），内环顺时针。面可以是平面或曲面，由一个外环和若干内环组成；法矢向外为正向面（由外环方向确定，确保指向实体外侧）。思考