填充圖元的生成

第四章填充圖元的生成

?掃描轉(zhuǎn)換矩形

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

?掃描轉(zhuǎn)換扇形區(qū)域

?區(qū)域填充

?以圖像填充區(qū)域

-字符的表示與輸出

1

'般步驟

1.確定那些像素位于填充圖元的內(nèi)部

2.確定以什么顏色填充這些像素

2

掃描轉(zhuǎn)換矩形（1/2）

?方法

voidFillRectangle(Rectangle*rect,intcolor)

{intx,y;

for(y=rect->ymin;y<=rect->ymax;y++)

for(x=rect->xmin;x<=rect->xmax;x++)

PutPixel(x,yfcolor);

}/女endofFillRectangleQV

掃描轉(zhuǎn)換矩形（2/2）

?問(wèn)題：

-矩形是簡(jiǎn)單的多邊形，那么為什么要單獨(dú)處

理矩形？

-共享邊界如何處理？

■原則：左閉右開(kāi)，下閉上開(kāi)

屬于誰(shuí)?4

掃描轉(zhuǎn)換多邊形(1/19)

-掃描轉(zhuǎn)換多邊形：將頂點(diǎn)表示形式轉(zhuǎn)換成點(diǎn)

陣表示形式

5

掃描轉(zhuǎn)換多邊形(2/19)

?逐點(diǎn)判斷算法

-方法

voidFillPolygonPbyP(Polygon*P,intpolygonColor)

{intx,y;

for(y=ymin;y<=ymax;y++)

for(x=xmin;x<=xmax;x++)

if(IsInside(P^y))

PutPixel(x,y,polygonColor);

else

PutPixel(x^backgroundColor);

}/*endofFillPolygonPbyP()*/

6

掃描轉(zhuǎn)換多邊形(3/19)

-問(wèn)題：如何判別點(diǎn)(x,y)關(guān)于多邊形區(qū)域P

的內(nèi)外關(guān)系？

-射線(xiàn)法

?步驟：

1.從待判別點(diǎn)V發(fā)出射線(xiàn)

2.求交點(diǎn)個(gè)數(shù)k

3.K的奇偶性決定了點(diǎn)與多邊形的內(nèi)外關(guān)系

?奇異情況處理

掃描轉(zhuǎn)換多邊形(4/19)

累計(jì)角度法

?步驟

1.從v點(diǎn)向多邊形p頂點(diǎn)發(fā)出射線(xiàn)，形成有向角q

2.計(jì)算有相交的和，得出結(jié)論--------------

位于之外

>0.—\vP

占z[±2??位于月之內(nèi)

?奇異情況處理

■例子：五角星

?離散計(jì)算方法：編碼方法

8

掃描轉(zhuǎn)換多邊形(5/19)

-算法優(yōu)點(diǎn)：簡(jiǎn)單

-算法缺點(diǎn)：計(jì)算量太大，速度慢

?掃描線(xiàn)算法

-目標(biāo)：利用像素之間的連貫性，提高算法效

率

處理對(duì)象：非自交多邊形

9

掃描轉(zhuǎn)換多邊形(6/19)

_基本原理演示：Morphlnk

一條掃描線(xiàn)與多邊形的邊有偶數(shù)個(gè)交點(diǎn)

-步驟：

1.求交

2.排序

3.填充

10

掃描轉(zhuǎn)換多邊形(7/19)

-邊的連貫性

■第一類(lèi)交點(diǎn)：新出現(xiàn)的邊與掃描線(xiàn)的交點(diǎn)

?第二類(lèi)交點(diǎn)：位于同一條變上的后繼交點(diǎn)

11

掃描轉(zhuǎn)換多邊形(8/19)

-交點(diǎn)的取整規(guī)則

?要求：使生成的像素全部位于多邊形之內(nèi)

-用于線(xiàn)畫(huà)圖元掃描轉(zhuǎn)換的四舍五入原則導(dǎo)致部分像素

位于多邊形之外，從而不可用

?假定非水平變與掃描線(xiàn)y=e

相交，交點(diǎn)的合作標(biāo)為x,

規(guī)則如下

12

掃描轉(zhuǎn)換多邊形(9/19)

1.X為小數(shù)

?(a)交點(diǎn)位于左邊之上，相右取整

?(b)交點(diǎn)位于右邊之上，相左取整

13

掃描轉(zhuǎn)換多邊形(10/19))

2.(x,e)落在像素之上

-(a)(x,e)位于左邊之上，屬于多邊形

-(b)(x,e)位于右邊之上，不屬于多邊形

14

掃描轉(zhuǎn)換多邊形(11/19)

3.交點(diǎn)位多邊形的頂點(diǎn)

-(a)算作1個(gè)交點(diǎn)

-(b)算作1個(gè)交點(diǎn)

-(c)算作2個(gè)交點(diǎn)

-(d)算作0個(gè)交點(diǎn)

9)

(d)

15

掃描轉(zhuǎn)換多邊形(12/19)

-特殊情況處理

?水平邊:扔掉!

?尖角：凡混淆

掃描轉(zhuǎn)換多邊形(13/19)

-數(shù)據(jù)結(jié)構(gòu)

?邊

typedefstruct{intymax;

floatx,deltax;

Edge^nextEdge;

/Edge;

-邊的分類(lèi)表E

按照變得下端點(diǎn)y坐標(biāo)對(duì)非水平邊進(jìn)行分類(lèi)的指針數(shù)組

?活化邊表AEL

紀(jì)錄與當(dāng)前掃描線(xiàn)相交的邊(交點(diǎn))

17

掃描轉(zhuǎn)換多邊形(14/19)

ET

(a)

(b)

掃描轉(zhuǎn)換多邊形（15/19）

-算法

1、建立ET；

2、將掃描線(xiàn)縱坐標(biāo)y的初值置為ET中非空元素的最小序號(hào)，如在上圖中,

y=i；

3、置AEL為空；

4、執(zhí)行下列步驟直至ET和AEL都為空.

4.1、如ET中的第y類(lèi)非空，則將其中的所有邊取出并插入AEL中；

4.2＞如果有新邊插入AEL,則對(duì)AEL中各邊排序；

4.3＞對(duì)AEL中的邊兩兩配對(duì)，（1和2為一對(duì)，3和4為一對(duì)，…），將每

對(duì)邊中x坐標(biāo)按規(guī)則取整，獲得有效的填充區(qū)段，再填充.

4.4、將當(dāng)前掃描線(xiàn)縱坐標(biāo)y值遞值1；

4.5、將AEL中滿(mǎn)足y=ymax邊刪去（因?yàn)槊織l邊被看作下閉上開(kāi)的）；

4.6＞對(duì)'AEL中剩下的每一條邊的x遞增deltax,BPx=x+deltax.

思考題

19

掃描轉(zhuǎn)換多邊形(16/19)

?邊緣填充算法

-原理：以求余運(yùn)算代替掃描線(xiàn)算法中的排序

運(yùn)算

-求余(A=OxFFFFFFFF)

M=A-M=MXorA

-算法1：(以?huà)呙杈€(xiàn)為中心的邊緣填充算法)

1、將當(dāng)前掃描線(xiàn)上的所有象素著上值為防的顏色；

2、求余：

for(i=0;i<=m;i++)

在當(dāng)前掃描線(xiàn)上，從x坐標(biāo)為交點(diǎn)向右求余；

20

掃描轉(zhuǎn)換多邊形(17/19)

(a)(b)

(c)(d)21

掃描轉(zhuǎn)換多邊形(18/19)

-算法2：(以邊為中心的邊緣填充算法)

1、將繪圖窗口的背景色置為；

2、對(duì)多邊形的每一條非水平邊做：

從該邊上的每個(gè)象素開(kāi)始向右求余;

22

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

23

掃描轉(zhuǎn)換扇形區(qū)域（1⑸

?扇形區(qū)域的描述

■原理：同掃描轉(zhuǎn)換多邊形

?問(wèn)題：如何確定掃描線(xiàn)與直線(xiàn)段和圓弧

段的相交順序

?方法：分類(lèi)

按點(diǎn)，和P2點(diǎn)所處象限的不同，需要將扇形區(qū)域分成

4X4=16種情況

掃描轉(zhuǎn)換扇形區(qū)域(2/5)

?假設(shè)2點(diǎn)落在第一象限，扇形區(qū)域的掃描

轉(zhuǎn)換分四種情況

1、22落在第一象限

25

掃描轉(zhuǎn)換扇形區(qū)域(3/5)

2、2落在第二象限,

?當(dāng)時(shí)

?當(dāng)乂>^2時(shí)

掃描轉(zhuǎn)換扇形區(qū)域(4/5)

掃描轉(zhuǎn)換扇形區(qū)域(5/5)

?遺留問(wèn)題：當(dāng)小落在其它區(qū)域時(shí)？

?其它方法：

多邊形迫近方法

28

區(qū)域填充(1/10)

?區(qū)域：點(diǎn)陣表示的圖形，像素集合

?表示方法：內(nèi)點(diǎn)表示、邊界表示

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

-枚舉處區(qū)域內(nèi)部的所有像素

-內(nèi)部的所有像素著同一個(gè)顏色

-邊界像素像素著與內(nèi)部像素不同的顏色

?邊界表示

-枚舉出邊界上所有的像素

-邊界上的所有像素著同一顏色

-內(nèi)部像素著與邊界像素不同的顏色

29

區(qū)域填充(2/10)

?區(qū)域填充

-將指定的顏色從種子點(diǎn)擴(kuò)展到整個(gè)取得過(guò)程

例子：PaintBrush例子：PhotoShop

30

區(qū)域填充(3/10)

?連通性：4連通、8連通

31

區(qū)域填充(4/10)

?4連通與8連通區(qū)域的區(qū)別

-連通性

-對(duì)邊界的要求

32

區(qū)域填充(5/10)

?遞歸填充算法

-內(nèi)點(diǎn)表示的4連通區(qū)域

voidFloodFill4(intx,inty,intoldColor,intnewColor)

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

{PutPixel(x9yfnewColor);

FloodFill4(xfy+l9oldColor,newColor);

FloodFill4(x,y-l,oldColor,newColor);

FloodFill4(x-l,y9oldColor,newColor);

FloodFill4(x+l,y,oldColor,newColor);

}

*endofFloodFill4()V

33

區(qū)域填充(6/10)

34

區(qū)域填充(7/10)

-邊界表示的4連通區(qū)域

voidBoundaryFill4(intx,intyfintoldColorjntnewColor)

{intcolor;

color=GetPixel(x,y);

if((color!=boundaryColor)&&(color!=newColor))

{PutPixel(x,y,newColor);

BoundaryFill4(x,y^r1,oldColor,newColor);

BoundaryFill4(x,y-l,oldColor,newColor);

BoundaryFill4(x-1,y,oldColor,ne^Color);

BoundaryFill4(x+1fy,oldColor,newColor);

)

}/*endofBoundaryFill4()*/

35

區(qū)域填充(8/10)

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

-遞歸填充算法的特點(diǎn)

?算法、程序簡(jiǎn)單

?遞歸層次太多，效率極低

■例子：判斷填充方法

例子：PaintBrush例子：PhotoShop

36

區(qū)域填充(9/10)

?掃描線(xiàn)算法

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

-