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

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