《計(jì)算機(jī)圖形學(xué)基礎(chǔ)》課件第4章

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

4.2區(qū)域填充技術(shù)

4.3反走樣

習(xí)題4

4.1多邊形的掃描轉(zhuǎn)換

4.1.1多邊形的掃描轉(zhuǎn)換的定義

多邊形的掃描轉(zhuǎn)換算法對(duì)多邊形的形狀沒(méi)有限制，但多邊形的邊界必須是封閉的，且不自交。由于大多數(shù)圖形都是采用頂點(diǎn)序列表示的，而頂點(diǎn)表示又不能直接進(jìn)行顯示，因此，就必須將圖形從頂點(diǎn)表示轉(zhuǎn)換為點(diǎn)陣表示。多邊形的掃描轉(zhuǎn)換就是從多邊形的給定邊界出發(fā)，求出位于其內(nèi)部的各個(gè)像素，并給幀緩存器內(nèi)的各個(gè)對(duì)應(yīng)元素設(shè)置相應(yīng)的灰度和顏色。如圖4-1所示是多邊形的頂點(diǎn)表示。圖4-1多邊形的頂點(diǎn)表示多邊形的掃描轉(zhuǎn)換過(guò)程實(shí)際上是給多邊形包圍的區(qū)域著色的過(guò)程，是一種面著色的方法。運(yùn)用面著色方法可以使畫(huà)面明暗自然，色彩豐富，形象逼真。面著色圖形體現(xiàn)了光柵顯示系統(tǒng)的優(yōu)勢(shì)。將圖4-1轉(zhuǎn)換為點(diǎn)陣圖形，如圖4-2所示。圖4-2多邊形的點(diǎn)陣表示4.1.2逐點(diǎn)判斷算法(x掃描線(xiàn)算法)

對(duì)多邊形所圍成的區(qū)域進(jìn)行填充，就是要找出所有位于多邊形內(nèi)部的像素，并賦以適當(dāng)?shù)南袼刂?，產(chǎn)生面填充的圖形。多邊形區(qū)域具有內(nèi)部相鄰的像素空間連貫的特點(diǎn)，當(dāng)

一條掃描線(xiàn)穿過(guò)多邊形時(shí)，必然與多邊形的邊相交并有交點(diǎn)，依據(jù)交點(diǎn)可以確定哪些像素在區(qū)域內(nèi)。一般來(lái)講，這些像素在水平方向是相鄰、連續(xù)的，我們只要知道掃描線(xiàn)與多邊形的兩個(gè)交點(diǎn)，就能確定填充區(qū)間，知道哪些像素是要填充的。注意到在一般情況下，一條直線(xiàn)與任意封閉曲線(xiàn)相交時(shí)，總是從第一個(gè)交點(diǎn)進(jìn)入內(nèi)部，再?gòu)牡诙€(gè)交點(diǎn)退出，以后交替地進(jìn)入、退出，即奇數(shù)次交點(diǎn)進(jìn)入多邊形、偶數(shù)次交點(diǎn)退出多邊形，如圖4-3所示。這就是多邊形掃描轉(zhuǎn)換算法的基本思想，當(dāng)然還有一些特殊情況應(yīng)特殊處理。圖4-3掃描線(xiàn)與多邊形的交點(diǎn)逐點(diǎn)判斷算法的基本思想就是采用累計(jì)交點(diǎn)的方法進(jìn)行多邊形內(nèi)部像素點(diǎn)的判斷，若從一點(diǎn)出發(fā)的射線(xiàn)與多邊形邊界的交點(diǎn)個(gè)數(shù)為奇數(shù)，則該點(diǎn)位于多邊形內(nèi)，否則該點(diǎn)在多邊形外。

由于用于畫(huà)線(xiàn)圖元掃描轉(zhuǎn)換的四舍五入原則會(huì)導(dǎo)致部分像素位于多邊形之外，因而不可用。為了使生成的像素全部位于多邊形之內(nèi)，當(dāng)交點(diǎn)坐標(biāo)不是整數(shù)時(shí)，需要制定交點(diǎn)的取整規(guī)則。假定非水平邊與掃描線(xiàn)y=e相交，交點(diǎn)的橫坐標(biāo)為x，規(guī)則如下：

規(guī)則1：x為小數(shù)，即交點(diǎn)落于掃描線(xiàn)上兩個(gè)相鄰像素之間(如圖4-4所示)，若交點(diǎn)位于左邊，則向右取整；若交點(diǎn)位于右邊，則向左取整。圖4-4交點(diǎn)位于左、右邊之上規(guī)則2：邊界上像素的取舍問(wèn)題，避免填充擴(kuò)大化。對(duì)于邊界像素，規(guī)定落在右上邊界的像素不予填充。具體實(shí)現(xiàn)時(shí)，只要對(duì)掃描線(xiàn)與多邊形的相交區(qū)間左閉右開(kāi)(如圖4-5所示)即可。圖4-5邊界交點(diǎn)左閉右開(kāi)逐點(diǎn)判斷算法的步驟如下：

(1)確定多邊形所占有的最大掃描線(xiàn)數(shù)，得到多邊形頂點(diǎn)的最小和最大y值(ymin和ymax)。

(2)從y=ymin到y(tǒng)=ymax，每次用一條掃描線(xiàn)進(jìn)行填充。

(3)對(duì)一條掃描線(xiàn)填充的過(guò)程可分為四個(gè)步驟：

①求交：計(jì)算掃描線(xiàn)與多邊形各邊的交點(diǎn)；

②排序：把所有交點(diǎn)按遞增順序排列；

③交點(diǎn)配對(duì)：將奇數(shù)與偶數(shù)交點(diǎn)進(jìn)行配對(duì)，每對(duì)交點(diǎn)就代表掃描線(xiàn)與多邊形的一個(gè)相交區(qū)間；

④區(qū)間填色：把這些相交區(qū)間內(nèi)的像素置成不同于背景色的填充色。例如在圖4-3中，對(duì)掃描線(xiàn)y＝3，交點(diǎn)經(jīng)排序后表示為(2，4，7，9)，因此，對(duì)區(qū)間(2，4)和(7，9)進(jìn)行填充。

采用逐點(diǎn)判斷算法還要解決的一個(gè)問(wèn)題是掃描線(xiàn)與多邊形頂點(diǎn)相交的特殊情況，這時(shí)如果排序后交點(diǎn)表中的交點(diǎn)個(gè)數(shù)是奇數(shù)，填充就會(huì)出錯(cuò)。例如，圖4-3中的掃描線(xiàn)y＝1，y＝7等就是這種情況。以y＝1為例，它與多邊形所有各邊的交點(diǎn)排序后所得是(3，8)，其中兩個(gè)x坐標(biāo)為3，表明掃描線(xiàn)同時(shí)與多邊形的兩條邊在頂點(diǎn)相交。如果還是按區(qū)間填充，則需要填充的區(qū)域是(3，8)，這時(shí)就會(huì)發(fā)生填充錯(cuò)誤。上述問(wèn)題稱(chēng)為奇點(diǎn)問(wèn)題，其解決辦法是：當(dāng)頂點(diǎn)表現(xiàn)為局部極大或局部極小時(shí)，就看做是零個(gè)或兩個(gè)交點(diǎn)，否則看做一個(gè)。如果這個(gè)頂點(diǎn)的兩條邊同在掃描線(xiàn)的下面，這個(gè)頂點(diǎn)是局部極大，反之稱(chēng)這個(gè)頂點(diǎn)是局部極小。例如，在圖4-3中，與掃描線(xiàn)y＝1相交的兩個(gè)奇點(diǎn)都是極小點(diǎn)，交點(diǎn)個(gè)數(shù)算做零個(gè)。而與掃描線(xiàn)y＝7相交的奇點(diǎn)是非極值點(diǎn)，其交點(diǎn)個(gè)數(shù)算做一個(gè)。設(shè)inside(P，x，y)是驗(yàn)證點(diǎn)(x，y)是否在多邊形P內(nèi)的布爾函數(shù)。當(dāng)從(x，y)到(+∞，y)的射線(xiàn)與P的交點(diǎn)個(gè)數(shù)是奇數(shù)時(shí)，該函數(shù)取值為true，否則取值為false。設(shè)framebuffer是用以存放圖形的幀緩存器，framebuffer(x，y)對(duì)應(yīng)幀緩存器中的元素，用以存放屏幕上對(duì)應(yīng)像素的顏色值。設(shè)polygon-color是多邊形P的顏色值，background-color是背景色。逐點(diǎn)判斷算法可以采用下列程序表示：由上述程序可以看出，逐點(diǎn)判斷算法的特點(diǎn)是程序非常簡(jiǎn)單，易于實(shí)現(xiàn)。但由于運(yùn)行速度很慢，該算法并沒(méi)有實(shí)用價(jià)值。逐點(diǎn)判斷算法效率極低的原因在于，該算法需要孤立地考察各個(gè)像素與多邊形的內(nèi)外關(guān)系，使得大量像素都要一一判斷，每次判斷又要多次求交點(diǎn)，需要做大量的乘除運(yùn)算，花費(fèi)很多時(shí)間。4.1.3掃描線(xiàn)算法

掃描線(xiàn)算法是多邊形掃描轉(zhuǎn)換的常用方法。掃描線(xiàn)算法的處理對(duì)象是非自交多邊形(邊與邊之間除了頂點(diǎn)外無(wú)其他交點(diǎn))。圖4-6中(a)為非自交多邊形，(b)為自交多邊形。掃描線(xiàn)算法是多邊形掃描轉(zhuǎn)換的常用算法，與逐點(diǎn)判斷算法相比，掃描線(xiàn)算法充分利用了相鄰像素之間的連貫性，避免了對(duì)像素的逐點(diǎn)判斷和反復(fù)求交的運(yùn)算，達(dá)到了減少計(jì)算量和提高速度的目的。

開(kāi)發(fā)和利用相鄰像素之間的連貫性是光柵圖形算法研究的重要內(nèi)容。掃描轉(zhuǎn)換算法綜合利用了區(qū)域的連貫性、掃描線(xiàn)的連貫性和邊的連貫性等三種形式的連貫性。圖4-6非自交及自交多邊形

1.區(qū)域的連貫性

設(shè)多邊形P的頂點(diǎn)Pi=(xi，yi)，i=0，1，…，n，又設(shè)yi0，yi1，…，yin是各頂點(diǎn)Pi的坐標(biāo)yi的遞減數(shù)列，即yik≥yik+1，0≤k≤n－1。這樣，屏幕上位于y=yik和y=yik+1兩條掃描線(xiàn)之間的長(zhǎng)方形區(qū)域被多邊形P的邊分割成若干梯形(三角形可看做其中一底邊長(zhǎng)為零的梯形)，如圖4-7所示。圖4-7區(qū)域的連貫性從圖4-7中可以看出，區(qū)域的連貫性具有如下性質(zhì)：

(1)梯形的兩底邊分別在y=yik和y=yik+1兩條掃描線(xiàn)上，腰在多邊形P的邊上或在顯示屏幕的邊界上。

(2)這些梯形可分為兩類(lèi)：一類(lèi)位于多邊形P的內(nèi)部；另一類(lèi)在多邊形P的外部。

(3)兩類(lèi)梯形在長(zhǎng)方形區(qū)域{yik，yik+1}內(nèi)相間地排列，即相鄰的兩梯形必有一個(gè)在多邊形P內(nèi)，另一個(gè)在P外。

根據(jù)這些性質(zhì)，實(shí)際上只需知道該長(zhǎng)方形區(qū)域任一梯形內(nèi)一點(diǎn)關(guān)于多邊形P的內(nèi)外關(guān)系后，即可確定區(qū)域內(nèi)所有梯形關(guān)于P的內(nèi)外關(guān)系。

2.掃描線(xiàn)的連貫性

設(shè)e為一整數(shù)，yi0≥e≥yin。若掃描線(xiàn)y=e與多邊形P的Pi－1Pi相交，則記其交點(diǎn)的橫坐標(biāo)為xei?，F(xiàn)設(shè)xei1，xei2，xei3，…，xeil是該掃描線(xiàn)與P的邊界各交點(diǎn)橫坐標(biāo)的遞增序列，稱(chēng)此序列為交點(diǎn)序列，如圖4-8所示。

由區(qū)域的連貫性可知，此交點(diǎn)序列具有以下性質(zhì)：

(1)設(shè)L是偶數(shù)。

(2)在該掃描線(xiàn)上，只有區(qū)段(xeik，xeik+1)，k=1，3，5，…，L－1，位于多邊形P內(nèi)，其余區(qū)段都在P外。

以上性質(zhì)稱(chēng)為掃描線(xiàn)的連貫性，它是多邊形區(qū)域連貫性在一條掃描線(xiàn)上的反映。圖4-8掃描線(xiàn)的連貫性

3.邊的連貫性

設(shè)d為一整數(shù)，并且d=e－1，yi0≥d≥yin。設(shè)位于掃描線(xiàn)y=d上的交點(diǎn)序列為xdj1，xdj2，xdj3，…，xdjk。對(duì)于掃描線(xiàn)d、e的交點(diǎn)序列，若多邊形P的邊Pr－1Pr與掃描線(xiàn)y=e，y=d都相交，則交點(diǎn)序列中的對(duì)應(yīng)元素xer，xdr滿(mǎn)足下列關(guān)系：

其中，mr為邊Pr－1Pr的斜率。

從圖4-9中可以看出，可利用d的交點(diǎn)序列計(jì)算e的交點(diǎn)序列，則由區(qū)域的連貫性可知，d的交點(diǎn)序列和e的交點(diǎn)序列之間有以下關(guān)系：

(1)兩序列元素的個(gè)數(shù)相等。

(2)點(diǎn)(xeir，e)與點(diǎn)(xdjr，d)位于多邊形P的同一邊上，于是

這樣，運(yùn)用上述遞推關(guān)系式可直接由d的交點(diǎn)序列得到e的交點(diǎn)序列。以上性質(zhì)稱(chēng)為邊的連貫性，它是區(qū)域的連貫性在相鄰兩掃描線(xiàn)上的反映。圖4-9邊的連貫性

4.數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟

算法基本思想：取d=yin，容易求得掃描線(xiàn)y=d上的交點(diǎn)序列為xdj1，xdj2，…，xdjn，這一序列由位于掃描線(xiàn)y=d上的0多邊形P的頂點(diǎn)組成；由yin的交點(diǎn)序列開(kāi)始，根據(jù)多邊形的

邊的連貫性，按從上到下的順序求得各條掃描線(xiàn)的交點(diǎn)序列；根據(jù)掃描線(xiàn)的連貫性，可確定各條掃描線(xiàn)上位于多邊形P內(nèi)的區(qū)段，并表示成點(diǎn)陣形式。如果算法對(duì)每條掃描線(xiàn)與所有的邊求交點(diǎn)，則效率很低，因?yàn)橐粭l掃描線(xiàn)往往只和少數(shù)幾條邊相交。因此，如果只對(duì)與該掃描線(xiàn)相交的邊求交點(diǎn)，算法的效率將有很大的提高。如何判斷多邊形的一條邊與掃描線(xiàn)是否相交成為算法的關(guān)鍵。掃描線(xiàn)算法采用如下方法解決上述問(wèn)題：與當(dāng)前掃描線(xiàn)相交的邊稱(chēng)為活性邊(activeedge)，把它們按與掃描線(xiàn)交點(diǎn)x坐標(biāo)遞增的順序存入一個(gè)表中，稱(chēng)為邊的活化邊表(ActiveEdgeTable，AET)，它記錄了多邊形邊沿掃描線(xiàn)的交點(diǎn)序列。

經(jīng)過(guò)上述處理，掃描線(xiàn)算法只需對(duì)當(dāng)前掃描線(xiàn)的活化邊表作更新，即可得到下一條掃描線(xiàn)的活化邊表(可采用邊的連貫性計(jì)算下一條掃描線(xiàn)與邊的交點(diǎn))。設(shè)直線(xiàn)方程為ax+by+c=0，當(dāng)前交點(diǎn)坐標(biāo)為(xi，yi)，下一交點(diǎn)坐標(biāo)為(xi+1，yi+1)，則xi+1=xi+1/mr。

活化邊表中需要存放的信息如下：

x：當(dāng)前掃描線(xiàn)與邊的交點(diǎn)；

dx＝－b/a：從當(dāng)前掃描線(xiàn)到下一條掃描線(xiàn)之間的x增量；

ymax：邊所交的最高掃描線(xiàn)。

為了方便活化邊表的更新，先建立另一個(gè)表，稱(chēng)為邊表(EdgeTable,ET)，也叫邊的分類(lèi)表，邊表存放多邊形各邊的初始狀態(tài)。因此，掃描線(xiàn)算法中采用了較靈活的數(shù)據(jù)結(jié)構(gòu)。它由邊的分類(lèi)表(ET)和活化邊表(AET)兩部分組成。表結(jié)構(gòu)ET和AET中的基本元素為多邊形的邊。邊的結(jié)構(gòu)由以下四個(gè)域組成：

ymax：邊的上端點(diǎn)的y坐標(biāo)；

x：在ET中表示邊的下端點(diǎn)的x坐標(biāo)，在AET中為邊與掃描線(xiàn)的交點(diǎn)的坐標(biāo)；

Δx：斜率的倒數(shù)；

Next：指向下一條邊的指針。

邊的分類(lèi)表(ET)是按邊的下端點(diǎn)的y坐標(biāo)對(duì)非水平邊進(jìn)行分類(lèi)的指針數(shù)組。下端點(diǎn)的y坐標(biāo)的值等于i的邊歸入第i類(lèi)。有多少條掃描線(xiàn)，就設(shè)多少類(lèi)。同一類(lèi)中，各邊按x值(x值相等時(shí)，按Δx的值)遞增的順序排列成行。圖4-10為ET表的結(jié)構(gòu)，該表為靜態(tài)表，表示多邊形的結(jié)構(gòu)。而AET表是動(dòng)態(tài)表，其節(jié)點(diǎn)數(shù)據(jù)隨著多邊形掃描線(xiàn)的變動(dòng)而變動(dòng)，如圖4-11所示。圖4-10

ET表的結(jié)構(gòu)圖4-11

AET表的結(jié)構(gòu)這樣當(dāng)建立了邊的分類(lèi)表(ET)后，掃描線(xiàn)算法可按下列步驟進(jìn)行：

(1)取掃描線(xiàn)縱坐標(biāo)y的初始值為ET中非空元素的最小序號(hào)。

(2)將邊的活化邊表(AET)設(shè)置為空。

(3)按從下到上的順序?qū)v坐標(biāo)值為y的掃描線(xiàn)(當(dāng)前掃描線(xiàn))執(zhí)行下列步驟，直到邊的分類(lèi)表和活化邊表都變成空為止。

AET表的動(dòng)態(tài)更新步驟如下：

(1)如ET中的第y類(lèi)元素非空，則將屬于該類(lèi)的所有邊從ET中取出并插入邊的AET中，AET中的各邊按照x值(當(dāng)x值相等時(shí)，按Δx值)遞增方向排序。

(2)若相對(duì)于當(dāng)前掃描線(xiàn)，邊的AET非空，則將AET中的邊兩兩依次配對(duì)，即1、2邊為一對(duì)，3、4邊為一對(duì)，依次類(lèi)推。每一對(duì)邊與當(dāng)前掃描線(xiàn)的交點(diǎn)所構(gòu)成的區(qū)段位于多邊形內(nèi)，依次對(duì)這些區(qū)段上的點(diǎn)(像素)按多邊形屬性著色。

(3)將邊的AET中滿(mǎn)足y=ymax的邊刪去。

(4)將邊的AET中剩下的每一條邊的x域累加Δx，即x′=x+Δx。

(5)將當(dāng)前的掃描線(xiàn)的縱坐標(biāo)值y累加1，即y′=y+1。掃描轉(zhuǎn)換算法利用了掃描線(xiàn)的相關(guān)性和邊的相關(guān)性，極大地提高了效率。掃描線(xiàn)相關(guān)性指在一條掃描線(xiàn)上，相鄰的像素只有通過(guò)邊界線(xiàn)時(shí)才能從內(nèi)部變到外部或者從外部變到內(nèi)部。邊的相關(guān)性指對(duì)多邊形的每一條邊，相鄰的掃描線(xiàn)只有在通過(guò)線(xiàn)段的端點(diǎn)時(shí)才會(huì)改變與邊的相交情形。同時(shí)，這是一種非常有效的算法，它使所顯示的每—個(gè)像素只訪(fǎng)問(wèn)一次，輸入、輸出的要求可降為最少。由于該算法與輸入、輸出的細(xì)節(jié)無(wú)關(guān)，因而它也與設(shè)備無(wú)關(guān)。掃描線(xiàn)算法的主要缺點(diǎn)在于：對(duì)各種表的維持和排序的開(kāi)銷(xiāo)太大，適合軟件實(shí)現(xiàn)而不適合硬件實(shí)現(xiàn)。

掃描轉(zhuǎn)換算法描述如下：4.1.4邊界標(biāo)志算法

掃描轉(zhuǎn)換算法存在的問(wèn)題是：如何處理多邊形的水平邊，以及如何修改掃描線(xiàn)算法，使它能處理邊自交的多邊形。邊界標(biāo)志算法解決了上述問(wèn)題，其基本思想是：首先，對(duì)多邊形的每一條邊進(jìn)行掃描轉(zhuǎn)換，即對(duì)多邊形邊界所經(jīng)過(guò)的像素作一個(gè)邊界標(biāo)志；然后，對(duì)每條與多邊形相交的掃描線(xiàn)，按從左到右的順序，逐個(gè)訪(fǎng)問(wèn)該掃描線(xiàn)上的像素。

取一個(gè)布爾變量inside來(lái)指示當(dāng)前點(diǎn)的狀態(tài)。若點(diǎn)在多邊形內(nèi)，則inside為真；若點(diǎn)在多邊形外，則inside為假。Inside的初始值為假，每當(dāng)當(dāng)前訪(fǎng)問(wèn)像素為被打上標(biāo)志的點(diǎn)時(shí)，就把inside取反。對(duì)未打標(biāo)志的點(diǎn)，inside不變。如圖4-12所示為邊界標(biāo)志算法的示意圖。圖4-12邊界標(biāo)志算法邊界標(biāo)志算法描述如下：如果使用軟件實(shí)現(xiàn)，則掃描線(xiàn)算法與邊界標(biāo)志算法的執(zhí)行速度幾乎相同，但由于邊界標(biāo)志算法不必建立和維護(hù)邊表以及對(duì)它進(jìn)行排序，因此邊界標(biāo)志算法更適合硬件實(shí)現(xiàn)，這時(shí)它的執(zhí)行速度比掃描線(xiàn)算法快一至兩個(gè)數(shù)量級(jí)。

4.2區(qū)域填充技術(shù)

區(qū)域指已經(jīng)表示成點(diǎn)陣形式的填充圖形，它是像素的集合。區(qū)域填充指先將區(qū)域的一點(diǎn)賦予指定的顏色，然后將該顏色擴(kuò)展到整個(gè)區(qū)域的過(guò)程。區(qū)域填充算法要求區(qū)域是連通的。一個(gè)封閉區(qū)域確定以后，填充要解決的問(wèn)題是如何確定填充的像素以及如何高效地填充。

4.2.1區(qū)域的表示

區(qū)域有兩種表示方法：內(nèi)點(diǎn)表示和邊界表示。內(nèi)點(diǎn)表示是枚舉出區(qū)域內(nèi)部的所有像素，使這些像素著同一個(gè)顏色。邊界表示是枚舉出邊界上所有的像素，使這些像素著同一顏色。內(nèi)部像素著與邊界像素不同的顏色。區(qū)域填充要求區(qū)域是連通的。區(qū)域的連通方式分為兩種：4連通區(qū)域和8連通區(qū)域。首先定義4鄰接點(diǎn)和8鄰接點(diǎn)。4鄰接點(diǎn)是指一個(gè)點(diǎn)的上、下、左、右四個(gè)相鄰的點(diǎn)，而8鄰接點(diǎn)是指其上、下、左、右、左上、右上、左下、右下8個(gè)相鄰的點(diǎn)，如圖4-13所示。

從圖4-13可以看出，4連通區(qū)域是指從區(qū)域的一點(diǎn)出發(fā)，通過(guò)訪(fǎng)問(wèn)已知點(diǎn)的4鄰接點(diǎn)，在不越出區(qū)域的前提下，遍歷區(qū)域內(nèi)的所有像素。8連通區(qū)域則是指從區(qū)域的一點(diǎn)出發(fā)，通過(guò)訪(fǎng)問(wèn)已知點(diǎn)的8鄰接點(diǎn)，遍歷區(qū)域內(nèi)的所有像素。4連通區(qū)域與8連通區(qū)域的區(qū)別在于，對(duì)邊界的要求有所不同，如圖4-14所示。圖4-13鄰接點(diǎn)的定義圖4-14

4連通區(qū)域與8連通區(qū)域的邊界從圖4-14中可以看出，8連通區(qū)域比4連通區(qū)域?qū)吔绲囊蟾摺Ｍㄟ^(guò)上述分析，可以將區(qū)域的表示方式與區(qū)域的連通性相結(jié)合，共得到4種區(qū)域的表示方式，分別是以邊界表示的4連通區(qū)域、以?xún)?nèi)點(diǎn)表示的4連通區(qū)域、以邊界表示的8連通區(qū)域、以?xún)?nèi)點(diǎn)表示的8連通區(qū)域，如圖4-15所示。圖4-15區(qū)域的表示方式4.2.2遞歸算法

遞歸算法的思想是，在一個(gè)封閉區(qū)域內(nèi)部有一已知像素，由此出發(fā)通過(guò)某種方法找到區(qū)域內(nèi)的所有像素。遞歸的基本方法是設(shè)種子像素為(x，y)，種子點(diǎn)是4連通區(qū)域內(nèi)的一點(diǎn)，old_color為區(qū)域內(nèi)的原有像素的顏色，new_color是要填充的顏色。遞歸填充的過(guò)程是：如果種子像素是區(qū)域內(nèi)原有顏色old_color，說(shuō)明該種子像素在區(qū)域內(nèi)，則將像素置為被填充顏色new_color，同時(shí)將種子像素的上、下、左、右像素當(dāng)做種子，遞歸調(diào)用填充算法；否則說(shuō)明該像素已被填充，不再處理。種子遞歸填充算法如下：遞歸算法的原理和程序都很簡(jiǎn)單，但由于要進(jìn)行多次遞歸，因此費(fèi)時(shí)、費(fèi)內(nèi)存，計(jì)算機(jī)的效率將非常低。4.2.3棧結(jié)構(gòu)的種子填充算法

設(shè)G為一內(nèi)點(diǎn)表示的區(qū)域，(x，y)為區(qū)域內(nèi)一點(diǎn)，old_color為G的原色?，F(xiàn)取(x，y)為種子點(diǎn)對(duì)區(qū)域G進(jìn)行填充，即先置像素(x，y)的顏色為new_color，然后逐步將整個(gè)區(qū)域G都置為同樣的顏色。步驟如下：

種子像素入棧，當(dāng)棧非空時(shí)，執(zhí)行如下三步操作：

(1)棧頂像素出棧；

(2)將出棧像素置成多邊形當(dāng)前顏色；

(3)按上、下、左、右的順序檢查與出棧像素相鄰的四個(gè)像素，若其中某個(gè)像素不在邊界上且未置成多邊形當(dāng)前顏色，則把該像素入棧。

例4-1有多邊形P0(1，5)P1(5，5)P2(7，3)P3(7，1)P4(1，1)。設(shè)種子點(diǎn)為(3，3)，搜索的方向是上、下、左、右。依此類(lèi)推，最后像素被選中并填充的次序如圖4-16中箭頭所示。

像素的出棧與入棧順序表如下所示：

(210812)

(371310812)

(461471310812)

(561471310812)

從上述的出棧及入棧順序可以看出，基于棧結(jié)構(gòu)的填充算法會(huì)出現(xiàn)有些像素反復(fù)入棧的情況，因此，出棧時(shí)需要先判斷后決定是否填充。這一方面降低了算法的效率，另一方面還要求很大的存儲(chǔ)空間以實(shí)現(xiàn)棧結(jié)構(gòu)。圖4-16區(qū)域的填充過(guò)程4.2.4掃描線(xiàn)填充算法

掃描線(xiàn)填充算法的目標(biāo)是減少遞歸層次以及像素的入棧次數(shù)，該算法適用于邊界表示的4連通區(qū)域。掃描線(xiàn)填充算法的思想是在任意不間斷區(qū)間中只取一個(gè)種子像素(不間斷區(qū)間指在一條掃描線(xiàn)上的一組相鄰元素)，填充當(dāng)前掃描線(xiàn)上的該段區(qū)間；然后確定與這一區(qū)段相鄰的上下兩條掃描線(xiàn)上位于區(qū)域內(nèi)的區(qū)段，并依次把它們保存起來(lái)，反復(fù)進(jìn)行這個(gè)過(guò)程，直到所保存的各區(qū)段都填充完畢。算法步驟如下。

種子像素入棧。當(dāng)棧非空時(shí)作如下四步操作：

(1)棧頂像素出棧；

(2)沿掃描線(xiàn)對(duì)出棧像素的左右像素進(jìn)行填充，直至遇到邊界像素為止，即每出棧一個(gè)像素，就對(duì)包含該像素的整個(gè)區(qū)間進(jìn)行填充；

(3)將上述區(qū)間內(nèi)最左、最右的像素分別記為xl和xr；

(4)在區(qū)間檢查與當(dāng)前掃描線(xiàn)相鄰的上下兩條掃描線(xiàn)的有關(guān)像素是否全為邊界像素或已填充的像素，若存在非邊界、未填充的像素，則把每一區(qū)間的最右或最左像素取作種子像素入棧，繼續(xù)執(zhí)行步驟(1)。

掃描線(xiàn)填充算法的填充過(guò)程如圖4-17所示。圖4-17掃描線(xiàn)填充過(guò)程圖4-17演示了4連通區(qū)域中掃描線(xiàn)填充的過(guò)程，白色像素為種子。圖(a)是填充過(guò)程的開(kāi)始，表示了種子位置和第一條掃描線(xiàn)上的填充區(qū)域，相鄰掃描線(xiàn)上準(zhǔn)備入棧的像素及位置；圖(b)是第一條掃描線(xiàn)之上的第二條掃描線(xiàn)填充的像素區(qū)段及入棧像素；圖(c)是在第一條掃描線(xiàn)之上的第三條掃描線(xiàn)的填充像素區(qū)段及入棧像素；圖(d)定義區(qū)域右上角部分的完整像素區(qū)段及剩余的待處理?xiàng)?nèi)種子像素。圖中的數(shù)字表示了入棧像素的位置和入棧順序。

上述算法對(duì)于每一個(gè)待填充區(qū)段，只需壓棧一次，因此，掃描線(xiàn)填充算法提高了區(qū)域填充的效率。4.2.5區(qū)域填充圖案

進(jìn)行區(qū)域填充時(shí)，有時(shí)需要用一種圖案來(lái)填充平面區(qū)域。用圖案來(lái)填充平面區(qū)域的基本思想是：首先用模板定義各種圖案；然后修改填充的掃描轉(zhuǎn)換算法，即在確定了區(qū)域內(nèi)的一個(gè)像素之后，不是馬上往該像素填色，而是先查詢(xún)模板位圖的對(duì)應(yīng)位置，若對(duì)應(yīng)位置有圖案，即圖案的對(duì)應(yīng)位置為1時(shí)，則對(duì)像素填充顏色，否則，不改變?cè)撓袼氐闹?。填充圖案有兩種方式，一種是以不透明方式填充圖案，另一種是以透明方式填充圖案。不透明圖案填充的算法是根據(jù)模板位圖對(duì)應(yīng)位置為0或1來(lái)決定是用前景色還是背景色去寫(xiě)像素的。若以透明方式填充，則當(dāng)模板位圖的對(duì)應(yīng)位置為1時(shí)，用前景色寫(xiě)像素，否則，不改變像素的顏色。圖案填充算法首先要進(jìn)行圖案的定義，可以使用一個(gè)M×N的二維數(shù)組來(lái)記錄，color［i］［j］表示局部坐標(biāo)系(i，j)處的像素值；其次是圖案與區(qū)域的定位問(wèn)題，有兩種定位方式：相對(duì)定位和絕對(duì)定位；最后是像素著色模式的定義，同樣有兩種方式：透明(Transparent)方式和不透明(Opaque)方式。

絕對(duì)定位方式是指將圖案在區(qū)域所在的繪圖空間坐標(biāo)系中定位。此時(shí)若區(qū)域的位置不同，則區(qū)域中填充的圖案也不同。此時(shí)的視覺(jué)效果是：若區(qū)域移動(dòng)，則區(qū)域中的填充圖案發(fā)生變化。定位公式為，value［x］［y］=color［x%M］［y%N］。絕對(duì)定位方式如圖4-18所示。圖4-18絕對(duì)定位方式相對(duì)定位方式是指將圖案在區(qū)域的局部坐標(biāo)系中定義。記局部坐標(biāo)系原點(diǎn)為(x0，y0)，則value［x］［y］=color［(x－x0)%M］［(y－y0)%N］。相對(duì)定位方式如圖4-19所示。圖4-19相對(duì)定位方式圖案填充算法在掃描轉(zhuǎn)換算法中對(duì)像素著色操作需增加額外控制。在著色模式下，將圖案中標(biāo)記為1的位置對(duì)應(yīng)的像素寫(xiě)為前景色。在透明模式下，對(duì)圖案中標(biāo)記為0的位置對(duì)應(yīng)的像素不進(jìn)行寫(xiě)操作；在不透明模式下，將圖案中標(biāo)記為0的位置對(duì)應(yīng)的像素寫(xiě)為背景色。像素著色模式的本質(zhì)是規(guī)定前景色與背景色的組合規(guī)則，如前景色優(yōu)先、背景色優(yōu)先、前景色與背景色的加權(quán)組合或各種規(guī)則的組合。

例4-2以不透明模式實(shí)現(xiàn)圖案填充(如圖4-20所示)。

填充過(guò)程：圖(d)為待填充區(qū)域的像素位圖，圖(e)擦除圖(a)中圖(d)區(qū)域，并將待填充區(qū)域像素寫(xiě)為背景色，圖(f)

對(duì)待填充區(qū)域進(jìn)行圖案填充，圖(g)以透明模式把圖(f)繪制在屏幕上。圖4-20圖案填充過(guò)程4.2.6多邊形的掃描轉(zhuǎn)換與區(qū)域填充方法比較

多邊形的掃描轉(zhuǎn)換和區(qū)域填充均為平面著色問(wèn)題，它們的聯(lián)系非常緊密。如采用畫(huà)線(xiàn)算法將多邊形表示成8連通區(qū)域，并取區(qū)域內(nèi)一點(diǎn)作為種子點(diǎn)，則多邊形的掃描轉(zhuǎn)換問(wèn)題可轉(zhuǎn)化成區(qū)域填充問(wèn)題；反之，當(dāng)已知多邊形區(qū)域的頂點(diǎn)表示，則區(qū)域填充問(wèn)題也可轉(zhuǎn)化為多邊形的掃描轉(zhuǎn)換問(wèn)題。但是這兩類(lèi)算法的區(qū)別還是很明顯的，主要體現(xiàn)在以下幾個(gè)方面：

(1)基本思想不同。掃描轉(zhuǎn)換是將頂點(diǎn)表示轉(zhuǎn)換成點(diǎn)陣表示，主要利用多邊形各種形式的連貫性。區(qū)域填充只改變區(qū)域內(nèi)的填充顏色，沒(méi)有改變區(qū)域的表示方法，在填充過(guò)程中利用了區(qū)域的連通性。

(2)對(duì)邊界的要求不同。掃描轉(zhuǎn)換只要求掃描線(xiàn)與多邊形邊界交點(diǎn)個(gè)數(shù)為偶數(shù)。區(qū)域填充的區(qū)域邊界是封閉的，這樣可以防止遞歸填充時(shí)跨越邊界。

(3)基本的條件不同。掃描轉(zhuǎn)換是從邊界頂點(diǎn)信息出發(fā)的。區(qū)域填充是以區(qū)域內(nèi)的一點(diǎn)作為種子點(diǎn)，然后從這點(diǎn)開(kāi)始對(duì)區(qū)域進(jìn)行著色的。 4.3反走樣

對(duì)多邊形進(jìn)行掃描轉(zhuǎn)換后，多邊形的邊界一般呈現(xiàn)鋸齒形狀，這是由于在光柵圖形顯示器上顯示的圖形都是由一系列相同亮度的離散像素構(gòu)成的，因此，會(huì)形成或多或少的臺(tái)階或鋸齒狀。這種用離散量表示連續(xù)量引起的失真，就叫做走樣。反走樣技術(shù)就是減少或消除這種不良效果的技術(shù)。走樣現(xiàn)象還有其他的表現(xiàn)形式，如紋理圖形走樣、圖形細(xì)節(jié)失真。當(dāng)圖形中包含相對(duì)微小的物體時(shí)，這些物體在靜態(tài)圖形中顯示時(shí)容易被丟棄或忽略，而在動(dòng)畫(huà)顯示時(shí)會(huì)時(shí)隱時(shí)現(xiàn)，產(chǎn)生閃爍。常用的反走樣方法分為兩類(lèi)：一類(lèi)是提高分辨率，增加采樣點(diǎn)；另一類(lèi)是把像素作為一個(gè)有限區(qū)域，對(duì)區(qū)域進(jìn)行采樣。4.3.1提高分辨率

提高顯示器分辨率可改進(jìn)圖形的顯示效果。如圖4-21(a)所示，在理想直線(xiàn)經(jīng)過(guò)的每一列像素中，選擇離直線(xiàn)最近的一個(gè)，置為直線(xiàn)顏色(黑色)，每當(dāng)前一列所選的像素不同行時(shí)，在線(xiàn)上就出現(xiàn)一個(gè)臺(tái)階?，F(xiàn)在假設(shè)我們把顯示器分辨率提高一倍，如圖4-21(b)所示，直線(xiàn)經(jīng)過(guò)兩倍的像素，臺(tái)階也增加一倍。但是由于每個(gè)臺(tái)階在水平方向與垂直方向的臺(tái)階大小只有原先的一半，因此效果會(huì)好很多。這種改進(jìn)需要付出較高的代價(jià)，掃描轉(zhuǎn)換算法的執(zhí)行時(shí)間也成倍增加，因此增加分辨率是不經(jīng)濟(jì)的方法，同時(shí)它也只能減輕而不能消除鋸齒問(wèn)題。圖4-21提高分辨率前后的鋸齒現(xiàn)象比較提高分辨率顯然可以通過(guò)硬件實(shí)現(xiàn)，但是，當(dāng)無(wú)法采用硬件進(jìn)一步提高分辨率時(shí)，可采用軟件的方法提高分辨率，即采用某種平均算法，把結(jié)果轉(zhuǎn)化到較低分辨率的顯示器上進(jìn)行顯示。

用軟件方式提高分辨率是對(duì)單個(gè)像素進(jìn)行進(jìn)一步的細(xì)分。假設(shè)初始分辨率是m×n，單個(gè)像素被細(xì)分成s×t個(gè)子像素，顯示圖形按照s×t×m×n的分辨率進(jìn)行掃描轉(zhuǎn)換，記錄每個(gè)子像素的顏色。原分辨率下像素所對(duì)應(yīng)的顏色由其細(xì)分后的子像素顏色值的某種平均來(lái)定義，得到像素的顏色值顯示。實(shí)踐證明，這種方法對(duì)于改進(jìn)圖形質(zhì)量有較好的效果。采用