Bài giảng Đồ họa máy tính - Chương 1: Giới thiệu đồ họa máy tính - Trường Đại học Bách khoa TP Hồ Chí Minh

ĐỒ HỌA MÁY TÍNH 
Trƣờng Đại Học Bách Khoa TP Hồ Chí Minh 
Khoa Khoa học & Kỹ thuật Máy tính 
CHƢƠNG 1: 
GIỚI THIỆU ĐỒ HỌA 
MÁY TÍNH 
Slide 2 Faculty of Computer Science and Engineering - HCMUT 
NỘI DUNG TRÌNH BÀY 
Giới thiệu tổng quan về đồ họa máy tính 
Đối tƣợng cơ bản trong đồ họa máy tính 
Thiết bị hiển thị đồ họa 
Slide 3 Faculty of Computer Science and Engineering - HCMUT 
CHƢƠNG TRÌNH 
Nội dung 
Chƣơng 1-Giới thiệu đồ họa máy tính 
Chƣơng 2-Bƣớc đầu tạo dựng hình ảnh 
Chƣơng 3-Xây dựng công cụ vẽ hình ảnh 
Chƣơng 4-Vector trong đồ họa máy tính 
Chƣơng 5-Biến đổi hình 
Chƣơng 6-Mô hình hóa đối tƣợng 3 D bằng lƣới đa giác 
Chƣơng 7-Phép nhìn trong không gian ba chiều 
Chƣơng 8-Tô màu vật thể ba chiều 
Chƣơng 9-Kỹ thuật lặp đệ quy, ứng dụng tạo hoa văn 
Chƣơng 10-Đồ họa raster 
Slide 4 Faculty of Computer Science and Engineering - HCMUT 
TÀI LIỆU MÔN HỌC 
 [1] Francis S. Hill, Jr, Computer Graphics, Macmillan Publishing 
Company, 1990. 
 [2] Foley, van Dam, Feiner, Hughes, Computer Graphics principles and 
practice, Addison-Wesley Publishing Company, 1996. 
 [3] Nguyễn Hữu Lộc, Đồ họa máy tính và mô hình hóa hình học, Nhà 
xuất bản thành phố Hồ Chí Minh, 2000. 
 [4] Hoàng Kiếm, Dƣơng Anh Đức, Lê Đình Huy, Vũ Hải Quân, Cơ sở 
đồ họa máy tính, Nhà xuất bản giáo dục, 2000. 
 [5] Nguyễn Quốc Cƣờng, Hoàng Đức Hải, Đồ họa vi tính, Nhà xuất bản 
giáo dục, 1998. 
 [6] Tống Nghĩa, Hoàng Đức Hải, Đồ họa máy tính trong ngôn ngữ C, Nhà 
xuất bản giáo dục, 1999. 
 [7] Nguyễn Tiến, Ngô Quốc Việt, Giáo trình đồ họa máy tính, Nhà xuất 
bản thống kê, 2001. 
 [8] Lê Tấn Hùng, Huỳnh Quyết Thắng, Kỹ thuật đồ họa, Nhà xuất bản 
Khoa học và Kỹ thuật, 2004 
  Graphics 
Slide 5 Faculty of Computer Science and Engineering - HCMUT 
ĐỊNH NGHĨA ĐỒ HỌA MÁY TÍNH 
Dùng máy tính để tạo ra hình ảnh 
Đồ họa máy tính và xử lý ảnh 
– Đồ họa máy tính: tạo hình ảnh dựa trên đặc tả hoặc 
mô hình 
– Xử lý ảnh: nâng cao chất lƣợng hoặc chỉnh sửa hình 
ảnh. 
Slide 6 Faculty of Computer Science and Engineering - HCMUT 
ỨNG DỤNG CỦA ĐỒ HỌA MÁY TÍNH 
Ứng dụng trong giải trí, xuất bản và nghệ thuật 
– Sản xuất phim hoạt hình, tạo hiệu ứng cho phim nhựa 
– Trò chơi máy tính 
– Duyệt Web 
– Chế bản điện tử 
Xử lý ảnh 
Ứng dụng trong tự động hóa và điều khiển 
Mô phỏng 
Máy tính hỗ trợ thiết kế 
– Hỗ trợ thiết kế kiến trúc 
– Hỗ trợ thiết kế mạch điện tử 
Hình ảnh hóa số liệu khoa học 
Slide 7 Faculty of Computer Science and Engineering - HCMUT 
ĐỐI TƢỢNG CƠ BẢN TRONG ĐHMT 
Đƣờng gấp khúc (polyline) 
Văn bản (text) 
Vùng tô (filled region) 
Ảnh ma trận điểm hay ảnh raster (raster image) 
Slide 8 Faculty of Computer Science and Engineering - HCMUT 
ĐƢỜNG GẤP KHÖC 
Đƣờng gấp khúc là một tập các đoạn thẳng đƣợc nối với 
nhau. 
Đƣờng gấp khúc đƣợc dùng mô phỏng đƣờng cong. 
Các hàm liên quan 
– Vẽ điểm: drawDot(x1, y1) 
– Vẽ đoạn thẳng: drawLine(x1, y1, x2, y2) 
– Vẽ đƣờng gấp khúc: drawPolyline(poly) 
Slide 9 Faculty of Computer Science and Engineering - HCMUT 
ĐƢỜNG GẤP KHÖC 
Khi đỉnh đầu và đỉnh cuối đƣợc nối bằng một đoạn thẳng 
thì đƣờng gấp khúc trở thành đa giác 
Slide 10 Faculty of Computer Science and Engineering - HCMUT 
ĐƢỜNG GẤP KHÖC 
Thuộc tính 
– Màu sắc 
– Độ dày 
– Kiểu đƣờng (liền nét, đứt nét) 
– Cách nối hai cạnh dày 
Thiết lập thuộc tính: 
 setDash (dash7) hoặc setLineThickness(thickness). 
Slide 11 Faculty of Computer Science and Engineering - HCMUT 
VĂN BẢN 
Một số thiết bị có hai chế độ hiển thị 
– Chế độ hiển thị văn bản 
– Chế độ hiển thị đồ họa 
Thủ tục hiển thị chuỗi 
– drawString(x, y, string); 
Thuộc tính 
– Font 
– Màu sắc 
– Kích thƣớc 
– Hƣớng 
– Khoảng cách giữa các ký tự trong chuỗi 
Slide 12 Faculty of Computer Science and Engineering - HCMUT 
VĂN BẢN 
Slide 13 Faculty of Computer Science and Engineering - HCMUT 
VÙNG TÔ 
Hình đƣợc tô bởi màu hoặc mẫu tô. Đƣờng biên thƣờng 
là hình đa giác. 
Thủ tục : fillPolygon(poly, pattern); 
Slide 14 Faculty of Computer Science and Engineering - HCMUT 
VÙNG TÔ 
Dùng vùng tô để mô phỏng các mặt khác nhau của vật 
thể tô màu 
Slide 15 Faculty of Computer Science and Engineering - HCMUT 
ẢNH RASTER 
Đƣợc tạo bởi các pixel 
Lƣu trữ dƣới dạng mảng các giá trị 
Phƣơng pháp tạo ảnh raster 
– Thiết kế thủ công 
– Tạo bằng thuật toán 
– Quét 
Ảnh raster có thể tiến hành xử lý 
Slide 16 Faculty of Computer Science and Engineering - HCMUT 
THIẾT BỊ HIỂN THỊ ĐỒ HỌA 
Thiết bị đồ họa vector: tạo hình ảnh từ những đoạn 
thẳng 
– Ƣu điểm: nhanh 
– Khuyết điểm: không tô màu cho vùng đƣợc 
Các loại thiết bị vector thƣờng gặp 
– Máy vẽ: 
• Máy vẽ flatbed 
• Máy vẽ dạng trống 
– Màn hình vector 
Slide 17 Faculty of Computer Science and Engineering - HCMUT 
THIẾT BỊ HIỂN THỊ ĐỒ HỌA 
Thiết bị raster: Tạo hình ảnh từ ma trận điểm 
Phân loại: 
– Màn hình video 
– Màn hình tấm phẳng 
– Các thiết bị sao chép cứng 
• Máy in film (film recorder) 
• Máy in laser 
• Máy in phun 
Slide 18 Faculty of Computer Science and Engineering - HCMUT 
THIẾT BỊ RASTER 
Các vấn đề cần tìm hiểu 
– Bề mặt hiển thị 
– Bộ đệm frame 
– Quá trình quét dòng 
Bề mặt hiển thị (display surface) 
Slide 19 Faculty of Computer Science and Engineering - HCMUT 
THIẾT BỊ RASTER 
Bộ đệm frame 
CPU Bộ nhớ hệ 
thống 
Bộ đệm 
Bộ điều khiển 
quét dòng 
Bộ chuyển đổi 
Bus hệ thống 
Bề mặt hiển thị 
Slide 20 Faculty of Computer Science and Engineering - HCMUT 
THIẾT BỊ RASTER 
Quá trình quét dòng 
Slide 21 Faculty of Computer Science and Engineering - HCMUT 
THIẾT BỊ RASTER 
Màn hình video màu 
Slide 22 Faculty of Computer Science and Engineering - HCMUT 
THIẾT BỊ RASTER 
Màu chỉ mục và bảng tìm kiếm 
Slide 23 Faculty of Computer Science and Engineering - HCMUT 
THIẾT BỊ RASTER 
Màu chỉ mục và bảng tìm kiếm 
Slide 24 Faculty of Computer Science and Engineering - HCMUT 
THIẾT BỊ RASTER 
Màn hình tấm phẳ ... ol1 to col2 do 
 begin 
 SetPixel(x, Round(y),color); 
 y:= y + m; 
 end; 
 end; 
Slide 328 Faculty of Computer Science and Engineering - HCMUT 
Thuaät toaùn Bresenham 
Nhöõng haïn cheá cuûa giaûi thuaät DD_Line 
– Chaäm vì söû duïng haøm Round 
– Khoâng chính xaùc khi khoaûng caùch giöõa 2 ñieåm ñaàu 
muùt lôùn 
– Ñoä saùng khoâng ñoàng ñeàu 
Thuaät toaùn Bresenham 
– Chæ duøng soá nguyeân 
– Thuoäc vaøo lôùp giaûi thuaät incremental (xaùc ñònh toïa ñoä 
cuûa ñieåm hieän haønh döïa vaøo toïa ñoä cuûa ñieåm tröôùc) 
Slide 329 Faculty of Computer Science and Engineering - HCMUT 
Cho ñoaïn thaúng noái hai ñieåm (x
a
 , y
a
) vaø (x
b
 , y
b
), 
– caùc toïa ñoä ñeàu laø soá nguyeân (toïa ñoä trong frame buffer) 
Bieåu dieãn töôøng minh cuûa ñöôøng thaúng: 
– Ñoä doác: , vôùi 
Baøi toaùn: Xaùc ñònh caùc pixel bieåu dieãn ñoaïn thaúng “toát” nhaát 
– tuøy thuoäc vaøo caùch ñònh nghóa sai soá 
Wlog (without loss of generality), x
a
 < x
b
 vaø 0 < m < 1 
– X taêng töø a ñeán b 
– X taêng nhanh hôn y 
– Moãi laàn x taêng leân 1, y khoâng taêng hoaëc taêng leân 1 
Bieåu dieãn ñoaïn thaúng trong frame buffer 
y = m(x - x
a
) + y
a
x
y
m
Dy = y
b
 - y
a
Dx = x
b
 - x
a
Slide 330 Faculty of Computer Science and Engineering - HCMUT 
Sai soá khi choïn pixel 
Sinh caùc pixel baèng phöông phaùp taêng daàn 
Ñònh nghóa sai soá e(Ti) = y* - yi - 1 
e(S
i
) = (y
i - 1
 + 1) - y* 
x
i - 1 
x
i
y
i - 1 
S
i
T
i
Ñoaïn thaúng lyù töôûng 
y
*
Slide 331 Faculty of Computer Science and Engineering - HCMUT 
Quy taéc choïn pixel xaáp xæ toát ñoaïn thaúng thöïc 
Quy taéc choïn pixel 
Tính e(T
i
) - e(S
i
) = 2m(x
i
 - x
a
) + 2(y
a
 - y
i - 1
) - 1 
Töø treân, ñeå chæ tính vôùi soá nguyeân, ñònh nghóa 
e
i
 = Dx(e(T
i
) - e(S
i
)) 
 = 2(Dy)(x
i
 - x
a
) + 2(Dx)(y
a
 - y
i - 1
) - Dx (*) 
Choïn T
i
 neáu vaø chæ neáu e(T
i
) - e(S
i
) < 0 
Neáu e
i
 < 0 thì choïn y
i
 = y
i - 1
 , neáu khoâng thì choïn y
i
 = y
i - 1
 + 1
Caàn kieåm tra tính ñuùng ñaén cuûa quy taéc treân! 
Slide 332 Faculty of Computer Science and Engineering - HCMUT 
Kieåm tra tính ñuùng ñaén cuûa quy taéc choïn pixel 
Tröôøng hôïp ñoaïn thaúng lyù töôûng ñi qua giöõa S
i
 vaø T
i
x
i - 1
 x
i
y
i - 1
S
i
T
i
Ñoaïn thaúng lyù töôûng 
e(T
i
) = y* - y
i - 1 
e(S
i
) = (y
i - 1
 + 1) - y* 
y
*
Slide 333 Faculty of Computer Science and Engineering - HCMUT 
Kieåm tra tính ñuùng ñaén cuûa quy taéc choïn pixel (tieáp) 
Caùc tröôøng hôïp coøn laïi 
xi 1 xi 
yi 1 
Si 
Ti 
xi 1 xi 
yi 1 
Si 
Ti 
Nhaéc laïi: e(T
i
) = y* y
i 1 
 e(S
i
) = (y
i 1 + 1) y* 
ñoaïn thaúng lyù töôûng 
ñi qua phía treân S
i
 vaø T
i 
ñoaïn thaúng lyù töôûng 
ñi qua phía döôùi S
i
 vaø T
i 
e(T
i
) >= 0
e(S
i
) <= 0 
e(T
i
) <= 0
e(S
i
) >= 0 
Slide 334 Faculty of Computer Science and Engineering - HCMUT 
Tính sai soá moät caùch höõu hieäu 
Töø 
 suy ra e
i + 1
 = 2(Dy)(x
i + 1
 - x
a
) + 2(Dx)(y
a
 - y
i 
) ‟ Dx 
 Töø treân, e
i + 1
 = e
i
 + 2(Dy)(x
i + 1
 - x
i
) - 2(Dx)(y
i
 - y
i - 1 
) 
 Theo quy taéc choïn pixel, 
‟ neáu e
i
 < 0 thì choïn y
i
 = y
i - 1
 e
i + 1
 = e
i
 + 2Dy 
‟ neáu khoâng thì choïn y
i
 = y
i - 1 
+ 1 
 e
i + 1
 = e
i
 + 2Dy - 2Dx 
e
i
 = 2(Dy)(x
i
 - x
a
) + 2(Dx)(y
a
 - y
i - 1
) - Dx 
Slide 335 Faculty of Computer Science and Engineering - HCMUT 
Giaûi thuaät cuûa Bresenham 
Bieåu dieãn ñoaïn thaúng trong frame buffer 
‟ Giaûi thuaät baét ñaàu nhö theá naøo? 
„ x
0
 = x
a
, y
0
 = y
a
„ Töø (*) coù e
1
 = 2(Dy) - Dx (duøng x
1
 - x
a
 = 1) 
procedure Bresenham(xa, xb : col; ya, yb : row; col_val : color); 
{veõ ñoaïn thaúng coù maøu laø col_val töø (xa, ya) ñeán (ya, yb)} 
{wlog, xa < xb vaø 0 < ñoä doác cuûa ñoaïn thaúng < 1} 
var 
 x : col; 
 y : row; 
 dx, dy, 
 e_inc, {thay ñoåi cuûa sai soá khi y taêng} 
 e_noinc, {thay ñoåi cuûa sai soá khi y khoâng taêng} 
 e : integer; {sai soá hieän thôøi} 
Slide 336 Faculty of Computer Science and Engineering - HCMUT 
Giaûi thuaät cuûa Bresenham (tieáp) 
begin 
 y := ya; 
 dx := xb - xa; 
 dy := yb - ya; 
 e_noinc := dy + dy; {2dy} 
 e := e_noinc - dx; {e1=2dy-dx} 
 e_inc := e - dx; {2dx-dy} 
 for x := xa to xb do {voøng laëp chính} 
 begin 
 SetPixel(x, y, col_val); 
 if e < 0 then e := e + e_noinc; 
 else begin 
 y := y + 1; 
 e := e + e_inc 
 end; 
 end; 
end; {Bresenham} 
Slide 337 Faculty of Computer Science and Engineering - HCMUT 
Caùc tröôøng hôïp khaùc 
 Giaûi thuaät Bresenham giaû söû x
a
 > x
b
 vaø 0 < m < 1. 
Giaûi quyeát caùc tröôøng hôïp coøn laïi: 
x
a
 > x
b
 (ñoåi vò trí hai ñaàu muùt) 
m > 1 (ñoåi vai troø cuûa x vaø y) 
Ñoä doác aâm: -1 < m < 0 (thay dy baèng ‟dy) 
m < -1 (thay dx baèng ‟dx, ñoåi vai troø cuûa x vaø y) 
Ñoaïn thaúng ñöùng vaø ñoaïn thaúng naèm ngang 
Slide 338 Faculty of Computer Science and Engineering - HCMUT 
Bieåu dieãn voøng troøn trong frame buffer 
Baøi toaùn: Xaùc ñònh caùc pixel bieåu dieãn voøng troøn y2 = 
R
2
 ‟ x2 “toát” nhaát 
‟ tuøy thuoäc vaøo caùch ñònh nghóa sai soá 
Giaûi quyeát 
‟ Do ñoái xöùng, chæ caàn khaûo saùt caùch veõ khi 0 x 
sao cho y(x) x töùc laø cung AB. 
‟ Sinh caùc pixel baèng phöông phaùp taêng daàn 
(incremental). 
Slide 339 Faculty of Computer Science and Engineering - HCMUT 
Ñoái xöùng treân voøng troøn 
Giaûm phí toån tính toaùn baèng caùch duøng pheùp ñoái 
xöùng treân voøng troøn 
‟ Chæ caàn xaùc ñònh caùc pixel töông öùng vôùi moät 
cung laø 1/8 voøng troøn, ôû ñaây choïn cung AB. 
(x, y) 
(y, x) 
(y, x) 
( x, y) (x, y) 
( y, x) 
( y, x) 
( x, y) 
x 
y 
A 
B 
Slide 340 Faculty of Computer Science and Engineering - HCMUT 
Sai soá khi choïn pixel 
Giaû söû coù pixel toát nhaát taïi böôùc thöù i - 1 laø P
i - 1
 = 
(x
i - 1
, y
i - 1
) 
Ñònh nghóa 
 S
i
 = (x
i - 1
 + 1, y
i - 1
) 
 T
i
 = (x
i - 1
 + 1, y
i - 1
 - 1) 
Ñònh nghóa sai soá 
 e(P) = (x
2
 + y
2
) - R
2 
Ñònh nghóa haøm soá quyeát ñònh 
 d
i
 = e(S
i
) + e(T
i
) 
xi 
1 
xi 
yi 1 
Pi 1 Si 
Ti 
Slide 341 Faculty of Computer Science and Engineering - HCMUT 
Qui taéc choïn pixel xaáp xæ toát cung voøng troøn 
 xi 
1 
xi 
yi 1 
Pi 1 Si 
Ti 
Neáu d
i
 < 0 thì choïn S
i 
coøn neáu khoâng thì choïn T
i 
Caàn kieåm tra tính ñuùng ñaén cuûa quy taéc treân! 
Slide 342 Faculty of Computer Science and Engineering - HCMUT 
Kieåm tra tính ñuùng ñaén cuûa quy taéc choïn pixel 
Nhaéc laïi: d
i
 = e(S
i
) + e(T
i
) 
Tröôøng hôïp: d
i
 < 0 (S
i 
gaàn ñöôøng troøn hôn)
Si Si Si 
Ti Ti 
Ti 
e(Si) > 0 
e(Ti) < 0 
e(Si) > 0 
e(Ti) > 0 
e(Si) < 0 
e(Ti) < 0 
OK! OK, vì di < 0 
 S
i
 gaàn ñöôøng troøn hôn
Khoâng theå! 
Slide 343 Faculty of Computer Science and Engineering - HCMUT 
Kieåm tra tính ñuùng ñaén cuûa quy taéc choïn pixel (tieáp) 
Nhaéc laïi: d
i
 = e(S
i
) + e(T
i
) 
Tröôøng hôïp: d
i
 0 (T
i
 gaàn ñöôøng troøn hôn)
Si Si Si 
Ti Ti 
Ti 
e(Si) > 0 
e(Ti) < 0 
e(Si) > 0 
e(Ti) > 0 
e(Si) < 0 
e(Ti) < 0 
Khoâng theå! OK!
OK, vì d
i
 0 
 T
i
 gaàn ñöôøng troøn hôn 
Slide 344 Faculty of Computer Science and Engineering - HCMUT 
Tính haøm soá quyeát ñònh moät caùch höõu hieäu 
Nhaéc laïi: e(P) = (x2 + y2) - R2 
Coù theå chöùng minh ñöôïc (baøi taäp): 
 d
i + 1
 = d
i
 + 4 x
i - 1
 + 6 + 2(y
i
2
 - y
i - 1
2
) - 2(y
i
 - y
i - 1
) 
 Theo quy taéc choïn pixel 
‟ neáu d
i
 < 0 thì ta coù y
i
 = y
i - 1 
, do ñoù choïn T
i
 d
i + 1
 = d
i
 + 4 x
i - 1
 + 6 
‟ neáu khoâng thì y
i
 = y
i - 1
 - 1, do ñoù choïn S
i
 d
i + 1
 = d
i
 + 4(x
i - 1
 - y
i - 1
) + 10 
Giaûi thuaät baét ñaàu nhö theá naøo? 
 x
0
 = 0, y
0
 = R 
 do ñoù S
1
 = (1, R) vaø T
1
 = (1, R - 1), vaäy 
 d
1
=e(S
1
) + e(T
1
) =(1
2
+R
2
-R
2
)+(1
2+
(R-1)
2
-R
2)=
3 - 2R 
Slide 345 Faculty of Computer Science and Engineering - HCMUT 
Giaûi thuaät cuûa Michener 
Bieåu dieãn voøng troøn trong frame buffer 
procedure MichCirc(xc : col; yc : row; Rad : integer; value : color); 
{Veõ voøng troøn coù taâm (xc, yc), baùn kính Rad, vaø maøu value} 
var 
 x : col; 
 y : row; 
 d : integer; 
begin 
 x := 0; y := Rad; 
 d := 3 - 2*Rad; 
Slide 346 Faculty of Computer Science and Engineering - HCMUT 
Giaûi thuaät cuûa Michener (tieáp) 
 while x <= y do begin 
 SetPixel(xc + x, yc + y, value); {draw 8 points } 
 SetPixel(xc - x, yc + y, value); {based on (x, y)} 
 SetPixel(xc + x, yc - y, value); 
 SetPixel(xc - x, yc - y, value); 
 SetPixel(xc + y, yc + x, value); 
 SetPixel(xc - y, yc + x, value); 
 SetPixel(xc + y, yc - x, value); 
 SetPixel(xc - y, yc - x, value); 
 if d < 0 then d := d + 4*x + 6 {update error term} 
 else begin 
 d := d + 4*(x - y) + 10; 
 y := y - 1 
 end; 
 x := x + 1 
 end 
end; {MichCirc} 
Slide 347 Faculty of Computer Science and Engineering - HCMUT 
Ñònh nghóa vuøng 
Ñònh nghóa vuøng baèng pixel 
Ñònh nghóa vuøng baèng ña giaùc 
Slide 348 Faculty of Computer Science and Engineering - HCMUT 
Định nghĩa vùng bằng pixel 
 Dựa trên màu của các pixel 
 Hai cách định nghĩa tính kết nối: 
– 4-connected: 2 điểm ảnh được xem là kết nối nếu 
chúng nằm kề nhau theo chiều ngang hay chiều dọc 
– 8-connected: 2 điểm ảnh được xem là kết nối nếu 
chúng nằm kề nhau theo chiều ngang, chiều dọc hay 
đường chéo 
 Hai cách xác định vùng bởi: 
– Tất cả các điểm ảnh trong vùng có cùng 1 màu, có thể 
có lỗ trống (hole) bên trong. 
– Vùng được xác định bởi các điểm ảnh có cùng màu của 
đường bao quanh, các điểm ảnh bên trong không có 
màu bao, có thể có lỗ trống bên trong 
Slide 349 Faculty of Computer Science and Engineering - HCMUT 
Ví duï 
Slide 350 Faculty of Computer Science and Engineering - HCMUT 
Giải thuật tô màu tràn đệ qui 
 Dùng trong các phần mềm đồ họa 
 Vùng xác định bởi 1 màu và 4-connected 
 Bắt đầu bằng bởi 1 điểm hạt giống (seed) nằm bên trong vùng cần tô 
procedure FloodFill(x : col; y : row; int_color, new_color : color); 
{bắt đầu từ điểm (x,y), đổi từ màu int_color sang new_color} 
begin 
 if GetPixel(x, y) = int_color then 
 begin 
 SetPixel(x, y, new_color); 
 FloodFill(x – 1, y, int_color, new_color); 
 FloodFill(x + 1, y, int_color, new_color); 
 FloodFill(x, y + 1, int_color, new_color); 
 FloodFill(x, y – 1, int_color, new_color); 
 end 
end; 
Slide 351 Faculty of Computer Science and Engineering - HCMUT 
Giải thuật tô màu tràn đệ qui (tt.) 
 Vùng xác định bởi 1 màu và 8-connected 
 Bắt đầu bằng bởi 1 điểm hạt giống (seed) nằm bên trong vùng 
cần tô 
 Thêm: 
 FloodFill(x – 1, y – 1, int_color, new_color); 
 FloodFill(x – 1, y + 1, int_color, new_color); 
 FloodFill(x + 1, y + 1, int_color, new_color); 
 FloodFill(x + 1, y – 1, int_color, new_color); 
. Nhược điểm: 
 - bị lặp lại nhiều lần 
 - dễ bị tràn stack 
Slide 352 Faculty of Computer Science and Engineering - HCMUT 
Giải thuật tô màu tràn đệ qui (tt.) 
 Vùng xác định bởi màu bao và 4-connected 
 Bắt đầu bằng bởi 1 điểm hạt giống (seed) nằm bên trong vùng cần tô 
procedure FloodFill(x : col; y : row; int_color, new_color : color); 
{bắt đầu từ điểm (x,y), đổi từ màu int_color sang new_color} 
begin 
 if (GetPixel(x, y) >< new_color) then 
 begin 
 SetPixel(x, y, new_color); 
 FloodFill(x – 1, y, int_color, new_color); 
 FloodFill(x + 1, y, int_color, new_color); 
 FloodFill(x, y + 1, int_color, new_color); 
 FloodFill(x, y – 1, int_color, new_color); 
 end 
end; 
Slide 353 Faculty of Computer Science and Engineering - HCMUT 
Run of Pixels 
 Giaû thieát caùc pixel laø 4-connected 
 Giaûi thuaät 
 Push address of seed pixel on the stack; 
 while stack not empty do 
 Pop the stack to provide the next seed; 
 Fill in the run defined by the seed; 
 Examine the row above for runs reachable from this run; 
 Push the address of the rightmost pixels of each such 
run; 
 Do the same for the row below the current run; 
 end; 
Slide 354 Faculty of Computer Science and Engineering - HCMUT 
Ví duï 
Slide 355 Faculty of Computer Science and Engineering - HCMUT 
Ví duï 
D 
C 
Slide 356 Faculty of Computer Science and Engineering - HCMUT 
Ví duï 
J 
I 
G 
F 
C 
Slide 357 Faculty of Computer Science and Engineering - HCMUT 
Tô màu vùng đa giác 
Xét từng dòng ngang trên bộ đệm màn hình: 
– Tìm các giao điểm của dòng với tất cả các cạnh của 
đa giác 
– Sắp xếp các giao điểm theo chiều tăng dần giá trị x 
– Tô các điểm ảnh nằm giữa các cặp giao điểm 
Slide 358 Faculty of Computer Science and Engineering - HCMUT 
Tô màu vùng đa giác 
 Cạnh nằm ngang không cần phải xử lý 
 Tính chẵn lẻ không còn đúng khi ở điểm mút không phải là cực trị 
địa phương. 
– Cách giải quyết: dịch điểm đầu mút của một cạnh xuống 1 pixel 
Slide 359 Faculty of Computer Science and Engineering - HCMUT 
Tô màu vùng đa giác 
 Active Edge List (AEL) lợi dụng tính lân cận của cạnh 
– những cạnh cắt bởi scanline y sẽ cắt bởi scanline y+1 
– giá trị x của giao điểm có thể dự đoán trước 
 type 
 edge_ptr = ^edge_info 
 edge_info = record 
 y_upper : row; 
 x_int : real; 
 recip_slope : real; 
 next : egde_ptr; 
 end; 
Slide 360 Faculty of Computer Science and Engineering - HCMUT 
Tô màu vùng đa giác 
 update AEL cho scanline y+1 
– xóa tất cả những cạnh có y_upper < new_y 
– thay đổi x_value bằng cách cộng thêm recip_slope 
– có thể thêm vào cạnh mới có y_lower = new_y 
– thứ tự của giao điểm có thể bị xáo trộn, nên phải sắp 
xếp lại 
Slide 361 Faculty of Computer Science and Engineering - HCMUT 
Tô màu vùng đa giác 
 Xây dựng bảng cạnh: edge_table: array [row] of edge_ptr