三下圖形學(xué)第5-10講9和

邊緣填充算法思路：利用求余運(yùn)算代替交點(diǎn)排序、配對(duì)、構(gòu)造填充區(qū)間。原理：像素點(diǎn)顏色值經(jīng)過(guò)偶數(shù)次求余運(yùn)算后保持不變，經(jīng)過(guò)奇數(shù)次求余運(yùn)算后變?yōu)槠溆鄶?shù)算法：以掃描線為中心的邊緣填充算法以邊為中心的邊緣填充算法基本思想：對(duì)于每一條掃描線和每條多邊形邊的交點(diǎn)(x1，y1)，將該掃描線上交點(diǎn)右方的所有像素取補(bǔ)。對(duì)多邊形的每條邊做此處理，多邊形的順序隨意。該算法的優(yōu)點(diǎn)是簡(jiǎn)單，缺點(diǎn)是對(duì)復(fù)雜圖形，每一像素可能被訪問多次，輸入輸出的量比較大。??邊緣填充算法以掃描線為中心的邊緣填充算法基本思想：對(duì)于每一條掃描線和每條多邊形邊的交點(diǎn)(x1,y1)，將該掃描線上交點(diǎn)右方的所有像素取補(bǔ)。對(duì)多邊形的每條邊做此處理，

多邊形的順序隨意。將當(dāng)前掃描線上的所有像素著上指定顏色的補(bǔ)色以掃描線為中心的邊緣填充算法向右求余從1)(xa以掃描線為中心的邊緣填充算法以掃描線為中心的邊緣填充算法向右求余從2)(xc以掃描線為中心的邊緣填充算法向右求余從2)(xc以掃描線為中心的邊緣填充算法向右求余從3)(xd以掃描線為中心的邊緣填充算法向右求余從3)(xd以掃描線為中心的邊緣填充算法以掃描線為中心的邊緣填充算法以掃描線為中心的邊緣填充算法將當(dāng)前掃描線上的所有像素著上指定顏色的補(bǔ)色以掃描線為中心的邊緣填充算法將當(dāng)前掃描線上的所有像素著上指定顏色的補(bǔ)色以掃描線為中心的邊緣填充算法以掃描線為中心的邊緣填充算法以掃描線為中心的邊緣填充算法以掃描線為中心的邊緣填充算法以掃描線為中心的邊緣填充算法以掃描線為中心的邊緣填充算法以掃描線為中心的邊緣填充算法對(duì)各條掃描線循環(huán)上述處理過(guò)程。以邊為中心的邊緣填充算法原始多邊形以邊為中心的邊緣填充算法初始化：將繪圖窗口的背景色置為多邊形顏色的補(bǔ)色以邊為中心的邊緣填充算法對(duì)非水平邊上的每個(gè)像素點(diǎn)向右求余以邊為中心的邊緣填充算法以邊為中心的邊緣填充算法以邊為中心的邊緣填充算法

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

柵欄填充算法

基本思想:對(duì)于每個(gè)掃描線與多邊形邊的交點(diǎn)，僅將交點(diǎn)與柵欄之間的像素取補(bǔ)。邊緣填充算法特點(diǎn)柵欄填充算法向左求余從0)(xa將當(dāng)前掃描線上的所有像素著上指定顏色的補(bǔ)色向左求余從1)(xa柵欄填充算法向左求余從2)(xa將當(dāng)前掃描線上的所有像素著上指定顏色的補(bǔ)色柵欄填充算法向右求余從3)(xa將當(dāng)前掃描線上的所有像素著上指定顏色的補(bǔ)色柵欄填充算法

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

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

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

填充。邊標(biāo)志算法

掃描線算法：對(duì)每條掃描線，首先計(jì)算它與扇形區(qū)域邊界的交點(diǎn)，再把配對(duì)交點(diǎn)之間的像素用指定顏色填充。FillingEllipseArcs

區(qū)域（種子）填充是指先將區(qū)域內(nèi)的一點(diǎn)（種子點(diǎn)）賦予給定顏色，然后將顏色擴(kuò)充到整個(gè)區(qū)域內(nèi)的過(guò)程（染色過(guò)程）。區(qū)域:已經(jīng)表示成點(diǎn)陣形式的像素集合，具有相

同顏色。區(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)（不能通過(guò)區(qū)域外的點(diǎn)），若從其中一點(diǎn)出發(fā)，通過(guò)上、下、左、右四種運(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個(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)遞歸算法遞歸填充算法初始化：種子像素入棧；第一步：棧頂像素出棧，作為種子點(diǎn)；第二步：種子點(diǎn)被置為填充色；第三步：按照上、下、左、右順序檢查與種子點(diǎn)相鄰的像素：若非邊界且未被填充，則入棧（8向連通區(qū)域需考慮更多相鄰像素）；若棧不空，則重復(fù)第一步。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);}

}

Algorithm12345678910111213141516171819202122Example：算法:(1)填充并確定種子點(diǎn)所在的區(qū)段；

(2)將種子區(qū)段壓棧；(3)若堆棧非空，棧頂區(qū)段出棧；否則算法結(jié)束；(4)填充并確定新的區(qū)段，將其區(qū)段信息壓棧。(2)掃描線算法掃描線種子填充算法流程（1）初始化：由指定的種子像素點(diǎn)(x,y)生成種子(y,xl,xr),填充并入棧。

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

Definitionofthepattern:MXNbitmapspattern[i][j]:thevalueoftheposition(i,j)TwoissuestherelationoftheareaofthepatterntothatoftheprimitiveRelativeanchorAbsoluteanchorwritemodeTransparentOpaqueRelativeanchorToanchorthepatternatavertexoftheprimitive:(x0,y0)value[x][y]=pattern[(x-x0)%M][(y-y0)%N](x0,y0)MN個(gè)像素定義的圖案AbsoluteanchorMN個(gè)像素定義的圖案Toconsidertheentirescreenasbeingtiledwiththepatternandtothinkoftheprimitiveasconsistingofanoutlineorfilledareaoftransparentbitsthatletthepatternshowthroughvalue[x][y]=pattern[x%M][y%n](x,y)writemodeFillingwithapattern:Addingextracontroltothepartofthescan-conversionalgorithmthatactuallywriteseachpixelWritemodeDoingPutPixelwithforegroundcoloratapixelfora1inthepatternIntransparentmode:

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

若為0，則用背景色顯示該像素PatternfillingwithoutrepeatedscanconversionRectanglewriteToscanconvertaprimitivefirstintoarectangularworkarea,andthentowriteeachpixelfromthatbitmaptotheappropriateplaceinthecanvas.TwiceasmuchworkasfillingduringscanconversionBesuitabletocharacters,iconsandapplicationsymbols(a)Mountainscene(b)Outlineofhouseicon(d)(e)(g)(c)Brickpattern(f)(d)Bitmapforsolidversionofhouseicon.(e)Clearingthescenebywritingbackground(f)Brickpatternappliedtohouseicon(g)WritingthescreentransparentlywithpatternedhouseiconAnexample:WritingapatternedobjectinopaquemodewithtwotransparentwritesThickprimitives

在產(chǎn)生一定寬度的線條時(shí)，只需用一個(gè)“刷子”來(lái)替代單像素直線段中掃描生成的單像素即可。線畫圖元的屬性控制Replicatingpixels(1)(線刷子)Usingmorethan1pixelforeachcolumn(orrow)duringscanconversionThicklinedrawnbycolumnreplicationPixelsareduplicatedincolumnforlineswith–1<slope<1Pixelsareduplicatedinrowsforallotherlines原理:假設(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)缺點(diǎn):(1)線的始末斷總是水平或垂直的。(2)線的粗細(xì)不一樣，水平和垂直線最粗，45斜線最細(xì)。(3)

當(dāng)線寬為偶數(shù)個(gè)時(shí)，繪制的線條寬度不精確。Disadvantages

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

m1TheMovingPen(方形刷子)方形刷子TheMovingPen(方形刷子)Thicklinedrawnbytracingarectangularpen.Thic