圖形學(xué)課件第四講多變形填充

1、 滁州學(xué)院滁州學(xué)院 國土信息工程系國土信息工程系主講主講 孫勇孫勇Email：sunyong_計算機(jī)圖形學(xué)計算機(jī)圖形學(xué)第四章第四章 多邊形的掃描轉(zhuǎn)換與區(qū)域填充多邊形的掃描轉(zhuǎn)換與區(qū)域填充4.14.1多邊形掃描轉(zhuǎn)換多邊形掃描轉(zhuǎn)換4.24.2區(qū)域填充區(qū)域填充4.14.1多邊形的掃描轉(zhuǎn)換與區(qū)域填充多邊形的掃描轉(zhuǎn)換與區(qū)域填充多邊形有兩種重要的表示方法：頂點(diǎn)表示和點(diǎn)陣表示。多邊形有兩種重要的表示方法：頂點(diǎn)表示和點(diǎn)陣表示。多邊形的掃描轉(zhuǎn)換多邊形的掃描轉(zhuǎn)換: :把多邊形的頂點(diǎn)表示轉(zhuǎn)換為點(diǎn)陣表示。把多邊形的頂點(diǎn)表示轉(zhuǎn)換為點(diǎn)陣表示。區(qū)域可采用內(nèi)點(diǎn)表示和邊界表示兩種表示形式。區(qū)域可采用內(nèi)點(diǎn)表示和邊界表示兩種表示形式

2、。區(qū)域填充區(qū)域填充: :指先將區(qū)域的一點(diǎn)賦予指定的顏色，然后將該顏色指先將區(qū)域的一點(diǎn)賦予指定的顏色，然后將該顏色擴(kuò)展到整個區(qū)域的過程擴(kuò)展到整個區(qū)域的過程。多邊形分為凸多邊形、凹多邊形、含內(nèi)環(huán)的多邊形多邊形分為凸多邊形、凹多邊形、含內(nèi)環(huán)的多邊形。4.1.1多邊形的掃描轉(zhuǎn)換多邊形的掃描轉(zhuǎn)換掃描線算法掃描線算法基本思想：基本思想：按掃描線順序，計算掃描線與多邊形的相交區(qū)間，按掃描線順序，計算掃描線與多邊形的相交區(qū)間，再用要求的顏色顯示這些區(qū)間的象素，即完成再用要求的顏色顯示這些區(qū)間的象素，即完成填充工作。填充工作。對于一條掃描線填充過程可以分為四個步驟：對于一條掃描線填充過程可以分為四個步驟：（1

3、1）求交（）求交（2 2）排序）排序（3 3）配對（）配對（4 4）填色）填色判斷任意點(diǎn)是否在多邊形內(nèi)判斷任意點(diǎn)是否在多邊形內(nèi)l算法思想算法思想 從該點(diǎn)（從該點(diǎn)（x, yx, y）向（）向（ , y, y）引直線，并計算該線與多邊形的）引直線，并計算該線與多邊形的交點(diǎn)數(shù)交點(diǎn)數(shù)n(n(自左向右算起自左向右算起) ) if(n%2 = 0) if(n%2 = 0) 則（則（x, yx, y）在多邊形外）在多邊形外 else else 則（則（x, yx, y）在多邊形內(nèi)）在多邊形內(nèi) 掃描線與多邊形的頂點(diǎn)或邊界相交時，必須正確的交點(diǎn)的取掃描線與多邊形的頂點(diǎn)或邊界相交時，必須正確的交點(diǎn)的取舍。只需檢查

4、頂點(diǎn)的兩條邊的另外兩個端點(diǎn)的舍。只需檢查頂點(diǎn)的兩條邊的另外兩個端點(diǎn)的y y值。按這兩個值。按這兩個y y值中大于交點(diǎn)值中大于交點(diǎn)y y值的個數(shù)是值的個數(shù)是0,1,20,1,2來決定。來決定。123P1P2P3P4l實際上將多邊形的每條邊與所有掃描線都求交點(diǎn)沒有實際上將多邊形的每條邊與所有掃描線都求交點(diǎn)沒有必要的。因為可能大多數(shù)掃描線與多邊形根本不相交。必要的。因為可能大多數(shù)掃描線與多邊形根本不相交。為了提高算法效率，應(yīng)只處理與多邊形相交的那些掃為了提高算法效率，應(yīng)只處理與多邊形相交的那些掃描線，同時，交點(diǎn)的計算可以通過增量法來實現(xiàn)描線，同時，交點(diǎn)的計算可以通過增量法來實現(xiàn)掃描線填色法掃描線填色

5、法 一個多邊形與若干掃描線 0112233445566778891011P2(5,1)EP3(11,3)DP4(11,8)GFCBP5(5,5)P6(2,7)AP1(2,2)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)活性邊表活性邊表(AET)(AET)：把與當(dāng)前掃描線相交的邊稱為活性邊，：把與當(dāng)前掃描線相交的邊稱為活性邊，并把它們按與掃描線交點(diǎn)并把它們按與掃描線交點(diǎn)x x坐標(biāo)遞增的順序存放在一個坐標(biāo)遞增的順序存放在一個鏈表中鏈表中結(jié)點(diǎn)內(nèi)容結(jié)點(diǎn)內(nèi)容 x x：當(dāng)前掃描線與邊的交點(diǎn)坐標(biāo)：當(dāng)前掃描線與邊的交點(diǎn)坐標(biāo)x x：從當(dāng)前掃描線到下一條掃描線間：從當(dāng)前掃描線到下一條掃描線間x x的增量的增量ymaxymax：該邊所交的最高

6、掃描線號：該邊所交的最高掃描線號y ymaxmax 2 0 7 3.5 -1.5 7P6P1P5P6AB 7 2 8 11 0 8P4P5P3P4CDx ymaxx ymaxx ymaxx ymax新邊表（新邊表（NETNET）：）：存放在該掃描線第一次出現(xiàn)的邊。若某邊的較低端點(diǎn)為存放在該掃描線第一次出現(xiàn)的邊。若某邊的較低端點(diǎn)為y yminmin，則該邊就放在掃描線則該邊就放在掃描線y yminmin的新邊表中的新邊表中上圖所示各條掃描線的新邊表上圖所示各條掃描線的新邊表NETNET 7 6P4P5 P5P6 5 4 3 2 1 0P1P2 P2P3 8 5 -3 2 5 3 3 2 0 7

7、11 0 8 5 2 8 5 -1.5 7P6P1P3P4假定當(dāng)前掃描線與多邊形某一條邊的交點(diǎn)的假定當(dāng)前掃描線與多邊形某一條邊的交點(diǎn)的x x坐標(biāo)為坐標(biāo)為x x，則下一條，則下一條掃描線與該邊的交點(diǎn)不要重計算，只要加一個增量掃描線與該邊的交點(diǎn)不要重計算，只要加一個增量x x。設(shè)該邊的直線方程為：設(shè)該邊的直線方程為：ax+by+c=0ax+by+c=0；若若y yy yi i，x=xx=x i i；則當(dāng)；則當(dāng)y = yy = y i+1 i+1時，時，其中其中 為常數(shù)為常數(shù);)(111abxcybaxiiiiabx FDC E AB975312468多邊形掃描轉(zhuǎn)換多邊形掃描轉(zhuǎn)換算法過程(偽代碼)v

8、oid polyfillvoid polyfill (polygon, color) (polygon, color) int int color; color; 多邊形多邊形 polygon;polygon; for ( for (各條掃描線各條掃描線i )i ) 初始化新邊表頭指針初始化新邊表頭指針NET iNET i； 把把y y min min = i = i 的邊放進(jìn)邊表的邊放進(jìn)邊表NET i; NET i; y = y = 最低掃描線號；最低掃描線號； 初始化活性邊表初始化活性邊表AETAET為空；為空； for (for (各條掃描線各條掃描線i )i ) 把新邊表把新邊表NET

9、 i NET i 中的邊結(jié)點(diǎn)用插入排序法插入中的邊結(jié)點(diǎn)用插入排序法插入AETAET表，使之按表，使之按x x坐標(biāo)遞增順序排列；坐標(biāo)遞增順序排列；遍歷遍歷AETAET表，把配對交點(diǎn)區(qū)間表，把配對交點(diǎn)區(qū)間( (左閉右開左閉右開) )上的象素上的象素(x, (x, y)y)，用，用drawpixeldrawpixel (x, y, color) (x, y, color) 改寫象素顏色值；改寫象素顏色值；遍歷遍歷AETAET表，把表，把y y max max= i = i 的結(jié)點(diǎn)從的結(jié)點(diǎn)從AETAET表中刪除，并把表中刪除，并把y y max max i i 結(jié)點(diǎn)的結(jié)點(diǎn)的x x值遞增值遞增 x x；

10、若允許多邊形的邊自相交，則用冒泡排序法對若允許多邊形的邊自相交，則用冒泡排序法對AETAET表表重新排序；重新排序； / /* * polyfill polyfill * */ /邊界標(biāo)志算法邊界標(biāo)志算法基本思想：基本思想：幀緩沖器中對多邊形的每條邊進(jìn)行直線掃描轉(zhuǎn)換，亦即對幀緩沖器中對多邊形的每條邊進(jìn)行直線掃描轉(zhuǎn)換，亦即對多邊形邊界所經(jīng)過的象素打上標(biāo)志。多邊形邊界所經(jīng)過的象素打上標(biāo)志。然后再采用和掃描線算法類似的方法將位于多邊形內(nèi)的各然后再采用和掃描線算法類似的方法將位于多邊形內(nèi)的各個區(qū)段著上所需顏色。個區(qū)段著上所需顏色。使用一個布爾量使用一個布爾量insideinside來指示當(dāng)前點(diǎn)是否在多

11、邊形內(nèi)的狀來指示當(dāng)前點(diǎn)是否在多邊形內(nèi)的狀態(tài)。態(tài)。算法過程算法過程void edgemark_fill(polydefvoid edgemark_fill(polydef, color), color)多邊形定義多邊形定義 polydefpolydef； intint color; color; 對多邊形對多邊形polydefpolydef 每條邊進(jìn)行直線掃描轉(zhuǎn)換；每條邊進(jìn)行直線掃描轉(zhuǎn)換； inside = FALSE;inside = FALSE; for ( for (每條與多邊形每條與多邊形polydefpolydef相交的掃描線相交的掃描線y )y ) for ( for (掃描線上每個

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

13、，幾乎相同，但由于邊界標(biāo)志算法不必建立維護(hù)邊表以及對它進(jìn)行排但由于邊界標(biāo)志算法不必建立維護(hù)邊表以及對它進(jìn)行排序，所以邊界標(biāo)志算法更適合硬件實現(xiàn)，這時它的執(zhí)序，所以邊界標(biāo)志算法更適合硬件實現(xiàn)，這時它的執(zhí)行速度比有序邊表算法快一至兩個數(shù)量級。行速度比有序邊表算法快一至兩個數(shù)量級。2.3.2區(qū)域填充算法區(qū)域填充算法區(qū)域指已經(jīng)表示成點(diǎn)陣形式的填充圖形，它是象素的集合。區(qū)域指已經(jīng)表示成點(diǎn)陣形式的填充圖形，它是象素的集合。區(qū)域可采用內(nèi)點(diǎn)表示和邊界表示兩種表示形式。區(qū)域可采用內(nèi)點(diǎn)表示和邊界表示兩種表示形式。區(qū)域可分為區(qū)域可分為4 4向連通區(qū)域和向連通區(qū)域和8 8向連通區(qū)域。向連通區(qū)域。區(qū)域填充指先將區(qū)域的一

14、點(diǎn)賦予指定的顏色，然后將該顏色區(qū)域填充指先將區(qū)域的一點(diǎn)賦予指定的顏色，然后將該顏色擴(kuò)展到整個區(qū)域的過程。區(qū)域填充算法要求區(qū)域是連通的擴(kuò)展到整個區(qū)域的過程。區(qū)域填充算法要求區(qū)域是連通的4 4向連通區(qū)域和向連通區(qū)域和8 8向連通區(qū)域向連通區(qū)域 四個方向運(yùn)動四個方向運(yùn)動 八個方向運(yùn)動八個方向運(yùn)動 四連通區(qū)域四連通區(qū)域 八連通區(qū)域八連通區(qū)域表示內(nèi)點(diǎn)表示邊界點(diǎn)區(qū)域填充的遞歸算法區(qū)域填充的遞歸算法內(nèi)點(diǎn)表示的內(nèi)點(diǎn)表示的4 4連通區(qū)域的遞歸填充算法連通區(qū)域的遞歸填充算法: :void FloodFill4(int x,int y,int oldcolor,int newcolorvoid FloodFill4

15、(int x,int y,int oldcolor,int newcolor) ) if(getpixel(x,y)=oldcolor if(getpixel(x,y)=oldcolor) /) /屬于區(qū)域內(nèi)點(diǎn)屬于區(qū)域內(nèi)點(diǎn)oldcoloroldcolor drawpixel(x,y,newcolordrawpixel(x,y,newcolor););FloodFill4(x,y+1,oldcolor,newcolor);FloodFill4(x,y+1,oldcolor,newcolor);FloodFill4(x,y-1,oldcolor,newcolor);FloodFill4(x,y-1

16、,oldcolor,newcolor);FloodFill4(x-1,y,oldcolor,newcolor);FloodFill4(x-1,y,oldcolor,newcolor);FloodFill4(x+1,y,oldcolor,newcolor);FloodFill4(x+1,y,oldcolor,newcolor); 邊界表示的邊界表示的4 4連通區(qū)域的遞歸填充算法連通區(qū)域的遞歸填充算法: :void BoundaryFill4(int x,int y,int boundarycolor,int void BoundaryFill4(int x,int y,int boundaryc

17、olor,int newcolornewcolor) ) int int color; color;if(color!=newcolor & color!=boundarycolorif(color!=newcolor & color!=boundarycolor) ) drawpixel(x,y,newcolordrawpixel(x,y,newcolor););BoundaryFill4 (x,y+1, boundarycolor,newcolorBoundaryFill4 (x,y+1, boundarycolor,newcolor););BoundaryFill4 (x,y-1, bo

18、undarycolor,newcolorBoundaryFill4 (x,y-1, boundarycolor,newcolor););BoundaryFill4 (x-1,y, boundarycolor,newcolorBoundaryFill4 (x-1,y, boundarycolor,newcolor););BoundaryFill4 (x+1,y, boundarycolor,newcolorBoundaryFill4 (x+1,y, boundarycolor,newcolor);); 區(qū)域填充的掃描線算法區(qū)域填充的掃描線算法算法步驟：算法步驟：首先填充種子點(diǎn)所在掃描線上的位于給

19、定區(qū)域的首先填充種子點(diǎn)所在掃描線上的位于給定區(qū)域的一個區(qū)段一個區(qū)段然后確定與這一區(qū)段相連通的上、下兩條掃描線然后確定與這一區(qū)段相連通的上、下兩條掃描線上位于給定區(qū)域內(nèi)的區(qū)段，并依次保存下來。上位于給定區(qū)域內(nèi)的區(qū)段，并依次保存下來。反復(fù)這個過程，直到填充結(jié)束。反復(fù)這個過程，直到填充結(jié)束。(1)(1)初始化：堆棧置空。將種子點(diǎn)（初始化：堆棧置空。將種子點(diǎn)（x x，y y）入棧。）入棧。(2)(2)出棧：若?？談t結(jié)束。否則取棧頂元素（出棧：若棧空則結(jié)束。否則取棧頂元素（x x，y y），以），以y y作為當(dāng)作為當(dāng)前掃描線。前掃描線。(3)(3)填充并確定種子點(diǎn)所在區(qū)段：從種子點(diǎn)（填充并確定種子點(diǎn)所在

20、區(qū)段：從種子點(diǎn)（x x，y y）出發(fā)，沿當(dāng)前）出發(fā)，沿當(dāng)前掃描線向左、右兩個方向填充，直到邊界。分別標(biāo)記區(qū)段的左、掃描線向左、右兩個方向填充，直到邊界。分別標(biāo)記區(qū)段的左、右端點(diǎn)坐標(biāo)為右端點(diǎn)坐標(biāo)為xlxl和和xrxr。(4)(4)并確定新的種子點(diǎn)：在區(qū)間并確定新的種子點(diǎn)：在區(qū)間xlxl，xrxr 中檢查與當(dāng)前掃描線中檢查與當(dāng)前掃描線y y上、上、下相鄰的兩條掃描線上的象素。若存在非邊界、未填充的象素，下相鄰的兩條掃描線上的象素。若存在非邊界、未填充的象素，則把每一區(qū)間的最右象素作為種子點(diǎn)壓入堆棧，返回第（則把每一區(qū)間的最右象素作為種子點(diǎn)壓入堆棧，返回第（2 2）步。）步。上述算法對于每一個待填充

21、區(qū)段，只需壓棧一次；因此，掃描線上述算法對于每一個待填充區(qū)段，只需壓棧一次；因此，掃描線填充算法提高了區(qū)域填充的效率。填充算法提高了區(qū)域填充的效率。2.4 字字 符符字符指數(shù)字、字母、漢字等符號。計算機(jī)中字符由一個數(shù)字編碼唯一標(biāo)識?！懊绹畔⒔粨Q用標(biāo)準(zhǔn)代碼集”簡稱ASCII碼。它是用7位二進(jìn)制數(shù)進(jìn)行編碼表示128個字符漢字編碼的國家標(biāo)準(zhǔn)字符集。每個符號由一個區(qū)碼和一個位碼（2字節(jié)）共同標(biāo)識。區(qū)分ASCII碼與漢字編碼，采用字節(jié)的最高位來標(biāo)識 點(diǎn)陣字符點(diǎn)陣字符:每個字符由一個位圖表示矢量字符矢量字符:記錄字符的筆畫信息點(diǎn)陣字符 點(diǎn)陣字庫中的位圖表示 矢量輪廓字符11111100010101010

22、10101010111110001010101010101011111110000000000特點(diǎn)：點(diǎn)陣字符：存儲量大，易于顯示矢量字符：存儲量小，美觀，變換方便需要光柵化后才能顯示。字符屬性字符屬性字體 宋體 仿宋體 楷體 黑體 隸書字高 宋體 宋體 宋體 宋體字寬字傾斜角傾斜 傾斜對齊 (左對齊、中心對齊、右對齊)字色 紅色、綠色、藍(lán)色紅色、綠色、藍(lán)色寫方式：替換方式。與方式大 海 大 海 大 海 大 海2.5 裁剪裁剪裁剪：確定圖形中哪些部分落在顯示區(qū)之內(nèi)，哪些落在顯示區(qū)之外,以便只顯示落在顯示區(qū)內(nèi)的那部分圖形。這個選擇過程稱為裁剪裁剪。2.5.1直線段裁剪2.5.2 多邊形裁剪2.5.1直線段裁剪直線段裁剪直線段裁剪算法是復(fù)雜圖元裁剪的基礎(chǔ)。直線段裁剪算法是復(fù)雜圖元裁剪的基礎(chǔ)。復(fù)雜的曲線可以