三角面表描述的网格物体布尔运算模型

1、三角面表描述的网格物体布尔运算模型李瑞鑫，韩旭（武汉凯迪电力环保有限公司，武汉，430223）摘 要：自主开发三维造型系统，并通过对工程实际进行集成开发，实现关键设备的参数化与自动化建模。在此基础上，本文提出了一种三角面表描述的网格物体布尔运算模型。应用结果表明，该模型可靠性强、操作便捷，是实现布尔运算和创建复杂实体的有效方法，大大提高了工程设计效率和质量。关键词：三角面；网格物体；布尔运算中图分类号：Boolen operation model of mesh objects described by triangular face listRuixin Li, Xu Han(Wuhan K

2、aidi Electric Power Environmental Protection Co.,Ltd, Wuhan, 430223)Abstract: The 3D molding system, developed independently, implements parameterized and automatic modeling of main equipment by integrated developing for the project practice. On the basis of the developed system, a boolen operation

3、model of mesh objects described by triangular face list is proposed in this paper. Applied results show that the proposed model has some characteristics such as strong reliability and simple operation, the proposed model is an effective method for implementing boolen operation and creating complex e

4、ntity, the proposed model improves efficiency and quality of the project design greatly.Keywords: Triangular face; mesh object; boolen operation1 引言实体造型是以长方体、球体、圆柱体、圆锥体、拉伸体、旋转体等多种基本体素为单元元素，通过布尔集合运算，生成所需要的几何形体。这些形体具有完整的几何信息，是真实而唯一的三维物体。所以，实体造型包括两部分内容：即体素定义和描述，以及体素之间的布尔运算。实体的布尔运算是任何三维造型系统必不可少的组成部分，它完成

5、实体间的并集、差集和交集操作，是构造复杂实体的有效工具。作者自主开发的三维造型系统中，所有物体最终都采用一组基于顶点列表的三角面表进行边界描述。本文在总结开发工作的基础上，提出了一种三角面表描述的网格物体布尔运算模型，它完成实体的布尔操作，从而实现构造复杂的三维实体。2 网格物体布尔运算模型实体的布尔运算包括三个集合操作：并集（布尔加）、差集（布尔减）和交集（布尔乘），这里将它们分别记作+、-和*。已知两个物体A（图1-1）和B（图1-2），则它们之间的布尔运算规则定义如下：A+B = A与B的全部（图1-3）A-B = A中除去与B相交的部分（图1-4）A*B = A与B相交的部分（图1-5

6、） (图1-1 物体A)(图1-2 物体B)(图1-3 物体A+B)(图1-4 物体A-B)(图1-5 物体A*B)图1 两个物体之间的布尔运算规则定义这里，所有物体最终都采用一组基于顶点列表的三角面表进行边界描述，约定使用左手坐标系和顺时针顶点排列顺序，并采用左手规则定义三角面的法线方向。如图2-1所示，物体A由12个三角面对其边界进行网格化描述：顶点列表：VA = 0,1,2,3,4,5,6,7三角面表：FA = 012,023,765,754,326,367,104,145,037,074,215,256 (图2-1 A由12个三角面描述)(图2-2 B由144个三角面描述)图2 物体的

7、三角面表描述因此，三角面表描述的网格物体的布尔运算替代规则定义如下：A+B = A在B外部的三角面表 B在A外部的三角面表A-B = A在B外部的三角面表 B在A内部的三角面表-1A*B = A在B内部的三角面表 B在A内部的三角面表集合A在B外部/内部的三角面表表示一个A中每个三角面在B外部/内部的区域的三角剖分后形成的三角面表的集合S，即首先确定A中每个三角面在B外部/内部的区域，然后对该区域进行三角剖分，形成三角面表Si，再将每个Si中的所有三角面并入到S中。显然，集合S也是一个三角面表。如图3所示，765, 754, 326, 367, 104, 145, 037, 074, 215,

8、 256都在B外部，无需进行三角剖分，可以直接将它们并入S中；012和023在B外部的区域必须先进行三角剖分（图中虚线部分为012和023在B内部的区域），再将形成的三角面表Si分别并入S中。图3中，得到的S中共含有52个三角面。 图3 A在B外部的三角面表集合B在A内部的三角面表-1表示一个与B在A内部的三角面表所含的所有三角面相同但法线方向相反的三角面表。记号表示粘合操作，即把其前后两组不同的三角面表合并在一起，形成布尔运算后新物体的三角面表。本文约定：1）当求解A+B时，A在B外部的三角面表包含A中与B重合，并且法线方向相同的部分；2）当求解A-B时，A在B外部的三角面表包含A中与B重合

9、，并且法线方向相反的部分；3）当求解A*B时，A在B内部的三角面表包含A中与B重合，并且法线方向相同的部分。显然，三角面表描述的网格物体布尔运算模型实际上是一个过程模型，具体实现的关键在于寻找A在B外部/内部的三角面表。由于A和B本身由三角面表构成，因此，寻找A在B外部/内部的三角面表S被转化成寻找A中每个三角面在B外部/内部的区域，并将其三角剖分形成新的三角面表Si，再将每个Si中的所有三角面并入到三角面表S中。寻找A中三角面fai在B外部/内部的三角面表Si，其过程归纳如下：1）执行剖切：用fai所在平面剖切B，得到交线边表。2）检出环表：从交线边表中检出若干个环，形成环表。3）重组环表：

10、对环表执行包容性重组，创建使用树形结构描述的新环表。4）裁剪环表：用fai对树形环表执行裁剪操作。5）插入外环：将fai插入到树形环表中。6）三角剖分：对树形环表执行三角剖分，形成三角面表Si。2.1 执行剖切用fai所在平面pa剖切B，实际上等价于求解B中每个三角形和平面pa的交线，而剖切的结果是得到一组交线边表。因此，问题转化为求解三角形和平面相交的交线。如图4所示，三角形和平面共有6种相交构形：(a)三角形三个顶点都在平面上；(b)三角形两个顶点在平面外的同一侧，第三个顶点在平面上；(c)三角形两个顶点在平面外的不同侧，第三个顶点在平面上；(d)三角形两个顶点在平面上，第三个顶点在平面外

11、；(e)三角形三个顶点在平面外的同一侧；(f) 三角形两个顶点在平面外的同一侧，第三个顶点在平面外的另一侧。图4 三角形和平面的相交构形这里，构形(a)、(b)和(e)被认为三角形和平面不相交；构形(c)和(f)被认为三角形和平面相交；构形(d)比较特殊，涉及如何处理A与B重合的部分，根据前文约定，这里按如下情形处理：1）当求解A+B时，且正在求A在B外部的三角面表，如果三角形第三个顶点在平面的负半空间，则认为三角形和平面不相交；2）当求解A-B时，且正在求A在B外部的三角面表，如果三角形第三个顶点在平面的正半空间，则认为三角形和平面不相交；3）当求解A-B时，且正在求B在A内部的三角面表-1

12、，如果三角形第三个顶点在平面的负半空间，则认为三角形和平面不相交；4）当求解A*B时，且正在求A在B内部的三角面表，如果三角形第三个顶点在平面的正半空间，则认为三角形和平面不相交；5）当求解A*B时，且正在求B在A内部的三角面表，如果三角形第三个顶点在平面的负半空间，则认为三角形和平面不相交；6）其他情形，则认为三角形和平面相交。2.2 检出环表用fai所在平面pa剖切B，所产生的交线边表，实际描述一个封闭的边界，这个边界可能会存在多个封闭的内环和外环，但不可能发生自交现象（图5）。图5 交线边表描述的封闭边界从交线边表中检出封闭环的算法如下：1) 如果交线边表为空，算法结束；否则，转2）。2

13、）如果当前环为空环，则从交线边表中取出第一条边，并将该边的两个结点依次插入到当前环的结点列表中，同时将该边从交线边表中删除，转1）；否则，转3）。3）遍历交线边表，如果某一条边的一个结点与当前环的最后一个结点坐标相同，则将该边的另一个结点插入到当前环的结点列表末尾，同时将该边从交线边表中删除，转4）；否则，继续向后遍历交线边表。4）如果当前环为封闭环，即当前环的第一个结点和最后一个结点坐标相同，则将当前环插入到环表中，并置当前环为空环，即将当前环的结点列表清空，转1）；否则，转1）。2.3 重组环表从交线边表中检出封闭环后，还必须检测环表中的各个环之间的包含关系，从而确定由这些封闭环包围的区域

14、是对物体B执行剖切后形成的截面还是孔洞。显然，封闭环的包含关系可以用树形结构描述，树的根结点环为空，它的所有子结点环为封闭边界的最外层环。创建使用树形结构描述的新环表，重组算法如下：1）创建一个空环，做为树的根结点T插入树中。2）遍历环表，取出所有不被其它环包含的环，将这些最外层环做为根结点的子结点插入树中，同时将它们从环表中删除。3）遍历环表，如果某个环不被其它环包含，则确定树中包含此环的叶子结点，将此环作为该叶子结点的子结点插入树中，同时将此环从环表中删除。图5中，假设检出的封闭环序列为：0-1-2-3-4-5，则重组后的树形环表，按广度优先遍历序列为：T-1-4-5-0-2-3，按深度优

15、先遍历序列为：T-1-5-4-0-2-3，T位于第0层，1和4位于第1层，5、0和2位于第2层，3位于第3层（图6）。图6 重组后的树形环表由于环与环之间不存在相交，如果环的一个结点在另一个环之内，则可以判定此环被另一个环包含。判定一个结点是否在环之内，检测算法常用的有射线追踪法、夹角之和法。2.4 裁剪环表由于需要寻找的是三角面fai在B外部/内部的区域，而重组后的树形环表，描述的却是一个用fai所在平面pa剖切B后形成的封闭边界。因此，必须用三角环fai对树形环表执行裁剪操作，算法如下：1）按深度优先遍历树形环表，对除根结点环外的每个树结点环执行步骤2）至5）。2）通过循环反复线线求交测试

16、，找出当前树结点环各条边在三角环内的部分，将计算出来的这些零散新边插入一个临时边表中。3）类似步骤2），找出三角环各条边在当前树结点环内的部分，也将计算出来的这些零散新边插入临时边表中。4）至此，得到的临时边表描述的是一个用三角环裁剪后的边界，它是空环、退化环和封闭环中的一种。退化环将被当作空环处理；有效的封闭环按2.2节中的算法检出。5）如果裁剪后的边界是空环或退化环，则将当前树结点环及其所有子结点环都置为空环，然后继续按深度优先顺序处理它的兄弟结点环；否则，将由步骤4）检出的有效封闭环覆盖替代当前树结点环，然后继续按深度优先顺序处理它的子结点环。如图7所示，用三角环fai对图5中检出并经重

17、组的树形环表执行裁剪，操作后的结果是0、2和4在三角环fai外的部分被裁剪，3被完整保留下来，1和5在三角环fai外，被全部裁剪。图7中的虚线表示被裁剪的部分。图7 用三角环裁剪树形环表注意，裁剪后的树形环表中，仅仅是环的结点列表发生变化，而环的其他信息和树形层次关系保持不变。另外，裁剪后，环与环之间可能出现边重合即区域退化现象，在后面的三角剖分中，应该对其进行特殊预处理。2.5 插入外环树形环表中，位于奇数层的结点环，描述剖切B后形成的截面的外环；而位于偶数层的结点环，描述剖切B后形成的截面的内环即孔洞。而我们要寻找的是三角面fai在B外部/内部的区域，所以必须把三角环fai插入到环表中。插

18、入算法如下：1) 获取树形环表中处于最外层（层数最低）的有效封闭环（非空环）所在的层数ID。2）如果当前正在寻找三角面fai在B外部的区域，且层数ID为奇数，则用三角环fai覆盖替代根结点环T；如果当前正在寻找三角面fai在B内部的区域，且层数ID为偶数，则用三角环fai覆盖替代根结点环T；否则，执行NULL操作。图7中，如果当前正在寻找三角面fai在B外部的区域，则必须用三角环fai覆盖替代根结点环T；如果当前正在寻找三角面fai在B内部的区域，则执行NULL操作。2.6 三角剖分至此，树形环表中所有的有效封闭环（非空环），描述了三角面fai在B外部/内部的区域。这些有效封闭环，从（层数低的

19、）外层到（层数高的）内层，依次交替表示该区域的外环、内环、外环、内环、。图7中，如果当前正在寻找三角面fai在B外部的区域，则fai、0和2为区域的外环，4和3为区域的内环；如果当前正在寻找三角面fai在B内部的区域，则4和3为区域的外环，0和2为区域的内环。由于所有物体最终都采用一组基于顶点列表的三角面表进行边界描述，所以必须对这些含有孔洞的区域进行三角剖分。首先必须统一待剖分的含有孔洞的多边形的顶点编号方向，本文约定外环按逆时针方向、内环按顺时针方向。统一顶点编号方向的算法如下：1）结合平面pa的法线，判定环的当前顶点编号方向。2）如果当前环为外环，且环的方向为顺时针，则反转环的顶点列表；

20、如果当前环为内环，且环的方向为逆时针，则反转环的顶点列表；否则，执行NULL操作。如图8所示，统一顶点编号方向后的含有孔洞的多边形已不再有内环和外环之分。 (图8-1 三角面fai在B外部的区域)(图8-2 三角面fai在B内部的区域)图8 统一顶点编号后的多边形区域进行三角剖分之前，应该对可能出现的边重合即区域退化现象进行特殊预处理。这里，以图8-1为例，说明区域退化预处理的方法。1）生成一个对应多边形的有向边表EL1 = E01, E12, E20, E34, E45, E56, E67, E78, E89, E93, E1011, E1112, E1210, E1314, E1415,

21、E1516, E1617, E1718, E1813, E1920, E2021, E2122, E2219。2）将E01分割成E03、E313、E1314、E149、E91，将E20分割成E26、E612、E1210、E105、E50，将E56分割成E510、E1012、E126，将E93分割成E914、E1413、E133。3）剔除方向相反的重合边对：E313和E133、E1314和E1413、E149和E914、E612和E126、E1210和E1012、E105和E510。经上述预处理后，图8-1可用于三角剖分的多边形有向边表EL1 = E03, E91, E12, E26, E50,

22、 E34, E45, E67, E78, E89, E1011, E1112, E1210, E1314, E1415, E1516, E1617, E1718, E1813, E1920, E2021, E2122, E2219。同理，图8-2可用于三角剖分的多边形有向边表EL2 = E010, E151, E12, E23, E34, E48, E75, E56, E60, E89, E97, E1011, E1112, E1213, E1314, E1415, E1617, E1718, E1819, E1916。Delaunay三角剖分是对任意含有内孔的平面多边形进行三角剖分的有效方法

23、。这里，采用此方法进行多边形区域的三角剖分。Delaunay三角剖分实际上是从多边形区域中逐个剥离有效的Delaunay三角形，直至剩下的多边形区域本身已是三角形。Delaunay三角剖分算法如下：1）如果有向边表的边数为3，则多边形区域已是三角形，算法结束；否则，转2）。2）从有向边表中取出第一条边E0(V01,V02)，用它做为下一个即将从多边形区域中剥离的新三角形的基础边，并将E0从有向边表中删除，转3）。3）遍历有向边表中的每一条边Ei(Vi1,Vi2)，如果结点Vi2在E0的左边，且有向线段V02Vi2、Vi2V01和有向边表中其余各边都不存在相交，则将结点Vi2添加到候选结点列表中

24、；否则，继续向后遍历有向边表。4）从候选结点列表中找出与基础结点V01、V02形成的外接圆最小的结点，记为V03，则结点V01、V02和V03构成一个有效的Delaunay三角形，将它从多边形区域中剥离并添加到三角面表Si中，转5）。5）如果有向线段V02V03、V03V01都不在有向边表中，则向有向边表中添加有向边V03V02，并置下一个Delaunay三角形的基础边E0为有向边V01V03，转3）；如果有向线段V02V03（V03V01）在有向边表中，而有向线段V03V01（V02V03）不在有向边表中，则将有向边V02V03（V03V01）从有向边表中删除，并置下一个Delaunay三角

25、形的基础边E0为有向边V01V03（V03V02），转3）；否则，将有向边V02V03、V03V01从有向边表中删除，转1）。图9为图8对应多边形区域的Delaunay三角剖分。 (图9-1 三角面fai在B外部的区域)(图9-2 三角面fai在B内部的区域)图9 图8对应多边形区域的Delaunay三角剖分3 模型应用与推广作者自主开发的三维造型系统中，已经实现了本文提出的网格物体布尔运算模型，它不仅具备一般的三维建模和在线渲染能力，而且针对工程实际进行集成开发，实现了对关键设备参数化与自动化建模。该造型系统目前已经成功应用于200MW、300MW、600MW燃煤机组烟气脱硫工程。图10中的模型为使用该三维造型系统创建的某电厂脱硫系统的吸收塔，其建模过程多次使用了实体布尔运算操作。图10 某电厂脱硫系统的吸收塔模型实际上，本文的布尔运算模型不仅可以完成实体间的并集、差集和交集操作，它还可以推广应用于获取平面剖切截面和创建平面剖切体的三维操作。获取平面剖切截面，其实就是寻找平面在实体内部的区域，在完成执行剖切、检出环表和重组环表后，无须执行裁剪环表和插入外环，而直接对区域进行