劉 歡,周惠群,李日華

(西北工業(yè)大學(xué)現(xiàn)代設(shè)計(jì)與集成制造技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室,陜西西安710072)

快速成形(rapid prototyping,RP)技術(shù)是20世紀(jì)80年代后期至90年代初期出現(xiàn)的一項(xiàng)新型現(xiàn)代制造技術(shù),它是將計(jì)算機(jī)輔助設(shè)計(jì)(CAD)、計(jì)算機(jī)輔助制造(CAM)、計(jì)算機(jī)數(shù)字控制(CNC)、精密伺服驅(qū)動(dòng)、激光技術(shù)和新材料等集于一體的新技術(shù)。自快速成形技術(shù)出現(xiàn)以來,CAD模型的分層技術(shù)便得到了廣泛的研究。理論上,在快速成形過程中,只要切片厚度足夠小,則燒結(jié)的三維實(shí)體模型與三維設(shè)計(jì)模型就應(yīng)當(dāng)是完全相同的。但事實(shí)上,由于受材料厚度的限制以及成形周期等因素的影響,切片的厚度不可能足夠小,于是在成形零件的外形輪廓上便產(chǎn)生了階梯狀誤差。

目前,國內(nèi)外學(xué)者就如何通過改變算法來提高快速成形零件的精度做了大量研究。周滿元[1]討論了快速成形中基于STEP的直接分層算法。平雪良等[2]提出了一種提高快速成形精度的正負(fù)公差切片算法。溫佩芝等[3]進(jìn)行了基于有向加權(quán)圖遞歸切片算法的研究。本文在上述研究的基礎(chǔ)上,提出了一種新的切片算法,該方法可提高快速成形精度,且在一定程度上提高了分層的效率。

1 遺傳算法

遺傳算法是將問題的參數(shù)用基因表示,將問題的解用染色體表示,從而得到一個(gè)由具有不同染色體的個(gè)體所組成的群體。這個(gè)群體在問題的特定環(huán)境里生存競爭,適者有最好的機(jī)會(huì)生存和產(chǎn)生后代,后代隨機(jī)地繼承父代的最好特征,并在生存環(huán)境的控制下繼續(xù)這一過程。同時(shí),群體的染色體都將逐漸適應(yīng)環(huán)境,不斷進(jìn)化,最后收斂到一族最適應(yīng)環(huán)境的類似個(gè)體,便得到問題的最優(yōu)解。按照以上思路,遺傳算法包含選擇、交叉、變異3個(gè)基本算子。

1.1 選擇

適應(yīng)度越大的染色體,其被復(fù)制的比例也越高。適應(yīng)度最大的染色體應(yīng)直接復(fù)制到下一代,以保存上一代最優(yōu)的染色體,避免丟失可能的最優(yōu)解;其他染色體被選擇的概率為其適應(yīng)度函數(shù)值占種群適應(yīng)度函數(shù)值總和的百分比,被選擇的染色體將進(jìn)入交叉群進(jìn)行交叉和變異操作。

1.2 交叉

隨機(jī)地在種群中選擇兩條染色體 A、B,并在所選染色體中隨機(jī)地選擇一個(gè)交配區(qū)域進(jìn)行交叉操作,其約束條件為基因值之和相等。

如:A=314 265 987,B=346 792 158;A′=314 792 265 987,B′=346 265 792 158。在 A′、B′中依次刪除與交配區(qū)相同的零部件編碼:A″=314 792 658,B″=342 657 918。

1.3 變異

按一定概率對(duì)進(jìn)入下一代的染色體進(jìn)行變異操作:100011→101001。

2 遺傳算法應(yīng)用于快速成形

對(duì)于分層切片而言,由于切片本身具有厚度,所以成形過程中必然產(chǎn)生階梯狀誤差。成形時(shí),公差在零件原始輪廓以外稱為正公差,在零件原始輪廓以內(nèi)稱為負(fù)公差。在完成加工后,正公差將導(dǎo)致外型輪廓留有余料,而負(fù)公差將導(dǎo)致材料不足。由于受加工效率和加工工藝的影響,目前的快速成形技術(shù)多采用等厚分層切片技術(shù)(圖1),其特點(diǎn)是不能像自適應(yīng)切片技術(shù)那樣根據(jù)零件結(jié)構(gòu)特點(diǎn)的變化而變化。對(duì)于同一個(gè)零件,采用的分層算法不同,最終得到的成形精度也不同。

圖1 傳統(tǒng)分層切片

圖1a和圖1b是兩種較傳統(tǒng)的切片方法,分別表示對(duì)零件自上而下和自下而上進(jìn)行切片。由于斜率的變化,這兩種方法都將導(dǎo)致成形后的零件某些部位留有余料,其他一些部位則材料不足,對(duì)于精度要求較高的零件而言,均可能導(dǎo)致不合格產(chǎn)品的出現(xiàn)。按圖1c所示的切片方法,所成形的零件整體都留有余料,這給后處理帶來了較大的麻煩;圖1d所示的方法則使零件整體余料不足,這有可能導(dǎo)致零件尺寸偏小,造成不合格現(xiàn)象。

本文將就以上分層方法的不足及成形零件的結(jié)構(gòu)特點(diǎn),提出一種新的基于遺傳算法的優(yōu)化分層算法。對(duì)于一個(gè)確定的零件而言,成形后的零件輪廓需留有余量的部位,可選擇遺傳算法中選擇復(fù)制的思想,采用正公差切片,多余的階梯狀余量可通過后處理進(jìn)行打磨;然而對(duì)于自由曲面的過渡部分,以往多采用隨機(jī)正負(fù)公差切片算法。

針對(duì)隨機(jī)算法中存在不可控性的缺點(diǎn),本文提出一種新的依據(jù)遺傳算法進(jìn)行分層的優(yōu)化分層方法。由于零件的STL模型尺寸是固定的,當(dāng)給定分層厚度以后,便可求出相應(yīng)的切片層數(shù),這在計(jì)算機(jī)里很容易實(shí)現(xiàn)。首先對(duì)每一層切片進(jìn)行編碼,每一層里,如采用正公差,切片則記為1;如采用負(fù)公差,切片則記為0。這樣,便得出了關(guān)于零件加工的二進(jìn)制編碼。在實(shí)際加工過程中,隨機(jī)取出兩組編碼(圖2)。由于零件分層后的第一層和第五層斜率較大,故以第一層和第五層作為交叉算子進(jìn)行交叉,得到新的編碼:0101010和1011101,對(duì)新生成的編碼依次刪除與交叉區(qū)域相同的編碼,得到優(yōu)化后的編碼:01101和10110。

圖2 遺傳算法的二進(jìn)制編碼

對(duì)于本文提出的正負(fù)公差采用二進(jìn)制編碼的遺傳算法而言,其隨機(jī)編碼可采用KD樹的二分查找法來獲得,其算法思想大致如下:

算法BUILDKDTREE(P,depth)

輸入:點(diǎn)集P以及當(dāng)前的深度depth

輸出:與P對(duì)應(yīng)的(k-d)樹的根節(jié)點(diǎn)

1.if(P只包含一個(gè)點(diǎn))

2.then return(存儲(chǔ)該點(diǎn)的葉子)

3.else

if(depth為偶數(shù))

4.then沿著通過P內(nèi)各點(diǎn)x-坐標(biāo)中值的垂線 l,將 P劃分為左、右兩個(gè)子集

(*記P1為對(duì)應(yīng)于位于 l左側(cè)或者落在l上諸點(diǎn)的子集,記P2為對(duì)應(yīng)于位于 l右側(cè)諸點(diǎn)的子集*)

5.else沿著通過P內(nèi)各點(diǎn)y-坐標(biāo)中值的水平線l,將P劃分為上、下兩個(gè)子集(*記P1為對(duì)應(yīng)于位于l下方或者落在l上諸點(diǎn)的子集,記P2為對(duì)應(yīng)于位于l上方諸點(diǎn)的子集 *)

6.vleft←BUILDKDTREE(P1,depth+1)

7.vright←BUILDKDT REE(P2,depth+1)

8.生成一個(gè)節(jié)點(diǎn) v以存儲(chǔ)直線l,并分別將vleft和vright置成 v的左、右孩子

9.return v

在開始討論查找算法前,首先確定構(gòu)造一棵二維(k-d)樹所需的時(shí)間。構(gòu)造過程所需時(shí)間 T(n)滿足如下結(jié)論:

給定由任意n個(gè)點(diǎn)組成的一個(gè)集合,其對(duì)應(yīng)的(k-d)樹占用O(n)空間,并可在O(nlogn)時(shí)間內(nèi)構(gòu)造出來。

完成二維(k-d)樹的構(gòu)造后,在GLUT圖形處理中采用拉格朗日插值查看遺傳算法的效果顯示,插值公式如下:

其C語言編程是很容易實(shí)現(xiàn)的。本文所選擇的例子包含5個(gè)節(jié)點(diǎn),對(duì)于更多節(jié)點(diǎn)的實(shí)例而言,只是N值的變化。在快速成形實(shí)際加工過程中,節(jié)點(diǎn)數(shù)N往往較大,如插值精度不理想,可采用分段插值的方法,即將模型的插值區(qū)間分成若干段,再對(duì)每段進(jìn)行低階插值。

在基于STL幾何特征分層的模型中,對(duì)三角面片進(jìn)行分類、分級(jí)快速排序后,每一面片結(jié)構(gòu)都將引入兩個(gè)新的數(shù)值Zmin和Zmax,分別表示在同一類面片中排列在某面片以后的面片的頂點(diǎn)Z坐標(biāo)的最小值和最大值。

在分層過程中,對(duì)某一類面片進(jìn)行交互判斷時(shí),當(dāng)分層高度小于Zmin時(shí),無須再對(duì)以后的三角形面片進(jìn)行交互判斷;同理,當(dāng)分層高度大于Zmax時(shí),也無須對(duì)以后的三角形面片進(jìn)行交互判斷。這樣,在分層過程中,隨著分層高度的變化,減少了與其他面片不必要的相交關(guān)系的判斷,從而提高了分層處理的速度。

3 運(yùn)算實(shí)例結(jié)果

圖3是采用傳統(tǒng)算法和遺傳算法對(duì)模型進(jìn)行分層切片的示意圖?；谶z傳算法的STL切片模型采用了優(yōu)化的三角面片分隔,相比于傳統(tǒng)的STL三角面片分隔,能有效避免誤差的累積。對(duì)于面片較少的零件而言,采用遺傳算法進(jìn)行分層切片,與文獻(xiàn)[3]中的方法相比,在效率方面無明顯優(yōu)勢(shì);對(duì)于面片較多的零件而言,采用遺傳算法進(jìn)行分層切片,與文獻(xiàn)[3]中的方法相比,其效率有了較明顯的提升。詳細(xì)參數(shù)及效率對(duì)比見表1。

圖3 兩種算法實(shí)例比較

表1 STL模型切片算法的模型參數(shù)及切片耗時(shí)對(duì)比

4 結(jié)語

本文在文獻(xiàn)[2]和文獻(xiàn)[3]的基礎(chǔ)上,提出了一種新的算法,該算法能有效解決對(duì)精度要求較高的零件的分層切片問題,并在一定程度上提高了分層切片的效率。

[1] 周滿元.一種非均勻自適應(yīng)分層方法[J].計(jì)算機(jī)工程與應(yīng)用,2005(3):72-75.

[2] 平雪良,高同軍,孟凡虹.一種提高快速成形系統(tǒng)精度的新切片算法[J].機(jī)械科學(xué)與技術(shù),2008,27(9):1121-1124.

[3] 溫佩芝,黃文明,吳成柯.一種改進(jìn)的ST L文件快速分層算法[J].計(jì)算機(jī)應(yīng)用,2008,28(7):1766-1768.

[4] 李廣慧,王麗萍,于平,等.SLS激光快速成形燒結(jié)層厚的選取[J].煤礦機(jī)械,2003(3):27-29.