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

多邊形的掃描轉(zhuǎn)換與區(qū)域填充第1頁(yè)，共61頁(yè)，2023年，2月20日，星期四2023/4/513.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)的灰度和顏色，通常稱(chēng)這種轉(zhuǎn)換為多邊形的掃描轉(zhuǎn)換。三種方法：掃描線算法邊填充算法邊界標(biāo)志法第2頁(yè)，共61頁(yè)，2023年，2月20日，星期四2023/4/52多邊形分類(lèi)多邊形分為凸多邊形、凹多邊形、含內(nèi)環(huán)的多邊形。第3頁(yè)，共61頁(yè)，2023年，2月20日，星期四2023/4/53多邊形表示多邊形的表示方法頂點(diǎn)表示點(diǎn)陣表示頂點(diǎn)表示：用多邊形頂點(diǎn)的序列來(lái)刻劃多邊形。直觀、幾何意義強(qiáng)、占內(nèi)存少；不能直接用于面著色。點(diǎn)陣表示：用位于多邊形內(nèi)的象素的集合來(lái)刻劃多邊形。失去了許多重要的幾何信息；便于運(yùn)用幀緩沖存儲(chǔ)器表示圖形，易于面著色。第4頁(yè)，共61頁(yè)，2023年，2月20日，星期四2023/4/543.4.1.1掃描線算法-x掃描線法掃描線算法目標(biāo)：利用相鄰像素之間的連貫性，提高算法效率處理對(duì)象：非自交多邊形（邊與邊之間除了頂點(diǎn)外無(wú)其它交點(diǎn)）第5頁(yè)，共61頁(yè)，2023年，2月20日，星期四2023/4/55步驟(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ū)間填充色。第6頁(yè)，共61頁(yè)，2023年，2月20日，星期四2023/4/56需要解決的幾個(gè)問(wèn)題掃描線與多邊形頂點(diǎn)相交時(shí)交點(diǎn)的取舍問(wèn)題多邊形邊界上像素點(diǎn)的取舍問(wèn)題水平邊的處理減少求交運(yùn)算問(wèn)題第7頁(yè)，共61頁(yè)，2023年，2月20日，星期四2023/4/57需要解決的幾個(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è)。第8頁(yè)，共61頁(yè)，2023年，2月20日，星期四2023/4/58具體實(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)。第9頁(yè)，共61頁(yè)，2023年，2月20日，星期四2023/4/59xy213456789111234567891011121012與多邊形頂點(diǎn)相交的交點(diǎn)的處理第10頁(yè)，共61頁(yè)，2023年，2月20日，星期四2023/4/510011110222

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

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

dx：x的增量

ymax：該邊的最大y值第20頁(yè)，共61頁(yè)，2023年，2月20日，星期四2023/4/520數(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：指向下一條邊的指針。第21頁(yè)，共61頁(yè)，2023年，2月20日，星期四2023/4/521ymaxx1/m(△x)nextymaxx1/m(△x)nextAET活性邊表NET新邊表X:邊的下端點(diǎn)的x坐標(biāo)X:邊與掃描線的交點(diǎn)的坐標(biāo)第22頁(yè)，共61頁(yè)，2023年，2月20日，星期四2023/4/522第23頁(yè)，共61頁(yè)，2023年，2月20日，星期四2023/4/523活性邊表的例子34-2P3P456.50.5^P3P2掃描線2AET指針620P4P5570.5^P3P2掃描線3AET指針(Ymax,x,Δx,next)36-2P3P4560.5^P3P2掃描線1AET指針第24頁(yè)，共61頁(yè)，2023年，2月20日，星期四2023/4/524活性邊表的例子620P4P557.50.5^P3P2掃描線4AET指針620P4P578-1^P2P1掃描線5AET指針724P5P178-1^P2P1掃描線6AET指針第25頁(yè)，共61頁(yè)，2023年，2月20日，星期四2023/4/525新邊表724^P5P178-1^P2P1620^P4P536-2P3P4560.5^P3P2^^^(Ymax,x,Δx,next)第26頁(yè)，共61頁(yè)，2023年，2月20日，星期四2023/4/526算法實(shí)現(xiàn)步驟

這樣，當(dāng)建立了邊的分類(lèi)表NET后，掃描線算法可按下列步驟進(jìn)行：（1）取掃描線縱坐標(biāo)y的初始值為NET中非空元素的最小序號(hào)。（2）將邊的活化鏈表AET設(shè)置為空。（3）按從下到上的順序?qū)v坐標(biāo)值為y的掃描線（當(dāng)前掃描線）執(zhí)行下列步驟，直到邊的分類(lèi)表ET和邊的活化鏈表都變成空為止。第27頁(yè)，共61頁(yè)，2023年，2月20日，星期四2023/4/527算法實(shí)現(xiàn)步驟1）如邊分類(lèi)表NET中的第y類(lèi)元素非空，則將屬于該類(lèi)的所有邊從AET中取出并插入邊的活化鏈表中，AET中的各邊按照x值（當(dāng)x值相等時(shí)，按Δx值）遞增方向排序。2）若相對(duì)于當(dāng)前掃描線，邊的活化鏈表AEL非空，則將AET中的邊兩兩依次配對(duì)，即1，2邊為一對(duì)，3，4邊為一對(duì)，依次類(lèi)推。每一對(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。第28頁(yè)，共61頁(yè)，2023年，2月20日，星期四2023/4/528掃描線算法特點(diǎn)：算法效率較高。缺點(diǎn)：對(duì)各種表的維持和排序開(kāi)銷(xiāo)太大，適合軟件實(shí)現(xiàn)而不適合硬件實(shí)現(xiàn)。第29頁(yè)，共61頁(yè)，2023年，2月20日，星期四2023/4/529掃描線算法問(wèn)題：如何處理多邊形的水平邊？如何修改掃描線算法，使它能處理邊自交的多邊形？第30頁(yè)，共61頁(yè)，2023年，2月20日，星期四2023/4/5303.4.1.3邊填充法算法簡(jiǎn)單，但對(duì)于復(fù)雜圖型，每一象素可能被訪問(wèn)多次算法過(guò)程：對(duì)于每一條掃描線和每條多邊形邊的交點(diǎn)（x1,y1）,將該掃描線上交點(diǎn)右方的所有像素取補(bǔ)，對(duì)多邊形的每條邊做同樣處理，多邊形順序隨意，如下圖：第31頁(yè)，共61頁(yè)，2023年，2月20日，星期四2023/4/531第32頁(yè)，共61頁(yè)，2023年，2月20日，星期四2023/4/5323.4.1.4柵欄填充算法為了減少重復(fù)計(jì)算，可采用柵欄算法，柵欄指的是一條過(guò)多邊形頂點(diǎn)且與掃描線垂直的直線。它把多邊形分為兩半。第33頁(yè)，共61頁(yè)，2023年，2月20日，星期四2023/4/533算法過(guò)程對(duì)于每個(gè)掃描線與多邊形的交點(diǎn)，將交點(diǎn)與柵欄之間的像素取補(bǔ)，若交點(diǎn)位于柵欄左邊，則將交點(diǎn)之右，柵欄之作的所有像素取補(bǔ)，若交點(diǎn)位于柵欄右邊，則將柵欄之左，交點(diǎn)之右的像素取補(bǔ)。第34頁(yè)，共61頁(yè)，2023年，2月20日，星期四2023/4/534柵欄算法圖示第35頁(yè)，共61頁(yè)，2023年，2月20日，星期四2023/4/5353.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不變。第36頁(yè)，共61頁(yè)，2023年，2月20日，星期四2023/4/536邊界標(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); }}第37頁(yè)，共61頁(yè)，2023年，2月20日，星期四2023/4/537邊界標(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ù)？第38頁(yè)，共61頁(yè)，2023年，2月20日，星期四2023/4/5383.4.2區(qū)域填充算法3.4.2.1種子填充法區(qū)域指已經(jīng)表示成點(diǎn)陣形式的填充圖形，它是象素的集合。區(qū)域填充指先將區(qū)域的一點(diǎn)賦予指定的顏色，然后將該顏色擴(kuò)展到整個(gè)區(qū)域的過(guò)程。區(qū)域填充算法要求區(qū)域是連通的第39頁(yè)，共61頁(yè)，2023年，2月20日，星期四2023/4/539區(qū)域填充表示方法：內(nèi)點(diǎn)表示、邊界表示內(nèi)點(diǎn)表示枚舉出區(qū)域內(nèi)部的所有像素內(nèi)部的所有像素著同一個(gè)顏色邊界像素著與內(nèi)部像素不同的顏色邊界表示枚舉出邊界上所有的像素邊界上的所有像素著同一顏色內(nèi)部像素著與邊界像素不同的顏色第40頁(yè)，共61頁(yè)，2023年，2月20日，星期四2023/4/540區(qū)域填充區(qū)域填充要求區(qū)域是連通的連通性：4連通、8連通4連通：8連通44p44(b)p的8-鄰接點(diǎn)88888p888(a)p的4-鄰接點(diǎn)

鄰接點(diǎn)的定義第41頁(yè)，共61頁(yè)，2023年，2月20日，星期四2023/4/541區(qū)域填充4連通與8連通區(qū)域的區(qū)別連通性：4連通可看作8連通區(qū)域，但對(duì)邊界有要求第42頁(yè)，共61頁(yè)，2023年，2月20日，星期四2023/4/542

區(qū)域的邊界表示和內(nèi)點(diǎn)表示(a)以邊界表示的4-連通區(qū)域(d)以?xún)?nèi)點(diǎn)表示的8-連通區(qū)域(b)以?xún)?nèi)點(diǎn)表示的4-連通區(qū)域(c)以邊界表示的8-連通區(qū)域第43頁(yè)，共61頁(yè)，2023年，2月20日，星期四2023/4/543四鄰域法不能正確填充一些特殊圖形第44頁(yè)，共61頁(yè)，2023年，2月20日，星期四2023/4/544種子填充算法-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)不是邊界色且未置成多邊形色，則把該象素入棧。第45頁(yè)，共61頁(yè)，2023年，2月20日，星期四2023/4/545種子填充算法-8鄰域棧結(jié)構(gòu)實(shí)現(xiàn)8-連通邊界填充算法的算法步驟為：種子象素入棧；當(dāng)棧非空時(shí)重復(fù)執(zhí)行如下三步操作：(1)棧頂象素出棧；(2)將出棧象素置成填充色；(3)按一定順序檢查出棧象素的8-鄰接點(diǎn)，若其中某個(gè)象素點(diǎn)不是邊界色且未置成多邊形色，則把該象素入棧。第46頁(yè)，共61頁(yè)，2023年，2月20日，星期四2023/4/546種子填充算法適合于內(nèi)點(diǎn)表示區(qū)域的填充算法設(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）將出棧象素置成多邊形色；（3）按上、下、左、右的順序檢查與出棧象素相鄰的四個(gè)象素，若其中某個(gè)象素不在邊界上且未置成多邊形色，則把該象素入棧。第47頁(yè)，共61頁(yè)，2023年，2月20日，星期四2023/4/547舉例以s1為種子，按照左、上、右、下順序入棧出棧，過(guò)程如下：第48頁(yè)，共61頁(yè)，2023年，2月20日，星期四2023/4/5484321096S1452378012345第49頁(yè)，共61頁(yè)，2023年，2月20日，星期四2023/4/54968454468422684533S1S16845568466S1S1123456789101168446886668498868499684977第50頁(yè)，共61頁(yè)，2023年，2月20日，星期四2023/4/550種子填充算法例：多邊形由P0P1P2P3P4構(gòu)成，P0(1,5)P1(5,5)P2(7,3)P3(7,1)P4(1,1)設(shè)種子點(diǎn)為（3，3），搜索的方向是上、下、左、右。依此類(lèi)推，最后像素被選中并填充的次序如圖中箭頭所示第51頁(yè)，共61頁(yè)，2023年，2月20日，星期四2023/4/551種子填充算法遞歸算法可實(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() */第52頁(yè)，共61頁(yè)，2023年，2月20日，星期四2023/4/552種子填充算法-邊界表示的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() */第53頁(yè)，共61頁(yè)，2023年，2月20日，星期四2023/4/553種子填充算法該算法也可以填充有孔區(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)算法，減少遞歸