基于FDM 3D打印的模型数据前处理

2022-03-24吉冰倩王尧甘新基

机械工程师 2022年3期

吉冰倩，王尧，甘新基

（北华大学机械工程学院，吉林吉林 132000）

0 引言

FDM 3D打印通过分层构建来直接制造具有更复杂几何形状的零件。在大多数三维建模过程中，首先创建一个三维实体模型，转换成立体光刻(STL)文件格式，然后通过组成STL模型的三角面片与切平面相交生成二维平面轮廓线。

STL文件的切片是FDM 3D打印过程中的一个重要环节。然而，STL文件的最大特点也是其主要问题，它是由一系列的三角形面片无序排列组合在一起的，没有反映三角形面片之间的拓扑关系。对于一个较复杂的三维立体模型，其所记录的三角面片数量庞大，在STL文件创建过程中生成的大量三角形的数据冗余会影响对模型进行切片效率[1]。文献[2]构建链表数据结构对集合拓扑关系进行重建，但在去除冗余数据时，每次遍历链表上时间复杂度较长，总体性能较低。文献[3]采用哈希表将三角面片中的每个顶点及三角面片保存下来，提升了顶点的查找速度，但不同顶点的坐标还可能存在相同哈希值的情况，对拓扑的重建存在影响。文献[4]采用了红黑树为基础的数据结构，去除每个三角面片上的冗余数据，重新构建拓扑结构，该算法具有良好的可扩展性。文献[5]构建了半边结构和哈希表的快速拓扑重构算法，首先通过哈希表建立一个无重复位置信息的点表，然后在其中维护一个未添加邻接面的半边集合，依据半边集合和拓扑算法完善三角面片的整个拓扑关系，有效的缩短了拓扑关系的建立，但拓扑算法复杂。

基于以上算法的研究，本文提出一种基于广度优先搜索的三角面片搜索算法，通过建立顶点结构体，边存储体，三角面片类，在读取数据过程中，一方面剔除冗余数据，一方面快速找出三角面片的邻接关系，提升了搜索的效率。

1 STL文件的格式

根据数据存储结构性紧凑特点，本文选用二进制(BINARY)数据格式。由于二进制格式易于存储且占内存空间较小，二进制STL文件用固定的字节数表示三角面片的空间几何信息。完整的二进制STL文件是三角面片数乘以50再加上84字节。

2 STL文件信息的搜索机制

2.1 广度优先搜索的策略

根据拓扑学的欧拉公式，在三角面片数量很多的情况下，近似关系为

式中：V为三角面片网格的顶点数；F为网格面数。

本文采用广度优先遍历的搜索算法用来查找STL文件三角面片的顶点和边，以及面片之间的邻接关系，系统的展开并检查几何拓扑图中的所有节点，以完成整个文件的访问。从STL文件的几何拓扑信息中任意地选择一个顶点s作为根，依次访问s所有尚未访问的邻接顶点，就需要逐一枚举并访问邻接顶点，顶点的标号按照访问顺序注意标记下来，同时由顶点s通往它刚被访问的邻接顶点的边都被记录在Edge数组内，在这个阶段所添加的新顶点成为生成树在第一层的顶点。如此反复，直至没有尚未访问的邻接顶点。

2.2 三角面片数据结构的建立

根据STL文件的几何拓扑信息繁杂特点，为了提升文件的读取效率，需要考虑时间复杂度的运行过程。

通过读取并识别一个STL文件是二进制或ASCII码格式，创建一个顶点结构体(Class Vertex)，记录顶点自身的位置信息，设置在被创建时每个顶点的存储状态，设置时间标签记录顶点被发现。通过广度优先搜索算法搜索过程的运行速度快，以顶点为起点的全部邻接点都被访问并存储起来。

建立一个边结构体，记录相邻顶点的边的信息，经过搜索之后，由一个顶点访问其未处于队列中邻接顶点的边被直接存储进来，而访问正处于队列中的顶点或已经存储完的顶点，其相连接的边被归为跨边类型（两点之间存在一条连边，设置顶点之间边的查询状态为已存在）。

三角面片的信息被存储到Vector容器中，定义一个固定大小的数组用来存储v1、v2、v3，定义法向量数组，邻接三角面片存储数组。顶点、边、三角面片存储的数据结构设置如下：

3 STL文件几何信息拓扑重建的流程

3.1 冗余数据的处理

基于广度优先搜索的过程，为了使得算法便于实现，搜索过程中暂时存放节点的数据结构需要采用队列的结构。如图1，队列允许插入的叫“队尾”（rear），允许删除的叫“队首”（front）。在读取的过程中，首先读入头部法向量，接着迭代读取3 个顶点，直到读到尾部标志，读取结束。

图1 队列结构

首先让最初的顶点s入队，入队之前刚被发现，更改状态为已发现，并附上时间标签d_Time，在确定队列不空的情况下，让顶点s出队，搜索直接与顶点s有邻接关系的顶点，此为第一层向外扩展搜索的等价类顶点{A1，A2，A3，A4},在这第一层等价类顶点{A1，A2，A3，A4}中，视邻接顶点的状态，分别处理。

第一种情况，如果邻接顶点A1尚未被发现，则发现该邻接顶点并让A1入队，并附上时间标签d_Time，就被标记为已发现状态，并将顶点s和顶点A1这条边引入边结构体；至此顶点s已被发现完毕；依次发现并访问A2、A3、A4迭代上述过程。

第二种情况，如果邻接顶点A1已被发现也就是正在队列中，或者已经访问完毕(已出队列)，则将起始顶点s与A1所在的边归类于跨边CROSS中；这就完成一个新顶点的添加。

3.2 拓扑信息的生成

1）创建起始顶点的拓扑信息。顶点V出队，说明此时V已经被发现并标记d_Time=1，搜寻V具有的若干个第一层等价类邻接顶点。如图3所示，A={A1，A2，A3}为V的第一层等价类，首先读入A1的位置信息，接着入队操作，标记d_Time=2，判断Edge(V,A1)是否存在，不存在则将这条边添加到边结构体；接着读取A2的位置信息，进行入队操作，标记d_Time=3，判断Edge(V,A2)是否存在，不存在则将这条边加入边结构体；读入最后一个顶点A3信息，接着入队操作，标记d_Time=4，判断Edge(V，A3)是否存在，同样加入边结构体；至此，第一层的邻接顶点已被搜索完，起始顶点V存储完毕。

2）创建第一个邻接点A1的拓扑信息。顶点A1出队，搜索具有邻接关系的顶点，如图3所示，邻接点的集合为{V,A2,A3,B1,B3}，V已经存储完毕，A2、A3已被发现正在队列中，则直接将Edge（A1,A2），Edge (A1,A3）归类于跨边类型CROSS中，三角面片Point3f（V,A1,A2）和Point3f（V,A1,A3）被搜索和添加到Adjacency[]中，添加面表所携带的法向量信息。读入第二层等价类顶点B1的数据，存入队列，标记d_Time=5，判断边Edge（A1,B1）是否存在，不存在则将这条新边添加到边结构体；进行下一个邻接点B3的数据读取，判断边Edge（A1,B3）是否存在，不存在则将这条新边加入边结构体至此，A1存储完毕。

图2 起始顶点V的拓扑信息

图3 顶点A1的拓扑信息

3）创建第二个邻接顶点A2的拓扑信息。顶点A2出队，搜索其具有邻接关系的顶点，如图4所示，A2的邻接顶点集合为{V,A1, A3,B1,B2,B3}、V、A1的顶点信息及面片Point3f(V,A1,A2)存储完毕。A3、B1、B3被发现正在队列中，所以将Edge(A2,A3)、Edge(A2,B1)和Edge（A2,B1）归类于跨边类型CROSS中，三角面片Point3f（V,A2,A3），Point3f（A1,A2,B1）被添加到Adjacency[]中数组内，同时将2个三角面片的法向量加入到Normal_Vector[]中。读入第二层等价类顶点B2，入队列，标记d_Time=7判断边Edge（A2,B2）是否存在，不存在则将这条新边加到边结构体。至此，A2存储完毕。

图4 顶点A2的拓扑信息

4）创建第三个邻接顶点A3的拓扑信息。顶点A3出队，同样搜索其所具有的邻接关系的顶点为{V,A1,A2,B3}，V，A1，A2的顶点信息已经被存储起来。B3被发现在队列中，所以将Edge（A3,B3）归类于跨边类型CROSS中。至此，A3存储完毕。所以第一层的等价类顶点以及三角面片的信息已经被存储起来，接着B1，B3，B2出队进行迭代访问并读取后续层的等价类顶点以及存储，直到STL文件的几何拓扑信息被完整读取和存储。过程如图5所示。

图5 顶点A3的拓扑信息

4 读取实例显示与测试

本文基于广度优先搜索的三维拓扑重建算法，根据STL文件的数据排列规则，若要一个字节都不漏地读入整个文件，需要采用二进制的方式打开，读取规则如下：1）打开一个STL文件；2）读取并访问顶点的信息；3）进入队列，存储连接便；4）迭代访问邻接点；5）邻接点是否已在队列中，是进行步骤6），否则转到步骤3）；6）将相邻顶点连接边标记为CROSS；7）顶点存储完毕，文件读取成功；8）关闭文件。

在完成三角面片拓扑数据读取及存储后，最终点云图的形式显示出来。本文以Visual Studio2017和QT5.14为实验开发平台，测试本文基于广度优先搜索的几何信息拓扑重建的程序算法，结合配置OpenGL编程技术实现对STL 文件的读取与显示。

通过VS2017软件读取了3个STL文件模型进行读取测试，分析对比两种算法，结果如表1所示。