基于FDM 3D打印的模型數據前處理

吉冰倩， 王堯， 甘新基

（北華大學機械工程學院，吉林 吉林 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所示。

圖6 兔子點云圖

表1 兩種算法查詢時間比較

通過對具體的STL文件的讀取和顯示，測試了算法執行的時間，從表中的對比可以發現，本文算法在讀取的時候，運行時間上有一點改進，但也有的運行時間較慢一些，在算法上還有改進的空間。

5 結語

本文通過廣度優先搜索算法對STL文件進行三角面片的讀取及幾何信息拓撲重建，不斷搜索頂點以及讀取數據信息，同時不斷更新鄰接三角面片網絡，由于該算法無回溯過程，從時間上實現了更加快速的讀取，可為之后模型的切片處理提高了效率。