ĐỒ HỌA MÁY TÍNH
Dương Anh Đức, Lê Đình Duy Các thuật toán tô màu 1/16
C
CC
C
C
CC
C
a
aa
a
a
aa
a
ù
ùù
ù
ù
ùù
ù
c
cc
c
c
cc
c
ä
t
tt
t
t
tt
t
t
tt
t
t
tt
t
o
oo
o
o
oo
o
a
aa
a
a
aa

o
â
ââ
â
â
ââ
â
m
mm
m
m
mm
m
a
aa
a
a
aa
a
ø
øø
ø
ø
øø

• Có hai dạng vùng tô thường gặp : tô bằng một màu
thuần nhất (solid fill) và tô theo một mẫu tô (fill-
pattern) nào đó.
• Việc tô màu thường được chia làm hai công đoạn :
♦ Xác đònh vò trí các điểm cần tô màu.
♦ Quyết đònh tô các điểm trên bằng màu nào. Công đoạn
này thực sự phức tạp khi ta cần tô theo một mẫu tô nào
đó chứ không phải tô thuần một màu.
• Có hai cách tiếp cận chính : tô màu theo dòng quét
và tô màu dựa theo đường biên.
♦ Phương pháp tô màu dựa theo dòng quét sẽ xác đònh
phần giao của các dòng quét kế tiếp nhau với đường biên
của vùng tô, sau đó sẽ tiến hành tô màu các điểm thuộc
phần giao này. Cách này thường được dùng để tô màu đa
giác, đường tròn, ellipse và một số đường cong đơn giản
khác.
♦ Phương pháp tô màu dựa theo đường biên sẽ bắt đầu từ
một điểm bên trong vùng tô và từ đó loang dần ra cho
đến khi gặp điểm biên. Cách này thường được dùng cho
các dạng đường biên phức tạp.
ĐỒ HỌA MÁY TÍNH
Dương Anh Đức, Lê Đình Duy Các thuật toán tô màu 2/16
T
TT
T
T
TT
T
h
hht
tt
t
t
tt
t
o
oo
o
o
oo
o
a
aa
a
a
aa
a
ù
ùù
ù
ù
ùù
ù
n
nnt
tt
t
t
tt
t
h
hh
h
h
hh
h
e
ee
e
e
ee
e
o
oo
o
o
oo
o
g
g
gg
g
q
qq
q
q
qq
q
u
uu
u
u
uu
u
e
ee
e
e
ee
e
ù
ùù

t
t
a
a
é
é
t
tc
c
a
a
ù
ù
c
cb
b
ư
ư
ơ
ơ
ù
ù
c
c

a
a
ä
ä
t
tt
t
o
o
a
a
ù
ù
n
n
• Tìm
top
y
,
bottom
y
lần lượt là giá trò lớn nhất, nhỏ
nhất của tập các tung độ của các đỉnh của đa giác đã
cho:
(){}
Pyxyy
iiitop

y
=
lần lượt
được giới hạn bởi các cặp
()()( )
1222110
,, ,,,,
+kk
x
x
x
x
x
x
.
O
y
0123
x
y
bottom
y
top
ĐỒ HỌA MÁY TÍNH
Dương Anh Đức, Lê Đình Duy Các thuật toán tô màu 3/16
C
C
a
a
ù

tr
r
a
a
• Hạn chế được số cạnh cần tìm giao điểm ứng với mỗi
dòng quét vì ứng với mỗi dòng quét, không phải lúc
nào tất cả các cạnh của đa giác cũng tham gia cắt
dòng quét.
• Xác đònh nhanh hoành độ giao điểm vì nếu lặp lại
thao tác tìm giao điểm của cạnh đa giác với mỗi
dòng quét bằng cách giải hệ phương trình sẽ tốn rất
nhiều thời gian.
• Giải quyết trường hợp số giao điểm ứng với trường
hợp dòng quét đi ngang qua đỉnh : Nếu số giao điểm
tìm được giữa các cạnh đa giác và dòng quét là lẻ thì
việc nhóm từng cặp giao điểm kế tiếp nhau để hình
thành các đoạn tô có thể sẽ không chính xác. Điều
này chỉ xảy ra khi dòng quét đi ngang qua các đỉnh
của đa giác.
• Ngoài ra, việc tìm giao điểm của dòng quét với các
cạnh nằm ngang là một trường hợp đặc biệt cần
phải có cách xử lí thích hợp
y=k
1
y=k
2
0 1,2

á
u
ut
t
r
r
u
u
ù
ù
c
cd
d
ư
ư
õ
õl
l
i
i
e

t
o
o
a
a
ù
ù
n
n
• Danh sách các cạnh (Edge Table – ET) : chứa toàn
bộ các cạnh của đa giác (đã loại đi các cạnh nằm
ngang) được sắp theo thứ tự tăng dần của
Min
y
.
• Danh sách các cạnh kích hoạt (Active Edge Table –
AET) : chứa các cạnh của đa giác có thể cắt ứng với
dòng quét hiện hành, các cạnh này được sắp theo
thứ tự tăng dần của hoành độ giao điểm giữa cạnh
và dòng quét.
• Khi dòng quét đi từ bottom đến top, các cạnh thỏa
điều kiện sẽ được di chuyển từ ET sang AET:
♦ Khi dòng quét
k
y
=
bắt đầu cắt một cạnh, nghóa là
Min
yk ≥
, cạnh này sẽ được chuyển từ ET sang AET.

y=k
x
k
x
k+1
ĐỒ HỌA MÁY TÍNH
Dương Anh Đức, Lê Đình Duy Các thuật toán tô màu 5/16
Đ
Đ
e
e
à
àx
x
u
u
a
a
á
á
t
tc
c
a

i
e
e
ä
ä
u
uc
c
u
u
û
û
a
am
m
o
o
ä
ä
t
tc

: hoành độ giao điểm của cạnh với dòng
quét hiện hành.
•
DxPerScan
: giá trò 1/m (m là hệ số góc của cạnh).
•
deltaY
: khoảng cách từ dòng quét hiện hành tới đỉnh
Max
y
. Lúc này điều kiện
Max
yk >
trở thành
0≤deltaY
.
• Giá trò
txIntersec
được khởi gán ban đầu là hoành độ
của đỉnh có tung độ là
Min
y
, và giá trò
deltaY
được
khởi gán ban đầu là
1+−
MinMax
yy
.
t
t
r
r
ư
ư
ơ
ơ
ø
ø
n
n
g
gh
h
ơ
ơ
ï
ï
p
pd
d

u
u
a
ađ
đ
ỉ
ỉ
n
n
h
h
• Tính một giao điểm nếu chiều của hai cạnh kề của
đỉnh đó có xu hướng tăng hay giảm.
• Tính hai giao điểm nếu chiều của hai cạnh kề của
đỉnh đó có xu hướng thay đổi, nghóa là tăng-giảm
hay giảm-tăng.
• Khi cài đặt để khỏi phải xét điều kiện này cho phức
tạp, khi xây dựng dữ liệu cho mỗi cạnh trước khi đưa
vào ET, người ta sẽ xử lí các cạnh có đỉnh tính hai
giao điểm bằng cách loại đi một pixel trên cùng của
một trong hai cạnh.
(a) (b)
P
i
P
i-1
P

P
i+1
P
i
P
i-1
y=k-1
P
i-1
P
i
*
P
i
*
P
i-1
P
i+1
ĐỒ HỌA MÁY TÍNH
Dương Anh Đức, Lê Đình Duy Các thuật toán tô màu 7/16
M
M
i
i
n
n
h
h


a
ù
ù
n
n
• Ban đầu :
♦ ET : AB*, AI, H*G, BC, G*F, DC, EF. (loại IH và DE)
♦ AET : NULL.
• Khi dòng quét đạt y=y
A
♦ ET : H*G, BC, G*F, DC, EF. (chuyển AB*, AI sang AET)
♦ AET : AB*, AI.
• Khi dòng quét đạt y=y
H*
♦ ET : BC, G*F, DC, EF. (chuyển H*G sang AET)
♦ AET : AB*, H*G. (loại AI vì không còn cắt dòng quét)
Top
F
ED
C
B
G
HI
A
Bottom
y
B
y
G*
=y

• Khi dòng quét đạt y=y
C
+1
♦ ET : NULL.
♦ AET : EF, G*F. (loại BC, DC vì không còn cắt dòng quét)
• Khi dòng quét đạt y=y
F
+1
♦ ET : NULL.
♦ AET : NULL. (loại EF, G*F vì không còn cắt dòng quét).
• Thuật toán dừng tại đây.
ĐỒ HỌA MÁY TÍNH
Dương Anh Đức, Lê Đình Duy Các thuật toán tô màu 9/16
Lưu đồ thuật toán tô màu theo dòng quét
Begin
Tạo danh sách tất cả các cạnh ET
i<TopScan
i=BottomScan
Yes
No
Cập nhật danh sách các cạnh
kích hoạt AET
Tìm hoành độ giao điểm và sắp xếp
theo thứ tự tăng dần
Tô màu các đoạn giao được tạo bởi
từng cặp hoành độ kế tiếp nhau
Cập nhật lại thông tin của các cạnh
để sử dụng cho dòng quét kế tiếp
i=i+1
End

g
gd
d
a
a
ã
ã
n
nc
c
a
a
ø
ø
i
iđ
đ
a
a
ë
ë

ĐỒ HỌA MÁY TÍNH
Dương Anh Đức, Lê Đình Duy Các thuật toán tô màu 11/16
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++;

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))

ä
ä
ää
ä
t
tt
t
t
tt
t
t
tt
t
t
tt
t
o
oo
o
o
oo
o
a
aa

o
o
oo
o
â
ââ
â
â
ââ
â
m
mm
m
m
mm
m
a
aa
a
a
aa
a
ø
øø

e
e
ee
e
o
oo
o
o
oo
o
đ
đđ
đ
đ
đđ
đ
ư
ưư
ư
ư
ưư
ư
ơ
ơơ
ơ
ơ
ơơ
ơ
ø
øø

i
i
ii
i
e
ee
e
e
ee
e
â
ââ
â
â
ââ
â
n
nn
n
n
nn
n
• Bài toán đặt ra : Cần tô màu vùng tô nếu biết được
màu của đường biên vùng tô và một điểm nằm bên
trong vùng tô.
• tưởng : Bắt đầu từ điểm nằm bên trong vùng tô,
kiểm tra các điểm lân cận của nó đã được tô hay có
phải là điểm có màu trùng màu biên hay không, nếu
không phải thì ta sẽ tô điểm đó. Quá trình này được
lặp lại cho tới khi không còn tô được nữa thì dừng.

được xét ở bước trước hay chưa. Ví dụ khi ta xét 4
điểm lân cận của (x, y), thì khi gọi thực hiện đệ qui
với điểm hiện hành là một trong 4 điểm trên, (x, y)
vẫn được xem là điểm lân cận của chúng và được gọi
thực hiện lạ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