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

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

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

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

柵欄填充算法

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

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

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

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

填充.邊標(biāo)志算法第三十二頁(yè)，共六十三頁(yè)，2022年，8月28日

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

(特征值),邊界上pixel不著色.第三十五頁(yè)，共六十三頁(yè)，2022年，8月28日要求:

區(qū)域具有一定的連通性:4連通或8連通4連通區(qū)域:取區(qū)域內(nèi)任意兩點(diǎn),在該區(qū)域內(nèi)(不能通過(guò)區(qū)域外的點(diǎn)),若從其中一點(diǎn)出發(fā),通過(guò)上、下、左、右四種運(yùn)動(dòng)可到達(dá)另一點(diǎn)時(shí),則稱該區(qū)域?yàn)?連通區(qū)域.區(qū)域連通性（1）第三十六頁(yè)，共六十三頁(yè)，2022年，8月28日4連通運(yùn)動(dòng)方向8連通運(yùn)動(dòng)方向區(qū)域連通性（2）第三十七頁(yè)，共六十三頁(yè)，2022年，8月28日區(qū)域連通性（3）允許從4個(gè)方向搜索下一個(gè)象素的填充算法稱為是四向填充算法允許從8個(gè)方向搜索下一個(gè)象素的填充算法稱為是8向填充算法第三十八頁(yè)，共六十三頁(yè)，2022年，8月28日算法思想：

設(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)遞歸算法第三十九頁(yè)，共六十三頁(yè)，2022年，8月28日遞歸填充算法初始化：種子象素入棧第一步：棧頂象素出棧，作為種子點(diǎn)；第二步：種子點(diǎn)被置為填充色；第三步：按照上、下、左、右順序檢查與種子點(diǎn)相鄰的象素：若非邊界且未被填充，則入棧（8向連通區(qū)域需考慮更多相鄰象素）。若棧不空，則重復(fù)第一步。第四十頁(yè)，共六十三頁(yè)，2022年，8月28日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第四十一頁(yè)，共六十三頁(yè)，2022年，8月28日12345678910111213141516171819202122Example：第四十二頁(yè)，共六十三頁(yè)，2022年，8月28日算法:(1)填充并確定種子點(diǎn)所在的區(qū)段；

(2)將種子區(qū)段壓棧;(3)若堆棧非空,棧頂區(qū)段出棧;否則算法結(jié)束;(4)填充并確定新的區(qū)段,將其區(qū)段信息壓棧.(2)掃描線算法第四十三頁(yè)，共六十三頁(yè)，2022年，8月28日掃描線種子填充算法流程（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ū)間并將新種子壓入堆棧第三步：上述過(guò)程循環(huán)執(zhí)行。第四十四頁(yè)，共六十三頁(yè)，2022年，8月28日掃描線種子填充算法流程（2）考慮到區(qū)域可以是凹的或有內(nèi)環(huán)的，所以可能在該掃描線上出現(xiàn)多個(gè)填充區(qū)間，亦即需定義多個(gè)種子。yy+1同樣考慮到凹或有孔的區(qū)域，需對(duì)掃描線y-1進(jìn)行同樣的處理，獲得新的種子。第四十五頁(yè)，共六十三頁(yè)，2022年，8月28日掃描線種子填充算法的改進(jìn)思路算法中的回溯過(guò)程并非總是必要的。無(wú)需進(jìn)行填充回溯需要進(jìn)行填充回溯第四十六頁(yè)，共六十三頁(yè)，2022年，8月28日Patternfilling用圖象(pattern)填充區(qū)域

Definitionofthepattern:MXNbitmapspattern[i][j]:thevalueoftheposition(i,j)第四十七頁(yè)，共六十三頁(yè)，2022年，8月28日Twoissues

therelationoftheareaofthepatterntothatoftheprimitiveRelativeanchorAbsoluteanchorwritemodeTransparentOpaque第四十八頁(yè)，共六十三頁(yè)，2022年，8月28日RelativeanchorToanchorthepatternatavertexoftheprimitive:(x0,y0)value[x][y]=pattern[(x-x0)%M][(y-y0)%N](x0,y0)MN個(gè)像素定義的圖案第四十九頁(yè)，共六十三頁(yè)，2022年，8月28日AbsoluteanchorMN個(gè)像素定義的圖案

Toconsidertheentirescreenasbeingtiledwiththepatternandtothinkoftheprimitiveasconsistingofanoutlineorfilledareaoftransparentbitsthatletthepatternshowthroughvalue[x][y]=pattern[x%M][y%n](x,y)第五十頁(yè)，共六十三頁(yè)，2022年，8月28日writemodeFillingwithapattern:Addingextracontroltothepartofthescan-conversionalgorithmthatactuallywriteseachpixelWritemodeDoingPutPixelwithforegroundcoloratapixelfora1inthepatternIntransparentmode:

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

若為0，則用背景色顯示該象素第五十一頁(yè)，共六十三頁(yè)，2022年，8月28日PatternfillingwithoutrepeatedscanconversionRectanglewriteToscanconvertaprimitivefirstintoarectangularworkarea,andthentowriteeachpixelfromthatbitmaptotheappropriateplaceinthecanvas.TwiceasmuchworkasfillingduringscanconversionBesuitabletocharacters,iconsandapplicationsymbols第五十二頁(yè)，共六十三頁(yè)，2022年，8月28日(a)Mountainscene(b)Outlineofhouseicon(d)(e)(g)(c)Brickpattern(f)(d)Bitmapforsolidversionofhouseicon.(e)Clearingthescenebywritingbackground(f)Brickpatternappliedtohouseicon(g)WritingthescreentransparentlywithpatternedhouseiconAnexample:Writingapatternedobjectinopaquemodewithtwotransparentwrites第五十三頁(yè)，共六十三頁(yè)，2022年，8月28日Thickprimitives

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

當(dāng)線寬為偶數(shù)個(gè)時(shí),繪制的線條寬度不精確.Disadvantages第五十七頁(yè)，共六十三頁(yè)，2022年，8月28日

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

m1TheMovingPen(方形刷子)方形刷子第五十八頁(yè)，共六十三頁(yè)，2022年，8月28日TheMovingPen(方形刷子)Thicklinedrawnbytracingarecta