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

計(jì)算機(jī)圖形學(xué)邊緣填充算法第一頁，共六十三頁，編輯于2023年，星期五基本思想:對于每一條掃描線和每條多邊形邊的交點(diǎn)(x1,y1),將該掃描線上交點(diǎn)右方的所有象素取補(bǔ).對多邊形的每條邊做此處理,多邊形的順序隨意.該算法的優(yōu)點(diǎn)是簡單,缺點(diǎn)是對復(fù)雜圖形,每一象素可能被訪問多次,輸入輸出的量比較大.??邊緣填充算法第二頁，共六十三頁，編輯于2023年，星期五以掃描線為中心的邊緣填充算法基本思想:對于每一條掃描線和每條多邊形邊的交點(diǎn)(x1,y1),將該掃描線上交點(diǎn)右方的所有象素取補(bǔ).對多邊形的每條邊做此處理,

多邊形的順序隨意.第三頁，共六十三頁，編輯于2023年，星期五將當(dāng)前掃描線上的所有象素著上指定顏色的補(bǔ)色以掃描線為中心的邊緣填充算法第四頁，共六十三頁，編輯于2023年，星期五向右求余從1)(xa以掃描線為中心的邊緣填充算法第五頁，共六十三頁，編輯于2023年，星期五以掃描線為中心的邊緣填充算法第六頁，共六十三頁，編輯于2023年，星期五向右求余從2)(xc以掃描線為中心的邊緣填充算法第七頁，共六十三頁，編輯于2023年，星期五向右求余從2)(xc以掃描線為中心的邊緣填充算法第八頁，共六十三頁，編輯于2023年，星期五向右求余從3)(xd以掃描線為中心的邊緣填充算法第九頁，共六十三頁，編輯于2023年，星期五向右求余從3)(xd以掃描線為中心的邊緣填充算法第十頁，共六十三頁，編輯于2023年，星期五以掃描線為中心的邊緣填充算法第十一頁，共六十三頁，編輯于2023年，星期五以掃描線為中心的邊緣填充算法將當(dāng)前掃描線上的所有象素著上指定顏色的補(bǔ)色第十二頁，共六十三頁，編輯于2023年，星期五以掃描線為中心的邊緣填充算法將當(dāng)前掃描線上的所有象素著上指定顏色的補(bǔ)色第十三頁，共六十三頁，編輯于2023年，星期五以掃描線為中心的邊緣填充算法第十四頁，共六十三頁，編輯于2023年，星期五以掃描線為中心的邊緣填充算法第十五頁，共六十三頁，編輯于2023年，星期五以掃描線為中心的邊緣填充算法第十六頁，共六十三頁，編輯于2023年，星期五以掃描線為中心的邊緣填充算法第十七頁，共六十三頁，編輯于2023年，星期五以掃描線為中心的邊緣填充算法第十八頁，共六十三頁，編輯于2023年，星期五以掃描線為中心的邊緣填充算法第十九頁，共六十三頁，編輯于2023年，星期五以掃描線為中心的邊緣填充算法對各條掃描線循環(huán)上述處理過程。第二十頁，共六十三頁，編輯于2023年，星期五以邊為中心的邊緣填充算法原始多邊形第二十一頁，共六十三頁，編輯于2023年，星期五以邊為中心的邊緣填充算法初始化：將繪圖窗口的背景色置為多邊形顏色的補(bǔ)色第二十二頁，共六十三頁，編輯于2023年，星期五以邊為中心的邊緣填充算法對非水平邊上的每個(gè)象素點(diǎn)向右求余第二十三頁，共六十三頁，編輯于2023年，星期五以邊為中心的邊緣填充算法第二十四頁，共六十三頁，編輯于2023年，星期五以邊為中心的邊緣填充算法第二十五頁，共六十三頁，編輯于2023年，星期五以邊為中心的邊緣填充算法第二十六頁，共六十三頁，編輯于2023年，星期五

該算法的優(yōu)點(diǎn)是簡單,缺點(diǎn)是對復(fù)雜圖形,每一象素可能被訪問多次,輸入輸出的量比較大.

柵欄填充算法

基本思想:對于每個(gè)掃描線與多邊形邊的交點(diǎn),僅將交點(diǎn)與柵欄之間的象素取補(bǔ).邊緣填充算法特點(diǎn)第二十七頁，共六十三頁，編輯于2023年，星期五柵欄填充算法向左求余從0)(xa將當(dāng)前掃描線上的所有象素著上指定顏色的補(bǔ)色第二十八頁，共六十三頁，編輯于2023年，星期五向左求余從1)(xa柵欄填充算法第二十九頁，共六十三頁，編輯于2023年，星期五向左求余從2)(xa將當(dāng)前掃描線上的所有象素著上指定顏色的補(bǔ)色柵欄填充算法第三十頁，共六十三頁，編輯于2023年，星期五向右求余從3)(xa將當(dāng)前掃描線上的所有象素著上指定顏色的補(bǔ)色柵欄填充算法第三十一頁，共六十三頁，編輯于2023年，星期五

邊標(biāo)志算法進(jìn)一步改進(jìn)了柵欄算法,使得算法對每個(gè)象素僅訪問一次.

邊標(biāo)志算法分兩步進(jìn)行:

對多邊形邊界上的象素打上邊標(biāo)志;

填充.邊標(biāo)志算法第三十二頁，共六十三頁，編輯于2023年，星期五

掃描線算法：對每條掃描線，首先計(jì)算它與扇形區(qū)域邊界的交點(diǎn)，再把配對交點(diǎn)之間的像素用指定顏色填充。FillingEllipseArcs第三十三頁，共六十三頁，編輯于2023年，星期五區(qū)域（種子）填充是指先將區(qū)域內(nèi)的一點(diǎn)(種子點(diǎn))賦予給定顏色,然后將顏色擴(kuò)充到整個(gè)區(qū)域內(nèi)的過程(染色過程).區(qū)域:已經(jīng)表示成點(diǎn)陣形式的象素集合,具有相同顏色.區(qū)域填充(種子填充算法)第三十四頁，共六十三頁，編輯于2023年，星期五區(qū)域的兩種表示:內(nèi)點(diǎn)表示、邊界表示.邊界表示:給位于邊界上的所有象素著色,而區(qū)域內(nèi)不著色.區(qū)域的表示內(nèi)點(diǎn)表示:給區(qū)域內(nèi)所有象素都著上同一種顏色

(特征值),邊界上pixel不著色.第三十五頁，共六十三頁，編輯于2023年，星期五要求:

區(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）第三十六頁，共六十三頁，編輯于2023年，星期五4連通運(yùn)動(dòng)方向8連通運(yùn)動(dòng)方向區(qū)域連通性（2）第三十七頁，共六十三頁，編輯于2023年，星期五區(qū)域連通性（3）允許從4個(gè)方向搜索下一個(gè)象素的填充算法稱為是四向填充算法允許從8個(gè)方向搜索下一個(gè)象素的填充算法稱為是8向填充算法第三十八頁，共六十三頁，編輯于2023年，星期五算法思想：

設(shè)G為一內(nèi)點(diǎn)表示的區(qū)域，(x,y)是G內(nèi)一點(diǎn)，以(x,y)為種子點(diǎn)，先將(x,y)置為newcolor，然后對(x,y)的4(或8)領(lǐng)域進(jìn)行遞歸處理，逐步將整個(gè)區(qū)域G置為newcolor.(1)遞歸算法第三十九頁，共六十三頁，編輯于2023年，星期五遞歸填充算法初始化：種子象素入棧第一步：棧頂象素出棧，作為種子點(diǎn)；第二步：種子點(diǎn)被置為填充色；第三步：按照上、下、左、右順序檢查與種子點(diǎn)相鄰的象素：若非邊界且未被填充，則入棧（8向連通區(qū)域需考慮更多相鄰象素）。若棧不空，則重復(fù)第一步。第四十頁，共六十三頁，編輯于2023年，星期五voidFloodFill4(intx,inty,intoldColor,intnewColor)

{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);}

}

Algorithm第四十一頁，共六十三頁，編輯于2023年，星期五12345678910111213141516171819202122Example：第四十二頁，共六十三頁，編輯于2023年，星期五算法:(1)填充并確定種子點(diǎn)所在的區(qū)段；

(2)將種子區(qū)段壓棧;(3)若堆棧非空,棧頂區(qū)段出棧;否則算法結(jié)束;(4)填充并確定新的區(qū)段,將其區(qū)段信息壓棧.(2)掃描線算法第四十三頁，共六十三頁，編輯于2023年，星期五掃描線種子填充算法流程（1）初始化：由指定的種子象素點(diǎn)(x,y)生成種子(y,xl,xr),填充并入棧。

(xl,xr分別為種子點(diǎn)所在掃描線上多邊形內(nèi)部區(qū)間的左、右端點(diǎn))第一步：若種子?？談t算法終止，否則棧頂種子出棧第二步：確定新種子：分別確定y+1,y-1掃描線上與(y,xl,xr)連通的區(qū)間；填充新區(qū)間并將新種子壓入堆棧第三步：上述過程循環(huán)執(zhí)行。第四十四頁，共六十三頁，編輯于2023年，星期五掃描線種子填充算法流程（2）考慮到區(qū)域可以是凹的或有內(nèi)環(huán)的，所以可能在該掃描線上出現(xiàn)多個(gè)填充區(qū)間，亦即需定義多個(gè)種子。yy+1同樣考慮到凹或有孔的區(qū)域，需對掃描線y-1進(jìn)行同樣的處理，獲得新的種子。第四十五頁，共六十三頁，編輯于2023年，星期五掃描線種子填充算法的改進(jìn)思路算法中的回溯過程并非總是必要的。無需進(jìn)行填充回溯需要進(jìn)行填充回溯第四十六頁，共六十三頁，編輯于2023年，星期五Patternfilling用圖象(pattern)填充區(qū)域

Definitionofthepattern:MXNbitmapspattern[i][j]:thevalueoftheposition(i,j)第四十七頁，共六十三頁，編輯于2023年，星期五Twoissues

therelationoftheareaofthepatterntothatoftheprimitiveRelativeanchorAbsoluteanchorwritemodeTransparentOpaque第四十八頁，共六十三頁，編輯于2023年，星期五RelativeanchorToanchorthepatternatavertexoftheprimitive:(x0,y0)value[x][y]=pattern[(x-x0)%M][(y-y0)%N](x0,y0)MN個(gè)像素定義的圖案第四十九頁，共六十三頁，編輯于2023年，星期五AbsoluteanchorMN個(gè)像素定義的圖案

Toconsidertheentirescreenasbeingtiledwiththepatternandtothinkoftheprimitiveasconsistingofanoutlineorfilledareaoftransparentbitsthatletthepatternshowthroughvalue[x][y]=pattern[x%M][y%n](x,y)第五十頁，共六十三頁，編輯于2023年，星期五writemodeFillingwithapattern:Addingextracontroltothepartofthescan-conversionalgorithmthatactuallywriteseachpixelWritemodeDoingPutPixelwithforegroundcoloratapixelfora1inthepatternIntransparentmode:

若為0，則不改變屏幕上該象素的顏色（不做任何處理）；Inopaquemode

若為0，則用背景色顯示該象素第五十一頁，共六十三頁，編輯于2023年，星期五PatternfillingwithoutrepeatedscanconversionRectanglewriteToscanconvertaprimitivefirstintoarectangularworkarea,andthentowriteeachpixelfromthatbitmaptotheappropriateplaceinthecanvas.TwiceasmuchworkasfillingduringscanconversionBesuitabletocharacters,iconsandapplicationsymbols第五十二頁，共六十三頁，編輯于2023年，星期五(a)Mountainscene(b)Outlineofhouseicon(d)(e)(g)(c)Brickpattern(f)(d)Bitmapforsolidversionofhouseicon.(e)Clearingthescenebywritingbackground(f)Brickpatternappliedtohouseicon(g)WritingthescreentransparentlywithpatternedhouseiconAnexample:Writingapatternedobjectinopaquemodewithtwotransparentwrites第五十三頁，共六十三頁，編輯于2023年，星期五Thickprimitives

在產(chǎn)生一定寬度的線條時(shí),只需用一個(gè)“刷子”來替代單象素直線段中掃描生成的單象素即可.線畫圖元的屬性控制第五十四頁，共六十三頁，編輯于2023年，星期五Replicatingpixels(1)(線刷子)Usingmorethan1pixelforeachcolumn(orrow)duringscanconversionThicklinedrawnbycolumnreplicationPixelsareduplicatedincolumnforlineswith–1<slope<1Pixelsareduplicatedinrowsforallotherlines第五十五頁，共六十三頁，編輯于2023年，星期五原理:假設(shè)直線斜率在[-1,+1]之間,如圖(a)所示.這時(shí)可把刷子置成垂直方向圖(b).首先將刷子的中點(diǎn)對準(zhǔn)直線的一個(gè)端點(diǎn),從該點(diǎn)開始,讓刷子中點(diǎn)沿直線的軌跡往直線的另一端點(diǎn)平移即可“刷出”具有一定寬度的直線.如圖(c).m1m2(a)(b)(c)ReplicatingPixels(2)第五十六頁，共六十三頁，編輯于2023年，星期五缺點(diǎn):(1)線的始末斷總是水平或垂直的.(2)線的粗細(xì)不一樣.水平和垂直線最粗,45斜線最細(xì).(3)

當(dāng)線寬為偶數(shù)個(gè)時(shí),繪制的線條寬度不精確.Disadvantages第五十七頁，共六十三頁，編輯于2023年，星期五

方形刷子是一個(gè)寬度為指定線寬的正方形.將正方形的中心對準(zhǔn)直線作平移運(yùn)動(dòng)即可.

m1TheMovingPen(方形刷子)方形刷子第五十八頁，共六十三頁，編輯于2023年，星期五TheMovingPen(方形刷子)Thicklinedrawnbytracingarect