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

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

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

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

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

x：當前掃描線與邊的交點

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

x：掃描線與該邊的初始交點

dx：x的增量

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

）兩部分組成。表結構NET和AET中的基本元素為多邊形的邊。邊的結構由以下四個域組成：

ymax：邊的上端點的y坐標；

x：在NET中表示邊的最低點的x坐標，在AET中則表示邊與掃描線的交點的坐標；

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

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

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

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

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

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