計(jì)算機(jī)圖形學(xué)電子教案

計(jì)算機(jī)圖形學(xué)電子教案1第1頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月第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字符2第2頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月第4章二維填充圖元生成二維填充圖元用顏色或圖案填充一個(gè)二維區(qū)域(由封閉的輪廓線包圍)。輪廓線通常是多邊形。如果是曲線的話：求出邊界像素→區(qū)域填充；可以采用直線段逼近→多邊形的掃描轉(zhuǎn)換。3第3頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月第4章二維填充圖元生成多邊形的兩種表示方法：頂點(diǎn)表示（多邊形）用多邊形頂點(diǎn)的序列來(lái)刻劃多邊形。直觀、幾何意義強(qiáng)、占內(nèi)存少、易于幾何變換；不能直接用于光柵系統(tǒng)顯示。點(diǎn)陣表示（區(qū)域）用象素的集合(邊界/內(nèi)部)來(lái)刻畫(huà)多邊形。失去了許多重要的幾何信息；便于光柵系統(tǒng)顯示。4第4頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月第4章二維填充圖元生成多邊形分類：凸多邊形凹多邊形含內(nèi)環(huán)的多邊形5第5頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月第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字符6第6頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月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第7頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月1.掃描轉(zhuǎn)換矩形設(shè)矩形的四條邊分另為mina，xmax,ymin,ymax。只要填充從ymin到y(tǒng)max的每條掃描線上位于xmin和xmax之間的象素。ymaxyminxminxmaxvoidFillRectangle(Rectangle*rect，intcolor) {intx，y; for(y=rect->ymin；y<=rect->ymax；y++) for(x=rect->xmin；x<=rect->xmax；x++) SETPixel(x，y，color); }/*endofFillRectangle()*/8第8頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月1.掃描轉(zhuǎn)換矩形矩形也是多邊形，那么為什么要單獨(dú)處理矩形？掃描轉(zhuǎn)換多邊形的算法復(fù)雜，而矩形的應(yīng)用非常多(窗口)，所以對(duì)其單獨(dú)處理以提高效率。共享邊界將會(huì)被重繪兩次，如何處理？ 屬于誰(shuí)？原則：左、下邊的象素屬于矩形，而右、上邊的象素不屬于矩形。左閉右開(kāi)，下閉上開(kāi)。邊界像素重繪問(wèn)題；填充擴(kuò)大化問(wèn)題。9第9頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月1.掃描轉(zhuǎn)換矩形考慮填充從BL(x，y)到TR（x+5，y+5）的矩形。voidFillRectangle(Rectangle*rect，intcolor) {intx，y; for(y=rect->ymin；y<=rect->ymax；y++) for(x=rect->xmin；x<=rect->xmax；x++) SETPixel(x，y，color); }/*endofFillRectangle()*/10第10頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月1.掃描轉(zhuǎn)換矩形BL(x,y)TR(x+5,y+5)Area=6*6=36pixelsArea=5*5=25pixels矩形面積為：6*6＝36pixels矩形實(shí)際面積應(yīng)為:

[(x+5)-x]*[(y+5)-y]

＝25pixels采用左閉右開(kāi)，下閉上開(kāi)的原則對(duì)邊界象素進(jìn)行處理可保證矩形的面積不被擴(kuò)大。對(duì)FillRectangle()進(jìn)行修改。11第11頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月1.掃描轉(zhuǎn)換矩形設(shè)矩形的四條邊分另為xmin，xmax，ymin，ymax。ymaxyminxminxmaxvoidFillRectangle(Rectangle*rect，intcolor) {intx，y; for(y=rect->ymin；y<rect->ymax；y++) for(x=rect->xmin；x<rect->xmax；x++) SETPixel(x，y，color); }/*endofFillRectangle()*/12第12頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月2.

逐點(diǎn)判斷法它是掃描轉(zhuǎn)換多邊形的最簡(jiǎn)單算法，即逐個(gè)判斷繪圖窗口內(nèi)的象素是否在多邊形內(nèi)部。如何判斷點(diǎn)在多邊形的內(nèi)外？－計(jì)算幾何射線法：累計(jì)角度法編碼法；13第13頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月2.

逐點(diǎn)判斷法逐點(diǎn)判斷的算法雖然程序簡(jiǎn)單，但不可取。原因是速度太慢。主要是由于該算法割斷了各象素之間的聯(lián)系，孤立地考察各象素與多邊形的內(nèi)外關(guān)系，使得幾十萬(wàn)甚至幾百萬(wàn)個(gè)象素都要一一判別，每次判別又要多次求交點(diǎn)，花費(fèi)很多時(shí)間。不適于實(shí)際使用，很少采用。14第14頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月第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字符15第15頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.1.2掃描線算法掃描線算法是掃描轉(zhuǎn)換多邊形的常用算法，它充分利用了相鄰像素之間的連貫性，避免了逐點(diǎn)判斷和反復(fù)求交計(jì)算，達(dá)到了減少計(jì)算量和提高算法效率的目的。處理對(duì)象：非自交多邊形（邊與邊之間除了頂點(diǎn)外無(wú)其它交點(diǎn)）。16第16頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.1.2掃描線算法開(kāi)發(fā)和利用相鄰象素之間的連貫性是光柵圖形學(xué)算法的重要技巧。掃描線算法綜合利用了區(qū)域的連貫性、掃描線的連貫性和邊的連貫性等三種形式的連貫性。17第17頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.1.2掃描線算法區(qū)域的連貫性：相鄰兩條掃描線構(gòu)成一個(gè)水平長(zhǎng)方形區(qū)域，并被多邊形的邊分割為若干梯形（一類位于多邊形的內(nèi)部；另一類在多邊形的外部，且間隔排列）。只需知道該區(qū)域內(nèi)任一梯形中一點(diǎn)關(guān)于多邊形的內(nèi)外關(guān)系，即可確定區(qū)域內(nèi)所有梯形關(guān)于多邊形的內(nèi)外關(guān)系。

掃描線的連貫性：區(qū)域的連貫性在一條掃描線上的反映；邊的連貫性：某條邊與當(dāng)前掃描線相交，也可能與下一條掃描線相交?？赏ㄟ^(guò)與當(dāng)前掃描線的交點(diǎn)計(jì)算與下一掃描線的交點(diǎn)(利用斜率)。（區(qū)域的連貫性在相鄰兩掃描線上的反映）y=iXe1Xe2Xe3Xe4Xe8Xe7y=i+1Xd1Xd2Xd3Xd4Xd8Xd7P0P8P7P1P2P3P4P5P618第18頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月根據(jù)掃描線的連貫性可知：一條掃描線與多邊形的交點(diǎn)中，入點(diǎn)和出點(diǎn)之間所有點(diǎn)都是多邊形的內(nèi)部點(diǎn)。所以，對(duì)所有的掃描線填充入點(diǎn)到出點(diǎn)之間的點(diǎn)就可填充多邊形。如何具體實(shí)現(xiàn)（如何找到入點(diǎn)、出點(diǎn)）？4.1.2掃描線算法－原理0246810122468101234入點(diǎn)出點(diǎn)內(nèi)部點(diǎn)19第19頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月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之間、9與13之間的所有象素點(diǎn)進(jìn)行填充。求交、排序、配對(duì)、填色02468101224681020第20頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.1.2掃描線算法－數(shù)據(jù)結(jié)構(gòu)及實(shí)現(xiàn)算法中采用較靈活的數(shù)據(jù)結(jié)構(gòu)。它由邊分類表NET（EdgeTable）和活化邊表AET（ActiveEdgeList）兩部分組成。21第21頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月求交、排序、配對(duì)、填色利用鏈表：與當(dāng)前掃描線相交的邊稱為活化邊(ActiveEdge)，把它們按與掃描線交點(diǎn)x坐標(biāo)遞增的順序存入一個(gè)鏈表中，稱為活化邊表AET(AET，ActiveEdgeList)。它記錄了多邊形邊沿掃描線的交點(diǎn)序列。y=6，AET：y=6y=7024681012246810P3P2P1P4P5P6e3e4e2e1e5e6e2e592011130^ymaxxΔxAET中每個(gè)對(duì)象需要存放的信息：ymax：邊所交的最高掃描線；x：當(dāng)前掃描線與邊的交點(diǎn)；Δx：從當(dāng)前掃描線到下一條掃描線之間的x增量(邊的斜率的倒數(shù))；next：指向下一對(duì)象的指針?；罨叡鞟ET第22頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月求交、排序、配對(duì)、填色隨掃描線的遞增如何更新AET？邊的加入、刪除，交點(diǎn)的更新。y=6，AET：y=7，AET：y=6y=7024681012246810P3P2P1P4P5P6e3e4e2e1e5e6e2e592011130^ymaxxΔxe2e392097-2.5e4e51171.511130^建立一個(gè)新的數(shù)據(jù)結(jié)構(gòu)：邊分類表NET活化邊表AET第23頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月邊分類表NET（EdgeTable）

：按掃描線i對(duì)非水平邊進(jìn)行分類的指針數(shù)組。下端點(diǎn)的y坐標(biāo)值等于i的邊歸入第i類(在該掃描線第一次出現(xiàn)的邊)。同一類中，各邊按x值（x值相等時(shí)，按Δx的值）遞增的順序排列。有多少條掃描線，就設(shè)多少類。024681012246810P3P2P1P4P5P6e3e4e2e1e5e6ymaxxΔxNET中每個(gè)對(duì)象需要存放的信息：ymax：邊所交的最高掃描線；x：邊的下端點(diǎn)的x坐標(biāo)；Δx：從當(dāng)前掃描線到下一條掃描線之間的x增量(邊的斜率的倒數(shù))；next：指向下一對(duì)象的指針。第24頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月邊分類表NET（EdgeTable）

：按掃描線i對(duì)非水平邊進(jìn)行分類的指針數(shù)組。下端點(diǎn)的y坐標(biāo)值等于i的邊歸入第i類(在該掃描線第一次出現(xiàn)的邊)。同一類中，各邊按x值（x值相等時(shí)，按Δx的值）遞增的順序排列。有多少條掃描線，就設(shè)多少類。e2e5e1e6e3e4NET（桶）同一類中的邊按x、Δx的遞增順序排列024681012246810P3P2P1P4P5P6e3e4e2e1e5e697-2.51171.5^11130^920^37-2.5571.5^76^54^32^10^ymaxxΔx第25頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.1.2掃描線算法－數(shù)據(jù)結(jié)構(gòu)及實(shí)現(xiàn)算法中采用較靈活的數(shù)據(jù)結(jié)構(gòu)。它由邊分類表NET（EdgeTable）和活化邊表AET（ActiveEdgeList）兩部分組成。NET和AET中的基本元素稱為“邊”（Edge）。邊的結(jié)構(gòu)“Edge”由以下四個(gè)域組成：ymax：邊的上端點(diǎn)的y坐標(biāo)；x：在NET中表示邊的下端點(diǎn)的

x坐標(biāo)；在AET中則表示邊 與掃描線的交點(diǎn)的x坐標(biāo)；Δx：邊的斜率的倒數(shù)；next：指向下一“邊”的指針。typedefstruct{intymax；

floatx，deltax；

Edge*next；

}Edge；

ymaxxΔx26第26頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.1.2掃描線算法－幾點(diǎn)規(guī)則求交、排序、配對(duì)、填色交點(diǎn)與多邊形頂點(diǎn)重合時(shí)，會(huì)導(dǎo)致“配對(duì)”失敗，如何處理？下閉上開(kāi)02468101224681027第27頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.1.2掃描線算法－幾點(diǎn)規(guī)則掃描線與多邊形的頂點(diǎn)相交時(shí)，交點(diǎn)的取舍(保證交點(diǎn)正確配對(duì))。檢查該頂點(diǎn)的兩相鄰邊在掃描線的哪一側(cè)： 只要檢查頂點(diǎn)的兩條邊的另外兩個(gè)端點(diǎn)的Y值，兩個(gè)Y值中大于交點(diǎn)Y值的個(gè)數(shù)是0，1，2，來(lái)決定取0，1，2個(gè)交點(diǎn)。(下閉上開(kāi))(a)P0P2P1P0P2P1P0P2P1P0P2P1(b)(c)(d)y=e28第28頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.1.2掃描線算法－算法描述建立NET，置y為NET中非空桶的最小序號(hào)；置AET表為空，且把y桶中NET表的邊加入AET表中；whileAET表中非空do

begin

對(duì)AET表中的x、Δx按升序排列；

按照AET表中交點(diǎn)前后次序，在每對(duì)奇偶交點(diǎn)間的x段予 以填充；

計(jì)算下一條掃描線：y=y+1；

if掃描線y=ymax

then從AET表中刪除這些邊；

對(duì)在AET表中的其他邊，計(jì)算與下一條掃描線的交點(diǎn)： x=x+Δx

按照掃描線y值把NET表中相應(yīng)桶中的邊加入AET表中；

endendofalgorithm29第29頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.1.2掃描線算法－幾點(diǎn)規(guī)則邊界象素的取舍問(wèn)題，避免填充擴(kuò)大化。若x為整數(shù)，即交點(diǎn)落于像素點(diǎn)上（邊界象素）。落在右邊界的象素(出點(diǎn))不予填充；“左閉右開(kāi)”y=e(x,e)(a)y=e(x,e)(b)30第30頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.1.2掃描線算法－幾點(diǎn)規(guī)則1.邊界上的象素:“左閉右開(kāi)”，將左邊界的點(diǎn)算為內(nèi)部，而將右邊界的點(diǎn)算為外部。2.頂點(diǎn)：“下閉上開(kāi)”，即丟棄上頂點(diǎn)。掃描線交于一頂點(diǎn)，共享交點(diǎn)的兩條邊分另處于掃描線的兩邊，這時(shí)交點(diǎn)只取1個(gè)，如掃描線y=3，根據(jù)“下閉上開(kāi)”原則，該點(diǎn)被填充1次。共享交點(diǎn)的兩條邊處于掃描線的上方，這時(shí)交點(diǎn)取2個(gè)，如掃描線y=1。共享交點(diǎn)的兩條邊處于掃描線的下方，這時(shí)交點(diǎn)取0個(gè)，如掃描線y=9，無(wú)交點(diǎn)，不填充。02468101224681031第31頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月第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字符32第32頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.1.3其它算法1.

邊界標(biāo)志法33第33頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月1.

邊界標(biāo)志算法取一個(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不變。沒(méi)有了求交、排序等運(yùn)算。02468101224681034第34頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月1.

邊界標(biāo)志算法也稱輪廓填充算法－改進(jìn)的邊緣填充法。1.對(duì)多邊形的每一條邊進(jìn)行掃描轉(zhuǎn)換，即對(duì)多邊形邊界所經(jīng)過(guò)的象素作一個(gè)邊界標(biāo)志。2.填充：對(duì)每條與多邊形相交的掃描線，按從左到右的順序，逐個(gè)訪問(wèn)該掃描線上的象素。取一個(gè)布爾變量inside來(lái)指示當(dāng)前點(diǎn)的狀態(tài)：若點(diǎn)在多邊形內(nèi)，則inside為真；若點(diǎn)在多邊形外，則inside為假。Inside的初始值為假，每當(dāng)當(dāng)前訪問(wèn)象素為被打上邊界標(biāo)志的點(diǎn)，就把inside取反。對(duì)未打標(biāo)志的點(diǎn)，inside不變。35第35頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月1.

邊界標(biāo)志算法優(yōu)點(diǎn)：對(duì)每個(gè)象素只訪問(wèn)一次。不必建立、維護(hù)NET及AET等數(shù)據(jù)結(jié)構(gòu)，也沒(méi)有了排序、求交等運(yùn)算，適于硬件實(shí)現(xiàn)。用軟件實(shí)現(xiàn)時(shí)，掃描線算法與邊界標(biāo)志算法的執(zhí)行速度幾乎相同。但由于邊界標(biāo)志算法不必建立維護(hù)AET以及對(duì)它進(jìn)行排序，所以邊界標(biāo)志算法更適合硬件實(shí)現(xiàn)，這時(shí)它的執(zhí)行速度比掃描線算法快一至兩個(gè)數(shù)量級(jí)。36第36頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月第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字符37第37頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.2區(qū)域填充多邊形的兩種表示方法：頂點(diǎn)表示（多邊形）用多邊形頂點(diǎn)的序列來(lái)刻劃多邊形。直觀、幾何意義強(qiáng)、占內(nèi)存少、易于幾何變換；不能直接用于光柵系統(tǒng)顯示。點(diǎn)陣表示（區(qū)域）用象素的集合(邊界/內(nèi)部)來(lái)刻畫(huà)多邊形。失去了許多重要的幾何信息；便于光柵系統(tǒng)顯示。38第38頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.2區(qū)域填充區(qū)域可采用兩種表示形式:內(nèi)點(diǎn)表示枚舉區(qū)域內(nèi)部的所有像素；內(nèi)部的所有像素著同一個(gè)顏色；邊界像素著不同的顏色。邊界表示枚舉出邊界上所有的像素；邊界上的所有像素著同一顏色；內(nèi)部像素著不同的顏色。邊界點(diǎn)內(nèi)點(diǎn)39第39頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.2區(qū)域填充區(qū)域填充先將區(qū)域內(nèi)的一點(diǎn)賦予指定的顏色，然后將該顏色擴(kuò)展到整個(gè)區(qū)域的過(guò)程。簡(jiǎn)單種子算法掃描線種子算法要求區(qū)域是“連通”的。邊界點(diǎn)內(nèi)點(diǎn)40第40頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.2區(qū)域填充區(qū)域填充要求區(qū)域是連通的連通性：4連通：從區(qū)域內(nèi)任意一點(diǎn)出發(fā)，可通過(guò)上、下、左、右四個(gè)方向到達(dá)區(qū)域內(nèi)的任意象素；8連通：從區(qū)域內(nèi)任意一點(diǎn)出發(fā)，可通過(guò)上、下、左、右、左上、左下、右上、右下八個(gè)方向到達(dá)區(qū)域內(nèi)的任意象素；41第41頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月第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字符42第42頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.2.1簡(jiǎn)單種子填充算法設(shè)G為一內(nèi)點(diǎn)表示的區(qū)域，(x,y)為區(qū)域內(nèi)一點(diǎn)，old_color為G的原色。現(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_color；（3）按左、上、右、下的順序檢查與出棧象素相鄰的四個(gè)象素，若其中某個(gè)象素為old_color，則把該象素作為新的種子入棧。43第43頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.2.1簡(jiǎn)單種子填充算法/*內(nèi)點(diǎn)表示的4連通區(qū)域*/voidFloodFill4(intx,inty,intoldColor,intnewColor){if(GNETPixel(x,y)==oldColor){SNETPixel(x,y,newColor);FloodFill4(x-1,y,oldColor,newColor); FloodFill4(x,y+1,oldColor,newColor); FloodFill4(x+1,y,oldColor,newColor);FloodFill4(x,y-1,oldColor,newColor);}}/*endofFloodFill4() */44第44頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月8239S4576543210082319S4527634各象素入棧及出棧順序:S入棧S出棧并填充,(4,7,9,2入棧)2出棧并填充,(3,8入棧)8出棧并填充,(9入棧)9出棧并填充,(無(wú)象素入棧)3出棧并填充,(4入棧)4出棧并填充,(5,6入棧)6出棧并填充,(7入棧)7出棧并填充,(無(wú)象素入棧)5出棧并填充,(無(wú)象素入棧)9出棧7出棧4出棧入棧:

s47923894567出棧:

s28934675974

按左、上、右、下檢查出棧象素四個(gè)相鄰的象素第45頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.2.1簡(jiǎn)單種子填充算法/*邊界表示的4連通區(qū)域*/voidBoundaryFill4(intx,inty,intboundaryColor,intnewColor){ intcolor; color=GETPixel(x,y); if((color!=boundaryColor)&&(color!=newColor)) { drawPixel(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); }}/*endofBoundaryFill4() */

46第46頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月S4.2.1簡(jiǎn)單種子填充算法采用4向填充算法能否填充此8向連通區(qū)域？8連通區(qū)域的填充：將搜索方向改為8向?？商畛?連通區(qū)域和4連通區(qū)域？47第47頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.2.1簡(jiǎn)單種子填充算法該算法也可以填充有孔區(qū)域。

優(yōu)點(diǎn)：算法簡(jiǎn)單缺點(diǎn)：遞歸執(zhí)行，效率不高，要求很大的存儲(chǔ)空間來(lái)實(shí)現(xiàn)堆棧。費(fèi)時(shí)費(fèi)內(nèi)存。改進(jìn)：減少遞歸次數(shù)，提高效率。掃描線種子填充算法48第48頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月第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字符49第49頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.2.2掃描線種子算法－原理原理：基于種子填充算法的思想，利用掃描線的連貫性，減少遞歸層次?；具^(guò)程：當(dāng)給定種子點(diǎn)時(shí)，首先填充種子點(diǎn)所在的掃描線上的位于給定區(qū)域的一個(gè)區(qū)段；然后確定與這一區(qū)段相通的上下兩條掃描線上位于給定區(qū)域內(nèi)的區(qū)段，并依次保存下來(lái)。反復(fù)這個(gè)過(guò)程，直到填充結(jié)束。50第50頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.2.2掃描線種子算法－算法描述將種子象素壓入堆棧while堆棧非空do

begin

從堆棧中彈出一個(gè)種子象素；

沿著掃描線對(duì)種子象素的左右象素進(jìn)行填充，直至遇 到邊界象素為止；

標(biāo)志區(qū)間內(nèi)最左和最右象素為xleft

和xright；

if在xleft≤x≤xright中檢查與當(dāng)前掃描線相鄰的上下兩 條掃描線全為邊界象素或全為已填充過(guò)的象素then goto2；在xleft≤x≤xright中標(biāo)記每一個(gè)既不包含邊界象素又不 包含已填充過(guò)的象素的區(qū)間；

將每一區(qū)間的最右象素作為種子象素壓入堆棧；

endendofalgorithm51第51頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.2.2掃描線種子算法－算法示例執(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ū)域填充完畢。S12312412512612789101278127812711217121212112781134569101252第52頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.2.2掃描線種子算法上述算法對(duì)于每一個(gè)待填充區(qū)段，只需壓棧一次；因此，掃描線種子填充算法提高了區(qū)域填充的效率。53第53頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月第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字符54第54頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.3字符字符：在屏幕上顯示的字母、數(shù)字、符號(hào)、漢字等。由一個(gè)數(shù)字編碼唯一標(biāo)識(shí)。例如：ASCII碼，GB2312-80等。為了顯示輸出字符，必須有相應(yīng)的字庫(kù)，用于存儲(chǔ)每個(gè)字符的形狀信息。點(diǎn)陣字符：存儲(chǔ)量大，易于顯示；矢量字符：存儲(chǔ)量小，美觀，變換方便;但需要光柵化后才能顯示。55第55頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.3.1點(diǎn)陣字符點(diǎn)陣式字符將字符形狀表示為一個(gè)矩形點(diǎn)陣，由點(diǎn)