基于FDM 3D打印的模型數(shù)據(jù)前處理

吉冰倩， 王堯， 甘新基

（北華大學(xué)機(jī)械工程學(xué)院，吉林 吉林 132000）

0 引言

FDM 3D打印通過分層構(gòu)建來直接制造具有更復(fù)雜幾何形狀的零件。在大多數(shù)三維建模過程中，首先創(chuàng)建一個(gè)三維實(shí)體模型，轉(zhuǎn)換成立體光刻(STL)文件格式，然后通過組成STL模型的三角面片與切平面相交生成二維平面輪廓線。

STL文件的切片是FDM 3D打印過程中的一個(gè)重要環(huán)節(jié)。然而，STL文件的最大特點(diǎn)也是其主要問題，它是由一系列的三角形面片無序排列組合在一起的，沒有反映三角形面片之間的拓?fù)潢P(guān)系。對(duì)于一個(gè)較復(fù)雜的三維立體模型，其所記錄的三角面片數(shù)量龐大，在STL文件創(chuàng)建過程中生成的大量三角形的數(shù)據(jù)冗余會(huì)影響對(duì)模型進(jìn)行切片效率[1]。文獻(xiàn)[2]構(gòu)建鏈表數(shù)據(jù)結(jié)構(gòu)對(duì)集合拓?fù)潢P(guān)系進(jìn)行重建，但在去除冗余數(shù)據(jù)時(shí)，每次遍歷鏈表上時(shí)間復(fù)雜度較長，總體性能較低。文獻(xiàn)[3]采用哈希表將三角面片中的每個(gè)頂點(diǎn)及三角面片保存下來，提升了頂點(diǎn)的查找速度，但不同頂點(diǎn)的坐標(biāo)還可能存在相同哈希值的情況，對(duì)拓?fù)涞闹亟ù嬖谟绊憽Ｎ墨I(xiàn)[4]采用了紅黑樹為基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，去除每個(gè)三角面片上的冗余數(shù)據(jù)，重新構(gòu)建拓?fù)浣Y(jié)構(gòu)，該算法具有良好的可擴(kuò)展性。文獻(xiàn)[5]構(gòu)建了半邊結(jié)構(gòu)和哈希表的快速拓?fù)渲貥?gòu)算法，首先通過哈希表建立一個(gè)無重復(fù)位置信息的點(diǎn)表，然后在其中維護(hù)一個(gè)未添加鄰接面的半邊集合，依據(jù)半邊集合和拓?fù)渌惴ㄍ晟迫敲嫫恼麄€(gè)拓?fù)潢P(guān)系，有效的縮短了拓?fù)潢P(guān)系的建立，但拓?fù)渌惴◤?fù)雜。

基于以上算法的研究，本文提出一種基于廣度優(yōu)先搜索的三角面片搜索算法，通過建立頂點(diǎn)結(jié)構(gòu)體，邊存儲(chǔ)體，三角面片類，在讀取數(shù)據(jù)過程中，一方面剔除冗余數(shù)據(jù)，一方面快速找出三角面片的鄰接關(guān)系，提升了搜索的效率。

1 STL文件的格式

根據(jù)數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)性緊湊特點(diǎn)，本文選用二進(jìn)制(BINARY)數(shù)據(jù)格式。由于二進(jìn)制格式易于存儲(chǔ)且占內(nèi)存空間較小，二進(jìn)制STL文件用固定的字節(jié)數(shù)表示三角面片的空間幾何信息。完整的二進(jìn)制STL文件是三角面片數(shù)乘以50再加上84字節(jié)。

2 STL文件信息的搜索機(jī)制

2.1 廣度優(yōu)先搜索的策略

根據(jù)拓?fù)鋵W(xué)的歐拉公式，在三角面片數(shù)量很多的情況下，近似關(guān)系為

式中：V為三角面片網(wǎng)格的頂點(diǎn)數(shù)；F為網(wǎng)格面數(shù)。

本文采用廣度優(yōu)先遍歷的搜索算法用來查找STL文件三角面片的頂點(diǎn)和邊，以及面片之間的鄰接關(guān)系，系統(tǒng)的展開并檢查幾何拓?fù)鋱D中的所有節(jié)點(diǎn)，以完成整個(gè)文件的訪問。從STL文件的幾何拓?fù)湫畔⒅腥我獾剡x擇一個(gè)頂點(diǎn)s作為根，依次訪問s所有尚未訪問的鄰接頂點(diǎn)，就需要逐一枚舉并訪問鄰接頂點(diǎn)，頂點(diǎn)的標(biāo)號(hào)按照訪問順序注意標(biāo)記下來，同時(shí)由頂點(diǎn)s通往它剛被訪問的鄰接頂點(diǎn)的邊都被記錄在Edge數(shù)組內(nèi)，在這個(gè)階段所添加的新頂點(diǎn)成為生成樹在第一層的頂點(diǎn)。如此反復(fù)，直至沒有尚未訪問的鄰接頂點(diǎn)。

2.2 三角面片數(shù)據(jù)結(jié)構(gòu)的建立

根據(jù)STL文件的幾何拓?fù)湫畔⒎彪s特點(diǎn)，為了提升文件的讀取效率，需要考慮時(shí)間復(fù)雜度的運(yùn)行過程。

通過讀取并識(shí)別一個(gè)STL文件是二進(jìn)制或ASCII碼格式，創(chuàng)建一個(gè)頂點(diǎn)結(jié)構(gòu)體(Class Vertex)，記錄頂點(diǎn)自身的位置信息，設(shè)置在被創(chuàng)建時(shí)每個(gè)頂點(diǎn)的存儲(chǔ)狀態(tài)，設(shè)置時(shí)間標(biāo)簽記錄頂點(diǎn)被發(fā)現(xiàn)。通過廣度優(yōu)先搜索算法搜索過程的運(yùn)行速度快，以頂點(diǎn)為起點(diǎn)的全部鄰接點(diǎn)都被訪問并存儲(chǔ)起來。

建立一個(gè)邊結(jié)構(gòu)體，記錄相鄰頂點(diǎn)的邊的信息，經(jīng)過搜索之后，由一個(gè)頂點(diǎn)訪問其未處于隊(duì)列中鄰接頂點(diǎn)的邊被直接存儲(chǔ)進(jìn)來，而訪問正處于隊(duì)列中的頂點(diǎn)或已經(jīng)存儲(chǔ)完的頂點(diǎn)，其相連接的邊被歸為跨邊類型（兩點(diǎn)之間存在一條連邊，設(shè)置頂點(diǎn)之間邊的查詢狀態(tài)為已存在）。

三角面片的信息被存儲(chǔ)到Vector容器中，定義一個(gè)固定大小的數(shù)組用來存儲(chǔ)v1、v2、v3，定義法向量數(shù)組，鄰接三角面片存儲(chǔ)數(shù)組。頂點(diǎn)、邊、三角面片存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)設(shè)置如下：

3 STL文件幾何信息拓?fù)渲亟ǖ牧鞒?/h2>

3.1 冗余數(shù)據(jù)的處理

基于廣度優(yōu)先搜索的過程，為了使得算法便于實(shí)現(xiàn)，搜索過程中暫時(shí)存放節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)需要采用隊(duì)列的結(jié)構(gòu)。如圖1，隊(duì)列允許插入的叫“隊(duì)尾”（rear），允許刪除的叫“隊(duì)首”（front）。在讀取的過程中，首先讀入頭部法向量，接著迭代讀取3 個(gè)頂點(diǎn)，直到讀到尾部標(biāo)志，讀取結(jié)束。

圖1 隊(duì)列結(jié)構(gòu)

首先讓最初的頂點(diǎn)s入隊(duì)，入隊(duì)之前剛被發(fā)現(xiàn)，更改狀態(tài)為已發(fā)現(xiàn)，并附上時(shí)間標(biāo)簽d_Time，在確定隊(duì)列不空的情況下，讓頂點(diǎn)s出隊(duì)，搜索直接與頂點(diǎn)s有鄰接關(guān)系的頂點(diǎn)，此為第一層向外擴(kuò)展搜索的等價(jià)類頂點(diǎn){A1，A2，A3，A4},在這第一層等價(jià)類頂點(diǎn){A1，A2，A3，A4}中，視鄰接頂點(diǎn)的狀態(tài)，分別處理。

第一種情況，如果鄰接頂點(diǎn)A1尚未被發(fā)現(xiàn)，則發(fā)現(xiàn)該鄰接頂點(diǎn)并讓A1入隊(duì)，并附上時(shí)間標(biāo)簽d_Time，就被標(biāo)記為已發(fā)現(xiàn)狀態(tài)，并將頂點(diǎn)s和頂點(diǎn)A1這條邊引入邊結(jié)構(gòu)體；至此頂點(diǎn)s已被發(fā)現(xiàn)完畢；依次發(fā)現(xiàn)并訪問A2、A3、A4迭代上述過程。

第二種情況，如果鄰接頂點(diǎn)A1已被發(fā)現(xiàn)也就是正在隊(duì)列中，或者已經(jīng)訪問完畢(已出隊(duì)列)，則將起始頂點(diǎn)s與A1所在的邊歸類于跨邊CROSS中；這就完成一個(gè)新頂點(diǎn)的添加。

3.2 拓?fù)湫畔⒌纳?/h3>

1）創(chuàng)建起始頂點(diǎn)的拓?fù)湫畔ⅰｍ旤c(diǎn)V出隊(duì)，說明此時(shí)V已經(jīng)被發(fā)現(xiàn)并標(biāo)記d_Time=1，搜尋V具有的若干個(gè)第一層等價(jià)類鄰接頂點(diǎn)。如圖3所示，A={A1，A2，A3}為V的第一層等價(jià)類，首先讀入A1的位置信息，接著入隊(duì)操作，標(biāo)記d_Time=2，判斷Edge(V,A1)是否存在，不存在則將這條邊添加到邊結(jié)構(gòu)體；接著讀取A2的位置信息，進(jìn)行入隊(duì)操作，標(biāo)記d_Time=3，判斷Edge(V,A2)是否存在，不存在則將這條邊加入邊結(jié)構(gòu)體；讀入最后一個(gè)頂點(diǎn)A3信息，接著入隊(duì)操作，標(biāo)記d_Time=4，判斷Edge(V，A3)是否存在，同樣加入邊結(jié)構(gòu)體；至此，第一層的鄰接頂點(diǎn)已被搜索完，起始頂點(diǎn)V存儲(chǔ)完畢。

2）創(chuàng)建第一個(gè)鄰接點(diǎn)A1的拓?fù)湫畔ⅰｍ旤c(diǎn)A1出隊(duì)，搜索具有鄰接關(guān)系的頂點(diǎn)，如圖3所示，鄰接點(diǎn)的集合為{V,A2,A3,B1,B3}，V已經(jīng)存儲(chǔ)完畢，A2、A3已被發(fā)現(xiàn)正在隊(duì)列中，則直接將Edge（A1,A2），Edge (A1,A3） 歸類于跨邊類型CROSS中，三角面片Point3f（V,A1,A2）和Point3f（V,A1,A3）被搜索和添加到Adjacency[]中，添加面表所攜帶的法向量信息。讀入第二層等價(jià)類頂點(diǎn)B1的數(shù)據(jù)，存入隊(duì)列，標(biāo)記d_Time=5，判斷邊Edge（A1,B1）是否存在，不存在則將這條新邊添加到邊結(jié)構(gòu)體；進(jìn)行下一個(gè)鄰接點(diǎn)B3的數(shù)據(jù)讀取，判斷邊Edge（A1,B3）是否存在，不存在則將這條新邊加入邊結(jié)構(gòu)體至此，A1存儲(chǔ)完畢。

圖2 起始頂點(diǎn)V的拓?fù)湫畔?/p>

圖3 頂點(diǎn)A1的拓?fù)湫畔?/p>

3）創(chuàng)建第二個(gè)鄰接頂點(diǎn)A2的拓?fù)湫畔?。頂點(diǎn)A2出隊(duì)，搜索其具有鄰接關(guān)系的頂點(diǎn)，如圖4所示，A2的鄰接頂點(diǎn)集合為{V,A1, A3,B1,B2,B3}、V、A1的頂點(diǎn)信息及面片Point3f(V,A1,A2)存儲(chǔ)完畢。A3、B1、B3被發(fā)現(xiàn)正在隊(duì)列中，所以將Edge(A2,A3)、Edge(A2,B1)和Edge（A2,B1）歸類于跨邊類型CROSS中，三角面片Point3f（V,A2,A3），Point3f（A1,A2,B1）被添加到Adjacency[]中數(shù)組內(nèi)，同時(shí)將2個(gè)三角面片的法向量加入到Normal_Vector[]中。讀入第二層等價(jià)類頂點(diǎn)B2，入隊(duì)列，標(biāo)記d_Time=7判斷邊Edge（A2,B2）是否存在，不存在則將這條新邊加到邊結(jié)構(gòu)體。至此，A2存儲(chǔ)完畢。

圖4 頂點(diǎn)A2的拓?fù)湫畔?/p>

4）創(chuàng)建第三個(gè)鄰接頂點(diǎn)A3的拓?fù)湫畔?。頂點(diǎn)A3出隊(duì)，同樣搜索其所具有的鄰接關(guān)系的頂點(diǎn)為{V,A1,A2,B3}，V，A1，A2的頂點(diǎn)信息已經(jīng)被存儲(chǔ)起來。B3被發(fā)現(xiàn)在隊(duì)列中，所以將Edge（A3,B3）歸類于跨邊類型CROSS中。至此，A3存儲(chǔ)完畢。所以第一層的等價(jià)類頂點(diǎn)以及三角面片的信息已經(jīng)被存儲(chǔ)起來，接著B1，B3，B2出隊(duì)進(jìn)行迭代訪問并讀取后續(xù)層的等價(jià)類頂點(diǎn)以及存儲(chǔ)，直到STL文件的幾何拓?fù)湫畔⒈煌暾x取和存儲(chǔ)。過程如圖5所示。

圖5 頂點(diǎn)A3的拓?fù)湫畔?/p>

4 讀取實(shí)例顯示與測試

本文基于廣度優(yōu)先搜索的三維拓?fù)渲亟ㄋ惴ǎ鶕?jù)STL文件的數(shù)據(jù)排列規(guī)則，若要一個(gè)字節(jié)都不漏地讀入整個(gè)文件，需要采用二進(jìn)制的方式打開，讀取規(guī)則如下：1）打開一個(gè)STL文件；2）讀取并訪問頂點(diǎn)的信息；3）進(jìn)入隊(duì)列，存儲(chǔ)連接便；4）迭代訪問鄰接點(diǎn)；5）鄰接點(diǎn)是否已在隊(duì)列中，是進(jìn)行步驟6），否則轉(zhuǎn)到步驟3）；6）將相鄰頂點(diǎn)連接邊標(biāo)記為CROSS；7）頂點(diǎn)存儲(chǔ)完畢，文件讀取成功；8）關(guān)閉文件。

在完成三角面片拓?fù)鋽?shù)據(jù)讀取及存儲(chǔ)后，最終點(diǎn)云圖的形式顯示出來。本文以Visual Studio2017和QT5.14為實(shí)驗(yàn)開發(fā)平臺(tái)，測試本文基于廣度優(yōu)先搜索的幾何信息拓?fù)渲亟ǖ某绦蛩惴?，結(jié)合配置OpenGL編程技術(shù)實(shí)現(xiàn)對(duì)STL 文件的讀取與顯示。

通 過VS2017軟件讀取了3個(gè)STL文件模型進(jìn)行讀取測試，分析對(duì)比兩種算法，結(jié)果如表1所示。

圖6 兔子點(diǎn)云圖

表1 兩種算法查詢時(shí)間比較

通過對(duì)具體的STL文件的讀取和顯示，測試了算法執(zhí)行的時(shí)間，從表中的對(duì)比可以發(fā)現(xiàn)，本文算法在讀取的時(shí)候，運(yùn)行時(shí)間上有一點(diǎn)改進(jìn)，但也有的運(yùn)行時(shí)間較慢一些，在算法上還有改進(jìn)的空間。

5 結(jié)語

本文通過廣度優(yōu)先搜索算法對(duì)STL文件進(jìn)行三角面片的讀取及幾何信息拓?fù)渲亟ǎ粩嗨阉黜旤c(diǎn)以及讀取數(shù)據(jù)信息，同時(shí)不斷更新鄰接三角面片網(wǎng)絡(luò)，由于該算法無回溯過程，從時(shí)間上實(shí)現(xiàn)了更加快速的讀取，可為之后模型的切片處理提高了效率。