第9讲 三维几何建模-1

1、计算机图形学与计算机图形学与CADCAD技术技术 华中科技大学华中科技大学 国家国家CAD支撑软件工程技术研究中心支撑软件工程技术研究中心 第第8讲讲 几何造型几何造型- - 本章目的本章目的 1了解计算机内部是怎样表达三维机械零部件模型了解计算机内部是怎样表达三维机械零部件模型 2了解实体模型了解实体模型CSG、BREP表达的基本原理表达的基本原理 3了解实体模型的其它表达方法了解实体模型的其它表达方法 1. 几何形体的计算机内部表达 2. 实体模型的CSG、BREP表达 3. 实体模型的其它表达方法 几何造型技术几何造型技术 几何造型技术是研究在计算机中，如何表达物体模型形几何造型技术是研

2、究在计算机中，如何表达物体模型形 状的技术。几何造型通过对点、线、面、体等几何元素状的技术。几何造型通过对点、线、面、体等几何元素 的数学描述，经过平移、旋转、变比等几何变换和并、的数学描述，经过平移、旋转、变比等几何变换和并、 交、差等集合运算，产生实际的或想象的物体模型。交、差等集合运算，产生实际的或想象的物体模型。 1几何形体的计算机内部表达 2实体模型的CSG、BREP表达 3. 实体模型的其它表达方法 第第8讲讲 几何造型几何造型-I-I 几何形体的计算机内部表达几何形体的计算机内部表达 线框模型和表面模型保存的三维形线框模型和表面模型保存的三维形 体信息都不完整。只有实体模型才能体

3、信息都不完整。只有实体模型才能 够完整地、无歧义地表示三维形体，够完整地、无歧义地表示三维形体， 已成为各种图形系统的核心已成为各种图形系统的核心 计算机中表示形体，通常用计算机中表示形体，通常用 n 线框模型线框模型 n 表面模型表面模型 n 实体模型实体模型 三种模式实质上代表了形体在计算三种模式实质上代表了形体在计算 机内三种不同的存储方式机内三种不同的存储方式 线框模型线框模型(wireframe Model) 线框模型线框模型用顶点和棱边表示三维形体，其棱边可以为用顶点和棱边表示三维形体，其棱边可以为 直线、圆弧、二次曲线及样条曲线组成直线、圆弧、二次曲线及样条曲线组成 。 线框模型

4、在计算机内存储的数据结构：线框模型在计算机内存储的数据结构： 顶点表：顶点表：记录各顶点坐标值记录各顶点坐标值； 棱线表：棱线表：记录每条棱线所连接的两顶点。记录每条棱线所连接的两顶点。 class POINT class EDGE double v3; /坐标值 int start_point_no; /边的起点 int pointtype; /点的属性 int end_point_no; /边的终点 CURVE cur； /边方程定义； . . 以立方体为例，其线框模型结构如下表：以立方体为例，其线框模型结构如下表： 优点优点 1.1.结构简单，计算机内部易于表达，绘制快速；结构简单，计算

5、机内部易于表达，绘制快速； 2.2.物体的三维数据可以产生任意视图，为生成工程图带来了方便物体的三维数据可以产生任意视图，为生成工程图带来了方便 缺点缺点 1.1.有二义性，缺少表面轮廓信息，当形状复杂、有二义性，缺少表面轮廓信息，当形状复杂、 棱线过多时，会引起模糊理解。棱线过多时，会引起模糊理解。 2.2.在数据结构中缺少边与面、面与体之间关系在数据结构中缺少边与面、面与体之间关系 的信息。从原理上讲，此种模型不能消除隐的信息。从原理上讲，此种模型不能消除隐 藏线、计算物性、生成数控加工刀具轨迹、藏线、计算物性、生成数控加工刀具轨迹、 有限元网格剖分、物体干涉检验等。有限元网格剖分、物体干

6、涉检验等。 表面模型表面模型(Surface Model) 表面模型表面模型是用有连接顺序的棱边围成的有限区域是用有连接顺序的棱边围成的有限区域 来定义形体的表面来定义形体的表面, ,再由表面的集合来定义形体。再由表面的集合来定义形体。 表面可以是平面，也可以是柱面、球面等类型的表面可以是平面，也可以是柱面、球面等类型的 二次曲面，也可是样条曲面构成的自由曲面。二次曲面，也可是样条曲面构成的自由曲面。 表面模型是在线框模型的基础上，增加有关面边表面模型是在线框模型的基础上，增加有关面边 信息以及表面特征、棱边的连接方向等内容。信息以及表面特征、棱边的连接方向等内容。 表面模型存储几何信息的方法

7、是建立三表结构，表面模型存储几何信息的方法是建立三表结构， 即即顶点表顶点表、边表和面表边表和面表。 1.1. 顶点坐标值存放在顶点坐标值存放在顶点表顶点表中；中； 2.2. 含有指向顶点表指针的含有指向顶点表指针的边表边表，用来为多边形的，用来为多边形的 每条边标识顶点；每条边标识顶点； 3.3. 面表面表有指向边表的指针，用来为每个表面标识有指向边表的指针，用来为每个表面标识 其组成边。其组成边。 class POINT class EDGE class FACE 同线框模型同线框模型 同线框模型同线框模型 int edge_num； /边数边数 int *edge_no; /边链表边链表

8、 int face_type; /面类型面类型 SURFACE sur； /面方程面方程 . . . 以立方体为例，其表面模型结构如下表：以立方体为例，其表面模型结构如下表： 表面模型唯一没有解决的问题是形体究表面模型唯一没有解决的问题是形体究 竟在表面的哪一侧竟在表面的哪一侧，因而在物性计算、有限元，因而在物性计算、有限元 分析等应用中，表面模型在形体的表示上仍然分析等应用中，表面模型在形体的表示上仍然 缺乏完整性。缺乏完整性。 表面模型可以满足面面求交，线面消隐、表面模型可以满足面面求交，线面消隐、 明暗处理和数控加工的要求。明暗处理和数控加工的要求。 表面模型的特点表面模型的特点 为了解

9、决形体存在于表面的哪一侧的问题，可采用实为了解决形体存在于表面的哪一侧的问题，可采用实 体模型来描述三维立体体模型来描述三维立体 在表面模型的基础上可用三种方法来定义表面的哪在表面模型的基础上可用三种方法来定义表面的哪 一侧存在实体。一侧存在实体。 给出实体存在一侧的一点；给出实体存在一侧的一点； 直接用表面的外法矢来指明实体存在的一侧；直接用表面的外法矢来指明实体存在的一侧； 用有向棱边隐含地表示表面的外法矢方向。用有向棱边隐含地表示表面的外法矢方向。（该方（该方 法为法为CADCAD系统广泛采用）系统广泛采用） 实体模型实体模型(Solid Model) （思考：为什么不直接用法矢？）（思

10、考：为什么不直接用法矢？） 用有向棱边隐含地表示表面的用有向棱边隐含地表示表面的 外法矢方向时，规定有向棱边按外法矢方向时，规定有向棱边按右右 手法则手法则取向取向：沿着沿着闭合的棱边闭合的棱边所得所得 的方向与表面外法矢方向一致。的方向与表面外法矢方向一致。 思考：相邻两个面的公共棱边思考：相邻两个面的公共棱边 的方向不会矛盾吗？的方向不会矛盾吗？ （有矛盾，（有矛盾，CADCAD系统中增加系统中增加“环环” ” 的定义解决矛盾）的定义解决矛盾） class POINT class EDGE class FACE 同线框模型同线框模型 同线框模型同线框模型 int edge_num； /边数

11、边数 EDGE * edge; /边链表边链表 int face_type; /面类型面类型 SURFACE sur； /面方程面方程 . . . 数据结构如下：数据结构如下： 根据实体模型，可以进行物性计算（如体积、质根据实体模型，可以进行物性计算（如体积、质 量，惯量）、有限元分析等应用。量，惯量）、有限元分析等应用。 从前面的实体模型可知，本质上我们仍然采用形从前面的实体模型可知，本质上我们仍然采用形 体的体的边界表面边界表面的数学描述代替实体描述的数学描述代替实体描述, ,这种典型的描这种典型的描 述方法通常称为实体的述方法通常称为实体的边界表达方法（边界表达方法（BREPBREP）

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

13、算构造形体 只能产生正则形体只能产生正则形体 抽象形体的层次较低抽象形体的层次较低 1几何形体的计算机内部表达 2实体模型的CSG、BREP表达 3. 实体模型的其它表达方法 第第8讲讲 几何造型几何造型-I-I 实体模型能够完整地、无歧义地表示实体模型能够完整地、无歧义地表示 三维形体，已成为各种图形系统的核心。三维形体，已成为各种图形系统的核心。 在实体模型的表示中，出现了许多方法，在实体模型的表示中，出现了许多方法， 基本上可以分为三大类基本上可以分为三大类 u 空间分解表示空间分解表示 u 构造表示构造表示(CSG)(CSG) u 边界表示边界表示(BREP)(BREP) 空间分解表示

14、有空间分解表示有单元枚举单元枚举、八叉八叉 树分解树分解等等 构造表示是按照生成过程来定义构造表示是按照生成过程来定义 形体的方法，构造表示通常有形体的方法，构造表示通常有扫描扫描 表示表示、构造实体几何表示构造实体几何表示和和特征表特征表 示示三种。三种。 边界表示边界表示( (Boundary RepresentationBoundary Representation， 缩写缩写BrepBrep) )通过描述实体的边界来表示实通过描述实体的边界来表示实 体。实体的边界将该实体分为实体内点体。实体的边界将该实体分为实体内点 集和实体外点集，是实体与环境之间的集和实体外点集，是实体与环境之间的

15、 分界面。定义了实体的边界，实体就被分界面。定义了实体的边界，实体就被 唯一定义，如右图所示。唯一定义，如右图所示。 实体实体的边界通常是由的边界通常是由面面的并集来表示的并集来表示, , 面可以是一组曲面（或平面），如图为面可以是一组曲面（或平面），如图为 平面表示的立体和曲面表示的立体。平面表示的立体和曲面表示的立体。 而每个面又由它的数学定义加上其边而每个面又由它的数学定义加上其边 界来表示，面的边界是界来表示，面的边界是环环边的并集，边的并集， 而而边边又是由又是由点点来表示的。来表示的。 边界表式方法边界表式方法(BREP) 点点用三维坐标表示，是最基本的元素用三维坐标表示，是最基本

16、的元素 边边是形体相邻面的交界，可为空间直是形体相邻面的交界，可为空间直 线或曲线线或曲线 环环是由有序、有向的边组成的封闭边是由有序、有向的边组成的封闭边 界。环有内、外环之分，外环最大且界。环有内、外环之分，外环最大且 只有一个；内环的方向和外环相反，只有一个；内环的方向和外环相反， 外环边通常按逆时针方向排序，内环外环边通常按逆时针方向排序，内环 边通常按顺时针方向排序。边通常按顺时针方向排序。 面面是一是一个多连通区域个多连通区域，可以是平面或曲面，由一个外环，可以是平面或曲面，由一个外环 和若干个内环组成。根据环的定义，在面上沿环的方向和若干个内环组成。根据环的定义，在面上沿环的方向

17、 前进，左侧总在面内，右侧总在面外。面的方向用垂直前进，左侧总在面内，右侧总在面外。面的方向用垂直 于面的法矢表示，法矢向外为正向面。于面的法矢表示，法矢向外为正向面。 实体实体是由若干个面组成的闭包，实体的边界是有限个面是由若干个面组成的闭包，实体的边界是有限个面 的集合。的集合。 BrepBrep中必须表达的信息分为两类中必须表达的信息分为两类: : 一类是一类是几何信息几何信息。描述形体的大小、位置、形状等基。描述形体的大小、位置、形状等基 本信息，如顶点坐标，边和面的数学表达式等。本信息，如顶点坐标，边和面的数学表达式等。 另一类是另一类是拓扑信息拓扑信息。拓扑信息描述形体上的顶点、边

18、、。拓扑信息描述形体上的顶点、边、 面的连接关系。面的连接关系。 拓扑信息形成物体边界表示的拓扑信息形成物体边界表示的“骨架骨架”，形体的几何，形体的几何 信息犹如附着在信息犹如附着在“骨架骨架”上的上的“肌肉肌肉”。 在在BrepBrep中，拓扑信息是指用来说明体、面、边及顶点中，拓扑信息是指用来说明体、面、边及顶点 之间连接关系的这一类信息，例如面与哪些面相邻；面由之间连接关系的这一类信息，例如面与哪些面相邻；面由 那些边组成等。那些边组成等。 描述形体拓扑信息的根本目的是便于直接对构成形体描述形体拓扑信息的根本目的是便于直接对构成形体 的各面、边及顶点的参数和属性进行存取和查询，便于实的

19、各面、边及顶点的参数和属性进行存取和查询，便于实 现以面、边、点为基础的各种几何运算和操作。现以面、边、点为基础的各种几何运算和操作。 例如：多面体的面、边和顶点间的九种拓扑关系例如：多面体的面、边和顶点间的九种拓扑关系 面面邻接关系面面邻接关系 面上点的关系面上点的关系 面上边的关系面上边的关系 点与面连接关系点与面连接关系 点点连接关系点点连接关系 点与边连接关系点与边连接关系 边面邻接关系边面邻接关系 边点连接关系边点连接关系 边边连接关系边边连接关系 在这九种不同类型的拓扑关系中，有些关系冗余，在这九种不同类型的拓扑关系中，有些关系冗余， 因此计算机内部并不需要所有拓扑关系都直接表达。

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

21、描述 边界表示强调实体的外表细节，把面、边、顶点的信息分边界表示强调实体的外表细节，把面、边、顶点的信息分 层描述，并建立了层与层之间边界表示。层描述，并建立了层与层之间边界表示。 没有统一的数据结构，为了有效地表示几何体的拓扑关系没有统一的数据结构，为了有效地表示几何体的拓扑关系 ，斯坦福大学，斯坦福大学B BG GBaumgartBaumgart在在19721972年提出的以棱边为中心的年提出的以棱边为中心的 多面体表示的多面体表示的翼边结构翼边结构( (Winged Edge Data Winged Edge Data StructureStructure，WEDWED) ) 及改进后的

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

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

24、尔运算 BREP表达数据结构举例表达数据结构举例 Brep表示法的优点：表示法的优点： 1.1. 表示形体的点、线、面等几何元素是显式表示、使得形体表示形体的点、线、面等几何元素是显式表示、使得形体 的显示很快并且很容易确定几何元素之间的连接关系；的显示很快并且很容易确定几何元素之间的连接关系； 2.2. 可对可对BrepBrep法的形体进行多种局部操作，比如倒角；法的形体进行多种局部操作，比如倒角； 3.3. 便于在数据结构上附加各种非几何信息，如精度、表面粗便于在数据结构上附加各种非几何信息，如精度、表面粗 糙度等。糙度等。 4.4. BrepBrep表示覆盖域大，原则上能表示所有的形体表

25、示覆盖域大，原则上能表示所有的形体 缺点：缺点： 1.1. 数据结构复杂，需要大量存储空间，维护内部数据结构及数据结构复杂，需要大量存储空间，维护内部数据结构及 一致性的程序较复杂；一致性的程序较复杂； 2.2. 对形体的修改操作较难实现；对形体的修改操作较难实现； 3.3. BrepBrep表示不一定对应一个有效形体。表示不一定对应一个有效形体。 构造实体几何表示构造实体几何表示( (Constructive Solid GeometryConstructive Solid Geometry， 缩写为缩写为CSG)CSG)的含义是任何复杂的形体都可用简单形体的含义是任何复杂的形体都可用简单形

26、体 通过正则集合运算组合，并配合几何变换来表示。通过正则集合运算组合，并配合几何变换来表示。 在在19771977年由罗切斯特年由罗切斯特(Rochester)(Rochester)大学的大学的VoelckerVoelcker和和 BequichaBequicha等人首先提出的。等人首先提出的。 CSGCSG中物体形状的定义中物体形状的定义以集合论为基础，先定义集合以集合论为基础，先定义集合 本身，其次是集合之间运算本身，其次是集合之间运算。所以，。所以，CSGCSG表示先定义有表示先定义有 界体素界体素( (如立方体、圆柱、球、锥、圆环等如立方体、圆柱、球、锥、圆环等) )，然后将，然后将

27、这些体素进行并、交、差运算（如图）。这些体素进行并、交、差运算（如图）。 构造实体几何表示方法构造实体几何表示方法(CSG) A 体B 体 A* B A* BA*B 形体的形体的CSGCSG可看成是一个有序的二叉树可看成是一个有序的二叉树，其叶子，其叶子 节点是节点是体素体素或或几何变换的参数几何变换的参数，非叶节点则是，非叶节点则是布尔运布尔运 算的操作符算的操作符或或几何变换操作几何变换操作。任何子树表示其下两个。任何子树表示其下两个 节点的组合或变换的结果，树根表示最终的形体。节点的组合或变换的结果，树根表示最终的形体。 用用CSGCSG树表示一个形体是无二义性的，但一个形树表示一个形体

28、是无二义性的，但一个形 体可以有不同的体可以有不同的CSGCSG树表示，取决于使用的体素、构树表示，取决于使用的体素、构 造操作方法和操作顺序。造操作方法和操作顺序。 CSGCSG表示依赖稳定可靠的布尔运算算法支撑。表示依赖稳定可靠的布尔运算算法支撑。 CSG表示法的优点：表示法的优点： 1.1.数据结构比较简单，数据量比较小，易于管理；数据结构比较简单，数据量比较小，易于管理； 2.2.每个每个CSGCSG都和一个实际的有效形体相对应；都和一个实际的有效形体相对应； 3.3.CSGCSG树记录了形体的生成过程，可修改形体生成的各环节树记录了形体的生成过程，可修改形体生成的各环节 以改变形体的

29、形状；以改变形体的形状； 4.4.CSGCSG表示可方便地转换成边界（表示可方便地转换成边界（BrepBrep）表示。）表示。 缺点：缺点： 1.1.对形体的表示受体素的种类和对体素操作的种类的限制，对形体的表示受体素的种类和对体素操作的种类的限制， 也就是说，也就是说，CSGCSG方法表示形体的覆盖域有较大的局限性；方法表示形体的覆盖域有较大的局限性； 2.2.不能进行形体的局部修改，例如，不能对基本体素的交不能进行形体的局部修改，例如，不能对基本体素的交 线倒圆角；线倒圆角； 3.3.由于形体的边界几何元素（点、边、面）是隐含地表示由于形体的边界几何元素（点、边、面）是隐含地表示 在在CS

30、GCSG中，集合中，集合运算效率低，运算效率低，显示显示CSGCSG表示的形体需要较表示的形体需要较 长的时间。长的时间。 从用户进行造型的角度看，从用户进行造型的角度看，CSGCSG方法比较方便，从对方法比较方便，从对 形体的存储管理和操作的角度看，形体的存储管理和操作的角度看，BrepBrep法更为实用。法更为实用。 CSGBREP混合表示混合表示 目前大多数目前大多数CADCAD系统都以系统都以CSGCSGBrepBrep的混合表示作为的混合表示作为 形体数据表示的基础：形体数据表示的基础： u 以以CSGCSG模型表示几何造型的特征历史过程及其特模型表示几何造型的特征历史过程及其特 征

31、设计参数；征设计参数； u 用用BrepBrep模型维护详细的几何信息和显示、查询等模型维护详细的几何信息和显示、查询等 操作，同时也为布尔运算提供基础。操作，同时也为布尔运算提供基础。 ACIS ACIS是美国是美国Spatial TechnologySpatial Technology公司推出的三维几何造型引擎，公司推出的三维几何造型引擎， 它集线框、曲面和实体造型于一体，并允许这三种表示共存于统一它集线框、曲面和实体造型于一体，并允许这三种表示共存于统一 的数据结构中。的数据结构中。 几何（几何（GeometryGeometry）、拓扑）、拓扑(Topology)(Topology)和属

32、性和属性(Attribute)(Attribute)构成构成 了了ACISACIS模型，三者统一由最基础的抽象类模型，三者统一由最基础的抽象类ENTITYENTITY所派生所派生. .虽然虽然 ENTITYENTITY本身不代表任何对象，但在本身不代表任何对象，但在ENTITYENTITY中定义了它所有子类应中定义了它所有子类应 具有的数据和方法（如存储、恢复、回溯等）。具有的数据和方法（如存储、恢复、回溯等）。 ACIS ACIS的拓扑包括的拓扑包括BODYBODY（体）、（体）、LUMPLUMP（块）、（块）、SHELLSHELL（壳）、（壳）、 SUBSHELLSUBSHELL（子壳）、

33、（子壳）、FACEFACE（面）、（面）、LOOPLOOP（环）、（环）、WIREWIRE（线框）、（线框）、 COEDGECOEDGE（公共边）、（公共边）、EDGEEDGE（边）和（边）和VERTEXVERTEX（顶点）。（顶点）。 ACIS ACIS的几何包括的几何包括SURFACE(SURFACE(面面) )、CURVECURVE（线（线) )、APOINTAPOINT（点（点) )。 一个典型的一个典型的CAD几何引擎几何引擎ACIS介绍介绍* ACIS ACIS把线框（把线框（WIREFRAMEWIREFRAME）、曲面（）、曲面（SURFACESURFACE）和实体（）和实体（S

34、OLIDSOLID） 存储在统一的数据结构中，这种共存机制使存储在统一的数据结构中，这种共存机制使ACISACIS支持混合维模型和支持混合维模型和 各种非闭合模型。各种非闭合模型。 ACIS中模型的数据结构中模型的数据结构 ACIS中模型的中模型的C+类层次关系类层次关系 ACIS拓扑对象间的关系以及拓扑与几何间的关系 1几何形体的计算机内部表达 2实体模型的CSG、BREP表达 3. 实体模型的其它表达方法 第第8讲讲 几何造型几何造型-I-I 将形体按某种规则分解为小的更易于描述的将形体按某种规则分解为小的更易于描述的 部分，每一小部分又可分为更小的部分，这种分部分，每一小部分又可分为更小

35、的部分，这种分 解过程直至每一小部分都能够直接描述为止。解过程直至每一小部分都能够直接描述为止。 1.空间位置枚举表示 2.八叉树表示 空间分割表示空间分割表示 空间位置枚举表示空间位置枚举表示 空间位置枚举法空间位置枚举法是一种穷举是一种穷举 表示法，它可以用来表示任表示法，它可以用来表示任 何物体，通常情况下，它只何物体，通常情况下，它只 是物体的近似表示。是物体的近似表示。 当立方体被物体所占据时，取当立方体被物体所占据时，取 值为值为1 1，否则为，否则为0 0。这样，三维。这样，三维 数组就唯一表示了包含于立方数组就唯一表示了包含于立方 体之内的物体。体之内的物体。 优点：优点：采用这种表示很容易采用这种表示很容易 实现物体的集合运算以及计实现物体的集合运算以及计 算物体的诸如体积等的许多算物体的诸如体积等的许多 整体性质。整体性质。 缺点：缺点：如果没有明确给出物如果没有明确给出物 体的边界信息，不适于图形体的边界信息，不适于图形 显示，并且它占据的存储量显示，并且它占据的存储量 非常大。非常大。 八叉树表示法八叉树表示法对空间位置对空间位置 枚举法中的空间分割方法做枚举法中的空间分割方法做 了改进，它并不是统一将物了改进，它并不是统一将物 体所在的立方体空间均匀划体所在的立方体空间均匀划 分