計(jì)算機(jī)圖形學(xué)彩版第四章多邊形填充

孔令德

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

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

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

圖4-3多邊形的定義⑴頂點(diǎn)表示法

4.1.2多邊形的表示

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

4.1.3多邊形著色模式

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

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

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

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

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

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

4.2.1填充原理

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

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

P0P5P1P7P6P8P2P3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.4.2四鄰接點(diǎn)與八鄰接點(diǎn)

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

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

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

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

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

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