基于線段拓撲關系的輪廓偏置算法

胡平山 丁浩亮 馮漾漾 嚴 波

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

0 引言

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

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

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

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

針對復雜零件,本文提出一種基于線段拓撲關系的輪廓偏置算法,研究對偏置算法穩定性影響較大的環相交問題和尖角問題,并進行了實驗驗證。

1 偏置算法模型

1.1 總體框架

算法的基本原理是:對于經切片處理得到的簡單填充區域,由一個外環和若干內環組成,實現外環的向內偏置更新,依次處理環的相交和干涉異常情況,得到無重疊無干涉的有效路徑環,進行環的光順處理消除路徑上的極端尖角,提高算法的穩定性,重復以上過程直到區域完全填充,算法流程如圖1所示。

1.2 偏置異常處理

由于曲線形狀的復雜性,偏置結果常常包含環的相交,一方面會導致輪廓的失真,成形件的表面特征缺失,另一方面會出現內部填充的欠熔覆和過熔覆問題,影響零件力學性能,更嚴重的是使曲線偏離正常拓撲關系,算法計算出現失穩和崩潰。因此需要對偏置異常情況進行分析,提出基于線段拓撲的多環處理算法流程,如圖2所示。

圖2 偏置異常處理流程圖

1.2.1環相交的形成機理

目前大多數理論證明環的相交是由于曲線局部曲率小于偏置距離,邊界發生翻轉造成的干涉現象。對偏置過程中線段端點的移動進行數學建模,研究偏置過程中端點的移動如何影響線段的空間拓撲關系。

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

圖3 線段相交數學分析

由幾何關系可以得到右端點在直線方向上的相對移動距離:

(1)

同理計算左端點的移動距離ΔdL,當兩者的移動距離之和大于線段長度L即

ΔdR+ΔdL>L

(2)

時,線段偏置后反向。

考慮線段的方向,定義沿環方向相鄰兩線段方向向量的偏轉為逆時針時,兩線段之間的夾角角度是正值,此時PR的偏置點為向左移動,ΔdR為正值;而沿環方向相鄰兩線段方向向量的偏轉為順時針的線段夾角角度為負值,此時PR的偏置點向右移動,ΔdR為負值。在圖3中,θ和α均為正值,式(2)可以調整為左右兩端點移動的相對距離絕對值:

(3)

如圖4所示,將滿足線段發生翻轉分為兩種,計算相鄰線段的夾角θ和α,當相鄰線段的方向向量叉乘為正時夾角為正值,叉乘為負時夾角為負值。當相鄰兩線段的偏轉方向相同時,目標線段如果發生翻轉,相鄰線段會提前相交,在局部形成自交環,如圖4a所示。當相鄰兩線段的偏轉方向相反時,目標線段如果發生翻轉,相鄰線段仍然經過翻轉線段后并不會在局部形成自交環,如圖4b所示。

1.2.2異常分類和環失效識別

根據異常出現的原因可以大致分為:第一類自交問題、第二類自交問題、干涉問題和特殊相交情形。

圖5 第一類自交異常

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

圖6 第二類自交異常

干涉問題(圖7)。對于復雜的圖形邊界,當外環(實線)向內不斷偏置,到達某一時刻和內環(虛線)發生相交,內環邊界成為外環邊界的一部分。

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

特殊相交(圖8):在復雜局部特征的偏置中,局部區域的線段長度與偏置距離相比較小,導致多條線段的多次翻轉。圖8所示兩環均是逆時針方向,其中被包含的環為無效環。

圖8 特殊情形

通過以上分類討論,確定了每種異常的產生原因和特點,設計了相應的環失效判據:

(1)由于當前操作的環為外環,初始旋向為逆時針,因此,若識別目標的旋轉方向為順時針則屬于異常分類中的前三類。

(2)理想的邊界為無相交無干涉的外環,通過判斷當前區域內環的包含關系,被包含的環屬于異常分類中的第四類。

(3)計算環內坐標值得最大值和最小值,面積過小的環形區域為冗余加工區域。

1.3 偏置尖角問題

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

圖9 未光順化的邊界

1.3.1尖角對算法穩定性的影響分析

算法穩定性是偏置算法設計的首要目標,需要保證算法在任何情形下均能保持計算的合理性以及結果的可靠性。在圖3中,頂點PR到P′R的移動距離Δd可以使用偏置距離H和鄰邊的夾角θ表示:

Δd=H/cos(0.5θ)

(6)

將頂點偏置距離和夾角的關系表示為表1,可以發現隨著偏轉角度的增大,Δd會急劇增大。

表1 頂點偏置距離和偏置夾角關系

圖10和圖11所示分別為原始圖形(圖9)經過一次偏置和兩次偏置后的結果,可以發現圖9中的尖角被區域偏置后逐漸放大,而在偏置過程中形成的極端尖角會在圖11中造成偏置過程的崩潰。

圖10 第一次偏置結果

圖11 第二次偏置結果

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

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

B區域的局部放大如圖12所示,實線為偏置之前的原始線段,虛線為偏置之后的邊界線,由于線段P2P3和線段P6P7的翻轉,在偏置線上出現極端尖角,符合1.2.1節中提出的相交分析理論,由于左右端點的相對運動,原本偏轉角度極小的短線段產生方向的翻轉,成為偏轉角度極大的尖角。

圖12 B區域尖角放大圖

圖13是C區域的局部放大圖,實線為偏置前的原始線段,虛線為偏置后的邊界線,由于偏置過程中的相交現象導致原本不相鄰的線段變成相鄰的線段。

圖13 C區域尖角放大圖

1.3.2修補式光順處理

為解決以上尖角問題,提出通過增加線段調整偏轉角度的修補式光順處理方案。如圖14所示,當前判斷的線段BC與集合中最后的線段AB的夾角為θ,判斷超出上邊界:

圖14 修補式光順方案

θ≥θmax

(7)

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

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

對圖9原始數據光順處理之后再次偏置,得到結果如圖15所示,由于修補式光順方案保證了偏置曲線上任意鄰邊之間偏轉角度θ∈(10°,120°),頂點的偏置距離不超過線段偏置距離的兩倍,不會出現圖11中過長的移動,保證了算法穩定運行。圖16所示為兩次偏置的優化結果。

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

圖16 最終優化結果

2 算法實例分析

2.1 CGAL幾何圖形庫偏置對比

對于二維曲線的偏置,CGAL幾何圖形庫提供了一種基于多邊形骨架的輪廓偏置算法。基于CGAL庫編寫計算程序對圖9進行骨架偏置計算,偏置距離為0.5,得到結果如圖17所示。

圖17 基于CGAL算法的結果

分析發現,圖17中存在以下問題:

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

(2)頂點的移動距離差異較大,填充區域粉末燒結不均勻,會導致零件力學性能降低。

(3)填充區域被分割為多個獨立區域,需要增加區域之間的過渡連接線。

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

表2 程序運行時間對比

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

與本文算法的偏置結果進行比較,兩者形狀基本一致,本質是頂點沿著鄰邊夾角的角平分線移動,CGAL算法采用更加稠密的計算步長生成骨架,避免了偏置后線段自交的出現,而本文的算法采用固定的偏置距離,離散并簡化計算過程,但需要重點研究環自交問題處理。而與CGAL算法的偏置計算時間相比,本文算法具有顯著的效率優勢,更符合加工需要。

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

2.2 掃描效率分析

目前常用的掃描路徑規劃方式還有平行線掃描、分區掃描、分形掃描等,根據各自成形特點適用于不同結構特征的零件,因此對平行線掃描(圖19)、分區掃描(圖20)和輪廓掃描(圖21)進行實驗對比分析。

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

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

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

平行線掃描是最樸素的掃描方式,沿著某確定的方向順序填充截面區,并根據掃描線奇偶調整方向進行往返運動掃描,算法簡單,容易實現,但激光器會頻繁跨越型腔。

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

針對三種掃描路徑對上述零件進行實驗設計,分別對加工過程中的轉彎次數m、啟停次數n、打印總長度Ltol進行統計,結果如表3所示。可以看出,平行線掃描方式由于存在跨越型腔的運動,掃描線長度最長,并且激光器需要頻繁的啟停操作;分區掃描方式將區域劃分為簡單連通區域,減少了無效行程,掃描線總長度最短,但是存在頻繁轉彎;而輪廓掃描的掃描線長度較短,同時保持了較少的激光器轉彎次數和啟停次數,是最優的掃描方式。

表3 三種掃描方式結果對比

3 結論

本文研究了選區激光熔化的輪廓偏置路徑規劃算法,從偏置向量的計算、偏置異常情況處理和偏置光順處理三個方面進行設計,并探究了環相交異常和尖角問題的產生機理,分析其對算法穩定性的影響,并提出相應的解決方法,實現高效穩定的偏置計算。通過實驗分析得到以下結論:

(1)與現有的CGAL算法庫中偏置算法相比,本文算法結果計算準確,時間成本低,更加符合選區激光熔化工藝需要。

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