多邊形的掃描轉(zhuǎn)換與區(qū)域填充

1、第四章多邊形的掃描轉(zhuǎn)換與區(qū)域填充,4.1多邊形掃描轉(zhuǎn)換4.2區(qū)域填充,,多邊形分為凸多邊形、凹多邊形、含內(nèi)環(huán)的多邊形。,4.1多邊形的掃描轉(zhuǎn)換,4.1多邊形的掃描轉(zhuǎn)換,多邊形的表示方法頂點表示點陣表示頂點表示：用多邊形頂點的序列來刻劃多邊形。直觀、幾何意義強、占內(nèi)存少；不能直接用于面著色。點陣表示：用位于多邊形內(nèi)的象素的集合來刻劃多邊形。失去了許多重要的幾何信息；便于運用幀緩沖存儲器表示圖形，易于面著色。,4.1多邊形的

2、掃描轉(zhuǎn)換,多邊形的掃描轉(zhuǎn)換：把多邊形的頂點表示轉(zhuǎn)換為點陣表示，也就是從多邊形的給定邊界出發(fā)，求出位于其內(nèi)部的各個象素，并給幀緩沖器內(nèi)的各個對應(yīng)元素設(shè)置相應(yīng)的灰度和顏色，通常稱這種轉(zhuǎn)換為多邊形的掃描轉(zhuǎn)換。兩種方法：掃描線算法；邊界標(biāo)志法。,掃描線算法,掃描線算法目標(biāo)：利用相鄰像素之間的連貫性，提高算法效率處理對象：非自交多邊形 （邊與邊之間除了頂點外無其它交點）,掃描線算法,交點的取整規(guī)則要求：使生成的像素全部位于多邊形之內(nèi)用于

3、線畫圖元掃描轉(zhuǎn)換的四舍五入原則導(dǎo)致部分像素位于多邊形之外，從而不可用假定非水平邊與掃描線y=e相交，交點的橫坐標(biāo)為x,規(guī)則如下,掃描線算法,●規(guī)則1：X為小數(shù)，即交點落于掃描線上兩個相鄰像素之間 (a)交點位于左邊之上，向右取整 (b)交點位于右邊之上，向左取整,●規(guī)則2：邊界上象素的取舍問題，避免填充擴大化?！窠鉀Q方法： 邊界象素：規(guī)定落在右上邊界的象素不予填充。 具體實現(xiàn)時，只要對

4、掃描線與多邊形的相交區(qū)間左閉右開,掃描線算法,●規(guī)則3：掃描線與多邊形的頂點相交時，交點的取舍，保證交點正確配對?！窠鉀Q方法：檢查兩相鄰邊在掃描線的哪一側(cè)。 只要檢查頂點的兩條邊的另外兩個端點的Y值，兩個Y值中大于交點Y值的個數(shù)是0，1，2，來決定取0，1，2個交點。,掃描線算法,掃描線算法是多邊形掃描轉(zhuǎn)換的常用算法。與逐點判斷算法相比，掃描線算法充分利用了相鄰象素之間的連貫性，避免了對象素的逐點判斷和反復(fù)求交的運算，達(dá)

5、到了減少了計算量和提高速度的目的。 開發(fā)和利用相鄰象素之間的連貫性是光柵圖形算法研究的重要內(nèi)容。掃描轉(zhuǎn)換算法綜合利用了區(qū)域的連貫性、掃描線連貫性和邊的連貫性等三種形式的連貫性。,掃描線算法,設(shè)多邊形P的頂點Pi=(xi,yi),i=0,1, …,n，又設(shè)yi0,yi1,…yin是各頂點Pi的坐標(biāo)yi的遞減數(shù)列，即yik≥yik+1,0≤k≤n-1這樣，當(dāng)yik≥yik+1,0≤k≤n-1時，屏幕上位于y=yik和y=

6、yik+1兩條掃描線之間的長方形區(qū)域被多邊形P的邊分割成若干梯形（三角形可看作其中一底邊長為零的梯形），它們具有下列性質(zhì)：,區(qū)域的連貫性,y=yik,y=yik+1,區(qū)域的連貫性,1）梯形的兩底邊分別在y=yik和y=yik+1兩條掃描線上，腰在多邊形P的邊上或在顯示屏幕的邊界上。2）這些梯形可分為兩類：一類位于多邊形P的內(nèi)部；另一類在多邊形P的外部。3）兩類梯形在長方形區(qū)域{yik,yik+1}內(nèi)相間的排列，即相鄰的兩梯形必有一個

7、在多邊形P內(nèi)，另一個在P外。,y=yik+1,y=yik,區(qū)域的連貫性,根據(jù)這些性質(zhì)，實際上只需知道該長方形區(qū)域內(nèi)任一梯形內(nèi)一點關(guān)于多邊形P的內(nèi)外關(guān)系后，即可確定區(qū)域內(nèi)所有梯形關(guān)于P的內(nèi)外關(guān)系。,設(shè)e為一整數(shù)，yi0≥e≥yin。若掃描線y=e與多邊形P的Pi-1Pi相交，則記其交點的橫坐標(biāo)為xei。 現(xiàn)設(shè)xei1,xei2,xei3,…,xeil 是該掃描線與P的邊界各交點橫坐標(biāo)的遞增序列，稱此序列為交點序列。由區(qū)域的連貫性可

8、知，此交點序列具有以下性質(zhì)：,掃描線的連貫性,掃描線的連貫性,1）設(shè)L是偶數(shù)。2）在該掃描線上，只有區(qū)段(xeik,xeik+1）,k=1,3,5,…,L-1位于多邊形P內(nèi)，其余區(qū)段都在P外。 以上性質(zhì)稱為掃描線的連貫性，它是多邊形區(qū)域連貫性在一條掃描線上的反映。,設(shè)d為一整數(shù)，并且d=e-1,并且 yi0≥d≥yin。設(shè)位于掃描線y=d上的交點序列為xdj1,xdj2,xdj3,…,xdjk 現(xiàn)在來討論掃描線d，e交點

9、序列之間的關(guān)系。若多邊形P的邊Pr-1Pr與掃描線y=e,y=d都相交，則交點序列中對應(yīng)元素xer,xdr滿足下列關(guān)系：xer= xdr + 1/mr (1)其中mr為邊Pr-1Pr的斜率。,,邊的連貫性,y=e,y=d,邊的連貫性,于是，可利用d的交點序列計算e的交點序列，即先運用遞推關(guān)系式(1)求得與掃描線y=e和y=d都相交的所有多邊形上的交點xer,再求得與掃描線y=d不相交但與掃描線y=e相交的所有邊PqPq+1上的

10、交點xeq。如果P的頂點的坐標(biāo)是整數(shù)，那么xeq=xq或xeq=xq+1,然后把這兩部分按遞增的順序排列，即可得e的交點序列。,y=e,y=d,邊的連貫性,特別是當(dāng)存在某一個整數(shù)k,0≤k≤n-1,使得yik>e, d>yik+1成立時，則由區(qū)域的連貫性可知d的交點序列和e的交點序列之間有以下關(guān)系： 1）兩序列元素的個數(shù)相等，如上圖所示。 2）點(xeir,e)與(xdjr,d)位于多邊形P的同一邊上，于

11、是 xeir= xdjr + 1/kjr (2)這樣，運用遞推關(guān)系式(2)可直接由d的交點序列和e的獲得e的交點序列。以上性質(zhì)稱為邊的連貫性，它是區(qū)域的連貫性在相鄰兩掃描線上的反映。,當(dāng)掃描線與多邊形P的交點是P的頂點時，則稱該交點為奇點。以上所述多邊形的三種形式的連貫性都基于這樣的幾何事實：每一條掃描線與多邊形P的邊界的交點個數(shù)都是偶數(shù)。但是如果把每一奇點簡單地計為一個交點或者簡單地計為兩個交點，都可能出現(xiàn)奇數(shù)個交點。那

12、么如果保證交點數(shù)為偶數(shù)呢？,奇點的處理,奇點的處理,若奇點做一個交點處理，則情況A，交點個數(shù)不是偶數(shù)。若奇點做兩個交點處理，則情況B，交點個數(shù)不是偶數(shù)。,奇點的處理,多邊形P的頂點可分為兩類：極值奇點和非極值奇點。如果(yi-1 - yi)(yi+1 - yi)≥0，則稱頂點Pi為極值點；否則稱Pi為非極值點。規(guī)定：奇點是非極值點時，該點按兩個交點計算，否則按一個交點計算。,數(shù)據(jù)結(jié)構(gòu)與實現(xiàn)步驟,算法基本思想：首先取d=yin。容易求

13、得掃描線y=d上的交點序列為xdj1,xdj2,…xdjn ，這一序列由位于掃描線y=d上的多邊形P的頂點組成。 由yin的交點序列開始，根據(jù)多邊形的邊的連貫性，按從上到下的順序求得各條掃描線的交點序列；根據(jù)掃描線的連貫性，可確定各條掃描線上位于多邊形P內(nèi)的區(qū)段，并表示成點陣形式。,數(shù)據(jù)結(jié)構(gòu)與實現(xiàn)步驟,所有的邊和掃描線求交，效率很低。因為一條掃描線往往只和少數(shù)幾條邊相交。如何判斷多邊形的一條邊與掃描線是否相交？與當(dāng)前掃描線相

14、交的邊稱為活性邊（active edge)，把它們按與掃描線交點x坐標(biāo)遞增的順序存入一個鏈表中，邊的活化鏈表 （ AEL, Active edge table)。它記錄了多邊形邊沿掃描線的交點序列。只需對當(dāng)前掃描線的活動邊表作更新，即可得到下一條掃描線的活動邊表。,數(shù)據(jù)結(jié)構(gòu)與實現(xiàn)步驟,如何計算下一條掃描線與邊的交點。直線方程：ax+by+c = 0當(dāng)前交點坐標(biāo)：(xi, yi)下一交點坐標(biāo)：(xi+1,yi+1)xi+1= (

15、(-byi+1)-c)/a = ((-byi+1)-c)/a =xi-b/a=xi+1/mi活動邊表中需要存放的信息：x：當(dāng)前掃描線與邊的交點dx＝-b/a：從當(dāng)前掃描線到下一條掃描線之間的x增量ymax：邊所交的最高掃描線,數(shù)據(jù)結(jié)構(gòu)與實現(xiàn)步驟,為了方便邊的活化鏈表的更新，建立另一個表-邊表，存放在該掃描線第一次出現(xiàn)的邊。存放的信息：x：掃描線與該邊的初始交點dx：x的增量ymax：該邊的最大y值,即算法中采

16、用較靈活的數(shù)據(jù)結(jié)構(gòu)。它由邊的分類表ET（Edge Table）和邊的活化鏈表AEL（Active Edge List）兩部分組成。 表結(jié)構(gòu)ET和AEL中的基本元素為多邊形的邊。邊的結(jié)構(gòu)由以下四個域組成： ymax 邊的上端點的y坐標(biāo)； x 在ET中表示邊的下端點的x坐標(biāo)，在AEL中則表示邊與掃描線的交點的坐標(biāo)； Δx 邊的斜率的倒數(shù)； next 指向下一條邊的指針

17、。,數(shù)據(jù)結(jié)構(gòu)與實現(xiàn)步驟,數(shù)據(jù)結(jié)構(gòu)與實現(xiàn)步驟,邊的分類表ET是按邊的下端點的y坐標(biāo)對非水平邊進(jìn)行分類的指針數(shù)組。下端點的y坐標(biāo)的值等于i的邊歸入第i類。有多少條掃描線，就設(shè)多少類。同一類中，各邊按x值（x值相等時，按Δx的值）遞增的順序排列成行。,邊表,(Ymax, x,Δx, next),活動邊表的例子,活動邊表的例子,算法實現(xiàn)步驟,這樣，當(dāng)建立了邊的分類表ET后，掃描線算法可按下列步驟進(jìn)行： （1）取掃描線縱坐標(biāo)y的初始值為E

18、T中非空元素的最小序號。 （2）將邊的活化鏈表AEL設(shè)置為空。 （3）按從下到上的順序?qū)v坐標(biāo)值為y的掃描線（當(dāng)前掃描線）執(zhí)行下列步驟，直到邊的分類表ET和邊的活化鏈表都變成空為止。,算法實現(xiàn)步驟,1）如邊分類表ET中的第y類元素非空，則將屬于該類的所有邊從ET中取出并插入邊的活化鏈表中，AEL中的各邊按照x值（當(dāng)x值相等時，按Δx值）遞增方向排序。2）若相對于當(dāng)前掃描線，邊的活化鏈表AEL非空，則將AEL中的邊兩兩依

19、次配對，即1，2邊為一對，3，4邊為一對，依次類推。每一對邊與當(dāng)前掃描線的交點所構(gòu)成的區(qū)段位于多邊形內(nèi)，依次對這些區(qū)段上的點（象素）按多邊形屬性著色。3）將邊的活化鏈表AEL中滿足y=ymax的邊刪去。4）將邊的活化鏈表AEL剩下的每一條邊的x域累加Δx，即x:=x+Δx。5）將當(dāng)前的掃描線的縱坐標(biāo)值y累加1，即y:=y+1。,掃描線算法,特點：算法效率較高。缺點：對各種表的維持和排序開銷太大，適合軟件實現(xiàn)而不適合硬件實現(xiàn)。,

20、掃描線算法,問題：如何處理多邊形的水平邊？如何修改掃描線算法，使它能處理邊自交的多邊形？,1. 對多邊形的每一條邊進(jìn)行掃描轉(zhuǎn)換，即對多邊形邊界所經(jīng)過的象素作一個邊界標(biāo)志。2.填充。對每條與多邊形相交的掃描線，按從左到右的順序，逐個訪問該掃描線上的象素。取一個布爾變量inside來指示當(dāng)前點的狀態(tài)，若點在多邊形內(nèi)，則inside為真。若點在多邊形外，則inside為假。Inside 的初始值為假，每當(dāng)當(dāng)前訪問象素為被打上標(biāo)志的點

21、，就把inside取反。對未打標(biāo)志的點，inside不變。,邊界標(biāo)志算法,,邊界標(biāo)志算法:算法過程,void edgemark_fill(polydef, color)多邊形定義 polydef； int color;{ 對多邊形polydef 每條邊進(jìn)行直線掃描轉(zhuǎn)換； inside = FALSE; for (每條與多邊形polydef相交的掃描線y ) for (掃描線上每個象素x )

22、 { if(象素 x 被打上邊標(biāo)志) inside = ! (inside); if(inside！= FALSE) drawpixel (x, y, color); else drawpixel (x, y, background); } },邊界標(biāo)志算法,用軟件實現(xiàn)時，掃描線算法與邊界標(biāo)志算法的執(zhí)行速度幾乎相同，但由于邊界標(biāo)志

23、算法不必建立維護(hù)邊表以及對它進(jìn)行排序，所以邊界標(biāo)志算法更適合硬件實現(xiàn)，這時它的執(zhí)行速度比有序邊表算法快一至兩個數(shù)量級。,邊界標(biāo)志算法,思考：如何處理邊界的交點個數(shù)使其成為偶數(shù)？,第四章多邊形的掃描轉(zhuǎn)換與區(qū)域填充,4.1多邊形掃描轉(zhuǎn)換4.2區(qū)域填充,,4.2區(qū)域填充算法,區(qū)域指已經(jīng)表示成點陣形式的填充圖形，它是象素的集合。區(qū)域填充指先將區(qū)域的一點賦予指定的顏色，然后將該顏色擴展到整個區(qū)域的過程。區(qū)域填充算法要求區(qū)域是連通的,4.2

24、區(qū)域填充,表示方法：內(nèi)點表示、邊界表示內(nèi)點表示枚舉出區(qū)域內(nèi)部的所有像素內(nèi)部的所有像素著同一個顏色邊界像素著與內(nèi)部像素不同的顏色邊界表示枚舉出邊界上所有的像素邊界上的所有像素著同一顏色內(nèi)部像素著與邊界像素不同的顏色,4.2區(qū)域填充,區(qū)域填充要求區(qū)域是連通的連通性 4連通、8連通4連通：8連通,4.2區(qū)域填充,4連通與8連通區(qū)域的區(qū)別連通性： 4連通可看作8連通區(qū)域，但對邊界有要求對邊界的要求,適

25、合于內(nèi)點表示區(qū)域的填充算法設(shè)G為一內(nèi)點表示的區(qū)域，(x,y)為區(qū)域內(nèi)一點，old_color為G的原色。現(xiàn)取(x,y)為種子點對區(qū)域G進(jìn)行填充：即先置像素(x,y)的顏色為new_color，然后逐步將整個區(qū)域G都置為同樣的顏色。 步驟如下：種子象素入棧，當(dāng)棧非空時，執(zhí)行如下三步操作： （1）棧頂象素出棧； （2）將出棧象素置成多邊形色； （3）按上、下、左、右的順序檢查與出棧象素相鄰的四個象素，若其中某個象素不在邊界上

26、且未置成多邊形色，則把該象素入棧。,種子填充算法,種子填充算法,例：多邊形由P0P1P2P3P4構(gòu)成，P0(1,5)P1(5,5)P2(7,3)P3(7,1)P4(1,1)設(shè)種子點為（3，3），搜索的方向是上、下、左、右。依此類推，最后像素被選中并填充的次序如圖中箭頭所示,(2 10 8 12)(3 7 13 10 8 12)(4 6 14 7 13 10 8 12)(5 6 14 7 13 10 8 12)……,種子填充算法

27、,遞歸算法可實現(xiàn)如下,void FloodFill4(int x,int y,int oldColor,int newColor){ if(GetPixel(x,y) == oldColor) { PutPixel(x,y,newColor); FloodFill4(x,y+1,oldColor,newColor); FloodFill4(x,y-1,oldColor,newColor); FloodFi

28、ll4(x-1,y,oldColor,newColor); FloodFill4(x+1,y,oldColor,newColor); }}/*end of FloodFill4()*/,種子填充算法,邊界表示的4連通區(qū)域,void BoundaryFill4(int x,int y,int boundaryColor,int newColor){int color;color = GetPixel(x,y);

29、if((color != boundaryColor) && (color != newColor)){PutPixel(x,y,newColor);BoundaryFill4(x,y+1,oldColor,newColor);BoundaryFill4(x,y-1,oldColor,newColor);BoundaryFill4(x-1,y,oldColor,newColor);Bound

30、aryFill4(x+1,y,oldColor,newColor);}}/*end of BoundaryFill4()*/,該算法也可以填充有孔區(qū)域。 缺點：(1) 有些象素會入棧多次，降低算法效率；棧結(jié)構(gòu)占空間。(2) 遞歸執(zhí)行，算法簡單，但效率不高，區(qū)域內(nèi)每一象素都引起一次遞歸，進(jìn)/出棧，費時費內(nèi)存。改進(jìn)算法，減少遞歸次數(shù)，提高效率。解決方法是用掃描線填充算法,種子填充算法,掃描線算法,掃描線算法目標(biāo)：減少遞

31、歸層次適用于邊界表示的4連通區(qū)域算法思想：在任意不間斷區(qū)間中只取一個種子像素（不間斷區(qū)間指在一條掃描線上一組相鄰元素），填充當(dāng)前掃描線上的該段區(qū)間；然后確定與這一區(qū)段相鄰的上下兩條掃描線上位于區(qū)域內(nèi)的區(qū)段，并依次把它們保存起來，反復(fù)進(jìn)行這個過程，直到所保存的個區(qū)段都填充完畢。,掃描線填充算法,(1)初始化：堆棧置空。將種子點（x，y）入棧。(2)出棧：若?？談t結(jié)束。否則取棧頂元素（x，y），以y作為當(dāng)前掃描線。(3)填充并確定種

32、子點所在區(qū)段：從種子點（x，y）出發(fā)，沿當(dāng)前掃描線向左、右兩個方向填充，直到邊界。分別標(biāo)記區(qū)段的左、右端點坐標(biāo)為xl和xr。(4)并確定新的種子點：在區(qū)間[xl，xr]中檢查與當(dāng)前掃描線y上、下相鄰的兩條掃描線上的象素。若存在非邊界、未填充的象素，則把每一區(qū)間的最右象素作為種子點壓入堆棧，返回第（2）步。上述算法對于每一個待填充區(qū)段，只需壓棧一次；因此，掃描線填充算法提高了區(qū)域填充的效率。,掃描線算法分析（舉例分析）,該算法也可以填

33、充有孔區(qū)域。,像素中的序號標(biāo)指它所在區(qū)段位于堆棧中的位置,掃描線算法分析（舉例分析）,,掃描線算法分析（舉例分析）,,掃描線算法分析（舉例分析）,,多邊形掃描轉(zhuǎn)換與區(qū)域填充方法比較,聯(lián)系：都是光柵圖形面著色，用于真實感圖形顯示。可相互轉(zhuǎn)換。多邊形的掃描轉(zhuǎn)換轉(zhuǎn)化為區(qū)域填充問題：當(dāng)給定多邊形內(nèi)一點為種子點，并用Bresenham或DDA算法將多邊形的邊界表示成八連通區(qū)域后，則多邊形的掃描轉(zhuǎn)換轉(zhuǎn)化為區(qū)域填充。區(qū)域填充轉(zhuǎn)化為多邊形的掃描轉(zhuǎn)換