海量空间数据环境下的三维实体布尔运算

海量空间数据环境下的三维实体布尔运算_地学三维可视化与

1.海量空间数据环境下的三维实体布尔运算研究现状

George Boole是英国的数学家，在1847年发明了处理二值之间关系的逻辑数学计算方法。在布尔代数学中，变量仅有0或1两种数值，布尔运算产生的结果取决于两个变量之间的逻辑关系，布尔运算包括取反、联合、相交、相减、异或等。布尔方法的产生促进了近代数学中构造几何学和集合论的产生和发展，并成为了电子计算机数值运算和逻辑运算的基础方法。随着近代计算机技术的飞速发展，布尔方法已经在机械制造业、计算机图形学、计算机辅助设计、广告、美术设计等各方面得到了广泛的应用。也是地质体可视化的重要手段之一。

实体布尔方法已被广泛应用于三维CAD和虚拟现实中，CSG（Constructive Solid Geometry）在图形处理操作中引用布尔逻辑运算方法使用简单的基本图形组合产生新的形体。实体交、并、差布尔运算是实体造型领域最为重要、最为复杂的问题之一，是实体造型中构造复杂实体的必要手段之一。

对于二维布尔运算，目前研究得比较多也比较广泛，也相对比较成熟，但对于三维空间的布尔运算，由于算法和计算量相对复杂，精度控制困难，所以一直研究比较少。Yvon Gardan和Estelle Perrin从理论上细致描述了三维布尔运算的降维方法，但其有很多局限性，比如对奇异问题以及精度问题没有解决。

实体布尔运算是三维矢量剪切算法应用到体与体之间时的特殊情况，目前文献中介绍的实体布尔算法都是基于降维、链环法等传统方法进行研究，算法复杂，难以应用到海量的空间数据中。作为商业三维建模软件必备的功能，无论是国际上具有代表性的几何造型软件，还是国内自主版权的几何造型系统，当处理海量数据模型或是模型相对复杂时都会不同程度地出现死机现象，或者出现孔洞等错误。稳定可靠的海量空间数据环境的3D布尔算法技术含量非常高，研发难度非常大。运用BSP树划分空间，可以提高处理海量数据的效率。

2.实体布尔运算原理及算法概述

1）布尔运算原理

一般的剪切都在点、线、面与体模型之间进行，当这种运算应用于两个体对象时，就被称为布尔运算。基本的操作包括反、交、并、差、异或等几种运算，其中反与交为两种基本运算，其他几种运算都是基于这两种运算进行的。如图6-21所示。

布尔运算的原理与体模型矢量剪切相同，区别在于布尔运算只是针对实体对象，以体A与B分别构建BSP树结构，对体B和A区分为“内”和“外”两部分，根据不同的运算要求对这些分区后的多边形重组为“体”对象，得到最终运算结果。而在剪切操作中，剪切对象和被剪对象可以为面对象，也可以为体对象。

2）算法描述

假设结果体S＝被运算体A＜OP＞运算体B；其中：＜OP＞表示并∪，交∩，差一运算；被运算体A分成Ain B和Aout B，运算体B分成Bin A和Bout A。

交运算：C＝A∩B＝B∩A；取Ain B和Bin A以及A∩B中的同法向部分（同向共面部分）。

图6-21 正方体（A）与圆锥体（B）布尔操作示意图

并运算：C＝A∪B＝B∪A；取Aout B和Bout A以及A∩B中的同法向部分。

差运算：C＝A－B＝A∩～B；取Aout B和Bin A以及A∩B中的反法向部分（反向共面部分）。

均衡差：AΔB＝（A－B）∪（B－A）；取Aout B和Bout A以及A∩B中的反法向部分。

根据以上分析可以看出，结果体不会产生新的平面，它上面的任何一个面要么是原A体的面，要么是原B体的面，除了法向可能相反外，平面的几何位置不变，只是平面的顶点序列发生变化。结果体中面的法向量与原体面的法向量同向或者反向。三维实体交、并、差布尔运算算法很多，大多是以正则集合理论为基础针对多面体的，它的主要工作及难点是运算结果的拓扑信息的重构。

交运算：

（1）利用包围盒判断法排除两物体不相交的情况

包围盒判断法可分为以下两步：

第一步，求出体A与体B各自的包围盒，比较包围盒是否相交。

第二步，如果上述条件不满足，需要将体A上的每一个面与体B进行相交判断，求出体A中面的最小值和最大值，如果用包围盒不能判断出面体的相交关系，则转到面面求交一一进行判断。

（2）面面求交求出交点和交边

（3）交边连接成环

以下简单介绍其步骤：

第一步，依次访问面上的各条边，统计各端点的度，这里的度是指一个顶点所连接的边数。

第二步，遍历各条边，删除度为1的顶点所连接的边，即删除悬挂边。

第三步，找到第一条没有被访问的边，记录边的两个端点。把边的始点作为起点，在未被访问的边中寻找与边的终点号相同的边，要求这两条边不共线并且三个点所围成的平面的法向量与原面的法向量同向，这样保证顶点的走向正确。

第四步，依次搜索面上的各条边，直到所有边都被访问。

（4）环组合成面

第一步，依次取Ringl的每个顶点判断点是否在Ring2组成的封闭区域内，程序中用射线法判断点是否在面内。

第二步，以同样的方式判断Ring2的每个顶点是否在Ringl组成的封闭区域内。

第三步，通过以上的判断，如果Ringl的每个顶点都在Ring2围成的封闭区域外，或者Ring2的每个顶点都在Ringl围成的封闭区域外，则把这两个环记作两个交面加入交面表中。

第四步，如果Ringl的每个顶点都在Ring2围成的封闭区域内，或者Ring2的每个顶点都在Ringl围成的封闭区域内，则用内外环连接算法把两个环连接成多个面加入交面表中。

（5）对两物体的交面进行判断分类

（6）面剖分成三角形

通过以上步骤得到的所有交面进行三角剖分，删除三点共线的面，所有的三角面组成体A与体B进行交运算后的结果体S。

两个实体的差运算可利用数学上的集合运算公式A－B＝A∩B～B，求出实体B的补集后利用实体求交算法求出；并运算则取A－B中在体A上的交面及B－A中在体B上的交面进行适当的处理后通过合并直接得出。

3）实体布尔运算流程

实体模型的布尔运算流程除了与体模型的剪切过程相同外，还增加了反、交、并、差、异或等几种运算规则，根据不同的需求生成相应的结果模型。流程如图6-22所示。

图6-22 三维实体模型布尔运算流程

3.基于BSP树的实体模型剪切算法

1）实体模型剪切原理

实体模型的剪切原理在模型输入、分解、重构各过程均与面剪切、面模型相同。由于体模型封闭性的要求，在完成了剪切模型对被剪切体模型的剪切操作后，还要用实体模型对面模型进行分解，保留位于体内部的面片，与剪切后的面片重构，生成新的封闭的体模型的几何形态。

2）实体模型剪切流程图

实体模型的矢量剪切运算主要包括剪切集选择、剪切对象构建、三角形内外测试、被剪三角形分解、剪切后模型重构、结果输出这六个步骤。剪切流程如图6-23所示。

图6-23 实体模型的矢量剪切流程

3）实体模型剪切类型

（1）面剪切实体

面剪体可以应用于地形、巷道、采区等面对象对矿体、地质体对象的剪切操作，面剪切体运算依据面对象的法线方向在空间中把被剪体对象分解为上下两部分，形成剪切后的两个体对象。比如在矿山模型的建立过程中，需要考虑矿体与巷道，露采模型与数字地形，露采边坡与生产道路之间各个方向的矢量剪切。如图6-24所示。

图6-24 面剪切体效果图

（2）体分解面

体分解面操作与面剪体不同的是依据体对象的法线方向在空间中把被剪面对象分解为相对于体对象的“内部”和“外部”两个对象。体分解面主要应用于地质切片、品位剖面等操作。如图6-25所示。

图6-25 体分解面效果图

4.基于B Rep模型的矢量剪切算法

从几何学角度看，矢量剪切可分X方向、Y方向、Z方向和任意方向剪切。其基本方法原理为：取出所有图形数据点，判断此点是在剪切面的哪一侧，保留在其中一侧的数据点，舍弃在另一侧的数据点；然后求出剪切面与所保留图形的交点，并将这些交点按照图形的拓扑关系形成相应的填充区。例如，矢量剪切平面方程为a·x＋b·y＋c·z＋d＝0，则a·x＋b·y＋c ·z＋d＜0和a·x＋b·y＋c·z＋d＞0分别代表了矢量剪切平面两侧的图形。一旦确定保留其中一侧，便同时舍去了另一侧。

实体矢量剪切的实现是B Rep模型（Boundary Replacement，边界代替法）和多种插值方法模拟而成的。所谓边界替代法即用实体的边界来代替实体，各边界的联系通过几何拓扑关系来建立。这种拓扑关系是实现矢量剪切的依据。图6-26中的单体是由四个曲表面和两个填充区端面围成，上、下曲表面为地层界面，左、右曲表面为断层面或相界面，前后填充区端面为沉积相在地震剖面上的形态。假如将此单体编号为d0，则可以将两个填充区端面编号为d0，四个曲表面编号分别为d0b1、d0b2、d0b3、d0b4。为了矢量剪切计算方便，规定上曲表面编号为d0b1，下曲表面编号为d0b2，左曲表面编号为d0b3，右曲表面编号为d0b4。当矢量剪切面裁剪到此单体时，可让计算机按上述方法原理分别对它与各面的相交情况进行判断，求解出边界交点，再保存交点的空间数据及属性数据，舍弃相应的图形，然后将按交点的上下左右关系形成剪切后的填充区。有多个单体时，可以根据单体的编号（如d0）来区分各单体的交点，分别形成对应的填充区，并赋予相应的属性，这样就保存了原来的拓扑关系。

图6-26 实体的空间拓扑关系

5.基于三维BSP树的多面体布尔运算算法

1）BSP树空间分区原理

BSP树就是用来对N维空间中的元素进行排序和查找的二叉树。用它来划分整个空间时，树中的任意一个节点表示一个凸的子空间。每个节点包含一个“超平面”，将这个节点表示的空间分割成两个子空间。每个节点除了保存其两个子节点的引用以外，还可以保存一个或多个元素。对于N维空间，超平面为N－1维的对象。通常，用BSP树来表示二维或者三维空间，这时，空间中的元素分别指的是线段和多边形。

2）用BSP树对模型进行切割

BSP树建立后，用BSP树对任意模型进行切分。这里以切割一个三角形为例进行说明。目标是把一个三角形分割成在模型内部和在模型外部的两部分，当然这个模型现在已经被表示成BSP树了。首先，与根结点的超平面进行比较。如果在超平面前，则和左子树的超平面继续比较，如果在超平面后，则和右子树的超平面继续比较，直至叶子结点。由叶子结点来决定该三角形是在模型的内部或外部。如果三角形在叶子结点的前面，那么该三角形就在模型的外部，否则就在模型的内部。当然，这是最简单的情况，三角形在比较的过程中没有被分割。如果三角形与超平面相交，就需要用超平面将其分割成两个或三个三角形。分割后三角形加入到待处理序列中去，等待被处理。对于三角形和超平面的相交情况，三角形被分割了，分割后的三角形被加入到待处理序列中去，所以说待处理的三角形数量在不断变化。这样以来就很难分析它的时间和空间复杂度。

3）算法描述

实体布尔运算是计算机图形学运算数学方法，通过对实体模型进行交、差、并来逼近实体模型实际空间形态的一种边界切割取舍的方法。在复杂实体建模中需要进行实体模型的布尔运算，通过这种切割取舍运算，还原实际空间上相切的不同地质实体的空间关系。布尔运算能够使不同实体间的吻合空间关系表现得淋漓尽致。在许多算法中，布尔操作不仅仅能展现多面体对象之间的运算结果，还能提供一种方法来描述对象的物理处理过程。如在机械加工过程中，可以用集合运算的不同结果来检验刀具和夹具之间的碰撞，以验证设计结果的正确性。

假设多面体存储在顶点 边 面表中，并且面的顶点是有序的，使得面的法线对应于顶点的逆时针方向，其本质为封闭的不规则三角网。在图形学中，空间的相对位置是以图形对象的法线来判定的，根据法线方向相应地分为法线正向和负向两部分。

多面体的布尔运算包括多面体的反、交、差、异或。其中，反运算和交运算是基础运算，其他的运算可用它们来表示。一个多面体P的反表示为⇁P，而多面体P和多面体Q的交表示为P∩Q。多面体的并为P∪Q＝⇁（⇁P∩⇁Q），多面体的差为P－Q＝P∩⇁Q，而多面体的异或为P⊕Q＝⇁（（⇁（P∩⇁Q））∩（⇁（Q∩⇁P）））。所以，布尔运算最小的编码方法是：首先实现反和交，然后根据这两种运算来实现其他的运算。

（1）反运算

多面体的反运算即改变多面体内部和外部标识。若系统底层采用结构面顶点访问顺序而隐式定义法线方向的方法，则直接转换结构面上顶点的顺序，用右手准则可以判定出得到的法线方向指向相反的一侧；若对象底层定义了法线方向，则可以直接将法线向量乘以－1使其反向。反运算虽然处理起来比较简单，但它作为布尔运算的基础运算之一，直接影响并、差、异或运算的正确性。实现过程伪码为：

Polyhedron Negation（Polyhedron P）

｛

Polyhedron negate P；

Negate P．vertices＝P．vertices；

Negate P．edges＝P．edges；

for（each face F of P）

｛

／／反转每个面的顶点的次序

Face F’；

for（i＝0；i＜F．num Vertices；i＋＋）

F’．Insert Index（F．num Vertices–i–1）；

Negate P．faces．Insert（F’）；

｝

return negate P；

｝

（2）交运算

多面体的交运算即获取两个输入多面体共同包围的的子多面体。如果多面体对象A和B在空间相交，则在交线位置将每个对象分为内外两部分，A对象位于B对象内部的一部分，以及B对象位于A对象内部的一部分，组合成新的多面体对象，就是两个多面体交运算的结果。如果两对象在空间中并不是几何相交，那么交运算的结果就是空对象，伪码如下：

Polyhedron Intersection（Polyhedron P，Polyhedron Q）

｛

Polyhedron intersect PQ；

for（each face F of P）

｛

／／用Q树分解F每一个结构面

Get Partition（Q．bsptree，F，inside，outside，coinside，cooutside）；

for（each face S in（inside or coinside））

intersect PQ．faces．Insert（S）；

｝

for（each face F of Q）

｛

／／用P树分解Q每一个结构面

Get Partition（P．bsptree，F，inside，outside，coinside，cooutside）；

for（each face S in（inside or coinside））

intersect PQ．faces．Insert（S）；

｝

｝

这种方法的核心是通过将多面体的每一个面F与另一个多面体的相交来对其分区，即通过BSP树结构，将多边形分解为正负两个区域，算法中最复杂的部分是处理当多边形与分区平面重合时的情形，在这种情况下，问题可以简化为计算二维多边形的相交和差。

（3）并运算

多面体的并运算与交运算不同的是，并运算将多面体对象A和B相对于彼此的外部对象组合成新对象，也就是说，并运算结果的内部区域是原来两个体的内部区域的联合。如果两对象在空间中并不是几何相交，那么并运算的结果本质上就是两对象直接组合的结果。伪码如下：

Polyhedron Union（Polyhedron P，Polyhedron Q）

｛

return Negation（Intersection（Negation（P），Negation（Q））；

｝

（4）差运算

多面体的差运算，即计算包含在第一个输入的多面体之内，而不包含于第二个输入的多面体之内的多面体。两个多面体的差运算结果是一个实体，其内部区域是原来两个体的内部区域的差。伪码如下：

Polyhedron Difference（Polyhedron P，Polyhedron Q）

｛

return Intersection（P，Negation（Q））；

｝

（5）异或运算

多面体的异或运算即计算这两个多面体的差的并。两个多面体的异或运算结果是一个实体，其内部区域是原来两个体的差的并。伪码如下：

Polyhedron Exclusive Or（Polyhedron P，Polyhedron Q）｛

return Union（Difference（P，Q），Difference（Q，P））；

｝

4）实验测试与结果分析

（1）实体集合交运算

打开数据模型，选中所要分析的实体集。如图6-27所示，选择某地层实体和隧道实体。

图6-27 布尔运算前的地层实体与隧道实体

对两实体进行交运算后，获取地层实体与隧道实体的交集，其运算效果如图6-28所示。它显示了隧道在该地层中的空间实体形态，为分析隧道遇地层情况以及进行隧道设计提供了直观的模型依据。

（2）实体集合并运算

图6-28 地层实体与隧道实体的集合交运算效果

针对图6-27中的地层实体与隧道实体进行并运算，其运算效果如图6-29所示。它展示了地层实体与隧道实体共同占据的空间实体形态。

图6-29 地层实体与隧道实体的集合并运算效果

（3）实体集合差运算

针对图6-27中的地层实体与隧道实体进行集合差运算，其运算效果如图6-30所示。它展示了地层实体被隧道实体刻挖后的空间实体形态。与此类似，也可用隧道实体与地层实体进行集合差运算，获取隧道实体被地层刻挖后的空间实体形态。

（4）实体集合均衡差（异或）运算

图6-30 地层实体与隧道实体的集合差运算效果（地层实体 隧道实体）

打开数据模型，选中所要分析的实体集。根据需要，选择均衡差运算对象。如图6-31所示，选择两个地层实体（注：此处为了突出运算结果的可视化效果，将图中的上层地层实体以线条方式显示，并与下层地层实体有部分重合区域）。

图6-31 布尔运算前的两个地层实体

对两实体进行异或运算后，其实体均衡差运算效果如图6-32所示，它展示了两个地层实体异或运算后的空间实体形态。

6.小结

在三维建模中，复杂实体往往不能一次生成，一般都是由相对简单的多个实体通过并（Union）、求差（Subtract）和求交（Intersect）的布尔运算，对它们进行组合，最终形成用户需要的实体。实体间的布尔运算是三维软件必备的功能之一，作为一种通用的计算几何算法应用于商业的CAD、CAM和GIS分析中。

图6-32 两个地层实体的均衡差运算效果

基于BSP树的海量数据的实体布尔运算算法具有高效、准确、健壮的特点。将该方法应用到三维地学建模中，探索一种基于此算法的复杂地质体模型重构技术方法，可以非常好地解决基于复杂边界约束下模型的快速重构问题。利用实体间的布尔运算功能，可以快速、精确地生成含夹层、断层、透镜体等不能用传统方法生成的三维地质体模型，并且还可以实现任意形状实体模型在任意空间位置的真三维工程量扣减计算，彻底解决错层工程量快速准确计算的问题。三维实体布尔运算扣减算法速度快，零误差，可以快速准确地计算任意建筑结构的工程量。