填充圖元的生成

1、第四章 填充圖元的生成掃描轉(zhuǎn)換矩形掃描轉(zhuǎn)換多邊形掃描轉(zhuǎn)換扇形區(qū)域區(qū)域填充以圖像填充區(qū)域字符的表示與輸出8/14/20221多邊形的掃描轉(zhuǎn)換與區(qū)域填充多邊形有兩種重要的表示方法：頂點(diǎn)表示和點(diǎn)陣表示。多邊形的掃描轉(zhuǎn)換:把多邊形的頂點(diǎn)表示轉(zhuǎn)換為點(diǎn)陣表示。區(qū)域可采用內(nèi)點(diǎn)表示和邊界表示兩種表示形式。區(qū)域填充:指先將區(qū)域的一點(diǎn)賦予指定的顏色，然后將該顏色擴(kuò)展到整個(gè)區(qū)域的過(guò)程。8/14/20222掃描轉(zhuǎn)換的一般步驟確定哪些像素位于填充圖元的內(nèi)部 掃描轉(zhuǎn)換：矩形、多邊形、扇形確定以什么顏色填充這些像素 均勻填色，圖像填充 8/14/20223掃描轉(zhuǎn)換矩形方法：void FillRectangle(Rectan

2、gle *rect,int color) int x,y; for(y = rect-ymin;y ymax;y+) for(x = rect-xmin;x xmax;x+) PutPixel(x,y,color);/*end of FillRectangle()*/8/14/20224掃描轉(zhuǎn)換矩形問(wèn)題：矩形是簡(jiǎn)單的多邊形，那么為什么要單獨(dú)處理矩形？(比一般多邊形可簡(jiǎn)化計(jì)算。應(yīng)用非常多，如窗口系統(tǒng)。 )光柵系統(tǒng)的特點(diǎn):邊有寬度.共享邊界如何處理？原則：左閉右開(kāi)，下閉上開(kāi)屬于誰(shuí)？8/14/20225掃描轉(zhuǎn)換多邊形多邊形的表示方法頂點(diǎn)表示點(diǎn)陣表示掃描轉(zhuǎn)換多邊形： 將頂點(diǎn)表示形式轉(zhuǎn)換成點(diǎn)陣表示形式三

3、種方法： 逐點(diǎn)判斷法； 掃描線算法； 邊緣填充法。 8/14/20226掃描轉(zhuǎn)換多邊形-逐點(diǎn)判斷法逐個(gè)判斷繪圖窗口內(nèi)的像素： 射線法： 累計(jì)角度法 編碼法； 算法優(yōu)點(diǎn)：簡(jiǎn)單算法缺點(diǎn)：計(jì)算量太大，速度慢8/14/20227掃描轉(zhuǎn)換多邊形-逐點(diǎn)判斷法逐點(diǎn)判斷算法方法void FillPolygonPbyP(Polygon *P,int polygonColor) int x,y; for(y = ymin;y = ymax;y+) for(x = xmin;x = xmax;x+)if(IsInside(P,x,y) PutPixel(x,y,polygonColor);else PutPixel

4、(x,y,backgroundColor);/*end of FillPolygonPbyP()*/8/14/20228掃描轉(zhuǎn)換多邊形-逐點(diǎn)判斷法問(wèn)題：如何判別點(diǎn)(x,y)關(guān)于多邊形區(qū)域P的內(nèi)外關(guān)系？射線法步驟：從待判別點(diǎn)v發(fā)出射線求交點(diǎn)個(gè)數(shù)kK的奇偶性決定了 點(diǎn)與多邊形的內(nèi)外關(guān)系，若交點(diǎn)個(gè)數(shù)偶數(shù)，V點(diǎn)在外邊，反之在多邊形內(nèi)部奇異情況處理交點(diǎn)通過(guò)多邊形頂點(diǎn)8/14/20229掃描轉(zhuǎn)換多邊形-逐點(diǎn)判斷法累計(jì)角度法步驟從v點(diǎn)向多邊形P頂點(diǎn)發(fā)出射線，形成有向角 ,取絕對(duì)值小于180度的角計(jì)算有向角的和8/14/202210掃描轉(zhuǎn)換多邊形-逐點(diǎn)判斷法累計(jì)角度法奇異情況處理對(duì)于落在邊上的點(diǎn),作預(yù)處理由于

5、所求解以2pi為周期, 應(yīng)取角度的絕對(duì)值小于pi的解.等于pi時(shí),點(diǎn)落在邊上,已在預(yù)處理過(guò)程中處理掉了.8/14/202211掃描轉(zhuǎn)換多邊形-逐點(diǎn)判斷法累計(jì)角度方法的離散方法（編碼方法）8/14/202212掃描轉(zhuǎn)換多邊形-逐點(diǎn)判斷法8/14/202213掃描轉(zhuǎn)換多邊形-逐點(diǎn)判斷法8/14/202214掃描轉(zhuǎn)換多邊形-掃描線算法掃描線算法目標(biāo)：利用像素之間的連貫性，提高算法效率處理對(duì)象：非自交多邊形8/14/202215掃描轉(zhuǎn)換多邊形-掃描線算法掃描線的連貫性：掃描線與多邊形有偶數(shù)個(gè)交點(diǎn)，排序后(1,2), (3,4)區(qū)段位于多邊形內(nèi)部。利用掃描線的連貫性填充每一條掃描線位于多邊形內(nèi)部的區(qū)段8

6、/14/202216掃描轉(zhuǎn)換多邊形-掃描線算法基本原理一條掃描線與多邊形的邊有偶數(shù)個(gè)交點(diǎn)步驟：求交排序填充（交點(diǎn)配對(duì)，填充區(qū)段）8/14/202217掃描轉(zhuǎn)換多邊形-掃描線算法利用邊的連貫性(一條邊與相繼的兩條掃描線的交點(diǎn)的連貫性),提高求交效率第一類(lèi)交點(diǎn)：新出現(xiàn)的邊與掃描線的交點(diǎn)第二類(lèi)交點(diǎn)：位于同一條邊上的后繼交點(diǎn)8/14/202218掃描轉(zhuǎn)換多邊形-掃描線算法第二類(lèi)交點(diǎn)可以利用邊的連貫性來(lái)獲得邊的連貫性與掃描轉(zhuǎn)換直線段算法中用到的遞推關(guān)系完全一致,所以求交過(guò)程中可以直接利用直線段的中點(diǎn)算法遞推式.用于線畫(huà)圖元掃描轉(zhuǎn)換的四舍五入原則,將導(dǎo)致部分像素位于多邊形之外.為了使得所求得的像素點(diǎn)都落在

7、多邊形區(qū)域內(nèi),需要對(duì)算法作一些改進(jìn).8/14/202219掃描轉(zhuǎn)換多邊形-掃描線算法交點(diǎn)的取整規(guī)則要求：使生成的像素全部位于多邊形之內(nèi)假定非水平邊與掃描線y=e相交，交點(diǎn)的合作標(biāo)為x,規(guī)則如下8/14/202220掃描轉(zhuǎn)換多邊形-掃描線算法X為小數(shù)(a)交點(diǎn)位于左邊之上，向右取整(b)交點(diǎn)位于右邊之上，向左取整8/14/202221掃描轉(zhuǎn)換多邊形-掃描線算法2. (x,e)落在像素之上(a) (x,e)位于左邊之上，屬于多邊形(b) (x,e)位于右邊之上，不屬于多邊形8/14/202222掃描轉(zhuǎn)換多邊形-掃描線算法3. 交點(diǎn)位于多邊形的頂點(diǎn)(a) 算作1個(gè)交點(diǎn)(b) 算作1個(gè)交點(diǎn)(c) 算作

8、2個(gè)交點(diǎn)(d) 算作0個(gè)交點(diǎn)8/14/202223掃描轉(zhuǎn)換多邊形-掃描線算法特殊情況處理水平邊:扔掉！尖角：反混淆8/14/202224掃描轉(zhuǎn)換多邊形-掃描線算法數(shù)據(jù)結(jié)構(gòu)邊邊的分類(lèi)表E按照邊的下端點(diǎn)y坐標(biāo)對(duì)非水平邊進(jìn)行分類(lèi)的指針數(shù)組活化邊表AEL紀(jì)錄與當(dāng)前掃描線相交的邊（交點(diǎn)）typedef struct int ymax; float x,deltax; Edge *nextEdge; Edge; 8/14/202225掃描轉(zhuǎn)換多邊形-掃描線算法幾個(gè)概念活性邊：與當(dāng)前掃描線相交的邊。按交點(diǎn)x的增量順序存放在一個(gè)鏈表中； 活性邊表：活性邊表的每個(gè)結(jié)點(diǎn)存放對(duì)應(yīng)邊的有關(guān)信息。 邊的連貫性：某條邊與

9、當(dāng)前掃描線相交，也可能與下一條掃描線相交。 掃描線的連貫性：當(dāng)前掃描線與各邊的交點(diǎn)順序與下一條掃描線與各邊的交點(diǎn)順序可能相同或類(lèi)似。8/14/202226掃描轉(zhuǎn)換多邊形-掃描線算法8/14/202227掃描轉(zhuǎn)換多邊形-掃描線算法算法1、建立ET；2、將掃描線縱坐標(biāo)y的初值置為ET中非空元素的最小序號(hào)，如在上圖中，y=1；3、置AEL為空；4、執(zhí)行下列步驟直至ET和AEL都為空4.1、如ET中的第y類(lèi)非空，則將其中的所有邊取出并插入AEL中；4.2、如果有新邊插入AEL，則對(duì)AEL中各邊排序；8/14/202228掃描轉(zhuǎn)換多邊形-掃描線算法4.3、對(duì)AEL中的邊兩兩配對(duì)，（1和2為一對(duì)，3和4

10、為一對(duì)，），將每對(duì)邊中x坐標(biāo)按規(guī)則取整，獲得有效的填充區(qū)段，再填充4.4、將當(dāng)前掃描線縱坐標(biāo)y值遞值1；4.5、將AEL中滿(mǎn)足y=ymax邊刪去（因?yàn)槊織l邊被看作下閉上開(kāi)的）；4.6、對(duì)AEL中剩下的每一條邊的x遞增deltax，即x = x+deltax8/14/202229掃描轉(zhuǎn)換多邊形-邊界標(biāo)志算法基本思想：幀緩沖器中對(duì)多邊形的每條邊進(jìn)行直線掃描轉(zhuǎn)換，亦即對(duì)多邊形邊界所經(jīng)過(guò)的象素打上標(biāo)志。然后再采用和掃描線算法類(lèi)似的方法將位于多邊形內(nèi)的各個(gè)區(qū)段著上所需顏色。使用一個(gè)布爾量inside 來(lái)指示當(dāng)前點(diǎn)是否在 多邊形內(nèi)的狀態(tài)。8/14/202230算法void edgemark_fill(po

11、lydef, color)多邊形定義 polydef； int color; 對(duì)多邊形polydef 每條邊進(jìn)行直線掃描轉(zhuǎn)換； inside = FALSE; for (每條與多邊形polydef相交的掃描線y ) for (掃描線上每個(gè)象素x ) if(象素 x 被打上邊標(biāo)志) inside = ! (inside); if(inside！= FALSE) drawpixel (x, y, color); else drawpixel (x, y, background); 8/14/202231掃描轉(zhuǎn)換多邊形-邊界標(biāo)志算法用軟件實(shí)現(xiàn)時(shí)，掃描線算法與邊界標(biāo)志算法的執(zhí)行速度幾乎相同，但由于邊界

12、標(biāo)志算法不必建立維護(hù)邊表以及對(duì)它進(jìn)行排序，所以邊界標(biāo)志算法更適合硬件實(shí)現(xiàn)，這時(shí)它的執(zhí)行速度比有序邊表算法快一至兩個(gè)數(shù)量級(jí)。8/14/202232掃描轉(zhuǎn)換多邊形-邊緣填充算法邊緣填充算法原理：以求余運(yùn)算代替掃描線算法中的排序運(yùn)算（對(duì)于每條掃描線和每條多邊形邊的交點(diǎn)，將該掃描線上交點(diǎn)右方的所有象素取補(bǔ)。對(duì)多邊形的每條邊作此處理，與邊的順序無(wú)關(guān)。） 求余(A=0 xFFFFFFFF)適合用于具有幀緩存的圖形系統(tǒng)。8/14/202233掃描轉(zhuǎn)換多邊形-邊緣填充算法優(yōu)點(diǎn)：算法簡(jiǎn)單缺點(diǎn)：對(duì)于復(fù)雜圖形，每一象素可能被訪問(wèn)多次，輸入/輸出的量比有序邊表算法大得多。8/14/202234掃描轉(zhuǎn)換多邊形-邊緣填充

13、算法算法1：（以掃描線為中心的邊緣填充算法） 1、將當(dāng)前掃描線上的所有象素著上值為 的顏色；2、求余：for(i = 0;i = m; i+)在當(dāng)前掃描線上，從x坐標(biāo)為交點(diǎn)向右求余； 8/14/202235掃描轉(zhuǎn)換多邊形-邊緣填充算法8/14/202236掃描轉(zhuǎn)換多邊形-邊緣填充算法算法2：以邊為中心的邊緣填充算法 1、將繪圖窗口的背景色置為；2、對(duì)多邊形的每一條非水平邊做：從該邊上的每個(gè)象素開(kāi)始向右求余； 8/14/202237掃描轉(zhuǎn)換多邊形-邊緣填充算法8/14/202238掃描轉(zhuǎn)換扇形區(qū)域扇形區(qū)域的描述原理：同掃描轉(zhuǎn)換多邊形問(wèn)題：如何確定掃描線與直線段和圓弧段的相交順序方法：分類(lèi)按點(diǎn) 和

14、 點(diǎn)所處象限的不同，需要將扇形區(qū)域分成44=16種情況 8/14/202239掃描轉(zhuǎn)換扇形區(qū)域假設(shè) 點(diǎn)落在第一象限 ,扇形區(qū)域的掃描轉(zhuǎn)換 分四種情況1、 落在第一象限 8/14/202240掃描轉(zhuǎn)換扇形區(qū)域2、 落在第二象限，此時(shí)又分為兩種情況 當(dāng) 時(shí)當(dāng) 時(shí)8/14/202241掃描轉(zhuǎn)換扇形區(qū)域3、 落在第三象限 4、 落在第四象限 8/14/202242掃描轉(zhuǎn)換扇形區(qū)域遺留問(wèn)題：當(dāng) 落在其它區(qū)域時(shí)?其它方法：多邊形迫近方法8/14/202243區(qū)域填充區(qū)域：點(diǎn)陣表示的圖形，像素集合表示方法：內(nèi)點(diǎn)表示、邊界表示內(nèi)點(diǎn)表示枚舉處區(qū)域內(nèi)部的所有像素內(nèi)部的所有像素著同一個(gè)顏色邊界像素像素著與內(nèi)部像素不

15、同的顏色邊界表示枚舉出邊界上所有的像素邊界上的所有像素著同一顏色內(nèi)部像素著與邊界像素不同的顏色8/14/202244區(qū)域填充區(qū)域填充將指定的顏色從種子點(diǎn)擴(kuò)展到整個(gè)取得過(guò)程例子：PaintBrush例子：PhotoShop8/14/202245區(qū)域填充連通性：4連通、8連通4連通：8連通8/14/202246區(qū)域填充4連通與8連通區(qū)域的區(qū)別連通性對(duì)邊界的要求8/14/202247區(qū)域填充種子填充算法（四向算法）：允許從四個(gè)方向?qū)ふ蚁乱幌笏?，棧結(jié)構(gòu)實(shí)現(xiàn)。 算法：種子象素入棧，當(dāng)棧非空時(shí)，重復(fù)執(zhí)行： （ 棧頂象素出棧；將出棧象素置成多邊形色；四向檢查象素，若其中某個(gè)象素不在邊界對(duì)未置成多邊形色，該象

16、素入棧。） 可用于填充帶內(nèi)孔的平面區(qū)域。8/14/202248區(qū)域填充遞歸填充算法內(nèi)點(diǎn)表示的4連通區(qū)域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,newC

17、olor); /*end of FloodFill4()*/ 8/14/202249區(qū)域填充8/14/202250區(qū)域填充邊界表示的4連通區(qū)域void BoundaryFill4(int x,int y,int oldColor,int newColor)int color;color = GetPixel(x,y);if(color != boundaryColor) & (color != newColor)PutPixel(x,y,newColor);BoundaryFill4(x,y+1,oldColor,newColor);BoundaryFill4(x,y-1,oldColor,n

18、ewColor);BoundaryFill4(x-1,y,oldColor,newColor);BoundaryFill4(x+1,y,oldColor,newColor);/*end of BoundaryFill4()*/ 8/14/202251區(qū)域填充內(nèi)點(diǎn)表示與邊界表示的8連通區(qū)域？遞歸填充算法的特點(diǎn)算法、程序簡(jiǎn)單遞歸層次太多，效率極低（有些象素會(huì)入棧多次，降低算法效率；棧結(jié)構(gòu)占空間。遞歸執(zhí)行，算法簡(jiǎn)單，但效率不高，區(qū)域內(nèi)每一象素都引起一次遞歸，進(jìn)/出棧，費(fèi)時(shí)費(fèi)內(nèi)存）例子：判斷填充方法改進(jìn)算法:減少遞歸次數(shù)。解決方法:用掃描線填充算法；例子：PaintBrush例子：PhotoShop8

19、/14/202252區(qū)域填充掃描線算法目標(biāo)：減少遞歸層次步驟1、填充并確定種子區(qū)段 ；2、初始化 ：將種子區(qū)段壓入堆棧；3、出棧：如果堆棧為空，則算法結(jié)束；否則取棧頂元素 （y,xLeft,xRight），以縱坐標(biāo)為 y的掃描線為當(dāng)前 掃描線，xLeft,xRight為搜索區(qū)間 ；4、填充并確定新的區(qū)段 。8/14/202253區(qū)域填充8/14/202254多邊形掃描轉(zhuǎn)換與區(qū)域填充方法比較相同點(diǎn)： 都是光柵圖形面著色，用于真實(shí)感圖形顯示?？上嗷マD(zhuǎn)換。 不同點(diǎn)： 1.基本思想不同: 前者:頂點(diǎn)表示轉(zhuǎn)換成點(diǎn)陳表示 后者:只改變區(qū)域內(nèi)填充顏色，沒(méi)有改變表示方法。 2.對(duì)邊界的要求不同 前者只要求掃描線與多邊形邊界交點(diǎn)個(gè)數(shù)為偶數(shù)。 后者：區(qū)域封閉，防止遞歸填充跨界。 3.基本的條件不同 前者：從邊界頂點(diǎn)信息出發(fā)。 后者：區(qū)域內(nèi)種子點(diǎn)。 8/14/202255以圖象填充區(qū)域四種填充方法： (1)均勻著色方法； (2)位圖不透明； (3)位圖透明； (4)像素圖填充。8/14/202256以圖象填充區(qū)域基本問(wèn)題 :建立繪圖空間與紋理（圖像）空間的1-1映射 方法1：建立整個(gè)繪圖空間與圖像空間的 1-1映射方法2：建立區(qū)域局部坐標(biāo)空間與圖像空間 的1-1映射8/14/202257以圖像填充區(qū)域例子：PowerPo