第四章二維填充與多邊形掃描轉(zhuǎn)化.ppt

1、第五章 多邊形的掃描轉(zhuǎn)換與區(qū)域填充,教學(xué)內(nèi)容: 1、多邊形掃描轉(zhuǎn)換： 通過確定穿越區(qū)域的掃描線的覆蓋去件來填充。 2、區(qū)域填充： 是從給定的位置開始涂描直到指定的邊界條件為止。,關(guān)于光柵圖形 本質(zhì)：點陣表示 特點：面著色，畫面明暗自然、色彩豐富 與線框圖相比：更加生動、直觀、真實感強,線框多邊形物體,填充多邊形物體,5.1.1概念 多邊形分為凸多邊形、凹多邊形、含內(nèi)環(huán)的多邊形。,5.1多邊形的掃描轉(zhuǎn)換,多邊形的表示方法 頂點表示 點陣表示 頂點表示：用多邊形頂點的序列來刻劃多邊形。 優(yōu)點:直觀、幾何意義強、占內(nèi)存少； 缺點:難以判斷哪些像素位于多邊形內(nèi)部,不能直接用于面著色。,點陣表示：用位于

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

3、轉(zhuǎn)換的四舍五入原則導(dǎo)致部分像素位于多邊形之外，從而不可用 假定非水平邊與掃描線y=e 相交，交點的橫坐標(biāo)為x, 規(guī)則如下,規(guī)則1： X為小數(shù)，即交點落于掃描線上兩個相鄰像素之間 (a)交點位于左邊之上，向右取整 (b)交點位于右邊之上，向左取整,規(guī)則2： 邊界上象素的取舍問題，避免填充擴大化。 解決方法： 邊界象素：規(guī)定落在右上邊界的象素不予填充。 具體實現(xiàn)時，只要對掃描線與多邊形的相交區(qū)間左閉右開,規(guī)則3： 掃描線與多邊形的頂點相交時，交點的取舍，保證交點正確配對。 解決方法： 檢查兩相鄰邊在掃描線的哪一側(cè)。 只要檢查頂點的兩條邊的另外兩個端點的Y值，兩個Y值中大于交點Y值的個數(shù)是0，1，2

4、，來決定取0，1，2個交點。,y=yik,y=yik+1,一、掃描線算法 基本思想：按掃描線順序，計算掃描線與多邊形的相交區(qū)間（像素），再用相應(yīng)的顏色（或圖案）顯示這些像素。,算法步驟： (1)確定多邊形所占有的最大掃描線數(shù)。即得到多邊形頂點的最小和最大y值。（Ymin和Ymax) (2)從y=ymin到y(tǒng)=ymax:每次用一條掃描線填充。 (3)填充步驟： 求交：計算掃描線與多邊形各邊的交點。 排序：所有交點按遞增的順序排序。 交點配對：第一個與第二個，第三個與第四個等，每對交點代表掃描線與多邊行的一個相交區(qū)間。 區(qū)間填色：把這些相交區(qū)間內(nèi)的像素置成不同于背景的填充色。,存在的問題： 當(dāng)掃描

5、線與多邊形頂點相交時，交點的取舍問題 解決的方法： 共享頂點的兩條邊分別落在掃描線的兩邊，則交點只算一個 共享頂點的兩條邊在掃描線的一側(cè)，則交點算或者個,二、改進的有效邊表算法（Y-連貫性算法） （）有效邊（Active Edge):與該掃描線相關(guān)的多邊形的邊。 邊的相關(guān)性： 若pi(xi,yi),則有,掃描線Yi+1,掃描線Yi,Pi,Pi+1,pi+1(xi+1,yi+1),其中,xi+1=xi+1/k,yi+1=yi+1,兩邊的相關(guān)性為每條邊建立一個邊記錄，其結(jié)點內(nèi)容為：,(2)邊表（：Edge Table):是一個包含多邊形全部邊記錄的表。,邊表,縱向鏈表的構(gòu)造：長度為最大掃描線數(shù)。

6、將相關(guān)邊（該掃描線）的記錄接點鏈入。 一個結(jié)點（縱向鏈）有多個相關(guān)邊時，按x|ymin由小到大的順序；如果x|ymin相等，則按k由小到大的順序。 在ET表中： 與X軸平行的邊不計入 頂點：如前法則相同。,（）有效邊表（活動邊表）：AET(Active Edge Table) 將有效邊按與掃描線交點x坐標(biāo)遞增的順序存放在一個鏈表中，稱此鏈表為AET。 結(jié)點內(nèi)容為：,其中x為當(dāng)前掃描線與邊的交點,活動邊表的例子,活動邊表的例子,(4)算法實現(xiàn)步驟,這樣，當(dāng)建立了邊的分類表ET后，掃描線算法可按下列步驟進行： （1）取掃描線縱坐標(biāo)y的初始值為ET中非空元素的最小序號。 （2）將邊的活化鏈表AEL設(shè)

7、置為空。 （3）按從下到上的順序?qū)v坐標(biāo)值為y的掃描線（當(dāng)前掃描線）執(zhí)行下列步驟，直到邊的分類表ET和邊的活化鏈表都變成空為止。,A）如邊分類表ET中的第y類元素非空，則將屬于該類的所有邊從ET中取出并插入邊的活化鏈表中，AEL中的各邊按照x值（當(dāng)x值相等時，按x值）遞增方向排序。 B）若相對于當(dāng)前掃描線，邊的活化鏈表AEL非空，則將AEL中的邊兩兩依次配對，即1，2邊為一對，3，4邊為一對，依次類推。每一對邊與當(dāng)前掃描線的交點所構(gòu)成的區(qū)段位于多邊形內(nèi)，依次對這些區(qū)段上的點（象素）按多邊形屬性著色。 C）將邊的活化鏈表AEL中滿足y=ymax的邊刪去。 D）將邊的活化鏈表AEL剩下的每一條邊的

8、x域累加x，即x:=x+x。(x=1/k) E）將當(dāng)前的掃描線的縱坐標(biāo)值y累加1，即y=y+1。,多邊形邊表實例,多邊形掃描轉(zhuǎn)換實例,多邊形掃描轉(zhuǎn)換實例,多邊形掃描轉(zhuǎn)換實例,多邊形掃描轉(zhuǎn)換實例,多邊形掃描轉(zhuǎn)換實例,多邊形掃描轉(zhuǎn)換實例,多邊形掃描轉(zhuǎn)換實例,多邊形掃描轉(zhuǎn)換實例,多邊形掃描轉(zhuǎn)換實例,多邊形掃描轉(zhuǎn)換實例,多邊形掃描轉(zhuǎn)換實例,掃描線算法,特點：算法效率較高。 缺點：對各種表的維持和排序開銷太大，適合軟件實現(xiàn)而不適合硬件實現(xiàn)。,掃描線算法,問題： 如何處理多邊形的水平邊？ 如何修改掃描線算法，使它能處理邊自交的多邊形？,1. 對多邊形的每一條邊進行掃描轉(zhuǎn)換，即對多邊形邊界所經(jīng)過的象素作一個

9、邊界標(biāo)志。 2.填充。對每條與多邊形相交的掃描線，按從左到右的順序，逐個訪問該掃描線上的象素。 取一個布爾變量inside來指示當(dāng)前點的狀態(tài)，若點在多邊形內(nèi)，則inside為真。若點在多邊形外，則inside為假。 Inside 的初始值為假，每當(dāng)當(dāng)前訪問象素為被打上標(biāo)志的點，就把inside取反。對未打標(biāo)志的點，inside不變。,5.1.3邊界標(biāo)志算法,邊界標(biāo)志算法:算法過程,void edgemark_fill(polydef, color) 多邊形定義 polydef； int color; 對多邊形polydef 每條邊進行直線掃描轉(zhuǎn)換； inside = FALSE; for (每

10、條與多邊形polydef相交的掃描線y ) for (掃描線上每個象素x ) 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)志算法不必建立維護邊表以及對它進行排序，所以邊界標(biāo)志算法更適合硬件實現(xiàn)，這時它的執(zhí)行速度比有序邊表算法快一至兩個數(shù)量級。,邊界標(biāo)志算法,思考：如何處理邊界的交點個數(shù)使其成為偶數(shù)？,5.2區(qū)域填充算法,區(qū)

11、域指已經(jīng)表示成點陣形式的填充圖形，它是象素的集合。 區(qū)域填充指先將區(qū)域的一點賦予指定的顏色，然后將該顏色擴展到整個區(qū)域的過程。區(qū)域填充算法要求區(qū)域是連通的,表示方法：內(nèi)點表示、邊界表示 內(nèi)點表示 枚舉出區(qū)域內(nèi)部的所有像素 內(nèi)部的所有像素著同一個顏色 邊界像素不能著上述顏色,邊界表示: 枚舉出邊界上所有的像素 邊界上的所有像素著同一顏色 內(nèi)部像素著與邊界像素不同的顏色,區(qū)域填充要求區(qū)域是連通的 連通性 4連通、8連通 4連通： 8連通,4連通與8連通區(qū)域的區(qū)別 連通性： 4連通可看作8連通區(qū)域，但對邊界有要求 對邊界的要求,適合于內(nèi)點表示區(qū)域的填充算法 設(shè)G為一內(nèi)點表示的區(qū)域，(x,y)為區(qū)域內(nèi)

12、一點，old_color為G的原色?，F(xiàn)取(x,y)為種子點對區(qū)域G進行填充：即先置像素(x,y)的顏色為new_color，然后逐步將整個區(qū)域G都置為同樣的顏色。 步驟如下： 種子象素入棧，當(dāng)棧非空時，執(zhí)行如下三步操作： （1）棧頂象素出棧； （2）將出棧象素置成多邊形色； （3）按上、下、左、右的順序檢查與出棧象素相鄰的四個象素，若其中某個象素不在邊界上且未置成多邊形色，則把該象素入棧。,5.2.1種子填充算法,例：多邊形由P0P1P2P3P4構(gòu)成，P0(1,5)P1(5,5)P2(7,3)P3(7,1)P4(1,1) 設(shè)種子點為（3，2），搜索的方向是上、下、左、右。依此類推，最后像素被選

13、中并填充的次序如圖中箭頭所示,s1,2 3 4,9 8 7 6 5,11 12 13 14 15,10,(2 10 8 12) (3 7 13 10 8 12) (4 6 14 7 13 10 8 12) ,遞歸算法可實現(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); Flo

14、odFill4(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); if(color != boundaryColor) /*end of BoundaryFill4()*/,該算法也可以填充有孔區(qū)域。 缺點： (1) 有些象素會入棧多次，降低算法效率；棧結(jié)構(gòu)占

15、空間。 (2) 遞歸執(zhí)行，算法簡單，但效率不高，區(qū)域內(nèi)每一象素都引起一次遞歸，進/出棧，費時費內(nèi)存。 改進算法，減少遞歸次數(shù)，提高效率。 解決方法是用掃描線填充算法,5.2.2掃描線算法,一、掃描線算法 目標(biāo)：減少遞歸層次 適用于邊界表示的4連通區(qū)域 算法思想：在任意不間斷區(qū)間中只取一個種子像素（不間斷區(qū)間指在一條掃描線上一組相鄰元素），填充當(dāng)前掃描線上的該段區(qū)間；然后確定與這一區(qū)段相鄰的上下兩條掃描線上位于區(qū)域內(nèi)的區(qū)段，并依次把它們保存起來，反復(fù)進行這個過程，直到所保存的個區(qū)段都填充完畢。,二、掃描線填充算法,（1)初始化：堆棧置空。將種子點（x，y）入棧。 (2)出棧：若?？談t結(jié)束。否則取

16、棧頂元素（x，y），以y作為當(dāng)前掃描線。 (3)填充并確定種子點所在區(qū)段：從種子點（x，y）出發(fā)，沿當(dāng)前掃描線向左、右兩個方向填充，直到邊界。分別標(biāo)記區(qū)段的左、右端點坐標(biāo)為xl和xr。 (4)并確定新的種子點：在區(qū)間xl，xr中檢查與當(dāng)前掃描線y上、下相鄰的兩條掃描線上的象素。若存在非邊界、未填充的象素，則把每一區(qū)間的最右象素作為種子點壓入堆棧，返回第（2）步。 上述算法對于每一個待填充區(qū)段，只需壓棧一次；因此，掃描線填充算法提高了區(qū)域填充的效率。,三、掃描線算法分析（舉例分析）,該算法也可以填充有孔區(qū)域。,像素中的序號標(biāo)指它所在區(qū)段位于堆棧中的位置,多邊形掃描轉(zhuǎn)換與區(qū)域填充方法比較,聯(lián)系：都是光柵圖形面著色，用于真實感圖形顯示?？上嗷マD(zhuǎn)換。 多邊形的掃描轉(zhuǎn)換轉(zhuǎn)化為區(qū)域填