計(jì)算機(jī)圖形學(xué) 第四講 區(qū)域填充

第四講

區(qū)域填充計(jì)算機(jī)圖形學(xué)中，多邊形區(qū)域有兩種重要的表示方法：頂點(diǎn)表示和點(diǎn)陣表示。所謂頂點(diǎn)表示，即是用多邊形的頂點(diǎn)序列來(lái)表示多邊形。這種表示直觀、幾何意義強(qiáng)、占內(nèi)存少，易于進(jìn)行幾何變換，但由于它沒(méi)有明確指出哪些像素在多邊形內(nèi)，故不能直接用于區(qū)域填充。所謂點(diǎn)陣表示，則是用位于多邊形內(nèi)的像素集合來(lái)刻畫(huà)多邊形。這種表示丟失了許多幾何信息，但便于進(jìn)行填充。根據(jù)區(qū)域的定義，可以采用不同的填充算法，其中最具代表性的是：適應(yīng)于頂點(diǎn)表示的掃描線類算法和適應(yīng)于點(diǎn)陣表示的種子填充類算法。

復(fù)雜邊界從內(nèi)部指定位置開(kāi)始填充，遞歸填充直至邊界簡(jiǎn)單邊界通過(guò)掃描線與邊界交點(diǎn)確定填充區(qū)域掃描線算法掃描線多邊形區(qū)域填充算法基本原理是，待填充區(qū)域按Y方向(X方向亦可)掃描線順序掃描生成。具體實(shí)現(xiàn)時(shí)，首先按掃描線順序，計(jì)算掃描線與多邊形的相交區(qū)間；再用要求的顏色填充這些區(qū)間內(nèi)的像素，即完成這一條掃描線的填充工作。區(qū)間的端點(diǎn)可以通過(guò)計(jì)算掃描線與多邊形邊界線的交點(diǎn)獲得。對(duì)于一條掃描線，多邊形的填充過(guò)程可以分為四個(gè)步驟：(1)求交：計(jì)算掃描線與多邊形各邊的交點(diǎn)；(2)排序：把所有交點(diǎn)按x值遞增順序排序；(3)配對(duì)：第一個(gè)與第二個(gè)，第三個(gè)與第四個(gè)等等；每對(duì)交點(diǎn)代表掃描線與多邊形的一個(gè)相交區(qū)間；(4)填色：把相交區(qū)間內(nèi)的像素置成多邊形顏色，把相交區(qū)間外的像素置成背景色。為了提高速度，假定當(dāng)前掃描線與多邊形某一條邊的交點(diǎn)的x坐標(biāo)為xi，則下一條掃描線與該邊的交點(diǎn)不要重新計(jì)算，而是通過(guò)增加一個(gè)增量△x來(lái)獲得。具體方法是：設(shè)該邊的直線方程為：ax+by+c=0；若y＝y(tǒng)i，x=xi；則當(dāng)y=yi+1=yi+1時(shí)，其中為常數(shù)，yiyi+1(xi,yi)交點(diǎn)計(jì)算交點(diǎn)數(shù)的處理多邊形Pi的頂點(diǎn)可分為兩類：如果(yi-1-yi)(yi+1-yi)≥0，則稱頂點(diǎn)Pi為局部最高點(diǎn)或最低點(diǎn)，按兩個(gè)交點(diǎn)計(jì)算，否則按一個(gè)交點(diǎn)計(jì)算。不計(jì)算水平邊和掃描線的交點(diǎn)水平邊處理數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟輸入?yún)?shù)頂點(diǎn)數(shù)和頂點(diǎn)坐標(biāo)數(shù)據(jù)結(jié)構(gòu)有序邊表活化邊表有序邊表有序邊表的構(gòu)建按頂點(diǎn)輸入順序依次形成邊，存儲(chǔ)到每條最小Y值所對(duì)應(yīng)的掃描線位置（水平邊除外），相同最小Y值的邊按較低頂點(diǎn)X值的升序排列。有序邊表結(jié)構(gòu)typedef

struct

tEage{int

yUpper;floatxIntersect;floatdxPerScan;struct

tEage*next;}Eage活化邊表把與當(dāng)前掃描線相交的邊稱為活化邊，并把它們按與掃描線交點(diǎn)X坐標(biāo)遞增的順序存放在一個(gè)鏈表中，形成活化邊表。算法中采用較靈活的數(shù)據(jù)結(jié)構(gòu)。它由邊的分有序邊表ET（EdgeTable）和邊的活化邊表AEL（ActiveEdgeTable

）兩部分組成。表結(jié)構(gòu)ET和AET中的基本元素為多邊形的邊。邊的結(jié)構(gòu)由以下四個(gè)域組成：

ymax

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

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

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

next指向下一條邊的指針。

表結(jié)構(gòu)舉例：724^P5P178-1^P2P1620^P4P536-2P3P4560.5^P3P2^^^(Ymax,x,Δx,next)

有序邊表活化邊表34-2P3P456.50.5^P3P2掃描線2AET指針620P4P5570.5^P3P2掃描線3AET指針(Ymax,x,Δx,next)36-2P3P4560.5^P3P2掃描線1AET指針620P4P557.50.5^P3P2掃描線4AET指針620P4P578-1^P2P1掃描線5AET指針724P5P178-1^P2P1掃描線6AET指針

voidpolyfill(polygon,color){

for(各條掃描線，標(biāo)識(shí)為i) {

初始化新邊表頭指針NET[i]；把ymin=i的邊放進(jìn)邊表NET[i]；

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

for(各條掃描線i){

把新邊表NET[i]中的邊結(jié)點(diǎn)用插入排序法插入AET表，使之按x坐標(biāo)遞增順序排列；

遍歷AET表，把配對(duì)交點(diǎn)區(qū)間上的像素(x,y)，用drawpixel(x,y,color)改寫(xiě)像素顏色值；

遍歷AET表，把ymax=i的結(jié)點(diǎn)從AET表中刪除，并把ymax>i結(jié)點(diǎn)的x值遞增x；

}}多邊形填充的算法流程掃描線算法特點(diǎn)：算法效率較高。缺點(diǎn)：對(duì)各種表的維持和排序開(kāi)銷太大，適合軟件實(shí)現(xiàn)而不適合硬件實(shí)現(xiàn)。內(nèi)外測(cè)試目標(biāo)：鑒別非標(biāo)準(zhǔn)多邊形的內(nèi)部區(qū)域自相交多邊形。方法奇偶規(guī)則非零環(huán)繞數(shù)規(guī)則奇偶規(guī)則從位置P作不經(jīng)過(guò)頂點(diǎn)的射線計(jì)算射線穿過(guò)多邊形的邊數(shù)奇數(shù)為內(nèi)部點(diǎn)，否則為外部點(diǎn)非零環(huán)繞數(shù)規(guī)則環(huán)繞數(shù)初始為零；從位置P作不經(jīng)過(guò)頂點(diǎn)的射線；多邊形從右至左穿過(guò)射線，加1；多邊形從左至右穿過(guò)射線，減1；非零為內(nèi)部點(diǎn)；舉例：種子填充算法區(qū)域：用點(diǎn)陣形式表示的填充圖形，是像素的集合。區(qū)域可采用內(nèi)點(diǎn)表示和邊界表示兩種表示形式。內(nèi)點(diǎn)表示法，指區(qū)域內(nèi)的所有像素著同一顏色；邊界表示法，則是指區(qū)域的邊界點(diǎn)著同一顏色。區(qū)域填充算法要求區(qū)域是連通的，因?yàn)橹挥性谶B通區(qū)域中，才可能將種子點(diǎn)的顏色擴(kuò)展到區(qū)域內(nèi)的其它點(diǎn)。區(qū)域可分為4向連通區(qū)域和8向連通區(qū)域。4向連通區(qū)域指的是從區(qū)域上一點(diǎn)出發(fā)，可通過(guò)四個(gè)方向，即上、下、左、右移動(dòng)的組合，在不越出區(qū)域的前提下，到達(dá)區(qū)域內(nèi)的任意像素；8向連通區(qū)域指的是從區(qū)域內(nèi)每一像素出發(fā)，可通過(guò)八個(gè)方向，即上、下、左、右、左上、右上、左下、右下這八個(gè)方向的移動(dòng)的組合來(lái)到達(dá)。

四個(gè)方向運(yùn)動(dòng)八個(gè)方向運(yùn)動(dòng)四連通區(qū)域八連通區(qū)域算法原理：填充區(qū)域邊界以一種顏色指定，從區(qū)域的一個(gè)內(nèi)部點(diǎn)開(kāi)始，由內(nèi)至外繪制直到邊界。適用于單色邊界的填充。四連通的局限性voidFloodFill4(intx,int

y,int

oldcolor,int

newcolor){

if(GetPixel(x,y)==oldcolor) {

SetPixel(x,y,newcolor); FloodFill4(x,y+1,oldcolor,newcolor); FloodFill4(x,y-1,oldcolor,newcolor); FloodFill4(x-1,y,oldcolor,newcolor); FloodFill4(x+1,y,oldcolor,newcolor);}}設(shè)(x,y)為內(nèi)點(diǎn)表示的4連通區(qū)域內(nèi)的一點(diǎn)，oldcolor為區(qū)域的原色，要將整個(gè)區(qū)域填充為新的顏色newcolor。內(nèi)點(diǎn)表示的4連通區(qū)域的遞歸填充算法:

簡(jiǎn)單的種子填充算法voidBoundaryFill4(intx,int

y,int

boundarycolor,int

newcolor){

intcolor; if(color!=newcolor&&color!=boundarycolor) {

SetPixel(x,y,newcolor); BoundaryFill4(x,y+1,boundarycolor,newcolor); BoundaryFill4(x,y-1,boundarycolor,newcolor); BoundaryFill4(x-1,y,boundarycolor,newcolor); BoundaryFill4(x+1,y,boundarycolor,newcolor);}}邊界表示的4連通區(qū)域的遞歸填充算法:

掃描線種子填充算法簡(jiǎn)單種子填充算法原理和程序都很簡(jiǎn)單，但由于多次遞歸，費(fèi)時(shí)、費(fèi)內(nèi)存，效率不高。為了減少遞歸次數(shù)，提高效率可以采用掃描線種子填充算法。算法的基本過(guò)程如下：當(dāng)給定種子點(diǎn)(x,y)時(shí)，首先填充種子點(diǎn)所在掃描線上的位于給定區(qū)域的一個(gè)區(qū)段，然后確定與這一區(qū)段相連通的上、下兩條掃描線上位于給定區(qū)域內(nèi)的區(qū)段，并依次保存下來(lái)。反復(fù)這個(gè)過(guò)程，直到填充結(jié)束。1234123451234512341234123區(qū)域填充的掃描線算法可由下列四個(gè)步驟實(shí)現(xiàn)：(1)初始化：堆棧置空。將種子點(diǎn)(x，y)入棧；