实体建模技术研究进展

Research Progress of Solid Modeling Technology

摘要: 实体建模技术是当今科学和工程计算相关领域的重要研究内容。通过实体建模方法对物体外形进行恰当的描述，从而确定给定的计算区域，是科学与工程数值模拟计算的前提。此外，实体建模技术也是计算机图形学，计算机动画，科学计算可视化等领域相关应用实现的基础。本文系统回顾了当前各类主流实体建模方法，其后重点对隐式几何建模技术相关的理论和方法进行了阐述，分析了实体建模领域现在存在的问题和技术局限性，对未来该领域的发展趋势进行了展望。

Abstract: Solid modeling technology is an important research topic in the field of science and engineering computing. It is the premise of scientific and engineering numerical simulation to describe the shape of the object appropriately by solid modeling method, so as to determine the computational domain. In addition, solid modeling is also the foundation of applications in the fields such as computer graphics, computer animation and visualization in scientific computing. This paper reviews various current mainstream solid modeling methods, and focuses on the theories and approaches of implicit geometric modeling. We also analyze the existing problems and technical limitations of current solid modeling methodologies, and give the research prospect of this field.

1. 引言

实体建模技术是一门通过计算机软件和程序，设计相应的数据结构描述和表达物体几何外形，并生成相应几何模型的技术，其在机械动力学，地质勘探，航空航天以及生物医药等领域得到广泛的应用。根据几何外形的表达方式，常见的实体建模方法大致分为显式建模方法和隐式建模方法两种。如图1所示，显式实体建模方法往往通过网格 [1] 或者参数化曲线曲面 [2] 的方式描述模型区域的边界和内部形态，其采用的外形描述方式更加直接。与物体外形的显式表达方式相比，隐式建模方法往往通过定义隐函数的形式来间接表达区域的内部和外部 [3] [4] [5]，物体的表面边界为所定义隐函数的等值面 [6]。

Figure 1. The solids represented by explicit mesh (left) and implicit function (right)

图1. 显式网格(左)与隐函数表达的物体外形(右)

在面对不同应用时，实体外形的显式与隐式表达各有优劣。一方面，显式实体建模方法表达实体边界较为清晰，便于进行交互操作和可视化，近几十年来，在计算机辅助设计(Computer Aided Design, CAD)领域得到了巨大发展。另一方面，隐式几何模型对区域内外区分的良好特性使得隐式实体建模方法被广泛应用于三维点云等采样数据的曲面重建过程中 [7] [8]。与显示表达的几何模型相比，隐式表达几何模型对于碰撞检测和布尔运算等方面具有更好的鲁棒性 [9] [10] [11]。此外，在相关领域的运动界面捕捉过程中，采用隐式形式的边界面还能够适应物体外形界面和拓扑的复杂变化 [12]。

2. 常用实体建模方法

实体建模通过设计一系列数学和计算机准则描述和构建三维实体。相对于基于线框和表面的几何建模方法，实体建模技术更着重于保持几何实体模型的信息完整性，物理保真度和通用性 [13]。目前，在实体建模领域，最广泛采用的实体建模方法为边界表示法(Boundary Representation, B-rep)，构造实体几何法(Constructive Solid Geometry, CSG)和分解表示法(Decomposition Representation, D-rep)。

2.1. 边界表示法

边界表示法是当前CAD领域主要采用的实体建模方法，其以描述模型的表面边界为基础构建实体 [14]。如图2所示，在边界表示法中，每个实体由多个面闭合包裹形成，面与面之间由边相邻，边由点连接形成，面的边界为边构成的环，整个实体模型以“体–面–环–边–点”的方式组织起来。

Figure 2. The solid of boundary representation

图2. 边界表示法表达的实体

边界表示法需要定义相应的拓扑数据结构来组织点线面等几何元素之间的邻接关系。早期，Baumgart [15] 提出翼边数据结构(Winged-edge Structure)，通过指针记录每条边相关的两个邻接面，边顶点和该边邻接的其它边等信息来维护各个几何元素构成实体。Weiler [16] 设计了辐射边结构(Radial Edge Structure)，与翼边结构不同，辐射边数据结构为每条边构建了一个指针列表，每个指针指向一个单独的曲面。辐射边结构允许一条边关联两个以上的曲面，因此可以处理非流形结构的实体 [14]。边界表示法的主要优点是几何元素之间邻接关系可以充分利用，在模型设计过程中，设计人员可以通过调整点和边的形状和位置方便对模型进行局部操作。由于需要维持庞大而繁琐的数据结构，边界表示法在模型布尔运算过程中不仅需要更新几何信息，还需要更新拓扑信息，且曲面之间求交较为复杂，拓扑信息的更新也经常出现错误，使得模型的布尔运算过程缓慢且困难 [17]。

2.2. 构造实体几何法

构造实体几何方法根据集合论思想，首先定义简单形状的基本几何实体(Primitive)，通过基本几何实体之间的布尔运算完成更复杂实体构造 [18]。如图3，在构造实体几何方法中，每个实体由一颗二叉树表示，称之为构造实体几何树或CSG树(CSG Tree)，树的叶子结点为基本几何实体，中间结点为布尔运算符，实体根据CSG树从底向上构建 [19]。

Figure 3. The solid built by constructive solid geometry

图3. 构造实体几何法构建实体

构造实体几何法数据结构简洁，数据量较小并便于管理。在实体建模过程中，CSG方法可以利用简单的形体构建出极为复杂的实体形状，还可以通过几何外形设计构建更多的基本几何实体扩展构造实体几何方法对复杂实体的造型表达能力。通过改变基本几何实体的位置以及构造实体几何树存储的布尔运算符，可以轻松的完成对实体的修改。相对于边界表示法模型，通过点在各个基本几何实体内外的判断，CSG方法还能方便地判断点在实体区域的内外 [20]。由于隐式几何模型对于布尔运算具有很强的鲁棒性，构造实体几何方法在隐式实体建模过程中得到广泛的应用 [6]。

2.3. 分解表示法

根据需求，分解表示法通过空间划分的方法，将实体划分为规则或者不规则的简单几何形体的集合来表达空间中实体占据的区域，其不但能够方便地描述空间中具有有限边界的物体形状，而且可以有效表达内部有孔的复杂形体。目前，常见的实体分解表示方法有八叉树方法(Octree Method)和单元分解法(Cell Decomposition)。

1) 八叉树方法：如图4所示，八叉树方法不断将空间划分，然后采用树结构组织各个规则子空间描述物体几何外形。其原理首先计算物体所占区域的立方体包围盒，然后在每一步不断将叶子结点立方体区域等分成八个子立方体构建新的叶子结点，最终实体由与物体相交的叶子结点子立方体集合表示。八叉树表示物体的精度与树的最大深度有关，一般情况下，物体内部远离边界的子立方体体积较大，在边界附近的结点会不断细分以达到需求的精度 [21]。八叉树方法构造简单，适于进行实体之间的相交检测等运算，但是作为一种近似几何外形表示方法，对曲率较大的几何边界实现高精度的表示需要不断细分构建深层八叉树造成较大存储空间。

2) 单元分解法：如图5，单元分解法通过规则或者不规则的简单单元集合表达实体 [22]。一般情况下，采用规则单元构造实体较为容易，但是对物体边界表达不够精确。由于不规则单元对复杂边界的适应性，相应的单元集合可以更精确的描述实体的几何外形，在有限元等数值模拟计算领域得到广泛的应用 [23]。将实体区域分裂为边界一致的简单几何单元集合，也称为网格生成。虽然近几十年来研究人员在这方面做了大量研究，但是目前其仍然是一项复杂困难的工作 [24] [25]。

Figure 4. Octree space partition

图4. 八叉树空间划分

图5. 规则和不规则单元表达的实体

3. 隐式几何模型理论与应用

由于隐式几何外形表达相对于显式外形表达方法的诸多优点，近几十年来，不同领域的研究人员设计出各种隐式几何模型来解决计算机图形学与动画，工程计算等方面的相关问题 [26]。总体上，隐式几何模型的方法和应用主要为基于函数的隐式曲面造型方法和基于水平集方法的离散隐式几何模型两类。

3.1. 隐式曲面造型方法

在交互式图形学设计和计算机动画领域，随着计算机性能的不断提高，隐式几何造型方法得到越来越广泛的应用 [27]。相对于直接编辑显式网格和参数化曲线曲面，隐式曲面造型方法可以通过隐函数表示的各种曲面进行融合，创造出独特的外形和视觉效果 [28]。创建的隐式曲面造型方法大多基于骨架形式的隐式曲面 [29] (Skeleton-based Implicit Surface)，其隐式建模的基本几何实体(Primitive)是以点，线段或者多边形为骨架的隐式曲面 [30]。其中，blobby分子模型 [31] (Blobby Molecule)，柔性物体模型 [32] (Soft Objects)，元球模型 [33] (Meta-balls)和Blobby模型 [34] (Blobby model)是最常见的基于点骨架(Point Skeleton)构建实体的隐式曲面造型方法，其表达基本几何实体的隐函数为以点为中心的径向基函数。为了隐式曲面造型方法从点骨架推广到高维骨架，Bloomenthal [35] 提出卷积曲面(Convolution Surface)的概念，其构建实体模型的线和多边形骨架相当于所构建实体的中轴。

对于以点为骨架的隐式曲面，可以通过对点集的组织重建相应的隐式曲面 [36] [37] [38] [39] [40]。此外，研究人员也尝试按照类似CSG建模的方法，以树结构组织各个体元构建实体，并提供更多的算子实现更丰富的曲面造型效果 [41]。Wyvill [11] 提出BlobTree模型，作为对CSG树数据结构的拓展，在树中间结点可通过操作算子实现曲面的弯曲和混合等操作。Shapiro和Tsukanov [42] 提出通过定义R函数的方式，实现隐式实体之间的交并运算，并分析了R函数的微分特性。Gourmel [43] 等提出基于梯度的隐函数混合方法，可使得混合的隐式曲面之间过渡光滑，构建的隐式实体函数能保持 阶连续。

3.2. 基于水平集方法的隐式模型

水平集隐式几何模型广泛应用于科学和工程计算领域，其最初由Osher和Sethian [44] 提出并运用于运动界面追踪。最初设计的经典水平集模型定义在笛卡尔网格结构上，与显式网格追踪运动界面相比，水平集方法对运动边界的复杂拓扑变化具有非常良好的适用性。随后，Adalsteinsson和Sethian [45] 提出了窄带形式的水平集模型(Narrow Band Level Set Model)，其通过定义相应的数据结构，只记录并维护隐式边界两侧一小部分活动网格用于数值计算，大大减少了数值计算过程中的运算开销，隐式边界两侧活动的网格单元集合也被称为窄带。近十几年，越来越多的研究人员致力于水平集模型的结构优化。Losasso等 [46] 在八叉树网格上定义水平集模型，实现了多层次细节捕捉运动实体的外形并节省计算时间和空间开销。Museth [47] 设计了VDB数据结构(Volumetric Dynamic Grid with B+ Tree)，结合了DT网格 [48] (Dynamic Tubular Grid)和行程长度编码形式的水平集模型 [49] [50] (Run-length-encoding Level Set Model，RLE Level Set Model)，不但能够动态调整窄带内网格单元，实现窄带以外空间的紧凑存储，而且支持常量时间随机访问操作。Setaluri等 [51] 提出SPGrid网格结构(Sparse Paged Grid)，支持虚拟内存实现大规模高分辨率水平集模型的应用。

除了优化水平集模型结构减少存储开销，研究人员也尝试设计新的数据结构提高其几何外形的描述表达能力。Losasso等 [52] 在流体运动模拟过程中，通过水平集方法实现了多个运动界面追踪的算法。Heo and Ko [53] 提出在网格单元内增加插值点的方式，构造高阶多项式插值，在同样精度的网格上实现更高精度的Level Set方法。Mitchell [54] 提出通过在每个网格顶点上存储多个采样数值使得水平集模型能够实现非流形形式的几何外形表达，相对于传统水平集方法，其设计的水平集模型可以表达模型缝隙和重叠区域等特征。Dan等 [55] [56] 结合八叉树空间划分与多项式拟合技术，提出了一种多层次高阶多项式符号距离场生成算法，实现更少内存更精确描述复杂隐式几何外形。

4. 总结

目前，大量的实体建模技术应用到工程计算领域解决相关问题，相关的理论体系也较为完整。然而，在面对实际工程问题时，各种方法和理论有其各自的特点和局限性。综合实体建模领域的研究现状，该方向仍有广阔的发展前景。一方面，目前工程计算领域在前处理过程中广泛采用显式参数化曲线曲面等方式进行实体建模，曲面之间的布尔过程非常复杂，且没有形成统一的标准。在布尔运算错误出现缝隙和漏洞时，需要几何模型设计人员进行后续修补。设计鲁棒性更强，更规范的几何模型和布尔运算方法以应对计算机辅助设计和工程领域的相关需求十分必要。

另一方面，隐式几何外形表达曲面之间的布尔运算十分便捷，并能够适应模型几何外形变形过程中的拓扑变化，但是往往需要进行面网格生成转化为显式网格，或者采用直接体绘制的方法渲染成可视化图像，需要附加开销。作为一种科学和工程计算领域典型的隐式外形表达方法，水平集模型通常离散定义在网格结构上，模型表达的边界面为一个光滑的隐式曲面，其表达的精度受限于网格的精度，因此经常难以表达尖锐和窄薄的外形特征，在一定程度上会影响数值计算的准确程度。设计相应几何模型结构，以更小的开销表达更精确的几何外形，以及隐式几何模型的快速可视化方法也是隐式几何建模领域重要的研究方向。