用掃描線算法實現(xiàn)多邊形填充

1、計算機圖形學(xué)論文基于掃描線的區(qū)域填充算法姓 名： 魏艷娜學(xué) 號： 2012151115班 級： 201201基于掃描線的區(qū)域填充算法 摘 要 ：圖形通常由點、線、面、體等幾何元素和灰度、色彩、線型、線寬等非幾何屬性組成。從處理技術(shù)上來看，圖形主要分為兩類，一類是基于線條信息表示的，如工程圖、等高線地圖、曲面的線框圖等，另一類是明暗圖，也就是通常所說的真實感圖形。為此，必須建立圖形所描述的場景的幾何表示，再用某種光照模型，計算在假想的光源、紋理、材質(zhì)屬性下的光照明效果。計算機圖形學(xué)的內(nèi)容非常廣泛，如圖形硬件、圖形標(biāo)準(zhǔn)、圖形交互技術(shù)、光柵圖形生成算法，以及科學(xué)計算可視化、計算機動畫、虛擬現(xiàn)實等，這

2、里重點研究區(qū)域填充。 關(guān)鍵詞 ：計算機圖形學(xué)；區(qū)域填充；掃描線算法第1章  緒論 1.1研究的背景 在計算機中重現(xiàn)真實世界的場景叫做真實感繪制。真實感繪制的主要任務(wù)是模擬真實物體的物理屬性，簡單的說就是物體的形狀、光學(xué)性質(zhì)、表面的紋理和粗糙程度，以及物體間的相對位置、遮擋關(guān)系等等。實時的真實感繪制已經(jīng)成為當(dāng)前真實感繪制的研究熱點，而當(dāng)前真實感圖形實時繪制的兩個熱點問題則是物體網(wǎng)格模型的面片簡化和基于圖象的繪制。網(wǎng)格模型的面片簡化，就是指對網(wǎng)格面片表示的模型，在一定誤差的精度范圍內(nèi)，刪除點、邊、面，從而簡化所繪制場景的復(fù)雜層度，加快圖形繪制速度。IBR完全摒棄傳統(tǒng)的先建模，然后確定光源

3、的繪制的方法。它直接從一系列已知的圖象中生成未知視角的圖象。這種方法省去了建立場景的幾何模型和光照模型的過程，也不用進行如光線跟蹤等極費時的計算。該方法尤其適用于野外極其復(fù)雜場景的生成和漫游。 1.2研究的主要內(nèi)容及結(jié)構(gòu) 主要任務(wù)是實現(xiàn)多邊形區(qū)域掃描線填充的有序邊表算法，設(shè)計相關(guān)的數(shù)據(jù)結(jié)構(gòu)，并將實現(xiàn)的算法應(yīng)用于任意多邊形的填充，區(qū)域填充,指的是在輸出平面的閉合區(qū)域內(nèi)完整地填充某種顏色或圖案。以下所述及的區(qū)域填充算法或相關(guān)程序,主要針對顯示平面內(nèi)的區(qū)域而言。 區(qū)域填充的問題一般分兩大類,一是多邊形填充；一是種子填充；種子填充在學(xué)生掌握了“棧”這一抽象數(shù)據(jù)類型的實現(xiàn)方法的前提下,比較容易完成。而邊

4、標(biāo)志填充算法卻是介于這兩類之間,部分地具有它們的痕跡,算法思想巧妙,實現(xiàn)起來更容易。多邊形填充有一定難度，我們主要對多邊形的掃描線算法填充做一些探討，具體將以五角星為實例。第2章   理論綜述 2.1  區(qū)域填充的理論知識 2.1.1 區(qū)域填充的概念         將區(qū)域的邊界表示轉(zhuǎn)換為區(qū)域內(nèi)部象素表示的過程稱為區(qū)域填充。區(qū)域填充是計算機圖形學(xué)中的一個基本問題， 在計算機輔助設(shè)計、 真實感圖形顯示、 圖像分析等領(lǐng)域有著廣泛的應(yīng)用。區(qū)域填充算法是指給出一個區(qū)域的邊界，要求在邊

5、界范圍內(nèi)對所有像素單元賦予指定的顏色代碼。目前，區(qū)域填充算法中最常用的是多邊形填色，常用的多邊形填色算法有兩種： 一類是種子填充算法， 一類是掃描線填充算法。 研究如何用一種顏色或圖案來填充一個二維區(qū)域。一般來說，區(qū)域的封閉輪廓是簡單的多邊形。若輪廓線由曲線構(gòu)成，則可將曲線轉(zhuǎn)換成多條直線段順連而成，此時，區(qū)域輪廓線仍然是一種多邊形逼近。在計算機圖形學(xué)中，多邊形區(qū)域有兩種重要的表示方法：頂點表示和點陣表示。所謂頂點表示，即是用多邊形的頂點序列來表示多邊形。這種表示直觀、幾何意義強、占內(nèi)存少、易于進行幾何變換，但由于它沒有明確指出哪些像素在多邊形內(nèi)，故不能直接用于區(qū)域填充。所謂點陣表示，則是用位于

6、多邊形內(nèi)的像素集合來刻畫多邊形。這種表示丟失了許多幾何信息，但便于進行填充。根據(jù)區(qū)域的定義，可以采用不同的填充算法，其中最具代表性的是：適用于頂點表示的掃描線類算法和適應(yīng)于點陣表示的種子填充算法。 2.1.2 掃描線算法的描述 掃描線填充算法一般包括四個步驟：求交、排序、交點配對、區(qū)域填充。正確求得掃描線與區(qū)域填內(nèi)外輪廓線的交點是算法成敗的關(guān)鍵問題。另一方面，采用合適的數(shù)據(jù)結(jié)構(gòu)又可以簡化操作、提高算法的效率。本論文由于采用鏈表結(jié)構(gòu)記錄輪廓線和交點，無需焦點排序的過程，因而提高了算法效率。掃描線來源于光柵顯示器的顯示原理：對于屏幕上所有待顯示像素的信息，將這些信息按從上到下、自左至右的方式顯示。

7、 掃描線多邊形區(qū)域填充算法是按掃描線順序，計算掃描線與多邊形的相交區(qū)間，再用要求的顏色顯示這些區(qū)間的象素，即完成填充工作。區(qū)間的端點可以通過計算掃描線與多邊形邊界線的交點獲得。對于一條掃描線，多邊形的填充過程可以分為四個步驟：（1）求交：計算掃描線與多邊形各邊的交點；（2）排序：把所有交點按x值遞增順序排序；（3）配對：第一個與第二個，第三個與第四個等等；每對交點代表掃描線與多邊形的一個相交區(qū)間;（4）填色：把相交區(qū)間內(nèi)的象素置成多邊形顏色; 2.2  數(shù)據(jù)結(jié)構(gòu)與算法   2.2.1 掃描線多邊形填充算法的主要步驟 1.建立NET(NewEdgeList)； 2.

8、從最低掃描線開始到最高掃描線循環(huán)：  3.建立或調(diào)整AET(ActiveEdgeList)； 4.按照AET中的接點順序填充。 掃描線填充算法的目標(biāo)是減少遞歸層次。步驟是填充并確定種段；初始化：將種子區(qū)段壓入堆棧；出棧：如果堆棧為空，則算法結(jié)束；否則取棧頂元素 (y, xLeft, xRight)，以縱坐標(biāo)為 y 的掃描線為當(dāng)前掃描線，xLeft, yLeft為搜索區(qū)間；填充并確定新的區(qū)段。 因此，掃描線多邊形區(qū)域填充算法的基本原理是，待填充區(qū)域按y方向(x方向亦可)掃描線順序掃描生成。具體實現(xiàn)時，首先按掃描線順序，計算掃描線與多邊形的相交區(qū)間；再用指定的顏色填充這些區(qū)間內(nèi)的像素，即

9、完成這一條掃描線的填充工作。區(qū)間的端點可以通過計算掃描線與多邊形邊界的交點獲得。為了提高效率，在處理每一條掃描線時，僅對與它相交的多邊形的邊進行求交運算。我們把當(dāng)前掃描線相交的邊稱為活性邊(active edge)，并把它們按掃描線交點x坐標(biāo)遞增的順序存放在一個鏈表中，稱此鏈表為活性邊表(AET)。為了提高速度，假定當(dāng)前掃描線與多邊形某一條邊的交點的x坐標(biāo)為xi，則下一條掃描線與該點的交點不需要重新計算，而是通過增加一個增量x來獲得。對于直線ax+by+c=0,x=-b/a為常數(shù)。另外使用增量法計算時，還需要知道一條邊何時不再與下一條掃描線相交，以便及時把它從活性邊表中刪除出去。因此，活性邊表

10、結(jié)點的數(shù)據(jù)結(jié)構(gòu)應(yīng)保存如下內(nèi)容：第1項保存當(dāng)前掃描線與邊的交點坐標(biāo)x值；第2項保存從當(dāng)前掃描線到下一條掃描線間x的增量x；第3項保存該邊所交的最高掃描線好ymax。第4項存指向下一條邊的指針。  為了方便活性邊表的建立與更新，可為每一條掃描線建立一個邊表(ET)，存放在該掃描線第一次出現(xiàn)的邊。也就是說，若某邊的較低端點為ymin，則該邊就放在掃描線ymin的邊表中。  邊的分類表ET按照邊的下端點y坐標(biāo)對非水平邊進行分類的指針數(shù)組活化邊表AEL記錄與當(dāng)前掃描線相交的邊（交點）2.2.2邊的算法:typedef struct    int

11、 ymax;    float x,delta;    struct Edge *nextEdge;Edge;ymax:邊的上端點y坐標(biāo)x:在AEL中表示當(dāng)前掃描線與邊的交點的x坐標(biāo)，在ET中的初值為邊的下端點的x坐標(biāo)。deltax:邊的斜率的倒數(shù)nextEdge:指向下一條邊的指針。具體步驟如下:step1：把新邊表NETi中的邊結(jié)點，用插入排序法              插入活性邊表AET，使之按X坐

12、標(biāo)遞增順序排序；step2：遍歷AET表，把配對交點之間的區(qū)間(左閉右開)上的各象             素(X，Y)，用drawpixel(x,y,color)改寫象素顏色值；step3：遍歷AET表，把Ymax=i的結(jié)點從AET表中刪除，并把            Ymaxi的結(jié)果點的X值遞增X；step4：重復(fù)各掃描線2.2.3頂點交點的計數(shù)問題 : 

13、; 掃描線與多邊形頂點相交時，必須正確的進行交點個數(shù)計算，否則，在進行填充時會出現(xiàn)錯誤。掃描線與多邊形相交的邊分處掃描線的兩側(cè)，則計一個交點；掃描線與多邊形相交的邊分處掃描線同側(cè)，且yi<y(i-1),yi<y(i+1)，則計2個交點，若yi>y(i-1),yi>y(i+1)，則計0個交點；掃描線與多邊形邊界重合，則計1個交點。 是否正確求取掃描線與多邊形的交點是掃描線填充算法成敗的關(guān)鍵。研究發(fā)現(xiàn)，求取掃描線與多邊形的交點，既要利用邊界點的局部信息，又要利用一條掃描線上所有交點的全部信息。因此，論文的求交過程包括以下三步： 第一步：遍歷多邊形的邊一次，確定掃描

14、線縱坐標(biāo)的變化范圍ymin 和ymax,建立一個空間的掃描線交點鏈表； 第二步：遍歷多邊形區(qū)域的邊一次，根據(jù)每一邊界點與前驅(qū)、后繼之間的空間關(guān)系，初步求得各掃描線與邊的交點； 第三步：對第二步中求得的交點進行修剪，得到正確的掃描線交點表。  當(dāng)遍歷完區(qū)域多邊形輪廓線上的所有邊界點之后，求交過程的第二步結(jié)束，此時的掃描線活動邊表所記錄得是各條掃描線與區(qū)域輪廓線的交點。但是，此時還不能保證各條掃描線上的交點的數(shù)目為偶數(shù)，因此不能直接用于配對，必須對各個掃描線的交點鏈表進行修剪。  求交點過程的第三步對每一條掃描線的交點鏈表進行修剪，其目的是刪除那些由于出現(xiàn)“半交半切”

15、的情況而多算的交點，以便實現(xiàn)正確的配對。假設(shè)待修剪的掃描線為y=i,修正的過程為：1)以掃描線y=i的交點鏈表上的第一個交點Pi,l點作為起點；2)如果起點為空，轉(zhuǎn)5）結(jié)束；否則，按照從左到右的順序遍歷鏈表上的每一個點，如果遇到一個標(biāo)號非零的交點Pf(設(shè)其標(biāo)號值為lf),則從Pf的后繼開始，尋找第二個標(biāo)號非零的交點Ps,設(shè)其標(biāo)號值為ls,此時：如果lf與ls 符號相同，則轉(zhuǎn)3）；如果lf與ls符號相反，則轉(zhuǎn)4）；3)將Pf和Ps從交點鏈表中刪除，并以Ps 的后繼作為起點，轉(zhuǎn)2）；4)將Pf從交點鏈表中刪除，令Ps的標(biāo)號ls=0，并以Ps的后繼作為起點，轉(zhuǎn)2）；5)結(jié)束。 通過分析不難發(fā)現(xiàn)，對于

16、任意多邊形區(qū)域，經(jīng)上述算法所求的每一條掃描線與多邊形的交點數(shù)目為偶數(shù)，按照先后次序兩兩配對時，能確保交點之間的區(qū)域位于區(qū)域的內(nèi)部。 描述掃描線與多邊形交點的數(shù)據(jù)結(jié)構(gòu)定義一為：struct crosspointint x;/*交點的橫坐標(biāo)*/int y;/*交點的縱坐標(biāo)*/int l;/*交點的標(biāo)記*/crosspoint* pNextPoint;/*下一個交點*/ 采用單鏈表的方式記錄多邊形上的所有與掃描線的交點坐標(biāo)，下圖所示。圖中，E表示多邊形的邊，E ， =1,2,n。由于多邊形的外輪廓具有封閉性，所以鏈表的起點E 和終點E 也具有8-連通關(guān)系。對于鏈表中任意一個邊界點E ，定義E 為E

17、的前驅(qū)，E 為E 的后繼。后面將會看到，前去和后繼對于判斷交點的屬性是必不可少的。  把與當(dāng)前掃描線相交的邊稱為活性邊，并把它們按與掃描線交點x坐標(biāo)遞增的順序存放在一個鏈表中，稱此鏈表為活性邊表(AET)。  2.3掃描線的算法步驟： 1） 分析多邊形區(qū)域掃描線填充算法的原理，確定算法流程  初始化：構(gòu)造邊表ET，置AET表為空；  將第一個不空的ET表中的邊插入AET表；  由AET表取出交點進行配對（奇偶）獲得填充區(qū)間，依次對這些填充區(qū)間著色；  y=yi+1時，根據(jù)x=xi+1/k修改AET表所有結(jié)點中交點的

18、x坐標(biāo)。同時如果相應(yīng)的ET表不空，則將其中的結(jié)點插入AET表，形成新的AET表；  AET表不空，則轉(zhuǎn)（3），否則結(jié)束。 2） 編程  首先確定多邊形頂點和ET/AET表中結(jié)點的結(jié)構(gòu)  編寫鏈表相關(guān)操作（如鏈表結(jié)點插入、刪除和排序等）  根據(jù)1）中的算法結(jié)合上述已有的鏈表操作函數(shù)實現(xiàn)多邊形區(qū)域掃描線填充的主體功能  編寫主函數(shù)，測試該算法 3）算法描述：void polyfill (多邊形  polygon, 顏色 color) for (各條掃描線i )  初始化新邊表頭指針NET i；把ymin = i 的邊放

19、進邊表NET i;      y = 最低掃描線號；   初始化活性邊表AET為空；   for (各條掃描線i )    把新邊表NETi中的邊結(jié)點用插入排序法插入AET表，使之按x坐標(biāo)遞增順序排列；  遍歷AET表，把y max= i 的結(jié)點從AET表中刪除，并把y max > i結(jié)點的x值遞增D x；  若允許多邊形的邊自相交，則用冒泡排序法對AET表重新排序；      遍歷AET表

20、，把配對交點區(qū)間(左閉右開)上的象素(x, y)，用drawpixel (x, y, color) 改寫象素顏色值；     /* polyfill */第3章 多邊形填充實例 多邊形區(qū)域填充算法。多邊形區(qū)域填充主要有以下步驟：第一步是確定哪些像素位于圖元內(nèi)部，第二步是確定用何種顏色顯示那些像素。經(jīng)過上一章的知識，本章將以五角星為實例進行用掃描線算法的填充。 3.1用掃描線算法實現(xiàn)五角星填充   以（50,0），（60,30），（90,30），（70,45），（80,90），（50,60），（20,90），（30,45），（10,30

21、），（40,30）這十個點作為五角星的十個點，利用掃描線算法將這個五角星進行填充。 3.2畫五角星圖形 (1)五角星圖形  (2)五角星的邊表  構(gòu)造ET表算法描述如下：void CreatET(Edge *et,struct pointtype p)     /*根據(jù)頂點數(shù)組構(gòu)造ET表*/    int i,lasty,lastx,nextx,nexty,ymax,cy,cx;    Edge *pe;    for(i=0;i<EDGE

22、MAX;i+)        cy=pi.y;        cx=pi.x;      /*確定上一點的坐標(biāo)及下一點的坐標(biāo)，考慮數(shù)組的首尾點*/        if(0=i)lasty=pEDGEMAX-1.y;         

23、0;  lastx=pEDGEMAX-1.x;                else lasty=pi-1.y;            lastx=pi-1.x;                if

24、(EDGEMAX-1=i)            nexty=p0.y;            nextx=p0.x;                else nexty=pi+1.y;    

25、60;       nextx=pi+1.x;        五角星的邊的分類表：  (3)相對應(yīng)活化邊表（a）y=0對應(yīng)的活化邊表： （4）描述邊算法的數(shù)據(jù)結(jié)構(gòu)定義為：typedef struct    int ymax;    float x,delta;    struct Edge *nextEdge;Edge;void CreatET(Edge *

26、et,struct pointtype p);  /*根據(jù)頂點數(shù)組構(gòu)造ET表*/void EdgeInAel(Edge *ael,Edge *edge);        /*ET表中某邊edge插入至AEL表中，并排序，x相同時用下一點x+delta判斷*/void EdgeOutAel(Edge *ael,int y);               /*刪除AEL中

27、y=ymax的邊，并同時修改每邊的delta值*/  (5) 頂點交點的計數(shù)問題  （6）對AEL中的邊兩兩配對，（1和2為一對，3和4為一對，） （7）如果ET中的第y類非空，則將其中的結(jié)點插入AET，形成新的AET表 （8）實現(xiàn)五角星主要算法：void main()    int gd=DETECT,gm;    int i,y,ymax;      struct pointtype pEDGEMAX=50,0,60,30,90,30,70,45,80

28、,90,50,60,20,90,30,45,10,30,40,30,50,0;    Edge *etETMAX=0;    Edge *ael;    ael->nextEdge=NULL;    initgraph(&gd,&gm,"");    CreatET(et,p);    for(i=0;i<ETMAX;i+)    

29、;    if(eti!=NULL)            y=i;            break;            /*確定y的最小序號*/    ymax=p0.y;    f

30、or(i=0;i<EDGEMAX;i+)        if(pi.y>ymax)            ymax=pi.y;            /*確定ymax*/while(y<=ymax)        EtInAel(e

31、t,ael,y);        EdgeDraw(ael,y);        y+;        EdgeOutAel(ael,y);    填充算法如下：void EdgeDraw(Edge *ael,int y)        int counter=1;  

32、 /*奇偶計數(shù)器*/    int color,maxcolor;    Edge *pmove;    float xlast,xcur;    int ylast,ycur;    maxcolor=getmaxcolor();    pmove=ael->nextEdge;    while(pmove!=NULL)     

33、   if(counter%2=1)            xlast=pmove->x;                else      /*每兩次邊畫線一次并重新賦值開始*/        

34、;    xcur=pmove->x;            color=random(maxcolor);            setcolor(color);  line(int)xlast+1,y,(int)xcur,y);       

35、0;    xlast=0;            xcur=0;                counter+;        pmove=pmove->nextEdge;    結(jié)束語：這種方法省去了建立場景的幾何模型和