二維填充圖元生成ppt課件

1、第4章 二維填充圖元生成4.1 多邊形的掃描轉(zhuǎn)換4.1.1 概述4.1.2 掃描線算法4.1.3 其它算法4.2 區(qū)域填充4.2.1 簡(jiǎn)單種子填充4.2.2 掃描線種子填充4.3 圖案填充4.4 字符第4章 二維填充圖元生成n二維填充圖元n用顏色或圖案填充一個(gè)二維區(qū)域(由封閉的輪廓線包圍)。n輪廓線通常是多邊形。如果是曲線的話(huà)：n求出邊界像素區(qū)域填充；n可以采用直線段逼近多邊形的掃描轉(zhuǎn)換。第4章 二維填充圖元生成n多邊形的兩種表示方法：n頂點(diǎn)表示多邊形）n用多邊形頂點(diǎn)的序列來(lái)刻劃多邊形。n直觀、幾何意義強(qiáng)、占內(nèi)存少、易于幾何變換；n不能直接用于光柵系統(tǒng)顯示。n點(diǎn)陣表示區(qū)域）n用象素的集合(邊境

2、/內(nèi)部)來(lái)刻畫(huà)多邊形。n失去了許多重要的幾何信息；n便于光柵系統(tǒng)顯示。第4章 二維填充圖元生成n多邊形分類(lèi)：凸多邊形凹多邊形含內(nèi)環(huán)的多邊形第4章 二維填充圖元生成4.1.1 概述多邊形的掃描轉(zhuǎn)換n多邊形的掃描轉(zhuǎn)換：n把多邊形的頂點(diǎn)表示轉(zhuǎn)換為點(diǎn)陣表示。n也就是從多邊形的給定邊界出發(fā)，求出位于其內(nèi)部的各個(gè)象素，并給幀緩沖器內(nèi)對(duì)應(yīng)元素設(shè)置相應(yīng)的灰度，通常稱(chēng)這種轉(zhuǎn)換為多邊形的掃描轉(zhuǎn)換。n方法：n逐點(diǎn)判斷法、掃描線算法、邊緣填充法、柵欄填充法、邊界標(biāo)志法1. 掃描轉(zhuǎn)換矩形n設(shè)矩形的四條邊分另為xmin，xmax，ymin，ymax。n只要填充從ymin到y(tǒng)max的每條掃描線上位于xmin和xmax之間的

3、象素。ymax yminxminxmaxvoid FillRectangle ( Rectangle *rect，int color ) int x，y; for ( y = rect-ymin；y ymax；y+ ) for ( x = rect-xmin；x xmax；x+ ) SetPixel ( x，y，color ); /*end of FillRectangle ()*/1. 掃描轉(zhuǎn)換矩形n矩形也是多邊形，那么為什么要單獨(dú)處理矩形？n掃描轉(zhuǎn)換多邊形的算法復(fù)雜，而矩形的應(yīng)用非常多(窗口)，所以對(duì)其單獨(dú)處理以提高效率。n共享邊界將會(huì)被重繪兩次，如何處理？屬于誰(shuí)？n準(zhǔn)繩：左、下邊的象素屬

4、于矩形，而右、上邊的象素不屬于矩形。n左閉右開(kāi)，下閉上開(kāi)。n邊界像素重繪問(wèn)題；n填充擴(kuò)大化問(wèn)題。1. 掃描轉(zhuǎn)換矩形n考慮填充從BL(x，y)到TRx+5，y+5的矩形。void FillRectangle ( Rectangle *rect，int color ) int x，y; for ( y = rect-ymin；y ymax；y+ ) for ( x = rect-xmin；x xmax；x+ ) SetPixel ( x，y，color ); /*end of FillRectangle ()*/1. 掃描轉(zhuǎn)換矩形BL(x,y)TR(x+5,y+5)Area=6*6 =36 pix

5、elsArea=5*5 =25 pixelsn矩形面積為：n6*636 pixelsn矩形實(shí)際面積應(yīng)為:n(x+5)-x*(y+5)-yn25 pixelsn采用左閉右開(kāi)，下閉上開(kāi)的原則對(duì)邊界象素進(jìn)行處理可保證矩形的面積不被擴(kuò)大。n對(duì)FillRectangle ()進(jìn)行修改。1. 掃描轉(zhuǎn)換矩形n設(shè)矩形的四條邊分另為xmin，xmax，ymin，ymax。ymax yminxminxmaxvoid FillRectangle ( Rectangle *rect，int color ) int x，y; for ( y = rect-ymin；y ymax；y+ ) for ( x = rect-

6、xmin；x xmax；x+ ) SetPixel ( x，y，color ); /*end of FillRectangle ()*/2. 逐點(diǎn)判斷法n它是掃描轉(zhuǎn)換多邊形的最簡(jiǎn)單算法，即逐個(gè)判斷繪圖窗口內(nèi)的象素是否在多邊形內(nèi)部。n如何判斷點(diǎn)在多邊形的內(nèi)外？2. 逐點(diǎn)判斷法n逐點(diǎn)判斷的算法雖然程序簡(jiǎn)單，但不可取。原因是速度太慢。n主要是由于該算法割斷了各象素之間的聯(lián)系，孤立地考察各象素與多邊形的內(nèi)外關(guān)系，使得幾十萬(wàn)甚至幾百萬(wàn)個(gè)象素都要一一判別，每次判別又要多次求交點(diǎn)，花費(fèi)很多時(shí)間。n不適于實(shí)際使用，很少采用。第4章 二維填充圖元生成4.1.2 掃描線算法n掃描線算法是掃描轉(zhuǎn)換多邊形的常用算法，

7、它充分利用了相鄰像素之間的連貫性，避免了逐點(diǎn)判斷和反復(fù)求交計(jì)算，達(dá)到了減少計(jì)算量和提高算法效率的目的。n處理對(duì)象：非自交多邊形 （邊與邊之間除了頂點(diǎn)外無(wú)其它交點(diǎn)）。4.1.2 掃描線算法n開(kāi)發(fā)和利用相鄰象素之間的連貫性是光柵圖形學(xué)算法的重要技巧。n掃描線算法綜合利用了區(qū)域的連貫性、掃描線的連貫性和邊的連貫性等三種形式的連貫性。4.1.2 掃描線算法n區(qū)域的連貫性：相鄰兩條掃描線構(gòu)成一個(gè)水平長(zhǎng)方形區(qū)域，并被多邊形的邊分割為若干梯形一類(lèi)位于多邊形的內(nèi)部；另一類(lèi)在多邊形的外部，且間隔排列）。只需知道該區(qū)域內(nèi)任一梯形中一點(diǎn)關(guān)于多邊形的內(nèi)外關(guān)系，即可確定區(qū)域內(nèi)所有梯形關(guān)于多邊形的內(nèi)外關(guān)系。 n掃描線的連

8、貫性：區(qū)域的連貫性在一條掃描線上的反映；n邊的連貫性：某條邊與當(dāng)前掃描線相交，也可能與下一條掃描線相交?？赏ㄟ^(guò)與當(dāng)前掃描線的交點(diǎn)計(jì)算與下一掃描線的交點(diǎn)(利用斜率)。（區(qū)域的連貫性在相鄰兩掃描線上的反映）y=iXe1Xe2Xe3Xe4Xe8 Xe7y=i+1Xd1Xd2Xd3Xd4Xd8Xd7P0P8P7P1P2P3P4P5P6n根據(jù)掃描線的連貫性可知：一條掃描線與多邊形的交點(diǎn)中，入點(diǎn)和出點(diǎn)之間所有點(diǎn)都是多邊形的內(nèi)部點(diǎn)。n所以，對(duì)所有的掃描線填充入點(diǎn)到出點(diǎn)之間的點(diǎn)就可填充多邊形。n如何具體實(shí)現(xiàn)如何找到入點(diǎn)、出點(diǎn)）？4.1.2 掃描線算法原理02468 10 122468101 234入點(diǎn)出點(diǎn)內(nèi)部

9、點(diǎn)4.1.2 掃描線算法原理n根據(jù)區(qū)域的連貫性，分為3個(gè)步驟：n(1)求出掃描線與多邊形所有邊的交點(diǎn)；n(2)把這些交點(diǎn)按x坐標(biāo)值以升序排列；n(3)對(duì)排序后的交點(diǎn)進(jìn)行奇偶配對(duì)，對(duì)每一對(duì)交點(diǎn)間的區(qū)域進(jìn)行填充。n步驟(3)如上圖：對(duì)y8的掃描線，對(duì)交點(diǎn)序列按x坐標(biāo)升序排序得到的交點(diǎn)序列是(2,4,9,13)，然后對(duì)交點(diǎn)2與4之間、9與13之間的所有象素點(diǎn)進(jìn)行填充。n求交點(diǎn)、排序、配對(duì)、填色02468 10 122468104.1.2 掃描線算法數(shù)據(jù)結(jié)構(gòu)及實(shí)現(xiàn)n算法中采用較靈活的數(shù)據(jù)結(jié)構(gòu)。它由邊分類(lèi)表ETEdge Table和活化邊表AELActive Edge List兩部分組成。y=6，AEL

10、：y=6y=702468 10 12246810P3P2P1P4P5P6e3e4e2e1e5e6e2e59 2 011 13 0 ymaxxxnAEL中每個(gè)對(duì)象需要存放的信息：nymax：邊所交的最高掃描線；nx：當(dāng)前掃描線與邊的交點(diǎn)；nx：從當(dāng)前掃描線到下一條掃描線之間的x增量nnext：指向下一對(duì)象的指針。y=6，AEL：y=7，AEL：y=6y=702468 10 12246810P3P2P1P4P5P6e3e4e2e1e5e6e2e59 2 011 13 0 ymaxxxe2e39 2 09 7 -2.5e4e511 7 1.511 13 0 n邊分類(lèi)表ET （Edge Table）

11、：按掃描線i對(duì)非水平邊進(jìn)行分類(lèi)的指針數(shù)組。下端點(diǎn)的y坐標(biāo)值等于i的邊歸入第i類(lèi)(在該掃描線第一次出現(xiàn)的邊)。同一類(lèi)中，各邊按x值x值相等時(shí)，按x的值遞增的順序排列。有多少條掃描線，就設(shè)多少類(lèi)。02468 10 12246810P3P2P1P4P5P6e3e4e2e1e5e6ymaxxxnET中每個(gè)對(duì)象需要存放的信息：nymax：邊所交的最高掃描線；nx：邊的下端點(diǎn)的x坐標(biāo)；nx：從當(dāng)前掃描線到下一條掃描線之間的x增量(邊的斜率的倒數(shù))；nnext：指向下一對(duì)象的指針。n邊分類(lèi)表ET （Edge Table） ：按掃描線i對(duì)非水平邊進(jìn)行分類(lèi)的指針數(shù)組。下端點(diǎn)的y坐標(biāo)值等于i的邊歸入第i類(lèi)(在該掃

12、描線第一次出現(xiàn)的邊)。同一類(lèi)中，各邊按x值x值相等時(shí)，按x的值遞增的順序排列。有多少條掃描線，就設(shè)多少類(lèi)。e2e5e1e6e3e4ET桶）同一類(lèi)中的邊按x、 x的遞增順序排列02468 10 12246810P3P2P1P4P5P6e3e4e2e1e5e69 7 -2.511 7 1.5 11 13 092 03 7 -2.55 7 1.5 76543210ymaxxx4.1.2 掃描線算法數(shù)據(jù)結(jié)構(gòu)及實(shí)現(xiàn)n算法中采用較靈活的數(shù)據(jù)結(jié)構(gòu)。它由邊分類(lèi)表ETEdge Table和活化邊表AELActive Edge List兩部分組成。nET和AEL中的基本元素稱(chēng)為“邊”（Edge）。n邊的結(jié)構(gòu)“Ed

13、ge由以下四個(gè)域組成：nymax：邊的上端點(diǎn)的y坐標(biāo)；nx：在ET中表示邊的下端點(diǎn)的n x坐標(biāo)；在AEL中則表示邊n 與掃描線的交點(diǎn)的x坐標(biāo)；nx：邊的斜率的倒數(shù)；nnext：指向下一“邊的指針。typedef struct int ymax； float x，deltax； Edge *next； Edge； ymaxxx4.1.2 掃描線算法幾點(diǎn)規(guī)則02468 10 122468104.1.2 掃描線算法幾點(diǎn)規(guī)則n掃描線與多邊形的頂點(diǎn)相交時(shí)，交點(diǎn)的取舍(保證交點(diǎn)正確配對(duì))。n檢查該頂點(diǎn)的兩相鄰邊在掃描線的哪一側(cè)：n只要檢查頂點(diǎn)的兩條邊的另外兩個(gè)端點(diǎn)的Y值，兩個(gè)Y值中大于交點(diǎn)Y值的個(gè)數(shù)是0，

14、1，2，來(lái)決定取0，1，2個(gè)交點(diǎn)。(下閉上開(kāi))(a)P0P2P1P0P2P1P0P2P1P0P2P1(b)(c)(d)y=e4.1.2 掃描線算法算法描述l建立ET，置y為ET中非空桶的最小序號(hào)；l置AEL表為空，且把y桶中ET表的邊加入AEL表中；lwhile AEL表中非空 do beginl 對(duì)AEL表中的x、 x按升序排列；l 按照AEL表中交點(diǎn)前后次序，在每對(duì)奇偶交點(diǎn)間的x段予 以填充；l 計(jì)算下一條掃描線：y=y+1；l if 掃描線 y=ymax then 從AEL表中刪除這些邊；l 對(duì)在AEL表中的其他邊，計(jì)算與下一條掃描線的交點(diǎn)：x=x +xl 按照掃描線y值把ET表中相應(yīng)桶

15、中的邊加入AEL表中；endlend of algorithme2e5e1e6e3e4:ET02468 10 12246810P3P2P1P4P5P6e3e4e2e1e5e69 7 -2.511 7 1.5 11 13 092 03 7 -2.55 7 1.5 76543210AEL=空y=1 AEL=(7，1) (7，1)(4.5，2) (8.5，2)(2，3) (10，3)(2，4) (11.5，4)(2，5) (13，5)(2，6) (13，6)AEL：3 7 -2.55 7 1.5 3 4.5-2.55 8.5 1.5y=2 AEL=9 205 10 1.5y=3 AEL=9 205

16、11.5 1.5y=4 AEL=9 2011 130 y=5 AEL=9 2011 130 y=6 AEL=e2e5e1e6e3e4:ET02468 10 12246810P3P2P1P4P5P6e3e4e2e1e5e69 7 -2.511 7 1.5 11 13 092 03 7 -2.55 7 1.5 76543210y=7 AEL=(2，7) (7，7)(7，7) (13，7)(2，6) (13，6)AEL：9 209 7 -2.511 7 1.511 13 0 9 2011 130 y=6 AEL=y=8 AEL=(2，8) (4.5，8)(8.5，8) (13，8)9 209 4.5

17、-2.511 8.51.511 13 0 y=9 AEL=(10，9) (13，9)11 10 1.511 13 0 e2e5e1e6e3e4:ET02468 10 12246810P3P2P1P4P5P6e3e4e2e1e5e69 7 -2.511 7 1.5 11 13 092 03 7 -2.55 7 1.5 76543210y=10 AEL=(11.5，10) (13，10)AEL：11 11.5 1.5y=9 AEL=(10，9) (13，9)11 10 1.511 13 0 11 13 0 y=11 AEL= 空練習(xí)n寫(xiě)出如圖所示的多邊形的邊分類(lèi)表ET及y=7和y=1對(duì)應(yīng)的活性邊表

18、AEL）024681012246810P1(2,2)e3e4e2e1e5y=1y=7P2(5,1)P3(11,3)P4(11,8)P5(2,7)024681012246810P1(2,2)e3e4e2e1e5y=1y=7P2(5,1)P3(11,3)P4(11,8)P5(2,7)e3e5e1e2e48 298 11 02 5 -33 537654321072 0ymaxxx024681012246810P1(2,2)e3e4e2e1e5y=1y=7P2(5,1)P3(11,3)P4(11,8)P5(2,7)y=7，AET：y=1，AET：e4e38 2 98 11 0 ymaxxxe1e22

19、5 -335 3 4.1.2 掃描線算法幾點(diǎn)規(guī)則02468 10 12246810n交點(diǎn)的取整n利用連貫性計(jì)算出的交點(diǎn)可能導(dǎo)致部分像素位于多邊形之外。n目的：使生成的像素盡量位于多邊形之內(nèi)，并且避免填充擴(kuò)大化。4.1.2 掃描線算法幾點(diǎn)規(guī)則4.1.2 掃描線算法幾點(diǎn)規(guī)則n假定非水平邊與掃描線y=e相交，交點(diǎn)的橫坐標(biāo)為x。若x為小數(shù)，即交點(diǎn)落于掃描線上兩個(gè)相鄰像素之間時(shí)，規(guī)則如下：n(a) 交點(diǎn)位于左邊之上(入點(diǎn))，向右取整；n(b) 交點(diǎn)位于右邊之上(出點(diǎn))，向左取整；y=e(x,e)(a)y=e(x,e)(b)4.1.2 掃描線算法幾點(diǎn)規(guī)則n邊界象素的取舍問(wèn)題，避免填充擴(kuò)大化。n若x為整數(shù)，

20、即交點(diǎn)落于像素點(diǎn)上邊界象素）。n落在右邊界的象素(出點(diǎn))不予填充；n“左閉右開(kāi)”y=e(x,e)(a)y=e(x,e)(b)4.1.2 掃描線算法幾點(diǎn)規(guī)則n1.邊界上的象素: “左閉右開(kāi)” ，將左邊界的點(diǎn)算為內(nèi)部，而將右邊界的點(diǎn)算為外部。n2.頂點(diǎn)：“下閉上開(kāi)”，即丟棄上頂點(diǎn)。n掃描線交于一頂點(diǎn)，共享交點(diǎn)的兩條邊分另處于掃描線的兩邊，這時(shí)交點(diǎn)只取1個(gè)，如掃描線y=3，根據(jù)“下閉上開(kāi)” 準(zhǔn)繩，該點(diǎn)被填充1次。n共享交點(diǎn)的兩條邊處于掃描線的上方，這時(shí)交點(diǎn)取2個(gè)，如掃描線y=1。n共享交點(diǎn)的兩條邊處于掃描線的下方，這時(shí)交點(diǎn)取0個(gè)，如掃描線y=9，無(wú)交點(diǎn)，不填充。02468 10 122468104.

21、1.2 掃描線算法小結(jié)n優(yōu)點(diǎn)：充分利用了區(qū)域的連貫性，算法的效率比逐點(diǎn)填充法高很多。n缺陷：對(duì)各種表的維持和排序開(kāi)銷(xiāo)太大，適合軟件實(shí)現(xiàn)而不適合硬件實(shí)現(xiàn)。n思索：n多邊形的水平邊對(duì)算法有何影響？n上述算法中交點(diǎn)如何實(shí)現(xiàn)所述規(guī)則的取舍？n算法是否能處理自交多邊形？4.1.2 掃描線算法思索ABCDEFGHIJXYn水平邊對(duì)算法有何影響？n水平邊對(duì)算法沒(méi)有影響，可在預(yù)處理階段去除。第4章 二維填充圖元生成4.1.3 其它算法1. 邊緣填充法2. 柵欄填充法3. 邊界標(biāo)志法n求余運(yùn)算：假定A為一個(gè)正整數(shù)(計(jì)算機(jī)中取A為n位能表示的最大整數(shù)。即，A=0 xFFFFFFFF )，則M的余定義為A M, 記

22、為 。n求余可用異或顯示模式實(shí)現(xiàn)：n光柵圖形中，如果某區(qū)域已著上值為M的顏色值，做偶數(shù)次求余運(yùn)算，該區(qū)域顏色不變；而做奇數(shù)次求余運(yùn)算，則該區(qū)域顏色變?yōu)橹禐?的顏色。這一規(guī)律應(yīng)用于多邊形掃描轉(zhuǎn)換，就是邊緣填充算法。n算法基本思想：對(duì)于每條掃描線和每條多邊形邊的交點(diǎn)，將該掃描線上交點(diǎn)右方的所有象素取余。1. 邊緣填充算法MM MAMMXor AMMXor AXor AM1. 邊緣填充算法以邊為中心的算法1. 將繪畫(huà)窗口的背景置為 ；2. 從多邊形的每一條非水平邊上的象素開(kāi)始向右求余。M1. 邊緣填充算法與掃描線算法的比較n適合用于具有幀緩存的圖形系統(tǒng)。n優(yōu)點(diǎn)：n算法簡(jiǎn)單，數(shù)據(jù)結(jié)構(gòu)和程序結(jié)構(gòu)都比掃描

23、線法簡(jiǎn)單。n缺陷：n對(duì)于復(fù)雜圖形，每一象素可能被訪問(wèn)多次，輸入、輸出的量比掃描線填充算法大得多；n要對(duì)幀緩存的大量象素反復(fù)賦值，速度較慢；n并難于用圖案填充。2. 柵欄填充算法n邊緣填充算法的改進(jìn)。引入柵欄，以減少填充算法重復(fù)訪問(wèn)象素的次數(shù)。n柵欄：與掃描線垂直的直線，通常過(guò)一頂點(diǎn)，且把多邊形分為左右二部分。n基本思想：將交點(diǎn)與柵欄之間的象素取余。n減少了象素重復(fù)訪問(wèn)數(shù)目，但不徹底。柵欄3. 邊界標(biāo)志算法n取一個(gè)布爾變量inside來(lái)指示當(dāng)前點(diǎn)的狀態(tài)；Inside 的初始值為假，每當(dāng)當(dāng)前訪問(wèn)象素為被打上邊界標(biāo)志的點(diǎn)，就把inside取反。對(duì)未打標(biāo)志的點(diǎn)，inside不變。n沒(méi)有了求交、排序等運(yùn)

24、算。02468 10 122468103. 邊界標(biāo)志算法n也稱(chēng)輪廓填充算法改進(jìn)的邊緣填充法。n1. 對(duì)多邊形的每一條邊進(jìn)行掃描轉(zhuǎn)換，即對(duì)多邊形邊界所經(jīng)過(guò)的象素作一個(gè)邊界標(biāo)志。n2. 填充：對(duì)每條與多邊形相交的掃描線，按從左到右的順序，逐個(gè)訪問(wèn)該掃描線上的象素。n取一個(gè)布爾變量inside來(lái)指示當(dāng)前點(diǎn)的狀態(tài)：若點(diǎn)在多邊形內(nèi)，則inside為真；若點(diǎn)在多邊形外，則inside為假。nInside 的初始值為假，每當(dāng)當(dāng)前訪問(wèn)象素為被打上邊界標(biāo)志的點(diǎn)，就把inside取反。對(duì)未打標(biāo)志的點(diǎn)，inside不變。3. 邊界標(biāo)志算法n優(yōu)點(diǎn)：對(duì)每個(gè)象素只訪問(wèn)一次。不必建立、維護(hù)ET及AEL等數(shù)據(jù)結(jié)構(gòu)，也沒(méi)有了排

25、序、求交等運(yùn)算，適于硬件實(shí)現(xiàn)。n用軟件實(shí)現(xiàn)時(shí)，掃描線算法與邊界標(biāo)志算法的執(zhí)行速度幾乎相同。n但由于邊界標(biāo)志算法不必建立維護(hù)AEL以及對(duì)它進(jìn)行排序，所以邊界標(biāo)志算法更適合硬件實(shí)現(xiàn)，這時(shí)它的執(zhí)行速度比掃描線算法快一至兩個(gè)數(shù)量級(jí)。第4章 二維填充圖元生成4.1 多邊形的掃描轉(zhuǎn)換4.1.1 概述4.1.2 掃描線算法4.1.3 其它算法4.2 區(qū)域填充4.2.1 簡(jiǎn)單種子填充4.2.2 掃描線種子填充4.3 圖案填充4.4 字符4.2 區(qū)域填充n多邊形的兩種表示方法：n頂點(diǎn)表示多邊形）n用多邊形頂點(diǎn)的序列來(lái)刻劃多邊形。n直觀、幾何意義強(qiáng)、占內(nèi)存少、易于幾何變換；n不能直接用于光柵系統(tǒng)顯示。n點(diǎn)陣表示區(qū)

26、域）n用象素的集合(邊境/內(nèi)部)來(lái)刻畫(huà)多邊形。n失去了許多重要的幾何信息；n便于光柵系統(tǒng)顯示。4.2 區(qū)域填充n區(qū)域可采用兩種表示形式:n內(nèi)點(diǎn)表示n枚舉區(qū)域內(nèi)部的所有像素；n內(nèi)部的所有像素著同一個(gè)顏色；n邊界像素著不同的顏色。n邊界表示n枚舉出邊界上所有的像素；n邊界上的所有像素著同一顏色；n內(nèi)部像素著不同的顏色。邊界點(diǎn)內(nèi) 點(diǎn)4.2 區(qū)域填充n區(qū)域填充n先將區(qū)域內(nèi)的一點(diǎn)賦予指定的顏色，然后將該顏色擴(kuò)展到整個(gè)區(qū)域的過(guò)程。n簡(jiǎn)單種子算法n掃描線種子算法n要求區(qū)域是“連通的。邊界點(diǎn)內(nèi) 點(diǎn)4.2 區(qū)域填充n區(qū)域填充要求區(qū)域是連通的n連通性：n4連通：n 從區(qū)域內(nèi)任意一點(diǎn)出發(fā)，可通過(guò)上、下、左、右四個(gè)方

27、向到達(dá)區(qū)域內(nèi)的任意象素；n8連通：n 從區(qū)域內(nèi)任意一點(diǎn)出發(fā)，可通過(guò)上、下、左、右、左上、左下、右上、右下八個(gè)方向到達(dá)區(qū)域內(nèi)的任意象素；第4章 二維填充圖元生成4.1 多邊形的掃描轉(zhuǎn)換4.1.1 概述4.1.2 掃描線算法4.1.3 其它算法4.2 區(qū)域填充4.2.1 簡(jiǎn)單種子填充4.2.2 掃描線種子填充4.3 圖案填充4.4 字符4.2.1 簡(jiǎn)單種子填充算法n設(shè)G為一內(nèi)點(diǎn)表示的區(qū)域，(x,y)為區(qū)域內(nèi)一點(diǎn)，old_color為G的原色?，F(xiàn)取(x,y)為種子點(diǎn)對(duì)區(qū)域G進(jìn)行填充：即先置像素(x,y)的顏色為new_color，然后逐步將整個(gè)區(qū)域G都置為同樣的顏色。 步驟如下：種子象素入棧，當(dāng)棧非

28、空時(shí)，執(zhí)行如下三步操作：（1棧頂象素出棧；（2將出棧象素置成new_color ；（3按左、上、右、下的順序檢查與出棧象素相鄰的四個(gè)象素，若其中某個(gè)象素為old_color，則把該象素作為新的種子入棧。4.2.1 簡(jiǎn)單種子填充算法/*內(nèi)點(diǎn)表示的4連通區(qū)域*/void FloodFill4(int x,int y,int oldColor,int newColor) if(GetPixel(x,y) = oldColor) SetPixel(x,y,newColor); FloodFill4(x-1,y,oldColor,newColor);FloodFill4(x,y+1,oldColor,n

29、ewColor);FloodFill4(x+1,y,oldColor,newColor); FloodFill4(x,y-1,oldColor,newColor);/*end of FloodFill4()*/ 種子填充算法-邊界表示區(qū)域0 1 2 3 4 54321(3,2)(2,2)(3,3)(4,2)(3,1)(2,1)(4,1)(4,2)(2,2)(1,2)(2,3)(3,3)155(1,6)(6,6)(8,4)(8,1)(1,1)S (4,3)設(shè)種子象素為S(4,3)，按左、上、右、下檢查出棧象素四個(gè)相鄰的象素，寫(xiě)出各象素入棧及出棧順序。入棧順序： (4,3) (3,3),(4,4)

30、,(5,3),(4,2) (3,2),(5,2) (5,3),(6,2) .出棧填色順序:(4,3)(4,2)(5,2)(6,2).棧內(nèi)象素: (3,3),(4,4), (5,3),(3,2), (5,3)4.2.1 簡(jiǎn)單種子填充算法/*邊界表示的4連通區(qū)域*/void BoundaryFill4(int x,int y,int boundaryColor,int newColor) int color;color = GetPixel(x,y);if(color != boundaryColor) & (color != newColor)SetPixel(x,y,newColor)

31、;BoundaryFill4(x,y+1,oldColor,newColor);BoundaryFill4(x,y-1,oldColor,newColor);BoundaryFill4(x-1,y,oldColor,newColor);BoundaryFill4(x+1,y,oldColor,newColor);/*end of BoundaryFill4()*/ S4.2.1 簡(jiǎn)單種子填充算法n采用4向填充算法能否填充此8向連通區(qū)域？n8連通區(qū)域的填充：n將搜索方向改為8向。n可填充8連通區(qū)域和4連通區(qū)域？4.2.1 簡(jiǎn)單種子填充算法n該算法也可以填充有孔區(qū)域。 n優(yōu)點(diǎn)：n算法簡(jiǎn)單n缺陷：n

32、遞歸執(zhí)行，效率不高，要求很大的存儲(chǔ)空間來(lái)實(shí)現(xiàn)堆棧。費(fèi)時(shí)費(fèi)內(nèi)存。n改良：n減少遞歸次數(shù)，提高效率。n掃描線種子填充算法第4章 二維填充圖元生成4.1 多邊形的掃描轉(zhuǎn)換4.1.1 概述4.1.2 掃描線算法4.1.3 其它算法4.2 區(qū)域填充4.2.1 簡(jiǎn)單種子填充4.2.2 掃描線種子填充4.3 圖案填充4.4 字符4.2.2 掃描線種子算法原理n原理：基于種子填充算法的思想，利用掃描線的連貫性，減少遞歸層次。n基本過(guò)程：n當(dāng)給定種子點(diǎn)時(shí)，首先填充種子點(diǎn)所在的掃描線上的位于給定區(qū)域的一個(gè)區(qū)段；n然后確定與這一區(qū)段相通的上下兩條掃描線上位于給定區(qū)域內(nèi)的區(qū)段，并依次保存下來(lái)。n反復(fù)這個(gè)過(guò)程，直到填充

33、結(jié)束。4.2.2 掃描線種子算法算法描述l將種子象素壓入堆棧lwhile 堆棧非空 do beginl 從堆棧中彈出一個(gè)種子象素；l 沿著掃描線對(duì)種子象素的左右象素進(jìn)行填充，直至遇 到邊界象素為止；l 標(biāo)志區(qū)間內(nèi)最左和最右象素為xleft 和xright；l if在xleftxxright中檢查與當(dāng)前掃描線相鄰的上下兩 條掃描線全為邊界象素或全為已填充過(guò)的象素 then goto 2；l 在xleftxxright中標(biāo)記每一個(gè)既不包含邊界象素又不 包含已填充過(guò)的象素的區(qū)間；l 將每一區(qū)間的最右象素作為種子象素壓入堆棧；endlend of algorithm4.2.2 掃描線種子算法算法示例n

34、執(zhí)行掃描線種子法的過(guò)程如圖所示，是種子象素點(diǎn)S。開(kāi)始時(shí)，堆棧只有一個(gè)種子象素S，先填充S所在的區(qū)段，然后將其上下掃描線未填充的各區(qū)段的最右象素1，2，3作為種子象素壓入堆棧，再?gòu)亩褩Ｖ腥〕龇N子象素3，填充該區(qū)段，并將下一條掃描線未填充的區(qū)段的最右象素4壓入堆棧，重復(fù)執(zhí)行，直至堆棧為空時(shí)結(jié)束，整個(gè)區(qū)域填充完畢。S1231241251261278910127812781271121712121211278113456910124.2.2 掃描線種子算法n上述算法對(duì)于每一個(gè)待填充區(qū)段，只需壓棧一次；因此，掃描線種子填充算法提高了區(qū)域填充的效率。多邊形掃描轉(zhuǎn)換與區(qū)域填充n聯(lián)絡(luò)：都是光柵圖形的多邊形面著

35、色?？上嗷マD(zhuǎn)換：n當(dāng)用直線的掃描轉(zhuǎn)換算法將多邊形的邊界像素求出，并給定多邊形內(nèi)一點(diǎn)為種子點(diǎn)時(shí)，則多邊形的掃描轉(zhuǎn)換轉(zhuǎn)化為區(qū)域填充。n若已知給定區(qū)域?yàn)槎噙呅?，可求出其頂點(diǎn)坐標(biāo)，則區(qū)域填充轉(zhuǎn)化為多邊形的掃描轉(zhuǎn)換。多邊形掃描轉(zhuǎn)換與區(qū)域填充n區(qū)別：n基本思想不同n前者：將多邊形的頂點(diǎn)表示轉(zhuǎn)換成點(diǎn)陣表示，n后者：只改變區(qū)域的填充顏色，沒(méi)有改變表示方法。n對(duì)邊界的要求不同n前者：只要求掃描線與多邊形邊界交點(diǎn)個(gè)數(shù)為偶數(shù)。邊界可以不封閉例如對(duì)水平邊的預(yù)處理）。n后者：區(qū)域封閉，防止遞歸填充跨界。n基于的條件不同n前者：從邊界頂點(diǎn)信息出發(fā)。n后者：區(qū)域內(nèi)種子點(diǎn)。第4章 二維填充圖元生成4.1 多邊形的掃描轉(zhuǎn)換4.1.1 概述4.1.2 掃描線算法4.1.3 其它算法4.2 區(qū)域填充4.2.1 簡(jiǎn)單種子填充4.2.2 掃描線種子填充4.3 圖案填充4.4 字符4.3 圖案填充n基本問(wèn)題n關(guān)鍵是建立區(qū)域與圖像間的對(duì)應(yīng)關(guān)系。n方法1：建立整個(gè)繪圖空間(xoy)與圖像空間(uov)的1-1映射。（遨游）xyo旋轉(zhuǎn)區(qū)域oxy填充區(qū)域uov圖像紋理）2.7 以圖像