圖形學課件第四講 多變形填充

滁州學院國土信息工程系主講孫勇Email：sunyong_cug@163.com計算機圖形學第四章多邊形的掃描轉換與區(qū)域填充4.1多邊形掃描轉換4.2區(qū)域填充4.1多邊形的掃描轉換與區(qū)域填充多邊形有兩種重要的表示方法：頂點表示和點陣表示。多邊形的掃描轉換:把多邊形的頂點表示轉換為點陣表示。區(qū)域可采用內(nèi)點表示和邊界表示兩種表示形式。區(qū)域填充:指先將區(qū)域的一點賦予指定的顏色，然后將該顏色擴展到整個區(qū)域的過程。多邊形分為凸多邊形、凹多邊形、含內(nèi)環(huán)的多邊形。4.1.1多邊形的掃描轉換掃描線算法基本思想：按掃描線順序，計算掃描線與多邊形的相交區(qū)間，再用要求的顏色顯示這些區(qū)間的象素，即完成填充工作。對于一條掃描線填充過程可以分為四個步驟：（1）求交（2）排序（3）配對（4）填色判斷任意點是否在多邊形內(nèi)算法思想

從該點（x,y）向（—∞,y）引直線，并計算該線與多邊形的交點數(shù)n(自左向右算起)if(n%2==0){則（x,y）在多邊形外}else{則（x,y）在多邊形內(nèi)}掃描線與多邊形的頂點或邊界相交時，必須正確的交點的取舍。只需檢查頂點的兩條邊的另外兩個端點的y值。按這兩個y值中大于交點y值的個數(shù)是0,1,2來決定。實際上將多邊形的每條邊與所有掃描線都求交點沒有必要的。因為可能大多數(shù)掃描線與多邊形根本不相交。為了提高算法效率，應只處理與多邊形相交的那些掃描線，同時，交點的計算可以通過增量法來實現(xiàn)掃描線填色法

一個多邊形與若干掃描線

數(shù)據(jù)結構活性邊表(AET)：把與當前掃描線相交的邊稱為活性邊，并把它們按與掃描線交點x坐標遞增的順序存放在一個鏈表中結點內(nèi)容x：當前掃描線與邊的交點坐標△x：從當前掃描線到下一條掃描線間x的增量ymax：該邊所交的最高掃描線號ymax新邊表（NET）： 存放在該掃描線第一次出現(xiàn)的邊。若某邊的較低端點為ymin，則該邊就放在掃描線ymin的新邊表中 上圖所示各條掃描線的新邊表NET假定當前掃描線與多邊形某一條邊的交點的x坐標為x，則下一條掃描線與該邊的交點不要重計算，只要加一個增量△x。設該邊的直線方程為：ax+by+c=0；若y＝y(tǒng)i，x=xi；則當y=yi+1時，其中為常數(shù)FDCEAB975312468多邊形掃描轉換算法過程(偽代碼)voidpolyfill(polygon,color)intcolor;多邊形polygon;{for(各條掃描線i) {初始化新邊表頭指針NET[i]；把ymin=i的邊放進邊表NET[i];}y=最低掃描線號；初始化活性邊表AET為空；for(各條掃描線i){

把新邊表NET[i]中的邊結點用插入排序法插入AET表，使之按x坐標遞增順序排列；遍歷AET表，把配對交點區(qū)間(左閉右開)上的象素(x,y)，用drawpixel(x,y,color)改寫象素顏色值；遍歷AET表，把ymax=i的結點從AET表中刪除，并把ymax>i結點的x值遞增

x；若允許多邊形的邊自相交，則用冒泡排序法對AET表重新排序；}}/*polyfill*/邊界標志算法基本思想：幀緩沖器中對多邊形的每條邊進行直線掃描轉換，亦即對多邊形邊界所經(jīng)過的象素打上標志。然后再采用和掃描線算法類似的方法將位于多邊形內(nèi)的各個區(qū)段著上所需顏色。使用一個布爾量inside來指示當前點是否在多邊形內(nèi)的狀態(tài)。算法過程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); }}用軟件實現(xiàn)時，掃描線算法與邊界標志算法的執(zhí)行速度幾乎相同，但由于邊界標志算法不必建立維護邊表以及對它進行排序，所以邊界標志算法更適合硬件實現(xiàn)，這時它的執(zhí)行速度比有序邊表算法快一至兩個數(shù)量級。2.3.2區(qū)域填充算法區(qū)域指已經(jīng)表示成點陣形式的填充圖形，它是象素的集合。區(qū)域可采用內(nèi)點表示和邊界表示兩種表示形式。區(qū)域可分為4向連通區(qū)域和8向連通區(qū)域。區(qū)域填充指先將區(qū)域的一點賦予指定的顏色，然后將該顏色擴展到整個區(qū)域的過程。區(qū)域填充算法要求區(qū)域是連通的4向連通區(qū)域和8向連通區(qū)域

四個方向運動八個方向運動四連通區(qū)域八連通區(qū)域區(qū)域填充的遞歸算法內(nèi)點表示的4連通區(qū)域的遞歸填充算法:voidFloodFill4(intx,inty,intoldcolor,intnewcolor){if(getpixel(x,y)==oldcolor)//屬于區(qū)域內(nèi)點oldcolor { drawpixel(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);}}邊界表示的4連通區(qū)域的遞歸填充算法:voidBoundaryFill4(intx,inty,intboundarycolor,intnewcolor){intcolor; if(color!=newcolor&&color!=boundarycolor) { drawpixel(x,y,newcolor); BoundaryFill4(x,y+1,boundarycolor,newcolor); BoundaryFill4(x,y-1,boundarycolor,newcolor); BoundaryFill4(x-1,y,boundarycolor,newcolor); BoundaryFill4(x+1,y,boundarycolor,newcolor);}}區(qū)域填充的掃描線算法算法步驟：首先填充種子點所在掃描線上的位于給定區(qū)域的一個區(qū)段然后確定與這一區(qū)段相連通的上、下兩條掃描線上位于給定區(qū)域內(nèi)的區(qū)段，并依次保存下來。反復這個過程，直到填充結束。(1)初始化：堆棧置空。將種子點（x，y）入棧。(2)出棧：若?？談t結束。否則取棧頂元素（x，y），以y作為當前掃描線。(3)填充并確定種子點所在區(qū)段：從種子點（x，y）出發(fā)，沿當前掃描線向左、右兩個方向填充，直到邊界。分別標記區(qū)段的左、右端點坐標為xl和xr。(4)并確定新的種子點：在區(qū)間[xl，xr]中檢查與當前掃描線y上、下相鄰的兩條掃描線上的象素。若存在非邊界、未填充的象素，則把每一區(qū)間的最右象素作為種子點壓入堆棧，返回第（2）步。上述算法對于每一個待填充區(qū)段，只需壓棧一次；因