1、第四講 區(qū)域填充 計(jì)算機(jī)圖形學(xué)中，多邊形區(qū)域有兩種重要的表示方法：頂計(jì)算機(jī)圖形學(xué)中，多邊形區(qū)域有兩種重要的表示方法：頂 點(diǎn)表示和點(diǎn)陣表示。點(diǎn)表示和點(diǎn)陣表示。 所謂頂點(diǎn)表示，即是用多邊形的頂點(diǎn)序列來(lái)表示多邊形。所謂頂點(diǎn)表示，即是用多邊形的頂點(diǎn)序列來(lái)表示多邊形。 這種表示直觀、幾何意義強(qiáng)、占內(nèi)存少，易于進(jìn)行幾何變換，這種表示直觀、幾何意義強(qiáng)、占內(nèi)存少，易于進(jìn)行幾何變換， 但由于它沒(méi)有明確指出哪些像素在多邊形內(nèi)，故不能直接用但由于它沒(méi)有明確指出哪些像素在多邊形內(nèi)，故不能直接用 于區(qū)域填充。于區(qū)域填充。 所謂點(diǎn)陣表示，則是用位于多邊形內(nèi)的像素集合來(lái)刻畫(huà)多所謂點(diǎn)陣表示，則是用位于多邊形內(nèi)的像素集合來(lái)刻畫(huà)

2、多 邊形。這種表示丟失了許多幾何信息，但便于進(jìn)行填充。邊形。這種表示丟失了許多幾何信息，但便于進(jìn)行填充。 根據(jù)區(qū)域的定義，可以采用不同的填充算法，其中最具代表根據(jù)區(qū)域的定義，可以采用不同的填充算法，其中最具代表 性的是：適應(yīng)于頂點(diǎn)表示的掃描線類(lèi)算法和適應(yīng)于點(diǎn)陣表示性的是：適應(yīng)于頂點(diǎn)表示的掃描線類(lèi)算法和適應(yīng)于點(diǎn)陣表示 的種子填充類(lèi)算法。的種子填充類(lèi)算法。 復(fù)雜邊界 從內(nèi)部指定位置 開(kāi)始填充，遞歸 填充直至邊界 簡(jiǎn)單邊界 通過(guò)掃描線與邊 界交點(diǎn)確定填充 區(qū)域 掃描線算法 掃描線多邊形區(qū)域填充算法基本原理是，待填充區(qū)域按掃描線多邊形區(qū)域填充算法基本原理是，待填充區(qū)域按Y方向方向 (X方向亦可方向亦可

3、)掃描線順序掃描生成。具體實(shí)現(xiàn)時(shí)，首先按掃描掃描線順序掃描生成。具體實(shí)現(xiàn)時(shí)，首先按掃描 線順序，計(jì)算掃描線與多邊形的相交區(qū)間；再用要求的顏色填線順序，計(jì)算掃描線與多邊形的相交區(qū)間；再用要求的顏色填 充這些區(qū)間內(nèi)的像素，即完成這一條掃描線的填充工作。區(qū)間充這些區(qū)間內(nèi)的像素，即完成這一條掃描線的填充工作。區(qū)間 的端點(diǎn)可以通過(guò)計(jì)算掃描線與多邊形邊界線的交點(diǎn)獲得。對(duì)于的端點(diǎn)可以通過(guò)計(jì)算掃描線與多邊形邊界線的交點(diǎn)獲得。對(duì)于 一條掃描線，多邊形的填充過(guò)程可以分為四個(gè)步驟：一條掃描線，多邊形的填充過(guò)程可以分為四個(gè)步驟： (1) 求交：計(jì)算掃描線與多邊形各邊的交點(diǎn)；求交：計(jì)算掃描線與多邊形各邊的交點(diǎn)； (2)

4、 排序：把所有交點(diǎn)按排序：把所有交點(diǎn)按x值遞增順序排序；值遞增順序排序； (3)配對(duì)：第一個(gè)與第二個(gè)，第三個(gè)與第四配對(duì)：第一個(gè)與第二個(gè)，第三個(gè)與第四 個(gè)等等；每對(duì)交點(diǎn)代表掃描線與多邊形的一個(gè)等等；每對(duì)交點(diǎn)代表掃描線與多邊形的一 個(gè)相交區(qū)間；個(gè)相交區(qū)間； (4)填色：把相交區(qū)間內(nèi)的像素置成多邊形填色：把相交區(qū)間內(nèi)的像素置成多邊形 顏色，把相交區(qū)間外的像素置成背景色。顏色，把相交區(qū)間外的像素置成背景色。 為了提高速度，假定當(dāng)前掃描線與多邊形某一條邊的交點(diǎn)的為了提高速度，假定當(dāng)前掃描線與多邊形某一條邊的交點(diǎn)的x 坐標(biāo)為坐標(biāo)為xi，則下一條掃描線與該邊的交點(diǎn)不要重新計(jì)算，而是，則下一條掃描線與該邊的交

5、點(diǎn)不要重新計(jì)算，而是 通過(guò)增加一個(gè)增量通過(guò)增加一個(gè)增量x來(lái)獲得。具體方法是：來(lái)獲得。具體方法是： 設(shè)該邊的直線方程為：設(shè)該邊的直線方程為：ax+by+c=0； 若若yyi，x=xi；則當(dāng)；則當(dāng)y = yi+1= yi+1時(shí)，時(shí)， 其中其中 為常數(shù)，為常數(shù)， ; a b i x)c i yb( a i x 1 1 1 a b x yi yi+1 多邊形Pi的頂點(diǎn)可分為兩類(lèi)：如果(yi-1 - yi)(yi+1 - yi)0，則稱(chēng)頂點(diǎn)Pi為局 部最高點(diǎn)或最低點(diǎn)，按兩個(gè)交點(diǎn)計(jì)算， 否則按一個(gè)交點(diǎn)計(jì)算。 不計(jì)算水平邊和 掃描線的交點(diǎn) 水平邊處理 數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟 輸入?yún)?shù) 頂點(diǎn)數(shù)和頂點(diǎn)坐標(biāo) 數(shù)據(jù)結(jié)構(gòu)

6、 有序邊表 活化邊表 有序邊表 有序邊表的構(gòu)建 按頂點(diǎn)輸入順序依次形 成邊，存儲(chǔ)到每條最小 Y值所對(duì)應(yīng)的掃描線位 置（水平邊除外），相 同最小Y值的邊按較低 頂點(diǎn)X值的升序排列。 有序邊表結(jié)構(gòu) typedef struct tEage int yUpper; float xIntersect; float dxPerScan; struct tEage *next; Eage 活化邊表 把與當(dāng)前掃描線 相交的邊稱(chēng)為活 化邊，并把它們 按與掃描線交點(diǎn) X坐標(biāo)遞增的順 序存放在一個(gè)鏈 表中，形成活化 邊表。 算法中采用較靈活的數(shù)據(jù)結(jié)構(gòu)。它由邊的分有序邊 表ET（Edge Table）和邊的活化邊表

7、AEL（Active Edge Table ）兩部分組成。 表結(jié)構(gòu)ET和AET中的基本元素為多邊形的邊。邊 的結(jié)構(gòu)由以下四個(gè)域組成： ymax 邊的上端點(diǎn)的y坐標(biāo)； x 在ET中表示邊的下端點(diǎn)的x坐標(biāo)，在 AET中則表示邊與掃描線的交點(diǎn)的坐標(biāo)； x 邊的斜率的倒數(shù)； next 指向下一條邊的指針。 表結(jié)構(gòu) 舉例： 724 P5 P1 78-1 P2 P1 620 P4 P5 36-2 P3 P4 560.5 P3 P2 (Y(Ymax max, , x,x, next) x,x, next) 有序邊表 活化邊表 34-2 P3 P4 56.50.5 P3 P2 掃描線2 AET指針 620 P

8、4 P5 570.5 P3 P2 掃描線3 AET指針 (Y(Ymax max, , x,x, next) x,x, next) 36-2 P3 P4 560.5 P3 P2 掃描線1 AET指針 620 P4 P5 57.50.5 P3 P2 掃描線4 AET指針 620 P4 P5 78-1 P2 P1 掃描線5 AET指針 724 P5 P1 78-1 P2 P1 掃描線6 AET指針 void polyfill (polygon, color) for (各條掃描線，標(biāo)識(shí)為各條掃描線，標(biāo)識(shí)為i) 初始化新邊表頭指針初始化新邊表頭指針NET i； 把把ymin = i 的邊放進(jìn)邊表的邊放

9、進(jìn)邊表NET i； y = 最低掃描線號(hào)；最低掃描線號(hào)； 初始化活性邊表初始化活性邊表AET為空；為空； for (各條掃描線各條掃描線i) 把新邊表把新邊表NETi中的邊結(jié)點(diǎn)用插入排序法插入中的邊結(jié)點(diǎn)用插入排序法插入AET表，使之按表，使之按x坐標(biāo)遞增順序排列；坐標(biāo)遞增順序排列； 遍歷遍歷AET表，把配對(duì)交點(diǎn)區(qū)間上的像素表，把配對(duì)交點(diǎn)區(qū)間上的像素(x, y)，用，用drawpixel (x, y, color)改寫(xiě)像素顏色值改寫(xiě)像素顏色值 ； 遍歷遍歷AET表，把表，把y max= i的結(jié)點(diǎn)從的結(jié)點(diǎn)從AET表中刪除，并把表中刪除，并把y max i結(jié)點(diǎn)的結(jié)點(diǎn)的x值遞增值遞增 x； 多邊形填充

10、的算法流程 掃描線算法 特點(diǎn)：算法效率較高。 缺點(diǎn)：對(duì)各種表的維持和排序開(kāi)銷(xiāo)太 大，適合軟件實(shí)現(xiàn)而不適合硬件實(shí)現(xiàn)。 內(nèi)外測(cè)試 目標(biāo)：鑒別非標(biāo)準(zhǔn)多邊形的內(nèi)部區(qū)域 自相交多邊形。 方法 奇偶規(guī)則 非零環(huán)繞數(shù)規(guī)則 奇偶規(guī)則 從位置P作不經(jīng) 過(guò)頂點(diǎn)的射線 計(jì)算射線穿過(guò)多 邊形的邊數(shù) 奇數(shù)為內(nèi)部點(diǎn)， 否則為外部點(diǎn) 非零環(huán)繞數(shù)規(guī)則 環(huán)繞數(shù)初始為零； 從位置P作不經(jīng)過(guò) 頂點(diǎn)的射線； 多邊形從右至左穿 過(guò)射線，加1； 多邊形從左至右穿 過(guò)射線，減1； 非零為內(nèi)部點(diǎn)； 舉例： 種子填充算法 表示內(nèi)點(diǎn) 表示邊界點(diǎn) 區(qū)域：用點(diǎn)陣形式表示的填充圖形，是像素的集合。區(qū)域：用點(diǎn)陣形式表示的填充圖形，是像素的集合。 區(qū)域可

11、采用區(qū)域可采用內(nèi)點(diǎn)表示內(nèi)點(diǎn)表示和和邊界表示邊界表示兩種表示形式。兩種表示形式。 內(nèi)點(diǎn)表示法，指區(qū)域內(nèi)的所有像素著同一顏色；內(nèi)點(diǎn)表示法，指區(qū)域內(nèi)的所有像素著同一顏色； 邊界表示法，則是指區(qū)域的邊界點(diǎn)著同一顏色。邊界表示法，則是指區(qū)域的邊界點(diǎn)著同一顏色。 區(qū)域填充算法要求區(qū)域是連通的，因?yàn)橹挥性谶B通區(qū)域中，才區(qū)域填充算法要求區(qū)域是連通的，因?yàn)橹挥性谶B通區(qū)域中，才 可能將種子點(diǎn)的顏色擴(kuò)展到區(qū)域內(nèi)的其它點(diǎn)。區(qū)域可分為可能將種子點(diǎn)的顏色擴(kuò)展到區(qū)域內(nèi)的其它點(diǎn)。區(qū)域可分為4向向 連通區(qū)域和連通區(qū)域和8向連通區(qū)域。向連通區(qū)域。 指的是從區(qū)域上一點(diǎn)出發(fā)，可通過(guò)四個(gè)方向，指的是從區(qū)域上一點(diǎn)出發(fā)，可通過(guò)四個(gè)方向，

12、即上、下、左、右移動(dòng)的組合，在不越出區(qū)域的前提下，到達(dá)即上、下、左、右移動(dòng)的組合，在不越出區(qū)域的前提下，到達(dá) 區(qū)域內(nèi)的任意像素；區(qū)域內(nèi)的任意像素； 指的是從區(qū)域內(nèi)每一像素出發(fā)，可通過(guò)八個(gè)方指的是從區(qū)域內(nèi)每一像素出發(fā)，可通過(guò)八個(gè)方 向，即上、下、左、右、左上、右上、左下、右下這八個(gè)方向向，即上、下、左、右、左上、右上、左下、右下這八個(gè)方向 的移動(dòng)的組合來(lái)到達(dá)。的移動(dòng)的組合來(lái)到達(dá)。 四個(gè)方向運(yùn)動(dòng)四個(gè)方向運(yùn)動(dòng) 八個(gè)方向運(yùn)動(dòng)八個(gè)方向運(yùn)動(dòng) 四連通區(qū)域四連通區(qū)域 八連通區(qū)域八連通區(qū)域 算法原理：算法原理： 填充區(qū)域邊界填充區(qū)域邊界 以一種顏色指以一種顏色指 定，從區(qū)域的定，從區(qū)域的 一個(gè)內(nèi)部點(diǎn)開(kāi)一個(gè)內(nèi)部點(diǎn)

13、開(kāi) 始，由內(nèi)至外始，由內(nèi)至外 繪制直到邊界。繪制直到邊界。 適用于單色邊適用于單色邊 界的填充。界的填充。 四連通的局限性四連通的局限性 void FloodFill4(int x,int y,int oldcolor,int newcolor) if(GetPixel(x,y)=oldcolor) SetPixel(x,y,newcolor); FloodFill4(x,y+1,oldcolor,newcolor); FloodFill4(x,y-1,oldcolor,newcolor); FloodFill4(x-1,y,oldcolor,newcolor); FloodFill4(x+1

14、,y,oldcolor,newcolor); 設(shè)設(shè)(x,y)為內(nèi)點(diǎn)表示的為內(nèi)點(diǎn)表示的4連通區(qū)域內(nèi)的一點(diǎn)，連通區(qū)域內(nèi)的一點(diǎn)，oldcolor為區(qū)域的為區(qū)域的 原色，要將整個(gè)區(qū)域填充為新的顏色原色，要將整個(gè)區(qū)域填充為新的顏色newcolor。內(nèi)點(diǎn)表示的。內(nèi)點(diǎn)表示的 4連通區(qū)域的遞歸填充算法連通區(qū)域的遞歸填充算法: 簡(jiǎn)單的種子填充算法 void BoundaryFill4(int x,int y,int boundarycolor,int newcolor) int color; if(color!=newcolor BoundaryFill4 (x,y+1, boundarycolor,newco

15、lor); BoundaryFill4 (x,y-1, boundarycolor,newcolor); BoundaryFill4 (x-1,y, boundarycolor,newcolor); BoundaryFill4 (x+1,y, boundarycolor,newcolor); 掃描線種子填充算法 簡(jiǎn)單種子填充算法原理和程序都很簡(jiǎn)單，但由于多次遞歸，簡(jiǎn)單種子填充算法原理和程序都很簡(jiǎn)單，但由于多次遞歸， 費(fèi)時(shí)、費(fèi)內(nèi)存，效率不高。為了減少遞歸次數(shù)，提高效率可費(fèi)時(shí)、費(fèi)內(nèi)存，效率不高。為了減少遞歸次數(shù)，提高效率可 以采用掃描線種子填充算法。以采用掃描線種子填充算法。 算法的基本過(guò)程如下：

16、當(dāng)給定種子點(diǎn)算法的基本過(guò)程如下：當(dāng)給定種子點(diǎn)(x,y)時(shí)，首先填充種子時(shí)，首先填充種子 點(diǎn)所在掃描線上的位于給定區(qū)域的一個(gè)區(qū)段，然后確定與這點(diǎn)所在掃描線上的位于給定區(qū)域的一個(gè)區(qū)段，然后確定與這 一區(qū)段相連通的上、下兩條掃描線上位于給定區(qū)域內(nèi)的區(qū)段，一區(qū)段相連通的上、下兩條掃描線上位于給定區(qū)域內(nèi)的區(qū)段， 并依次保存下來(lái)。反復(fù)這個(gè)過(guò)程，直到填充結(jié)束。并依次保存下來(lái)。反復(fù)這個(gè)過(guò)程，直到填充結(jié)束。 1 2 3 4 1 2 3 4 5 1 2 3 4 5 1 2 3 4 1 2 3 4 1 2 3 區(qū)域填充的掃描線算法可由下列四個(gè)步驟實(shí)現(xiàn)：區(qū)域填充的掃描線算法可由下列四個(gè)步驟實(shí)現(xiàn)： (1)初始化：堆棧置空。將種子點(diǎn)初始化：堆棧置空。將種子點(diǎn)(x，y)入棧；入棧； (2)出棧：若棧空則結(jié)束。否則取棧頂元素出棧：若棧空則結(jié)束。否則取棧頂元素(x，y)，以，以y作為當(dāng)作為當(dāng) 前掃描線；前掃描線； (3)填充并確定種子點(diǎn)所在區(qū)段：從種子點(diǎn)填充并確定種子點(diǎn)所在區(qū)段：從種子點(diǎn)(x，y)