面向流形和非流形网格模型的高效切片方法

吴 婷，张礼兵

(嘉兴学院 信息科学与工程学院，浙江 嘉兴 314001)

0 引言

三角网格模型是一种采用大量三角片模拟复杂物体表面的三维几何模型。描述三角网格模型的STL(standard template library)文件因其数据格式简单、占用储存空间少，已成为3D打印系统的一类标准接口文件格式，它能够满足模型信息在不同软件系统之间高效、及时传输的需求[1]。在对STL模型进行3D打印时，分层切片处理是首要且最为关键的一步，它通过层切平面与三维模型相交，得到各层切片轮廓信息[2]。由于切片处理需要计算每层切平面与三角片的交线，大量三角片会影响创建切片轮廓的时间，切片算法的有效性直接影响了最终模型制作的效率和质量。

目前，现有切片算法和商业软件都主要针对流形网格模型，即模型封闭且无自交，不存在法向量错误、相邻面片不共顶点、顶点分离、重叠面片和孤立面片等网格模型常见错误[3]。然而，在实际应用中，从三维扫描仪、CT和MRI等设备构建出来的STL模型，通常含有孔洞、悬边、悬面、自交等情况。将CAD软件绘制的3D模型转换为STL模型时，也容易出现三角片重叠、拓扑连接信息重复或相邻面片法向不相容等情况[4]。虽然一些逆向工程软件能够自动修复不正确法矢、重叠三角片、孔洞裂缝等简单错误，但对于一些复杂的非流形三角片则无法进行修复。如果直接用传统流形网格的切片算法处理非流形网格，会导致难以修复的错误结果。因此，研究适用于流形网格和非流形网格模型的切片处理算法，对于提高分层切片处理的有效性和鲁棒性具有重要意义。

1 相关工作

STL模型文件记录了每个三角片的顶点和法矢信息，因此对STL模型进行切片，需首先根据顶点坐标判断三角片与各层切平面的相交关系，然后计算出切平面与三角片的交线段，并将这些交线段连接成有序轮廓，如图1所示。根据STL模型的复杂性，切片算法具体可分为基于流形网格的算法和基于非流形网格的算法两种情况。

1.1 流形网格模型切片算法

流形网格模型一般需满足两个条件：①每一条网格边只被两个三角面片所共享；②与每一个顶点相邻接的边和面构成一个且只能构成一个围绕该顶点的“环”。一个网格表面是流形(manifold)的，当且仅当它所有的边和顶点都是流形的，否则为非流形(non-manifold)的[5]，如图2所示。

尽管流形网格模型中三角片之间拓扑连接紧密，但在STL文件中三角片的存储顺序却是杂乱无章的，因此要想获得有序的切片轮廓，关键在于如何将切平面与这些散乱的三角片形成的交线段有序地组织起来。目前已有的基于流形网格的切片算法中，应用最广泛的有以下两种类型：

(1)基于冗余交点信息的切片算法 该类算法首先计算出切平面与所有三角片的交线段，由于相邻三角片之间存在公共边，因此这些交线段的端点存在重复，利用这些重复冗余的交点信息即可确定三角片之间的邻接关系，将交点依次首尾连接即可得到有序封闭轮廓[6-8]，如图3所示。田仁强等[9]首先采用二分查找法进行切平面与相交三角片的快速分组，然后在计算出交线段后，利用深度优先搜索算法将这些散乱交线段连成有序封闭轮廓。MINETTO等[10]将相交线段端点间的邻接关系建立成哈希表，利用哈希表的快速查询功能将这些交线段构成有序轮廓，从而极大提高了切片算法的执行时间。这种类型的算法无需构建复杂的网格拓扑关系，但在计算切平面和三角片公共边的交点时会重复计算两次。

(2)基于网格拓扑信息的切片算法 该类算法需要首先建立STL模型三角片之间的邻接拓扑关系，然后在求得切平面与第一个相交三角片后，根据拓扑关系找到与之相邻的下一个三角片，依次求交后即可得到首尾相连的有向封闭轮廓[11-12]。这种算法能够避免重复计算冗余交点，而且无需对交点进行重新排序。但如果建立整个网格的拓扑关系，分层算法处理拓扑信息耗时较长、内存占用量较大，尤其是在处理数据量较大的STL文件时，将十分费时且对计算机的计算能力要求更高[13]。王素等[14]根据三角片各点坐标在切平面方向上投影的最大值和最小值反求与此三角片相交的切平面，并通过分析相邻两个三角片公共边与切平面的位置关系, 按邻接顺序建立交点链表，该算法不进行整体拓扑信息的提取和三角片的分组排序，只需读取一次信息即可建立有序的交点链表。徐敬华等[3,15]利用半边数据结构[16]建立每层相交三角面片集合的局部邻接拓扑关系，通过哈希链表递归遍历求解每一个三角面片的邻接面片，最后依次求解这些面片间的公共边与切平面的交点以获得有序轮廓交点集，如图4所示。ZHANG等[17]根据STL文件中三角片顶点的存储顺序和坐标值确定出每个三角片与切平面相交的“前驱边”和“后继边”，并由此建立了三角片之间的邻接关系链表，依次计算链表中每个三角片的前驱边和切平面的交点即可得到有序的封闭轮廓，该算法不仅可以避免冗余交点的重复计算和交点排序，还能够自动识别内外轮廓。

1.2 非流形网格模型切片算法

与流形网格相比，非流形网格模型中三角片的拓扑关系更为复杂，通常表现为一个网格边被两个以上的三角片共享。因此，若用传统方法对非流形网格进行切片，由于在公共边处无法分辨分支走向，会造成轮廓排序混乱。针对这一问题，MCMAINS等[18]将非流形三角片的法矢投影到与非流形边垂直的平面上，根据法矢投影的指向来构建相邻三角片的邻接关系，以此构建正确的封闭轮廓，但该方法无法处理大量非流形边汇聚相交的问题。HUANG等[19]通过分析模型上的每个公共边所共享三角片的数量，将每条边的属性进行标记，然后在计算切平面与边的交点时，若遇到非流形边，找到与该边相邻的下一个非流形边进行求交，直到计算完成所有边与切平面的交点。该方法对于模型上的裂缝能够产生较好的效果，但当多个三角形共享一条边时，求得的交线容易出现绕行，从而无法产生正确的封闭区域。巢海远等[20]针对非封闭网格，首先建立点边面的拓扑连接关系，并利用边界判断规则提取所有边界边，然后在计算切平面与所有三角片的交点后，从含有边界边的三角片开始，按照邻接关系依次连接交点以获得非封闭的切片轮廓，由于这种方法需要建立整个网格的拓扑关系和边界边索引，因此切片效率较低。

可以看出，现阶段关于流形网格模型切片算法的研究较多，而对非流形网格模型的切片算法还没有形成一套完善的体系。目前切片算法主要存在两个需要解决的问题：①如何避免耗时耗空间的邻接拓扑关系的建立，并将散乱的交线段排列成有序轮廓，关系到整个算法的效率;②无论是流形网格还是非流形网格，都有可能产生切片轮廓的奇异问题，传统单一的轮廓跟踪或摄动法[21]无法解决多个轮廓的自交，也不能去除多余轮廓分支，因此建立有效的奇异问题解决方法尤为重要。

针对上述挑战和问题，本文提出一种面向流形和非流形网格模型的高效切片算法，该方法将三角片和切平面的相交关系映射成无向图，利用图的节点度特性判断切片轮廓的封闭性和复杂性，并基于图论的路径规划技术进行轮廓构建，以解决切片轮廓的排序和自交问题。

2 本文方法

本文提出的面向流形和非流形网格模型的高效切片算法主要包括数据预处理、相交边提取、无向图构建、轮廓路径规划4个部分，算法整体框架如图5所示。首先对输入的模型进行预处理，使模型数据满足正则性和有序性要求；其次，根据三角片与切平面的关系提取每层的相交边集合，并将相交边关系映射为无向图；最后利用图的节点度特性判断切片轮廓的封闭性和自交性，并基于路径规划技术对不同类型轮廓进行拓扑排序。

2.1 数据预处理

为保证切片算法的有效性和准确性，首先应对输入的STL模型进行合法性检查，修复模型的拓扑错误，使模型为正则三角网格模型[4]，即模型无悬面、无重叠等错误。

修复STL模型后，由于模型三角片的存储顺序是散乱的，为提高分层切片处理速度，需根据三角片的顶点坐标对三角片数据进行排序优化，以加快筛选出与各层切平面相交的三角片集合。

不失一般性，设层切平面垂直于z轴。根据成型精度和模型表面形态特征，首先确定各层切平面的位置hi,i=1, 2, …,n，n为切片总数；然后获取模型上每个三角片的3个顶点坐标vmin(x1,y1,zmin)，vmed(x2,y2,zmed)，vmax(x3,y3,zmax)，其中，zmin、zmed、zmax分别为3个顶点z轴坐标的最小值、中间值和最大值。由图6可知，对于第i层切平面hi，当zmin≤hi≤zmax时，该三角片与当前层切平面hi相交。因此，将模型三角片序列中每个三角片的3个顶点按z轴坐标最小值zmin、中间值zmed和最大值zmax的顺序进行排序；然后对所有的三角片按z轴坐标最小值进行升序排序，即z轴坐标最小值zmin更小的三角片排在前面。

2.2 相交边提取

当模型的三角片序列按照从低到高排序后，对于高度为hi的切平面，若某个三角片的zmin>hi, 则排在其后的三角片都不会与该切平面相交, 无需再进行相交计算。因此，查找三角片序列中最后一个满足zmin≤hi的三角片索引号j，提取出前j个三角片，然后在前j个三角片中比较每个三角片的zmax和hi大小，若有zmax

对于任意一层切平面筛选出的相交三角片集合，切平面均与集合中每个三角片的两条边相交。为了快速计算出交点坐标，将三角片的每条边用该边的两个顶点vi、vj表示为，当某个顶点vi与切平面在z轴方向的距离小于容差ε(例如，ε=10-5)时，则认为该顶点vi在切平面上，将其相交边修改为。

提取出每个三角片与切平面相交的两条边e1、e2后，将其构建成一个相交边对：[e1,e2]。根据当前切片面hi与三角片3个顶点z轴坐标zmin、zmed、zmax的关系，相交边对分为如下几种情况：

(1)当zmin

当hi

相交边对：[，]；

当hi=zmed，

相交边对：[，]；

当hi>zmed，

相交边对：[，]。

(2)当zmed=zmin=hi且zmax>hi, 如图7b所示:

相交边对：[，]。

(3)当zmed=zmax=hi且zmin

相交边对：[，]。

(4)其他。

无相交边。

以如图8所示情况为例，切平面hi与各三角面片Fj(j=1,2,…,7)产生的相交边如表1所示，其中三角片F6与切平面只有一个交点，故无相交边对。因此，最终得到的有效相交边集合为： {[e1,e2],[e3,e4],…,[e11,e12]}。

表1 图8所对应的相交边信息

2.3 构建相交边无向图

由于每个三角片的两条边与切平面产生交点，交点连线构成交线段，可以将这两条边映射为节点，交线段映射为节点间的边，将所有三角片与切平面形成的交线段都这样映射后，就可以得到一个无向图。具体步骤为：

步骤1将所有三角片的相交边对组成集合：

V0={[e1,e2],[e3,e4],…,[e2s-1,e2s]}，

式中s为相交三角片总数。

步骤2将集合V0中的每条边当做节点，对节点进行冗余过滤，建立不含冗余节点的集合：

V={ei|ei≠ej(i≠j)}。

将集合V中的节点对应回原集合V0，求得索引向量id，使V0=V(id)。

步骤3根据集合V0中每两条边构成边对的关系，建立边集：

步骤4利用集合V和边集E，构建无向图G= (V,E)。

步骤5对图G中的边进行精简，删除重复的边。

以如图9a所示的切平面与三角片相交情况为例，按照所述方法，提取的相交边对集合V0={[e1,e2],[e3,e4],…,[e11,e12]}，由于e2=e9,e3=e10,e4=e5,e6=e7=e11,e8=e12，对V0进行冗余过滤后得到集合V= {e1,e2,e3,e4,e6,e8}，然后根据V0中每两个节点构成边对的关系，得到边集E={[e1,e2], [e2,e3], [e3,e4], [e4,e6], [e6,e8], [e6,e8]}，利用V和E构建的无向图G如图9b所示，因为图9a中有两个三角片与切平面产生的交线段重合，导致边集E中的边对[e6,e8]重复记录了两次，所以需对图G中的边集E进行精简，删除重复的边，最终结果如图9c所示。

2.4 轮廓路径规划

通过建立相交边无向图的数据结构, 可将相交边的拓扑排序问题转化为基于图论的路径规划问题。根据模型的复杂性，每层切片有可能产生多条轮廓，每条轮廓还可能出现封闭、不封闭、自交等问题。为使算法具有较高的鲁棒性，本文首先计算无向图G的极大连通子图Gg，g=1, 2, …,k，k为连通分量总数，根据每个连通子图Gg中节点度的分布特性，对不同类型图采用不同方法进行拓扑排序，以得到正确有序切片轮廓，整个技术路线如图10所示。

节点度是指在一个图中与该节点关联的节点个数总和[22]。设D(Gg)为连通子图Gg中所有节点的节点度集合，根据D(Gg)的分布特性，可将连通子图Gg分为如图11所示的3种类型。

如图11a所示，这种类型的连通图中所有节点度均为2，其所对应的切片轮廓为简单封闭环。对于这种轮廓的拓扑排序，可以将任意一个节点作为起点e1，然后从起点e1出发，按照深度优先遍历[23]搜索与它关联的邻接节点e2，再从节点e2出发，搜索与e2邻接且未被访问过的节点e3，依次进行搜索，直到回到起点e1。例如图11a所示的连通图，以节点1开始，按照深度优先遍历得到的有序封闭轮廓路径为：1→2→3→4→5→1。节点排列顺序确定后，依次计算节点对应的相交边和切平面的交点坐标即可得到有序轮廓交点集。

如图11b所示，这种类型的连通图，除首末节点的度等于1外，其余节点的度均为2，其所对应的切片形状为非封闭的开轮廓。对于这种轮廓的拓扑排序，首先找到图中节点度为1的节点，将其作为首节点e1，然后按照深度优先遍历搜索与它关联的邻接节点，直到遍历完全部的节点，即创建一条有序开轮廓。图11b所示的开轮廓中，只有节点2和节点3的度数为1，按照存储顺序，节点2在节点3之前，因此以节点2为起点进行深度优先排序，结果为2→1→5→4→3。

如图11c所示，这种类型的连通图存在度大于2的节点，如节点1、节点3和节点5，说明在该层切片位置，模型可能具有非流形边，从而导致轮廓存在自交问题。对于该类型的节点拓扑排序，需找到图中的割点，将图分解为简单连通图。所谓割点，是指在一个图中去掉一个节点，同时去掉与该点相关联的所有边后，该图的连通分量数增加，则称该节点为割点[24]。割点的节点度通常大于2，因为它是多个轮廓汇聚的关节点，利用Tarjan算法[25]可以找到图的割点，并将图分解为多个双联通子图，每个双联通子图不存在割点，从而有利于后续的节点排序，避免轮廓绕行。

根据上述分析，本文提出递归双连通分解法来解决复杂自交轮廓的排序问题，整个流程如图12所示。其基本思想为：首先计算连通图Gg的双连通子图，若双连通子图的个数为1，即不存在割点，则直接利用双连通子图的节点建立凸包，根据凸包确定轮廓路径的起始边，然后进行路径跟踪，当构成一条有序封闭轮廓路径后，再将剩余节点集组成新图后继续进行分解；若双连通子图的个数不为1，则计算每个双连通子图节点度：若节点度都为2，则利用深度优先遍历构建轮廓路径，若某个双连通子图存在度大于2的节点，则利用上述基于凸包的方法进行轮廓跟踪。

具体步骤如下：

步骤1计算连通图Gg中每个节点对应的相交边与切平面的交点，将交点坐标作为图中的节点坐标。

步骤2计算连通图Gg的极大双连通子图，若双连通子图的个数大于1，则对每个双连通子图Ggg循环执行步骤3；若双连通子图的个数等于1，则转步骤4。

步骤3判断双连通子图Ggg中节点度的分布：①当所有节点的度都等于2时，即D(Ggg)=2，利用深度优先遍历获得该连通域内的有序切片轮廓；②当节点度范围D(Ggg)≤2时，则为多余轮廓分支，不进行该连通域内轮廓路径的创建；③当存在度大于2的节点时，即D(Ggg) ≥2，则转步骤4。

步骤4利用双连通子图Ggg= (Vgg，Egg)的节点集Vgg的节点坐标计算凸包，凸包按逆时针方向排序，然后在凸包边界边上找到属于双连通子图Ggg边集Egg的一条边，并将其作为切片轮廓路径的起始边s1s2(起始边的第1个节点为s1，第2个节点为s2)，在子图Ggg中搜索与s2关联且未被使用的邻接点作为下一个路径点s3，若当前节点有多个邻接点，为使沿逆时针路径方向物体内部区域始终在路径的左边，应选择最右拐的节点作为下一个路径点，依次遍历求出路径点，直到回到起点s1，则完成一条有序切片轮廓路径P的创建，同时记录路径P中的割点SP。

步骤5提取剩余节点Vgg-P+SP，组成新图Ggg后，转步骤3，以完成剩余轮廓路径的创建。

以图13所示为例，说明本文方法对自交切片轮廓进行路径规划的过程。由于该连通图中存在节点度大于2的节点，首先对该连通图进行双连通分解，得到5个双连通子图。其中，前4个双连通子图中节点度都为2，利用深度优先遍历即可构建有序封闭轮廓路径；第5个双连通子图中存在节点度大于2的点，因此首先计算凸包，然后从凸包上找到属于该双连通子图边集上的一条边作为起始边s，从起始边s开始逆时针跟踪最右拐的点，构建一条封闭轮廓路径后，再对剩余节点进行路径搜索，从而得到所有的有序轮廓。

3 实验

为验证本文算法的有效性，以不同类型的STL模型为例, 进行分层切片测试。在Windows 10环境下利用MATLAB开发基于本文算法的分层切片程序，实验在2.4 GHz的CPU、8 GB内存的PC机上运行。

实验1如图14和图15所示为带有复杂孔洞结构的流形网格模型进行分层切片的效果图。利用这些模型进行实验能够表现算法处理复杂嵌套轮廓的能力。如图14a所示为一个具有1 194 952个三角片的镂空灯罩模型，为显示清晰，图14b所示为层厚2 mm的切片效果，该模型在顶层具有28个轮廓环，其所构成的连通域如图14c所示。图15a所示为一个具有96 364个三角片的扇子模型，图15b所示为层厚1 mm的切片效果，该模型的每一层切片上具有474个轮廓环，其所构成的连通域如图15c所示。可以看出，本文方法对具有复杂孔洞结构的模型均能够产生正确的切片结果。

利用本文方法和著名的Cura切片软件对这两种模型在不同切片厚度下的切片效率进行对比，结果如表2所示。对于第1个灯罩模型，在同样的切片厚度参数下，本文方法比Cura软件在耗时方面节省了近6%。对于第2个扇子模型，本文方法比Cura软件在耗时方面节省了近80%，这主要是因为灯罩模型中每层切片最多的只有28个轮廓环，而扇子模型的每层切片包含474个轮廓环，所以当处理大型嵌套轮廓时，本文方法比Cura软件更高效。

本文方法对于这两种模型在不同层厚下，各层切片从相交边提取到轮廓路径规划的执行时间如图16和图17所示。可以看出，对于灯罩模型(图16)，各层切片耗时大部分集中在0.02 s～0.03 s内，靠近顶层的三角片较多，但耗时也都在0.05 s以内。

表2 本文方法与Cura软件切片耗时对比

对于扇子模型(图17)，由于该模型各层切片的轮廓个数一样，即使具有474个轮廓环，各层切片耗时也都只有0.17 s左右。各层耗时加起来远远低于Cura软件的处理时间，可以看出，本文基于图论的路径规划技术，无需复杂耗时的拓扑关系重建，因此对于处理大量嵌套轮廓的拓扑排序具有显著的效率优势。

实验2利用本文方法和著名切片软件Cura软件、Simplify3D软件对非封闭模型进行切片测试。如图18a所示为米老鼠头的STL模型，该模型为带有边界的非封闭网格模型，三角片总数为65 019，X、Y、Z方向总体尺寸分别为77 mm、24 mm、69 mm。由图18b可以看出，Cura软件无法处理非封闭模型，因此不能产生非封闭的切片轮廓线。而Simplify3D软件将模型强行封闭后再进行切片计算，因此每层切片轮廓都是封闭的，如图18c所示，显然，这种方法将会导致错误的打印结果，同时也会浪费较多的打印材料和时间。如图18d所示为本文方法在切片测试精度为1 mm下生成的切片效果图，可以看出，无论是在米老鼠脸部的单连通区域还是两个耳朵处的多连通区域，均能产生正确的非封闭轮廓线。这是由于本文方法将相交边当做节点，将三角片与切平面的相交关系映射为图，利用图的节点度特性找到了非封闭模型轮廓的边界起点位置，从而有效解决了开环轮廓的排序错乱问题，将这些开环切片轮廓线偏置一定的厚度，即可得到正确的打印填充区域。

实验3利用本文方法与Simplify3D软件、Cura软件对非流形网格模型(如图19a)进行切片测试。测试的3种模型在不同程度上都具有一些非流形三角片，由图19b和图19c所示的切片结果可以看出，Simplify3D软件和Cura软件会在非流形边附近产生轮廓断裂现象，而本文方法能够产生如图19d所示的正确的切片连通域。这是由于这些非流形网格的非流形边被两个以上的三角片所共享，因此若用传统方法进行轮廓排序，在非流形边处由于无法分辨正确的邻接三角片，从而造成轮廓排序错误。本文方法将三角片与切平面的相交关系映射为图后，利用图的节点度特性分析出非流形边(即图的割点)的位置所在，并利用双联通分解法将这种复杂自交图转化为简单连通图，有效解决了自交轮廓排序混乱问题，获得了正确的有序切片轮廓。

4 结束语

本文针对流形和非流形网格模型，提出了一种基于节点度的高效切片方法。该方法通过数据预处理、相交边提取、无向图构建、轮廓路径规划等步骤，快速而准确地构建出模型的各层有序切片轮廓。实验分析结果表明，本文方法在处理大型嵌套的切片轮廓具有较高的效率，而且能够解决非流形模型切片轮廓存在的非封闭和自交问题。

与现有方法相比，本文方法主要优点在于：① 通过判断三角片顶点与切平面的相对位置，将相交边映射为无向图，利用基于图论的强大路径规划技术进行拓扑排序，不仅避免公共边交点的重复计算，还无需耗时而复杂的网格拓扑关系重建，从而提高分层处理效率；② 利用图的节点度特性智能判断轮廓的封闭性和自交性，无需进行额外的网格非流形边的判断；③针对切片轮廓产生的自交问题，提出双连通分解法，将复杂自交图转化为简单连通图，从而能够有效去除多余轮廓分支，解决轮廓排序混乱问题。本文方法目前只针对正则的流形和非流形网格模型，对于非正则网格模型的切片方法将是未来研究的重点。