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

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

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

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

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

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

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

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