多邊形的掃描轉(zhuǎn)換與區(qū)域填充2

2024年10月23日計(jì)算機(jī)圖形學(xué)13.4多邊形的掃描轉(zhuǎn)換與區(qū)域填充多邊形掃描轉(zhuǎn)換與區(qū)域填充可以統(tǒng)稱區(qū)域填充，就是如何用顏色或圖案來(lái)填充一個(gè)二維區(qū)域。填充主要做兩件工作：一是確定需要填充的范圍，二是確定填充的內(nèi)容。一般區(qū)域填充指的是已知區(qū)域內(nèi)一個(gè)種子，然后由種子向周圍蔓延填充規(guī)定區(qū)域。方法：掃描線法：x-掃描線法-〉有序邊表法，邊填充算法種子填充算法（區(qū)域填充）2024年10月23日計(jì)算機(jī)圖形學(xué)23.4.1掃描轉(zhuǎn)換（掃描線）法多邊形的掃描轉(zhuǎn)換：把多邊形的頂點(diǎn)表示轉(zhuǎn)換為點(diǎn)陣表示，也就是從多邊形的給定邊界出發(fā)，求出位于其內(nèi)部的各個(gè)象素，并給幀緩沖器內(nèi)的各個(gè)對(duì)應(yīng)元素設(shè)置相應(yīng)的灰度和顏色，通常稱這種轉(zhuǎn)換為多邊形的掃描轉(zhuǎn)換。三種方法：掃描線算法邊填充算法邊界標(biāo)志法2024年10月23日計(jì)算機(jī)圖形學(xué)3多邊形分類多邊形分為凸多邊形、凹多邊形、含內(nèi)環(huán)的多邊形。2024年10月23日計(jì)算機(jī)圖形學(xué)4多邊形表示多邊形的表示方法頂點(diǎn)表示點(diǎn)陣表示頂點(diǎn)表示：用多邊形頂點(diǎn)的序列來(lái)刻劃多邊形。直觀、幾何意義強(qiáng)、占內(nèi)存少；不能直接用于面著色。點(diǎn)陣表示：用位于多邊形內(nèi)的象素的集合來(lái)刻劃多邊形。失去了許多重要的幾何信息；便于運(yùn)用幀緩沖存儲(chǔ)器表示圖形，易于面著色。2024年10月23日計(jì)算機(jī)圖形學(xué)53.4.1.1掃描線算法-x掃描線法掃描線算法目標(biāo)：利用相鄰像素之間的連貫性，提高算法效率處理對(duì)象：非自交多邊形（邊與邊之間除了頂點(diǎn)外無(wú)其它交點(diǎn)）2024年10月23日計(jì)算機(jī)圖形學(xué)6步驟(1)確定多邊形所占有的最大掃描線數(shù)，得到多邊形頂點(diǎn)的最小和最大y值（ymin和ymax）。(2)從y=ymin到y(tǒng)=ymax，每次用一條掃描線進(jìn)行填充。(3)對(duì)一條掃描線填充的過(guò)程可分為四個(gè)步驟：

①計(jì)算掃描線與多邊形各邊的交點(diǎn)。②對(duì)求得的交點(diǎn)進(jìn)行排序。③奇偶配對(duì)求出掃描線與多邊形的相交區(qū)間。④對(duì)這些相交區(qū)間填充色。2024年10月23日計(jì)算機(jī)圖形學(xué)7需要解決的幾個(gè)問(wèn)題掃描線與多邊形頂點(diǎn)相交時(shí)交點(diǎn)的取舍問(wèn)題多邊形邊界上像素點(diǎn)的取舍問(wèn)題水平邊的處理減少求交運(yùn)算問(wèn)題2024年10月23日計(jì)算機(jī)圖形學(xué)8需要解決的幾個(gè)問(wèn)題（一）一、當(dāng)掃描線與多邊形頂點(diǎn)相交時(shí)，交點(diǎn)的取舍問(wèn)題。解決：當(dāng)掃描線與多邊形的頂點(diǎn)相交時(shí)，若共享頂點(diǎn)的兩條邊分別落在掃描線的兩邊，交點(diǎn)只算一個(gè)；若共享頂點(diǎn)的兩條邊在掃描線的同一邊，這時(shí)交點(diǎn)作為零個(gè)或兩個(gè)。2024年10月23日計(jì)算機(jī)圖形學(xué)9具體實(shí)現(xiàn)時(shí)只要檢查頂點(diǎn)的兩條邊的另外兩個(gè)端點(diǎn)的Y值，兩個(gè)Y值中大于交點(diǎn)Y值的個(gè)數(shù)是0，1，2，來(lái)決定取0，1，2個(gè)交點(diǎn)。2024年10月23日計(jì)算機(jī)圖形學(xué)10xy213456789111234567891011121012與多邊形頂點(diǎn)相交的交點(diǎn)的處理2024年10月23日計(jì)算機(jī)圖形學(xué)11011110222

與掃描線相交的多邊形頂點(diǎn)的交點(diǎn)數(shù)2024年10月23日計(jì)算機(jī)圖形學(xué)12需要解決的幾個(gè)問(wèn)題（二）二、邊界上象素的取舍問(wèn)題，避免填充擴(kuò)大化。解決方法：邊界象素：規(guī)定落在右上邊界的象素不予填充。具體實(shí)現(xiàn)時(shí)，只要對(duì)掃描線與多邊形的相交區(qū)間實(shí)行：左閉右開(kāi)（左邊界像素填充，右邊界像素不填充）下閉上開(kāi)（下邊界像素填充，上邊界像素不填充）屬于誰(shuí)？2024年10月23日計(jì)算機(jī)圖形學(xué)13需要解決的幾個(gè)問(wèn)題（三）三、水平邊的處理（與掃描線重合）將水平邊畫(huà)出后刪去，不參加求交，即求交后的操作（但是在計(jì)算交點(diǎn)個(gè)數(shù)時(shí)算作一個(gè)點(diǎn)）。2024年10月23日計(jì)算機(jī)圖形學(xué)14需要解決的幾個(gè)問(wèn)題（四）減少求交算法：x-掃描線法在處理每條掃描線時(shí)需要與多邊形的所有邊求交，而實(shí)際上一條掃描線往往只與少數(shù)幾條邊相交，因此降低了效率，于是提出了改進(jìn)算法—有序邊表法，也稱y連貫性算法。2024年10月23日計(jì)算機(jī)圖形學(xué)153.4.1.2掃描轉(zhuǎn)換法-有序邊表法該法與x-掃描線法基本過(guò)程一樣，只是在處理求交計(jì)算時(shí)作了改進(jìn)。2024年10月23日計(jì)算機(jī)圖形學(xué)16改進(jìn)思路可以從以下方面考慮：1在處理一條掃描線時(shí)，僅對(duì)與它相交的邊（有效邊）進(jìn)行求交運(yùn)算，于是可以構(gòu)造活性邊表。2考慮掃描描線的連貫性，即當(dāng)前掃描線與各邊的交點(diǎn)順序與下一條掃描線與各邊的交點(diǎn)順序很可能相同或者相似。3多邊形邊的連貫性，即當(dāng)一條邊與當(dāng)前掃描線相交時(shí)，它可能也與下一條掃描線相交。2024年10月23日計(jì)算機(jī)圖形學(xué)17所有的邊和掃描線求交，效率很低。因?yàn)橐粭l掃描線往往只和少數(shù)幾條邊相交。如何判斷多邊形的一條邊與掃描線是否相交？有效邊（ActiveEdge）：指與當(dāng)前掃描線相交的多邊形的邊，也稱為活性邊。有效邊表（ActiveEdgeTable,AET）：把有效邊按與掃描線交點(diǎn)x坐標(biāo)遞增的順序存放在一個(gè)鏈表中，此鏈表稱為有效（活性）邊表。2024年10月23日計(jì)算機(jī)圖形學(xué)18數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟只需對(duì)當(dāng)前掃描線的活動(dòng)邊表作更新，即可得到下一條掃描線的活動(dòng)邊表。2024年10月23日計(jì)算機(jī)圖形學(xué)19如何計(jì)算下一條掃描線與邊的交點(diǎn)直線方程：ax+by+c=0當(dāng)前交點(diǎn)坐標(biāo)：(xi,yi)下一交點(diǎn)坐標(biāo)：(xi+1,yi+1)xi+1=

((-byi+1)-c)/a=((-byi+1)-c)/a=xi-b/a=xi-1/k活動(dòng)邊表中需要存放的信息：

x：當(dāng)前掃描線與邊的交點(diǎn)

dx＝-b/a：從當(dāng)前掃描線到下一條掃描線之間的x增量△x ymax：邊所交的最高掃描線2024年10月23日計(jì)算機(jī)圖形學(xué)20數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟為了方便邊的活化鏈表的更新，建立另一個(gè)表-新邊表，存放在該掃描線第一次出現(xiàn)的邊。存放的信息：

x：掃描線與該邊的初始交點(diǎn)

dx：x的增量

ymax：該邊的最大y值2024年10月23日計(jì)算機(jī)圖形學(xué)21數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟即算法中采用較靈活的數(shù)據(jù)結(jié)構(gòu)。它由邊的新邊表NET（newEdgeTable）和邊的活性邊表AET（ActiveEdgeTable

）兩部分組成。表結(jié)構(gòu)NET和AET中的基本元素為多邊形的邊。邊的結(jié)構(gòu)由以下四個(gè)域組成：

ymax：邊的上端點(diǎn)的y坐標(biāo)；

x：在NET中表示邊的最低點(diǎn)的x坐標(biāo)，在AET中則表示邊與掃描線的交點(diǎn)的坐標(biāo)；

Δx：邊的斜率的倒數(shù)；（當(dāng)前掃描線到下一條掃描線x的增量）

next：指向下一條邊的指針。2024年10月23日計(jì)算機(jī)圖形學(xué)22ymaxx1/m(△x)nextymaxx1/m(△x)nextAET活性邊表NET新邊表X:邊的下端點(diǎn)的x坐標(biāo)X:邊與掃描線的交點(diǎn)的坐標(biāo)2024年10月23日計(jì)算機(jī)圖形學(xué)232024年10月23日計(jì)算機(jī)圖形學(xué)24活性邊表的例子34-2P3P456.50.5^P3P2掃描線2AET指針620P4P5570.5^P3P2掃描線3AET指針(Ymax,x,Δx,next)36-2P3P4560.5^P3P2掃描線1AET指針2024年10月23日計(jì)算機(jī)圖形學(xué)25活性邊表的例子620P4P557.50.5^P3P2掃描線4AET指針620P4P578-1^P2P1掃描線5AET指針724P5P178-1^P2P1掃描線6AET指針2024年10月23日計(jì)算機(jī)圖形學(xué)26新邊表724^P5P178-1^P2P1620^P4P536-2P3P4560.5^P3P2^^^(Ymax,x,Δx,next)2024年10月23日計(jì)算機(jī)圖形學(xué)27算法實(shí)現(xiàn)步驟

這樣，當(dāng)建立了邊的分類表NET后，掃描線算法可按下列步驟進(jìn)行：（1）取掃描線縱坐標(biāo)y的初始值為NET中非空元素的最小序號(hào)。（2）將邊的活化鏈表AET設(shè)置為空。（3）按從下到上的順序?qū)v坐標(biāo)值為y的掃描線（當(dāng)前掃描線）執(zhí)行下列步驟，直到邊的分類表ET和邊的活化鏈表都變成空為止。2024年10月23日計(jì)算機(jī)圖形學(xué)28算法實(shí)現(xiàn)步驟1）如邊分類表NET中的第y類元素非空，則將屬于該類的所有邊從AET中取出并插入邊的活化鏈表中，AET中的各邊按照x值（當(dāng)x值相等時(shí)，按Δx值）遞增方向排序。2）若相對(duì)于當(dāng)前掃描線，邊的活化鏈表AEL非空，則將AET中的邊兩兩依次配對(duì)，即1，2邊為一對(duì)，3，4邊為一對(duì)，依次類推。每一對(duì)邊與當(dāng)前掃描線的交點(diǎn)所構(gòu)成的區(qū)段位于多邊形內(nèi)，依次對(duì)這些區(qū)段上的點(diǎn)（象素）按多邊形屬性著色。3）將邊的活化鏈表AET中滿足y=ymax的邊刪去。4）將邊的活化鏈表AET剩下的每一條邊的x域累加Δx，即x:=x+Δx。5）將當(dāng)前的掃描線的縱坐標(biāo)值y累加1，即y:=y+1。2024年10月23日計(jì)算機(jī)圖形學(xué)29掃描線算法特點(diǎn)：算法效率較高。缺點(diǎn)：對(duì)各種表的維持和排序開(kāi)銷太大，適合軟件實(shí)現(xiàn)而不適合硬件實(shí)現(xiàn)。2024年10月23日計(jì)算機(jī)圖形學(xué)30掃描線算法問(wèn)題：如何處理多邊形的水平邊？如何修改掃描線算法，使它能處理邊自交的多邊形？2024年10月23日計(jì)算機(jī)圖形學(xué)313.4.1.3邊填充法算法簡(jiǎn)單，但對(duì)于復(fù)雜圖型，每一象素可能被訪問(wèn)多次算法過(guò)程：對(duì)于每一條掃描線和每條多邊形邊的交點(diǎn)（x1,y1）,將該掃描線上交點(diǎn)右方的所有像素取補(bǔ)，對(duì)多邊形的每條邊做同樣處理，多邊形順序隨意，如下圖：2024年10月23日計(jì)算機(jī)圖形學(xué)322024年10月23日計(jì)算機(jī)圖形學(xué)333.4.1.4柵欄填充算法為了減少重復(fù)計(jì)算，可采用柵欄算法，柵欄指的是一條過(guò)多邊形頂點(diǎn)且與掃描線垂直的直線。它把多邊形分為兩半。2024年10月23日計(jì)算機(jī)圖形學(xué)34算法過(guò)程對(duì)于每個(gè)掃描線與多邊形的交點(diǎn)，將交點(diǎn)與柵欄之間的像素取補(bǔ)，若交點(diǎn)位于柵欄左邊，則將交點(diǎn)之右，柵欄之作的所有像素取補(bǔ)，若交點(diǎn)位于柵欄右邊，則將柵欄之左，交點(diǎn)之右的像素取補(bǔ)。2024年10月23日計(jì)算機(jī)圖形學(xué)35柵欄算法圖示2024年10月23日計(jì)算機(jī)圖形學(xué)363.4.1.5邊界標(biāo)志算法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不變。2024年10月23日計(jì)算機(jī)圖形學(xué)37邊界標(biāo)志算法:算法過(guò)程voidedgemark_fill(polydef,color)多邊形定義polydef；intcolor;{對(duì)多邊形polydef每條邊進(jìn)行直線掃描轉(zhuǎn)換；

inside=FALSE;for(每條與多邊形polydef相交的掃描線y)for(掃描線上每個(gè)象素x){if(象素x被打上邊標(biāo)志)inside=!(inside);if(inside！=FALSE)drawpixel(x,y,color);elsedrawpixel(x,y,background); }}2024年10月23日計(jì)算機(jī)圖形學(xué)38邊界標(biāo)志算法用軟件實(shí)現(xiàn)時(shí)，掃描線算法與邊界標(biāo)志算法的執(zhí)行速度幾乎相同，但由于邊界標(biāo)志算法不必建立維護(hù)邊表以及對(duì)它進(jìn)行排序，所以邊界標(biāo)志算法更適合硬件實(shí)現(xiàn)，這時(shí)它的執(zhí)行速度比有序邊表算法快一至兩個(gè)數(shù)量級(jí)。思考：如何處理邊界的交點(diǎn)個(gè)數(shù)使其成為偶數(shù)？2024年10月23日計(jì)算機(jī)圖形學(xué)393.4.2區(qū)域填充算法3.4.2.1種子填充法區(qū)域指已經(jīng)表示成點(diǎn)陣形式的填充圖形，它是象素的集合。區(qū)域填充指先將區(qū)域的一點(diǎn)賦予指定的顏色，然后將該顏色擴(kuò)展到整個(gè)區(qū)域的過(guò)程。區(qū)域填充算法要求區(qū)域是連通的2024年10月23日計(jì)算機(jī)圖形學(xué)40區(qū)域填充表示方法：內(nèi)點(diǎn)表示、邊界表示內(nèi)點(diǎn)表示枚舉出區(qū)域內(nèi)部的所有像素內(nèi)部的所有像素著同一個(gè)顏色邊界像素著與內(nèi)部像素不同的顏色邊界表示枚舉出邊界上所有的像素邊界上的所有像素著同一顏色內(nèi)部像素著與邊界像素不同的顏色2024年10月23日計(jì)算機(jī)圖形學(xué)41區(qū)域填充區(qū)域填充要求區(qū)域是連通的連通性：4連通、8連通4連通：8連通44p44(b)p的8-鄰接點(diǎn)88888p888(a)p的4-鄰接點(diǎn)

鄰接點(diǎn)的定義2024年10月23日計(jì)算機(jī)圖形學(xué)42區(qū)域填充4連通與8連通區(qū)域的區(qū)別連通性：4連通可看作8連通區(qū)域，但對(duì)邊界有要求2024年10月23日計(jì)算機(jī)圖形學(xué)43

區(qū)域的邊界表示和內(nèi)點(diǎn)表示(a)以邊界表示的4-連通區(qū)域(d)以內(nèi)點(diǎn)表示的8-連通區(qū)域(b)以內(nèi)點(diǎn)表示的4-連通區(qū)域(c)以邊界表示的8-連通區(qū)域2024年10月23日計(jì)算機(jī)圖形學(xué)44四鄰域法不能正確填充一些特殊圖形2024年10月23日計(jì)算機(jī)圖形學(xué)45種子填充算法-4鄰域算法的輸入：種子點(diǎn)坐標(biāo)(x,y)，填充色和邊界顏色。棧結(jié)構(gòu)實(shí)現(xiàn)4-連通邊界填充算法的算法步驟為：種子象素入棧；當(dāng)棧非空時(shí)重復(fù)執(zhí)行如下三步操作：(1)棧頂象素出棧；(2)將出棧象素置成填充色；(3)按一定順序檢查出棧象素的4-鄰接點(diǎn)，若其中某個(gè)象素點(diǎn)不是邊界色且未置成多邊形色，則把該象素入棧。2024年10月23日計(jì)算機(jī)圖形學(xué)46種子填充算法-8鄰域棧結(jié)構(gòu)實(shí)現(xiàn)8-連通邊界填充算法的算法步驟為：種子象素入棧；當(dāng)棧非空時(shí)重復(fù)執(zhí)行如下三步操作：(1)棧頂象素出棧；(2)將出棧象素置成填充色；(3)按一定順序檢查出棧象素的8-鄰接點(diǎn)，若其中某個(gè)象素點(diǎn)不是邊界色且未置成多邊形色，則把該象素入棧。2024年10月23日計(jì)算機(jī)圖形學(xué)47種子填充算法適合于內(nèi)點(diǎn)表示區(qū)域的填充算法設(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）將出棧象素置成多邊形色；（3）按上、下、左、右的順序檢查與出棧象素相鄰的四個(gè)象素，若其中某個(gè)象素不在邊界上且未置成多邊形色，則把該象素入棧。2024年10月23日計(jì)算機(jī)圖形學(xué)48舉例以s1為種子，按照左、上、右、下順序入棧出棧，過(guò)程如下：2024年10月23日計(jì)算機(jī)圖形學(xué)492024年10月23日計(jì)算機(jī)圖形學(xué)5068454468422684533S1S16845568466S1S11234567891011684468866684988684996849772024年10月23日計(jì)算機(jī)圖形學(xué)51種子填充算法例：多邊形由P0P1P2P3P4構(gòu)成，P0(1,5)P1(5,5)P2(7,3)P3(7,1)P4(1,1)設(shè)種子點(diǎn)為（3，3），搜索的方向是上、下、左、右。依此類推，最后像素被選中并填充的次序如圖中箭頭所示2024年10月23日計(jì)算機(jī)圖形學(xué)52種子填充算法遞歸算法可實(shí)現(xiàn)如下：voidFloodFill4(intx,inty,intoldColor,intnewColor){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);FloodFill4(x+1,y,oldColor,newColor);}}/*endofFloodFill4() */2024年10月23日計(jì)算機(jī)圖形學(xué)53種子填充算法-邊界表示的4連通區(qū)域voidBoundaryFill4(intx,inty,intboundaryColor,intnewColor){ intcolor; color=GetPixel(x,y); if((color!=boundaryColor)&&(color!=newColor)) { PutPixel(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() */2024年10月23日計(jì)算機(jī)圖形學(xué)54種子填充算法該算法也可以填充有孔區(qū)域。缺點(diǎn)：(1)有些象素會(huì)入棧多次，降低算法效率；棧結(jié)構(gòu)占空間。(2)遞歸執(zhí)行，算法簡(jiǎn)單，但效率不高，區(qū)域內(nèi)每一象素都引起一次遞歸，進(jìn)/出棧，費(fèi)時(shí)費(fèi)內(nèi)存。解決方法改進(jìn)算法，減少遞歸次數(shù)，提高效率。解決方法是用掃描線填充算法2024年10月23日計(jì)算機(jī)圖形學(xué)553.4.2.2掃描線種子算法（四連通）目標(biāo)：減少遞歸層次適用于邊界表示的4連通區(qū)域算法思想：在任意不間斷區(qū)間中只取一個(gè)種子像素（不間斷區(qū)間指在一條掃描線上一組相鄰元素），填充當(dāng)前掃描線上的該段區(qū)間；然后確定與這一區(qū)段相鄰的上下兩條掃描線上位于區(qū)域內(nèi)的區(qū)段，并依次把它們保存起來(lái)，反復(fù)進(jìn)行這個(gè)過(guò)程，直到所保存的個(gè)區(qū)段都填充完畢。2024年10月23日計(jì)算機(jī)圖形學(xué)56掃描線填充算法(1)初始化：堆棧置空。將種子點(diǎn)（x，y）入棧。(2)出棧：若?？談t結(jié)束。否則取棧頂元素（x，y），以y作為當(dāng)前掃描線。(3)填充并確定種子點(diǎn)所在區(qū)段：從種子點(diǎn)（x，y）出發(fā)，沿當(dāng)前掃描線向左、右兩個(gè)方向填充，直到邊界。分別標(biāo)記區(qū)段的左、右端點(diǎn)坐標(biāo)為xl和xr。(4)并確定新的種子點(diǎn)：在區(qū)間[xl，xr]中檢查與當(dāng)前掃描線y上、下相鄰的兩條掃描線上的象素。若存在非邊界、未填充的象素，則把每一區(qū)間的最右象素作為種子點(diǎn)壓入堆棧，返回第（2）步。上述算法對(duì)于每一個(gè)待填充區(qū)段，只需壓棧一次