《計(jì)算機(jī)圖形學(xué)教學(xué)資料》(3)

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

2、編輯ppt以掃描線為中心的邊緣填充算法向右求余從0)(xa0 x1x2x3x編輯ppt以掃描線為中心的邊緣填充算法向右求余從1)(xb0 x1x2x3x編輯ppt以掃描線為中心的邊緣填充算法向右求余從1)(xb0 x1x2x3x編輯ppt以掃描線為中心的邊緣填充算法向右求余從2)(xc0 x1x2x3x編輯ppt以掃描線為中心的邊緣填充算法向右求余從2)(xc0 x1x2x3x編輯ppt以掃描線為中心的邊緣填充算法0 x1x2x3x向右求余從3)(xd編輯ppt以掃描線為中心的邊緣填充算法0 x1x2x3x向右求余從3)(xd編輯ppt以掃描線為中心的邊緣填充算法對(duì)各條掃描線循環(huán)上述處理過程。

3、編輯ppt以邊為中心的邊緣填充算法原始多邊形編輯ppt以邊為中心的邊緣填充算法初始化：將繪圖窗口的背景色置為多邊形顏色的補(bǔ)色編輯ppt以邊為中心的邊緣填充算法對(duì)非水平邊上的每個(gè)象素點(diǎn)向右求余編輯ppt以邊為中心的邊緣填充算法編輯ppt以邊為中心的邊緣填充算法編輯ppt以邊為中心的邊緣填充算法編輯ppt優(yōu)點(diǎn)：優(yōu)點(diǎn)：與掃描線算法相比，邊緣填充算法的數(shù)據(jù)結(jié)構(gòu)和程序結(jié)構(gòu)簡單。缺點(diǎn)：缺點(diǎn)：但該算法需要對(duì)幀緩存的大量象素反復(fù)賦值，速度較慢。邊緣填充算法特點(diǎn)編輯ppt柵欄填充算法柵欄：柵欄：一條與掃描線垂直的直線，過多邊形的某個(gè)頂點(diǎn)，并把多邊形分為左右兩半?；舅枷牖舅枷?對(duì)于每條掃描線與多邊形邊的交點(diǎn),

4、僅將交點(diǎn)與柵欄之間的象素取補(bǔ).編輯ppt柵欄填充算法0 x1x2x3x向左求余從0)(xa將當(dāng)前掃描線上的所有象素著上指定顏色的補(bǔ)色編輯ppt0 x1x2x3x向左求余從1)(xa柵欄填充算法編輯ppt0 x1x2x3x向左求余從2)(xa將當(dāng)前掃描線上的所有象素著上指定顏色的補(bǔ)色柵欄填充算法編輯ppt0 x1x2x3x向右求余從3)(xa將當(dāng)前掃描線上的所有象素著上指定顏色的補(bǔ)色柵欄填充算法編輯ppt邊標(biāo)志填充算法(1)n原理： 當(dāng)一條直線穿越多邊形時(shí)，其上各點(diǎn)針對(duì)多邊形的歸屬狀態(tài)將交替變化；若點(diǎn)在多邊形外，則在直線與多邊形相交一次后，點(diǎn)在多邊形內(nèi)；編輯ppt邊標(biāo)志填充算法(2)n算法步驟：

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

6、程(染色過程).n區(qū)域:已經(jīng)表示成點(diǎn)陣形式的象素集合,具有相同顏色.n與多邊形掃描轉(zhuǎn)換的比較n基本思想n邊界要求n基于的條件區(qū)域填充(種子填充算法)編輯pptn區(qū)域的兩種表示:內(nèi)點(diǎn)表示、邊界表示.v邊界表示:給位于邊界上的所有象素著同一種顏色(特征值),而區(qū)域內(nèi)著不同的顏色.區(qū)域的表示v 內(nèi)點(diǎn)表示:給區(qū)域內(nèi)所有象素都著上同一種顏色 (特征值),邊界上pixel著不同的顏色. 編輯ppt種子填充算法要求: 區(qū)域具有一定的連通性:4連通或8連通。4連通區(qū)域連通區(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)?連通

7、區(qū)域.區(qū)域連通性（區(qū)域連通性（1）編輯ppt4連通運(yùn)動(dòng)方向8連通運(yùn)動(dòng)方向區(qū)域連通性（區(qū)域連通性（2）編輯ppt區(qū)域連通性（區(qū)域連通性（3）邊界連通性邊界連通性：4連通區(qū)域雖可看作是8連通區(qū)域，但其作4連通區(qū)域或是8連通區(qū)域時(shí)其邊界邊界不同。編輯ppt區(qū)域連通性（區(qū)域連通性（4）允許從4個(gè)方向搜索下一個(gè)象素的填充算法稱為是四向填四向填充算法充算法.允許從8個(gè)方向搜索下一個(gè)象素的填充算法稱為是8向填向填充算法充算法.編輯ppt種子填充算法種子填充算法n遞歸填充算法遞歸填充算法n掃描線算法掃描線算法編輯ppt算法思想算法思想： 設(shè)G為一內(nèi)點(diǎn)表示的區(qū)域，(x,y)是G內(nèi)一點(diǎn)，以(x,y)為種子點(diǎn)，先將

8、(x,y)置為newcolor，然后對(duì)(x,y)的4(或8)領(lǐng)域進(jìn)行遞歸處理遞歸處理，逐步將整個(gè)區(qū)域G置為newcolor.(1)遞歸算法編輯pptvoid 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); Flood

9、Fill4(x+1,y,oldColor,newColor); Algorithm編輯ppt12345678910111213141516171819202122Example：編輯ppt優(yōu)點(diǎn)優(yōu)點(diǎn)：算法原理和程序都很簡單缺點(diǎn)：缺點(diǎn)：效率不高，原因是遞歸次數(shù)太多，區(qū)域內(nèi)的每個(gè)象素都引起一次遞歸，即系統(tǒng)堆棧的一次進(jìn)出操作，費(fèi)時(shí)費(fèi)內(nèi)存。遞歸算法編輯ppt思想: (1)填充并確定種子點(diǎn)所在的區(qū)段； (2)將種子區(qū)段壓棧; (3)若堆棧非空,棧頂區(qū)段出棧;否則算法 結(jié)束; (4)填充并確定新的區(qū)段, 將其區(qū)段信息 壓棧，返回第(3)步。(2)掃描線種子填充算法編輯ppt掃描線種子填充算法流程（1）n初始

10、化：由指定的種子象素點(diǎn)(x,y)生成種子區(qū)段(y,xl,xr),填充并入棧。 (xl,xr分別為種子點(diǎn)所在掃描線上多邊形內(nèi)部區(qū)間的左、右端點(diǎn))n第一步：若種子?？談t算法終止，否則棧頂種子出棧n第二步：確定新種子：分別確定y+1,y-1掃描線上與(y,xl,xr)連通的區(qū)間；填充新區(qū)間并將新種子壓入堆棧，n第三步：上述過程循環(huán)執(zhí)行。編輯ppt掃描線種子填充算法流程（2）n新種子的確定：在y+1掃描線的xl,xr區(qū)間內(nèi)遍歷象素點(diǎn)，對(duì)其上非邊界且未被填充的象素點(diǎn)，確定其左、右端點(diǎn)并定義為新種子。編輯ppt掃描線種子填充算法流程（3）考慮到區(qū)域可以是凹的或有內(nèi)環(huán)的，所以可能在該掃描線上出現(xiàn)多個(gè)填充區(qū)間

11、，亦即需定義多個(gè)種子。yy+1同樣考慮到凹或有孔的區(qū)域，需對(duì)掃描線y-1進(jìn)行同樣的處理，獲得新的種子。編輯ppt掃描線種子填充算法的改進(jìn)思路n算法中的回溯過程并非總是必要的。無需進(jìn)行填充回溯需要進(jìn)行填充回溯編輯pptPattern fillingn用圖像(pattern)填充區(qū)域v Definition of the pattern:v M X N bitmapsv patternij: the value of the position (i,j)編輯pptTwo issues n the relation of the area of the pattern to that of the

12、primitive Relative anchor（相對(duì)錨定） Absolute anchor（絕對(duì)錨定）n write mode Transparent（透明寫） Opaque（不透明寫）編輯pptRelative anchor(相對(duì)錨定）To anchor the pattern at a vertex of the primitive: (x0,y0)valuexy=pattern(x-x0)%M(y-y0)%N(x0,y0)M*N個(gè)像素定義的圖案編輯pptAbsolute anchor （絕對(duì)錨定）M*N個(gè)像素定義的圖案 To consider the entire screen as

13、 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(x,y)編輯pptwrite mode（寫模式）nFilling with a pattern: Adding extra control to the part of the scan-conversion algorithm that a

14、ctually writes each pixelnWrite modenDoing PutPixel with foreground color at a pixel for a 1 in the patternnIn transparent mode（透明寫）: 若圖案為0，則不改變屏幕上該象素的顏色（不做任何處理）；nIn opaque mode（不透明寫）： 若圖案為0，則用背景顏色顯示該象素：編輯pptPattern filling without repeated scan conversionnRectangle writenTo scan convert a primitive

15、 first into a rectangular work area, and then to write each pixel from that bitmap to the appropriate place in the canvas.nBe suitable to characters, icons and application symbols編輯ppt(a) Mountain scene(b) Outline of house icon(d)(e)(g)(c) Brick pattern(f)(d) Bitmap for solid version of house icon.

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

17、輯pptReplicating pixels(1) (線刷子)nUsing more than 1 pixel for each column (or row) during scan conversionThick line drawn by column replicationvPixels are duplicated in column for lines with 1slope1vPixels are duplicated in rows for all other lines編輯ppt原理:假設(shè)直線斜率在-1,+1之間,如圖(a)所示.這時(shí)可把刷子置成垂直方向圖(b).首先將刷子的

18、中點(diǎn)對(duì)準(zhǔn)直線的一個(gè)端點(diǎn),從該點(diǎn)開始,讓刷子中點(diǎn)沿直線的軌跡往直線的另一端點(diǎn)平移即可“刷出”具有一定寬度的直線.如圖(c).m1m2(a)(b)(c)Replicating Pixels(2)編輯ppt缺點(diǎn):(1)線的始末端總是水平或垂直的. (2)線的粗細(xì)不一樣.水平和垂直線最粗,45斜線最 細(xì). (3) 當(dāng)線寬為偶數(shù)個(gè)時(shí),繪制的線條寬度不精確.Disadvantages 編輯ppt 方形刷子是一個(gè)寬度為指定線寬的正方形.將正方形的中心對(duì)準(zhǔn)直線作平移運(yùn)動(dòng)即可. m1The Moving Pen(方形刷子)方形刷子編輯pptThe Moving Pen(方形刷子)Thick line drawn by tracing a rectangular pen.