基于STL文件的柱狀支撐結(jié)構(gòu)自動生成算法

宋廷強，劉亞林，張 敏

(青島科技大學(xué)信息科學(xué)技術(shù)學(xué)院，山東青島 266061)

0 引言

隨著全球工業(yè)的快速發(fā)展，快速成型技術(shù) (rapid prototyping，RP)已經(jīng)成為發(fā)展最快的技術(shù)之一。目前存在多種打印技術(shù)，但是其本質(zhì)的不同在于打印的材料和打印的方式。有一些利用融化的可塑性材料來打印，比如:選擇性激光燒結(jié) (selective laser sintering，SLS)和熔融擠壓(fused deposition modeling，F(xiàn)DM)，還有一些技術(shù)是用液體材料打印，例如:立體平板印刷 (stereolithography，SLA)和分層實體制造 (laminated object manufacturing，LOM)。每一種技術(shù)都有各自的優(yōu)缺點，一般根據(jù)不同的需求、打印機(jī)成本、打印速度和材料等方面考慮，選擇合適的打印技術(shù)［1］。

熔融擠壓 (FDM)型三維打印機(jī)一般以熱塑性材料，如PLA(Polylactic Acid)塑料、ABS(acrylonitrile–butadiene–styrene copolymer)塑料、尼龍等為打印原料，打印時先將材料融化，然后通過噴頭沿著一定路徑將材料擠出到打印平臺，材料迅速冷卻凝固，然后在打印第二層，直到模型打印完畢。由于FDM這種堆疊式的加工方式，遇到模型中懸空部分是，打印材料無法在半空中凝固成型，因此需要用戶為懸空部分模型添加支撐結(jié)構(gòu)［2-3］。支撐結(jié)構(gòu)會隨著模型一起被打印，但是由于其不屬于模型本身，因此在完成打印后需要將支撐結(jié)構(gòu)拆除。支撐結(jié)構(gòu)拆除會對模型表面造成損傷，因此在保證模型順利成型的前提下應(yīng)該盡可能的減少支撐結(jié)構(gòu)與模型表面的接觸面積和減少支撐結(jié)構(gòu)本身的體積。

目前在支撐研究方面已經(jīng)有人做了大量的工作，Wang［4］等提出了一種蒙皮——框架輕量打印模型，并在此基礎(chǔ)上拓展出一種圓柱支撐結(jié)構(gòu)的生成方法。陳巖等［5］在wang的基礎(chǔ)上提出一種改進(jìn)方法，這兩種方法的支撐結(jié)構(gòu)均為獨立圓柱體，雖然可以節(jié)省時間，但是打印時穩(wěn)定性不夠。Cura軟件通過在待支撐面添加稀疏密度的網(wǎng)格結(jié)構(gòu)作為支撐體，這樣雖然支撐結(jié)構(gòu)穩(wěn)定，但是會浪費材料，增加打印時間。Zhang［6］等受自然骨架的啟發(fā)，設(shè)計在模型內(nèi)部的六邊形支撐結(jié)構(gòu)，該結(jié)構(gòu)能夠使模型承受外部各個方向的負(fù)荷，穩(wěn)定性好，但是支撐結(jié)構(gòu)在模型內(nèi)部，無法去除。MeshMixer公司提出一種樹狀支撐結(jié)構(gòu)生成方法，但是該方法某些時候仍需要人工干預(yù)，有一定的學(xué)習(xí)成本，而且有時會出現(xiàn)打印失敗的現(xiàn)象。宋國華［7］等基于L－系統(tǒng)原理設(shè)計一套仿樹狀支撐結(jié)構(gòu)的生成方法，該樹狀支撐結(jié)構(gòu)對稱生長，穩(wěn)定性好，但是支撐結(jié)構(gòu)與模型接觸點坐標(biāo)計算復(fù)雜，且不易去除。

本文設(shè)計實現(xiàn)一種自動生成的柱狀支撐結(jié)構(gòu)，首先對STL文件建立拓?fù)浣Y(jié)構(gòu)，劃分出獨立的待支撐區(qū)域，然后通過邊長自適應(yīng)法獲得平面中的采樣點，進(jìn)而通過射線與面相交法獲得三維模型表面的待支撐點集。為了提高模型整體穩(wěn)定性，本文的支撐結(jié)構(gòu)盡量從XOY平面生成。最后對支撐結(jié)構(gòu)進(jìn)行調(diào)整，方便從模型表面剝離。

1 STL文件拓?fù)浣Y(jié)構(gòu)建立

STL文件由美國3D System公司提出的一種CAD系統(tǒng)與快速成型系統(tǒng)之間的數(shù)據(jù)交換格式，由于它格式簡單，對三維模型建模方法沒有特定的要求，因此得到廣泛的應(yīng)用，成為快速成型系統(tǒng)中事實上的標(biāo)準(zhǔn)文件輸入格式［8］。STL文件只存放CAD模型表面的離散三角形面片信息，并且三角面片信息是無序存儲的。

由于STL文件中三角面片信息都是無序存放的，且存在大量的冗余數(shù)據(jù)。由于缺乏各面片間的鄰接關(guān)系，如果尋找某個三角面片的相鄰面片時需要進(jìn)行大量計算，非常不利于后續(xù)待支撐面片的合并。因此需要建立STL文件的拓?fù)湫蛄?，本文設(shè)計的拓?fù)浣Y(jié)構(gòu)如圖1所示。

圖1 STL文件拓?fù)浣Y(jié)構(gòu)示意圖

首先需要建立一個存儲無重復(fù)頂點的點表，由于在STL文件中相鄰三角形面片共用兩個頂點，因此STL文件中存儲大量的冗余頂點坐標(biāo)。建立點表的目的是為了消除冗余信息，每個頂點坐標(biāo)只存儲一次，減少計算量。傳統(tǒng)方法通過先判斷兩個頂點坐標(biāo)是否完全一致，不一致則存儲到點表的方法效率太低，會浪費大量時間。由于用哈希表存儲頂點的坐標(biāo)檢索運算平均可能達(dá)到常數(shù)的時間，又能通過哈希函數(shù)的運算快速找到冗余的頂點坐標(biāo)［9］，因此本文把頂點的坐標(biāo)作為關(guān)鍵字，通過哈希函數(shù)快速計算出頂點對應(yīng)的哈希地址。哈希地址沖突時說明兩頂點坐標(biāo)相同，不需要存儲到點表中。

然后建立存儲所有三角面片點信息的面表，面表中不直接存儲點坐標(biāo)信息，而是存儲該點坐標(biāo)在點表中的索引位置。同時建立與面表對應(yīng)的法向量表。正確的STL數(shù)據(jù)模型必須滿足如下一致性規(guī)則:1)相鄰兩個三角形之間只有一條公共邊，即相鄰三角形必須共享兩個頂點;2)每一條組成三角形的邊有且只有兩個三角形面片與之相連。因此可以通過兩個面片存儲的點坐標(biāo)索引值是否有兩個相同而判斷兩個三角面片是否相鄰，可以得到面片的鄰接面片索引值。這樣當(dāng)有需要時可以通過面表可以直接找到對應(yīng)頂點的索引，也可以快速找到相鄰的面表索引，計算機(jī)處理速度更快，可以更快捷的得到需要的信息。

2 待支撐面片提取與快速合并

2.1 臨界角定義

在FDM技術(shù)中由于材料自身的粘性作用，在一定的傾角范圍內(nèi)，成型表面不需要添加支撐。計算所有三角面片的法向量n與Z軸正方向之間的夾角γ如圖2所示，本文測得打印機(jī)的臨界角度為α，如果γ＞α，則該三角面片為待支撐面片。由于不同打印機(jī)，不同打印材料，以及不同的打印參數(shù)的影響，臨界角并不是一個固定的值。本文以Smart-Maker打印機(jī)使用PLA材料進(jìn)行實驗。通過實驗結(jié)果比較，臨界角α=40°比較合適。

圖2 臨界角示意圖

2.2 待支撐面片快速合并

通過計算臨界角，得到的待支撐三角面片都是互相獨立的，為了合理添加支撐結(jié)構(gòu)和減少后期計算量，需要將獨立的三角形面片按接鄰關(guān)系連接起來，得到獨立的待支撐區(qū)域。面片合并采用的方法為種子擴(kuò)散法［10］如圖3所示。取待支撐面片集合中的第一個待支撐面片a作為種子面片，存入種子表，然后使用上一小節(jié)STL文件拓?fù)浣Y(jié)構(gòu)建立算法得到的面片鄰接表，從中快速找到a面片的3個相鄰面片b、c、d，分別判斷這3個相鄰面片是否在待支撐面片集合中，如果存在，則將該相鄰面片存入種子表，并將a面片從待支撐面片集合中刪除，如果3個相鄰面片都不在待支撐面片集合中，則代表a面片是一個孤立的待支撐面片。然后繼續(xù)尋找種子表中的其他種子的相鄰三角面片，直到種子表中所有種子都查找過為止，一個獨立的待支撐區(qū)域查找完成，重復(fù)上述方法，直到待支撐面片集合為空時，所有待支撐區(qū)域全部查找完畢。

圖3 種子擴(kuò)散法示意圖

3 支撐點采樣

通過上節(jié)的計算可以得到若干個獨立的待支撐區(qū)域，若對每個待支撐區(qū)域的所有待支撐面都添加支撐，則會導(dǎo)致支撐過密難以去除的問題。因此對懸空區(qū)域進(jìn)行采樣，獲得少量待支撐點是非常必要的。但是對于某一處懸空區(qū)域，如果采樣點過少，則不能保證模型正常成型。若是采樣點過多，雖然可以很好的保證模型成型，但是支撐難以去除而且浪費大量材料。因此采樣點的數(shù)目應(yīng)該在一個合理的范圍之內(nèi)，既能保證模型正常成型，又能節(jié)約材料。由于在三維空間中進(jìn)行重采樣需要進(jìn)行大量的計算，會嚴(yán)重降低算法的效率，因此本文采樣算法在懸空區(qū)域的投影區(qū)進(jìn)行，然后通過計算得到對應(yīng)的懸空面上的點。

3.1 邊長自適應(yīng)采樣法

柵格采樣是最常用的方法，將待支撐區(qū)域的三角面片坐標(biāo)像平面進(jìn)行投影，取得投影區(qū)域的X，Y軸的最大最小值，繼而獲得待支撐投影區(qū)域的最小矩形包圍盒。平面投影區(qū)域內(nèi)通過給定采樣間距d將投影區(qū)域柵格化，然后在每個柵格內(nèi)選取對應(yīng)的點。但是該方法由于間距d為給定的固定值，矩形包圍盒的長寬可能不是d的整數(shù)倍，因此采樣時會存在誤差。并且當(dāng)投影矩形一條邊小于間距d，而另一條邊大于間距d時，短邊會被忽略，影響待支撐點的選取。

邊長自適應(yīng)采樣是在柵格采樣的基礎(chǔ)上改進(jìn)而來，柵格采樣基于固定的采樣間距，而邊長自適應(yīng)采樣的間距根據(jù)邊長不同是動態(tài)變化的。對于一個投影區(qū)域，需要找到最合理的采樣點數(shù)N，既可以使模型正常成型，又能盡可能的減少支撐數(shù)量。假設(shè)材料在沒有支撐下保持不變形的最長打印長度為dmax，因此為了避免誤差，我們認(rèn)為在投影矩形的X，Y邊上的最大采樣數(shù)目為:

其中，∏表示向上取整.因此X，Y邊的采樣距離分為:

此時可以在投影矩形中得到 Nx，Ny個采樣點 (xi，yi):

對于一條邊小于dmax，而另一條邊遠(yuǎn)大于dmax的狹長投影矩形的情況，我們認(rèn)為不應(yīng)該直接將短邊忽略掉。因為如果切片時沿長邊方向切片時，打印頭沿長邊運動，那這樣會因為支撐點不足影響模型成型。因此對于這種情況我們規(guī)定長邊采樣距離正常取值，短邊采樣距離應(yīng)為短邊長度的一半。

3.2 局部最低點采樣法

上一節(jié)邊長自適應(yīng)采樣法得到一組位于柵格交點上的采樣點，這種采樣點分布的優(yōu)點是排列整齊，支撐結(jié)構(gòu)之間距離相同。但是在實際打印過程中，在某一區(qū)域內(nèi)切片軟件一般從該區(qū)域的最低點開始切片，支撐結(jié)構(gòu)在該區(qū)域的最低點下方生成相對比較合理。而上一小節(jié)的算法得到的采樣點中可能會丟失局部最低點，局部最低點采樣法在邊長自適應(yīng)采樣法的基礎(chǔ)上改進(jìn)而來。首先根據(jù)邊長自適應(yīng)采樣法獲得投影矩形各邊的采樣距離，得到采樣?xùn)鸥?，然后將投影下來的各三角面片的頂點按著柵格邊距進(jìn)行劃分，選擇一個柵格中高度最低的三角面片作為采樣點。當(dāng)柵格內(nèi)最低點采樣完成后，需要對網(wǎng)格最低點進(jìn)行篩選優(yōu)化，因為可能出現(xiàn)兩個最低點距離非常近的情況。這時需要刪除掉一個點，選擇柵格中心點作為新的采樣點。該算法的具體流程如下。

Step1:將最大采樣距離設(shè)為dmax2，根據(jù)邊長自適應(yīng)采樣法得到各邊的采樣距離，創(chuàng)建存儲采樣點的數(shù)組supportP;

Step2:根據(jù)各邊采樣距離，劃分網(wǎng)格;

Step3:將待支撐三角面片的頂點坐標(biāo)按著柵格邊距劃分到各個柵格中;

Step4:從坐標(biāo) (xmin，ymin)的柵格開始遍歷，尋找每個柵格中高度最低的面片頂點作為采樣點，加入到數(shù)組supportP中。繼續(xù)尋找其他柵格中的最低點，如果某個柵格中的最低點與supportP數(shù)組中的某一點距離非常近，小于dmin，則放棄該點，選擇該網(wǎng)格的中心點作為采樣點加入supportP數(shù)組;否則將柵格中最低點加入supportP數(shù)組中。

采用上述方法得到的采樣點可以保證選到該待支撐區(qū)域內(nèi)的最低點，雖然該方法的采樣點不如邊長自適應(yīng)采樣法得到采樣點分布的均勻，但是該方法有效的提升了支撐結(jié)構(gòu)生成位置的合理性。

3.3 檢測點與三角形位置

在矩形區(qū)域內(nèi)取得采樣點坐標(biāo)后，需要判斷采樣點是否位于懸空區(qū)域投影的內(nèi)部。由于計算平面中某個點與不規(guī)則圖形的位置比較麻煩，本文提出一種簡化算法，將其轉(zhuǎn)化為判斷采樣點與三角形的位置關(guān)系。通過上文已經(jīng)獲得所有待支撐三角面片坐標(biāo)值，以一個待支撐三角面片為例，如圖4所示，其坐標(biāo)值 (A，B，C)，并且待支撐面片垂直向XOY平面進(jìn)行投影，因此計算可得三角面片在XOY投影坐標(biāo) (A’，B’，C’)。采樣點是否在投影區(qū)域的判斷，就可簡化為判斷每個采樣點是否在相應(yīng)的三角面片的投影三角形內(nèi) (A’，B’，C’)即可。

圖4 三角面片投影示意圖

本文采用重心法［11］判斷點是否在三角形內(nèi)部。如圖5所示，三角形3個點ABC在同一水平面上，若選擇A為起點，則B點相當(dāng)于在AB方向移動一段距離得到，同樣C點相當(dāng)于在AC方向移動一段距離得到。因此，對于該三角形內(nèi)任意一點都可以有公式得到:

因此，如果點p在三角形內(nèi)部需要滿足以下條件:

通過計算得到U，V后，比較是否滿足以上條件，若滿足則點在三角形內(nèi)部，若不滿足，則點不在該三角形內(nèi)部。

圖5 三角形向量表示圖

3.4 射線與三角面片交點

通過上節(jié)算法證明采樣點p在投影三角形內(nèi)部，但是由于支撐需要添加到模型表面，因此需要計算出采樣點在模型表面的坐標(biāo)值。由圖可知，三角形A’B’C’內(nèi)的采樣點一定會在空間三角形ABC內(nèi)部，而且X，Y坐標(biāo)不變，只是Z軸坐標(biāo)發(fā)生變化。因此，求采樣點在三維模型表面坐標(biāo)簡化為求過采樣點p沿Z軸正方向的射線與三角形ABC的交點坐標(biāo)，射線與三角形的交點公式如下。

通過化簡求出t，u，v然后帶入公式即可求出射線與三角形的交點，該點即為待支撐點。

4 支撐結(jié)構(gòu)生成

通過對每個投影區(qū)域的計算，可以得到待支撐點集P，支撐結(jié)構(gòu)的生成就是建立在待支撐點集P的基礎(chǔ)上。陳巖等［5］實現(xiàn)的柱狀支撐結(jié)構(gòu)將部分支撐生長在模型表面，這樣雖然具有減少支撐結(jié)構(gòu)、縮短打印時間的優(yōu)點，但是由于模型表面本身不平坦，并且與支撐結(jié)構(gòu)接觸面較小等原因會導(dǎo)致支撐結(jié)構(gòu)不穩(wěn)定。打印模型是一個連續(xù)的過程，某一部分支撐的不穩(wěn)定會極大增加模型打印失敗的概率。若是模型打印失敗，那么前期為了節(jié)省材料和時間而做的工作就是無意義的，因此為了提高模型打印成功率，本文算法增加少量的支撐結(jié)構(gòu)和打印時間從而提高模型穩(wěn)定性。所以本文算法盡可能避免支撐結(jié)構(gòu)在模型表面生成。對于每一個待支撐點p∈P，尋找一個支撐基點q，生成一個以p，q為頂點的柱狀支撐結(jié)構(gòu)。基點的選取，本文算法首選在XOY平面上處于p點正下方的q點作為支撐基點。但是這樣選擇的pq支撐體，可能會與模型相交，還是會出現(xiàn)支撐結(jié)構(gòu)生長在模型表面的問題?；谶@個問題本文提出一個算法，保證支撐體不與模型相交的前提下，在XOY平面重新選擇一個支撐基點q’，使支撐體pq’既不與模型相交，而且pq’長度是在所有選擇中最短的。

4.1 支撐結(jié)構(gòu)與模型相交檢測

假設(shè)pq支撐結(jié)構(gòu)與模型相交，q是在XOY平面上處于p正下方的一個支撐基點。為了避免支撐結(jié)構(gòu)與模型相交，需要在XOY平面重新選擇一個支撐基點q’，由上文可知模型不需要支撐能夠成型的臨界角α=40°。因此對于重新選擇的支撐基點q’，pq’的傾斜角度也必須小于α，考慮到pq’為支撐結(jié)構(gòu)，還需要為模型提供有效支撐，本文將pq’的最大傾斜角度定義為β=30°。所以q’點的選擇范圍是以p為頂點，以γ為半頂角，高度為p點z軸高度的圓錐的底面圓內(nèi)部。如圖6所示。

圖6 支撐結(jié)構(gòu)有效生成區(qū)域

通過上圖可知，可選擇的支撐基點q’包含在以q為圓點，以r為半徑的圓內(nèi).設(shè) p點的坐標(biāo)為 (x0，y0，z0)，pq’的距離公式為:

本文要尋找既不與模型相交，同時支撐結(jié)構(gòu)長度pq’要盡可能小，即:

為了取值方便，x、y需要滿足的范圍分別為:

其中:d(x，y)函數(shù)表示重新選擇的支撐基點q’的坐標(biāo)位置，當(dāng)該點圓心距離小于等于圓的半徑r時，說明該點坐標(biāo)位于圓內(nèi)，符合要求，f(x，y)函數(shù)表示由q’點發(fā)出的沿pq’方向的射線是否與模型存在交點，如果存在交點函數(shù)值為1，不存在交點函數(shù)值為0。

所以針對該算法的數(shù)學(xué)模型如式 (7)所示:

最后針對該數(shù)學(xué)模型求出相應(yīng)的解，即是新的基點q’的坐標(biāo)。

4.2 支撐結(jié)構(gòu)優(yōu)化

由于支撐結(jié)構(gòu)并不屬于模型中的一部分，是為了保證模型能夠成功打印人為添加的部分。因此在模型打印完成后，支撐結(jié)構(gòu)需要去除。為了提高模型表面質(zhì)量，同時保證支撐部分比較容易去除，最有效的方法就是減少支撐與模型的接觸面積。因此本文對與模型直接接觸的支撐結(jié)構(gòu)頂部做削尖處理。其次，支撐結(jié)構(gòu)本身的穩(wěn)定性與其長度成反比。陳巖［5］等總結(jié)出一個支撐結(jié)構(gòu)寬度與長度的關(guān)系公式。

其中:w為支撐結(jié)構(gòu)寬度 (單位:mm)，l為支撐結(jié)構(gòu)長度 (單位:mm)。

最后增大支撐結(jié)構(gòu)與平臺的接觸面積，形成一個底座，因為接觸面積越大越穩(wěn)定，不容易發(fā)生翹邊等現(xiàn)象。

5 實驗結(jié)果

本文對不同模型通過本算法生成支撐結(jié)構(gòu)，并與平常使用的Cura軟件生成的支撐結(jié)構(gòu)進(jìn)行對比。所有模型均是在SmartMaker打印機(jī)上采用PLA塑料打印，打印機(jī)參數(shù)設(shè)置完全一樣情況下進(jìn)行打印。我們將本文算法生成的支撐結(jié)構(gòu)與Cura軟件自帶的支撐算法進(jìn)行對比，圖7展示了本文算法生成的支撐結(jié)構(gòu)與Cura軟件生成的支撐結(jié)構(gòu)實際打印結(jié)果。

圖中 (a)列為Cura軟件生成的支撐情況，(b)列為本文算法生成的支撐情況。本文主要材料消耗、穩(wěn)定性、易剝離性3個方面比較兩個算法的效果。

圖7 模型打印效果圖

通過上表實驗結(jié)果可以看出本文算法在消耗材料方面相比Cura軟件平均減少15%，而在穩(wěn)定性方面，兩者都很穩(wěn)定，可以有效的形成對模型的支撐。在易剝離性方面，由于本文算法對支撐結(jié)構(gòu)進(jìn)行了削尖處理，有效的減少了支撐結(jié)構(gòu)與模型的接觸面積，并且支撐結(jié)構(gòu)盡量避免在模型表面生成，因此支撐結(jié)構(gòu)只有削尖的一端與模型接觸，所以本文算法在較容易去除支撐的同時，提高了模型表面的質(zhì)量。Cura軟件生成的支撐結(jié)構(gòu)與模型接觸面積非常大，很難去除，并且對模型表面質(zhì)量損害比較嚴(yán)重。綜合對比，本文算法相比Cura軟件生成的支撐結(jié)構(gòu)，有用料少，穩(wěn)定性高，易剝離，對模型質(zhì)量損害小的優(yōu)點。

表1 本文算法與Cura算法對比表

6 結(jié)束語

本文通過哈希函數(shù)建立了STL文件的拓?fù)浣Y(jié)構(gòu)，通過三角面片法向量與打印正方向夾角與臨界角大小比較獲得待支撐三角面片，提出基于邊長自適應(yīng)法和射線與三角面片相交法得到待支撐點集，并改進(jìn)支撐結(jié)構(gòu)，使支撐結(jié)構(gòu)與模型接觸面積減小、不與模型相交，提高了模型表面質(zhì)量。

本文算法生成的支撐結(jié)構(gòu)雖然具有穩(wěn)定性好、易去除、用料少等優(yōu)點，但是也存在一些待改進(jìn)的地方，比如當(dāng)支撐結(jié)構(gòu)比較多時，會增加打印頭空移時間，會相應(yīng)的增加打印時間，下一步將針對以上問題進(jìn)行改進(jìn)優(yōu)化。