計算機圖形學彩版第四章多邊形填充

孔令德

多邊形填充第四章有效邊表填充算法邊緣填充算法四鄰接點種子填充算法八鄰接點種子填充算法掃描線種子填充算法本章學習目標4.1多邊形的掃描轉(zhuǎn)換4.2有效邊表填充算法4.3邊緣填充算法4.4區(qū)域填充算法4.5本章小結(jié)本章內(nèi)容

在第3章中，講解了直線段掃描轉(zhuǎn)換的中點Bresenham算法。多段直線彼此連接并且閉合就構(gòu)成了多邊形。多面體的每個表面就是一個多邊形，曲面體的連續(xù)表面一般被離散為三角形小面或四邊形小面。每個表面（小面）均需要按照頂點顏色進行著色，而頂點顏色可以直接指定也可以是材質(zhì)、紋理、光照等條件交互作用的結(jié)果。解決了多邊形的填充問題就解決了物體的表面著色問題。多邊形的邊界線可根據(jù)需要選擇繪制或者不繪制，如圖4-1所示。真實感圖形的繪制中，一般不繪制多邊形的邊界線。（a）無邊界（b）繪制邊界圖4-1填充多邊形本章基于圖4-2所示的“示例多邊形”講解多邊形填充算法。圖4-2示例多邊形4.1.1多邊形的定義

多邊形是由折線段組成的封閉圖形。它由有序頂點的點集Pi（i＝0，…，n-1）及有向邊的線集Ei（i＝0，…，n-1）定義，n為多邊形的頂點數(shù)或邊數(shù)，且Ei＝PiPi+1，i＝0，…，n-1。這里Pn＝P0，用以保證了多邊形的封閉性。多邊形可以分為凸、凹多邊形以及環(huán)，如圖4-3所示。4.1多邊形的掃描轉(zhuǎn)換

圖4-3多邊形的定義⑴頂點表示法

4.1.2多邊形的表示

圖4-4多邊形表示法⑵點陣表示法⑶多邊形的掃描轉(zhuǎn)換將多邊形的描述從頂點表示法變換到點陣表示法的過程，稱為多邊形的掃描轉(zhuǎn)換。即從多邊形的頂點信息出發(fā)，求出位于多邊形內(nèi)部及其邊界上的各個像素點信息。

4.1.3多邊形著色模式

多邊形可以使用平面著色模式（flatshadingmode）或光滑著色模式（smoothshadingmode）填充。平面著色是指使用多邊形第一個頂點的顏色填充，多邊形內(nèi)部具有單一顏色。光滑著色是指多邊形內(nèi)部像素點的顏色是由多邊形各個頂點的顏色進行線性插值得到。圖4-6所示為三角形的平面著色，三角形填充為三角形第一個頂點的顏色紅色。圖4-7所示為三角形的光滑著色，三角形上任一點的顏色為3個頂點顏色的光滑過渡。

圖4-6三角形的平面著色圖4-7三角形的光滑著色圖4-8所示的圖形是采用平面著色模式填充的不同灰度的矩形塊，被稱為馬赫帶（MachBand）。觀察明暗變化的邊界，可以看出邊界處亮度對比度加強，使得邊界表現(xiàn)得非常明顯，稱為馬赫帶效應。馬赫帶效應不是一種物理現(xiàn)象，而是一種心理現(xiàn)象，夸大了平面著色的渲染效果，使得人眼感到的亮度變化比實際的亮度變化要大，如圖4-9所示。實際光強感知光強

圖4-8馬赫帶圖4-9邊界位置的實際亮度與感知亮度

4.1.4多邊形填充算法這里的多邊形是用頂點法表示的多邊形。多邊形的填充是指從多邊形的頂點信息出發(fā)，求出其覆蓋的每個像素點，取為填充色，而將多邊形外部的像素點保留為背景色。

多邊形填充的主要工作是確定穿越多邊形掃描線的覆蓋區(qū)間，然后將其著色。

首先確定多邊形覆蓋的掃描線條數(shù)（ymin～ymax），對每一條掃描線，計算掃描線與多邊形邊界的交點區(qū)間（xmin～xmax），然后再將該區(qū)間內(nèi)的像素賦予指定的顏色。在掃描線從多邊形頂點的最小值ymin向多邊形頂點的最大值ymax的移動過程中，重復上述工作，就可以完成多邊形的填充任務。4.1.5區(qū)域填充算法區(qū)域是指一組相鄰而又具有相同屬性的像素，可以理解為圖形的內(nèi)部。區(qū)域一般由封閉邊界定義。區(qū)域的邊界色和填充色不一致，區(qū)域一般采用種子算法進行填充。種子填充算法是從區(qū)域內(nèi)給定的種子位置開始，按填充顏色填充種子的相鄰像素直到顏色不同的邊界像素為止。種子填充算法主要有4鄰接點算法和8鄰接點算法。4.2有效邊表填充算法

4.2.1填充原理

多邊形的有效邊表填充算法的基本原理是按照掃描線從小到大的移動順序，計算當前掃描線與多邊形各邊的交點，然后把這些交點按x值遞增的順序進行排序、配對，以確定填充區(qū)間，然后用指定顏色著色填充區(qū)間內(nèi)的每個像素，即完成填充工作。有效邊表填充算法通過訪問多邊形覆蓋區(qū)間內(nèi)的每個像素，可以填充凸多邊形、凹多邊形和環(huán)，已成為目前最為有效的多邊形填充算法。在圖4-10中，多邊形覆蓋了12條掃描線。掃描線y＝3與多邊形有4個交點，分別為（2.3,3），(4.5,3），（7,3）和（9,3）。對交點進行圓整處理后的結(jié)果為（2,3），(5,3），（7,3）和（9,3）。按x值遞增的順序?qū)稽c進行排序、配對后的填充區(qū)間為[2,5]和[7,9]，共有7個像素點需要著色。圖4-10用一條掃描線填充多邊形P44.2.2邊界像素處理原則

實際填充過程中，需要考慮到邊界像素的影響問題。圖4-11中正方形P0P1P2P3被等分為4個小正方形。假定小正方形P0P5P8P6被填充為綠色，P5P1P7P8被填充為黃色，P8P7P2P4被填充為綠色，P6P8P4P3被填充為黃色。

P0P5P1P7P6P8P2P3

對于相鄰多邊形的公共邊，如不做處理，可能公共邊上的像素先設置為一個多邊形的顏色，然后又設置為另一個多邊形的顏色，一條邊界繪制兩次會導致混亂的視覺效果。圖4-11邊界像素的問題

在實際應用中，有時也需要考慮到像素面積大小的影響問題。對左下角為（1，1），右上角為（3，3）的正方形進行填充時，若邊界上的所有像素全部填充，就得到圖4-12所示的結(jié)果。所填像素覆蓋的面積為3×3個單位，而正方形的面積實際只有2×2個單位。

圖4-12面積為3×3P4為了解決這些問題，在多邊形填充過程中，常采用“下閉上開”和“左閉右開”的原則對邊界像素進行處理。圖4-11的填充結(jié)果如圖4-13所示，每個小正方形的右邊界像素和上邊界像素都沒有填充，即P6P8和P5P8填充為黃色，P8P7和P8P4填充為綠色。圖4-12的填充結(jié)果如圖4-14所示，沒有填充上面一行像素和右面一列像素，保證正方形的面積是2×2個單位。圖4-13邊界像素的處理P2P5P8P0P6P3P7P1

圖4-14面積為2×2圖4-2中的頂點可分為3類。共享頂點的兩條邊落在掃描線的下方。如P1、P6和P4。局部最高點普通連接點局部最低點共享頂點的兩條邊分別落在掃描線兩側(cè)。如P2

共享頂點的兩條邊落在掃描線的上方。如P0、P3和P5常根據(jù)共享頂點的兩條邊的另一端的y值大于掃描線y值的個數(shù)來將這3類頂點個數(shù)分別取為0、1和2。有效邊表算法能自動處理這3類頂點。普通連接點的處理原則

圖4-2中P2點是邊P3P2的終點，也是邊P2P1的起點，屬于普通連接點的頂點個數(shù)計數(shù)為1。按照“下閉上開”的原則，P2點作為P3P2邊的終點不填充，但作為P2P1的起點被填充。局部最低點的處理原則P0、P3和P5點是局部最低點，如果處理不當，掃描線y＝1會填充區(qū)間[3，8]，結(jié)果填充了P3點和P5點之間的像素，如圖4-15所示。將局部最低點的頂點個數(shù)計數(shù)為2。y＝1的掃描線填充時，共享頂點P3的P3P2邊與P3P4邊加入有效邊表，所以P3點被填充兩次，同理，P4點也被填充兩次。圖4-15局部點的處理局部最高點的處理原則局部最高點的頂點個數(shù)計數(shù)為0，掃描線會自動填充P4點，根據(jù)“下閉上開”原則會自動放棄P1點、P4點和P6點。P1點與P6點將不再填充，P4點被掃描線y=5填充。如圖4-15所示。4.2.3有效邊與有效邊表

有效邊多邊形內(nèi)與當前掃描線相交的邊稱為有效邊（activeedge，AE）。在處理一條掃描線時僅對有效邊進行求交運算，可以避免與多邊形的所有邊求交。有效邊交點之間具有相關性，知道當前掃描線與有效邊的交點坐標，使用增量法可計算出下一條掃描線與有效邊的交點坐標。交點的y坐標就是掃描線，執(zhí)行的是加1操作，交點的x坐標可以按如下方法推導。設有效邊的斜率為k假定有效邊與當前掃描線yi的交點為（xi，yi），則有效邊與下一條掃描線yi+1的交點為（xi+1，yi+1）。其中，，如圖4-16所示，隨著掃描線的移動，掃描線與有效邊交點的x坐標是從邊的起點坐標開始按增量1/k計算出來的。圖4-16有效邊交點之間的相關性2.有效邊表將有效邊按照與掃描線交點的x坐標遞增的順序存放在一個鏈表中，稱為有效邊表（activeedgetable，AET），有效邊表的結(jié)點如圖4-17所示。圖4-17有效邊表結(jié)點圖4-17中，x是當前掃描線與有效邊的交點；ymax是邊所在的掃描線最大值，用于判斷該邊何時掃描完畢后，被拋棄而成為無效邊。對于圖4-2所示的多邊形，頂點表示法為：P0（7，8），P1（3，12），P2（1，7），P3（3，1）,P4（6，5）,P5（8，1）,P6（12，9）。掃描線的最大值為ymax＝12，最小值為ymin＝1。共有12條掃描線，掃描線之間間隔1個像素單位。每條掃描線的有效邊表如圖4～18～圖4-22所示。圖4-18掃描線y=1～y＝3的有效邊表圖4-19掃描線y=4～y＝5的有效邊表y=4的掃描線處理完畢后對于P3P4和P4P5兩條邊，因為下一條掃描線y=5與ymax相等，根據(jù)“下閉上開”的原則予以刪除，如圖4-19所示。圖4-20掃描線y=6～y＝7的有效邊表y=6的掃描線處理完畢后，對于P2P3邊，因為下一條掃描線y=7與ymax相等，根據(jù)“下閉上開”的原則予以刪除。當y＝7時，添加上新邊P1P2，如圖4-20所示。當y＝8時，添加上新邊P0P1和P0P6，如圖4-21所示。這條掃描線處理完畢后對于P5P6邊和P0P6邊，因為下一條掃描線y=9與ymax相等，根據(jù)“下閉上開”的原則予以刪除，如圖4-22所示。圖4-21掃描線y=8的有效邊表y=11的掃描線處理完畢后對于P1P2邊和P0P1邊，因為下一條掃描線y=12與ymax相等，根據(jù)“下閉上開”的原則予以刪除。圖4-22掃描線y=9～y＝11的有效邊表4.2.4桶表與邊表

桶表和邊表的表示法桶表是按照掃描線順序管理邊出現(xiàn)情況的一個數(shù)據(jù)結(jié)構(gòu)。構(gòu)造一個縱向掃描線鏈表，其長度為多邊形所覆蓋的最大掃描線數(shù)，鏈表的每個結(jié)點稱為桶（Bucket）。將每邊信息鏈到與該邊最小y坐標（ymin）相對應的桶結(jié)點。對于一條掃描線，如果新增多條邊，按x|ymin坐標遞增的順序存放在一個鏈表中，若x|ymin

相等，按照1/k由小到大排序，這樣就形成邊表，如圖4-23所示。圖4-23邊表結(jié)點2.桶表與邊表示例圖4-24示例多邊形的桶表與邊表4.3邊緣填充算法4.3.1填充原理

邊緣填充算法是先求出多邊形的每條邊與掃描線的交點，然后將交點右側(cè)的所有像素顏色全部取為補色。按任意順序處理完多邊形的所有邊后，就完成了多邊形的填充任務。邊緣填充算法利用了圖像處理中的求“補”的概念，對于黑白圖像，求補是把顏色為RGB(255,255,255)（白色）的像素置為RGB(0,0,0)（黑色），反之亦然；對于彩色圖像，求補是將背景色置為填充色，反之亦然。4.3.2填充過程

假定邊的訪問順序為E0、E1、E2、E3、E4、E5和E6，如圖4-25所示。圖4-25邊緣填充算法示例多邊形示例多邊形的填充過程如圖4-26所示。

圖4-26邊緣填充算法示意圖邊緣填充算法的效率受到交點右側(cè)像素的數(shù)量影響，右側(cè)像素越多，需要取補的像素也就越多。為了提高填充效率，可以在圖4-27所示多邊形的包圍盒內(nèi)進行像素取補，或者如圖4-28所示，在包圍盒內(nèi)再添加一條柵欄，處理每條邊與掃描線的交點時，只將交點與柵欄之間的像素取補。

圖4-27帶包圍盒的多邊形圖4-28帶柵欄形的多邊形4.4區(qū)域填充算法4.4.1填充原理

對于用點陣方法表示的區(qū)域，如果其內(nèi)部像素具有同一種顏色，而邊界像素具有另一種顏色，如圖4-29所示，可以使用種子填充算法進行填充。種子填充算法是從區(qū)域內(nèi)任一個種子像素位置開始，由內(nèi)向外將種子像素的顏色擴展到整個區(qū)域內(nèi)的填充過程。該算法基于連通域內(nèi)像素的連貫性，以遞歸方式確定區(qū)域內(nèi)部點與邊界點，而不涉及區(qū)域外部的點，從而有效地提高了算法的效率。圖4-29區(qū)域內(nèi)部與邊界表示

4.4.2四鄰接點與八鄰接點

（a）四鄰接點（b）八鄰接點圖4-30鄰接點定義區(qū)域內(nèi)部任意一個種子像素，其左、上、右、下這4個像素稱為四鄰接點，如圖4-30（a）所示。區(qū)域內(nèi)部任意一個種子像素，其左、上、右、下以及左上、右上、右下、左下這8個像素稱為八鄰接點，如圖4-30（b）所示。4.4.3四連通域與八連通域

種子填充算法要求區(qū)域內(nèi)部必須是連通的，才能將種子像素的顏色擴展到區(qū)域內(nèi)部的所有像素點，一般將區(qū)域劃分為四連通域與八連通域兩種。四連通域定義從區(qū)域內(nèi)部任意一個種子像素點出發(fā)，通過訪問其左、上、右、下這4個鄰接點可以遍歷區(qū)域內(nèi)的所有像素點，該區(qū)域稱為四連通域，如圖4-31和圖4-32所示。

八連通域定義從區(qū)域內(nèi)部任意一個種子像素點出發(fā)，通過訪問其左、左上、上、右上、右、右下、下、左下這8個鄰接點可以遍歷區(qū)域內(nèi)的所有像素，該區(qū)域稱為八連通域，如圖4-33和圖4-34所示。

圖4-31四連通域及四連通約束邊界圖4-32四連通域及八連通約束邊界

圖4-33八連通域及四連通約束邊界圖4-34八連通域及八連通約束邊界對于圖4-34所示的八連通域，假定種子像素位于多邊形區(qū)域的左下部區(qū)域內(nèi)，則四鄰接點算法只能填充其左下部區(qū)域，而不能進入其右上部區(qū)域，如圖4-35所示。八鄰接點算法則可以從其左下部區(qū)域進入右上部區(qū)域，填充完整個多邊形區(qū)域，如圖4-36所示。

圖4-35四鄰接點種子填充八連通域圖4-36八鄰接點種子填充八連通域4.4.4種子填充算法1.算法定義從種子像素點開始，使用四鄰接點方式搜索下一像素點的填充算法稱為四鄰接點種子填充算法。從種子像素點開始，使用八鄰接點方式搜索下一像素點的填充算法稱為八鄰接點種子填充算法。2.算法原理種子填充算法一般需要使用堆棧數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)。算法原理為：先將種子像素入棧，種子像素為棧底像素，如果棧不為空，執(zhí)行如下3步操作：（1）棧頂像素出棧；（2）按填充色繪制出棧像素。（3）按左、上、右、下（或左、左上、上、右上、右、右下、下、左下）順序搜索與出棧像素相鄰的4（或8）個像素，若該