二維填充圖元生成

1、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 字符,2,第4章 二維填充圖元生成,二維填充圖元用顏色或圖案填充一個(gè)二維區(qū)域(由封閉的輪廓線包圍)。輪廓線通常是多邊形。如果是曲線的話：求出邊界像素→區(qū)域填充；可以采用直線段逼近→多邊形的掃描轉(zhuǎn)換。,

2、,,3,第4章 二維填充圖元生成,多邊形的兩種表示方法：,頂點(diǎn)表示（多邊形）用多邊形頂點(diǎn)的序列來刻劃多邊形。直觀、幾何意義強(qiáng)、占內(nèi)存少、易于幾何變換；不能直接用于光柵系統(tǒng)顯示。,點(diǎn)陣表示（區(qū)域）用象素的集合(邊界/內(nèi)部)來刻畫多邊形。失去了許多重要的幾何信息；便于光柵系統(tǒng)顯示。,4,第4章 二維填充圖元生成,多邊形分類：,5,第4章 二維填充圖元生成,4.1 多邊形的掃描轉(zhuǎn)換4.1.1 概述4.1.2 掃描線算法4

3、.1.3 其它算法4.2 區(qū)域填充4.2.1 簡(jiǎn)單種子填充4.2.2 掃描線種子填充4.3 圖案填充4.4 字符,6,4.1.1 概述－多邊形的掃描轉(zhuǎn)換,多邊形的掃描轉(zhuǎn)換：把多邊形的頂點(diǎn)表示轉(zhuǎn)換為點(diǎn)陣表示。也就是從多邊形的給定邊界出發(fā)，求出位于其內(nèi)部的各個(gè)象素，并給幀緩沖器內(nèi)對(duì)應(yīng)元素設(shè)置相應(yīng)的灰度，通常稱這種轉(zhuǎn)換為多邊形的掃描轉(zhuǎn)換。方法：逐點(diǎn)判斷法、掃描線算法、邊緣填充法、柵欄填充法、邊界標(biāo)志法…,7,1. 掃描轉(zhuǎn)換

4、矩形,設(shè)矩形的四條邊分另為xmin，xmax，ymin，ymax。只要填充從ymin到y(tǒng)max的每條掃描線上位于xmin和xmax之間的象素。,void FillRectangle ( Rectangle *rect，int color ){ int x，y; for ( y = rect->ymin；y ymax；y++ ) for ( x = rect->xmin；x xmax；x+

5、+ ) SetPixel ( x，y，color );} /*end of FillRectangle ()*/,8,1. 掃描轉(zhuǎn)換矩形,矩形也是多邊形，那么為什么要單獨(dú)處理矩形？掃描轉(zhuǎn)換多邊形的算法復(fù)雜，而矩形的應(yīng)用非常多(窗口)，所以對(duì)其單獨(dú)處理以提高效率。共享邊界將會(huì)被重繪兩次，如何處理？,原則：左、下邊的象素屬于矩形，而右、上邊的象素不屬于矩形。左閉右開，下閉上開。邊界像素重繪問題；填充擴(kuò)大

6、化問題。,9,1. 掃描轉(zhuǎn)換矩形,考慮填充從BL(x，y)到TR（x+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 (

7、x，y，color );} /*end of FillRectangle ()*/,10,1. 掃描轉(zhuǎn)換矩形,Area=6*6 =36 pixels,Area=5*5 =25 pixels,矩形面積為：6*6＝36 pixels矩形實(shí)際面積應(yīng)為:[(x+5)-x]*[(y+5)-y]＝25 pixels采用左閉右開，下閉上開的原則對(duì)邊界象素進(jìn)行處理可保證矩形的面積不被擴(kuò)大。對(duì)FillRect

8、angle ()進(jìn)行修改。,,11,1. 掃描轉(zhuǎn)換矩形,設(shè)矩形的四條邊分另為xmin，xmax，ymin，ymax。,void FillRectangle ( Rectangle *rect，int color ){ int x，y; for ( y = rect->ymin；y ymax；y++ ) for ( x = rect->xmin；x xmax；x++ )

9、 SetPixel ( x，y，color );} /*end of FillRectangle ()*/,12,2. 逐點(diǎn)判斷法,它是掃描轉(zhuǎn)換多邊形的最簡(jiǎn)單算法，即逐個(gè)判斷繪圖窗口內(nèi)的象素是否在多邊形內(nèi)部。如何判斷點(diǎn)在多邊形的內(nèi)外？,,,,,13,2. 逐點(diǎn)判斷法,逐點(diǎn)判斷的算法雖然程序簡(jiǎn)單，但不可取。原因是速度太慢。主要是由于該算法割斷了各象素之間的聯(lián)系，孤立地考察各象素與多邊形的內(nèi)外關(guān)系，使得幾十萬甚至幾百萬個(gè)象素都要一

10、一判別，每次判別又要多次求交點(diǎn)，花費(fèi)很多時(shí)間。不適于實(shí)際使用，很少采用。,14,第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 字符,15,4.1.2 掃描線算法,掃描線算法是掃描轉(zhuǎn)換多邊形的常用算法，它充分利用了相鄰像素之間的連貫性，避免了逐點(diǎn)判斷和反復(fù)求交計(jì)算，

11、達(dá)到了減少計(jì)算量和提高算法效率的目的。處理對(duì)象：非自交多邊形 （邊與邊之間除了頂點(diǎn)外無其它交點(diǎn)）。,16,4.1.2 掃描線算法,開發(fā)和利用相鄰象素之間的連貫性是光柵圖形學(xué)算法的重要技巧。掃描線算法綜合利用了區(qū)域的連貫性、掃描線的連貫性和邊的連貫性等三種形式的連貫性。,17,4.1.2 掃描線算法,區(qū)域的連貫性：相鄰兩條掃描線構(gòu)成一個(gè)水平長(zhǎng)方形區(qū)域，并被多邊形的邊分割為若干梯形（一類位于多邊形的內(nèi)部；另一類在多邊形的外部，且間隔排列

12、）。只需知道該區(qū)域內(nèi)任一梯形中一點(diǎn)關(guān)于多邊形的內(nèi)外關(guān)系，即可確定區(qū)域內(nèi)所有梯形關(guān)于多邊形的內(nèi)外關(guān)系。 掃描線的連貫性：區(qū)域的連貫性在一條掃描線上的反映；邊的連貫性：某條邊與當(dāng)前掃描線相交，也可能與下一條掃描線相交?？赏ㄟ^與當(dāng)前掃描線的交點(diǎn)計(jì)算與下一掃描線的交點(diǎn)(利用斜率)。（區(qū)域的連貫性在相鄰兩掃描線上的反映）,18,根據(jù)掃描線的連貫性可知：一條掃描線與多邊形的交點(diǎn)中，入點(diǎn)和出點(diǎn)之間所有點(diǎn)都是多邊形的內(nèi)部點(diǎn)。所以，對(duì)所有的掃描線填

13、充入點(diǎn)到出點(diǎn)之間的點(diǎn)就可填充多邊形。如何具體實(shí)現(xiàn)（如何找到入點(diǎn)、出點(diǎn)）？,4.1.2 掃描線算法－原理,19,4.1.2 掃描線算法－原理,根據(jù)區(qū)域的連貫性，分為3個(gè)步驟：(1)求出掃描線與多邊形所有邊的交點(diǎn)；(2)把這些交點(diǎn)按x坐標(biāo)值以升序排列；(3)對(duì)排序后的交點(diǎn)進(jìn)行奇偶配對(duì)，對(duì)每一對(duì)交點(diǎn)間的區(qū)域進(jìn)行填充。,步驟(3)如上圖：對(duì)y＝8的掃描線，對(duì)交點(diǎn)序列按x坐標(biāo)升序排序得到的交點(diǎn)序列是(2,4,9,13)，然后對(duì)交點(diǎn)2與4之

14、間、9與13之間的所有象素點(diǎn)進(jìn)行填充。求交點(diǎn)、排序、配對(duì)、填色,20,4.1.2 掃描線算法－數(shù)據(jù)結(jié)構(gòu)及實(shí)現(xiàn),算法中采用較靈活的數(shù)據(jù)結(jié)構(gòu)。它由邊分類表ET（Edge Table）和活化邊表AEL（Active Edge List）兩部分組成。,求交點(diǎn)、排序、配對(duì)、填色利用鏈表：與當(dāng)前掃描線相交的邊稱為活化邊(Active Edge)，把它們按與掃描線交點(diǎn)x坐標(biāo)遞增的順序存入一個(gè)鏈表中，稱為活化邊表AEL (AEL， Active E

15、dge List)。它記錄了多邊形邊沿掃描線的交點(diǎn)序列。,y=6，AEL：,,e2,e5,AEL中每個(gè)對(duì)象需要存放的信息：ymax：邊所交的最高掃描線；x：當(dāng)前掃描線與邊的交點(diǎn)；Δx：從當(dāng)前掃描線到下一條掃描線之間的x增量next：指向下一對(duì)象的指針。,,活化邊表AEL,求交、排序、配對(duì)、填色隨掃描線的遞增如何更新AEL？邊的加入、刪除，交點(diǎn)的更新。,y=6，AEL：,y=7，AEL：,,,e2,e5,,e2,e3,e4,e

16、5,,建立一個(gè)新的數(shù)據(jù)結(jié)構(gòu)：邊分類表ET,活化邊表AEL,邊分類表ET （Edge Table） ：按掃描線i對(duì)非水平邊進(jìn)行分類的指針數(shù)組。下端點(diǎn)的y坐標(biāo)值等于i的邊歸入第i類(在該掃描線第一次出現(xiàn)的邊)。同一類中，各邊按x值（x值相等時(shí)，按Δx的值）遞增的順序排列。有多少條掃描線，就設(shè)多少類。,ET中每個(gè)對(duì)象需要存放的信息：ymax：邊所交的最高掃描線；x：邊的下端點(diǎn)的x坐標(biāo)；Δx：從當(dāng)前掃描線到下一條掃描線之間的x增量(邊的

17、斜率的倒數(shù))；next：指向下一對(duì)象的指針。,邊分類表ET （Edge Table） ：按掃描線i對(duì)非水平邊進(jìn)行分類的指針數(shù)組。下端點(diǎn)的y坐標(biāo)值等于i的邊歸入第i類(在該掃描線第一次出現(xiàn)的邊)。同一類中，各邊按x值（x值相等時(shí)，按Δx的值）遞增的順序排列。有多少條掃描線，就設(shè)多少類。,e2,e5,,,,,,,e1,e6,e3,e4,ET（桶）,同一類中的邊按x、 Δx的遞增順序排列,25,4.1.2 掃描線算法－數(shù)據(jù)結(jié)構(gòu)及實(shí)現(xiàn),算法中

18、采用較靈活的數(shù)據(jù)結(jié)構(gòu)。它由邊分類表ET（Edge Table）和活化邊表AEL（Active Edge List）兩部分組成。ET和AEL中的基本元素稱為“邊”（Edge）。邊的結(jié)構(gòu)“Edge”由以下四個(gè)域組成：ymax：邊的上端點(diǎn)的y坐標(biāo)；x：在ET中表示邊的下端點(diǎn)的 x坐標(biāo)；在AEL中則表示邊 與掃描線的交點(diǎn)的x坐標(biāo)；Δx：邊的斜率的倒數(shù)；next：指向下一“邊”的指針。,typedef struc

19、t { int ymax； float x，deltax； Edge *next； }Edge；,26,4.1.2 掃描線算法－幾點(diǎn)規(guī)則,求交點(diǎn)、排序、配對(duì)、填色交點(diǎn)與多邊形頂點(diǎn)重合時(shí)，會(huì)導(dǎo)致“配對(duì)”失敗，如何處理？下閉上開,,,27,4.1.2 掃描線算法－幾點(diǎn)規(guī)則,掃描線與多邊形的頂點(diǎn)相交時(shí)，交點(diǎn)的取舍(保證交點(diǎn)正確配對(duì))。檢查該頂點(diǎn)的兩相鄰邊在掃描線的哪一側(cè)：只要檢查頂點(diǎn)的兩條邊的另外兩個(gè)端點(diǎn)

20、的Y值，兩個(gè)Y值中大于交點(diǎn)Y值的個(gè)數(shù)是0，1，2，來決定取0，1，2個(gè)交點(diǎn)。(下閉上開),28,4.1.2 掃描線算法－算法描述,建立ET，置y為ET中非空桶的最小序號(hào)；置AEL表為空，且把y桶中ET表的邊加入AEL表中；while AEL表中非空 do     begin 對(duì)AEL表中的x、 Δx按升序排列；    

21、按照AEL表中交點(diǎn)前后次序，在每對(duì)奇偶交點(diǎn)間的x段予 以填充；  計(jì)算下一條掃描線：y=y+1； if 掃描線 y=ymax  then 從AEL表中刪除這些邊；     對(duì)在AEL表中的其他邊，計(jì)算與下一條掃描線的交點(diǎn)：x=x +Δx      按照掃描線y值把ET表中相應(yīng)桶中的邊加入

22、AEL表中；endend of algorithm,e2,e5,,,,,,,e1,e6,e3,e4,:ET,AEL=空,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：,,,y=2 AEL=,,y=3 AEL=,,y=4 AEL=,,y=5 AEL=,,y=6 AEL=,算法示例,

23、e2,e5,,,,,,,e1,e6,e3,e4,:ET,y=7 AEL=,(2，7) →(7，7),(7，7) →(13，7),(2，6) →(13，6),AEL：,,,,y=6 AEL=,,,y=8 AEL=,(2，8) →(4.5，8),(8.5，8) →(13，8),,,,,y=9 AEL=,(10，9) →(13，9),,算法示例,e2,e5,,,,,,,e1,e6,e3,e4,:ET,y=10 AEL=,(11.5，10) →

24、(13，10),AEL：,,y=9 AEL=,(10，9) →(13，9),,y=11 AEL= 空,算法示例,32,練習(xí),寫出如圖所示的多邊形的邊分類表（ET）及y=7和y=1對(duì)應(yīng)的活性邊表（AEL）,e3,e5,,,,,e1,e2,e4,,,y=7，AET：,y=1，AET：,,e4,e3,,e1,e2,35,4.1.2 掃描線算法－幾點(diǎn)規(guī)則,求交點(diǎn)、排序、配對(duì)、填色還需解決的問題：交點(diǎn)x坐標(biāo)可能是小數(shù)，如何取整？填充擴(kuò)大化的

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

26、取整；,38,4.1.2 掃描線算法－幾點(diǎn)規(guī)則,邊界象素的取舍問題，避免填充擴(kuò)大化。若x為整數(shù)，即交點(diǎn)落于像素點(diǎn)上（邊界象素）。落在右邊界的象素(出點(diǎn))不予填充；“左閉右開”,39,4.1.2 掃描線算法－幾點(diǎn)規(guī)則,1.邊界上的象素: “左閉右開” ，將左邊界的點(diǎn)算為內(nèi)部，而將右邊界的點(diǎn)算為外部。2.頂點(diǎn)：“下閉上開”，即丟棄上頂點(diǎn)。,掃描線交于一頂點(diǎn)，共享交點(diǎn)的兩條邊分另處于掃描線的兩邊，這時(shí)交點(diǎn)只取1個(gè)，如掃描線y=3，根據(jù)

27、“下閉上開” 原則，該點(diǎn)被填充1次。,共享交點(diǎn)的兩條邊處于掃描線的上方，這時(shí)交點(diǎn)取2個(gè)，如掃描線y=1。,共享交點(diǎn)的兩條邊處于掃描線的下方，這時(shí)交點(diǎn)取0個(gè)，如掃描線y=9，無交點(diǎn)，不填充。,,40,4.1.2 掃描線算法－小結(jié),優(yōu)點(diǎn)：充分利用了區(qū)域的連貫性，算法的效率比逐點(diǎn)填充法高很多。缺點(diǎn)：對(duì)各種表的維持和排序開銷太大，適合軟件實(shí)現(xiàn)而不適合硬件實(shí)現(xiàn)。思考：多邊形的水平邊對(duì)算法有何影響？上述算法中交點(diǎn)如何實(shí)現(xiàn)所述規(guī)則的取舍？算

28、法是否能處理自交多邊形？,41,4.1.2 掃描線算法－思考,水平邊對(duì)算法有何影響？水平邊對(duì)算法沒有影響，可在預(yù)處理階段去除。,42,第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 字符,43,4.1.3 其它算法,1. 邊緣填充法2. 柵欄填充法3. 邊界標(biāo)

29、志法,44,求余運(yùn)算：假定A為一個(gè)正整數(shù)(計(jì)算機(jī)中取A為n位能表示的最大整數(shù)。即，A=0xFFFFFFFF )，則M的余定義為A – M, 記為 。求余可用異或顯示模式實(shí)現(xiàn)：光柵圖形中，如果某區(qū)域已著上值為M的顏色值，做偶數(shù)次求余運(yùn)算，該區(qū)域顏色不變；而做奇數(shù)次求余運(yùn)算，則該區(qū)域顏色變?yōu)橹禐?的顏色。這一規(guī)律應(yīng)用于多邊形掃描轉(zhuǎn)換，就是邊緣填充算法。算法基本思想：對(duì)于每條掃描線和每條多邊形邊的交點(diǎn)，將該掃描線上交點(diǎn)

30、右方的所有象素取余。,1. 邊緣填充算法,45,1. 邊緣填充算法－以邊為中心的算法,1. 將繪畫窗口的背景置為 ；2. 從多邊形的每一條非水平邊上的象素開始向右求余。,46,1. 邊緣填充算法－與掃描線算法的比較,適合用于具有幀緩存的圖形系統(tǒng)。優(yōu)點(diǎn)：算法簡(jiǎn)單，數(shù)據(jù)結(jié)構(gòu)和程序結(jié)構(gòu)都比掃描線法簡(jiǎn)單。缺點(diǎn)：對(duì)于復(fù)雜圖形，每一象素可能被訪問多次，輸入、輸出的量比掃描線填充算法大得多；要對(duì)幀緩存的大量象素反復(fù)賦值，速度較慢；

31、并難于用圖案填充。,47,2. 柵欄填充算法,邊緣填充算法的改進(jìn)。引入柵欄，以減少填充算法重復(fù)訪問象素的次數(shù)。柵欄：與掃描線垂直的直線，通常過一頂點(diǎn)，且把多邊形分為左右二部分?；舅枷耄簩⒔稽c(diǎn)與柵欄之間的象素取余。減少了象素重復(fù)訪問數(shù)目，但不徹底。,48,3. 邊界標(biāo)志算法,取一個(gè)布爾變量inside來指示當(dāng)前點(diǎn)的狀態(tài)；Inside 的初始值為假，每當(dāng)當(dāng)前訪問象素為被打上邊界標(biāo)志的點(diǎn)，就把inside取反。對(duì)未打標(biāo)志的點(diǎn)，insi

32、de不變。沒有了求交、排序等運(yùn)算。,,,,,,,,,,,,,,,,,49,3. 邊界標(biāo)志算法,也稱輪廓填充算法－改進(jìn)的邊緣填充法。1. 對(duì)多邊形的每一條邊進(jìn)行掃描轉(zhuǎn)換，即對(duì)多邊形邊界所經(jīng)過的象素作一個(gè)邊界標(biāo)志。2. 填充：對(duì)每條與多邊形相交的掃描線，按從左到右的順序，逐個(gè)訪問該掃描線上的象素。取一個(gè)布爾變量inside來指示當(dāng)前點(diǎn)的狀態(tài)：若點(diǎn)在多邊形內(nèi)，則inside為真；若點(diǎn)在多邊形外，則inside為假。Ins

33、ide 的初始值為假，每當(dāng)當(dāng)前訪問象素為被打上邊界標(biāo)志的點(diǎn)，就把inside取反。對(duì)未打標(biāo)志的點(diǎn)，inside不變。,50,3. 邊界標(biāo)志算法,優(yōu)點(diǎn)：對(duì)每個(gè)象素只訪問一次。不必建立、維護(hù)ET及AEL等數(shù)據(jù)結(jié)構(gòu)，也沒有了排序、求交等運(yùn)算，適于硬件實(shí)現(xiàn)。用軟件實(shí)現(xiàn)時(shí)，掃描線算法與邊界標(biāo)志算法的執(zhí)行速度幾乎相同。但由于邊界標(biāo)志算法不必建立維護(hù)AEL以及對(duì)它進(jìn)行排序，所以邊界標(biāo)志算法更適合硬件實(shí)現(xiàn)，這時(shí)它的執(zhí)行速度比掃描線算法快一至兩個(gè)數(shù)量

34、級(jí)。,51,第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 字符,52,4.2 區(qū)域填充,多邊形的兩種表示方法：,頂點(diǎn)表示（多邊形）用多邊形頂點(diǎn)的序列來刻劃多邊形。直觀、幾何意義強(qiáng)、占內(nèi)存少、易于幾何變換；不能直接用于光柵系統(tǒng)顯示。,點(diǎn)陣表示（區(qū)域）用象素的集

35、合(邊界/內(nèi)部)來刻畫多邊形。失去了許多重要的幾何信息；便于光柵系統(tǒng)顯示。,53,4.2 區(qū)域填充,區(qū)域可采用兩種表示形式:內(nèi)點(diǎn)表示枚舉區(qū)域內(nèi)部的所有像素；內(nèi)部的所有像素著同一個(gè)顏色；邊界像素著不同的顏色。邊界表示枚舉出邊界上所有的像素；邊界上的所有像素著同一顏色；內(nèi)部像素著不同的顏色。,54,4.2 區(qū)域填充,區(qū)域填充先將區(qū)域內(nèi)的一點(diǎn)賦予指定的顏色，然后將該顏色擴(kuò)展到整個(gè)區(qū)域的過程。簡(jiǎn)單種子算法掃描線種子算

36、法要求區(qū)域是“連通”的。,55,4.2 區(qū)域填充,區(qū)域填充要求區(qū)域是連通的連通性：4連通： 從區(qū)域內(nèi)任意一點(diǎn)出發(fā)，可通過上、下、左、右四個(gè)方向到達(dá)區(qū)域內(nèi)的任意象素；8連通： 從區(qū)域內(nèi)任意一點(diǎn)出發(fā)，可通過上、下、左、右、左上、左下、右上、右下八個(gè)方向到達(dá)區(qū)域內(nèi)的任意象素；,,56,第4章 二維填充圖元生成,4.1 多邊形的掃描轉(zhuǎn)換4.1.1 概述4.1.2 掃描線算法4.1.3 其它算法4.2 區(qū)域填充4.

37、2.1 簡(jiǎn)單種子填充4.2.2 掃描線種子填充4.3 圖案填充4.4 字符,57,4.2.1 簡(jiǎ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)棧非空時(shí)，執(zhí)行如下三步操作：（1）棧頂象素出棧；（2）將出棧象素置成new_colo

38、r ；（3）按左、上、右、下的順序檢查與出棧象素相鄰的四個(gè)象素，若其中某個(gè)象素為old_color，則把該象素作為新的種子入棧。,58,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); F

39、loodFill4(x-1,y,oldColor,newColor);FloodFill4(x,y+1,oldColor,newColor);FloodFill4(x+1,y,oldColor,newColor); FloodFill4(x,y-1,oldColor,newColor);}}/*end of FloodFill4()*/,8,2,3,9,S,4,5,7,6,,5,4,3,2,1,0,,,,0,,8,

40、2,3,,1,,9,S,4,5,,2,,7,6,,3,,,4,,,,,,,,,,,,,,,,各象素入棧及出棧順序: S入棧S出棧并填充, (4,7,9,2入棧)2出棧并填充,(3,8入棧)8出棧并填充,(9入棧)9出棧并填充,(無象素入棧)3出棧并填充,(4入棧)4出棧并填充,(5,6入棧)6出棧并填充,(7入棧)7出棧并填充,(無象素入棧)5出棧并填充,(無象素入棧)9出棧7出棧4出棧,入棧: s

41、 4 7 9 2 3 8 9 4 5 6 7出棧: s 2 8 9 3 4 6 7 5 9 7 4,按左、上、右、下檢查出棧象素四個(gè)相鄰的象素,設(shè)種子象素為S(4,3)，按左、上、右、下檢查

42、出棧象素四個(gè)相鄰的象素，寫出各象素入棧及出棧順序。,入棧順序： (4,3) (3,3),(4,4),(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),

43、(3,2), (5,3)……,練習(xí),61,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)){SetPi

44、xel(x,y,newColor);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()*/,6

45、2,,4.2.1 簡(jiǎn)單種子填充算法,采用4向填充算法能否填充此8向連通區(qū)域？8連通區(qū)域的填充：將搜索方向改為8向?？商畛?連通區(qū)域和4連通區(qū)域？,63,4.2.1 簡(jiǎn)單種子填充算法,該算法也可以填充有孔區(qū)域。 優(yōu)點(diǎn)：算法簡(jiǎn)單缺點(diǎn)：遞歸執(zhí)行，效率不高，要求很大的存儲(chǔ)空間來實(shí)現(xiàn)堆棧。費(fèi)時(shí)費(fèi)內(nèi)存。改進(jìn)：減少遞歸次數(shù)，提高效率。掃描線種子填充算法,64,第4章 二維填充圖元生成,4.1 多邊形的掃描轉(zhuǎn)換4.1.1 概述

46、4.1.2 掃描線算法4.1.3 其它算法4.2 區(qū)域填充4.2.1 簡(jiǎn)單種子填充4.2.2 掃描線種子填充4.3 圖案填充4.4 字符,65,4.2.2 掃描線種子算法－原理,原理：基于種子填充算法的思想，利用掃描線的連貫性，減少遞歸層次。,基本過程：當(dāng)給定種子點(diǎn)時(shí)，首先填充種子點(diǎn)所在的掃描線上的位于給定區(qū)域的一個(gè)區(qū)段；然后確定與這一區(qū)段相通的上下兩條掃描線上位于給定區(qū)域內(nèi)的區(qū)段，并依次保存下來。反復(fù)這個(gè)過程，

47、直到填充結(jié)束。,66,4.2.2 掃描線種子算法－算法描述,將種子象素壓入堆棧while 堆棧非空 do begin    從堆棧中彈出一個(gè)種子象素；    沿著掃描線對(duì)種子象素的左右象素進(jìn)行填充，直至遇 到邊界象素為止；    標(biāo)志區(qū)間內(nèi)最左和最右象素為xleft 和xright； if在xleft≤x≤xri

48、ght中檢查與當(dāng)前掃描線相鄰的上下兩 條掃描線全為邊界象素或全為已填充過的象素 then goto 2； 在xleft≤x≤xright中標(biāo)記每一個(gè)既不包含邊界象素又不 包含已填充過的象素的區(qū)間；   將每一區(qū)間的最右象素作為種子象素壓入堆棧；endend of algorithm,67,4.2.2 掃描線種子算法－算法示例,執(zhí)行掃描線種子法的過程如圖所示，●是種子象素點(diǎn)S。開始時(shí)，堆

49、棧只有一個(gè)種子象素S，先填充S所在的區(qū)段，然后將其上下掃描線未填充的各區(qū)段的最右象素1，2，3作為種子象素壓入堆棧，再?gòu)亩褩Ｖ腥〕龇N子象素3，填充該區(qū)段，并將下一條掃描線未填充的區(qū)段的最右象素4壓入堆棧，重復(fù)執(zhí)行，直至堆棧為空時(shí)結(jié)束，整個(gè)區(qū)域填充完畢。,,,,,,,,,,,,,,68,4.2.2 掃描線種子算法,上述算法對(duì)于每一個(gè)待填充區(qū)段，只需壓棧一次；因此，掃描線種子填充算法提高了區(qū)域填充的效率。,69,多邊形掃描轉(zhuǎn)換與區(qū)域填充,聯(lián)

50、系：都是光柵圖形的多邊形面著色?？上嗷マD(zhuǎn)換：當(dāng)用直線的掃描轉(zhuǎn)換算法將多邊形的邊界像素求出，并給定多邊形內(nèi)一點(diǎn)為種子點(diǎn)時(shí)，則多邊形的掃描轉(zhuǎn)換轉(zhuǎn)化為區(qū)域填充。若已知給定區(qū)域?yàn)槎噙呅?，可求出其頂點(diǎn)坐標(biāo)，則區(qū)域填充轉(zhuǎn)化為多邊形的掃描轉(zhuǎn)換。,70,多邊形掃描轉(zhuǎn)換與區(qū)域填充,區(qū)別：基本思想不同前者：將多邊形的頂點(diǎn)表示轉(zhuǎn)換成點(diǎn)陣表示，后者：只改變區(qū)域的填充顏色，沒有改變表示方法。對(duì)邊界的要求不同前者：只要求掃描線與多邊形邊界交點(diǎn)個(gè)數(shù)為偶

51、數(shù)。邊界可以不封閉（例如對(duì)水平邊的預(yù)處理）。后者：區(qū)域封閉，防止遞歸填充跨界?；诘臈l件不同前者：從邊界頂點(diǎn)信息出發(fā)。后者：區(qū)域內(nèi)種子點(diǎn)。,71,第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 字符,72,4.3 圖案填充,基本問題關(guān)鍵是建立區(qū)域與圖像間的對(duì)

52、應(yīng)關(guān)系。方法1：建立整個(gè)繪圖空間(xoy)與圖像空間(uov)的1-1映射。（漫游）,,旋轉(zhuǎn)區(qū)域,填充區(qū)域,圖像（紋理）,,73,2.7 以圖像填充區(qū)域,方法2：建立區(qū)域局部坐標(biāo)空間(u’o’v’)與圖像空間(uov)的1-1映射。（動(dòng)畫）,填充區(qū)域,旋轉(zhuǎn)區(qū)域,圖像（紋理）,,,74,第4章 二維填充圖元生成,4.1 多邊形的掃描轉(zhuǎn)換4.1.1 概述4.1.2 掃描線算法4.1.3 其它算法4.2 區(qū)域填充4.2.1

53、簡(jiǎn)單種子填充4.2.2 掃描線種子填充4.3 圖案填充4.4 字符,75,4.4 字符,字符：在屏幕上顯示的字母、數(shù)字、符號(hào)、漢字等。由一個(gè)數(shù)字編碼唯一標(biāo)識(shí)。例如：ASCII碼，GB2312-80等。為了顯示輸出字符，必須有相應(yīng)的字庫(kù)，用于存儲(chǔ)每個(gè)字符的形狀信息。點(diǎn)陣字符：存儲(chǔ)量大，易于顯示；矢量字符：存儲(chǔ)量小，美觀，變換方便; 但需要光柵化后才能顯示。,76,4.4.1 點(diǎn)陣字符,點(diǎn)陣式字符將字符形狀表示為一個(gè)矩形點(diǎn)陣，

54、由點(diǎn)陣中點(diǎn)的不同值表達(dá)字符的形狀。,1 對(duì)應(yīng) 前景色0 對(duì)應(yīng) 背景色,7＊9位圖常用位圖：7＊99＊1616＊24,77,4.4.1 點(diǎn)陣字符,點(diǎn)陣字符的存儲(chǔ)（點(diǎn)陣字符是由位圖表示的，保存字符就是保存它的位圖）例：16＊16點(diǎn)陣漢字：16*16=256位（32個(gè)字節(jié)） 常用漢字6763個(gè)：6763*32=216416字節(jié) 16*24=384位（48字節(jié)） 6763*48=3

55、24K字節(jié)使用壓縮技術(shù)。點(diǎn)陣字符的顯示：從字庫(kù)中將字符的位圖檢索出來。將檢索到的位圖寫入幀緩存中。,78,4.4.1 點(diǎn)陣字符,點(diǎn)陣字符的變換：表示點(diǎn)陣字符的是位圖。對(duì)點(diǎn)陣字符的變換是逐像素的圖象變換。當(dāng)將點(diǎn)陣字符旋轉(zhuǎn)或放大時(shí)，會(huì)出現(xiàn)走樣而難看。,以字母P為原型的一些變化,79,4.4.2 矢量字符,記錄字符的筆畫信息（幾何信息，如字符所有端點(diǎn)的坐標(biāo)信息及拓?fù)浣Y(jié)構(gòu)）而不是整個(gè)位圖。占用空間少，美觀，變換方便。廣泛用于排版，工程

56、繪圖軟件中?；救〈它c(diǎn)陣字符。,80,4.4.2 矢量字符,矢量字符的變換：表示矢量字符的是端點(diǎn)坐標(biāo)，對(duì)矢量字符的變換是對(duì)端點(diǎn)進(jìn)行變換，屬于圖形的幾何變換。計(jì)算簡(jiǎn)單，且顯示效果好。矢量字符的顯示：根據(jù)給定字符的編碼，在字庫(kù)中檢索出表示該字符的數(shù)據(jù)。取出端點(diǎn)坐標(biāo)，對(duì)其進(jìn)行適當(dāng)?shù)膸缀巫儞Q，再根據(jù)各端點(diǎn)的標(biāo)志顯示字符。,81,4.4.3 字符屬性,字體： 宋體 仿宋體 楷體 黑體 隸書字高： 宋體 宋體 宋體 宋體字