計(jì)算機(jī)圖形學(xué)課件：6 邊緣填充算法

1、邊緣填充算法,思路：利用求余運(yùn)算代替交點(diǎn)排序、配對(duì)、構(gòu)造填充區(qū)間。 原理：象素點(diǎn)顏色值經(jīng)過偶數(shù)次求余運(yùn)算后保持不變，經(jīng)過奇數(shù)次求余運(yùn)算后變?yōu)槠溆鄶?shù)。 算法： 以掃描線為中心的邊緣填充算法 以邊為中心的邊緣填充算法,以掃描線為中心的邊緣填充算法,基本思想: 對(duì)于每一條掃描線和每條多邊形邊的交點(diǎn)(xi,yi),將該掃描線上交點(diǎn)右方的所有象素取補(bǔ).對(duì)多邊形的每條邊做此處理，邊的順序隨意。,以掃描線為中心的邊緣填充算法,(1)先將當(dāng)前掃描線上的所有象素著上指定顏色的補(bǔ)色 (2) 當(dāng)前掃描線上的各交點(diǎn)依次將右方的象素顏色取補(bǔ)色,以掃描線為中心的邊緣填充算法,以掃描線為中心的邊緣填充算法,以掃描線為中心的

2、邊緣填充算法,以掃描線為中心的邊緣填充算法,以掃描線為中心的邊緣填充算法,以掃描線為中心的邊緣填充算法,以掃描線為中心的邊緣填充算法,以掃描線為中心的邊緣填充算法,對(duì)各條掃描線循環(huán)上述處理過程。,以邊為中心的邊緣填充算法,原始多邊形,以邊為中心的邊緣填充算法,初始化：將繪圖窗口的背景色置為多邊形顏色的補(bǔ)色,以邊為中心的邊緣填充算法,對(duì)非水平邊上的每個(gè)象素點(diǎn)向右求余,以邊為中心的邊緣填充算法,以邊為中心的邊緣填充算法,以邊為中心的邊緣填充算法,優(yōu)點(diǎn)：與掃描線算法相比，邊緣填充算法的數(shù)據(jù)結(jié)構(gòu)和程序結(jié)構(gòu)簡單。 缺點(diǎn)：但該算法需要對(duì)幀緩存的大量象素反復(fù)賦值，速度較慢。,邊緣填充算法特點(diǎn),柵欄填充算法,

3、柵欄：一條與掃描線垂直的直線，過多邊形的某個(gè)頂點(diǎn)，并把多邊形分為左右兩半。 基本思想: 對(duì)于每條掃描線與多邊形邊的交點(diǎn),僅將交點(diǎn)與柵欄之間的象素取補(bǔ).,柵欄填充算法,將當(dāng)前掃描線上的所有象素著上指定顏色的補(bǔ)色,柵欄填充算法,將當(dāng)前掃描線上的所有象素著上指定顏色的補(bǔ)色,柵欄填充算法,將當(dāng)前掃描線上的所有象素著上指定顏色的補(bǔ)色,柵欄填充算法,邊標(biāo)志填充算法(1),原理： 當(dāng)一條直線穿越多邊形時(shí)，其上各點(diǎn)針對(duì)多邊形的歸屬狀態(tài)將交替變化；若點(diǎn)在多邊形外，則在直線與多邊形相交一次后，點(diǎn)在多邊形內(nèi)；,邊標(biāo)志填充算法(2),算法步驟： 第一步：多邊形各邊界線段經(jīng)掃描轉(zhuǎn)換過程后，對(duì)應(yīng)象素打上邊標(biāo)志； 第二步：

4、 對(duì)每一掃描線，由左至右逐點(diǎn)訪問：每訪問到標(biāo)志點(diǎn)，則進(jìn)行一次多邊形內(nèi)/外部的轉(zhuǎn)換，直至掃描線末。 對(duì)判別為多邊形內(nèi)部的象素點(diǎn)進(jìn)行填充； 第三步：第二步循環(huán)至掃描結(jié)束。 優(yōu)點(diǎn)：邊標(biāo)志算法進(jìn)一步改進(jìn)了柵欄算法,使得算法對(duì)每個(gè)象素僅訪問一次，用硬件實(shí)現(xiàn)時(shí)速度優(yōu)勢(shì)更明顯。,掃描線算法： 對(duì)每條掃描線，首先計(jì)算它與扇形區(qū)域邊界的交點(diǎn)，再把配對(duì)交點(diǎn)之間的像素用指定顏色填充。,Filling Ellipse Arcs,區(qū)域（種子）填充是指先將區(qū)域內(nèi)的一點(diǎn)(種子點(diǎn))賦予給定顏色,然后將顏色擴(kuò)充到整個(gè)區(qū)域內(nèi)的過程(染色過程). 區(qū)域:已經(jīng)表示成點(diǎn)陣形式的象素集合,具有相同顏色. 與多邊形掃描轉(zhuǎn)換的比較 基本思想

5、 邊界要求 基于的條件,區(qū)域填充(種子填充算法),區(qū)域的兩種表示:內(nèi)點(diǎn)表示、邊界表示. 邊界表示:給位于邊界上的所有象素著同一種顏色(特征值),而區(qū)域內(nèi)著不同的顏色.,區(qū)域的表示,內(nèi)點(diǎn)表示:給區(qū)域內(nèi)所有象素都著上同一種顏色 (特征值),邊界上pixel著不同的顏色.,種子填充算法要求: 區(qū)域具有一定的連通性:4連通或8連通。 4連通區(qū)域: 取區(qū)域內(nèi)任意兩點(diǎn),在該區(qū)域內(nèi)(不能通過區(qū)域外的點(diǎn)),若從其中一點(diǎn)出發(fā),通過上、下、左、右 四種運(yùn)動(dòng)可到達(dá)另一點(diǎn)時(shí),則稱該區(qū)域?yàn)?連通區(qū)域.,區(qū)域連通性（1）,4連通運(yùn)動(dòng)方向,8連通運(yùn)動(dòng)方向,區(qū)域連通性（2）,區(qū)域連通性（3）,邊界連通性：4連通區(qū)域雖可看作是

6、8連通區(qū)域，但其作4連通區(qū)域或是8連通區(qū)域時(shí)其邊界不同。,區(qū)域連通性（4）,允許從4個(gè)方向搜索下一個(gè)象素的填充算法稱為是四向填充算法.,允許從8個(gè)方向搜索下一個(gè)象素的填充算法稱為是8向填充算法.,種子填充算法,遞歸填充算法 掃描線算法,算法思想： 設(shè)G為一內(nèi)點(diǎn)表示的區(qū)域，(x,y)是G內(nèi)一點(diǎn)，以(x,y)為種子點(diǎn)，先將(x,y)置為newcolor，然后對(duì)(x,y)的4(或8)領(lǐng)域進(jìn)行遞歸處理，逐步將整個(gè)區(qū)域G置為newcolor.,(1)遞歸算法,void FloodFill4(int x, int y, int oldColor, int newColor) if (GetPixel(x,

7、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); ,Algorithm,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,Example：,優(yōu)點(diǎn)：算法原理和程序都很簡單 缺點(diǎn)：效率不高，原因是遞歸次數(shù)太多，區(qū)域內(nèi)的每

8、個(gè)象素都引起一次遞歸，即系統(tǒng)堆棧的一次進(jìn)出操作，費(fèi)時(shí)費(fèi)內(nèi)存。,遞歸算法,思想: (1)填充并確定種子點(diǎn)所在的區(qū)段； (2)將種子區(qū)段壓棧; (3)若堆棧非空,棧頂區(qū)段出棧;否則算法 結(jié)束; (4)填充并確定新的區(qū)段, 將其區(qū)段信息 壓棧，返回第(3)步。,(2)掃描線種子填充算法,掃描線種子填充算法流程（1）,初始化：由指定的種子象素點(diǎn)(x,y)生成種子區(qū)段(y,xl,xr),填充并入棧。 (xl,xr分別為種子點(diǎn)所在掃描線上多邊形內(nèi)部區(qū)間的左、右端點(diǎn)) 第一步：若種子棧空則算法終止，否則棧頂種子出棧 第二步：確定新種子：分別確定y+1,y-1掃描線上與(y,xl,xr)連通的區(qū)間；填充新區(qū)間

9、并將新種子壓入堆棧， 第三步：上述過程循環(huán)執(zhí)行。,掃描線種子填充算法流程（2）,新種子的確定：,在y+1掃描線的xl,xr區(qū)間內(nèi)遍歷象素點(diǎn)，對(duì)其上非邊界且未被填充的象素點(diǎn)，確定其左、右端點(diǎn)并定義為新種子。,掃描線種子填充算法流程（3）,考慮到區(qū)域可以是凹的或有內(nèi)環(huán)的，所以可能在該掃描線上出現(xiàn)多個(gè)填充區(qū)間，亦即需定義多個(gè)種子。,同樣考慮到凹或有孔的區(qū)域，需對(duì)掃描線y-1進(jìn)行同樣的處理，獲得新的種子。,掃描線種子填充算法的改進(jìn)思路,算法中的回溯過程并非總是必要的。,Pattern filling,用圖像(pattern)填充區(qū)域,Definition of the pattern: M X N b

10、itmaps patternij: the value of the position (i,j),Two issues,the relation of the area of the pattern to that of the primitive Relative anchor（相對(duì)錨定） Absolute anchor（絕對(duì)錨定） write mode Transparent（透明寫） Opaque（不透明寫）,Relative anchor(相對(duì)錨定）,To anchor the pattern at a vertex of the primitive: (x0,y0) valuexy

11、=pattern(x-x0)%M(y-y0)%N,Absolute anchor （絕對(duì)錨定）,To consider the entire screen as being tiled with the pattern and to think of the primitive as consisting of an outline or filled area of transparent bits that let the pattern show through valuexy=patternx%My%N,write mode（寫模式）,Filling with a pattern: A

12、dding extra control to the part of the scan-conversion algorithm that actually writes each pixel Write mode Doing PutPixel with foreground color at a pixel for a 1 in the pattern In transparent mode（透明寫）: 若圖案為0，則不改變屏幕上該象素的顏色（不做任何處理）； In opaque mode（不透明寫）： 若圖案為0，則用背景顏色顯示該象素：,Pattern filling without r

13、epeated scan conversion,Rectangle write To scan convert a primitive first into a rectangular work area, and then to write each pixel from that bitmap to the appropriate place in the canvas. Be suitable to characters, icons and application symbols,(d) Bitmap for solid version of house icon. (e) Clear

14、ing the scene by writing background (f) Brick pattern applied to house icon (g) Writing the screen transparently with patterned house icon,An example: Writing a patterned object in opaque mode with two transparent writes,Thick primitives 在產(chǎn)生一定寬度的線條時(shí),只需用一個(gè)“刷子”來替代單象素直線段中掃描生成的單象素即可.,線畫圖元的屬性控制,Replicati

15、ng pixels(1) (線刷子),Using more than 1 pixel for each column (or row) during scan conversion,Pixels are duplicated in column for lines with 1slope1 Pixels are duplicated in rows for all other lines,原理:假設(shè)直線斜率在-1,+1之間,如圖(a)所示.這時(shí)可把刷子置成垂直方向圖(b).首先將刷子的中點(diǎn)對(duì)準(zhǔn)直線的一個(gè)端點(diǎn),從該點(diǎn)開始,讓刷子中點(diǎn)沿直線的軌跡往直線的另一端點(diǎn)平移即可“刷出”具有一定寬度的直線.

16、如圖(c).,m1,m2,(a),(b),(c),Replicating Pixels(2),缺點(diǎn):(1)線的始末端總是水平或垂直的. (2)線的粗細(xì)不一樣.水平和垂直線最粗,45斜線最 細(xì). (3) 當(dāng)線寬為偶數(shù)個(gè)時(shí),繪制的線條寬度不精確.,Disadvantages,方形刷子是一個(gè)寬度為指定線寬的正方形.將正方形的中心對(duì)準(zhǔn)直線作平移運(yùn)動(dòng)即可.,The Moving Pen(方形刷子),The Moving Pen(方形刷子),Thick line drawn by tracing a rectangular pen.,該方法將會(huì)重復(fù)的寫象素.為避免重復(fù),可采用與活化邊表類似的技術(shù).,Disadvantages,Recording the spans,先算出直線的四個(gè)角點(diǎn)的坐