Area Filling Area Filling Tô màu Tô màu
11
Vùng tô Vùng tô
pixel-defined region pixel-defined region
ượ ượ
ở ể ả ở ể ả
Vùng đ Vùng đ Vùng xác đ nh b i đa giác – Vùng xác đ nh b i đa giác –
polygonal region polygonal region
c xác đ nh b i đi m nh – c xác đ nh b i đi m nh – ị ị
ị ị ở ở
pixel-defined pixel-defined region region
polygonal polygonal region region
22
Pixel-defined region Pixel-defined region
Vùng đ Vùng đ
c đ nh nghĩa b i màu c a pixel, chia làm 3 ph n: ủ c đ nh nghĩa b i màu c a pixel, chia làm 3 ph n: ủ
ở ở
ầ ầ
boundary boundary
ượ ị ượ ị Vùng trong – interior interior Vùng trong – exterior Vùng ngoài – exterior Vùng ngoài – Biên (liên t c) - ụ Biên (liên t c) - ụ
exterior
interior
boundary
33
Liên thông 4 và liên thông 8 Liên thông 4 và liên thông 8
4-connected : 2 pixel liên thông v i nhau n u chúng k nhau theo ớ 4-connected : 2 pixel liên thông v i nhau n u chúng k nhau theo ớ
ề ề
ế ế
chi u ngang hay chi u d c ề ọ chi u ngang hay chi u d c ề ọ
ề ề
8-connected : 2 pixel liên thông v i nhau n u chúng k nhau theo ớ 8-connected : 2 pixel liên thông v i nhau n u chúng k nhau theo ớ
ề ề
chi u ngang, hay chi u d c, hay đ chi u ngang, hay chi u d c, hay đ
ế ế ng chéo ng chéo
ề ọ ề ọ
ề ề
ườ ườ
44
pixel-defined region pixel-defined region
Cách th c đ nh nghĩa ứ ị Cách th c đ nh nghĩa ứ ị
inside-color inside-color
Interior defined Interior defined ấ ả ấ ả
ộ ộ ọ ọ
ỗ ỗ
boundary-color boundary-color T t c các pixel trong vùng có cùng m t màu, g i là T t c các pixel trong vùng có cùng m t màu, g i là Các pixel trên biên không có màu này Các pixel trên biên không có màu này trong vùng Có th có l ể Có th có l trong vùng ể Boundary defined Boundary defined ộ ộ
Các pixel thu c biên có cùng màu – Các pixel thu c biên có cùng màu – Các pixel trong vùng không có màu này Các pixel trong vùng không có màu này N u m t s pixel trong vùng có màu boundary-color thì vùng s ch a N u m t s pixel trong vùng có màu boundary-color thì vùng s ch a ẽ ứ ẽ ứ ộ ố ộ ố
ế ế lỗlỗ
inside color
Interior-defined
Boundary-defined
55
Polygonal Region Polygonal Region
Đ nh nghĩa b ng đa giác: xác đ nh các đ nh các đ nh p Đ nh nghĩa b ng đa giác: xác đ nh các đ nh các đ nh p
ằ ằ
ị ị
ị ị
ỉ ỉ
ị ị
= (xii,y,yii)) ii = (x
Các lo i đa giác: ạ Các lo i đa giác: ạ Convex Convex Concave, simple Concave, simple Nonsimple Nonsimple
concave concave
nonsimple nonsimple
convex convex
polygonal polygonal region region
66
Recursive Flood-Fill Algorithm Recursive Flood-Fill Algorithm interior-defined, 4-connected region)) ((interior-defined, 4-connected region
ổ ổ
ủ ấ ả ủ ấ ả
Đ i màu c a t Đ i màu c a t Quá trình tô màu b t đ u t Quá trình tô màu b t đ u t
ắ ầ ừ ộ ắ ầ ừ ộ
ể ể
fill color.. fill color ) thu c phía seed pixel) thu c phía ộ seed pixel ộ trong vùng tô và lan truy n kh p vùng tô => Flood-Fill trong vùng tô và lan truy n kh p vùng tô => Flood-Fill
t c các interior-pixel thành màu tô – t c các interior-pixel thành màu tô – m t đi m ( m t đi m ( ắ ắ
ề ề
seed pixel
inside color fill color
Recursive Flood-Fill
Interior-defined
77
Recursive Flood-Fill Algorithm (cont) Recursive Flood-Fill Algorithm (cont)
i (x,y) thu c vùng trong – màu c a pixel đó là i (x,y) thu c vùng trong – màu c a pixel đó là inside-color inside-color ạ ạ ủ ủ ộ ộ
ậThu t toán ậ Thu t toán N u pixel t ế N u pixel t ế thìthì
fill-color fill-color
ổ ổ
Đ i màu c a nó thành ủ Đ i màu c a nó thành ủ Áp d ng quá trình trên cho 4 đi m lân c n nó (4-connected). Áp d ng quá trình trên cho 4 đi m lân c n nó (4-connected).
ể ể
ậ ậ
Ng Ng
ụ ụ i, không làm gì. c l ượ ạ c l i, không làm gì. ượ ạ
(4,2)
(3,2)
(2,2) (4,2)
(1,2) (3,2)
(3,3)
(2,3) (2,1)
SS
6 5 4 3 2 1 0
0 1 2
43
5 6
88
Recursive Flood-Fill Program Recursive Flood-Fill Program
void FloodFill(int x, int y, int inside_color, int void FloodFill(int x, int y, int inside_color, int
fill_color) fill_color)
{{ if (getpixel(x,y) == inside_color) if (getpixel(x,y) == inside_color) {{
putpixel(x,y,fill_color); putpixel(x,y,fill_color); FloodFill(x-1,y, inside_color, fill_color); FloodFill(x-1,y, inside_color, fill_color); FloodFill(x+1,y, inside_color, fill_color); FloodFill(x+1,y, inside_color, fill_color); FloodFill(x,y+1, inside_color, fill_color); FloodFill(x,y+1, inside_color, fill_color); FloodFill(x,y-1, inside_color, fill_color); FloodFill(x,y-1, inside_color, fill_color);
}}
}}
99
Recursive Flood-Fill (cont) Recursive Flood-Fill (cont) boundary-defined, 4-connected region)) ((boundary-defined, 4-connected region
ả ả thu t toán ậ thu t toán ậ
Bài t pậ Bài t pậ Mô t Mô t Cài đ tặ Cài đ tặ
Boundary-defined
1010
C i ti n ả ế C i ti n ả ế
Run - Đ ng ch y ạ ườ Run - Đ ng ch y ạ ườ
ế ế ằ ằ
c c trái (hay ph i) c a run c c trái (hay ph i) c a run DDãy các pixel liên ti p theo hàng ngang n m trong vùng tô ãy các pixel liên ti p theo hàng ngang n m trong vùng tô M i run đ ả ủ ỗ M i run đ ả ủ ỗ c đ t tên b ng pixel ằ c đ t tên b ng pixel ằ ượ ặ ượ ặ ở ự ở ự
b
a
c
s d e
1111
Thu t toán c i ti n – Dùng stack ả ế Thu t toán c i ti n – Dùng stack ả ế
ậ ậ
Stack:
seed pixel run ch a ứ seed pixel
a
a
s
stack run ch a ứ not empty { stack not empty {
Stack:
Cho vào stack Cho vào while stack while = pop(); begin = pop(); begin Tô run b t đ u t Tô run b t đ u t Cho vào stack Cho vào Cho vào stack Cho vào
begin ắ ầ ừ begin ắ ầ ừ các run stack các run ở ở các run stack các run ở ở
bên trên bên trên i bên d ướ i bên d ướ
b
b
}}
c
d
c
d
Stack:
b
b
c
c
e
e
1212
Polygonal Region – Scanline Algorithm Polygonal Region – Scanline Algorithm
Scanline Scanline ườ ườ ố ố
ằ ằ ủ ủ
Đ ng th ng n m ngang Đ ng th ng n m ngang S giao đi m c a scanline và đa giác là s ch n (t ng quát) S giao đi m c a scanline và đa giác là s ch n (t ng quát) Các pixel n m gi a các c p giao đi m l Các pixel n m gi a các c p giao đi m l
ố ẵ ố ẵ -ch n n m trong đa giác ể ẽ ẵ -ch n n m trong đa giác ể ẽ ẵ
ẳ ẳ ể ể ằ ằ
ổ ổ ằ ằ
ữ ữ
ặ ặ
out in out
1 1
2
out in out in out
1
2
3
4
1313
Thu t toán Scanline t ng quát Thu t toán Scanline t ng quát
ổ ổ
ậ ậ
for each scanline { for each scanline {
ể ể
ạ ạ
ủ ủ tăng d n theo x ầ tăng d n theo x ầ
ớ ớ ứ ự ứ ự
ắ ế ắ ế
Tìm giao đi m c a scanline v i các c nh c a đa giác ủ Tìm giao đi m c a scanline v i các c nh c a đa giác ủ S p x p các giao đi m theo th t S p x p các giao đi m theo th t Tô các pixel n m gi a các c p giao đi m liên ti p nhau ặ Tô các pixel n m gi a các c p giao đi m liên ti p nhau ặ
ể ể ữ ữ
ế ế
ể ể
ằ ằ
}}
ạ
:: ạT i dòng scanline y = 3 T i dòng scanline y = 3 ể ể
ộ ộ
Các hoành đ giao đi m sau Các hoành đ giao đi m sau khi làm tròn là 1, 2, 7, 9 khi làm tròn là 1, 2, 7, 9 Do đó, 2 run [1,2] và [7,9] Do đó, 2 run [1,2] và [7,9]
c tô c tô
ượđ ượ đ
9 8 7 6 5 4 3 2 1 0
1414
0 1 2
43
5 6 7 8 9
DemoDemo
1515
Các tr Các tr
ườ ườ
ng h p đ c bi ợ ặ ng h p đ c bi ợ ặ
t ệ t ệ
c tô khi xét 2 c nh c tô khi xét 2 c nh ằ ằ ẽ ượ ẽ ượ ế ế ạ ạ
ủ ủ ẽ ẽ ạ ạ ỉ ỉ
ng h p đ nh không là c c tr , s giao đi m c a scanline v i đa giác ng h p đ nh không là c c tr , s giao đi m c a scanline v i đa giác ợ ỉ ợ ỉ ớ ớ ủ ủ ị ố ị ố ự ự ớ ớ ể ể
• Các c nh n m ngang không xét đ n vì chúng s đ Các c nh n m ngang không xét đ n vì chúng s đ ạ ạ k v i nó ề ớ k v i nó ề ớ • Khi scanline đi qua đ nh c a đa giác, nó s giao v i 2 c nh. Trong Khi scanline đi qua đ nh c a đa giác, nó s giao v i 2 c nh. Trong tr ườ tr ườ là là s lố ẽs lố ẽ..
2 giao đi mể out in in in
2 giao đi m => ể sai
1616
Các tr Các tr
t (cont) t (cont)
ườ ườ
ng h p đ c bi ợ ặ ng h p đ c bi ợ ặ
ệ ệ
y-extrema vertices: vertices: y-extrema minimum minimum maximum maximum
y-monotonic: y-monotonic:
ạ ạ
minimum v i 1 c nh ớ minimum v i 1 c nh ớ maximum v i c nh còn l ớ ạ maximum v i c nh còn l ớ ạ i ạ i ạ
C nh n m ngang ằ C nh n m ngang ằ
ạ ạ
1717
X líửX líử
Tr Tr ướ ướ ỉ ỉ
c quá trình tô màu, ki m tra các đ nh. c quá trình tô màu, ki m tra các đ nh. N u đ nh không ph i là c c tr , xét c nh phía d ế ỉ N u đ nh không ph i là c c tr , xét c nh phía d ế ỉ
ị ị
i. ướ i. ướ
ả ả Gi m tung đ trên Gi m tung đ trên
ể ể ự ạ ự ạ y_upper xu ng m t đ n v xu ng m t đ n v ộ ơ ị y_upper ộ ơ ị
ộ ộ
ố ố
ả ả
c c ướ ướ
Danh sách đ nh đa giác tr ỉ Danh sách đ nh đa giác tr ỉ ả ế ả ế
khi c i ti n: khi c i ti n: (6,8), (9,5), (9,1), (5,5), (1,2), (6,8), (9,5), (9,1), (5,5), (1,2),
ư ư
ạ ạ
9 8 7 6 5 4 3 2 1 0
(2,7), (4,8) (2,7), (4,8) Sau khi c i ti n, danh sách các ả ế Sau khi c i ti n, danh sách các ả ế c nh c a đa giác nh sau - ủ ạ c nh c a đa giác nh sau - ạ ủ m t c nh b xóa và 2 c nh ị ộ ạ m t c nh b xóa và 2 c nh ị ộ ạ ọ :: c rút g n đ ượ đ c rút g n ượ ọ = (6,8) to (9,5) ee1 1 = (6,8) to (9,5) ee22 = (9,4) to (9,1) = (9,4) to (9,1) = (9,1) to (5,5) ee33 = (9,1) to (5,5) ee44 = (5,5) to 1,2) = (5,5) to 1,2) = (1,2) to (2,6) ee55 = (1,2) to (2,6) = (2,7) to (4,8) ee66 = (2,7) to (4,8)
1818
0 1 2
43
5 6 7 8 9
H n ch c a thu t toán H n ch c a thu t toán
ế ủ ế ủ
ạ ạ
ậ ậ
ị ị
ể ể ườ ườ
ể ể ạ ạ ả ả
ủ ủ
ố ạ ố ạ
ấ ấ ấ ấ
ả ả ể ể
ờ ờ
ng scanline c t thì r t ng scanline c t thì r t
ố ạ ố ạ ắ ắ
ạ ạ ườ ườ
ố
• Đ xác đ nh giao đi m c a Đ xác đ nh giao đi m c a ủ ủ ng scanline và c nh c a đ ủ đ ng scanline và c nh c a ủ đa giác, chúng ta ph i duy t ệ đa giác, chúng ta ph i duy t ệ t c các c nh c a đa giác. t ạ ấ ả t c các c nh c a đa giác. t ạ ấ ả • Khi s c nh c a đa giác khá Khi s c nh c a đa giác khá ủ ủ , chúng ta ph i m t r t l nớl nớ , chúng ta ph i m t r t nhi u th i gian đ duy t h t ệ ế ề nhi u th i gian đ duy t h t ệ ế ề các c nh, trong khi s c nh các c nh, trong khi s c nh mà đ ấ mà đ ấ ít.ít.
S giao đi m là 2, trong khi s c nh là 12
ể ố ạ
1919
C i ti n t c đ thu t toán C i ti n t c đ thu t toán
ả ế ố ộ ả ế ố ộ
ậ ậ
ậ
ậNh n xét: Nh n xét:
ộ ơ ị ộ ơ ị
1
1/m1/m ổ ổ ộ ộ
ứ ứ
ơ ơ
1/m
ủ ủ
y_upper
ể ể s r ng 1 c nh c a đa giác có tung đ ộ s r ng 1 c nh c a đa giác có tung đ ộ thì khi tung [y_lower, y_upper] thì khi tung ộ ộ
ạ ạ
ắ ạ ắ ạ
t t
– Khi dòng quét tăng m t đ n v theo y thì Khi dòng quét tăng m t đ n v theo y thì hoành đ giao đi m thay đ i theo ể hoành đ giao đi m thay đ i theo ể -> Công th c tính giao đi m đ n gi n ả -> Công th c tính giao đi m đ n gi n ả – Gi Gi ạ ả ử ằ ả ử ằ ạ b ch n b i ị ặ ở [y_lower, y_upper] b ch n b i ị ặ ở đ c a dòng quét không thu c đo n này, ộ ủ đ c a dòng quét không thu c đo n này, ộ ủ chúng không c t c nh đó chúng không c t c nh đó ố ượ ố ượ
ế ế
y_lower
ph i tính giao đi m v i t ph i tính giao đi m v i t
ng tính toán, không nh t thi ng tính toán, không nh t thi t c các c nh ớ ấ ả t c các c nh ớ ấ ả
ấ ấ ạ ạ
ể ể
-> Gi m s l ả -> Gi m s l ả ả ả
2020
Active Edge List (AEL) Active Edge List (AEL)
ể ể
Đ gia tăng t c đ tính toán, chúng ta xây d ng và duy trì m t Đ gia tăng t c đ tính toán, chúng ta xây d ng và duy trì m t ủ ủ danh sách ộ danh sách ộ c m i b ng scanline ở ỗ ướ ng scanline c m i b ở ỗ ướ ố ộ ố ộ ọ ộ ọ ộ ườ ườ ể ể
ự ự xác đ nh t a đ giao đi m c a đa giác và đ ị xác đ nh t a đ giao đi m c a đa giác và đ ị ((AELAEL))..
Danh sách này cho phép tính toán giao đi m m t cách nhanh chóng b ng Danh sách này cho phép tính toán giao đi m m t cách nhanh chóng b ng ộ ộ ằ ằ
ng scanline c t. ng scanline c t. cách l u các thông tin các c nh mà đ cách l u các thông tin các c nh mà đ ể ể ườ ườ ắ ắ
ể ể
ạ ạ ộ ạ ộ ạ ấ y_upper ấ
c c
ướ ướ
ư ư Đ thu n l i tính toán, m t c nh có các thông tin sau: ậ ợ Đ thu n l i tính toán, m t c nh có các thông tin sau: ậ ợ – Tung đ cao nh t c a c nh (sau khi rút g n). Tung đ cao nh t y_upper c a c nh (sau khi rút g n). ọ ộ ủ ạ ọ ộ ủ ạ – Hoành đ giao đi m v i đ x_intersection v i đ Hoành đ giao đi m ng scanline hi n hành. ớ ườ ể x_intersection ộ ệ ng scanline hi n hành. ớ ườ ể ộ ệ – Ngh ch đ o h s góc 1/m : reciprocal_slope. Chú ý, 1/m đ . Chú ý, 1/m đ Ngh ch đ o h s góc 1/m : ượ ả ệ ố ị reciprocal_slope ị ượ ả ệ ố khi c nh đ ủ ượ ạ khi c nh đ ủ ượ ạ
c tính tr c tính tr c rút g n, do đó b o đ m tính chính xác c a giao đi m. ể c rút g n, do đó b o đ m tính chính xác c a giao đi m. ể
ả ả ả ả
ọ ọ
y_upper y_upper x_int x_int recip_slope recip_slope
2121
ụ ề AELAEL Ví d v Ví d v ụ ề
ee55
ee44
ee33
ee22
9 8 7 6 5 4 3 2 1 0
43
5 6 7 8 9
ạ
0 1 2 :: ạT i dòng scanline y = 3 T i dòng scanline y = 3
AEL
66
6/56/5
1/51/5
55
7/37/3
4/34/3
55
77
-1-1
44
99
00
2222
y_upper x_int 1 / m
S d ng AEL đ tô màu t S d ng AEL đ tô màu t
i m t dòng scanline i m t dòng scanline
ử ụ ử ụ
ể ể
ạ ộ ạ ộ
T i dòng scanline hi n hành T i dòng scanline hi n hành , AEL l u tr giao đi m c a scanline và yy, AEL l u tr giao đi m c a scanline và ệ ệ ạ ạ ư ư ữ ữ ủ ủ ể ể
ạc nh đa giác. ạ c nh đa giác.
Đ tô màu, chúng ta s p x p các c nh theo chi u tăng d n c a hoành đ ộ Đ tô màu, chúng ta s p x p các c nh theo chi u tăng d n c a hoành đ ộ ắ ế ắ ế ầ ủ ầ ủ ề ề ể ể ạ ạ
M i c p giá tr c a x_int xác đ nh m t run, mà chúng ta có th tô màu M i c p giá tr c a x_int xác đ nh m t run, mà chúng ta có th tô màu ộ ộ ể ể ị ị
x_int.. giao đi m ể x_int giao đi m ể ị ủ ỗ ặ ỗ ặ ị ủ ễd dàng ễ d dàng
tmp = AEL; tmp = AEL; while (tmp != NULL) while (tmp != NULL) {{
ee55
ee44
ee33
ee22
9 8 7 6 5 4 3 2 1 0
x1 = tmp.x_int; x1 = tmp.x_int; tmp = tmp->next; tmp = tmp->next; x2 = tmp.x_int; x2 = tmp.x_int; tmp = tmp->next; tmp = tmp->next; for(x = x1; x <= x2; x++) for(x = x1; x <= x2; x++) putpixel(x,y,color); putpixel(x,y,color);
0 1 2
43
5 6 7 8 9
2323
}}
C p nh t AEL khi dòng scanline di chuy n ể C p nh t AEL khi dòng scanline di chuy n ể
ậ ậ
ậ ậ
•
ee11
y+1 y
ee55
” : xóa ” : xóa
t quá t quá
ee44
ee33
ee22
• ộ ộ
9 8 7 6 5 4 3 2 1 0
ể ể
0 1 2
43
5 6 7 8 9
thì x_int
ậ ấ ả ậ ấ ả
T i y : ael = {
ạ
e5, e4, e3, e1}
i dòng scanline Sau khi tô màu t ạ i dòng scanline Sau khi tô màu t ạ c , AEL ph i đ yy, AEL ph i đ ệhi n hành ả ượ ệ c hi n hành ả ượ y+1y+1:: i scanline c p nh t t ậ ạ ậ c p nh t t i scanline ậ ạ ậ và yy và ằ1. B ng cách so sánh ằ 1. B ng cách so sánh y_upper c a các c nh trong c a các c nh trong ạ ủ y_upper ạ ủ dòng AEL, ta xác đ nh “ ị dòng AEL, ta xác đ nh “ ị scanline m i n m phía trên ớ ằ scanline m i n m phía trên ớ ằ ạc nh nào đó trong AEL ạ c nh nào đó trong AEL yy v y_upper.. ượ v ạc nh có ượ ạ c nh có y_upper 2. Giá tr c a hoành đ giao ị ủ 2. Giá tr c a hoành đ giao ị ủ đi m thay đ i theo dòng ổ đi m thay đ i theo dòng ổ scanline. Khi dòng scanline tăng scanline. Khi dòng scanline tăng 1/m1/m : : thay đ i là ổ x_int thay đ i là ổ lên 11 thì lên t c các c nh v i c p nh t t ớ ạ ậ c p nh t t t c các c nh v i ớ ạ ậ x_int = x_int + recip_slope x_int = x_int + recip_slope
T i y+1 : ael = {
ạ
e5, e1}
2424
ậ ậ
ậ ậ
ể ể
C p nh t AEL khi dòng scanline di chuy n C p nh t AEL khi dòng scanline di chuy n (cont) (cont)
•
ee11
y+1 y
ee55
•
ee44
ee33
ee22
9 8 7 6 5 4 3 2 1 0
c s p x p l c s p x p l Sau khi tô màu t i dòng scanline ạ Sau khi tô màu t i dòng scanline ạ ệhi n hành c , AEL ph i đ yy, AEL ph i đ ệ ả ượ hi n hành c ả ượ c p nh t t y+1y+1:: i scanline ậ ạ ậ c p nh t t i scanline ậ ạ ậ y_lower b ng v i 3. Khi y+1y+1 b ng v i ớ y_lower ằ 3. Khi ớ ằ c a m t c nh thì nó ph i ả ộ ạ ủ c a m t c nh thì nó ph i ủ ả ộ ạ c chèn vào AEL (giá tr đ ị ượ c chèn vào AEL (giá tr đ ị ượ c a c nh này s trình bày sau ẽ ủ ạ c a c nh này s trình bày sau ẽ ủ ạ trong Edge Table). trong Edge Table). c a hoành đ giao 4. Th t ộ ứ ự ủ c a hoành đ giao 4. Th t ộ ứ ự ủ c khi 2 đi m có th đ o ng ượ ể ả ể c khi 2 đi m có th đ o ng ượ ể ể ả c t) c nh giao nhau (đa giác t ự ắ ạ c t) c nh giao nhau (đa giác t ự ắ ạ i. : AEL ph i đ ả ượ ắ ế ạ i. : AEL ph i đ ả ượ ắ ế ạ
0 1 2
43
5 6 7 8 9
T i y : ael = {
ạ
e5, e4, e3, e2}
T i y+1 : ael = {
ạ
e5, e4, e3, e1}
2525
EdgeTable EdgeTable
Đ xác đ nh c nh nào đ Đ xác đ nh c nh nào đ ị ị ạ ạ ả ả ể ể ượ ượ ỉ ỉ
đ EdgeTable đ EdgeTable
ướ ướ c chèn vào AEL, chúng ta ph i xét t ng đ nh ừ c chèn vào AEL, chúng ta ph i xét t ng đ nh ừ l u tr c t o ra đ ữ ư ể l u tr ượ ạ ấ c t o ra đ ữ ư ể ượ ạ ấ c khi quá trình tô màu x y ra, b o đ m yêu ả ả ả c khi quá trình tô màu x y ra, b o đ m yêu ả ả ả
thông qua đ nh đa giác, recip_slope thông qua đ nh đa giác, ỉ ỉ
ạ ạ
ư ư = yy y_lower = y_lower c a đa giác. Tuy nhiên, c u trúc ủ c a đa giác. Tuy nhiên, c u trúc ủ tr thông tin các c nhạ tr thông tin các c nhạ c u c p nh t nhanh chóng AEL: ậ ầ ậ c u c p nh t nhanh chóng AEL: ậ ầ ậ • M i c nh đ y_upper, , recip_slope M i c nh đ c xác đ nh ượ ỗ ạ ị y_upper c xác đ nh ỗ ạ ượ ị i c a c nh. là hoành đ đ nh d x_int là hoành đ đ nh d và và x_int ướ ủ ạ ộ ỉ i c a c nh. ướ ủ ạ ộ ỉ • EdgeTable là m t m ng các danh sách các c nh (nh danh sách AEL). EdgeTable là m t m ng các danh sách các c nh (nh danh sách AEL). ả ộ ộ ả ] ch a danh sách các c nh có EdgeTable[yy] ch a danh sách các c nh có ạ ứ EdgeTable[ ạ ứ
2626
Building EdgeTable Building EdgeTable
AA
DD
CC
yyCC
xxBB
1/m1/mBCBC
yyAA
xxBB
1/m1/mBABA
BB
yyDD
xxEE
1/m1/mEDED
EE
yyAA
xxJJ
1/m1/mJAJA
JJ
GG
yyJJ-1-1
xxII
1/m1/mIJIJ
yyGG
xxHH
1/m1/mHGHG
HH
II
yyGG
xxFF
1/m1/mFGFG
yyEE-1-1
xxFF
1/m1/mFEFE
FF
2727
EdgeTable Ví d ụVí d ụ EdgeTable
ee77
ee66
22
88
22
ee11
ee66
ee11
-1-1
88
99
ee55
ee44
ee33
ee22
1/51/5
66
ee55 11
55
ee44 11
4/34/3
-1-1
55
44
00
9 8 7 6 5 4 3 2 1 0
99 ee33
99 ee22
11 10 9 8 7 6 5 4 3 2 1 0
0 1 2
43
5 6 7 8 9
2828
Dùng EdgeTable đ c p nh t AEL Dùng EdgeTable đ c p nh t AEL
ể ậ ể ậ
ậ ậ
Sau khi t o EdgeTable, AEL d dàng đ Sau khi t o EdgeTable, AEL d dàng đ c c p nh t thông qua các c nh c c p nh t thông qua các c nh ạ ạ ậ ậ ạ ạ
ễ ễ i dòng scanline i dòng scanline ượ ậ ượ ậ yy:: ẵ ẵ ạ ạ
ạ ạ ] vào AEL : nghĩa là dòng scanline b t ắ yy] vào AEL : nghĩa là dòng scanline b t ắ
i nên chính là i nên chính là ầ ắ ầ ắ ị ị ộ ủ ỉ ộ ủ ỉ ướ ướ
có s n trong EdgeTable t có s n trong EdgeTable t • Chèn các c nh t Chèn các c nh t ạ ạ đ u c t các c nh có ạ đ u c t các c nh có ạ • Giá tr ban đ u c a Giá tr ban đ u c a ầ ủ x_int ầ ủ hoành đ giao đi m ban đ u. ể ộ hoành đ giao đi m ban đ u. ể ộ i EdgeTable[ i EdgeTable[ = yy y_lower = y_lower là hoành đ c a đ nh d x_int là hoành đ c a đ nh d ầ ầ
2929
Ví dụVí dụ
ee77
ee66
22
88
22
ee11
ee66
ee11
-1-1
88
99
ee55
ee44
ee33
ee22
1/51/5
66
ee55 11
55
ee44 11
4/34/3
-1-1
55
44
00
9 8 7 6 5 4 3 2 1 0
99 ee33
99 ee22
11 10 9 8 7 6 5 4 3 2 1 0
0 1 2
43
5 6 7 8 9
66 55 66 66 66 66
9/59/5 99 8/58/5 7/57/5 6/56/5 11
1/51/5 -1-1 1/51/5 1/51/5 1/51/5 1/51/5
88 44 55 55 55 55
11/311/3 88 99 55 7/37/3 11
-1-1 00 4/34/3 4/34/3 4/34/3 4/34/3
55 55 55 55
55 88 66 77
-1-1 -1-1 -1-1 -1-1
88 44 44 44
99 99 99 99
-1-1 00 00 00
AEL
3030
Thu t toán c i ti n Thu t toán c i ti n
ả ế ả ế
ậ ậ
EdgeTable;; Xây d ng ự EdgeTable Xây d ng ự = NULL; AELAEL = NULL; = y_min; y <= y_max; y++) for( yy = y_min; y <= y_max; y++) for( {{
EdgeTable[y] vào EdgeTable[y] vào AELAEL;;
t c các c nh trong Chèn t ạ ấ ả t c các c nh trong Chèn t ấ ả ạ if (if (AELAEL != NULL) != NULL) {{
ề ề x_int;; ầ ủ x_int ầ ủ
ạ ạ
S p x p AEL theo chi u tăng d n c a ắ ế S p x p AEL theo chi u tăng d n c a ắ ế các run trong AEL; Tô màu các run trong AEL; Tô màu Xóa các c nh trong AEL có Xóa các c nh trong AEL có C p nh t giá tr ị x_int ậ C p nh t giá tr ị ậ y_upper = y_upper trong các c nh c a AEL; x_int trong các c nh c a AEL; ạ ạ = yy;; ủ ủ ậ ậ
}}
}}
