《計算機圖形學基礎》課件第4章

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

4.2區(qū)域填充技術

4.3反走樣

習題4

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

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

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

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

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

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

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

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

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

(3)對一條掃描線填充的過程可分為四個步驟：

①求交：計算掃描線與多邊形各邊的交點；

②排序：把所有交點按遞增順序排列；

③交點配對：將奇數(shù)與偶數(shù)交點進行配對，每對交點就代表掃描線與多邊形的一個相交區(qū)間；

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

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

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

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

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

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

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

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

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

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

2.掃描線的連貫性

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

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

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

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

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

3.邊的連貫性

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

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

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

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

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

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

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

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

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

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

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

x：當前掃描線與邊的交點；

dx＝－b/a：從當前掃描線到下一條掃描線之間的x增量；

ymax：邊所交的最高掃描線。

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

ymax：邊的上端點的y坐標；

x：在ET中表示邊的下端點的x坐標，在AET中為邊與掃描線的交點的坐標；

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

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

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

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

AET表的結(jié)構(gòu)這樣當建立了邊的分類表(ET)后，掃描線算法可按下列步驟進行：

(1)取掃描線縱坐標y的初始值為ET中非空元素的最小序號。

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

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

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

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

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

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

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

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

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

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

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

4.2區(qū)域填充技術

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

4.2.1區(qū)域的表示

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

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

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

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

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

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

(1)棧頂像素出棧；

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

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

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

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

(210812)

(371310812)

(461471310812)

(561471310812)

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

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

種子像素入棧。當棧非空時作如下四步操作：

(1)棧頂像素出棧；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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