逆向幾何求交方法的STL模型分層算法

段明德，鄭立霞，李明利，張壯雅

(1.河南科技大學(xué) 機(jī)電工程學(xué)院，河南 洛陽 471003；2.洛陽LYC軸承有限公司，河南 洛陽 471003)

?

逆向幾何求交方法的STL模型分層算法

段明德1，鄭立霞1，李明利2，張壯雅1

(1.河南科技大學(xué) 機(jī)電工程學(xué)院，河南 洛陽 471003；2.洛陽LYC軸承有限公司，河南 洛陽 471003)

摘要：為了解決三維網(wǎng)格曲面(STL)模型分層算法分層計算效率不高的問題，提出了一種可實現(xiàn)STL曲面模型快速分層的逆向幾何求交算法。通過遍歷三角面片頂點坐標(biāo)，確定模型最小包圍盒。利用分層面分割STL模型，散列表數(shù)據(jù)結(jié)構(gòu)記錄分層面坐標(biāo)。在此基礎(chǔ)上，計算連接截交線，生成模型輪廓，實現(xiàn)模型的快速分層。實驗結(jié)果證明：該算法可對各種結(jié)構(gòu)的STL模型進(jìn)行分層，具有可靠、穩(wěn)定和效率高等優(yōu)點。

關(guān)鍵詞：幾何求交；三角網(wǎng)格；STL模型；快速分層

0引言

隨著制造業(yè)的迅速發(fā)展，快速成型作為新興技術(shù)越來越受到重視。高效準(zhǔn)確地得到網(wǎng)格模型是分層制造的關(guān)鍵[1]，因此，分層問題一直是三維網(wǎng)格曲面(stereolithogrphy interface,STL)模型分層算法研究中的熱點。文獻(xiàn)[2]對三角網(wǎng)格和四面體的體素化算法做了研究。文獻(xiàn)[3]在對STL模型進(jìn)行分層計算時，將三角面片的順序關(guān)系融于交點鏈表中，以節(jié)省系統(tǒng)資源和提高計算效率。文獻(xiàn)[4]基于數(shù)學(xué)形態(tài)學(xué)運算和拓?fù)湟?guī)則消除網(wǎng)格中的拓?fù)淙毕荩行У靥岣吡司W(wǎng)格質(zhì)量。文獻(xiàn)[5]基于測地距離和圖割法對網(wǎng)格進(jìn)行分割，具有一定的適用性。文獻(xiàn)[6]對三角網(wǎng)格現(xiàn)有的分割算法進(jìn)行了綜合性的總結(jié)。文獻(xiàn)[7]改善了三角網(wǎng)格中的半徑頂點，而不改變之間的聯(lián)系，提高了建模精度，改善了3D打印產(chǎn)品的質(zhì)量。文獻(xiàn)[8]對任意三角網(wǎng)格表面線段的連續(xù)性和可見性進(jìn)行了研究，并通過分配所有正交點和三角網(wǎng)格表面單元提高了計算效率。STL模型等厚分層算法最常見的有基于模型毗鄰關(guān)系的分層算法和基于三角面片幾何特征的分層算法。當(dāng)前者出現(xiàn)分層面與三角面片的公共點相交時，將無法確定下一個待分層三角面片，造成在計算過程中的算法失敗而無法進(jìn)行計算。后者在分層時雖然省去了不相交三角面片的計算，但是這種算法仍然沒有明確的劃分標(biāo)準(zhǔn)，分層面與三角面片位置關(guān)系的無效判斷依然不可避免。

綜上所述，在對STL模型進(jìn)行分層方面，還存在著分層繁瑣的問題。本文針對此問題進(jìn)行了研究，在分層計算時，采用幾何求交逆向算法，除去不相交三角面片，處理頂點與分層面相近的三角面片。通過相交三角面片搜尋與之存在交點的分層面求取截交線，并運用實例驗證了此方法的可行性與有效性，可為快速成型分層制造提供理論依據(jù)和技術(shù)支持。

1算法描述

為了解決STL模型在分層時出現(xiàn)的效率不高和算法失效等問題，本文提出了基于三角面片幾何特征逆向算法，在讀取STL模型過程中，建立模型最小包圍盒，確定分層范圍，選擇Z向為分層方向進(jìn)行討論。模型分層示意圖見圖1。如圖1所示，矩形DEFG為包圍盒平行Z向的截面圖形，在分層過程中，首先設(shè)置分層厚度t，記錄所有分層面，除去與相應(yīng)分層面不存在相交的三角面片，如圖1中的分層面s1除了與三角面片a1、a4和a5相交之外，與三角面片a2和a3并不相交，在進(jìn)行s1的計算時，除去三角面片a2和a3。然后統(tǒng)一用相交三角面片搜尋與其相交的分層面，計算截交線段，并處理錯誤輪廓信息，如圖1中分層面s2與三角面片a1、a2、a3、a4和a5的頂點均相交的情況，處理結(jié)果只有一個交點。最后連接截交線段，生成截面封閉輪廓線，為了提高搜索分層面和計算截交線效率，用散列表的數(shù)據(jù)形式表達(dá)分層面，Z向的各封閉輪廓即實現(xiàn)了STL模型的分層。圖2為分層模型截面示意圖，其中：s1,s2,s3,…,si對應(yīng)的截面分別為f1,f2,f3,…,fi。其他方向的分層亦如此。

圖1 模型分層示意圖圖2 分層模型截面示意圖

2算法實現(xiàn)

2.1求取分層面

在獲得分層面之前，首先確定分層的范圍，即模型的最小包圍盒。在讀取STL模型時，可得到模型的Z向最大值max{Z}和最小值min{Z}，以及模型的最大邊界點(xmax,ymax,zmax)和最小邊界點(xmin,ymin,zmin)。根據(jù)模型的最大邊界點和最小邊界點建立模型的最小包圍盒，即模型的分層范圍。給定分層厚度t，對STL模型從min{Z}開始進(jìn)行分層，直至max{Z}結(jié)束，分層面的計算如式(1)所示。將散列表用V表示，V中各分層面對應(yīng)的坐標(biāo)根據(jù)式(2)確定。

z=si，(i=0,1,2,…,n)；

(1)

(2)

其中：si為第i個分層面對應(yīng)的分層面坐標(biāo)值；t為分層厚度；i為第i個分層面對應(yīng)的序列值；max{Z}和min{Z}分別為Z向坐標(biāo)的最大值和最小值。

圖3　散列表結(jié)構(gòu)示意圖

分層過程中，每一次分層就有一組分層結(jié)果與分層面對應(yīng)，所以，為了方便后續(xù)計算，需要給V中的每一項加上一個指針Si，指針指向分層結(jié)果存儲的區(qū)域，即指針Si指向si的分層結(jié)果，則可以將式(2)用圖3所示的散列表結(jié)構(gòu)形式表示。

2.2三角面片分層處理

在對STL模型分層時，在STL模型最小包圍盒內(nèi)，頂點Z向坐標(biāo)值最小 (min{Z})的三角面片先被分割，頂點Z向坐標(biāo)值最大(max{Z})的三角面片最后被分割。而當(dāng)三角形頂點Z向坐標(biāo)值的最大值小于分層面的Z向坐標(biāo)值或者頂點Z向坐標(biāo)值的最小值大于分層面的Z向坐標(biāo)值，三角面片與該分層面均無相交，在后續(xù)計算截交線時先把不與分層面存在交點的三角面片除去，提高程序計算的效率。為了除去不與分層面相交的三角面片，針對分層后的三角面片進(jìn)行兩次整合排序[9]。該處理不僅減少了對不相交三角面片的計算與判斷，而且還提高了計算效率，節(jié)省了對三角面片的存儲空間。

2.3逆向幾何求交計算截交線段

處理后的三角面片與相應(yīng)的分層面求取截交線段，為后續(xù)連接截交線段作準(zhǔn)備。采用逆向幾何求交算法計算截交線段，在包圍盒中按照一定順序依次選取三角面片；然后在V中查找與其相交的分層面；最后計算三角面片與分層面交點，得到每一層的截交線段。因此，如何在V中查找到與三角面片存在交點的分層面是計算的關(guān)鍵。

首先尋找分層面，主要是在V中尋找對應(yīng)的si的值，si與分層面一一對應(yīng)，因此只要確定si的值即可確定相應(yīng)分層面。此外，si與i一一對應(yīng)，確定了i即可得到對應(yīng)的si的分層序列值。假設(shè)第m個三角面片與分層面si相交，由圖2可知，三角面片am與分層面si相交的條件為：

(3)

將式(2)和式(3)聯(lián)立解得：

(4)

(5)

2.4修正錯誤輪廓信息

計算截交線過程中，會出現(xiàn)分層面與三角面片的頂點相距非常近的情況，利用式(5)進(jìn)行求解截交線時，會造成截交線計算誤差過大或者算法失效等問題。為提高算法健壯性，本文對三角面片的頂點接近分層面的3種情況進(jìn)行了分析與修正。圖4為三角面片的頂點接近分層面示意圖。

圖4　三角面片的頂點接近分層面示意圖

(Ⅰ)三角面片3個頂點有1個接近分層面，如圖4所示。當(dāng)計算三角面片a1與分層面si的截交線時，由于點距離分層面太近，會造成截交線求解失敗或誤差過大，但是截交線過于短小，甚至小到可以認(rèn)為頂點在分層面上的時候。此時的截交線因過小可以忽略不計，對最終截交線的封閉性和連接幾乎沒有影響。

(Ⅱ)三角面片中有2個頂點接近分層面，如圖4中頂點A和B距離分層面都很近，在計算分層面與三角面片a6的交點時可能出現(xiàn)2個交點或者1個交點，甚至沒有交點。但事實上，分層面與三角面片a6是沒有交線的，在計算截交線時會出現(xiàn)誤差。同理，與三角面片a6共AB邊的三角面片a5或許會出現(xiàn)類似的情況。在計算截交線的過程中可能會導(dǎo)致出現(xiàn)重邊和缺邊兩種錯誤。在同一分層中，若出現(xiàn)多個分層面與三角面片相交的這兩種情況，將會在后續(xù)的輪廓線連接中出現(xiàn)錯誤。

針對這兩種錯誤，采取近似平行邊判定方法來解決。比較三角面片任一條邊上兩頂點Z坐標(biāo)的差值△z，如果小于給定的值θ1，并且兩頂點所在邊與分層面的夾角(用邊的斜率|k|確定)小于給定值θ2，那么，就認(rèn)為是近似平行邊。否則，確定與此邊最近距離的分層面，并計算截交線。θ1取值為0<θ1≤1/2t，t為分層厚度，k的范圍是0<|k|≤1,可依據(jù)經(jīng)驗選取k=0.4，此時的三角面片中該邊與分層面的夾角大約為22°。

近似平行邊與最近距離的分層面層號的確定：假設(shè)三角面片中該邊兩頂點的Z向坐標(biāo)分別為z1和z2，如果maxZ-si<θ3(0<θ3≤1/2t)成立，那么si為最近分層面；反之，若maxZ-si>t-θ3成立，則i進(jìn)行i++運算，此時si+1為最近的分層面。

(Ⅲ)當(dāng)三角面片的形狀為細(xì)小狹長的三角形，且3個頂點都比較接近分層面時，如圖4中的三角面片a8所示，系統(tǒng)精度達(dá)不到此時的尺寸范圍，這樣的面片可以忽略不計，對整體的分層沒有影響，只需要計算與其共邊的其他三角面片，最后轉(zhuǎn)化為兩個頂點接近分層面的情況。

2.5連接截交線段

對相交的三角面片和分層面完成截交線的計算以后，得到的是一層層無序的線段，并沒有實現(xiàn)對STL模型的分層。對于每層的截交線段按照一定的順序連接起來，組成一層層獨立的封閉輪廓，這些封閉輪廓實現(xiàn)了STL模型的分層。圖5為直線與三角面片的相交實例。

圖5　直線與三角面片的相交實例

傳統(tǒng)的連接方式都是對端點的重復(fù)計算，即是兩共邊的三角面片，在連接截交線段時，截交線段的兩端點被重復(fù)計算。如圖5所示，當(dāng)連接a3、a4、a5與分層面si的交線段CD、DE、EF時，端點D、E均被計算兩次，在判定三角面片與分層面是否相交時，還要對端點進(jìn)行計算，增加了計算量，降低了算法的效率，因此，需要對該算法進(jìn)行改善。

當(dāng)三角面片a3、a4、a5與分層面si計算得到相交線CD、DE、EF后，并不直接計算交點，而是將其存放在指定的存儲容器內(nèi)，此時V的內(nèi)容也將發(fā)生改變。如圖5所示，當(dāng)a3、a4、a5與分層面si計算完成交線以后，將交線{(J,K),(I,K)}、{(I,M),(H,M)}存入V中。當(dāng)出現(xiàn)圖5所示的a1、a6與分層面si相交時，截交線段分別為{(A,A),(C,C)}和{(G,G),(J,K)}，a2同a1。

當(dāng)完成所有截交線段的計算以后，將每一層的截交線相連，構(gòu)成封閉輪廓，完成STL模型的分層，具體實現(xiàn)過程如下：

首先，判定散列表V是否為空，若為非空，則任取一個三角面片ai對應(yīng)的一組兩線段端點{(xi,yi),(xi+1,yi+1)}，并與對應(yīng)的相交分層面si求交線段，把得到的交線段存入新的容器V_P中。接著在V中取出與ai共(xi+1,yi+1)邊的ai+1所對應(yīng)的一組線段端點{(xi+1,yi+1),(xi+2,yi+2)}，并計算其與分層面si的交線段，將結(jié)果存入V_P中，由于V_P中已經(jīng)存有(xi+1,yi+1)，則將此次的(xi+1,yi+1)舍去，將(xi+2,yi+2)存入V_P中。以(xi+2,yi+2)為搜索對象在V中選取與(xi+2,yi+2)共邊的三角面片，直至不再有相同的端點，完成一個封閉環(huán)的求交計算。

然后，再判定散列表V是否為空，如果仍為非空，則說明存在多條封閉環(huán)，按照上述步驟循環(huán)計算，直至V中的元素為空，結(jié)束計算，完成所有的截交線的連接，各封閉環(huán)的集合實現(xiàn)了對STL模型的分層。

3實例驗證

針對上述算法進(jìn)行實例驗證，圖6為278 206個三角面片的人頭雕塑STL模型，設(shè)置分層厚度t為5 mm，對圖6模型進(jìn)行分層實驗，按照本文算法經(jīng)過分層、求交、計算并連接截交線段等程序，多次實驗得到側(cè)面局部分層效果圖，見圖7。由圖7可知：分層效果均勻性較好，沒有出現(xiàn)計算過程中算法失效或分層輪廓中斷的情況。此外，改變分層厚度，可以得到不同厚度的分層效果，算法方便靈活，無論是算法的計算量還是模型的分層質(zhì)量，都能夠較好地滿足要求，體現(xiàn)了本文算法的可靠性。為驗證本文算法的高效性和穩(wěn)定性，采用文獻(xiàn)[10]的分層算法對圖8所示的4個三角面片顯示的STL模型進(jìn)行分層，與本文算法進(jìn)行對比。其中，模型1、模型2、模型3和模型4的三角面片數(shù)量分別為16 776、40 152、128 800和230 206，分層厚度均設(shè)置為 5 mm。圖9為本文算法與文獻(xiàn)[10]算法分層時間對比圖。由圖9可知：兩種算法均能夠快速實現(xiàn)對各模型的分層計算，三角面片在10 000個以下時，兩種算法的分層時間相差不明顯；三角面片數(shù)量超出10 000個后，本文算法相對文獻(xiàn)[10]的計算效率提高了10%以上，具有較高的計算效率。文獻(xiàn)[10]的算法隨著三角面片數(shù)量的增多，分層時間迅速增加，時間變化率較大，而本文算法在三角面片數(shù)量較多時分層時間也有所增加，但時間變化率較小，且較為穩(wěn)定，表明本文算法的穩(wěn)定性較好。

圖6人頭雕塑STL模型

圖7側(cè)面局部分層效果

圖8 　STL三角網(wǎng)格模型

圖9　本文算法與文獻(xiàn)[10]算法分層時間對比

4結(jié)論

(1)建立了空間散列表索引結(jié)構(gòu)，可對各種STL模型進(jìn)行分層，算法適應(yīng)性強(qiáng)。

(2)除去了不相交三角面片計算量，提高了計算效率，節(jié)省儲存空間。

(3)輪廓誤差的分析處理，明確了三角面片與分層平面位置關(guān)系，降低了計算時無效判斷使程序終止計算的效率。

參考文獻(xiàn)：

[1]孫殿柱,朱昌志,李延瑞.三角網(wǎng)格曲面模型快速分層算法[J].北京航空航天大學(xué)學(xué)報(自然科學(xué)版),2010,36(3):279-282.

[2]朱曉濤.面向正則體積顯示的三維模型體素化研究[D].杭州:浙江大學(xué),2013:28-45.

[3]王素,劉恒,朱心雄.STL模型的分層鄰接排序快速切片算法[J].計算機(jī)輔助設(shè)計與圖形學(xué)報,2011,23(4):600-606.

[4]蔣恒恒,李奇敏,湯寶平.基于數(shù)學(xué)形態(tài)學(xué)與拓?fù)湟?guī)則的三角網(wǎng)格修補(bǔ)算法[J].機(jī)械工程學(xué)報,2013,49(1):148-155.

[5]劉磊.三維網(wǎng)格特征提取與分割[D].上海:華東師范大學(xué),2015:42-50.

[6]董洪偉.三角網(wǎng)格分割綜述[J].中國圖像圖形學(xué)報,2010,15(2):181-193.

[7]BOSCHETTO A,BOTTINI L.Triangular mesh offset aiming to enhance fused deposition modeling accuracy[J].International journal of advanced manufacturing technology,2015,80(1):99-111.

[8]HOLGATE N,JOLDES G R,MILLER K.Efficient visibility criterion for discontinuities discretized by triangular surface meshes[J].Engineering analysis with boundary elements,2015,58:1-6.

[9]王春香,郝志博.快速成型技術(shù)STL模型等厚分層算法研究[J].機(jī)械設(shè)計與制造,2014(4):133-136.

[10]王春香,李振華.STL模型分層算法的優(yōu)化及應(yīng)用[J].機(jī)械設(shè)計與制造,2013(3):87-90.

基金項目：河南省重點科技攻關(guān)基金項目(152102210281);河南省高等學(xué)校重點科研基金項目(16A460017);河南科技大學(xué)青年科學(xué)基金項目(2015QN005)

作者簡介：段明德(1966-),男,河南洛陽人,教授,碩士，碩士生導(dǎo)師,主要研究方向為CAD/CAM/CAE逆向工程.

收稿日期：2016-01-31

文章編號：1672-6871(2016)05-0011-05

DOI:10.15926/j.cnki.issn1672-6871.2016.05.003

中圖分類號：TP391.4

文獻(xiàn)標(biāo)志碼：A