一種快速3D打印分層方向確定算法

羅楠,王泉,劉紅霞

(西安電子科技大學計算機學院,710071,西安)

?

一種快速3D打印分層方向確定算法

羅楠,王泉,劉紅霞

(西安電子科技大學計算機學院,710071,西安)

針對減少3D打印等分層制造應用中成型的模型實體與理論模型之間的體積偏差,提出一種快速精確的分層方向確定算法。通過分析體積偏差的產生原因和理論模型,明確了統一分層厚度下使體積偏差最小的分層方向,是與模型面片面積加權法向量內積絕對值之和最小的單位向量,將最優方向選取問題轉化為最小絕對偏差線性回歸問題。用最小二乘準則近似最小絕對偏差準則,并用基于該準則的主成分分析方法,對加權法向量的散列矩陣進行特征值分解,從特征向量中快速確定最優的分層方向。針對多個不同復雜程度的模型進行評估實驗,結果表明,該算法能在保證精度的前提下將運算量減少80%,適合于復雜精細模型的分層制造應用。

3D打印;體積偏差;分層方向;線性回歸;主成分分析

3D打印是快速成型技術[1]的一種,采用分層制造的思想,將三維模型沿分層方向離散為一組二維圖形,即一組薄層(也被稱為切片或者分層),逐層加工形成三維模型實體,這種技術已被引入到許多實際應用當中[2-3]。STL模型[4]作為為快速成型技術服務的文件格式,被3D打印技術采用,但STL數據無法直接作為3D打印的輸入數據,必須通過分層軟件轉化為打印機可直接處理的數據形式。決定分層結果的因素有分層方向和分層厚度。分層厚度指相鄰兩個切片之間的縱向距離,分層方向即切片平面的法向量方向,分層厚度越小,構建的模型越細膩,構建時間也就越長。在分層厚度給定時,分層方向唯一決定模型構建的效果。由于分層厚度受打印機硬件條件限制,只能在一定范圍內調整,需根據實際情況折中處理,因此本文只關注分層方向的確定。

影響分層方向的因素有多個,如表面精度、支撐體積、構建時間、總消耗等。其中表面精度指的是構建的模型實體與理論模型的接近程度,是衡量成型質量的最重要指標。支撐體積用來支撐模型中傾斜或懸空的部分,保證成型的順利進行。對于結構簡單的部件,用戶一般可以根據經驗選擇與某坐標軸平行的方向作為分層方向,但對于面片眾多、結構復雜的模型則難以判斷,必須根據一定標準確定最優的分層方向。現有算法一般選取單個或多個因素構造目標函數,然后從候選方向中選擇使目標函數值最小的方向作為最優分層方向。單目標算法[5-9]以最主要的單一因素如體積偏差或表面平整度為目標函數,可以得到單一目標下的最優方向。多目標算法[10-13]選取多個因素如表面精度、構建時間、材料消耗等作為優化目標確定折中的分層方向,每個目標所占比重根據經驗確定。在候選方向預定義方面,一般由用戶根據經驗指定若干方向,或對方向空間進行采樣獲取一定數量候選方向,或使用模型表面面片法向量等幾何特征作為候選方向。這些方法基本都是基于遍歷枚舉思想,需對候選方向逐個計算目標函數,復雜度高,只適用于幾何特征簡單的規則模型,對于由大量三角面片組成的復雜模型,往往時間效率不能滿足要求,并且由于預定義的方向是有限的,總會有一定機率錯過最好的方向。因此,尋找一種快速精確的分層方向確定算法尤其必要。

本文以最少體積偏差為目標,提出一種快速分層方向確定算法。通過分析體積偏差的產生原因和數學模型,明確模型面片面積對體積偏差的影響,指出在統一分層厚度下,最優分層方向是與面積加權法向量內積絕對值之和最小的單位向量,并將問題進一步轉化為最小絕對偏差線性回歸問題;使用最小二乘準則替代最小絕對偏差準則,借助主成分分析和矩陣分解相關理論技術,近似估計線性回歸參數,快速確定最優分層方向。算法無需預定義初始候選方向,而是根據模型本身的特征自適應獲得最優分層方向,避免了遍歷候選方向帶來的計算量,很大程度上提高了時間效率,而且保持了很好的模型構建精度。

1 體積偏差

在3D打印或者其他快速成型技術中,模型的體積偏差定義為構建模型使用的材料與理論模型需要的材料之間的差值。體積偏差主要影響模型的構建精度,體積偏差越小,構建的模型表面與理論模型表面越接近,模型實體的表面精度就會越高。分層處理時在模型表面上產生的階梯效應[14]是引起模型誤差體積的直接原因。

1.1 誤差分析

3D打印采用的是分層制造的原理,在進行構建時,打印機并不會制造出與理論模型完全相同的面片,而是通過分層切割的方式用一系列階梯面近似表達每個面片(類似樓梯)。如圖1所示,使用統一的分層厚度l對表面Fi進行分層,圖中灰色塊ΔV代表相鄰兩個分層在該表面上產生的階梯效應,稱作誤差體積。理論上來說,分層厚度越小,制造的表面越接近理論表面,誤差體積越小,模型構建就越精確,但由于設備精度的限制,分層厚度只能取有限值,在分層厚度確定的情況下,分層方向唯一決定誤差體積的大小。

(a)面片Fi分層情況

(b)側面剖視圖圖1 分層時的階梯效應

圖1b為面片Fi分層情況的側面剖視圖,圖中虛線即表面的理論側視線,階梯實線表示實際的分層效果,灰色小三角代表分層時產生的局部體積偏差,右圖為放大效果。圖中d為分層方向單位向量,ni為三角形面片Fi的單位法向量,l表示分層厚度,θi為ni與d之間的夾角,ΔF表示誤差塊在面片Fi上所占面積,ci為面ΔF上的高,即

ci=l|cosθi|;cosθi=d·ni

(1)

誤差塊ΔV的體積

ΔV=(1/2)ciΔF

(2)

面片Fi分層時所產生的體積偏差

Vi=∑ΔV=(1/2)ciFi

(3)

式中Fi也代表該面片的面積。整個模型分層產生的誤差體積

(4)

令Ni=Fini為表面Fi的面積加權法向量,此時誤差體積表示為

(5)

從式(5)可以看出,體積偏差與分層厚度l成線性關系,l越小,則對應的體積偏差也越小。在l給定的情況下,V取決于分層方向與面片加權法向量Ni內積絕對值之和,而每個面片的面積加權法向量Ni在模型給定時即已確定,所以體積偏差就取決于分層方向。

因此,要獲得最小的分層誤差體積,只須確定一個分層方向,使得該方向與所有加權法向量的內積絕對值之和最小即可。

1.2 數學模型

由于分層方向為單位向量,其與加權法向量的內積絕對值即為加權法向量到分層方向上的投影長度值,因此上述問題可另述為:已知模型的加權法向量集Nn={N1,N2,…,Nn},求單位向量d,使得Nn中所有向量到d的投影長度之和最小。

圖2為加權法量在分層方向的投影示意圖,為方便觀察理解,只畫出了幾個向量,其余的向量只標出了終點位置。從圖中可看到,法向量Ni到方向d的投影長度為ξi。

圖2 加權法向量到分層方向投影

記d=(a,b,c)T,Ni=(xi,yi,zi),Nn到d的投影長度之和為L,則有

(6)

結合式(5)可知,L取最小值時體積偏差V最小。

考慮線性回歸模型

yi=xiβ+εi,i=1,…,n

(7)

式中:(xi,yi)為第i個觀測數據;β為回歸系數向量;εi為未觀測到的誤差。對于所有觀測數據,使得總體擬合誤差最小

(8)

可見分層方向的確定只取決于加權法向量的分布情況。已知加權法向量分布,與法向量內積絕對值之和最小的分層方向確定問題,等價于一個最小絕對偏差的線性回歸問題。

2 解決方案

2.1 最小二乘近似

在線性回歸領域,最小絕對偏差方法(LAD)和最小二乘方法(LS)常被用來進行回歸模型的統計分析。兩種方法的誤差分析準則為

(9)

與LS方法不同,LAD方法只考慮殘差的一次方,故其所受異常點的影響小很多,能產生更為穩健的參數估計。然而,LAD方法并無解析最優解,為線性規劃問題,使用迭代方法求解,在樣本數量較大時,計算量很大,從而限制了該方法的應用和發展。相比LAD,LS方法包含完善的理論推理和方差分析方法,且存在唯一解析最優解,計算簡單、高效。

因此,本文使用最小二乘準則替代最小絕對偏差準則,進行線性回歸參數的近似估計。借助主成分分析(PCA)[16]和矩陣特征分解的相關理論和技術,可以非常快速地求出線性回歸參數,即分層方向。雖然使用最小平方準則會產生一些誤差,但算法的效率得到了很大的提升。

2.2 分層方向確定

PCA是統計學中一種通過減少數據集維度來簡化分析的技術。PCA的基本思想是從最小平方角度尋找一個最能代表數據的投影。

(10)

(11)

通過對矩陣A進行特征分解,可得兩個特征值λ1、λ2(λ1>λ2),以及對應的兩個特征向量e1、e2。e=e1時J達到最小值;e=e2時J達到最大值。

圖3 PCA方法的最小平方解釋

由圖3可知

(12)

將該結論擴展到三維歐式空間,如圖4所示。對于一個封閉三角網格模型來說,其中所有三角形的面積加權法向量之和為0,即加權法向量終點的均值位于坐標系原點o。對加權法向量集Nn應用PCA可求得一條過原點o的直線,使得所有法向量在該直線的投影平方和最小,該直線所在的方向即法向量散列矩陣的最小特征值對應的特征向量e3。

圖4 加權法向量集PCA示意圖

算法主要步驟如下。

(1)讀取STL模型M,計算M每個三角面片法向量;

(2)計算M每個三角面片面積,并根據面積依次更改法向量長度,得到加權法向量集Nn;

(3)依公式(11)計算Nn的散列矩陣A;

(4)對矩陣A進行特征值分解,得到3個特征向量e1、e2、e3;

(5)分別以e1、e2、e3為分層方向計算誤差體積,取其中最小誤差體積的方向作為最終分層方向。

由于面積加權法向量的均值位于坐標系原點,計算A時,可以使用更簡單的公式

(13)

省去計算均值的步驟。對矩陣A進行特征值分解,會得到3個特征值λ1、λ2、λ3(λ1>λ2>λ3)及對應的3個特征向量e1、e2、e3,按照采用的近似準則及PCA理論分析,應取向量e3作為分層方向。然而由于近似時存在的誤差,對于某些模型,以e3作為分層方向的結果略遜于e1或e2時的結果。因此,在算法實施時,需通過計算從3個特征向量中選擇最優的一個作為最終確定的分層方向,以保證算法的精度。

3 實驗結果

將本文的高效自適應分層方向確定算法與兩種常用算法進行了比較,分別是法向量遍歷算法和方向空間全局搜索算法[5],實驗中且稱為算法1和算法2。法向量遍歷算法使用模型中所有三角面片的法向量作為候選方向,空間采樣算法從方向空間中采樣一定數量的候選方向(實驗中取方向數m=18×18),而后對每個候選方向計算體積偏差,選擇最優方向。為了便于理解和比較,效仿空間采樣算法借助球坐標系,使用方位角(φ,θ),φ,θ∈[0°,180°)表示分層方向,如圖5所示。

圖5 分層方向球坐標表示

實驗從效率和精度兩個角度評估算法。3種算法應用于10個不同復雜程度的STL模型,比較確定的分層方向、體積偏差和運行時間。STL模型如圖6所示,從上到下從左到右依次編號為1～10,其所包含的三角面個數見表1。實驗平臺為Windows7,運行機器為I3雙核CPU,主頻為3.3 GHz,內存2 GB,運行環境為VisualStudio2010,算法實現語言為C++。

表1列出了分層厚度為0.01 mm時3種算法針對10個模型得出的分層方向、體積偏差以及運算時間,由于模型尺寸大小不一,不同模型體積偏差的數值相差較大。

算法1 遍歷模型中所有三角面的法向量,計算每個法向量對應的體積偏差,每次體積偏差的計算都要對所有加權法向量進行內積運算,計算復雜度為logN2;算法2對每個采樣方向都進行一次體積偏差的計算,計算速度取決于采樣數m和模型復雜程度,時間復雜度為mlogN;本文算法只需對模型的加權法向量集的散列矩陣進行一次特征值分解,計算效率只取決于模型的三角面片個數,時間復雜度為logN。

圖6 10個STL模型

模型編號名稱面片數分層方向(?，θ)/(°)算法1算法2本算法體積偏差/mm3算法1算法2本算法計算時間/s算法1算法2本算法1CupCake861(90，0)(50，0)(146，0)65833065156365189510170032Bottle1240(0，96)(0，90)(0，90)39007638642538642720240043Bunny15110(1，73)(0，100)(0，90)0．257740．237740．23968270970174MakeRobot11966(90，90)(90，90)(90，88)1004111004111020241352250425MyScan23826(92，91)(90，10)(114，39)2239822062762149246114570856Bunny269630(1，98)(0，100)(0，90)010243700992821010032556×10313402487Buddha99448(0，43)(80，90)(90，90)071969206571380663926112×10319023548Trya200000(165，9)(70，170)(90，0)0．4675190．4522010．453515439×10337927009Armadillo212539(176，177)(90，110)(90，90)0．7449310．6393430．650632503×103402175410Angel270285(0，90)(0，90)(174，92)340710340818343179768×1035136978

圖7 3種算法運行時間

圖7為3種算法的時間曲線,符合時間復雜度分析。由于坐標范圍的限制,算法1只展示了部分曲線。由圖7可以看出,本文算法在運算效率上優勢明顯,耗時大幅減少,僅不到算法2的20%。對于簡單的STL模型,只需幾十至幾百毫秒,對于面片數在2×105的模型只需7 s左右,對最復雜的模型計算時間也在10 s之內,具有很強的適用性。相比而言,算法1適用于簡單模型,對于復雜模型,尤其是面片數在5 000以上的STL模型,時間復雜度急劇增加,難以應用。算法2有效降低了時間復雜度,但是該方法受限于采樣數。若采樣數目小,速度會更快,卻很有可能錯失更優方向;若數目太大,計算效率勢必受影響。實驗中取m=324,對面片數目在5×104以下的模型,可在10 s之內得到最優分層方向,對于更復雜的模型,則需要更長的用戶等待時間。

(a)與算法1相比

(b)與算法2相比圖8 本算法與算法1、2的精度性能比較

圖8給出了本文算法與對比算法在精度提升方面的比較,此處精度指的是算法在減少體積偏差方面的能力。相比法算法1,本文算法平均可減少3.6%的體積偏差,對模型3、7、9甚至超過了7%,但針對模型4、10也出現了微小的反復。與算法2相比,本文算法在精度方面平均降低1.16%,但除了個別模型(模型5),下降的幅度均很小,平均只有0.7%。該結果完全在可接受范圍內,也與2.1節中的敘述吻合,雖然精度略微下降,但計算效率大幅提升。綜合來看,本文提出的分層方向確定算法高效、可行。

4 結 語

本文以減小3D打印中的體積偏差為目標,提出了一種快速的分層方向確定算法。文中分析了分層時體積偏差的產生原理,指出模型面片面積對體積偏差的重要影響,引入面積加權法向量的概念,提出了一種新的體積偏差計算模型。基于該模型將最優分層方向確定問題轉化為最小絕對偏差線性回歸問題,并使用最小二乘準則近似最小絕對偏差準則,借助主成分分析方法快速求解分層方向。

該算法摒棄了遍歷查找的思想,避免預定義候選方向,而是根據模型特征自適應地確定最佳分層方向。算法能在兼顧分層精度的同時,快速求得最優分層方向,相比已有算法展現出較大優勢,使用簡單、效率高,適合復雜精細模型的3D打印等分層制造應用。

[1] CHUA C K, LEONG K F, LIM C S. Rapid prototyping: principles and applications [M]. Singapore: World Scientific, 2010: 1-23.

[2] NOVAK J, NOVAKOVA L, BARNA J, et al. Application of FDM rapid prototyping technology in experimental gearbox development process [J]. Tehniki vjesnik-Technical Gazette, 2012, 19(3): 689-694.

[3] 王燁, 賀健康, 劉亞雄, 等. 三維微流道支架直接壓印成形方法 [J]. 西安交通大學學報, 2012, 46(10): 116-120. WANG Ye, HE Jiankang, LIU Yaxiong, et al. Direct imprinting of three-dimensional microfluidic scaffolds [J]. Journal of Xi’an Jiaotong University, 2012, 46(10): 116-120.

[4] 3D Systems. Stereolithography interface specification [M]. Rock Hill, South Carolina, USA: 3D Systems, 1988.

[5] AHARI H, KHAJEPOUR A, BEDI S. Optimization of slicing direction in laminated tooling for volume deviation reduction [J]. Assembly Automation, 2013, 33(2): 139-148.

[6] AHN D, KIM H, LEE S. Surface roughness prediction using measured data and interpolation in layered manufacturing [J]. Journal of Materials Processing Technology, 2009, 209(2): 664-671.

[7] PAUL B K, VOORAKARNAM V. Effect of layer thickness and orientation angle on surface roughness in laminated object manufacturing [J]. Journal of Manufacturing Processes, 2001, 3(2): 94-101.

[8] LIN F, SUN W, YAN Y. Optimization with minimum process error for layered manufacturing fabrication [J]. Rapid Prototyping Journal, 2001, 7(2): 73-82.

[9] PHAM D, DIMOV S, GAULT R. Part orientation in stereolithography [J]. The International Journal of Advanced Manufacturing Technology, 1999, 15(9): 674-682.

[10]VIJAY P, DANAIAH P, RAJESH K. Critical parameters effecting the rapid prototyping surface finish [J]. Journal of Mechanical Engineering and Automation, 2011, 1(1): 17-20.

[11]CANELLIDIS V, GIANNATSIS J, DEDOUSSIS V. Genetic-algorithm-based multi-objective optimization of the build orientation in stereolithography [J]. The

International Journal of Advanced Manufacturing Technology, 2009, 45(7/8): 714-730.

[12]BYUN H S, LEE K H. Determination of the optimal build direction for different rapid prototyping processes using multi-criterion decision making [J]. Robotics and Computer-Integrated Manufacturing, 2006, 22(1): 69-80.

[13]THRIMURTHULU K, PANDEY P M, REDDY N V. Optimum part deposition orientation in fused deposition modeling [J]. International Journal of Machine Tools & Manufacture, 2004, 44(6): 585-594.

[14]DOLENC A, KEL M I. Slicing procedures for layered manufacturing techniques [J]. Computer-Aided Design, 1994, 26(2): 119-126.

[15]CHEN K, YING Z L, ZHANG H, et al. Analysis of least absolute deviation [J]. Biometrika, 2008, 95(1): 107-122.

[16]SHLENS J. A tutorial on principal component analysis [EB/OL]. [2014-09-28]. http:∥arxiv.org/pdf/1404.1100.pdf.

(編輯 趙煒)

A Fast Determination Algorithm for Slicing Direction of 3D Printing

LUO Nan, WANG Quan, LIU Hongxia

(School of Computer, Xidian University, Xi’an 710071, China)

An efficient determination algorithm on slicing direction is proposed to reduce the volume deviation between fabrication entity and its theoretical model in layered manufacturing applications such as 3D printing. The cause of volume deviation and its mathematical model are analyzed, and the results show that the optimal slicing direction with the least volume deviation is a unit vector with the minimum value in the sum of absolute inner products of the vector and the area weighted normal vector of model facets. Thus, the problem to determine the optimal direction is converted into a linear regression problem with the least absolute deviation. The least absolute deviation norm is approximated by using the least squares norm and the principal component analysis method is used to process eigenvalue decomposition on the scatter matrix of weighted normal vecter. The optimal direction is then efficiently determined from the eigenvectors. Experiments on several models with different complexity show that the proposed algorithm reduces 80% of the computation load on the premise of guarantee accuracy, and is suitable for layered manufacturing of complex models.

3D printing; volume deviation; slicing direction; linear regression; principal component analysis

2014-11-03。

羅楠(1987—),男,博士生;王泉(通信作者),男,教授,博士生導師。

國家自然科學基金資助項目(61070045)。

時間:2015-03-03

10.7652/xjtuxb201505022

TP391

A

0253-987X(2015)05-0140-07

網絡出版地址:http:∥www.cnki.net/kcms/detail/61.1069.T.20150303.1110.004.html