《計算機(jī)圖形學(xué)教學(xué)資料》第6講-多邊形填充ppt課件

1、Interactive Computer Graphics-交互式計算機(jī)圖形學(xué)本章內(nèi)容v直線的掃描轉(zhuǎn)換v圓與橢圓的掃描轉(zhuǎn)換v區(qū)域填充v二維裁剪v字符生成v反走樣第三節(jié) 區(qū)域填充區(qū)域填充是指：在一個封鎖的二維圖形內(nèi)部象素上著色(紋理、圖案。也稱為：多邊形的掃描轉(zhuǎn)換。本節(jié)內(nèi)容：矩形的掃描轉(zhuǎn)換多邊形區(qū)域填充圖案填充Interactive Computer Graphics-交互式計算機(jī)圖形學(xué)矩形的掃描轉(zhuǎn)換v可利用矩形的簡單性提高掃描轉(zhuǎn)換的效率。minxmaxxminymaxyminxmaxxminymaxy問題：邊境共享邊境像素的繪制？處理：象素中心定位于矩形的左、下邊境時繪制象素點(diǎn)。該規(guī)那么適用于

2、線畫矩形及多邊形以及共享頂點(diǎn)的情形。Interactive Computer Graphics-交互式計算機(jī)圖形學(xué)多邊形填充直線的掃描轉(zhuǎn)換算法填充區(qū)間：區(qū)間端點(diǎn)由掃描線與多邊形邊境限段的交點(diǎn)確定Interactive Computer Graphics-交互式計算機(jī)圖形學(xué)注：多邊形上的區(qū)間 (a) 原始端點(diǎn)由中點(diǎn)算法確定(b) 限制端點(diǎn)在多邊形內(nèi) Interactive Computer Graphics-交互式計算機(jī)圖形學(xué)實(shí)現(xiàn)區(qū)間填充的三個步驟v計算掃描線與多邊形邊境限段的交點(diǎn)v按照x升序陳列交點(diǎn)v填充多邊形內(nèi)交點(diǎn)對之間的一切像素)9 , 2()7 , 7()11,13()5 ,13() 1

3、 , 7()3 , 2(654321PPPPPP?：程度線段如何處置 P 1 P 2 P 4 P 5 P 6 0 2 4 6 8 10 P 3 Interactive Computer Graphics-交互式計算機(jī)圖形學(xué)區(qū)間填充戰(zhàn)略y=8為例：排序后的交點(diǎn)x坐標(biāo)列表為: (2, 4.5, 8.5, 13) P 1 P 2 P 4 P 5 P 6 0 2 4 6 8 10 P 3 如何填充?)9 , 2()7 , 7()11,13()5 ,13() 1 , 7()3 , 2(654321PPPPPPInteractive Computer Graphics-交互式計算機(jī)圖形學(xué)4舍？還是5入?當(dāng)

4、交點(diǎn)的當(dāng)交點(diǎn)的 x 坐標(biāo)值是分?jǐn)?shù)時需進(jìn)展舍入運(yùn)算。坐標(biāo)值是分?jǐn)?shù)時需進(jìn)展舍入運(yùn)算。(b)左端點(diǎn):向上取整v右端點(diǎn):向下取整Interactive Computer Graphics-交互式計算機(jī)圖形學(xué)內(nèi)？或者外?v當(dāng)交點(diǎn)的x 坐標(biāo)值是整數(shù)時，需確定該點(diǎn)是內(nèi)點(diǎn)擬或是外點(diǎn)。(b) 在右邊境:外點(diǎn)v在左邊境:內(nèi)點(diǎn)Interactive Computer Graphics-交互式計算機(jī)圖形學(xué)交點(diǎn)為尖點(diǎn)v交點(diǎn)Pl為尖點(diǎn)時，可計數(shù)為：1，2或者0。如以下圖P0P0P0P0P1P1P1P1P2P2P2P2(a)(b)(c)(d)(a) (b) 計數(shù)為1個交點(diǎn) (c) 計數(shù)為2個交點(diǎn) (d) 計為0個交點(diǎn)規(guī)那么

5、：端點(diǎn)縱坐標(biāo)是ymin 時計數(shù)加1； 端點(diǎn)縱坐標(biāo)是ymax 時不計數(shù) Interactive Computer Graphics-交互式計算機(jī)圖形學(xué)續(xù)：v在詳細(xì)實(shí)現(xiàn)時，對交點(diǎn)的后處置過程可以轉(zhuǎn)化為對邊境限段進(jìn)展的預(yù)處置。Interactive Computer Graphics-交互式計算機(jī)圖形學(xué)掃描線與多邊形邊境限段交點(diǎn)的計算(1)v交點(diǎn)特點(diǎn)：(,),(,)minmaxxyxy12maxminyyy(,)minxy1Y方向坐標(biāo)值滿足:交點(diǎn)界于線段兩端點(diǎn)間:第一個交點(diǎn)是其端點(diǎn)之一，無妨設(shè)為？：后續(xù)交點(diǎn)的計算 取整？！bayx (,)minxy1),(max2yxInteractive Comp

6、uter Graphics-交互式計算機(jī)圖形學(xué)掃描線與多邊形邊境限段交點(diǎn)的計算(2)v記前一掃描線與邊境限段交點(diǎn)為則：),(11iiyxbayxyxiiii ),(滿足bayxyyiiii1111byai) 1(axi的斜率是該邊界線段所在直線其中kka,1當(dāng)前掃描線與該邊境限段有否交點(diǎn)可經(jīng)過其縱坐標(biāo)值確定。記當(dāng)前掃描線與邊境限段交點(diǎn)為 xx的取整需針對邊境限段在多邊形的左右兩側(cè)做不同的處置：左側(cè)邊：向右取整，且當(dāng)交點(diǎn)落在邊境上時視做內(nèi)部點(diǎn)右側(cè)邊：向左取整，且當(dāng)交點(diǎn)落在邊境上時視做外部點(diǎn) xInteractive Computer Graphics-交互式計算機(jī)圖形學(xué)v思索到 ，為消除浮點(diǎn)數(shù)運(yùn)

7、算，v以交點(diǎn)在左側(cè)邊為例，可增設(shè)計數(shù)器Counter，并改寫交點(diǎn)公式為：掃描線與多邊形邊境限段交點(diǎn)的計算(3)xCounterakxxyyxy121maxminyCounterxyCounterxxiiiv下一個交點(diǎn)對應(yīng)計算器的值為：vCounter的初始值可以是：yxyCounterxyxxxxiiii11（隨初始點(diǎn)而定）或者 x0Interactive Computer Graphics-交互式計算機(jī)圖形學(xué)yyCounterxyCounterxii1yCounter 仍以交點(diǎn)在左側(cè)邊為例。1判別Counter的值能否大于02假設(shè)不是，那么直接取為xi；假設(shè)是，那么進(jìn)展如下運(yùn)算：此時，計數(shù)器

8、刷新為： 問題：交點(diǎn)在右側(cè)邊時的處置掃描線與多邊形邊境限段交點(diǎn)的計算(4):向右取整可運(yùn)算如下yCounterxi3上述步驟反復(fù)執(zhí)行k次，直至Counter的值小于0，此時xi+k的值即為交點(diǎn)向右取整的結(jié)果。其截斷部分仍是 。 yCounterInteractive Computer Graphics-交互式計算機(jī)圖形學(xué)活性邊表 AET (active-edge table)y m a x x a N e x t - p o i n t e r 引入如下的數(shù)據(jù)構(gòu)造記錄交點(diǎn)9 2 0 9 2 -5/211 10 3/2 1 1 1 3 0 P6P1P5P6P4P5P3P4Line 9 AETpo

9、inter11 11.5 3/2 11 13 0 P4P5P3P4Line 10 AETpointer引入Counter？9 2 0 9 4.5 -5/211 8.5 3/2 1 1 1 3 0 P6P1P5P6P4P5P3P4Line 8 AETpointer P 1 P 2 P 4 P 5 P 6 0 2 4 6 8 10 P 3 Interactive Computer Graphics-交互式計算機(jī)圖形學(xué)012345678910113 7 -5/25 7 3/2 9 2 0 11 13 0 9 7 -5/211 7 3/2 )9 , 2()7 , 7()11,13()5 ,13() 1

10、 , 7()3 , 2(654321PPPPPP邊表 (ET)的初始化 P 1 P 2 P 4 P 5 P 6 0 2 4 6 8 10 P 3 Interactive Computer Graphics-交互式計算機(jī)圖形學(xué)直線的掃描轉(zhuǎn)換填充算法v生成初始邊表 ET;v把掃描線的y值設(shè)為ET的最小y坐標(biāo);vAET 初始化為空;v循環(huán)直至滿足終止條件: AET 和 ET 為空v從ET 取值(滿足ymin=y的線段)放到AET;v從AET中刪除滿足 y=ymax的線段,然后按照x坐標(biāo)排序;v填充既定區(qū)間;vy 添加 1;v針對新的y值刷新AET中各項(xiàng)的 x 值. Interactive Compu

11、ter Graphics-交互式計算機(jī)圖形學(xué)算法偽代碼Polygongfill(polydef,color)Point polydef;int color; for(各條掃描線i) 建立初始化活性邊表EdgeTablei; i=0; ActiveEdgeList=0；/當(dāng)前掃描線對應(yīng)的活性邊表初始化 for(各條掃描線i) 把EdgeTablei插入ActiveEdgeList中，并排序； 遍歷ActiveEdgeList，把配對交點(diǎn)構(gòu)成半開半閉區(qū)間； 填充各區(qū)間； 從ActiveEdgeList中刪除假交點(diǎn)； 刷新ActiveEdgeList中交點(diǎn)的X坐標(biāo)值； /forInteractive

12、 Computer Graphics-交互式計算機(jī)圖形學(xué)曲線邊境區(qū)域填充運(yùn)用舉例v可用類似方法掃描轉(zhuǎn)換確定出交點(diǎn)實(shí)現(xiàn)曲線邊境區(qū)域的填充，但所需運(yùn)算量顯然比多邊形更大。v例：圓域的活性邊表填充算法。v仍假設(shè)圓心在坐標(biāo)原點(diǎn)；v每條掃描線與圓周有兩個交點(diǎn)，填充兩個交點(diǎn)構(gòu)成的區(qū)間即可；v掃描線與圓周的交點(diǎn)的計算，可利用圓的掃描轉(zhuǎn)換結(jié)果。Interactive Computer Graphics-交互式計算機(jī)圖形學(xué)算法特點(diǎn)v利用了多邊形邊境的銜接性加速與掃描線交點(diǎn)的計算：v算法及數(shù)據(jù)構(gòu)造復(fù)雜v計算效率高v對每個象素只訪問一次，對硬件的訪問量最小，且與設(shè)備無關(guān)。v引入活性邊表構(gòu)造，添加了維持邊表及進(jìn)展交點(diǎn)

13、排序的開銷，不適宜硬件實(shí)現(xiàn)。Interactive Computer Graphics-交互式計算機(jī)圖形學(xué)練習(xí)題-作業(yè)4用多邊形的掃描線算法對如下多邊形進(jìn)展掃描轉(zhuǎn)換。其中多邊形各頂點(diǎn)的坐標(biāo)為p1(5,7)，p2(5,11)，p3(8,13)，p4(12,12) ，p5(12,7)， p6(9,9)求該多邊形的ET表用AEL表表示出多邊 形掃描轉(zhuǎn)換的過程 Interactive Computer Graphics-交互式計算機(jī)圖形學(xué)其它填充算法v邊緣填充算法v種子填充算法：從區(qū)域內(nèi)部一點(diǎn)開場填充直至邊境。v遞歸種子填充算法v掃描線種子填充算法Interactive Computer Graphi

14、cs-交互式計算機(jī)圖形學(xué)邊緣填充算法v條件：已經(jīng)過掃描線與線段求交或?qū)€段進(jìn)展掃描轉(zhuǎn)換得到邊境點(diǎn)。v思緒：利用求余運(yùn)算替代交點(diǎn)排序、配對、構(gòu)造填充區(qū)間。v原理：象素點(diǎn)顏色值經(jīng)過偶數(shù)次求余運(yùn)算后堅(jiān)持不變，經(jīng)過奇數(shù)次求余運(yùn)算后變?yōu)槠渌麛?shù)v算法：v以掃描線為中心的邊緣填充算法v以邊為中心的邊緣填充算法像素求余運(yùn)算Interactive Computer Graphics-交互式計算機(jī)圖形學(xué)以掃描線為中心的邊緣填充算法0 x1x2x3x將當(dāng)前掃描線上的一切象素著上指定顏色的補(bǔ)色I(xiàn)nteractive Computer Graphics-交互式計算機(jī)圖形學(xué)以掃描線為中心的邊緣填充算法0 x1x2x3x向

15、右求余從0)(xa逐個“邊境點(diǎn)向右取余Interactive Computer Graphics-交互式計算機(jī)圖形學(xué)以掃描線為中心的邊緣填充算法0 x1x2x3x向右求余從1)(xb逐個“邊境點(diǎn)向右取余Interactive Computer Graphics-交互式計算機(jī)圖形學(xué)以掃描線為中心的邊緣填充算法0 x1x2x3x向右求余從1)(xb逐個“邊境點(diǎn)向右取余Interactive Computer Graphics-交互式計算機(jī)圖形學(xué)以掃描線為中心的邊緣填充算法0 x1x2x3x向右求余從2)(xc逐個“邊境點(diǎn)向右取余Interactive Computer Graphics-交互式計算

16、機(jī)圖形學(xué)以掃描線為中心的邊緣填充算法0 x1x2x3x向右求余從2)(xc逐個“邊境點(diǎn)向右取余Interactive Computer Graphics-交互式計算機(jī)圖形學(xué)以掃描線為中心的邊緣填充算法0 x1x2x3x向右求余從3)(xd逐個“邊境點(diǎn)向右取余Interactive Computer Graphics-交互式計算機(jī)圖形學(xué)以掃描線為中心的邊緣填充算法0 x1x2x3x向右求余從3)(xd逐個“邊境點(diǎn)向右取余Interactive Computer Graphics-交互式計算機(jī)圖形學(xué)以掃描線為中心的邊緣填充算法對各條掃描線循環(huán)上述處置過程。Interactive Computer

17、Graphics-交互式計算機(jī)圖形學(xué)以邊為中心的邊緣填充算法原始多邊形Interactive Computer Graphics-交互式計算機(jī)圖形學(xué)以邊為中心的邊緣填充算法初始化：將繪圖窗口的背風(fēng)光置為多邊形顏色的補(bǔ)色I(xiàn)nteractive Computer Graphics-交互式計算機(jī)圖形學(xué)以邊為中心的邊緣填充算法對非程度邊上的每個象素點(diǎn)向右求余邊1求余的結(jié)果圖示Interactive Computer Graphics-交互式計算機(jī)圖形學(xué)以邊為中心的邊緣填充算法邊2求余的結(jié)果圖示Interactive Computer Graphics-交互式計算機(jī)圖形學(xué)以邊為中心的邊緣填充算法邊3求余

18、的結(jié)果圖示Interactive Computer Graphics-交互式計算機(jī)圖形學(xué)以邊為中心的邊緣填充算法邊4求余的結(jié)果圖示Interactive Computer Graphics-交互式計算機(jī)圖形學(xué)種子填充算法v原理v 在多邊形內(nèi)部找到一個知的象素點(diǎn)作為種子點(diǎn)，由此開場，利用區(qū)域的連通性找到多邊形內(nèi)部的其它一切象素點(diǎn)進(jìn)展填充。v區(qū)域連通性Interactive Computer Graphics-交互式計算機(jī)圖形學(xué)區(qū)域連通性區(qū)域連通性1v四向連通區(qū)域v 從區(qū)域上任一點(diǎn)出發(fā)，在不超出區(qū)域邊境的前提下，可經(jīng)過4個方向：上、下、左、右的挪動組合到達(dá)區(qū)域中的恣意象素點(diǎn)。允許從4個方向搜索下一

19、個象素的填充算法稱為是四向填充算法Interactive Computer Graphics-交互式計算機(jī)圖形學(xué)區(qū)域連通性2v八向連通區(qū)域v 從區(qū)域上任一點(diǎn)出發(fā)，在不超出區(qū)域邊境的前提下，可經(jīng)過8個方向：上、下、左、右、左上、左下、右上、右下的挪動組合，到達(dá)區(qū)域中的恣意象素。允許從8個方向搜索下一個象素的填充算法稱為是8向填充算法Interactive Computer Graphics-交互式計算機(jī)圖形學(xué)區(qū)域連通性3 實(shí)際上以為，8向填充算法可以填充4向、8向連通區(qū)域，但實(shí)踐上對于4向連通區(qū)域來說，運(yùn)用8向填充算法會擴(kuò)展填充范圍、甚至?xí)?dǎo)致所定義區(qū)域不閉合的問題。Interactive Co

20、mputer Graphics-交互式計算機(jī)圖形學(xué)填充問題描畫v設(shè)填充區(qū)域?yàn)樗南蜻B通區(qū)域。v區(qū)域表示采用邊境表示方法：v 即區(qū)域邊境上一切象素點(diǎn)的值與區(qū)域內(nèi)部象素點(diǎn)的值不同。v 對于有內(nèi)環(huán)的區(qū)域仍可進(jìn)展處置。Interactive Computer Graphics-交互式計算機(jī)圖形學(xué)種子填充算法分類v遞歸填充算法v掃描線算法v改良的掃描線種子填充算法Interactive Computer Graphics-交互式計算機(jī)圖形學(xué)遞歸填充算法v初始化：種子象素入棧v第一步：棧頂象素出棧，作為種子點(diǎn)；v第二步：種子點(diǎn)被置為填充色；v第三步：按照左、上、右、下順序檢查與種子點(diǎn)相鄰的象素：假設(shè)非邊境且

21、未被填充，那么入棧8向連通區(qū)域需思索更多相鄰象素。v假設(shè)棧不空，那么反復(fù)第一步。Interactive Computer Graphics-交互式計算機(jī)圖形學(xué)s125697834象素填充順序表示圖問題：效率低下。Interactive Computer Graphics-交互式計算機(jī)圖形學(xué)掃描線算法掃描線算法v原理：v在每條掃描線上只取一個種子，每次填充該種子所在掃描線上區(qū)域內(nèi)部象素點(diǎn)區(qū)間。v減少程度方向連通性測試次數(shù)v在其相鄰的上、下掃描線上確定出一個新的種子，進(jìn)展如上處置。v減少在垂直方向上連通性測試次數(shù)Interactive Computer Graphics-交互式計算機(jī)圖形學(xué)掃描線種

22、子填充算法流程1v初始化：由指定的種子象素點(diǎn)(x,y)生成種子(y,xl,xr)填充區(qū)間并入棧。v (xl,xr分別為種子點(diǎn)所在掃描線上多邊形內(nèi)部區(qū)間的左、右端點(diǎn))v第一步：假設(shè)種子棧空那么算法終止，否那么棧頂種子出棧v第二步：確定新種子：分別確定y+1,y-1掃描線上與(y,xl,xr)連通的區(qū)間；填充新區(qū)間并將新種子壓入堆棧，v第三步：上述過程循環(huán)執(zhí)行。Interactive Computer Graphics-交互式計算機(jī)圖形學(xué)掃描線種子填充算法流程2思索到區(qū)域可以是凹的或有內(nèi)環(huán)的，所以能夠在該掃描線上出現(xiàn)多個填充區(qū)間，亦即需定義多個種子。yy+1同樣思索到凹或有孔的區(qū)域，需對掃描線y-

23、1進(jìn)展同樣的處置，獲得新的種子。Interactive Computer Graphics-交互式計算機(jī)圖形學(xué)掃描線種子填充算法的改良思緒v算法中的回溯過程并非總是必要的。無需進(jìn)展填充回溯需求進(jìn)展填充回溯Interactive Computer Graphics-交互式計算機(jī)圖形學(xué)Refer to:任繼成，劉慎權(quán)，區(qū)域填充掃描線算法的改良，計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，Vol.10 No.6 1998.改良的掃描線種子填充算法v對棧構(gòu)造進(jìn)展改造記錄種子點(diǎn)所在區(qū)間的左右端點(diǎn)，及掃描順序標(biāo)志v+y：表示沿縱坐標(biāo)添加的方向進(jìn)展逐行掃描；v-y：表示沿縱坐標(biāo)減小的方向進(jìn)展逐行掃描。v實(shí)踐的記錄數(shù)據(jù)分別可

24、以表示為：)1( ,()1(,(yxxyxxrlrl及Interactive Computer Graphics-交互式計算機(jī)圖形學(xué)相關(guān)問題v對于8向連通區(qū)域的填充需思索：當(dāng)象素點(diǎn)x，y為內(nèi)部點(diǎn)時，需調(diào)查象素點(diǎn)x+1，y+1能否是邊境。v圖案填充Interactive Computer Graphics-交互式計算機(jī)圖形學(xué)圖案填充v圖案定義：v可以運(yùn)用一個二維數(shù)組：M X N來記錄vcolorij:表示部分坐標(biāo)系(i,j)處的象素值v涉及問題：v圖案與區(qū)域的定位問題:相對定位，絕對定位v像素著色方式的問題：透明(Transparent)還是不透明(Opaque)Interactive Computer Graphics-交互式計算機(jī)圖形學(xué)圖案定位(1)v圖案在區(qū)域所在的繪圖空間坐標(biāo)系中定位v 此時假設(shè)區(qū)域的位置不