Bài giảng Đồ họa máy tính - Các thuật toán tô màu

ÑOÀ HOÏA MAÙY TÍNH

Caùc thuaät toaùn toâ maøu

ù ä ù â ø

Daãn nhaäp

ã

ä

• Moät vuøng toâ thöôøng ñöôïc xaùc ñònh bôûi moät ñöôøng

kheùp kín naøo ñoù goïi laø ñöôøng bieân. Daïng ñöôøng bieân

ñôn giaûn thöôøng gaëp laø ña giaùc.

• Coù hai daïng vuøng toâ thöôøng gaëp : toâ baèng moät maøu

thuaàn nhaát (solid fill) vaø toâ theo moät maãu toâ (fill-

pattern) naøo ñoù.

• Vieäc toâ maøu thöôøng ñöôïc chia laøm hai coâng ñoaïn :

♦ Xaùc ñònh vò trí caùc ñieåm caàn toâ maøu.

♦ Quyeát ñònh toâ caùc ñieåm treân baèng maøu naøo. Coâng ñoaïn

naøy thöïc söï phöùc taïp khi ta caàn toâ theo moät maãu toâ naøo

ñoù chöù khoâng phaûi toâ thuaàn moät maøu.

• Coù hai caùch tieáp caän chính : toâ maøu theo doøng queùt

vaø toâ maøu döïa theo ñöôøng bieân.

♦ Phöông phaùp toâ maøu döïa theo doøng queùt seõ xaùc ñònh

phaàn giao cuûa caùc doøng queùt keá tieáp nhau vôùi ñöôøng bieân

cuûa vuøng toâ, sau ñoù seõ tieán haønh toâ maøu caùc ñieåm thuoäc

phaàn giao naøy. Caùch naøy thöôøng ñöôïc duøng ñeå toâ maøu ña

giaùc, ñöôøng troøn, ellipse vaø moät soá ñöôøng cong ñôn giaûn

khaùc.

♦ Phöông phaùp toâ maøu döïa theo ñöôøng bieân seõ baét ñaàu töø

moät ñieåm beân trong vuøng toâ vaø töø ñoù loang daàn ra cho

ñeán khi gaëp ñieåm bieân. Caùch naøy thöôøng ñöôïc duøng cho

caùc daïng ñöôøng bieân phöùc taïp.

Döông Anh Ñöùc, Leâ Ñình Duy

Caùc thuaät toaùn toâ maøu 1/16

ÑOÀ HOÏA MAÙY TÍNH

Thuaät toaùn toâ theo doøng queùt

ä ù â ø ù

Baøi toaùn ñaët ra : Caàn toâ maøu moät ña giaùc cho bôûi N ñænh

P x_i, y_i,i = 0,...N − 1

( )

. Ña giaùc naøy coù theå laø ña giaùc loài, ña

giaùc loõm, vaø caû ña giaùc töï caét, …

i

Toùm taét caùc böôùc chính cuûa thuaät toaùn

ù

é ù

ù

û

ä

ù

y_topy_bottom

laàn löôït laø giaù trò lôùn nhaát, nhoû

• Tìm

,

nhaát cuûa taäp caùc tung ñoä cuûa caùc ñænh cuûa ña giaùc ñaõ

y_bottom= min{y_i,

(

x_i, y_i

)

P}

.

y_top= max

{y_i,

(

x_i, y_i

)

P}

cho:

,

y = k

k

• ÖÙng vôùi moãi doøng queùt

, vôùi

thay ñoåi töø

y_top

y

_bottomñeán

, laëp :

y = k

♦ Tìm taát caû caùc hoaønh ñoä giao ñieåm cuûa doøng queùt

vôùi caùc caïnh cuûa ña giaùc.

♦ Saép xeáp caùc hoaønh ñoä giao ñieåm theo thöù töï taêng daàn :

x₀, x₁, x₂,...,

y = k

♦ Toâ maøu caùc ñoaïn thaúng treân ñöôøng thaúng

laàn löôït

(

x₀, x₁),(x₁,x₂),...,(x_2k, x_2k+1)

.

ñöôïc giôùi haïn bôûi caùc caëp

y

y_top

0

1

2

3

y_bottom

x

O

Döông Anh Ñöùc, Leâ Ñình Duy

Caùc thuaät toaùn toâ maøu 2/16

ÑOÀ HOÏA MAÙY TÍNH

Caùc vaán ñeà ñaët ra

à ë

ù

á

• Haïn cheá ñöôïc soá caïnh caàn tìm giao ñieåm öùng vôùi moãi

doøng queùt vì öùng vôùi moãi doøng queùt, khoâng phaûi luùc

naøo taát caû caùc caïnh cuûa ña giaùc cuõng tham gia caét

doøng queùt.

• Xaùc ñònh nhanh hoaønh ñoä giao ñieåm vì neáu laëp laïi

thao taùc tìm giao ñieåm cuûa caïnh ña giaùc vôùi moãi

doøng queùt baèng caùch giaûi heä phöông trình seõ toán raát

nhieàu thôøi gian.

• Giaûi quyeát tröôøng hôïp soá giao ñieåm öùng vôùi tröôøng

hôïp doøng queùt ñi ngang qua ñænh : Neáu soá giao ñieåm

tìm ñöôïc giöõa caùc caïnh ña giaùc vaø doøng queùt laø leû thì

vieäc nhoùm töøng caëp giao ñieåm keá tieáp nhau ñeå hình

thaønh caùc ñoaïn toâ coù theå seõ khoâng chính xaùc. Ñieàu

naøy chæ xaûy ra khi doøng queùt ñi ngang qua caùc ñænh

cuûa ña giaùc.

• Ngoaøi ra, vieäc tìm giao ñieåm cuûa doøng queùt vôùi caùc

caïnh naèm ngang laø moät tröôøng hôïp ñaëc bieät caàn

phaûi coù caùch xöû lí thích hôïp

y=k₂

0

1,2

3

y=k₁

3

4

0

1,2

Döông Anh Ñöùc, Leâ Ñình Duy

Caùc thuaät toaùn toâ maøu 3/16

ÑOÀ HOÏA MAÙY TÍNH

Toå chöùc caáu truùc döõ lieäu vaø thuaät toaùn

ù á õ ä

å

ù

ø

ä

ù

• Danh saùch caùc caïnh (Edge Table – ET) : chöùa toaøn

boä caùc caïnh cuûa ña giaùc (ñaõ loaïi ñi caùc caïnh naèm

y_Min

ngang) ñöôïc saép theo thöù töï taêng daàn cuûa

.

• Danh saùch caùc caïnh kích hoaït (Active Edge Table –

AET) : chöùa caùc caïnh cuûa ña giaùc coù theå caét öùng vôùi

doøng queùt hieän haønh, caùc caïnh naøy ñöôïc saép theo

thöù töï taêng daàn cuûa hoaønh ñoä giao ñieåm giöõa caïnh

vaø doøng queùt.

• Khi doøng queùt ñi töø bottom ñeán top, caùc caïnh thoûa

ñieàu kieän seõ ñöôïc di chuyeån töø ET sang AET:

y = k

♦ Khi doøng queùt

baét ñaàu caét moät caïnh, nghóa laø

k ≥ y

_Min, caïnh naøy seõ ñöôïc chuyeån töø ET sang AET.

♦ Khi doøng queùt khoâng coøn caét caïnh naøy nöõa, nghóa laø

k > y

_Max, caïnh naøy seõ bò loaïi ra khoûi AET.

♦ Khi khoâng coøn caïnh naøo trong ET hay AET nöõa, quaù

trình toâ maøu keát thuùc.

• Ñeå tìm giao ñieåm giöõa caïnh ña giaùc vaø doøng queùt

hieän haønh nhanh, ta coù nhaän xeùt :

1

m

1

m

1

x_k+1− x_k=

((k + 1

)

− k

)

=

x_k+1= x_k+

hay

m ^.

y=k+1

y=k

x_k+1

x_k

Döông Anh Ñöùc, Leâ Ñình Duy

Caùc thuaät toaùn toâ maøu 4/16

ÑOÀ HOÏA MAÙY TÍNH

Ñeà xuaát caáu truùc döõ lieäu cuûa moät caïnh (EDGE)

à

á á

ù

õ ä û

ä ï

deltaY

y=k

xIntersect

yMin

y

•

_Min: giaù trò tung ñoä nhoû nhaát trong 2 ñænh cuûa

caïnh.

xIntersect

: hoaønh ñoä giao ñieåm cuûa caïnh vôùi doøng

queùt hieän haønh.

DxPerScan

•

: giaù trò 1/m (m laø heä soá goùc cuûa caïnh).

deltaY

: khoaûng caùch töø doøng queùt hieän haønh tôùi ñænh

y

k > y_Max

_Max. Luùc naøy ñieàu kieän

trôû thaønh

deltaY ≤ 0

.

xIntersect

• Giaù trò

ñöôïc khôûi gaùn ban ñaàu laø hoaønh ñoä

y

deltaY

cuûa ñænh coù tung ñoä laø _Min, vaø giaù trò

ñöôïc

y − y +1

khôûi gaùn ban ñaàu laø

.

Max

Min

Döông Anh Ñöùc, Leâ Ñình Duy

Caùc thuaät toaùn toâ maøu 5/16

ÑOÀ HOÏA MAÙY TÍNH

Giaûi quyeát tröôøng hôïp doøng queùt ñi qua ñænh

û

á

ø

ï

ø

ù

• Tính moät giao ñieåm neáu chieàu cuûa hai caïnh keà cuûa

ñænh ñoù coù xu höôùng taêng hay giaûm.

• Tính hai giao ñieåm neáu chieàu cuûa hai caïnh keà cuûa

ñænh ñoù coù xu höôùng thay ñoåi, nghóa laø taêng-giaûm

hay giaûm-taêng.

P_i+1

P_i-1

P_i

P_i-1

P_i

P_i+1

P_i

P_i+1

P_i-1

P_i+1

P_i-1

P_i

(a)

(b)

• Khi caøi ñaët ñeå khoûi phaûi xeùt ñieàu kieän naøy cho phöùc

taïp, khi xaây döïng döõ lieäu cho moãi caïnh tröôùc khi ñöa

vaøo ET, ngöôøi ta seõ xöû lí caùc caïnh coù ñænh tính hai

giao ñieåm baèng caùch loaïi ñi moät pixel treân cuøng cuûa

moät trong hai caïnh.

P_i+1

P_i-1

y=k

y=k-1

P_i

y=k-1

P_i

P_i^*

P_i-1

P_i+1

Döông Anh Ñöùc, Leâ Ñình Duy

Caùc thuaät toaùn toâ maøu 6/16

ÑOÀ HOÏA MAÙY TÍNH

Minh hoïa thuaät toaùn

ï

ä

ù

Top

F

C

D

E

y_G*=y_G+1

y_G

G

y_B

B

y_B*=y_B-1

y_H*=y_H+1

I

H

y_H

Bottom

A

• Ban ñaàu :

♦ ET : AB*, AI, H*G, BC, G*F, DC, EF. (loaïi IH vaø DE)

♦ AET : NULL.

• Khi doøng queùt ñaït y=y_A

♦ ET : H*G, BC, G*F, DC, EF. (chuyeån AB*, AI sang AET)

♦ AET : AB*, AI.

• Khi doøng queùt ñaït y=y_H*

♦ ET : BC, G*F, DC, EF. (chuyeån H*G sang AET)

♦ AET : AB*, H*G. (loaïi AI vì khoâng coøn caét doøng queùt)

Döông Anh Ñöùc, Leâ Ñình Duy

Caùc thuaät toaùn toâ maøu 7/16

ÑOÀ HOÏA MAÙY TÍNH

• Khi doøng queùt ñaït y=y_B

♦ ET : G*F, DC, EF. (chuyeån BC sang AET)

♦ AET : BC, H*G. (loaïi AB*, saép xeáp laïi H*G vaø BC)

• Khi doøng queùt ñaït y=y_G*

♦ ET : DC, EF. (chuyeån G*F sang AET)

♦ AET : BC, G*F. (loaïi H*G vì khoâng coøn caét doøng queùt)

• Khi doøng queùt ñaït y=y_D

♦ ET : NULL. (chuyeån DC, EF sang AET)

♦ AET : BC, DC, EF, G*F. (saép xeáp laïi BC, GF*, DC, EF)

• Khi doøng queùt ñaït y=y_C+1

♦ ET : NULL.

♦ AET : EF, G*F. (loaïi BC, DC vì khoâng coøn caét doøng queùt)

• Khi doøng queùt ñaït y=y_F+1

♦ ET : NULL.

♦ AET : NULL. (loaïi EF, G*F vì khoâng coøn caét doøng queùt).

• Thuaät toaùn döøng taïi ñaây.

Döông Anh Ñöùc, Leâ Ñình Duy

Caùc thuaät toaùn toâ maøu 8/16

ÑOÀ HOÏA MAÙY TÍNH

Löu ñoà thuaät toaùn toâ maøu theo doøng queùt

Begin

Taïo danh saùch taát caû caùc caïnh ET

i=BottomScan

i<TopScan

Yes

No

Caäp nhaät danh saùch caùc caïnh

kích hoaït AET

Tìm hoaønh ñoä giao ñieåm vaø saép xeáp

theo thöù töï taêng daàn

Toâ maøu caùc ñoaïn giao ñöôïc taïo bôûi

töøng caëp hoaønh ñoä keá tieáp nhau

Caäp nhaät laïi thoâng tin cuûa caùc caïnh

ñeå söû duïng cho doøng queùt keá tieáp

i=i+1

End

Döông Anh Ñöùc, Leâ Ñình Duy

Caùc thuaät toaùn toâ maøu 9/16

ÑOÀ HOÏA MAÙY TÍNH

Moät soá höôùng daãn caøi ñaët

ä á ø ë

ù

ã

#define MAXVERTEX 20

#define MAXEDGE

#define TRUE

#define FALSE

20

1

0

typedef struct {

int x;

int y;

}POINT;

typedef struct{

int

POINT aVertex[MAXVERTEX];

}POLYGON;

NumVertex;

typedef struct {

int

float

NumPt;

xPt[MAXEDGE];

}XINTERSECT;

typedef struct

{

int

float

yMin; // Gia tri y nho nhat cua 2 dinh

xIntersect; // Hoanh do giao diem cua canh & dong quet

float

dxPerScan; // Gia tri 1/m

DeltaY;

int

}EDGE;

typedef struct

{

int NumEdge;

EDGE aEdge[MAXEDGE];

}EDGELIST;

Döông Anh Ñöùc, Leâ Ñình Duy

Caùc thuaät toaùn toâ maøu 10/16

ÑOÀ HOÏA MAÙY TÍNH

void PutEdgeInList(EDGELIST &EdgeList, POINT p1, POINT p2, int NextY)

{

EDGE EdgeTmp;

EdgeTmp.dxPerScan = float(p2.x-p1.x)/(p2.y-p1.y); // 1/m

if(p1.y < p2.y)

{

/*

Truong hop dong quet di ngang qua dinh la giao diem

cua 2 canh co huong y cung tang

*/

if(p2.y < NextY)

{

p2.y--;

p2.x -= EdgeTmp.dxPerScan;

}

EdgeTmp.yMin = p1.y;

EdgeTmp.xIntersect= p1.x;

EdgeTmp.DeltaY = abs(p2.y-p1.y)+1;

} // if

else

{

/*

Truong hop dong quet di ngang qua dinh la giao diem cua 2 canh co

huong y cung giam

*/

if(p2.y > NextY)

{

p2.y++;

p2.x+= EdgeTmp.dxPerScan;

}

EdgeTmp.yMin = p2.y;

EdgeTmp.xIntersect= p2.x;

EdgeTmp.DeltaY = abs(p2.y-p1.y)+1;

}//else

// xac dinh vi tri chen

int j = EdgeList.NumEdge;

while((j>0) && (EdgeList.aEdge[j-1].yMin>EdgeTmp.yMin))

{

EdgeList.aEdge[j] = EdgeList.aEdge[j-1];

j--;

}

// tien hanh chen dinh moi vao canh

EdgeList.NumEdge++;

EdgeList.aEdge[j] = EdgeTmp;

} // PutEdgeInList

Döông Anh Ñöùc, Leâ Ñình Duy

Caùc thuaät toaùn toâ maøu 11/16

ÑOÀ HOÏA MAÙY TÍNH

/*

*/

Tim dinh ke tiep sao cho khong nam tren cung duong thang voi dinh dang

xet

int FindNextY(POLYGON P, int id)

{

int j = (id+1)%P.NumVertex;

while((j<P.NumVertex)&&(P.aVertex[id].y == P.aVertex[j].y))

j++;

if(j<P.NumVertex)

return (P.aVertex[j].y);

return 0;

} // FindNextY

// Tao danh sach cac canh tu polygon da cho

void MakeSortedEdge(POLYGON P, EDGELIST &EdgeList,

int &TopScan, int &BottomScan)

{

TopScan = BottomScan = P.aVertex[0].y;

EdgeList.NumEdge = 0;

for(int i=0; i<P.NumVertex; i++)

{

// Truong hop canh khong phai la canh nam ngang

if(P.aVertex[i].y != P.aVertex[i+1].y)

PutEdgeInList(EdgeList, P.aVertex[i], P.aVertex[i+1], FindNextY(P,

i+1));

// Xu li truong hop canh nam ngang

else

if(P.aVertex[i+1].y > TopScan)

TopScan = P.aVertex[i+1].y;

}

BottomScan = EdgeList.aEdge[0].yMin;

} //MakeSortedEdge

// Cap nhat lai hai con tro FirstId, LastId cho biet danhsach cac canh active

void UpdateActiveEdgeList(EDGELIST EdgeList, int yScan, int &FirstId, int

&LastId)

{

while((FirstId<EdgeList.NumEdge-1) &&(EdgeList.aEdge[FirstId].DeltaY ==

0))

FirstId++;

while((LastId<EdgeList.NumEdge-1)

&&(EdgeList.aEdge[LastId+1].yMin<=yScan))

LastId++;

} // UpdateActiveEdgeList

Döông Anh Ñöùc, Leâ Ñình Duy

Caùc thuaät toaùn toâ maøu 12/16

ÑOÀ HOÏA MAÙY TÍNH

Thuaät toaùn toâ maøu theo

ä ù â ø

ñöôøng bieân

ø â

• Baøi toaùn ñaët ra : Caàn toâ maøu vuøng toâ neáu bieát ñöôïc

maøu cuûa ñöôøng bieân vuøng toâ vaø moät ñieåm naèm beân

trong vuøng toâ.

• Yù töôûng : Baét ñaàu töø ñieåm naèm beân trong vuøng toâ,

kieåm tra caùc ñieåm laân caän cuûa noù ñaõ ñöôïc toâ hay coù

phaûi laø ñieåm coù maøu truøng maøu bieân hay khoâng, neáu

khoâng phaûi thì ta seõ toâ ñieåm ñoù. Quaù trình naøy ñöôïc

laëp laïi cho tôùi khi khoâng coøn toâ ñöôïc nöõa thì döøng.

Döông Anh Ñöùc, Leâ Ñình Duy

Caùc thuaät toaùn toâ maøu 13/16

ÑOÀ HOÏA MAÙY TÍNH

• Coù hai quan ñieåm veà caùch toâ naøy, ñoù laø duøng 4 ñieåm

laân caän (hình a) hay 8 ñieåm laân caän (hình b).

(a)

(b)

• Caøi ñaët minh hoïa thuaät toaùn toâ maøu theo ñöôøng bieân

void BoundaryFill(int x, int y, int FillColor, int BoundaryColor)

{

int CurrenColor;

CurrentColor = getpixel(x,y);

if((CurrentColor!=BoundaryColor)&&CurrentColor!= FillColor))

{

putpixel(x,y,FillColor);

BoundaryFill(x-1, y, FillColor, BoundaryColor);

BoundaryFill(x, y+1, FillColor, BoundaryColor);

BoundaryFill(x+1, y, FillColor, BoundaryColor);

BoundaryFill(x, y-1, FillColor, BoundaryColor);

}

} // Boundary Fill

• Moät soá nhaän xeùt

♦ Thuaät toaùn coù theå hoaït ñoäng khoâng chính xaùc khi coù moät

soá ñieåm naèm trong vuøng toâ coù maøu laø maøu caàn toâ cuûa

vuøng.

♦ Vieäc thöïc hieän ñeä qui laøm thuaät toaùn khoâng theå duøng cho

vuøng toâ lôùn.

Döông Anh Ñöùc, Leâ Ñình Duy

Caùc thuaät toaùn toâ maøu 14/16

ÑOÀ HOÏA MAÙY TÍNH

• Moät caûi tieán nhoû : nhaän xeùt raèng vieäc goïi thöïc hieän

ñeä qui thuaät toaùn cho 4 ñieåm laân caän cuûa ñieåm hieän

haønh khoâng quan taâm tôùi moät trong 4 ñieåm ñoù ñaõ

ñöôïc xeùt ôû böôùc tröôùc hay chöa. Ví duï khi ta xeùt 4

ñieåm laân caän cuûa (x, y), thì khi goïi thöïc hieän ñeä qui

vôùi ñieåm hieän haønh laø moät trong 4 ñieåm treân, (x, y)

vaãn ñöôïc xem laø ñieåm laân caän cuûa chuùng vaø ñöôïc goïi

thöïc hieän laïi.

void BoundaryFillEnhanced(int x, int y, int F_Color, int B_Color)

{

int CurrenColor;

CurrentColor = getpixel(x,y);

if((CurrentColor!=B_Color)&&CurrentColor!= F_Color))

{

putpixel(x,y,F_Color);

FillLeft(x-1, y, F_Color, B_Color);

FillTop(x, y+1, F_Color, B_Color);

FillRight(x+1, y, F_Color, B_Color);

FillBottom(x, y-1, F_Color, B_Color);

}

} // BoundaryFillEnhanced

void FillLeft(int x, int y, int F_Color, int B_Color)

{

int CurrenColor;

CurrentColor = getpixel(x,y);

if((CurrentColor!=B_Color)&&CurrentColor!= F_Color))

{

putpixel(x,y,F_Color);

FillLeft(x-1, y, F_Color, B_Color);

FillTop(x, y+1, F_Color, B_Color);

FillBottom(x, y-1, F_Color, B_Color);

}

} // FillLeft

Döông Anh Ñöùc, Leâ Ñình Duy

Caùc thuaät toaùn toâ maøu 15/16

ÑOÀ HOÏA MAÙY TÍNH

• Moät caûi tieán khaùc : khoâng caøi ñaët ñeä qui maø toâ theo

töøng doøng.

Döông Anh Ñöùc, Leâ Ñình Duy

Caùc thuaät toaùn toâ maøu 16/16