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

1、 滁州學(xué)院滁州學(xué)院 國(guó)土信息工程系國(guó)土信息工程系主講主講 孫勇孫勇Email：sunyong_計(jì)算機(jī)圖形學(xué)計(jì)算機(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ò)展到整個(gè)區(qū)域的過(guò)程擴(kuò)展到整個(gè)區(qū)域的過(guò)程。多邊形分為凸多邊形、凹多邊形、含內(nèi)環(huán)的多邊形多邊形分為凸多邊形、凹多邊形、含內(nèi)環(huán)的多邊形。4.1.1多邊形的掃描轉(zhuǎn)換多邊形的掃描轉(zhuǎn)換掃描線算法掃描線算法基本思想：基本思想：按掃描線順序，計(jì)算掃描線與多邊形的相交區(qū)間，按掃描線順序，計(jì)算掃描線與多邊形的相交區(qū)間，再用要求的顏色顯示這些區(qū)間的象素，即完成再用要求的顏色顯示這些區(qū)間的象素，即完成填充工作。填充工作。對(duì)于一條掃描線填充過(guò)程可以分為四個(gè)步驟：對(duì)于一條掃描線填充過(guò)程可以分為四個(gè)步驟：（1

3、1）求交（）求交（2 2）排序）排序（3 3）配對(duì)（）配對(duì)（4 4）填色）填色判斷任意點(diǎn)是否在多邊形內(nèi)判斷任意點(diǎn)是否在多邊形內(nèi)l算法思想算法思想 從該點(diǎn)（從該點(diǎn)（x, yx, y）向（）向（ , y, y）引直線，并計(jì)算該線與多邊形的）引直線，并計(jì)算該線與多邊形的交點(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)或邊界相交時(shí)，必須正確的交點(diǎn)的取掃描線與多邊形的頂點(diǎn)或邊界相交時(shí)，必須正確的交點(diǎn)的取舍。只需檢查

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

5、法 一個(gè)多邊形與若干掃描線 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)遞增的順序存放在一個(gè)坐標(biāo)遞增的順序存放在一個(gè)鏈表中鏈表中結(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、掃描線號(hào)：該邊所交的最高掃描線號(hào)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)不要重計(jì)算，只要加一個(gè)增量掃描線與該邊的交點(diǎn)不要重計(jì)算，只要加一個(gè)增量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í)，其中其中 為常數(shù)為常數(shù);)(111abxcybaxiiiiabx FDC E AB975312468多邊形掃描轉(zhuǎn)換多邊形掃描轉(zhuǎn)換算法過(guò)程(偽代碼)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 = 最低掃描線號(hào)；最低掃描線號(hào)； 初始化活性邊表初始化活性邊表AETAET為空；為空； for (for (各條掃描線各條掃描線i )i ) 把新邊表把新邊表NET

9、 i NET i 中的邊結(jié)點(diǎn)用插入排序法插入中的邊結(jié)點(diǎn)用插入排序法插入AETAET表，使之按表，使之按x x坐標(biāo)遞增順序排列；坐標(biāo)遞增順序排列；遍歷遍歷AETAET表，把配對(duì)交點(diǎn)區(qū)間表，把配對(duì)交點(diǎn)區(qū)間( (左閉右開(kāi)左閉右開(kāi)) )上的象素上的象素(x, (x, y)y)，用，用drawpixeldrawpixel (x, y, color) (x, y, color) 改寫(xiě)象素顏色值；改寫(xiě)象素顏色值；遍歷遍歷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、若允許多邊形的邊自相交，則用冒泡排序法對(duì)若允許多邊形的邊自相交，則用冒泡排序法對(duì)AETAET表表重新排序；重新排序； / /* * polyfill polyfill * */ /邊界標(biāo)志算法邊界標(biāo)志算法基本思想：基本思想：幀緩沖器中對(duì)多邊形的每條邊進(jìn)行直線掃描轉(zhuǎn)換，亦即對(duì)幀緩沖器中對(duì)多邊形的每條邊進(jìn)行直線掃描轉(zhuǎn)換，亦即對(duì)多邊形邊界所經(jīng)過(guò)的象素打上標(biāo)志。多邊形邊界所經(jīng)過(guò)的象素打上標(biāo)志。然后再采用和掃描線算法類似的方法將位于多邊形內(nèi)的各然后再采用和掃描線算法類似的方法將位于多邊形內(nèi)的各個(gè)區(qū)段著上所需顏色。個(gè)區(qū)段著上所需顏色。使用一個(gè)布爾量使用一個(gè)布爾量insideinside來(lái)指示當(dāng)前點(diǎn)是否在多

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

12、象素掃描線上每個(gè)象素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); 用軟件實(shí)現(xiàn)時(shí)，掃描線算法與邊界標(biāo)志算法的執(zhí)行速度用軟件實(shí)現(xiàn)時(shí)，掃描線算法與邊界標(biāo)志算法的執(zhí)行速度幾乎相同

13、，幾乎相同，但由于邊界標(biāo)志算法不必建立維護(hù)邊表以及對(duì)它進(jìn)行排但由于邊界標(biāo)志算法不必建立維護(hù)邊表以及對(duì)它進(jìn)行排序，所以邊界標(biāo)志算法更適合硬件實(shí)現(xiàn)，這時(shí)它的執(zhí)序，所以邊界標(biāo)志算法更適合硬件實(shí)現(xiàn)，這時(shí)它的執(zhí)行速度比有序邊表算法快一至兩個(gè)數(shù)量級(jí)。行速度比有序邊表算法快一至兩個(gè)數(shù)量級(jí)。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ò)展到整個(gè)區(qū)域的過(guò)程。區(qū)域填充算法要求區(qū)域是連通的擴(kuò)展到整個(gè)區(qū)域的過(guò)程。區(qū)域填充算法要求區(qū)域是連通的4 4向連通區(qū)域和向連通區(qū)域和8 8向連通區(qū)域向連通區(qū)域 四個(gè)方向運(yùn)動(dòng)四個(gè)方向運(yùn)動(dòng) 八個(gè)方向運(yùn)動(dòng)八個(gè)方向運(yùn)動(dòng) 四連通區(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

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

20、并確定種子點(diǎn)所在區(qū)段：從種子點(diǎn)（x x，y y）出發(fā)，沿當(dāng)前）出發(fā)，沿當(dāng)前掃描線向左、右兩個(gè)方向填充，直到邊界。分別標(biāo)記區(qū)段的左、掃描線向左、右兩個(gè)方向填充，直到邊界。分別標(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、對(duì)于每一個(gè)待填充區(qū)段，只需壓棧一次；因此，掃描線上述算法對(duì)于每一個(gè)待填充區(qū)段，只需壓棧一次；因此，掃描線填充算法提高了區(qū)域填充的效率。填充算法提高了區(qū)域填充的效率。2.4 字字 符符字符指數(shù)字、字母、漢字等符號(hào)。計(jì)算機(jī)中字符由一個(gè)數(shù)字編碼唯一標(biāo)識(shí)?！懊绹?guó)信息交換用標(biāo)準(zhǔn)代碼集”簡(jiǎn)稱ASCII碼。它是用7位二進(jìn)制數(shù)進(jìn)行編碼表示128個(gè)字符漢字編碼的國(guó)家標(biāo)準(zhǔn)字符集。每個(gè)符號(hào)由一個(gè)區(qū)碼和一個(gè)位碼（2字節(jié)）共同標(biāo)識(shí)。區(qū)分ASCII碼與漢字編碼，采用字節(jié)的最高位來(lái)標(biāo)識(shí) 點(diǎn)陣字符點(diǎn)陣字符:每個(gè)字符由一個(gè)位圖表示矢量字符矢量字符:記錄字符的筆畫(huà)信息點(diǎn)陣字符 點(diǎn)陣字庫(kù)中的位圖表示 矢量輪廓字符111111000

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