計算機圖形學5多邊形掃描轉(zhuǎn)換與區(qū)域填充

多邊形的掃描轉(zhuǎn)換與區(qū)域填充一、多邊形的掃描轉(zhuǎn)換前面講的畫直線是一維圖形的光柵化，就是如何在計算機屏幕上即在一個離散的像素集上表示一個連續(xù)的圖形。而多邊形的掃描轉(zhuǎn)換和區(qū)域填充這個問題是怎么樣在離散的像素集上表示一個連續(xù)的二維圖形。多邊形有兩種重要的表示方法：頂點表示和點陣表示。

點陣表示P1P2P3P4P5頂點表示P6

頂點表示是用多邊形的頂點序列來表示多邊形。這種表示直觀、幾何意義強、占內(nèi)存少，易于進行幾何變換，但由于它沒有明確指出哪些象素在多邊形內(nèi)，故不能直接用于面著色。

點陣表示是用位于多邊形內(nèi)的象素集合來刻畫多邊形。這種表示丟失了許多幾何信息（如邊界、頂點等），但它卻是光柵顯示系統(tǒng)顯示時所需的表示形式。這涉及到兩個問題：第一個問題是如果知道邊界，能否求出這個多邊形哪些像素在多邊形內(nèi)。眾所周知，在計算機上畫圖形，實際上就是寫幀緩存（framebuffer）。如果知道多邊形哪些像素在里面，就直接寫到幀緩存里即可。

第二個問題是知道多邊形內(nèi)部的像素，反過來求多邊形的邊界。很遺憾，這個問題不是圖形學關(guān)心的問題，是模式識別所關(guān)心的問題。圖形學、圖像處理、模式識別、計算機視覺有密切的聯(lián)系。我們只關(guān)心從頂點表示到點陣表示。光柵圖形的一個基本問題是把多邊形的頂點表示轉(zhuǎn)換為點陣表示。這種轉(zhuǎn)換稱為多邊形的掃描轉(zhuǎn)換。為什么叫掃描轉(zhuǎn)換？因為光柵顯示器是逐行掃描！區(qū)域填充:指先將區(qū)域的一點賦予指定的顏色，然后將該顏色擴展到整個區(qū)域的過程。多邊形分為凸多邊形、凹多邊形、含內(nèi)環(huán)的多邊形等：（1）凸多邊形任意兩頂點間的連線均在多邊形內(nèi)。（2）凹多邊形任意兩頂點間的連線有不在多邊形內(nèi)的部分。凸多邊形凹多邊形含內(nèi)環(huán)的多邊形

有關(guān)概念

1)區(qū)域：一組相鄰而且又相連的像素，而且具有相同屬性的封閉區(qū)域。3)區(qū)域填充：以某種屬性對整個區(qū)域進行設置的過程。2）種類：①單域②復合域逐點判斷填充算法區(qū)域填充的基本(初級)方法:逐點判斷填充算法逐點判斷繪圖窗口內(nèi)的每一個像素；若在區(qū)域的內(nèi)部：用指定的屬性設置該點；否則不予處理；設有如下函數(shù)：

TruewhenxDInside(D,x,y)=FalsewhenxDD取矩形R(x1≤x≤x2,y1≤y≤y2)，使R包圍D，則逐點判斷填充算法如下：for(y=y1;y<=y2;y++)for(x=x1;x<=x2;x++)if(inside(D,x,y))drawpixel(x,y,color);上述算法原理簡單、實用，但效率低；效率低的原因是沒有考慮各象素之間的聯(lián)系，孤立地考察象素與區(qū)域的關(guān)系，使得幾十萬甚至幾百萬個象素都要一一判別，每次判別又要多次求交點，需要做大量的乘除運算，花費很多時間。1）射線法；2）累計角度法；3）編碼法；4）……..如何判斷點在多邊形的內(nèi)或外？（包含性檢查的方法）1）射線法；

過被檢測點任作一條射線,求其與邊界的交點,若交點數(shù)為偶數(shù),則該點在邊界之外,否則在邊界之內(nèi)。

PP逐點判斷法2）累計角度法步驟從v點向多邊形P頂點發(fā)出射線，形成有向角計算有相交的和，得出結(jié)論現(xiàn)在的問題是，知道多邊形的邊界，如何找到多邊形內(nèi)部的點，即把多邊形內(nèi)部填上顏色。對每條橫越多邊形的掃描線，掃描轉(zhuǎn)換算法確定掃描線與多邊形邊的交點位置。掃描線交點交點交點交點

X-掃描線算法填充多邊形的基本思想是按掃描線順序，計算掃描線與多邊形的相交區(qū)間，再用要求的顏色顯示這些區(qū)間的像素，即完成填充工作。

區(qū)間的端點可以通過計算掃描線與多邊形邊界線的交點獲得。根據(jù)該原理，X-掃描線算法可以填充凸的、凹的、還可以是帶孔的多邊形。1、x-掃描線算法掃描線交點交點交點交點對于每條穿越多邊形的掃描線，X-掃描線算法確定掃描線與多邊形邊相交區(qū)間的像素點位置。x-掃描線算法填充多邊形xy213456789111234567891011121012如掃描線y=3與多邊形的邊界相交于4點：（2，3）、（4，3）、（7，3）、（9，3）。這四點定義了掃描線從X=2到X=4，從X=7到X=9兩個落在多邊形內(nèi)的區(qū)間，該區(qū)間內(nèi)的像素應取填充色。從該例可以看出，算法的核心是需按x遞增順序排列交點的x坐標序列。由此，可得到X-掃描線算法步驟如下：（1）確定多邊形所占有的最大掃描線數(shù)，得到多邊形頂點的最小和最大y值（ymin和ymax）。（2）從y=ymin到y(tǒng)=ymax，每次用一條掃描線進行填充。（3）對一條掃描線填充的過程可分為四個步驟：a、求交：計算掃描線與多邊形各邊的交點；b、排序：把所有交點按遞增順序進行排序；注意：交點在計算時未必是按遞增順序排列的。c、交點配對：第一個與第二個，第三個與第四個等等，每對交點就代表掃描線與多邊形的一個相交區(qū)間；d、區(qū)間填色：把這些相交區(qū)間內(nèi)的像素置成不同于背景色的填充色。在填充過程，當掃描線與多邊形頂點相交時，交點的取舍問題??（交點的個數(shù)應保證為偶數(shù)個）。xy213456789111234567891011121012與多邊形頂點相交的交點的處理當掃描線與多邊形頂點相交時，會出現(xiàn)異常情況。解決方案：（1）、若共享頂點的兩條邊分別落在掃描線的兩邊，交點只算一個；（2）若共享頂點的兩條邊在掃描線的同一邊，這時交點作為零個或兩個。具體實現(xiàn)方式是：檢查共享頂點的兩條邊的另外兩個端點的y值，按這兩個y值中大于交點y值的個數(shù)是0、1、2來決定交點數(shù)取0、1、2。

與掃描線相交的多邊形頂點的交點數(shù)123456789011110222但這個算法效率比較低，因為這個算法的關(guān)鍵問題是求交！而求交是很可怕的，求交的計算量是非常大的。假設一個100邊形（一個卡通片至少是100、200個邊形），現(xiàn)在每條掃描線和這個多邊形求交點，一共有1024條掃描線，一共要進行10萬多次求交運算，每次求交還要做大量的加減乘除法，計算量太大。

最理想的算法是不求交（排序、配對、填色總是要的）！如果不求交，那會極大提高算法的效率。

為了計算每條掃描線與多邊形各邊的交點，最簡單的方法是把多邊形的所有邊放在一個表中。在處理每條掃描線時，按順序從表中取出所有的邊，分別與掃描線求交。掃描轉(zhuǎn)換算法重要意義是提出了圖形學里兩個重要的思想：第一個思想是掃描線的思想，當處理圖形圖像時按一條條掃描線處理；第二個思想是增量的思想。DDA在算y值的時候是采用增量的方法，求交點的時候能不能也采取增量的方法？每條掃描線的y值都知道，關(guān)鍵是求x的值。X是什么？2、多邊形的掃描轉(zhuǎn)換算法可以從三方面考慮加以改進：（1）在處理一條掃描線時，僅對與它相交的多邊形的邊（有效邊）進行求交運算。（2）需要考慮掃描線的連貫性，即當前掃描線與各邊的交點順序與下一條掃描線與各邊的交點順序很可能相同或非常相似，這樣在當前掃描線處理完畢之后，不必為下一條掃描線從頭開始構(gòu)造交點信息。（3）最后考慮多邊形的連貫性，即當某條邊與當前掃描線相交時，它很可能也與下一條掃描線相交。為了避免求交運算，需要引進一套特殊的數(shù)據(jù)結(jié)構(gòu)。這套數(shù)據(jù)結(jié)構(gòu)在后面的消隱算法中還要出現(xiàn)。數(shù)據(jù)結(jié)構(gòu)：11/k

與多邊形邊界相交的兩條

連續(xù)掃描線交點的相關(guān)性xi,yixi+1,yi+1隨著掃描線的移動，掃描線與多邊形的交點和上一次交點相關(guān)：設邊的直線斜率為k，若y=yi時，x=xi，則當y=yi+1=yi+1時，xi+1=xi+1/k活性邊表(AET)：把與當前掃描線相交的邊稱為活性邊，并把它們按與掃描線交點x坐標遞增的順序存放在一個鏈表中。

x

△x

ymaxnext結(jié)點內(nèi)容（一個結(jié)點在數(shù)據(jù)結(jié)構(gòu)里可用結(jié)構(gòu)來表示）x：當前掃描線與邊的交點坐標△x：從當前掃描線到下一條掃描線間x的增量ymax：該邊所交的最高掃描線的坐標值ymax即△x=1/k為常量。則下一條掃描線與該邊的交點不要重新計算，只要加一個增量△x。x

△xymaxnext其中x為當前掃描線與邊的交點，ymax是邊所在的最大掃描線值，通過它可以知道何時才能“拋棄”該邊，△x表示從當前掃描線到下一條掃描線之間的x增量即斜率的倒數(shù)。next為指向下一條邊的指針另外使用增量法計算時，我們需要知道一條邊何時不再與下一條掃描線相交，以便及時把它從有效邊表中刪除出去，避免下一步進行無謂的計算。綜上所述，有效邊表AET的每個結(jié)點存放對應邊的有關(guān)信息如下：一個多邊形與若干掃描線看掃描線y=6的活性邊表：為了方便有效邊表的建立與更新，需構(gòu)造一個新邊表（NET），用來存放多邊形的邊的信息，分為4個步驟：（1）首先構(gòu)造一個縱向鏈表，鏈表的長度為多邊形所占有的最大掃描線數(shù)，鏈表的每個結(jié)點，稱為一個桶，對應多邊形覆蓋的每一條掃描線。（2）將每條邊的信息鏈入與該邊最小y坐標（ymin）相對應的桶處。也就是說，存放在該掃描線第一次出現(xiàn)的邊。若某邊的較低端點為ymin，則該邊就放在掃描線ymin的新邊表中。（3）每條邊的數(shù)據(jù)形成一個結(jié)點，內(nèi)容包括：該掃描線與該邊的初始交點x（即較低端點的x值），1/k，以及該邊的最大y值ymax。x|ymin1/kymaxnext（4）同一桶中若干條邊按X|ymin由小到大排序。若X|ymin

相等，則按照1/k由小到大排序。一個多邊形與若干掃描線

7

6

5

4

3

2

1

0

8P1P2

P2P3

5-32

533P4P5

P5P6

207

1108

528

5-1.57P6P1P3P4這個結(jié)構(gòu)實際上是一個指針數(shù)組，數(shù)組的每個變量是個指針，這個指針指向所有的以這個y值作為起點的邊。把多邊形所有的邊全部填成這樣的結(jié)構(gòu)，插到這個指針數(shù)組里面來。如y=1,y=5指向哪些邊？從上面這個指針數(shù)組里面就知道多邊形是從哪里開始的。在這個指針數(shù)組里只有1、2、3、5處有邊，因此當從下往上進行掃描轉(zhuǎn)換的時候，從y=1開始做，而在1這條線上有兩條邊進來了，然后就把這兩條邊放進活性邊表來處理。當處理y=2這條掃描線時（活性邊里有2條邊），先看活性邊表里是否有邊要退出和加入，實際上p1p2邊要退出了（y=ymax），p1p6邊要加入了。退出的邊要從活性邊表里去掉，不退出的邊要進行處理，即把x值加上一個增量。一個多邊形與若干掃描線即每做一次新的掃描線時，要對已有的邊進行三個處理：一是否被去除掉；如果不被去除，第二就要對它的數(shù)據(jù)進行更新，。所謂更新數(shù)據(jù)就是要更新它的x值，即x+△x；最后，就是有沒有新的邊進來，新的邊在NET里，可以插入排序插進來。這個算法過程從來沒有求交，這套數(shù)據(jù)結(jié)構(gòu)使得你不用求交點！避免了求交運算。voidpolyfill(polygon,color)intcolor;多邊形polygon;{for(各條掃描線i)

{

初始化新邊表頭指針NET[i]；把ymin=i的邊放進邊表NET[i];

}y=最低掃描線號；初始化活性邊表AET為空；

for(各條掃描線i)

{

把新邊表NET[i]中的邊結(jié)點用插入排序法插入AET表，使之按x坐標遞增順序排列；遍歷AET表，把配對交點區(qū)間(左閉右開)上的象素(x,y)，用putpixel(x,y,color)改寫象素顏色值；遍歷AET表，把ymax=i的結(jié)點從AET表中刪除，并把ymax>i結(jié)點的x值遞增x；若允許多邊形的邊自相交，則用冒泡排序法對AET表重新排序；

}}/*polyfill*/3、邊緣填充算法其基本思想是按任意順序處理多邊形的每條邊。在處理每條邊時，首先求出該邊與掃描線的交點，然后將每一條掃描線上交點右方的所有像素取補。多邊形的所有邊處理完畢之后，填充即完成。逐邊向右取右右右右邊緣填充算法缺點：每一個象素可能被訪問多次引入柵欄，以減少填充算法訪問象素的次數(shù)。柵欄：與掃描線垂直的直線，通常過一頂點，且把多邊形分為左右二半?；舅枷耄簰呙杈€與多邊形的邊求交，將交點與柵欄之間的象素取補。若交點位于柵欄左邊，則將交點之右，柵欄之左的所有象素取補；若交點位于柵欄右邊，則將交點之左，柵欄之右的所有象素取補。減少了象素重復訪問數(shù)目，但不徹底。柵欄填充算法6、邊界標志算法基本思想：幀緩沖器中對多邊形的每條邊進行直線掃描轉(zhuǎn)換，亦即對多邊形邊界所經(jīng)過的象素打上標志。然后再采用和掃描線算法類似的方法將位于多邊形內(nèi)的各個區(qū)段著上所需顏色。使用一個布爾量inside來指示當前點是否在多邊形內(nèi)的狀態(tài)。voidedgemark_fill(polydef,color)多邊形定義polydef；intcolor;{對多邊形polydef每條邊進行直線掃描轉(zhuǎn)換；

inside=FALSE;for(每條與多邊形polydef相交的掃描線y)for(掃描線上每個象素x){if(象素x被打上邊標志)//兩個交點之間的區(qū)域填充inside=!(inside);if(inside！=FALSE)putpixel(x,y,color);elsedrawpixel(x,y,background); }}用軟件實現(xiàn)時，掃描線算法與邊界標志算法的執(zhí)行速度幾乎相同，由于邊界標志算法不必建立維護邊表以及對它進行排序，所以邊界標志算法更適合硬件實現(xiàn)，這時它的執(zhí)行速度比有序邊表算法快一至兩個數(shù)量級。小結(jié)掃描線法可以實現(xiàn)已知多邊形域邊界的填充，多邊形域可以是凹的、凸的、還可以是帶孔的。該填充算法是按掃描線的順序，計算掃描線與待填充區(qū)域的相交區(qū)間，再用要求的顏色顯示這些區(qū)間的像素，即完成填充工作。這里區(qū)間的端點通過計算掃描線與多邊形邊界的交點獲得。所以待填充區(qū)域的邊界線必須事先知道，因此它的缺點是無法實現(xiàn)對未知邊界的區(qū)域填充。二、區(qū)域填充

區(qū)域填充是指將區(qū)域內(nèi)的一點(常稱種子點)賦予給定顏色,然后將這種顏色擴展到整個區(qū)域內(nèi)的過程。它是光柵計算機圖形學中的一個基本操作，在交互式圖形設計、動畫、計算機輔助設計等領(lǐng)域有著廣泛的應用。區(qū)域---指已經(jīng)表示成點陣形式的填充圖形，是象素的集合。在光柵圖形學中，區(qū)域指的是已經(jīng)表示成點陣形式的象素的集合。區(qū)域可采用內(nèi)點表示和邊界表示兩種表示形式。

內(nèi)點表示：枚舉出區(qū)域內(nèi)部的所有像素，內(nèi)部的所有像素著同一個顏色，邊界像素著與內(nèi)部像素不同的顏色。

邊界表示：枚舉出邊界上的所有像素，邊界上的所有像素著同一個顏色，內(nèi)部像素著與邊界像素不同的顏色。區(qū)域可分為4向連通區(qū)域和8向連通區(qū)域。四個方向運動八個方向運動四連通區(qū)域八連通區(qū)域區(qū)域填充算法要求區(qū)域是連通的，因為只有在連通區(qū)域中，才可能將種子點的顏色擴展到區(qū)域內(nèi)的其它點。4向連通區(qū)域指的是從區(qū)域上一點出發(fā)，可通過四個方向，即上、下、左、右移動的組合，在不越出區(qū)域的前提下，到達區(qū)域內(nèi)的任意象素；即：任取區(qū)域內(nèi)兩點，在該區(qū)域內(nèi)，通過上、下、左、右四個方向的運動，這兩點相互可達。8向連通區(qū)域指的是從區(qū)域內(nèi)每一象素出發(fā)，可通過八個方向，即上、下、左、右、左上、右上、左下、右下這八個方向的移動的組合來到達。即：任取區(qū)域內(nèi)兩點，通過水平、垂直、兩個對角線八個方向的運動，這兩點相互可達。四連通區(qū)域八連通區(qū)域種子填充1、簡單四連通種子填充算法種子填充算法的原理是：假設在多邊形區(qū)域內(nèi)部有一像素已知，由此出發(fā)找到區(qū)域內(nèi)的所有像素，用一定的顏色或灰度來填充。假設區(qū)域采用邊界定義，即區(qū)域邊界上所有像素均具有某個特定值，區(qū)域內(nèi)部所有像素均不取這一特定值，而邊界外的像素則可具有與邊界相同的值?？紤]區(qū)域的四向連通，即從區(qū)域上一點出發(fā)，可通過四個方向，即上、下、左、右移動的組合，在不越出區(qū)域的前提下，到達區(qū)域內(nèi)的任意像素?？梢允褂脳＝Y(jié)構(gòu)來實現(xiàn)簡單的種子填充算法。算法原理如下：種子像素入棧，當棧非空時重復執(zhí)行如下三步操作：（1）棧頂像素出棧；（2）將出棧像素置成要填充色；（3）按左、上、右、下順序檢查與棧像素相鄰的四個像素，若其中某個像素不在邊界且未置成填充色，則把該像素入棧。種子像素入棧，棧非空時重復執(zhí)行如下三步：（1）棧頂像素出棧；（2）將出棧像素置成要填充色；（3）按左、上、右、下順序檢查與棧像素相鄰的四個像素，若其中某個像素不在邊界且未置成填充色，則把該像素入棧。掃描線填充算法(1)初始化：堆棧置空。將種子點（x，y）入棧。(2)出棧：若?？談t結(jié)束。否則取棧頂元素（x，y），以y作為當前掃描線。(3)填充并確定種子點所在區(qū)段：從種子點（x，y）出發(fā)，沿當前掃描線向左、右兩個方向填充，直到邊界。分別標記區(qū)段的左、右端點坐標為xl和xr。(4)并確定新的種子點：在區(qū)間[xl，xr]中檢查與當前掃描線y上、下相鄰的兩條掃描線上的象素。若存在非邊界、未填充的象素，則把每一區(qū)間的最右象素作為種子點壓入堆棧，返回第（2）步。上述算法對于每一個待填充區(qū)段，只需壓棧一次；因此，掃描線填充算法提高了區(qū)域填充的效率。掃描線算法分析（舉例分析）該算法也可以填充有孔區(qū)域。像素中的序號標指它所在區(qū)段位于堆棧中的位置掃描線算法分析（舉例分析）掃描線算法分析（舉例分析）掃描線算法分析（舉例分析）2、掃描填充與區(qū)域填充區(qū)別基本思想不同多邊形掃描轉(zhuǎn)換是指將多邊形的頂點表示轉(zhuǎn)化為點陣表示；區(qū)域填充只改變區(qū)域的填充顏色，不改變區(qū)域表示方法。對邊界的要求不同多邊形掃描轉(zhuǎn)換的掃描算法只要求一條掃描線與多邊形邊界的交點個數(shù)為偶數(shù)，多邊形的邊界可以不封閉；在區(qū)域填充算法中，為了防止遞歸填充時跨越區(qū)域的邊界，要求：區(qū)域的邊界是封閉基于的條件不同在區(qū)域填充算法中，要求給定區(qū)域內(nèi)一點作為種子點，然后從這一點根據(jù)連通性將新的顏色擴散到整個區(qū)域；掃描轉(zhuǎn)換多邊形是從多邊形的邊界(頂點)信息出發(fā)，利用多種形式的連貫性進行填充的。4、填充圖元屬性控制填充一個定義的區(qū)域的選擇包括:選擇實區(qū)域顏色或圖案填充方式;選擇某種顏色和圖案。取決于可用軟件包的能力;這些填充選擇可應用于多邊形區(qū)域或用曲線邊界定