3.4 实体造型方法
几何实体建模研究的重点是用简单几何体构造复杂组合实体，即研究如何方便地定义形状简单的几何体（体素），如何经过适当的布尔集合运算构造出所需的复杂几何体，并最终在图形设备上输出各种视图。常用的三维实体造型方法有构造实体几何法（Constructive Solid Geometry, CSG）、边界表示法（Boundary Representation, B-Rep）和单元分解法（Cell Decomposition）。
3.4.1 构造实体几何法
构造实体几何法（也称几何体素构造法）是一种用简单几何体素构造复杂实体的造型方法，由罗切斯特（Rochester）大学的Voelcker和Bequicha等人在1977年首先提出。CSG的基本思想是一个复杂物体可由一些比较简单、规则的形体（体素）经过布尔运算得到。在CSG中，物体形状的定义是以集合论为基础的，首先是集合本身的定义，其次是集合之间的运算，所以，几何体素构造法首先定义有界体素（例如立方体、圆柱体、球体、锥体、环状体等），然后对这些体素施以并、交、差等布尔运算。
基本体素是指能够用有限个尺寸参数进行定形和定位的简单的封闭空间，如长方体可以通过长、宽、高来定义。此外还要定义体素在空间的基准点、位置和方向。布尔运算是指两个或两个以上体素经过集合运算得到新的实体的一种方法。经过布尔运算生成的形体应该是具有良好边界的几何形体，并保持初级形体的维数。为解决如悬面、悬边和悬点的情况，人们提出了正则布尔运算来得到有效的实体。
采用构造实体几何法构建三维实体的过程可以用一棵二叉树来描述，也称CSG树。CSG树的叶节点为基本体素或变换参数，中间点为集合运算符号或经集合运算生成的中间形体，树根为生成的最终几何形体，它可以完整地记录一个形体的生成过程。CSG可看成是物体单元分解的结果。在模型被分解为单元以后，通过拼合运算（并集）能使其结合为一体，其中，组件只能在匹配的面上进行拼接。CSG可以进行正则布尔运算（并集、交集、差集），从而既可以增加体素，又可以移去体素。
在图3.10中，5个叶节点代表体素和平移量，4个内部节点表示运算结果，树根表示最终得到的物体。值得注意的是，最初各中间物体都是有效的有界实体。此外，变换并不限于刚性运动，各种放大和相似变换在理论上都是可能的，只是要受布尔运算功能的限制。如果造型系统中的基本体素是由系统定义的有效的有界实体，且拼合运算是正则运算，那么拼合运算得到的最终实体模型也是有效和有界的。
图3.10 CSG构造实体的过程
CSG与机械装配方式类似。对机械产品来说，是先设计制造零件，然后将零件装配成产品；用CSG表示构造几何形体时，则是先定义体素，然后通过布尔运算将体素拼合成所需要的几何体。因此，一个几何形体可视为拼合过程中的半成品，其特点是信息简单无冗余，处理方便，并详细记录了构成几何体的原始特征和全部定义参数，必要时还可以附加几何体体素的各种属性。CSG表示的几何体具有唯一性和明确性，但一个几何体的CSG表示和描述方式却不是唯一的，即可以用几种不同的CSG树表示。
3.4.2 边界表示法
边界表示法是用实体的有界表面来表示一个实体。这种方法把实体的表面分解成小面（Faces）的集合来表示，构成实体完整的表皮，每个小面由位于这个表面上的一条封闭的边界曲线表示。边界曲线又由边（Edges）组成，最后边由顶点确定。边界表示的一个重要特点是在这种表示法中，描述形体的信息包括几何信息（Geometry）和拓扑信息（Topology）两个方面，拓扑信息描述形体上的顶点、边、面的连接关系，拓扑信息形成物体边界表示的“骨架”，形体的几何信息犹如附着在“骨架”上的肌肉，如形体的定型、定位尺寸、表面方程等。
用来定义形体表面的边界面可以是平面（称为多面体），也可以是曲面（称为雕塑实体）。形体上的边可以是直线段，也可以是曲线段。三维物体采用边界表示最普遍的方式是使用一组包围物体内部的表面多边形。
B-Rep是以物体边界表面为基础定义和描述几何形体的方法。这种方法能给出物体完整的、可显示的边界描述。其原理：物体都由有限个面构成，每个面（平面或曲面）由有限条边围成的有限个封闭域定义。或者说，物体的边界是有限个单元面的并集，而每一个单元面也必须是有界的。用边界法描述实体，实体须满足这样一个条件，即封闭、有向、不自交、有限和相连接，并能区分实体边界内、边界外和边界上的点。
根据边界表示原理，如图3.11所示实体可用一系列点和边有序地将其边界划分成许多单元面。该实体可以方便地分成10个单元面，各个单元面由有向、有序的边组成，每条边则由两个点定义。圆柱体底面和顶面自然也是一个单元面。圆柱面的分割有多种方法，图中划分为前、后两个圆柱面，每个柱面则由有向、有序的直线和圆弧线构成，而圆弧线则由三个点定义圆的方法描述。当用边界表示法描述曲面实体时将需要更多条件，例如一个Bezier曲面就需由其特征多边形顶点网格定义，该曲面上的曲线则用特征多边形顶点定义。通常，以边界表示的建模系统中都采用翼边数据结构。翼边数据结构最初由美国斯坦福大学提出。它以边为核心，通过某条边可以检索到该边的左边和右边的两个端点及上、下、左、右的四条邻边，从而确定各元素之间的连接关系。
图3.11 实体的B-Rep表示法
3.4.3 单元分解法
单元分解法将简单的造型块粘连在一起来描述实体。以非常普通的杯子为例，假定将它分解成一些独立的小件，使分解至最后的那些小件比原杯子容易描述。第一步，先将把手分开，这是很自然的一步，拓扑上也很合理。现在是两个零件，每个零件都只有单连通的拓扑关系，而不是一个多连通的物体。第二步，将杯底分出来，则有两个单连通的零件和一个多连通的零件。每个零件都比原来的杯子容易描述。如有必要，可一直分解下去，直到满足预定的可描述性标准为止。这一过程就是单元分解。每个实体都可表示为这些被分解成的单元的并集。采用单元分解的理由：整个物体可能无法表示，而它的单元却可以表示。将实体分解成单元的方法很多，但没有一种是唯一的，不过都无二义性。用于结构分析的单元分解通常是有限元造型的基础。
最简单的完全枚举法（Exhaustive Enumeration）是将欲表示的实体沿着直角坐标平面的方向分割为大小、形状一致的立方块。完全枚举法的概念比较清晰，对模型进行操作简单，但是要求系统有很大的存储量，而且精度不高。例如，在如图3.12所示的模型中，大约需要1300个立方块，但是模型看上去还是很粗糙，所以分解模型对一般的设计模型的实际应用比较困难。为了克服这些缺点，后来出现了更有效、实用的分解方法——空间分解法（Space Subdivision）。
图3.12 完全枚举法
空间分解法是单元分解法的一种特殊情况。在这种情况下，单元形状是立方体并位于固定的空间格栅中。随着立方体尺寸的减小，该方法逼近以空间中一组连续的点来表示的实体。用空间分解法来定义实体，需要用很方便的方法来表示这组立方体单元。一种方法是将单元中心的坐标点列表，实体就成为一组相邻的单元。单元的尺寸决定着模型的最高分辨率。
用空间分解法表示实体有两个优点：①可以较容易地存取一个给定的点；②可以保证空间的唯一性。同时该方法也有缺点：在物体的零件之间没有明显的关系，需要大量的存储空间。
空间数组中的一个单元可以被实体所占据，也可以不被占据。可以用二进制的1或0标记单元。早期，这种方法就很冗余，因为物体的所有单元都要标记。实际上，在物体内部的单元都具有与其邻近单元相同的状态，只有接近物体边界的单元才改变状态。
四叉树（Quadtrees）和八叉树（Octrees）为空间分解法提供了一种更有效的算法。二维形体的四叉树描述是以方域递归细分成小方域为基础的。每个节点代表平面上的一个小方域。在计算机图像应用中，这个平面是图形显示的屏幕平面。注意：如果二叉树的每个节点都有2个分枝，那么四叉树的每个节点就有4个分枝。
将一个方域与任意的二维形体重叠。若该形体不能全部覆盖方域，则将方域再细分成4个相等的小方域。如果任何一个小方域满了或空着，则不必再细分。图3.13中的小方域就是如此。若任一小方域只是部分满，则要再将它细分为4个小方域，继续细分部分满的小方域，直到结果是要么满，要么空，直至满足预定的分辨率为部分满的小方域，根据分辨率约定可以随意认为是满的或是空的。
图3.13 二维形体的四叉树描述
二维形体的四叉树描述是基于对形体所在的外接正方形递归地等分成4个正方形。这种分解一般是在显示屏幕空间进行的。分解过程所形成的一棵树不像二叉树，每个节点都有2个子孙，它的每个节点有4个子孙，除非到了叶节点。图3.13表示任意一个二维形体分解成的四叉树。首先对二维形体的外接正方形一分为四，如子正方形是空（没有形体在其中）或是满（完全充满了形体），则不需要对这类子正方形再作分解；如果一个子正方形部分地被形体占有，则需要对它再进行一分为四的分解，这样递归地分解下去，直到子正方形要么满，要么空，或已达到预先规定的分解精度。
四叉树的根节点表示整个形体所占的正方形区域。其叶节点表示不需要再分解的区域，这种区域的大小和位置与2的指数有关。从给定节点到根节点的递归分解深度取决于该节点在四叉树中的层次，也取次于该节点所代表区域的大小。设该树的高度为n，子正方形的最大数是2n×2n个。对于如图3.13所示的例子，n=3，由四叉树表示的精度可知，此例只需要33个节点而不是64个节点。用四叉树表示形体的精度取决于形体的大小、形体特征及其边界曲率。n的数值越大，精度越高，处理的时间越长，所需的存储空间就越大。将物体的模型简化为四叉树表示的过程也称为四叉树编码。
八叉树编码是四叉树编码的三维扩充。D.J.Meagher（1982）以八叉树编码为基础，开发了一种实体造型方法用于实体的高速操作、分析和计算机图像显示。他用空间中预先排序的八叉树来表示实体。这种方法也用到了只与物体的复杂性有线性增长关系的算法，该算法利用了树结构中的固有数据预先排序的优点。模型的八叉树编码过程与四叉树编码类似，就是将立方体区域递归细分成8个立方体区域（图3.14）。八叉树中，非叶节点的每个节点都有8个分枝。在图3.14所示的例子中，n=3。八叉树和四叉树编码方法对复杂物体的表示、分析和显示都提供了许多可能性。模型的所有计算都是以整数计算为基础的，也就是说，分析算法既快又适合于并行处理。对于平移、旋转和缩放八进制树模型，Meagher已经做过说明，即用布尔运算符将它们组合，并计算几何特性和进行干涉分析。这种灵活的方法提供了一些很有意义的工具，使得以其他技术为基础的系统能快速预处理或存储模型。
图3.14 三维实体的八叉树描述
空间分解法将物体分割成叫作体元（相当于二维图像元素pixels）的三维体积元素。采用此法时，如果直接将物体的空间细分成小的（分辨率）元素，则所需的存储量就十分庞大。例如，一个具有1000个体元的空间就要求100兆字节以上的存储容量，而每个体元只有1位。在许多工程应用场合，要得到合适的分辨率，起码要再增加1000倍的存储容量才行。空间分割系统认为在模型中最有意义的区域是在表面部分。因此，可以减少与表面无关的内外区域的存储容量。结果，所需的存储容量与表面积成正比，而与封闭的立方体体积无关。这样一来，在大多数情况下大大减少了存储容量。