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

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

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

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

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

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

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

7、 掃描線多邊形區(qū)域填充算法是按掃描線順序，計(jì)算掃描線與多邊形的相交區(qū)間，再用要求的顏色顯示這些區(qū)間的象素，即完成填充工作。區(qū)間的端點(diǎn)可以通過計(jì)算掃描線與多邊形邊界線的交點(diǎn)獲得。對(duì)于一條掃描線，多邊形的填充過程可以分為四個(gè)步驟：（1）求交：計(jì)算掃描線與多邊形各邊的交點(diǎn)；（2）排序：把所有交點(diǎn)按x值遞增順序排序；（3）配對(duì)：第一個(gè)與第二個(gè)，第三個(gè)與第四個(gè)等等；每對(duì)交點(diǎn)代表掃描線與多邊形的一個(gè)相交區(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中的接點(diǎn)順序填充。 掃描線填充算法的目標(biāo)是減少遞歸層次。步驟是填充并確定種段；初始化：將種子區(qū)段壓入堆棧；出棧：如果堆棧為空，則算法結(jié)束；否則取棧頂元素 (y, xLeft, xRight)，以縱坐標(biāo)為 y 的掃描線為當(dāng)前掃描線，xLeft, yLeft為搜索區(qū)間；填充并確定新的區(qū)段。 因此，掃描線多邊形區(qū)域填充算法的基本原理是，待填充區(qū)域按y方向(x方向亦可)掃描線順序掃描生成。具體實(shí)現(xiàn)時(shí)，首先按掃描線順序，計(jì)算掃描線與多邊形的相交區(qū)間；再用指定的顏色填充這些區(qū)間內(nèi)的像素，即

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

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

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

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

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

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

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

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

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

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

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

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

21、），（40,30）這十個(gè)點(diǎn)作為五角星的十個(gè)點(diǎn)，利用掃描線算法將這個(gè)五角星進(jìn)行填充。 3.2畫五角星圖形 (1)五角星圖形  (2)五角星的邊表  構(gòu)造ET表算法描述如下：void CreatET(Edge *et,struct pointtype p)     /*根據(jù)頂點(diǎn)數(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;      /*確定上一點(diǎn)的坐標(biāo)及下一點(diǎn)的坐標(biāo)，考慮數(shù)組的首尾點(diǎn)*/        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)相對(duì)應(yīng)活化邊表（a）y=0對(duì)應(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ù)頂點(diǎn)數(shù)組構(gòu)造ET表*/void EdgeInAel(Edge *ael,Edge *edge);        /*ET表中某邊edge插入至AEL表中，并排序，x相同時(shí)用下一點(diǎn)x+delta判斷*/void EdgeOutAel(Edge *ael,int y);               /*刪除AEL中

27、y=ymax的邊，并同時(shí)修改每邊的delta值*/  (5) 頂點(diǎn)交點(diǎn)的計(jì)數(shù)問題  （6）對(duì)AEL中的邊兩兩配對(duì)，（1和2為一對(duì)，3和4為一對(duì)，） （7）如果ET中的第y類非空，則將其中的結(jié)點(diǎn)插入AET，形成新的AET表 （8）實(shí)現(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的最小序號(hào)*/    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、 /*奇偶計(jì)數(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      /*每?jī)纱芜叜嬀€一次并重新賦值開始*/        

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é)束語：這種方法省去了建立場(chǎng)景的幾何模型和