二維填充圖元生成

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

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

交點(diǎn)位于邊界上時(shí)，象素的取舍問(wèn)題。

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

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

掃描線與多邊形的頂點(diǎn)相交時(shí)，交點(diǎn)的取舍，保證交點(diǎn)正確配對(duì)。解決方法： 檢查兩相鄰邊在掃描線的哪一側(cè)。

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

北大計(jì)算機(jī)系多媒體與人機(jī)交互1）活化邊：與當(dāng)前掃描線相交的邊。按交點(diǎn)x（x相同則按deltax）遞增順序存放在一個(gè)鏈表中；該鏈表稱(chēng)作活化邊表（AEL)。-算法所涉及的數(shù)據(jù)結(jié)構(gòu)：Ymax:與邊相交的最高掃描線號(hào)X：

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

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

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

4連通、8連通4連通：8連通北大計(jì)算機(jī)系多媒體與人機(jī)交互4連通與8連通區(qū)域的區(qū)別連通性：4連通可看作8連通區(qū)域，但對(duì)邊界有要求對(duì)邊界的要求北大計(jì)算機(jī)系多媒體與人機(jī)交互邊界表示的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、遞歸填充算法北大計(jì)算機(jī)系多媒體與人機(jī)交互內(nèi)點(diǎn)表示的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)為種子點(diǎn)北大計(jì)算機(jī)系多媒體與人機(jī)交互(x,y)北大計(jì)算機(jī)系多媒體與人機(jī)交互北大計(jì)算機(jī)系多媒體與人機(jī)交互北大計(jì)算機(jī)系多媒體與人機(jī)交互(1)有些像素會(huì)入棧多次，降低算法效率；棧結(jié)構(gòu)占空間。(2)遞歸執(zhí)行，算法簡(jiǎn)單，但效率不高，區(qū)域內(nèi)每一象素都引起一次遞歸，進(jìn)/出棧，費(fèi)時(shí)費(fèi)內(nèi)存。改進(jìn)算法，減少遞歸次數(shù)，提高效率。

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

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

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

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

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

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

關(guān)鍵：如何計(jì)算這個(gè)面積？北大計(jì)算機(jī)系多媒體與人機(jī)交互非加權(quán)區(qū)域采樣方法--計(jì)算相交區(qū)域的面積DD.m面積=(m*D*D)/2D------m像素實(shí)際顯示的灰度值==所得面積*該像素的最大灰度值北大計(jì)算機(jī)系多媒體與人機(jī)交互反混淆方法求相交區(qū)域的近似面積的離散計(jì)算方法1、將屏幕象素分割成n個(gè)更小的子象素；2、計(jì)算中心點(diǎn)落在直線段內(nèi)的子象素的個(gè)數(shù)，記為k，3、k/n為線段與象素相交區(qū)域面積的近似值目的：簡(jiǎn)化計(jì)算n=16,k=3近似面積=3/16北大計(jì)算機(jī)系多媒體與人機(jī)交互方法性質(zhì)：非加權(quán)區(qū)域采樣方法1）直線段對(duì)一個(gè)像素亮度的貢獻(xiàn)與兩者相交區(qū)域的面積成正比，從而和像素中心點(diǎn)距直線段的距離成反比(因?yàn)橄袼刂行狞c(diǎn)距直線段距離越元，相交區(qū)域的面積越?。?；2）當(dāng)直線段和某個(gè)像素不相交時(shí)，它對(duì)該像素的亮度無(wú)影響；3）相同面積的相交區(qū)域?qū)ο袼氐牧炼蓉暙I(xiàn)相同，而與這個(gè)相交區(qū)域落在像素內(nèi)的位置無(wú)關(guān)。北大計(jì)算機(jī)系多媒體與人機(jī)交互3、加權(quán)區(qū)域采樣方法改進(jìn)非加權(quán)區(qū)域采樣方法的第3條性質(zhì)：相交區(qū)域?qū)ο笏亓炼鹊呢暙I(xiàn)依賴(lài)于該區(qū)域與象素中心的距離北大計(jì)算機(jī)系多媒體與人機(jī)交互加權(quán)區(qū)域采樣方法權(quán)函數(shù)W(x,y)以象素A的中心