文 豪，高 健，张正甫

（1.广东科学技术职业学院机械与汽车学院，广东 珠海 519090；2.广东工业大学机电工程学院，广东 广州 510006）

1 引言

在计算机中，STL的文件格式[1]可用于表示三维模型的外形尺寸，常用于逆向工程、快速原型、快速制造等相关工业领域[2]。其中针对3D打印及快速原型等应用环境，STL文件经常需要进行轮廓切片及截面求交的数据处理操作。对此，可行的计算机数据处理操作为先判断网格面片与截平面的位置关系并提取相交面片的几何信息[3]，再依次计算相交截点的坐标信息并连接形成截面轮廓[4]。

然而，STL的文件格式[5]仅随机记录三维模型的网格面片信息，并且只包含面片法矢与三个顶点的三维坐标。STL文件的模型数据无法直接实现截面交点的相邻关系位置判断，需要在模型的切片操作前对STL文件进行拓扑重构的数据处理操作，建立多种模型几何数据的直接映射关系[6]。文献[7]提出了基于标准模板库set容器的拓扑关系重建算法，可有效去除STL文件的冗余数据，实现了模型数据的快速切片操作。文献[8]根据模型的冗余信息确定了三角面片之间的拓扑关系，并判定有序点列形成封闭的截面轮廓。文献[9]使用半边数据结构重构了三角面片间的邻接拓扑关系，解决了截面轮廓生成中截面交点的有序连接问题。基于ACIS平台，文献[10]研究了STL模型的拓扑重构问题，实现了模型数据快速准确的算法操作。文献[11]使用三维k-d树的方法实现了网格模型的自适应分层切片，并在增材制造中实际应用。文献[12]提出了基于链表的拓扑重建算法，可有效提高切片算法的整体效率。文献[13]以哈希表作为查找表，建立了模型的几何拓扑关系，可显著提升后续的切片效率。文献[14]提出了STL文件的数据扩展格式，丰富了模型文件内容，可实现切片数据的直接生成。

综上所述，针对3D打印中模型数据的截面轮廓求取问题，目前研究先对模型文件进行几何拓扑数据重构，再在已知几何邻接关系的基础上依次求取表示截面轮廓的交点坐标，从而根据模型重构的几何拓扑关系连接截面交点生成截面轮廓。然而模型文件的几何拓扑数据重构操作复杂，常伴随着大量的冗余数据处理，严重影响3D 打印系统中的截面轮廓与加工路径生成速度。对此重点研究STL文件的截面求交操作与轮廓线段的连接方法，通过STL文件的计算机数据格式特征分析，提出了面向STL文件的截面轮廓线段连接算法，先通过截面与面片的相交判断与交点计算，获取所有的相交轮廓线段，再对相交轮廓线段的邻接关系进行判断，最终形成有效的截面轮廓，并于PythonOCC的测试平台中编程验证。该算法可直接避免模型数据的拓扑数据操作，通过STL文件的直接数据处理，直接实现3D打印中模型数据截面轮廓的获取生成。

2 STL文件的数据处理分析

区别于工程领域中的参数化模型，三角网格模型使用一系列三角面片表示模型的外形轮廓。在计算机中常以STL的文件格式存储模型数据，其中随机记录了三维模型的网格面片信息。STL文件中的一个面片数据只包含面片法矢与三个顶点的三维坐标，如图1所示。

图1 STL文件中的一个面片数据Fig.1 One Facet Data in STL File

在模型数据的获取与处理当中，三角网格模型可能存在着几何缺陷问题，包括共边、相交、重叠、孔洞裂缝等[15]，会造成截面轮廓的求交计算错误。然而STL文件中并未直接反映这些几何缺陷问题，在截面轮廓的生成计算前应优化模型文件，确保网格质量。对于正确有效的模型数据，算法生成的截面轮廓应为首尾相连、不重叠重复的有序线段，且每条轮廓线段对应一个面片，如图2所示。

图2 STL文件的截面轮廓线段Fig.2 Cross Contour Segments of STL File

目前研究的操作过程为先对STL文件进行模型数据的几何关系拓扑重构，建立几何数据的映射关系，再在此基础上计算截面交点的坐标数据，并根据模型重构的几何拓扑关系连接截面交点生成截面轮廓。然而拓扑重构的数据处理量大，并伴随着与当前截面求交无关的大量冗余数据操作，对于STL文件的直接截面轮廓生成操作不具备速度优势。另一方面，由于截面轮廓线段分别对应于网格模型的相交三角面片，其数据信息已于STL文件中逐一记录。因此，针对STL文件的截面轮廓生成操作，应直接处理STL文件的模型数据。

3 算法原理与操作步骤

所提算法的主要思路是利用STL文件逐次记录的面片信息直接计算截面轮廓线段，再直接判断各线段的邻接关系生成截面轮廓，无需依靠模型重构的几何拓扑关系判断截面交点的连接顺序。算法流程，如图3所示。其中可分为三步操作。

图3 算法流程Fig.3 Algorithm Flow

3.1 相交面片判断与数据选取

欲使模型轮廓与截平面求交，则截面不能与轮廓重合，面片与截面只有相交和不相交的两种位置关系。若面片与截面不相交，则面片三个顶点均位于截面的一侧，可利用该特征依次提取STL文件中的面片数据，再判断是否与截面相交，如图4所示。

图4 截面与面片不相交的情况Fig.4 Situation that Cross Section and Facet are not Intersect

截平面的空间坐标表达式均可转换为一般方程：

式中：A、B、C、D—已知常数，A、B、C不可同时为0。设顶点与截面的位置判断函数：

对于提取的一个网格面片数据，可将三个顶点v1、v2、v3的三维坐标分别代入式（2），若f(x，y，z)的三个计算值均大于或小于0，说明了面片的三个顶点均位于截面的一侧，面片与截面不相交。否则应选取当前面片数据，并用于下一步的算法处理操作。

3.2 截面轮廓线段的计算生成

截面与面片相交可划分为四种情况，如图5所示。其中，相交的结果均可表示为一段长度大于或等于0的直线线段，并可用两个顶点的三维坐标表示。

图5 截面与面片相交的四种情况Fig.5 Four Situations of Cross Section and Facet

轮廓线段两个顶点的三维坐标计算判断如下：

（1）若面片三个顶点的f(x，y，z)计算值有两个为0，则截面与一条边重合，轮廓线段的两个顶点即为f(x，y，z)计算值为0的两个面片顶点。

（2）若面片三个顶点的f(x，y，z)计算值有且仅有一个为0，则需判断另外两个面片顶点相对截面的位置关系。若另外两个面片顶点的f(x，y，z)计算值均大于或小于0，则说明了面片与截面相交于一个顶点，轮廓线段的长度为0，两个顶点均为f(x，y，z)计算值为0的面片顶点。若另外两个面片顶点的f(x，y，z)计算值出现一个大于0和另一个小于0的情况，则说明了面片与截面相交于边上点与顶点。此时轮廓线段的一个顶点为f(x，y，z)计算值为0的面片顶点，另一个顶点为面片边与截面交点，需要选取f(x，y，z)计算值不为0的两个面片点与截面方程联合求解。

（3）若面片三个顶点的f(x，y，z)计算值均不为0，则面片与截面相交于两条边上的两个点。截面与边相交，边的两个顶点也应分别位于截面两侧。从面片三个顶点中选取两组f(x，y，z)计算值分别大于0和小于0的两个面片顶点组成两条面片边，再分别与截面方程联合求解，可得轮廓线段两个顶点的坐标数据。

截面与面片边的交点计算，如图6所示。根据截面方程和两个分别位于截面两侧的面片顶点可实现交点坐标的联合求解。

图6 截面交点的求解计算Fig.6 Calculation of Cross Section Intersection

相交边的两个顶点与坐标为P1(x1，y1，z1)和P2(x2，y2，z2)，分别位于截面的两侧，与截面的距离分别为d1和d2，可通过点到面的距离公式计算：

设截面交点及坐标为P(x，y，z)，根据点与点的距离比例关系，可得截面交点P的x坐标函数关系：

至此，通过对所有相交面片的求交计算，可生成所有的截面轮廓线段，且每段线段包含两顶点的坐标信息。然而选取STL文件的相交面片顺序是随机的，计算生成的截面轮廓线段也是随机无序的，需要对轮廓线段的相同顶点进行判断及连接才能生成截面轮廓。

3.3 截面轮廓线段的判断连接

对于不同的模型外形轮廓特征，截面轮廓是各不相同的。对于无几何缺陷问题的STL 文件，其模型外形可划分为封闭曲面、开放曲面及组合曲面三类，如图7所示。其中，封闭曲面的截面轮廓为首尾相连的闭合线条；开放曲面的截面轮廓为首尾不连接的线条；组合曲面则为多个曲面的组合，其截面轮廓也为多个单一截面轮廓的组合，各截面轮廓之间互不相同。

图7 截面轮廓的分类Fig.7 Classification of Cross Contour

根据上述的相交面片判断与数据选取及截面轮廓线段计算生成操作，可以得到当前截面所对应的轮廓线段，每条轮廓线段则包含两个顶点的坐标信息，且截面轮廓线段的所有数据均为无序排列。对网格模型的截面轮廓线段进行了归类划分，如图8所示。其中单一截面轮廓可能存在封闭与开放的两种情况，组合截面轮廓则由多个单一截面轮廓组成。

图8 截面轮廓的线段类型Fig.8 Segments Types of Cross Contour

对于截面轮廓的最终生成，需要对无序的轮廓线段进行连接，判断单一截面轮廓的封闭性，并分别存储组合截面轮廓中各个单一截面轮廓的数据信息。结合图8，具体的算法步骤及描述如下：

（1）选取轮廓线段的任意顶点作为起点。可任意选取P40作为起点，如图8（a）所示。

（2）使用当前选定的顶点检索相邻轮廓线段。由于截面交点计算可能存在一定的精度损失，若某个轮廓线段顶点与该顶点的距离小于允许计算精度（建议值为0.0001mm），则可认为两顶点所对应的两条截面轮廓线段相邻。如依次计算其他轮廓线段的顶点与已选取顶点P40的距离，其中，唯有P60符合允许计算精度要求。因而可知顶点P40和P60对应的截面轮廓线段E4和E6相邻，公用顶点坐标为P40和P60的坐标平均。

（3）使用上述操作（2）的方法依次检索相邻轮廓线段，获取最终轮廓连线的顶点坐标。通过已检索的顶点P60及其对应的轮廓线段E6可快速获取另一顶点P61，再使用（2）的方法可依次检索P61→P31→E3→P30→P10→E1→P11→...，最终生成的截面轮廓为相邻轮廓线段公用顶点的依次连线，即

（4）判断当前生成截面轮廓的封闭性。对于上述的操作（3），在相邻轮廓线段数据信息的依次检索中，可能出现封闭轮廓的重复检索问题，也可能出现开放轮廓无法继续检索的问题。对于封闭轮廓的判断，可将相邻轮廓线段快速获取的另一顶点与起点相比较，若为同一顶点则封闭轮廓形成闭环。每次相邻轮廓线段快速获取的另一顶点P61、P30、P11等均与起点P40比较，直至顶点P41对应轮廓线段E4快速获取的另一顶点为起点P40，如图8（a）所示。对于开放轮廓的判断与处理，若没有任何顶点与选定顶点的距离小于允许计算精度，则说明该选定顶点为边界点，此时应返回起点并使用操作（2）的方法向另一个方向检索相邻轮廓线段直至边界点。若从起点检索至P50，无法检索下一相邻轮廓线段，P50为边界点，返回起点并沿另一方向检索，直至另一边界点P60为止，如图8（b）所示。

（5）组合截面轮廓的判断与处理。若通过上述的4步操作仍有未被检索的轮廓线段，说明该截面轮廓为组合的，并存在未被处理的单一截面轮廓。可将未被检索的轮廓线段重新用于上述的4步操作，生成另一个单一截面轮廓，直至所有的轮廓线段均被检索。若E1、E4、E6所组成的单一截面轮廓已被处理，剩下的E2、E5、E3未被检索，可使用上述的4步操作生成对应的另一个单一截面轮廓，从而形成最终完整的组合截面轮廓，如图8（c）所示。

设所有轮廓线段的顶点集合为P，任意一条轮廓线段Eɑb对应的两个顶点为()Vɑ，Vb，O为每一条独立轮廓的点的有序集合（列表）。算法为cɑlc_outline，形参*P、*V、*O是指针传递形式。截面轮廓线段判断连接的算法伪代码，如图9所示。

图9 算法伪代码Fig.9 Algorithm Pseudocode

4 实例测试与数据验证

4.1 测试环境

基于所提出的STL文件截面轮廓线段连接算法，借助开源的三维模型显示平台，在计算机中编程开发了面向STL文件的截面轮廓生成模块。具体的测试环境参数如下：

4.2 数据验证

将多个STL文件输入至测试平台，并通过截面轮廓生成模块的数据处理，验证所提出截面轮廓线段连接算法的有效性。软件运行及数据处理的最终效果，如图10所示。可见所提算法可通过STL文件的直接数据处理，避免模型数据的拓扑数据操作，快速有效的生成3D打印中模型数据的截面轮廓。

图10 算法测试及效果显示Fig.10 Algorithm Test and Effect Display

5 结论

面向3D打印中模型数据的截面轮廓求取问题，重点研究了STL文件的截面求交操作与轮廓线段的连接方法，通过STL文件的计算机数据格式特征分析，提出了面向STL文件的截面轮廓线段连接算法。首先，通过STL文件的相交面片选取与求交坐标计算，直接生成了相交截面的轮廓线段；然后，通过轮廓线段的连接判断，快速生成了模型数据的截面轮廓；最后，借助PythonOCC的开源三维模型显示平台，使用Python的计算机编程语言编程开发了面向STL文件的截面轮廓生成模块，并通过多个模型的数据测试对所提算法的有效性给予了验证。实验结果表明，所提出算法可通过STL 文件的直接数据处理，避免模型数据的拓扑数据操作，快速有效的生成3D打印中模型数据的截面轮廓。