分區(qū)結(jié)構(gòu)的分區(qū)掃描路徑生成算法

分區(qū)結(jié)構(gòu)的分區(qū)掃描路徑生成算法

快速生產(chǎn)是一種分層制造技術(shù)。在零件制造過程中，最基本的步驟之一是選擇合適的掃描路徑，并掃描每個零件的截面。目前,按照填充掃描路徑的不同,掃描路徑可分為三種:(1)平行掃描路徑。采用這種掃描方式加工零件,所有掃描線均平行,見圖1a,這是一種應(yīng)用最為廣泛的平行線的往復掃描方法。為了提高加工零件的性能,許多專家提出了往復掃描的多種改進形式;同時為了提高掃描效率,對掃描矢量方向進行了優(yōu)化處理。(2)輪廓平行掃描。這種掃描方式的掃描線沿平行于邊界輪廓線的方向進行,即按照截面輪廓的等距線進行掃描,見圖1b掃描撟開生成算法小腦多邊形的多種操作,比較復雜。(3)分形掃描方法。這種掃描方法的掃描路徑是由短小的折線組成,見圖1c。掃描路徑的產(chǎn)生就是對截面輪廓進行填充,由STL模型分層得到的截面輪廓是一系列封閉的多邊形,這些多邊形是由順序連接的頂點鏈構(gòu)成。多邊形可能是凸的或凹的,包圍的區(qū)域可能是單連通的或多連通的。所以,截面輪廓的填充問題就轉(zhuǎn)化為復雜多邊形的填充問題,是計算機圖形學領(lǐng)域的基本運算?，F(xiàn)在介紹一種新的分區(qū)往復掃描路徑生成算法,這種算法不僅簡單,速度快,可以在加工控制過程中生成;同時,將復雜截面輪廓分割成若干個簡單的無內(nèi)孔的子區(qū)域,在每個簡單的子區(qū)域內(nèi)可以連續(xù)掃描,依次掃描每個子區(qū)域。這樣避免了簡單的平行掃描路徑需要跨越內(nèi)孔的非加工路徑,提高了加工效率。1徑反向旋轉(zhuǎn)角區(qū)域的分割與掃描路徑的方向有關(guān),下面按照水平掃描路徑方向進行區(qū)域分割和掃描路徑生成,如果優(yōu)化的掃描線方向與x坐標軸成α角,可以按以下步驟規(guī)劃掃描路徑:①將當前截面按順時針方向旋轉(zhuǎn)α角;②按水平方向規(guī)劃掃描路徑;③將得到的掃描路徑反向旋轉(zhuǎn)α角。區(qū)域分割的目的就是將復雜區(qū)域分割為簡單的單調(diào)區(qū)域,在每個單調(diào)區(qū)域內(nèi)可進行連續(xù)的掃描加工,避免跨越非加工區(qū)域。截面輪廓的區(qū)域分割就是將復雜的輪廓多邊形形成的區(qū)域劃分為沿掃描路徑垂線L方向的單調(diào)多邊形形成的單調(diào)域,要進行區(qū)域分割首先要找到L方向的輪廓多邊形的極值點。復雜輪廓多邊形劃分為單調(diào)多邊形的數(shù)目與極值點的數(shù)目有關(guān),一般情況下,復雜輪廓多邊形沿L方向劃分單調(diào)多邊形的數(shù)目等于L方向的平凡極大值或平凡極小值。如圖2所示,一個截面輪廓由一個外輪廓12345和一個內(nèi)輪廓6789組成,沿L方向,截面輪廓被劃分為3個單調(diào)多邊形,這3個單調(diào)多邊形圍成了3個單調(diào)區(qū)域Ⅰ、Ⅱ和Ⅲ,每個單調(diào)區(qū)域均處在一個極小值和一個極大值之間。這樣在每個單調(diào)區(qū)域內(nèi),沿掃描方向都可以進行連續(xù)的掃描。2掃描變量的分段生成算法2.1邊形邊線的點掃描線為水平直線在截面輪廓區(qū)域內(nèi)的部分,掃描線與多邊形的交點就是水平直線與輪廓多邊形邊線的交點。A、B為多邊形邊線的兩頂點,坐標分別為(xa,ya),(xb,yb),水平直線為:y=y0。相交情況分為兩種,一種是重合情況,一種是非重合情況,見圖3。重合時,交點有無數(shù)多個,此時記交點為(xa,y0);當正常相交時,其交點坐標為2.2頭終點的數(shù)據(jù)結(jié)構(gòu)為了方便地進行掃描路徑的規(guī)劃和記錄掃描線與截面輪廓的交點,設(shè)計一個二維的交點表進行交點數(shù)據(jù)的存儲,見圖4。每條單鏈表存儲一條掃描線與截面輪廓的所有多邊形交點的x坐標,每條單鏈表的頭結(jié)點存儲掃描線的序號和該鏈表存儲的交點數(shù),所有單鏈表形成一個鏈表數(shù)組。頭結(jié)點的數(shù)據(jù)結(jié)構(gòu)為,typedefstructCrossHead{intScanLine;//掃描線序號,intPointNum;//掃描線的交點數(shù),structCrossPoint*next;//數(shù)據(jù)結(jié)點指針};數(shù)據(jù)結(jié)點的數(shù)據(jù)結(jié)構(gòu)為:typedefstructCrossPoint{floatx_crosspoint;//掃描線的交點數(shù),structCrossPoint*next;//數(shù)據(jù)結(jié)點指針};2.3在掃描向量的區(qū)域內(nèi)生成算法描述下面詳細討論掃描矢量的分區(qū)域生成算法:(1)有非小值點的極值點因為假設(shè)掃描線方向為水平方向,搜索截面輪廓的各多邊形,得到y(tǒng)方向的所有極值點。當遇到非平凡極值點時,只保留x值較大的非平凡極值點,此時極大值點的個數(shù)應(yīng)當和極小值點的個數(shù)相等。然后將極大值點和極小值點按照y坐標從小到大排序。(2)掃描線農(nóng)業(yè)面為面的理論線和截面輪廓的點掃描線在y=0到最小的極小值之間,掃描線與截面輪廓沒有交點,掃描線直接在y=ymin+scandis處計算交點,ymin為最小的極值點,scandis為掃描線間距。求得交點后,將交點存儲在相應(yīng)的掃描線鏈表中,同時該掃描線甸表的頭結(jié)點的交點數(shù)加2。求解交點時,每遇到一個極小值,交點數(shù)增加兩個;每遇到一個極大值,交點數(shù)減少兩個;當遇到最大的極大值時,掃描線與截面輪廓的交點數(shù)減少到零,此時掃描結(jié)束。將每條掃描線的交點按照x坐標從小到大進行排序。這樣,每條掃描線相鄰兩個交點的x坐標,與該掃描線的y坐標合成填充矢量,構(gòu)成了掃描線與輪廓區(qū)域的相交敬意,每個相交區(qū)間對應(yīng)掃描線上的一條填充段。(3)充填矢量的提取從第一條交點數(shù)不為零的掃描線鏈表中提取最前的兩個元素,與該條掃描線的y坐標合成一條掃描矢量,存入掃描矢量文件。然后,從下一條掃描線中提取最前的兩個元素構(gòu)成掃描矢量,如果該條掃描線的交點數(shù)與上一條掃描線的交點數(shù)不同,此時需要判斷形成的掃描矢量是否還屬于同一區(qū)域,判斷的方法采用文獻中的方法,即判斷這兩條矢量在x軸上的投影是否有重疊的部分。同時,每形成一條填充矢量,應(yīng)從相應(yīng)的鏈表中刪掉最前的兩個元素,頭結(jié)點中的交點數(shù)減2。當處理編號為偶數(shù)的填充矢量時,應(yīng)將矢量的起點和終點位置互換,倒置矢量的方向,從而形成往復掃描。逐條掃描線提取屬于同一區(qū)域的填充矢量,直到下一條掃描線中已經(jīng)沒有屬于同一區(qū)域的填充矢量或者該條掃描線的交點數(shù)已為零,此時,該區(qū)域的填充矢量已提取完畢。當一個區(qū)域的填充矢量提取完畢時,搜索極值點中與最后一條掃描矢量的y坐標差值最近的極值點。如果是極小值,則按照y坐標值增加的順序提取掃描線上的填充矢量;如果是極大值,則按照y坐標值減小的順序提取;如果掃描線上的交點數(shù)已為零,則查找另一個鄰近的極值點,直到所有掃描線的交點數(shù)都為零,則該截面輪廓的填充矢量提取完畢。這樣填充完一個區(qū)域之后,就可以找到距離最近的一個區(qū)域,有效減少了空行程的距離,提高加工效率。如圖5所示為截面輪廓的填充過程,首先提取到第一條填充矢量,以y坐標值增加的順序填充的區(qū)域Ⅰ區(qū),填充完畢之后找到Ⅱ區(qū)的極大值,以y坐標值減小的順序填充Ⅱ區(qū);之后,以y坐標值減小的順序填充Ⅲ區(qū);最后,以y坐標值增加的順序填充Ⅳ區(qū)。3掃描矢量的合成(1)在提取同一區(qū)域的填充矢量時,只是在掃描線的交點數(shù)發(fā)生變化時,才對填充矢量是否屬于該區(qū)域進行判斷;如果下一條掃描線的交點數(shù)不發(fā)生變化,表示沒有空洞或凹點出現(xiàn),提取掃描線鏈表最前的兩個元素與y坐標合成的矢量,就是同一區(qū)域的填充矢量。這樣大減少了掃描矢量的判斷次數(shù),有效提高了程序的運行效率。(2)文獻中,各個區(qū)域的掃描順序是按照每個區(qū)域的掃描矢量的最小y坐標值排列的,對每個區(qū)域掃描總是從最低的矢量開始,這樣在一個區(qū)域掃描完畢之后,可能要有很長的“空行程”路線,見圖6所示。這里對各個區(qū)域的掃描順序是按照上一個區(qū)域的最后一個矢量的終點與