二維填充圖元生成

生成填充圖元的上機實習利用VC++，編程實現(xiàn)多邊形的填充地點：教五319時間：周一下午6-7節(jié)周二下午6-7節(jié)北大計算機系多媒體與人機交互第五章二維填充圖元生成 一般步驟確定那些像素位于填充圖元的內部；確定以什么顏色填充這些像素；北大計算機系多媒體與人機交互北大計算機系多媒體與人機交互5.1掃描轉換矩形5.2掃描轉換多邊形逐點判斷法、掃描線算法、邊緣填充算法5.3區(qū)域填充（種子填充法）

遞歸填充算法、掃描線算法5.4以圖像填充區(qū)域5.5字符的表示與輸出5.6混淆與反混淆主要內容北大計算機系多媒體與人機交互5.1掃描轉換矩形方法：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() */北大計算機系多媒體與人機交互問題：矩形是簡單的多邊形，那么為什么要單獨處理矩形？比一般多邊形可簡化計算。應用非常多，窗口系統(tǒng)。邊界如何處理？ 原則：左閉右開，下閉上開屬于誰？北大計算機系多媒體與人機交互5.2掃描轉換多邊形多邊形的表示方法頂點表示點陣表示掃描轉換多邊形：將頂點表示形式轉換成點陣表示形式三種方法：逐點判斷法；掃描線算法；邊緣填充法北大計算機系多媒體與人機交互voidFillPolygonPbyP(Polygon*P,intpolygonColor){intx,y;for(y=ymin;y<=ymax;y++)for(x=xmin;x<=xmax;x++) if(IsInside(P,x,y)) SetPixel(x,y,polygonColor); else SetPixel(x,y,backgroundColor);}/*endofFillPolygonPbyP() */#defineMAX100Typedefstruct{intPolygonNum;//多邊形頂點個數(shù) Pointvertexces[MAX];//多邊形頂點數(shù)組 }Polygon;//多邊形結構1、逐點判斷法逐個判斷繪圖窗口內的像素：北大計算機系多媒體與人機交互如何判斷點在多邊形的內外關系？1）射線法2）累計角度法3）編碼法IsInside(P,x,y)1）射線法步驟：從待判別點v發(fā)出射線求交點個數(shù)KK的奇偶性決定了點與多邊形的內外關系奇異情況處理射線與多邊形頂點相交時，如何算交點的個數(shù)北大計算機系多媒體與人機交互2）累計角度法步驟從V點向多邊形P頂點發(fā)出射線，形成有向角計算有向角的和，得出結論離散計算方法：編碼方法北大計算機系多媒體與人機交互3）編碼方法：累計角度方法的離散方法Step:a.預處理，測試點在邊上否？b.V為原點作局部坐標系,對象限按逆時針（或順時針）編碼；c.頂點編碼Ipi，d.邊編碼。PiPi+1:△PiPi+1=Ipi+1-Ipie.計算∑△PiPi+1（其中△PnPn+1=△PnP0)：若∑為0,V在P外； 若∑為+/-4，V在P內；逐點判斷法程序簡單，速度太慢，效率低。P0P1P2vv0123北大計算機系多媒體與人機交互2、掃描線算法目標：利用相鄰像素之間的連貫性，提高算法效率處理對象：非自交多邊形（邊與邊之間除了頂點外無其它交點）北大計算機系多媒體與人機交互基本原理一條掃描線與多邊形的邊有偶數(shù)個交點步驟(對于每一條掃描線):(1)求交點(2)交點排序(3)交點配對，填充區(qū)段。邊的連貫性（確定交點）第一類交點：位于同一條邊上的后繼交點（中點算法）第二類交點：新出現(xiàn)的邊與掃描線的交點（頂點即為交點）北大計算機系多媒體與人機交互交點的取整規(guī)則要求：使生成的像素全部位于多邊形之內用于線畫圖元掃描轉換的四舍五入原則導致部分像素位于多邊形之外，從而不可用規(guī)則如下假定非水平邊與掃描線y=e相交，交點的橫坐標為x規(guī)則(1)： x為小數(shù)時，即交點落于掃描線上兩個相鄰像素之間 (a)交點位于左邊之上，向右取整 (b)交點位于右邊之上，向左取整北大計算機系多媒體與人機交互規(guī)則(2)：

交點位于邊界上時，象素的取舍問題。

邊界象素：規(guī)定落在右上邊界的象素不予填充。

具體實現(xiàn)時，只要對掃描線與多邊形的相交區(qū)間左閉右開北大計算機系多媒體與人機交互規(guī)則(3)：

掃描線與多邊形的頂點相交時，交點的取舍，保證交點正確配對。解決方法： 檢查兩相鄰邊在掃描線的哪一側。

只要檢查頂點的兩條邊的另外兩個端點的Y值，兩個Y值中大于交點Y值的個數(shù)是0，1，2，來決定取0，1，2個交點。

北大計算機系多媒體與人機交互1）活化邊：與當前掃描線相交的邊。按交點x（x相同則按deltax）遞增順序存放在一個鏈表中；該鏈表稱作活化邊表（AEL)。-算法所涉及的數(shù)據(jù)結構：Ymax:與邊相交的最高掃描線號X：

在AEL中表示當前掃描線與邊的交點的x坐標；初值為邊的下端點的x坐標(存于ET中)?！鱔：邊的斜率的倒數(shù)Nextedge:指向下一條邊的指針AEL與ET的結點信息（p75）：typedefstruct{intymax; floatx,deltax; Edge*nextEdge; }Edge;P0P1P2P3P4P5P667北大計算機系多媒體與人機交互2）邊的分類表（ET）按照邊的下端點y坐標對非水平邊進行分類的指針數(shù)組。下端點y坐標值等于i的邊屬于第i類，同一類邊按x(x相同則按deltax）遞增的順序排列。typedefstruct{intymax; floatx,deltax; Edge*nextEdge; }Edge;

邊的分類表的作用是避免盲目求交。當處理一條掃描線時，為了求出它與多邊形邊的所有交點，必須將它與所有的邊進行求交測試。而實際上只有某幾條邊與該掃描線有交點。邊的分類表正是用來排除不必要的求交測試的。例如，P76圖4.17北大計算機系多媒體與人機交互算法1)、建立ET；2)、將掃描線縱坐標y的初值置為ET中非空元素的最小序號，如在上圖中，y=1；3)、置AEL為空；4)、執(zhí)行下列步驟直至ET和AEL都為空．a、如ET中的第y類非空，則將其中的所有邊取出并插入AEL中；b、如果有新邊插入AEL，則對AEL中各邊排序；c、對AEL中的邊兩兩配對，（1和2為一對，3和4為一對，…），將每對邊中x坐標按規(guī)則取整，獲得有效的填充區(qū)段，再填充．d、將當前掃描線縱坐標y值遞增1；e、將AEL中滿足y=ymax邊刪去（因為每條邊被看作下閉上開的）；f、對AEL中剩下的每一條邊的x遞增deltax，即x=x+deltax．北大計算機系多媒體與人機交互3、邊緣填充算法▼求余運算：假定A為一個正整數(shù)，則M的余定義為A–M,記為。計算機中取A為n位能表示的最大整數(shù)。即，A=0xFFFFFFFF▼由來：光柵圖形中，如果某區(qū)域已著上值為M的顏色值做偶數(shù)次求余運算，該區(qū)域顏色不變；而做奇數(shù)次求余運算，則該區(qū)域顏色變?yōu)橹禐?的顏色。這一規(guī)律應用于多邊形掃描轉換，就為邊緣填充算法。▼求余運算可用異或顯示模式實現(xiàn)。▼算法基本思想：對于每條掃描線和每條多邊形邊的交點，將該掃描線上交點右方的所有像素取余。北大計算機系多媒體與人機交互算法(1)（以掃描線為中心的邊緣填充算法）a、將當前掃描線上的所有象素著上顏色；b、求余： for(i=0;i<=m;i++) 在當前掃描線上，從橫坐標為Xi的交點向右求余；

北大計算機系多媒體與人機交互算法(2)（以邊為中心的邊緣填充算法） a、將繪圖窗口的背景色置為； b、對多邊形的每一條非水平邊做： 從該邊上的每個象素開始向右求余；北大計算機系多媒體與人機交互邊緣填充算法適合用于具有幀緩存的圖形系統(tǒng)。處理后，按掃描線順序讀出幀緩存的內容，送入顯示設備。優(yōu)點：算法簡單缺點：對于復雜圖形，每一象素可能被訪問多次，輸入/輸出的量比掃描線算法大得多。北大計算機系多媒體與人機交互5.3區(qū)域填充區(qū)域：點陣表示的填充圖形，像素集合表示方法：內點表示、邊界表示內點表示枚舉出區(qū)域內部的所有像素內部的所有像素著同一個顏色邊界像素著不同的顏色邊界表示枚舉出邊界上所有的像素邊界上的所有像素著同一顏色內部像素著不同的顏色北大計算機系多媒體與人機交互區(qū)域填充–對區(qū)域重新著色的過程將指定的顏色從種子點擴展到整個區(qū)域的過程區(qū)域填充算法要求區(qū)域是連通的連通性

4連通、8連通4連通：8連通北大計算機系多媒體與人機交互4連通與8連通區(qū)域的區(qū)別連通性：4連通可看作8連通區(qū)域，但對邊界有要求對邊界的要求北大計算機系多媒體與人機交互邊界表示的4連通區(qū)域voidBoundaryFill4(intx,inty,intboundaryColor,intnewColor){ intcolor;

color=GetPixel(x,y); if((color!=boundaryColor)&&(color!=newColor)) { SetPixel(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); }}/*endofBoundaryFill4() */

1、遞歸填充算法北大計算機系多媒體與人機交互內點表示的4連通區(qū)域voidFloodFill4(intx,inty,intoldColor,intnewColor){ if(GetPixel(x,y)==oldColor) { SetPixel(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() */

取(x,y)為種子點北大計算機系多媒體與人機交互(x,y)北大計算機系多媒體與人機交互北大計算機系多媒體與人機交互北大計算機系多媒體與人機交互(1)有些像素會入棧多次，降低算法效率；棧結構占空間。(2)遞歸執(zhí)行，算法簡單，但效率不高，區(qū)域內每一象素都引起一次遞歸，進/出棧，費時費內存。改進算法，減少遞歸次數(shù)，提高效率。

方法之一使用掃描線填充算法；遞歸填充法的缺點：北大計算機系多媒體與人機交互2、掃描線算法掃描線算法目標：減少遞歸層次適用于內點表示的4連通區(qū)域基本過程：

當給定種子點時，首先填充種子點所在的掃描線上的位于給定區(qū)域的一個區(qū)段，然后確定與這一區(qū)段相通的上下兩條掃描線上位于給定區(qū)域內的區(qū)段，并依次保存下來。反復這個過程，直到填充結束。北大計算機系多媒體與人機交互1)、確定并填充種子區(qū)段；2)、初始化：將種子區(qū)段壓入堆棧；3)、如果堆棧為空，則算法結束；否則取棧頂元素（y,xLeft,xRight）出棧，以縱坐標=y的掃描線為當前掃描線，[xLeft,xRight]為搜索區(qū)間；4)、在上下相鄰的兩掃描線上，確定和填充新的區(qū)段，并壓入堆栽，重復(3)(4)。算法步驟北大計算機系多媒體與人機交互像素中的序號指它所在區(qū)段的堆棧位置北大計算機系多媒體與人機交互5.4以圖象填充區(qū)域填充方式：(1)位圖不透明：若像素對應的位圖單元為1，則以前景色顯示該像素；若為0，則以背景色顯示該像素；(2)位圖透明：若像素對應的位圖單元為1，則以前景色顯示該像素；若為0，則不做任何處理。(3)按像素圖方式填充北大計算機系多媒體與人機交互基本問題關鍵是建立區(qū)域與圖像間的對應關系1：建立整個繪圖空間與圖像空間映射適用：動畫中漫游圖像北大計算機系多媒體與人機交互2：建立區(qū)域局部坐標空間與圖像空間的映射適用：圖像作為區(qū)域表面屬性的情況。北大計算機系多媒體與人機交互5.5字符的表示與輸出 點陣字符 矢量字符自學！北大計算機系多媒體與人機交互

5.6.1混淆現(xiàn)象 5.6.2反混淆方法

非加權區(qū)域采樣 加權區(qū)域采樣5.6 反混淆方法北大計算機系多媒體與人機交互5.6.1混淆現(xiàn)象混淆：用離散量(像素)表示連續(xù)的量(圖形)而引起的失真，叫混淆或叫走樣(aliasing)。光柵圖形的混淆現(xiàn)象階梯狀邊界；圖形細節(jié)失真；狹小圖形遺失：動畫序列中時隱時現(xiàn)，產生閃爍。北大計算機系多媒體與人機交互混淆現(xiàn)象（1/3）不光滑(階梯狀）的圖形邊界北大計算機系多媒體與人機交互混淆現(xiàn)象（2/3）圖形細節(jié)失真北大計算機系多媒體與人機交互混淆現(xiàn)象（3/3）狹小圖形的遺失與動態(tài)圖形的閃爍北大計算機系多媒體與人機交互什么是反混淆在圖形顯示過程中，用于減少或消除混淆現(xiàn)象的方法1）提高分辨率方法 2）非加權區(qū)域采樣 3）加權區(qū)域采樣

5.6.2反混淆方法北大計算機系多媒體與人機交互1、提高分辨率的反混淆方法 方法簡單，但代價非常大。

顯示器的水平、豎直分辯率各提高一倍，則顯示器的點距減少一倍，幀緩存容量則增加到原來的4倍，而掃描轉換同樣大小的圖元卻要花4倍時間。北大計算機系多媒體與人機交互2、非加權區(qū)域采樣方法方法由來兩點假設1、數(shù)學上，象素是抽象的點，它的面積為0，它的亮度由覆蓋該點的圖形的亮度所決定；2、直線段是數(shù)學上抽象直線段，它的寬度為0?，F(xiàn)實像素的面積不為0；直線段的寬度至少為1個像素；假設與現(xiàn)實的矛盾是導致混淆出現(xiàn)的原因之一北大計算機系多媒體與人機交互2、非加權區(qū)域采樣方法解決方法：改變直線段模型，由此產生算法方法步驟：1、將直線段看作具有一定寬度的狹長矩形；2、當直線段與某象素有交時，求出兩者相交區(qū)域的面積；3、根據(jù)相交區(qū)域的面積，確定該象素的亮度值

關鍵：如何計算這個面積？北大計算機系多媒體與人機交互非加權區(qū)域采樣方法--計算相交區(qū)域的面積DD.m面積=(m*D*D)/2D------m像素實際顯示的灰度值==所得面積*該像素的最大灰度值北大計算機系多媒體與人機交互反混淆方法求相交區(qū)域的近似面積的離散計算方法1、將屏幕象素分割成n個更小的子象素；2、計算中心點落在直線段內的子象素的個數(shù)，記為k，3、k/n為線段與象素相交區(qū)域面積的近似值目的：簡化計算n=16,k=3近似面積=3/16北大計算機系多媒體與人機交互方法性質：非加權區(qū)域采樣方法1）直線段對一個像素亮度的貢獻與兩者相交區(qū)域的面積成正比，從而和像素中心點距直線段的距離成反比(因為像素中心點距直線段距離越元，相交區(qū)域的面積越?。?）當直線段和某個像素不相交時，它對該像素的亮度無影響；3）相同面積的相交區(qū)域對像素的亮度貢獻相同，而與這個相交區(qū)域落在像素內的位置無關。北大計算機系多媒體與人機交互3、加權區(qū)域采樣方法改進非加權區(qū)域采樣方法的第3條性質：相交區(qū)域對象素亮度的貢獻依賴于該區(qū)域與象素中心的距離北大計算機系多媒體與人機交互加權區(qū)域采樣方法權函數(shù)W(x,y)以象素A的中心