基于線段拓?fù)潢P(guān)系的輪廓偏置算法

胡平山 丁浩亮 馮漾漾 嚴(yán) 波

1.上海交通大學(xué)材料科學(xué)與工程學(xué)院,上海,2000302.航天材料及工藝研究所,北京,100076

0 引言

曲線的偏置操作常用于復(fù)雜型面的工裝模具設(shè)計(jì)[1]、數(shù)控加工的刀軌控制[2-3]、智能機(jī)器人的行走路徑規(guī)劃[4]等領(lǐng)域。在增材制造過(guò)程中,偏置線段是無(wú)交叉無(wú)重疊的連續(xù)線段,與平行線掃描方式相比能保持加工過(guò)程的連續(xù),掃描效率更高,并能解決邊界處臺(tái)階效應(yīng)。因此研究合適的增材制造路徑規(guī)劃策略,能使零件成形精度更高和表面質(zhì)量更佳[5-6],并能影響加工過(guò)程溫度場(chǎng)和應(yīng)力場(chǎng)分布,決定成形零件的力學(xué)性能。但針對(duì)復(fù)雜零件的高效且穩(wěn)定的輪廓偏置算法一直是增材制造路徑規(guī)劃研究的難點(diǎn)。

當(dāng)前偏置算法包括圖形算法和圖像算法兩類。圖形算法基于拓?fù)潢P(guān)系的線段偏置[7],利用有向線段的集合表征自由曲線,通過(guò)線段端點(diǎn)的偏置來(lái)控制線段的移動(dòng)。YANG等[8]提出利用截面邊界進(jìn)行偏置得到填充線段的方法,對(duì)重疊部分進(jìn)行合并,對(duì)尖銳頂點(diǎn)進(jìn)行特殊處理,與光柵式掃描相比,掃描時(shí)間和零件表面質(zhì)量均得到了改善。ELBER[9]通過(guò)分析偏置線段是否發(fā)生反向來(lái)判斷曲線的局部自交。LEE等[10]使用圓環(huán)沿基曲線掃掠,計(jì)算圓環(huán)是否和基曲線發(fā)生干涉來(lái)檢測(cè)是否發(fā)生自交。PERSON[11]提出子區(qū)域劃分法Voronoi圖法,將平面區(qū)域劃分成多個(gè)子區(qū)域,之后在子區(qū)域中進(jìn)行偏置,避免了復(fù)雜的互交判斷。FELKEL等[12]提出通過(guò)多邊形的拓?fù)涔羌軄?lái)分析幾何形狀,并利用骨架的等分線計(jì)算區(qū)域的偏置填充曲線,完全回避了線段的偏置計(jì)算。

圖像算法一般基于頂點(diǎn)的離散偏置[13],將原始曲線細(xì)分為點(diǎn)集,對(duì)每個(gè)頂點(diǎn)進(jìn)行偏置之后將頂點(diǎn)擬合為線段。CHEN[14]將輪廓線離散為點(diǎn),再進(jìn)行基于圖像的擴(kuò)張和輪廓環(huán)的重新識(shí)別,以避免異常問(wèn)題,算法具有很好的穩(wěn)定性。李俊杰[1]通過(guò)在原始線段上選取參考點(diǎn)并利用漸進(jìn)迭代的方式獲取偏置軌跡。JIN等[15]利用非均勻有理B樣條曲線對(duì)偏置掃描路徑進(jìn)行擬合,進(jìn)一步提高偏置邊界的精度和加工產(chǎn)品的表面質(zhì)量。

以上兩種算法各有優(yōu)劣:圖形算法的優(yōu)勢(shì)在于方法直觀,運(yùn)行效率高,而缺點(diǎn)便是需要處理復(fù)雜的相交情況;圖像算法則能更加魯棒地實(shí)現(xiàn)偏置,避免異常情況的處理,但運(yùn)行速度緩慢,且在輪廓復(fù)雜區(qū)域難以正確高效處理小環(huán)路徑。

針對(duì)復(fù)雜零件,本文提出一種基于線段拓?fù)潢P(guān)系的輪廓偏置算法,研究對(duì)偏置算法穩(wěn)定性影響較大的環(huán)相交問(wèn)題和尖角問(wèn)題,并進(jìn)行了實(shí)驗(yàn)驗(yàn)證。

1 偏置算法模型

1.1 總體框架

算法的基本原理是:對(duì)于經(jīng)切片處理得到的簡(jiǎn)單填充區(qū)域,由一個(gè)外環(huán)和若干內(nèi)環(huán)組成,實(shí)現(xiàn)外環(huán)的向內(nèi)偏置更新,依次處理環(huán)的相交和干涉異常情況,得到無(wú)重疊無(wú)干涉的有效路徑環(huán),進(jìn)行環(huán)的光順處理消除路徑上的極端尖角,提高算法的穩(wěn)定性,重復(fù)以上過(guò)程直到區(qū)域完全填充,算法流程如圖1所示。

1.2 偏置異常處理

由于曲線形狀的復(fù)雜性,偏置結(jié)果常常包含環(huán)的相交,一方面會(huì)導(dǎo)致輪廓的失真,成形件的表面特征缺失,另一方面會(huì)出現(xiàn)內(nèi)部填充的欠熔覆和過(guò)熔覆問(wèn)題,影響零件力學(xué)性能,更嚴(yán)重的是使曲線偏離正常拓?fù)潢P(guān)系,算法計(jì)算出現(xiàn)失穩(wěn)和崩潰。因此需要對(duì)偏置異常情況進(jìn)行分析,提出基于線段拓?fù)涞亩喹h(huán)處理算法流程,如圖2所示。

圖2 偏置異常處理流程圖

1.2.1環(huán)相交的形成機(jī)理

目前大多數(shù)理論證明環(huán)的相交是由于曲線局部曲率小于偏置距離,邊界發(fā)生翻轉(zhuǎn)造成的干涉現(xiàn)象。對(duì)偏置過(guò)程中線段端點(diǎn)的移動(dòng)進(jìn)行數(shù)學(xué)建模,研究偏置過(guò)程中端點(diǎn)的移動(dòng)如何影響線段的空間拓?fù)潢P(guān)系。

圖3定義直線和相鄰兩直線的夾角分別為θ和α,線段偏置距離為H,左右兩端點(diǎn)分別為PL和PR,其中PR經(jīng)過(guò)偏置之后得到P′R,而線段的長(zhǎng)度記為L(zhǎng),由于兩端點(diǎn)移動(dòng)的差異,線段的長(zhǎng)度發(fā)生變化。

圖3 線段相交數(shù)學(xué)分析

由幾何關(guān)系可以得到右端點(diǎn)在直線方向上的相對(duì)移動(dòng)距離:

(1)

同理計(jì)算左端點(diǎn)的移動(dòng)距離ΔdL,當(dāng)兩者的移動(dòng)距離之和大于線段長(zhǎng)度L即

ΔdR+ΔdL>L

(2)

時(shí),線段偏置后反向。

考慮線段的方向,定義沿環(huán)方向相鄰兩線段方向向量的偏轉(zhuǎn)為逆時(shí)針時(shí),兩線段之間的夾角角度是正值,此時(shí)PR的偏置點(diǎn)為向左移動(dòng),ΔdR為正值;而沿環(huán)方向相鄰兩線段方向向量的偏轉(zhuǎn)為順時(shí)針的線段夾角角度為負(fù)值,此時(shí)PR的偏置點(diǎn)向右移動(dòng),ΔdR為負(fù)值。在圖3中,θ和α均為正值,式(2)可以調(diào)整為左右兩端點(diǎn)移動(dòng)的相對(duì)距離絕對(duì)值:

(3)

如圖4所示,將滿足線段發(fā)生翻轉(zhuǎn)分為兩種,計(jì)算相鄰線段的夾角θ和α,當(dāng)相鄰線段的方向向量叉乘為正時(shí)夾角為正值,叉乘為負(fù)時(shí)夾角為負(fù)值。當(dāng)相鄰兩線段的偏轉(zhuǎn)方向相同時(shí),目標(biāo)線段如果發(fā)生翻轉(zhuǎn),相鄰線段會(huì)提前相交,在局部形成自交環(huán),如圖4a所示。當(dāng)相鄰兩線段的偏轉(zhuǎn)方向相反時(shí),目標(biāo)線段如果發(fā)生翻轉(zhuǎn),相鄰線段仍然經(jīng)過(guò)翻轉(zhuǎn)線段后并不會(huì)在局部形成自交環(huán),如圖4b所示。

1.2.2異常分類和環(huán)失效識(shí)別

根據(jù)異常出現(xiàn)的原因可以大致分為:第一類自交問(wèn)題、第二類自交問(wèn)題、干涉問(wèn)題和特殊相交情形。

圖5 第一類自交異常

第二類自交異常(圖6)也稱為全局自交,是兩條不相鄰線段的最小距離小于偏置距離,在偏置之后出現(xiàn)相互干涉的情況。

圖6 第二類自交異常

干涉問(wèn)題(圖7)。對(duì)于復(fù)雜的圖形邊界,當(dāng)外環(huán)(實(shí)線)向內(nèi)不斷偏置,到達(dá)某一時(shí)刻和內(nèi)環(huán)(虛線)發(fā)生相交,內(nèi)環(huán)邊界成為外環(huán)邊界的一部分。

(a)偏置前 (b)偏置中 (c)偏置后

特殊相交(圖8):在復(fù)雜局部特征的偏置中,局部區(qū)域的線段長(zhǎng)度與偏置距離相比較小,導(dǎo)致多條線段的多次翻轉(zhuǎn)。圖8所示兩環(huán)均是逆時(shí)針?lè)较?其中被包含的環(huán)為無(wú)效環(huán)。

圖8 特殊情形

通過(guò)以上分類討論,確定了每種異常的產(chǎn)生原因和特點(diǎn),設(shè)計(jì)了相應(yīng)的環(huán)失效判據(jù):

(1)由于當(dāng)前操作的環(huán)為外環(huán),初始旋向?yàn)槟鏁r(shí)針,因此,若識(shí)別目標(biāo)的旋轉(zhuǎn)方向?yàn)轫槙r(shí)針則屬于異常分類中的前三類。

(2)理想的邊界為無(wú)相交無(wú)干涉的外環(huán),通過(guò)判斷當(dāng)前區(qū)域內(nèi)環(huán)的包含關(guān)系,被包含的環(huán)屬于異常分類中的第四類。

(3)計(jì)算環(huán)內(nèi)坐標(biāo)值得最大值和最小值,面積過(guò)小的環(huán)形區(qū)域?yàn)槿哂嗉庸^(qū)域。

1.3 偏置尖角問(wèn)題

實(shí)際的圖形邊界復(fù)雜多樣,往往是許多的短線段連接而成,相鄰短線段斜率可能相近,也可能相差很大,如圖9中Ⅰ、Ⅱ兩區(qū)域中所示。Ⅰ區(qū)域的直線是由一系列斜率相近的短線段連接而成,Ⅱ區(qū)域在局部出現(xiàn)相鄰線段的方向接近相反而構(gòu)成尖角特征,導(dǎo)致在激光加工時(shí)出現(xiàn)冗余行程。

圖9 未光順化的邊界

1.3.1尖角對(duì)算法穩(wěn)定性的影響分析

算法穩(wěn)定性是偏置算法設(shè)計(jì)的首要目標(biāo),需要保證算法在任何情形下均能保持計(jì)算的合理性以及結(jié)果的可靠性。在圖3中,頂點(diǎn)PR到P′R的移動(dòng)距離Δd可以使用偏置距離H和鄰邊的夾角θ表示:

Δd=H/cos(0.5θ)

(6)

將頂點(diǎn)偏置距離和夾角的關(guān)系表示為表1,可以發(fā)現(xiàn)隨著偏轉(zhuǎn)角度的增大,Δd會(huì)急劇增大。

表1 頂點(diǎn)偏置距離和偏置夾角關(guān)系

圖10和圖11所示分別為原始圖形(圖9)經(jīng)過(guò)一次偏置和兩次偏置后的結(jié)果,可以發(fā)現(xiàn)圖9中的尖角被區(qū)域偏置后逐漸放大,而在偏置過(guò)程中形成的極端尖角會(huì)在圖11中造成偏置過(guò)程的崩潰。

圖10 第一次偏置結(jié)果

圖11 第二次偏置結(jié)果

圖10尖角特征的形成機(jī)理可以分為圖中所示A、B、C區(qū)域中的三種情形。

A區(qū)域中的尖角特征來(lái)自基線上已經(jīng)存在的特征,如圖9中局部放大圖所示,此區(qū)域相鄰線段偏轉(zhuǎn)角度約170°,由表1可知該頂點(diǎn)的偏置距離大概為線段偏置距離H的11.5倍,從而在偏置線局部形成放大后的尖角。

B區(qū)域的局部放大如圖12所示,實(shí)線為偏置之前的原始線段,虛線為偏置之后的邊界線,由于線段P2P3和線段P6P7的翻轉(zhuǎn),在偏置線上出現(xiàn)極端尖角,符合1.2.1節(jié)中提出的相交分析理論,由于左右端點(diǎn)的相對(duì)運(yùn)動(dòng),原本偏轉(zhuǎn)角度極小的短線段產(chǎn)生方向的翻轉(zhuǎn),成為偏轉(zhuǎn)角度極大的尖角。

圖12 B區(qū)域尖角放大圖

圖13是C區(qū)域的局部放大圖,實(shí)線為偏置前的原始線段,虛線為偏置后的邊界線,由于偏置過(guò)程中的相交現(xiàn)象導(dǎo)致原本不相鄰的線段變成相鄰的線段。

圖13 C區(qū)域尖角放大圖

1.3.2修補(bǔ)式光順處理

為解決以上尖角問(wèn)題,提出通過(guò)增加線段調(diào)整偏轉(zhuǎn)角度的修補(bǔ)式光順處理方案。如圖14所示,當(dāng)前判斷的線段BC與集合中最后的線段AB的夾角為θ,判斷超出上邊界:

圖14 修補(bǔ)式光順?lè)桨?/p>

θ≥θmax

(7)

在兩線段上取lBE=lCE得到等腰三角形BEC,計(jì)算新線段和集合末尾線段AB的夾角:

從而保證了處理后的線段夾角β一定屬于合理角度范圍β<θmax。

對(duì)圖9原始數(shù)據(jù)光順處理之后再次偏置,得到結(jié)果如圖15所示,由于修補(bǔ)式光順?lè)桨副ＷC了偏置曲線上任意鄰邊之間偏轉(zhuǎn)角度θ∈(10°,120°),頂點(diǎn)的偏置距離不超過(guò)線段偏置距離的兩倍,不會(huì)出現(xiàn)圖11中過(guò)長(zhǎng)的移動(dòng),保證了算法穩(wěn)定運(yùn)行。圖16所示為兩次偏置的優(yōu)化結(jié)果。

圖15 第二次偏置結(jié)果(修正后)

圖16 最終優(yōu)化結(jié)果

2 算法實(shí)例分析

2.1 CGAL幾何圖形庫(kù)偏置對(duì)比

對(duì)于二維曲線的偏置,CGAL幾何圖形庫(kù)提供了一種基于多邊形骨架的輪廓偏置算法?；贑GAL庫(kù)編寫計(jì)算程序?qū)D9進(jìn)行骨架偏置計(jì)算,偏置距離為0.5,得到結(jié)果如圖17所示。

圖17 基于CGAL算法的結(jié)果

分析發(fā)現(xiàn),圖17中存在以下問(wèn)題:

(1)路徑中存在大量角度變化巨大的相鄰線段,造成激光器加工過(guò)程中的急停和變向,掃描速度的不均勻影響加工效率,出現(xiàn)粉末過(guò)燒。

(2)頂點(diǎn)的移動(dòng)距離差異較大,填充區(qū)域粉末燒結(jié)不均勻,會(huì)導(dǎo)致零件力學(xué)性能降低。

(3)填充區(qū)域被分割為多個(gè)獨(dú)立區(qū)域,需要增加區(qū)域之間的過(guò)渡連接線。

采用光順處理算法對(duì)原始曲線進(jìn)行處理后,再次使用CGAL的骨架輪廓偏置進(jìn)行計(jì)算,并和本文算法計(jì)算結(jié)果對(duì)比,結(jié)果如圖18所示,分析時(shí)間成本如表2所示。

表2 程序運(yùn)行時(shí)間對(duì)比

(a)優(yōu)化的CGAL算法 (b)本文算法

與本文算法的偏置結(jié)果進(jìn)行比較,兩者形狀基本一致,本質(zhì)是頂點(diǎn)沿著鄰邊夾角的角平分線移動(dòng),CGAL算法采用更加稠密的計(jì)算步長(zhǎng)生成骨架,避免了偏置后線段自交的出現(xiàn),而本文的算法采用固定的偏置距離,離散并簡(jiǎn)化計(jì)算過(guò)程,但需要重點(diǎn)研究環(huán)自交問(wèn)題處理。而與CGAL算法的偏置計(jì)算時(shí)間相比,本文算法具有顯著的效率優(yōu)勢(shì),更符合加工需要。

比較圖17和圖18a中的結(jié)果差異,CGAL偏置算法依賴于圖形骨架生成,對(duì)原始曲線的局部特征非常敏感,偏置結(jié)果差異性較大;采用本文光順化處理算法能優(yōu)化邊界曲線,使生成的骨架更加合理,偏置掃描線更加符合選取激光融化工藝的需求。

2.2 掃描效率分析

目前常用的掃描路徑規(guī)劃方式還有平行線掃描、分區(qū)掃描、分形掃描等,根據(jù)各自成形特點(diǎn)適用于不同結(jié)構(gòu)特征的零件,因此對(duì)平行線掃描(圖19)、分區(qū)掃描(圖20)和輪廓掃描(圖21)進(jìn)行實(shí)驗(yàn)對(duì)比分析。

(a)全局圖 (b)局部放大圖

(a)全局圖 (b)局部放大圖

(a)全局圖 (b)局部放大圖

平行線掃描是最樸素的掃描方式,沿著某確定的方向順序填充截面區(qū),并根據(jù)掃描線奇偶調(diào)整方向進(jìn)行往返運(yùn)動(dòng)掃描,算法簡(jiǎn)單,容易實(shí)現(xiàn),但激光器會(huì)頻繁跨越型腔。

分區(qū)掃描則是在平行線掃描基礎(chǔ)上,按照一定規(guī)則將零件截面劃分成多個(gè)小區(qū)域,將每個(gè)區(qū)域單獨(dú)規(guī)劃后依次連接得到整體的掃描路徑,解決了平行線掃描頻繁跨越型腔的空行程問(wèn)題,并可以通過(guò)在不同小區(qū)域采用不同的方向使各向異性和翹曲變形降低。

針對(duì)三種掃描路徑對(duì)上述零件進(jìn)行實(shí)驗(yàn)設(shè)計(jì),分別對(duì)加工過(guò)程中的轉(zhuǎn)彎次數(shù)m、啟停次數(shù)n、打印總長(zhǎng)度Ltol進(jìn)行統(tǒng)計(jì),結(jié)果如表3所示?？梢钥闯?平行線掃描方式由于存在跨越型腔的運(yùn)動(dòng),掃描線長(zhǎng)度最長(zhǎng),并且激光器需要頻繁的啟停操作;分區(qū)掃描方式將區(qū)域劃分為簡(jiǎn)單連通區(qū)域,減少了無(wú)效行程,掃描線總長(zhǎng)度最短,但是存在頻繁轉(zhuǎn)彎;而輪廓掃描的掃描線長(zhǎng)度較短,同時(shí)保持了較少的激光器轉(zhuǎn)彎次數(shù)和啟停次數(shù),是最優(yōu)的掃描方式。

表3 三種掃描方式結(jié)果對(duì)比

3 結(jié)論

本文研究了選區(qū)激光熔化的輪廓偏置路徑規(guī)劃算法,從偏置向量的計(jì)算、偏置異常情況處理和偏置光順處理三個(gè)方面進(jìn)行設(shè)計(jì),并探究了環(huán)相交異常和尖角問(wèn)題的產(chǎn)生機(jī)理,分析其對(duì)算法穩(wěn)定性的影響,并提出相應(yīng)的解決方法,實(shí)現(xiàn)高效穩(wěn)定的偏置計(jì)算。通過(guò)實(shí)驗(yàn)分析得到以下結(jié)論:

(1)與現(xiàn)有的CGAL算法庫(kù)中偏置算法相比,本文算法結(jié)果計(jì)算準(zhǔn)確,時(shí)間成本低,更加符合選區(qū)激光熔化工藝需要。

(2)與其他掃描方式相比,本文算法結(jié)果的路徑長(zhǎng)度、轉(zhuǎn)彎次數(shù)和啟停次數(shù)均較低,能保證較高的加工效率。