[理學(xué)]第四章 二維圖形的生成__區(qū)域填充.ppt

1、2021/3/29,西安工程大學(xué)計(jì)算機(jī)圖形學(xué),1,4.1、多邊形定義及表示 4.2、有序邊表填充算法(掃描線算法) 4.3、種子填充算法 4.4、種子掃描線算法,第四章、多邊形填充,多邊形是由折線段組成的封閉圖形。它由有序頂點(diǎn)的點(diǎn)集Pi（i=0n-1）及有向邊的線集Ei（i=0n-1）定義，n為多邊形的頂點(diǎn)數(shù)或邊數(shù)，且EiPiPi+1，i=0n-1 。這里PnP0，用以保證了多邊形的封閉性。多邊形可以分為凸、凹多邊形以 及環(huán)。,4.1、多邊形定義及表示,2021/3/29,西安工程大學(xué)計(jì)算機(jī)圖形學(xué),2,多邊形上任意兩頂點(diǎn)間的連線都在多邊形之內(nèi),凸點(diǎn)對應(yīng)的內(nèi)角小于180，只具有凸點(diǎn)的多邊形稱為凸

2、多邊形。,1.凸多邊形,2.凹多邊形,多邊形上任意兩頂點(diǎn)間的連線有不在多邊形內(nèi)部的部分，凹點(diǎn)對應(yīng)的內(nèi)角大于180，有一個(gè)凹點(diǎn)的多邊形稱為凹多邊形。,4.1、多邊形定義及表示,2021/3/29,西安工程大學(xué)計(jì)算機(jī)圖形學(xué),3,多邊形內(nèi)包含有另外的多邊形。如果規(guī)定：每條有向邊的左側(cè)為其內(nèi)部實(shí)面積區(qū)域。則當(dāng)觀察者沿著邊界行走時(shí)，內(nèi)部區(qū)域總在其左側(cè)，也就是說多邊形外輪廓線的環(huán)行方向?yàn)槟鏁r(shí)針，內(nèi)輪廓線的環(huán)行方向?yàn)轫槙r(shí)針。這種定義了環(huán)行方向的多邊形稱為環(huán)。,3.環(huán),4.1、多邊形定義及表示,在計(jì)算機(jī)圖形學(xué)中，多邊形有兩種示方法：頂點(diǎn)表示法和點(diǎn)陣表示法。,2021/3/29,西安工程大學(xué)計(jì)算機(jī)圖形學(xué),4,多

3、邊形的頂點(diǎn)表示法,P0,P1,P2,P3,P4,P5,多邊形的點(diǎn)陣表示法,P6,多邊形的掃描轉(zhuǎn)換,將多邊形的描述從頂點(diǎn)表示法變換到點(diǎn)陣表示法的過程，稱為多邊形的掃描轉(zhuǎn)換。即從多邊形的頂點(diǎn)信息出發(fā)，求出多邊形內(nèi)部的各個(gè)像素點(diǎn)信息。,2021/3/29,西安工程大學(xué)計(jì)算機(jī)圖形學(xué),5,2021/3/29,西安工程大學(xué)計(jì)算機(jī)圖形學(xué),6,矩形的填充,問題： 矩形是簡單的多邊形，那么為什么要單獨(dú)處理矩形？ 比一般多邊形可簡化計(jì)算。 應(yīng)用非常多，窗口系統(tǒng)。 共享邊界如何處理？ 原則：左閉右開，下閉上開,2021/3/29,西安工程大學(xué)計(jì)算機(jī)圖形學(xué),7,方法：,void FillRectangle(Recta

4、ngle *rect, int color) int x, y; for(y = rect.ymin; y = rect.ymax; y+;) for(x = rect.xmin; x = rect.xmax; x+;) PutPixel(x, y, color); /*end of FillRectangle()*/,矩形的填充,2021/3/29,西安工程大學(xué)計(jì)算機(jī)圖形學(xué),8,void FillPolygonPbyP(Polygon *P,int polygonColor) int x,y; for(y = ymin;y = ymax;y+) for(x = xmin;x = xmax;x

5、+) if(IsInside(P,x,y) PutPixel(x,y,polygonColor); else PutPixel(x,y,backgroundColor); /*end of FillPolygonPbyP()*/,#define MAX 100 Typedef struct int PolygonNum; / 多邊形頂點(diǎn)個(gè)數(shù) Point vertexcesMAX /多邊形頂點(diǎn)數(shù)組 Polygon / 多邊形結(jié)構(gòu),逐點(diǎn)判斷法,2021/3/29,西安工程大學(xué)計(jì)算機(jī)圖形學(xué),9,掃描線算法是多邊形填充的常用算法。與逐點(diǎn)判斷算法相比，掃描線算法充分利用了相鄰象素之間的連貫性，避免了對象

6、素的逐點(diǎn)判斷和反復(fù)求交的運(yùn)算，達(dá)到了減少了計(jì)算量和提高速度的目的。,4.2 掃描線算法,處理對象：非自交多邊形（邊與邊之間除了頂點(diǎn)外無其它交點(diǎn)）,2021/3/29,西安工程大學(xué)計(jì)算機(jī)圖形學(xué),10,設(shè)多邊形P的頂點(diǎn)Pi=(xi,yi),i=0,1,n，又設(shè)yi0, yi1,yin是各頂點(diǎn)Pi的坐標(biāo)yi的遞減數(shù)列，即yik yik+1, 0kn-1。這樣，當(dāng)yik yik+1,0 k n-1時(shí)，屏幕上位于y =yik和y =yik+1兩條掃描線之間的長方形區(qū)域被多邊形P的邊分割成若干梯形（三角形可看作其中一底邊長為零的梯形）它們具有下列性質(zhì)：,1、區(qū)域的連貫性,4.2 掃描線算法,2021/3/

7、29,西安工程大學(xué)計(jì)算機(jī)圖形學(xué),11,1）梯形的兩底邊分別在y=yik和y=yik+1兩條掃描線上，腰在多邊形P的邊上或在顯示屏幕的邊界上。 2）這些梯形可分為兩類：一類位于多邊形P的內(nèi)部；另一類在多邊形P的外部。 3）兩類梯形在長方形區(qū)域yik , yik+1內(nèi)相間的排列，即相鄰的兩梯形必有一個(gè)在多邊形P內(nèi)，另一個(gè)在P外。,4.2 掃描線算法,2021/3/29,西安工程大學(xué)計(jì)算機(jī)圖形學(xué),12,設(shè)e為一整數(shù)，yi0eyin。若掃描線y=e與多邊形P的Pi-1Pi相交，則記其交點(diǎn)的橫坐標(biāo)為xei。 現(xiàn)設(shè)xei1,xei2,xei3,xeil 是該掃描線與P的邊界各交點(diǎn)橫坐標(biāo)的遞增序列，稱此序列

8、為交點(diǎn)序列。由區(qū)域的連貫性可知，此交點(diǎn)序列具有以下性質(zhì)：,2、掃描線的連貫性,4.2 掃描線算法,2021/3/29,西安工程大學(xué)計(jì)算機(jī)圖形學(xué),13,1）L是偶數(shù)。 2）在該掃描線上，只有(xeik,xeik+1）,k=1,3,5,L-1 位于多邊形P內(nèi)，其余區(qū)段都在P外。 以上性質(zhì)稱為掃描線的連貫性，它是多邊形區(qū)域連 貫性在一條掃描線上的反映。,4.2 掃描線算法,2021/3/29,西安工程大學(xué)計(jì)算機(jī)圖形學(xué),14,設(shè)d為一整數(shù)，d=e-1,并且 yi0dyin。設(shè)位于掃描線y=d上的交點(diǎn)序列為xdj1,xdj2,xdjk （遞增） 現(xiàn)在來討論掃描線d，e交點(diǎn)序列之間的關(guān)系。若多邊形P的邊P

9、r-1Pr與掃描線y=e,y=d都相交，則交點(diǎn)序列中對應(yīng)元素xer,xdr滿足下列關(guān)系： xer= xdr + 1/mr (1) 其中mr為邊Pr-1Pr的斜率。,4.2 掃描線算法,2021/3/29,西安工程大學(xué)計(jì)算機(jī)圖形學(xué),15,可利用d的交點(diǎn)序列計(jì)算e的交點(diǎn)序列：先運(yùn)用遞推關(guān)系式xer= xdr + 1/mr求得與掃描線y=e和y=d都相交的所有多邊形上的交點(diǎn)xer；再求得與掃描線y=d不相交但與掃描線y=e相交的所有邊PqPq+1上的交點(diǎn)xeq。然后把這兩部分按遞增的順序排列，即可得e的交點(diǎn)序列。,4.2 掃描線算法,2021/3/29,西安工程大學(xué)計(jì)算機(jī)圖形學(xué),16,特別是當(dāng)存在某

10、一個(gè)整數(shù)k,0kn-1,使得 yike, dyik+1 成立時(shí)，則由區(qū)域的連貫性可知d的交點(diǎn)序列和e的交點(diǎn)序列之間有以下關(guān)系： 1）兩序列元素的個(gè)數(shù)相等，如上圖所示。 2）點(diǎn)(xeir,e)與(xdjr,d)位于多邊形P的同一邊上 于是 xeir= xdjr + 1/kjr (2) 這樣，運(yùn)用遞推關(guān)系式(2)可直接由d的交點(diǎn)序列獲得e的交點(diǎn)序列。以上性質(zhì)稱為邊的連貫性，它是區(qū)域的連貫性在相鄰兩掃描線上的反映。,4.2 掃描線算法,2021/3/29,西安工程大學(xué)計(jì)算機(jī)圖形學(xué),17,當(dāng)掃描線與多邊形P的交點(diǎn)是P的頂點(diǎn)時(shí)，則稱該交點(diǎn)為奇點(diǎn)。 以上所述多邊形的三種形式的連貫性都基于這樣的幾何事實(shí)：

11、每一條掃描線與多邊形P的邊界的交點(diǎn)個(gè)數(shù)都是偶數(shù)。但是如果把每一奇點(diǎn)簡單地計(jì)為一個(gè)交點(diǎn)或者簡單地計(jì)為兩個(gè)交點(diǎn)，都可能出現(xiàn)奇數(shù)個(gè)交點(diǎn)。那么如果保證交點(diǎn)數(shù)為偶數(shù)呢？,奇點(diǎn)的處理,4.2 掃描線算法,2021/3/29,西安工程大學(xué)計(jì)算機(jī)圖形學(xué),18,若奇點(diǎn)做一個(gè)交點(diǎn)處理，則情況A，交點(diǎn)個(gè)數(shù)不是偶數(shù)。 若奇點(diǎn)做兩個(gè)交點(diǎn)處理，則情況B，交點(diǎn)個(gè)數(shù)不是偶數(shù)。,A,B,奇點(diǎn)的處理,4.2 掃描線算法,2021/3/29,西安工程大學(xué)計(jì)算機(jī)圖形學(xué),19,奇點(diǎn)的處理,多邊形P的頂點(diǎn)可分為兩類：極值奇點(diǎn)和非極值奇點(diǎn)。如果(yi-1 - yi)(yi+1 - yi)0，則稱頂點(diǎn)Pi為極值點(diǎn)；否則稱Pi為非極值點(diǎn)。 規(guī)

12、定：奇點(diǎn)是極值點(diǎn)時(shí)，該點(diǎn)按兩個(gè)交點(diǎn)計(jì)算，否則按一個(gè)交點(diǎn)計(jì)算。 奇點(diǎn)的預(yù)處理：,2021/3/29,西安工程大學(xué)計(jì)算機(jī)圖形學(xué),20,數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟,算法基本思想： 首先取d=yin。容易求得掃描線y=d上的交點(diǎn)序列為xdj1,xdj2,xdjn ，這一序列由位于掃描線y=d上的多邊形P的頂點(diǎn)組成。 由yin的交點(diǎn)序列開始，根據(jù)多邊形的邊的連貫性，按從上到下的順序求得各條掃描線的交點(diǎn)序列；根據(jù)掃描線的連貫性，可確定各條掃描線上位于多邊形P內(nèi)的區(qū)段，并表示成點(diǎn)陣形式。,2021/3/29,西安工程大學(xué)計(jì)算機(jī)圖形學(xué),21,即算法中采用較靈活的數(shù)據(jù)結(jié)構(gòu)。它由邊的分類表ET（Edge Table）和邊

13、的活化鏈表AEL（Active Edge List）兩部分組成。 表結(jié)構(gòu)ET和AEL中的基本元素為多邊形的邊。邊的結(jié)構(gòu)由以下四個(gè)域組成： ymax 邊的上端點(diǎn)的y坐標(biāo)； x 在ET中表示邊的下端點(diǎn)的x坐標(biāo)，在AEL中 則表示邊與掃描線的交點(diǎn)的坐標(biāo)； x 邊的斜率的倒數(shù)； next 指向下一條邊的指針。,數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟,2021/3/29,西安工程大學(xué)計(jì)算機(jī)圖形學(xué),22,邊的分類表ET是按邊的下端點(diǎn)的y坐標(biāo)對非水平邊進(jìn)行分類的指針數(shù)組。下端點(diǎn)的y坐標(biāo)的值等于i的邊歸入第i類。有多少條掃描線，就設(shè)多少類。同一類中，各邊按x值（x值相等時(shí)，按x的值）遞增的順序排列成行。,數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟,與當(dāng)

14、前掃描線相交的邊稱為活性邊（active edge)，把它們按與掃描線交點(diǎn)x坐標(biāo)遞增的順序存入一個(gè)鏈表中，邊的活化鏈表 （ AEL, Active edge table)。它記錄了多邊形邊沿掃描線的交點(diǎn)序列。,2021/3/29,西安工程大學(xué)計(jì)算機(jī)圖形學(xué),23,數(shù)據(jù)結(jié)構(gòu) 例子,已知多邊形P=( P0P1P2P3P4P5P6P0 )； 其各邊坐標(biāo)分別為 （2，5）（2，10）（9，6）（16，11）（16，4）（12，2）（7，2） 建立其邊表和邊的活化鏈表,P0,P1,P2,P3,P4,P5,P6,2021/3/29,西安工程大學(xué)計(jì)算機(jī)圖形學(xué),24,例子_創(chuàng)建邊表,2021/3/29,西安工程

15、大學(xué)計(jì)算機(jī)圖形學(xué),25,例子_創(chuàng)建活動(dòng)邊表,y=3,AEL,y=8,AEL,e7,e5,e1,e2,e3,e4,2021/3/29,西安工程大學(xué)計(jì)算機(jī)圖形學(xué),26,算法實(shí)現(xiàn)步驟,當(dāng)建立了邊的分類表ET后，掃描線算法可按下列步驟進(jìn)行： （1）取掃描線縱坐標(biāo)y的初始值為ET中非空元素的最小序號(hào)。 （2）將邊的活化鏈表AEL設(shè)置為空。 （3）按從下到上的順序?qū)v坐標(biāo)值為y的掃描線（當(dāng)前掃描線）執(zhí)行下列步驟，直到邊的分類表ET和邊的活化鏈表都變成空為止。,2021/3/29,西安工程大學(xué)計(jì)算機(jī)圖形學(xué),27,算法實(shí)現(xiàn)步驟,1）如邊分類表ET中的第y類元素非空，則將屬于該類的所有邊從ET中取出并插入邊的活

16、化鏈表中。遞增方向排序。 2）若相對于當(dāng)前掃描線，邊的活化鏈表AEL非空，則將AEL中的邊兩兩依次配對，依此類推。并填色。 3）將邊的活化鏈表AEL中滿足y=ymax的邊刪去。 4）x:=x+x。 5）y:=y+1。,2021/3/29,西安工程大學(xué)計(jì)算機(jī)圖形學(xué),28,4.2、掃描線算法,特點(diǎn)：算法效率比逐點(diǎn)填充法高很多。 缺點(diǎn)：對各種表的維持和排序開銷太大，適合軟件實(shí)現(xiàn)而不適合硬件實(shí)現(xiàn)。,2021/3/29,西安工程大學(xué)計(jì)算機(jī)圖形學(xué),29,1. 對多邊形的每一條邊進(jìn)行掃描轉(zhuǎn)換，即對多邊形邊界所經(jīng)過的象素作一個(gè)邊界標(biāo)志。 2.填充。對每條與多邊形相交的掃描線，按從左到右的順序，逐個(gè)訪問該掃描線

17、上的象素。 3.取一個(gè)布爾變量inside來指示當(dāng)前點(diǎn)的狀態(tài)，若點(diǎn)在 多邊形內(nèi)，則inside為真。若點(diǎn)在多邊形外，則inside 為假。Inside 的初始值為假，每當(dāng)當(dāng)前訪問象素為被打 上標(biāo)志的點(diǎn)，就把inside取反。對未打標(biāo)志的點(diǎn)， inside 不變。,邊界標(biāo)志算法,2021/3/29,西安工程大學(xué)計(jì)算機(jī)圖形學(xué),30,邊界標(biāo)志算法:算法過程,void edgemark_fill(polydef, color) 多邊形定義 polydef； int color; 對多邊形polydef 每條邊進(jìn)行直線掃描轉(zhuǎn)換； inside = FALSE; for (每條與多邊形polydef相交的

18、掃描線y ) for (掃描線上每個(gè)象素x ) if(象素 x 被打上邊標(biāo)志) inside = ! (inside); if(inside！= FALSE) drawpixel (x, y, color); else drawpixel (x, y, background); ,邊界標(biāo)志算法:算法過程,2021/3/29,西安工程大學(xué)計(jì)算機(jī)圖形學(xué),31,2021/3/29,西安工程大學(xué)計(jì)算機(jī)圖形學(xué),32,邊界標(biāo)志算法:算法過程,2021/3/29,西安工程大學(xué)計(jì)算機(jī)圖形學(xué),33,用軟件實(shí)現(xiàn)時(shí)，掃描線算法與邊界標(biāo)志算法的執(zhí)行速度幾乎相同， 但由于邊界標(biāo)志算法不必建立維護(hù)邊表以及對它進(jìn)行排序，所

19、以邊界標(biāo)志算法更適合硬件實(shí)現(xiàn)，這時(shí)它的執(zhí)行速度比有序邊表算法快一至兩個(gè)數(shù)量級(jí)。,邊界標(biāo)志算法,思考：如何處理邊界的交點(diǎn)個(gè)數(shù)使其成為偶數(shù)？,2021/3/29,西安工程大學(xué)計(jì)算機(jī)圖形學(xué),34,4.3 區(qū)域填充原理,用點(diǎn)陣方法表示的多邊形區(qū)域，如果其內(nèi)部像素具有同一種顏色，而邊界像素具有另一種顏色，可以使用種子算法進(jìn)行填充。種子填充算法是從區(qū)域內(nèi)任一個(gè)種子像素位置開始，由內(nèi)向外將填充色擴(kuò)散到整個(gè)多邊形區(qū)域的填充過程。,表示方法：內(nèi)點(diǎn)表示、邊界表示,2021/3/29,西安工程大學(xué)計(jì)算機(jī)圖形學(xué),35,區(qū)域填充要求區(qū)域是連通的 連通性 4連通、8連通 4連通 8連通,4.3 區(qū)域填充原理,2021/3

20、/29,西安工程大學(xué)計(jì)算機(jī)圖形學(xué),36,四連通域及其四連通邊界,四連通域及其八連通邊界,2021/3/29,西安工程大學(xué)計(jì)算機(jī)圖形學(xué),37,八連通域及其四連通邊界,八連通域及其八連通邊界,2021/3/29,西安工程大學(xué)計(jì)算機(jī)圖形學(xué),38,四鄰接點(diǎn)算法填充八連通域,八鄰接點(diǎn)算法填充八連通域,2021/3/29,西安工程大學(xué)計(jì)算機(jī)圖形學(xué),39,適合于內(nèi)點(diǎn)表示區(qū)域的填充算法 設(shè)G為一內(nèi)點(diǎn)表示的區(qū)域，(x,y)為區(qū)域內(nèi)一點(diǎn)，old_color為G的原色?，F(xiàn)取(x,y)為種子點(diǎn)對區(qū)域G進(jìn)行填充：即先置像素(x,y)的顏色為new_color，然后逐步將整個(gè)區(qū)域G都置為同樣的顏色。 步驟如下： 種子象素

21、入棧，當(dāng)棧非空時(shí)，執(zhí)行如下三步操作： （1）棧頂象素出棧； （2）將出棧象素置成new_color ； （3）按上、下、左、右的順序檢查與出棧象素相鄰的四個(gè)象素，若其中某個(gè)象素在邊界內(nèi)且未置成new_color ，則把該象素入棧。,4.3、種子填充算法,2021/3/29,西安工程大學(xué)計(jì)算機(jī)圖形學(xué),40,例：多邊形由P0P1P2P3P4構(gòu)成，P0(1,5) P1(5,5) P2(7,3) P3(7,1) P4(1,1) 設(shè)種子點(diǎn)為（3，3），搜索的方向是上、下、左、右。依此類推，最后像素被選中并填充的次序如圖中箭頭所示,4.3、種子填充算法,2021/3/29,西安工程大學(xué)計(jì)算機(jī)圖形學(xué),41,

22、遞歸算法可實(shí)現(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); FloodFill4(x-1,y,oldColor,newColor); FloodFill4(x+1,y,oldColor,newColor); /*end of FloodFill4()*/,4.3、種子填充算法

23、,2021/3/29,西安工程大學(xué)計(jì)算機(jī)圖形學(xué),42,邊界表示的4連通區(qū)域,void BoundaryFill4(int x,int y,int boundaryColor,int newColor) int color; color = GetPixel(x,y); if(color != boundaryColor) /*end of BoundaryFill4()*/,4.3、種子填充算法,2021/3/29,西安工程大學(xué)計(jì)算機(jī)圖形學(xué),43,該算法也可以填充有孔區(qū)域。 缺點(diǎn)： (1) 有些象素會(huì)入棧多次，降低算法效率； (2) 遞歸執(zhí)行，算法簡單，但效率不高，區(qū)域內(nèi)每一象素都引起一次遞歸

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