多邊形的掃描轉(zhuǎn)換與區(qū)域填充

1、多邊形的掃描轉(zhuǎn)換與區(qū)域填充在計算機圖形學中，多邊形有兩種重要的表示方法：頂點表示和點陣表示。頂點表示是用多邊形的頂點序列來表示多邊形。這種表示直觀、幾何意義強、占內(nèi)存少，易于進行幾何變換，但由于它沒有明確指出哪些象素在多邊形內(nèi)，故不能直接用于面著色；點陣表示是用位于多邊形內(nèi)的象素集合來刻畫多邊形。這種表示丟失了許多幾何信息，但便于幀緩沖器表示圖形，是面著色所需要的圖形表示形式。光柵圖形的一個基本問題是把多邊形的頂點表示轉(zhuǎn)換為點陣表示，這種轉(zhuǎn)換稱為多邊形的掃描轉(zhuǎn)換。    區(qū)域填充則是指先將在點陣表示的多邊形區(qū)域內(nèi)的一點（稱為種子點）賦予指定的顏色和灰度，然后將這種

2、顏色和灰度擴展到整個區(qū)域內(nèi)的過程。多邊形的掃描轉(zhuǎn)換多邊形掃描轉(zhuǎn)換算法對多邊形的形狀沒有限制，但多邊形的邊界必須時封閉的，且不自交。我們可以將多邊形分為三種：凸多邊形、凹多邊形、含內(nèi)環(huán)的多邊形。所謂凸多邊形是指任意兩頂點間的連線均在多邊形內(nèi)；凹多邊形是指任意兩頂點間的連線有不在多邊形內(nèi)的部分；而含內(nèi)環(huán)的多邊形則是指多邊形內(nèi)再套有多邊形，多邊形內(nèi)的多邊形也叫內(nèi)環(huán)，內(nèi)環(huán)之間不能相交。多邊形的掃描轉(zhuǎn)換與區(qū)域填充掃描線算法：掃描線算法是按掃描線順序，計算掃描線與多邊形的相交區(qū)間，再用要求的顏色顯示這些區(qū)間的象素，完成轉(zhuǎn)換工作。區(qū)間的端點可以通過計算掃描線與多邊形邊界線的交點獲得。對于一條掃描線，多邊形的

3、掃描轉(zhuǎn)換過程可以分為四個步驟： （1）求交：計算掃描線與多邊形各邊的交點；（2）排序：把所有交點按x值遞增順序排序；（3）配對：第一個與第二個，第三個與第四個等等；每對交點代表掃描線與多邊形的一個相交區(qū)間，（4）著色：把相交區(qū)間內(nèi)的象素置成多邊形顏色，把相交區(qū)間外的象素置成背景色。圖2.3.2 一個多邊形與若干掃描線    為了提高效率，在處理一條掃描線時，僅對與它相交的多邊形的邊進行求交運算。我們把與當前掃描線相交的邊稱為活性邊，并把它們按與掃描線交點x坐標遞增的順序存放在一個鏈表中，稱此鏈表為活性邊表(AET)。 (a)掃描線6的活性邊表(b)掃描線7的活性邊

4、表圖2.3.3活性邊表(AET)     假定當前掃描線與多邊形某一條邊的交點的橫坐標為x，則下一條掃描線與該邊的交點不必要重計算，只要加一個增量x即可，下面，我們推導這個結(jié)論。     設(shè)該邊的直線方程為：ax+by+c=0，當前掃描線及下一條掃描線與邊的交點分別為(xi,yi)、(xi+1,yi+1)，則：    axi+byi+c=0    axi+1+byi+1+c=0          

5、   其中x=-b/a 為常數(shù)，    另外使用增量法計算時，我們需要知道一條邊何時不再與下一條掃描線相交，以便及時把它從活性邊表中刪除出去。綜上所述，活性邊表的結(jié)點應為對應邊保存如下內(nèi)容：第1項存當前掃描線與邊的交點坐標x值；第2項存從當前掃描線到下一條掃描線間x的增量Dx；第3項存該邊所交的最高掃描線號ymax。   為了方便活性邊表的建立與更新，我們?yōu)槊恳粭l掃描線建立一個新邊表（NET）,存放在該掃描線第一次出現(xiàn)的邊。也就是說，若某邊的較低端點為ymin，則該邊就放在掃描線ymin的新邊表中。圖2.3.4 上圖所示各條

6、掃描線的新邊表NET算法過程：void polyfill (polygon, color)int color;多邊形 polygon; for (各條掃描線i )  初始化新邊表頭指針NET i；    把y min = i 的邊放進邊表NET i;       y = 最低掃描線號；   初始化活性邊表AET為空；   for (各條掃描線i )    把新邊表NETi中的邊結(jié)點用插入排序法插入AET表，使之按x坐標遞增順序排列； &

7、#160;    遍歷AET表，把配對交點區(qū)間(左閉右開)上的象素(x, y)，用drawpixel (x, y, color) 改寫象素顏色值；      遍歷AET表，把y max= i 的結(jié)點從AET表中刪除，并把y max > i結(jié)點的x值遞增D x；      若允許多邊形的邊自相交，則用冒泡排序法對AET表重新排序；     /* polyfill */掃描線與多邊形頂點相交時，必須正確地取舍交點，如圖2.3.5所示。·   掃描線與多邊形相交的邊分別位于掃描線的兩側(cè)，則計一個交點，如點P5，P6。·   掃描線與多邊形相交的邊分別位于掃描線同側(cè)，且 yi<yi-1，yi<yi+1，則計2個交點(填色)，如P2。若 yi>yi-1，yi>yi+1，則計0個交點(不填色)，如P1。·   掃描線與多