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

"Qmputd

直線的掃描轉(zhuǎn)換

圓的掃描轉(zhuǎn)換

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

區(qū)域填充

光柵圖形的反走樣算法

2009-2010-2:CG:SCUEC

邊界標(biāo)志舁法--基本思想

首先用一種特殊的顏色在幀緩存中將

多邊形的邊界（水平邊的部分邊界除

外）勾畫出來，然后再把位于多邊形

內(nèi)的各個區(qū)段著上所需的顏色。

對幀緩沖存儲器中的每個元素的賦值

次數(shù)不超過2次。

、才由房施大與2009-2010-2:CG:SCUEC3

邊界標(biāo)志算法一算法實(shí)現(xiàn)

EdgeMarkFill(intp[][2],intn,intboundary_color,intpolygoncolor)

{inti,x,y,inflag,xmin,xmax,ymin,ymax;,-----

setcolor(boundary_color);/*設(shè)置畫筆色*/步驟1：以值為

boundary-color

fdr(i=O;i<n;i++)

的特殊顏色勾畫

皿皿

line(p0],p1],p[(i+l)%n][0],p[(i+l)%n])[l]);多邊形P的邊界。

從多邊形頂點(diǎn)數(shù)組p中，求出xmin,xmax,ymin,ymax;

fdr(y=ymin;y<=ymax;y++){

步驟2：求出多邊形

inflag=0;的最小包圍矩形。

fdr(x=xmin;x<=xmax;x++){

步驟3：逐條掃描線進(jìn)行

if(getpixel(x,y)==boundary_color)處理，對每條掃描線依

inflag=-inflag;從左往右的順序，逐個

if(inflag==l)訪問該掃描線上的像素。

putpixel(x,y,polygoncolor);每遇到邊界像素，標(biāo)志

取反。然后，按照標(biāo)志

}//endofinnerfbrloop

是否為真，決定像素是

}//endofouterfbrloop否為填充色。

}//endofalgorithm

'04南》號2009-2010-2:CG:SCUEC

邊界標(biāo)志算法一錯誤處理

?:?該算法雖然簡單，但程序運(yùn)行后會出現(xiàn)局部錯誤。

?錯誤1

-現(xiàn)象：填充時會出現(xiàn)“抽絲”。即某掃描線上不該填

充的區(qū)段填上色，而應(yīng)該填充的區(qū)段卻沒有填上色。

-原因：對于多邊形頂點(diǎn)為局部極值點(diǎn)時，掃描線與多

邊形的相交次數(shù)不再是偶數(shù)，而是奇數(shù)。

解決的辦法：判斷多邊形頂點(diǎn)的性質(zhì)，如果是局部極

值點(diǎn)，那么掃描線碰上它則不改變標(biāo)志。

,彳擊A施大亨2009-2010-2:CG:SCUEC5

-現(xiàn)象：當(dāng)掃描線y遇到|斜率|vl的邊界線時，碰到幾個邊界點(diǎn)，會

引起標(biāo)志的無序改變，將導(dǎo)致填充的錯誤。如圖（1）所示。

原因：在對多邊形的邊界進(jìn)行掃描轉(zhuǎn)換的時候，考慮了不同斜率

的情況，即|斜率|>1的時候以y為步進(jìn)方向，而|斜率的時候以x

為步進(jìn)方向。

-解決的辦法：對于不同斜率的邊界，都要使用斜率大于1的直線掃

描轉(zhuǎn)換方法：每次y方向增長一步，x方向增長1/m步距，以保證

掃描線y遇到斜率小于1的邊界時，只能遇到一個點(diǎn)。如圖（2）所示。

圖（1）錯誤的邊界圖（2）正確的邊界

O、彳由又菠攵身2009-2010-2:CG:SCUEC6

而又施人與2009-2010-2:CG:SCUEC7

區(qū)域填充

區(qū)域填充是指先修區(qū)域內(nèi)的

一點(diǎn)（常稱種子點(diǎn)）賦予給定

顏色，然后將這種顏色擴(kuò)展

到整個區(qū)域內(nèi)的過程。

@、彳.由A四大專2009-2010-2:CG:SCUEC8

內(nèi)點(diǎn)表示

把位于給定區(qū)域內(nèi)的所有像

素列舉出來的方法稱為

內(nèi)點(diǎn)表示法。它將區(qū)域內(nèi)的

■

所有像素填充成同一種顏色

（常稱為原色），而區(qū)域邊

界上的像素則不能填這種顏

色。如右圖，有?的方格表示

內(nèi)點(diǎn)，在內(nèi)點(diǎn)處像素填原色。內(nèi)點(diǎn)表示的區(qū)域

0彳94熱火手2009-2010-2:CG:SCUEC9

邊界表示法

把位于給定區(qū)域邊界上的像素

漢長漢漢漢

---列舉出來的方法稱為邊界次漢

汝漢

表示法。它將區(qū)域邊界上的像笈漢

漢漢漢漢漢

素都著上同一種顏色（常稱為漢漢漢笈

邊界色），而區(qū)域內(nèi)的像素則漢漢漢漢笈漢

漢漢

不能著這種顏色。如右圖，有漢漢

漢漢漢漢漢漢漢漢

X的方格表示邊界點(diǎn)，在邊界

點(diǎn)處像素填邊界色。邊界表示的區(qū)域

由士蘇?無？2009-2010-2:CG:SCUEC10

區(qū)域的表示和類型

區(qū)域的連通性

C四連通的區(qū)域是指從該區(qū)域內(nèi)一

點(diǎn)出發(fā)，通過上、下、左、右四

種運(yùn)動（如圖A）的組合，在不

越出區(qū)域的前提下，可到達(dá)區(qū)域

內(nèi)的任一點(diǎn)。圖A四個方向的運(yùn)動

Q八連通的區(qū)域是指從該區(qū)域內(nèi)一

點(diǎn)出發(fā)，通過沿水平方向、垂直

方向和對角線方向的八種運(yùn)動

（如圖B）的組合，在不越出區(qū)

域的前提下，可到達(dá)區(qū)域內(nèi)的任

—?八占、、。圖B八個方向的運(yùn)動

OI、才由又熱大與2009-2010-2:CG:SCUEC11

內(nèi)點(diǎn)表示的四連通區(qū)域邊界表示的四連通區(qū)域

內(nèi)點(diǎn)表示的八連通區(qū)域邊界表示的八連通區(qū)域

'彳由1押人辱2009-2010-2:CG:SCUEC12

e1…——■■^■iilli?t>—

四連通區(qū)域也可理解成八連通區(qū)域，

但兩者的邊界不盡相同。若將右圖中

標(biāo)有?號的像素組成的區(qū)域作為四連

通區(qū)域，則其邊界由圖中標(biāo)有△號的

像素組成。若將該區(qū)域作為八連通區(qū)

域，則其邊界由圖中標(biāo)有△號和X號

四連通區(qū)域與八連通區(qū)

的兩種像素組成。

域的不同邊界

_______________________________________________________￡

，用于八連通區(qū)域的填充算法可用于四連通區(qū)域的填充，但用

于四連通區(qū)域的填充算法并不適用于八連通區(qū)域的填充。

而又施人與2009-2010-2:CG:SCUEC13

/、設(shè)（X,y）是內(nèi)點(diǎn)表示的一區(qū)域G內(nèi)

本思鳥'的一點(diǎn)，old_color是G的原色。先取

（”）點(diǎn)為,子點(diǎn)，測試其顏色，

若等于old_color,說明是區(qū)域內(nèi)一

點(diǎn)，則將其置為新的顏色new_color,否則說明該點(diǎn)不

在區(qū)域G內(nèi)，則停止填充；然后將該點(diǎn)周圍的四個點(diǎn)

（四連通）或八個點(diǎn)（八連通）作為新的種子點(diǎn)進(jìn)行同

樣的處理，通過這種擴(kuò)散完成對整個區(qū)域的填充。顯然,

這一過程是用遞歸實(shí)現(xiàn)的。

0彳94熱火手2009-2010-2:CG:SCUEC14

遞歸算法（內(nèi)點(diǎn)表示的4連通區(qū)域）

flood_fill_4(intx,inty,intoldcolor,intnewcolor)

if(getpixel(framebuffer,x,y)==old_color)

(

setpixel(framebuffer,x,y,newcolor);

flood_fill_4(x,y+l,old_color,new_color);

floodfill_4(x,y-l,old_color,new_color);

floodfill_4(x-l,y,old_color,new_color);

flood_fill_4(x+l,y,old_color,new_color);

}

)

Oi、彳由I族大博2009-2010-2:CG:SCUEC15

試確定下圖區(qū)域中的點(diǎn)填充的順序，黑色點(diǎn)為種子點(diǎn)。

O],才由又熱大與2009-2010-2:CG:SCUEC16

掃描線種子填充算法

目標(biāo)：減少遞歸層次

目標(biāo)及范圍J

范圍：適用于邊界表示的4連通區(qū)域

從給定的種子點(diǎn)開始，先填充種子點(diǎn)

所在掃描線上的位于給定區(qū)域內(nèi)的一

個區(qū)間，然后確定與這一區(qū)間相鄰的

上下兩條掃描線上需要填充的區(qū)間，

從這些區(qū)間上各取一個種子點(diǎn)并依次

保存下來，作為下次填充的種子點(diǎn)，

反復(fù)進(jìn)行這個過程，直到所保存的各

區(qū)間都填充完畢。

’市又施人與2009-2010-2:CG:SCUEC17

掃描線種子填充算法

①將堆棧置空，并修給定的種子點(diǎn)

算法步驟（x,y）壓入堆棧。

②若堆棧為空，算法結(jié)束；否則取

棧頂元素（%了）作為種子點(diǎn)。

③從種子點(diǎn)（x,y）出發(fā)，沿縱坐標(biāo)為J的當(dāng)前掃描線

向左右兩個方向用新的顏色逐個像素地填充，直到

邊界。設(shè)區(qū)間兩邊界的橫坐標(biāo)分另1為X⑷和X.，。

④以區(qū)間］為搜索范圍，檢查與當(dāng)前掃描線相

鄰的上下兩條掃描線上的像素，若存在非邊界、未

填充的像素，則把相應(yīng)小區(qū)間中最右邊的點(diǎn)作為種

子點(diǎn)壓入堆棧，轉(zhuǎn)入②。

、，’市又施人與2009-2010-2:CG:SCUEC18

掃描線種子填充算法

push(x,y);/*種子壓入堆棧*/FB:FramBuffer

while(stack-not-empty)B:Boundary算法實(shí)現(xiàn)

N:New

pop(x,y)；/*從堆棧中取一種子象素*/

savex=x:/*保存橫坐標(biāo)x的值*/x=savex-1;/*向種子的左邊填充*/

while(getpixel(FB,x,y)<>B-color)while(getpixel(FB,x,y)<>B-color)

setpixel(FB,x,y,N-color);setpixel(FB,x,y,N-color);

x=x+lx=x-1

}

xright=x-1/*保存線段的右端點(diǎn)*/xle仕=x+l/*保存線段的左端點(diǎn)*/

’市又施人與2009-2010-2:CG:SCUEC19

while(((getpixel(FB,x,y)=B-color)

(getpixel(FB,x,y)=N-color))&&(x<xright))

span-need-fill=false;(

while((getpixel(FB,x,y)<>N-color)x=x+1;

&&(getpixel(FB,x,y)<>B-color))

(

}/*在上一條掃描上檢查完*/

span-need-fill=true;

x=x+1;y=y-2;

}/*在掃描線y-1上從左向右地檢查位于區(qū)間

igspan—need—fill)[xletft,xright]上的象素，其方法與在掃描線

{

y+1上檢查的情況完全一樣，故略去詳情*/

push(x-l,y);/*右端點(diǎn)進(jìn)棧*/

span-need-fill=false;/*出棧完*/

掃描線種子填充算法演示例子

2009-2010-2:CG:SCUEC20

■取多邊形內(nèi)一點(diǎn)作為種子點(diǎn)，用Bresenham或DDA算法將多邊形的邊界

表示成8連通區(qū)域，則多邊形的掃描轉(zhuǎn)換問題轉(zhuǎn)化為區(qū)域填充問題

■如果知道多邊形區(qū)域的頂點(diǎn)表示，區(qū)域填充問題亦可轉(zhuǎn)化為多邊形的掃

描轉(zhuǎn)換問題

?差別:

■基本思想不同

?掃描轉(zhuǎn)換將多邊形的頂點(diǎn)表示轉(zhuǎn)換成點(diǎn)陣表示，掃描過程中利用了

多邊形各種形式的連貫性

?區(qū)域填充只改變區(qū)域的顏色，不改變區(qū)域的表示方法，填充過程中

利用的區(qū)域的連通性

■對邊界要求不同

?掃描轉(zhuǎn)換允許不封閉的區(qū)域，區(qū)域填充不可以

■出發(fā)點(diǎn)不同

?區(qū)域填充要求指定區(qū)域內(nèi)的一點(diǎn)作為種子點(diǎn)，從該點(diǎn)開始進(jìn)行區(qū)域

填充，掃描轉(zhuǎn)換沒有這個要求

O、才由房施大冬2009-2010-2:CG:SCUEC21

光柵圖形的走樣問題

用離散量（像素）表示連續(xù)的量（圖形）

而引起的失真，稱作走樣。

走樣現(xiàn)篆工力Q產(chǎn)生階梯狀的邊界

^Q圖形的細(xì)節(jié)失真

、狹小圖形遺失，動畫序列

中時隱時現(xiàn)，產(chǎn)生閃爍

0彳94熱火手2009-2010-2:CG:SCUEC22

走樣現(xiàn)象（1/3）

?:?不光滑（階梯狀）的圖形邊界

階梯性線段階梯性邊界

彳市4羔女多2009-2010-2:CG:SCUEC23

走樣現(xiàn)象(2/3)

?圖形細(xì)節(jié)失真

、才由補(bǔ)大與

?A2009-2010-2:CG:SCUEC24

走樣現(xiàn)象(3/3)

*狹小圖形的遺失與動態(tài)圖形的閃爍

(a)

待顯

示的

狹小

矩形

(b顯)

示

結(jié)

果

O1、彳由I族大博2009-2010-2:CG:SCUEC25

反走樣方法

在圖形顯示過程中，用于減少或

消除走樣現(xiàn)象的方法

常用方法Q提高分辨率方法

Q非加權(quán)區(qū)域采樣

Q加權(quán)區(qū)域采樣

Oi、彳由I族大博2009-2010-2:CG:SCUEC26

提高分辨率的反走樣方法

提高分辨率的方法有兩種:

第一種是提高硬件的分辨率O

O1,才由又施大岑2009-2010-2:CG:SCUEC27

提高分辨率的反走樣方法

第二種是采用軟件的方法，高分辨率計(jì)算，低分辨率顯示。

高分辨率計(jì)算是指將低分辨的圖形顯示像素劃分為許多子像素,

然后計(jì)算出各個子像素的顏色值或灰度值。

低分辨率顯示是指將一像素內(nèi)的各個子像素的顏色值或灰度值的

平均值作為該像素顯示時的顏色值或灰度值。求平均值時可取算術(shù)

平均，也可取加權(quán)平均。下圖所示的是兩種典型的加權(quán)平均方法。

1234321

2468642

36912963

4812161284

36912963

2468642

1234321

(b)

◎才由*2009-2010-2:CG:SCUEC28

理想情況

1、像素是數(shù)學(xué)上抽象的點(diǎn)，它的面積為0,它的

亮度由覆蓋該點(diǎn)的圖形的亮度所決定；

2、直線段是數(shù)學(xué)上抽象直線段，它的寬度為0。

■現(xiàn)實(shí)情況

?像素的面積不為0；

?直線段的寬度至少為1個像素；

■理想與現(xiàn)實(shí)的矛盾是導(dǎo)致走樣出現(xiàn)的原因之一

I,才由信猊人塔

O2009-2010-2:CG:SCUEC29

非加權(quán)區(qū)域采樣方法

受假定每個像素都是一個具有一定面積的小

區(qū)域，將直線段看作具有一定寬度的狹長

矩形（如下圖所示）。

，當(dāng)線段通過某像素時，可以求出兩者相交

區(qū)域的面積。

Q根據(jù)相交面積的大小來確定該像素的顏色

值或灰度值。

Oi、彳由I族大博2009-2010-2:CG:SCUEC30

Q直線段對一個像素亮度的貢獻(xiàn)與兩者相交

區(qū)域的面積成正比，從而和像素中心點(diǎn)距

直線段的距離成反比（因?yàn)橄袼刂行狞c(diǎn)距直

線段距離越遠(yuǎn)，相交區(qū)域的面積越?。?/p>

Q當(dāng)直線段和某個像素不相交時，它對該像

素的亮度無影響；

Q相同面積的相交區(qū)域?qū)ο袼氐牧炼蓉暙I(xiàn)相

同，而與這個相交區(qū)域落在像素內(nèi)什么位

置無關(guān)。

關(guān)鍵：如何計(jì)算這個面積?

O、才由又熱大與2009-2010-2:CG:SCUEC31

有寬度的線條輪廓象素相交的五種情況及用于計(jì)算面積的量

-情況⑴（5）陰影面積為：D2/2m;

—情況⑵（4）陰影面積為：D-m/2;

-情況⑶陰影面積為：1-D2/m

像素實(shí)際顯示的灰度值==所得面積*該像素的最大灰度值

、才由房施大與2009-2010-2:CG:SCUEC32

非加權(quán)區(qū)域采樣方法

Q為了簡化運(yùn)算，有時候還

離散方法可以采用離散的方法。

Q將屏幕像素均分成n個子

像素。

Q計(jì)算中心點(diǎn)落在直線段內(nèi)

的子像素的個數(shù)k,那么

該像素的亮度就是最大灰

度值乘以相交區(qū)域面積的

近似值k/n。

1左圖所示是n=9,k=3,

近似面積為1/3的情況。

Oi、彳由I族大博2009-2010-2:CG:SCUEC33

非加權(quán)區(qū)域采樣方法』算您

上面的區(qū)域采樣算法存在著兩個缺點(diǎn):

Q一是像素的亮度與相交區(qū)域的面積成正比，而與

相交區(qū)域落