Giáo trình Đồ họa máy tính - Chương 2: Các đối tượng đồ họa cơ sở

 loang dần và lần lượt tô từng đoạn 
giao theo dòng quét ngang thay vì tô theo 4 điểm lân cận. Như vậy chúng ta chỉ cần 
lưu lại thông tin của điểm bắt đầu mỗi đoạn giao của dòng quét ngang thay vì phải lưu 
hết tất cả các điểm lân cận chưa được tô của điểm hiện hành. Chúng ta sẽ cho các 
dòng quét loang từ điểm bắt đầu theo hướng lên biên trên, sau khi đã tô xong, các 
dòng quét còn lại theo hướng xuống biên dưới sẽ được tô. Ứng với mỗi dòng quét 
ngang, ta sẽ loang và tìm pixel trái nhất (có hoành độ nhỏ nhất) để lưu lại. Trong hình 
2.26, đoạn giao đầu tiên chứa điểm bắt đầu (tô màu trắng) sẽ được tô trước. Sau đó 
các vị trí 1, 2 ứng với các đoạn giao của các dòng quét kế tiếp sẽ được lưu lại (hình 
2.26a). Bước tiếp theo, điểm ứng với vị trí 2 sẽ được lấy ra và tiến hành tô màu bằng 
cách loang từ điểm này ra theo chiều ngang, sau đó pixel ứng vị trí 3 của dòng quét 
kế tiếp sẽ được lưu lại (hình 2.26b). Sau khi dòng quét ứng với điểm 3 đã được xử lí 
tương tự như trên xong, stack lưu các vị trí của các điểm “hạt giống” cho các dòng 
quét kế tiếp như trong hình 2.26c. Hình 2.26d minh họa khi thuật toán đã tô được toàn 
bộ một phần vùng phía trên bên phải của vùng tô. Khi pixel ứng với vị trí 5 được xử lí 
xong, ta có phần còn lại phía trên bên trái sẽ được tô. Sau đó pixel ứng với vị trí 4 sẽ 
được xử lí, các dòng quét phía dưới sẽ được tô tiếp theo. 
Hình 2.26 – Thuật toán tô màu theo dòng quét cải tiến 
TÓM TẮT 
Các đối tượng đồ họa cơ sở cung cấp các công cụ cơ bản nhất cho việc xây dựng các ảnh đồ họa của các đối tượng phức 
tạp. Các đoạn thẳng, đường cong, vùng tô, kí tự, … là các đối tượng đồ họa cơ sở được hầu hết tất cả các công cụ lập trình đồ họa 
hỗ trợ. 
Mỗi đối tượng đồ họa cơ sở được mô tả thông qua dữ liệu về tọa độ và các thuộc tính của nó. Hệ tọa độ thường được dùng 
để mô tả đối tượng là hệ tọa độ Descartes. Các thuộc tính của đối tượng như màu sắc, kiểu, độ rộng, … cho biết kiểu cách mà đối 
tượng được hiển thị trên thiết bị. 
Để có thể hiển thị các đối tượng đồ họa trên thiết bị hiển thị dạng điểm mà điển hình là màn hình, cần phải có một quá 
trình chuyển các mô tả hình học của các đối tượng này trong hệ tọa độ thế giới thực về dãy các pixel tương ứng gần với chúng 
nhất trên hệ tọa độ của thiết bị. Quá trình này còn được gọi là quá trình chuyển đổi bằng dòng quét. Yêu cầu quan trọng nhất đối 
với quá trình này ngoài việc phải cho kết quả xấp xỉ tốt nhất còn phải cho tốc độ tối ưu. 
Ba cách tiếp cận để vẽ đoạn thẳng gồm thuật toán DDA, thuật toán Bresenham, thuật toán MidPoint đều tập trung vào 
việc đưa ra cách chọn một trong hai điểm nguyên kế tiếp khi đã biết được điểm nguyên ở bước trước. Thuật toán DDA đơn giản 
chỉ dùng thao tác làm tròn nên phải dùng các phép toán trên số thực, trong khi đó thuật toán Bresenham và thuật toán MidPoint 
đưa ra cách chọn phức tạp hơn nhưng cho kết quả tốt hơn. Đối với trường hợp vẽ đoạn thẳng, hai thuật toán Bresenham và thuật 
toán MidPoint cho kết quả giống nhau và tốc độ tối ưu. 
Các đối tượng khác như đường tròn, ellipse và các đường conics khác cũng được vẽ tương tự bằng cách sử dụng thuật toán 
MidPoint. Riêng với các đường phức tạp hơn như đường spline, sẽ được xây dựng từ các đoạn thẳng xấp xỉ với đường cong thay 
vì phải xấp xỉ chúng từ các điểm (xem phần sau). 
Các thuật toán tô màu các vùng tô thường chia làm hai công đoạn : công đoạn thứ nhất là xác định các điểm nào để tô và 
công đoạn còn lại đơn giản hơn đó là quyết định tô các điểm đó bằng giá trị màu nào. Công đoạn thứ hai chỉ thực sự phức tạp 
nếu ta tô theo một mẫu tô nào đó không phải là tô thuần một màu. Có hai cách tiếp cận chính để tô màu một vùng tô đối với 
thiết bị hiển thị dạng điểm đó là : tô theo dòng quét và tô dựa theo đường biên. Cách tô theo dòng quét thường được dùng để tô 
màu các đa giác, đường tròn, ellipse, và một số đường cong đơn giản khác, còn cách tô theo đường biên thường được dùng cho 
các vùng tô có dạng đường biên phức tạp hơn. 
Thuật toán tô màu đa giác theo dòng quét xác định các điểm thuộc vùng tô bằng cách xác định phần giao của các dòng 
quét với các đoạn thẳng biên của đa giác. Điểm độc đáo của thuật toán này ở chỗ đưa ra cấu trúc dữ liệu danh sách các cạnh 
kích hoạt AET và cách hoạt động của chúng để có thể hạn chế tối đa các cạnh cần tìm giao điểm ứng với mỗi dòng quét. Đây là 
điểm mấu chốt trong vấn đề cải thiện tốc độ của thuật toán. Thuật toán này có thể được áp dụng cho nhiều dạng đa giác khác 
nhau như đa giác lồi, đa giác lõm, và cả đa giác tự cắt, … 
Thuật toán tô màu dựa theo đường biên xuất phát từ điểm nằm bên trong vùng tô và tiến hành loang dần ra các điểm lân 
cận cho tới khi gặp các điểm thuộc biên thì dừng. Cách làm này gặp hạn chế về bộ nhớ khi cài đặt bằng đệ quy. Một phương 
pháp cải tiến đã được đề cập đó là loang theo từng dòng quét. Việc tô màu theo cách này thực sự là thuận tiện cho các chương 
trình đồ họa ứng dụng có khả năng tương tác cao. 
BÀI TẬP 
1. Thiết kế và cài đặt hàm vẽ hình chữ nhật, đường gấp khúc, đa giác từ hàm vẽ đoạn thẳng. 
2. Trong phần trình bày thuật toán Bresenham để vẽ đường thẳng, hãy cho biết với cách đặt d1, d2 
như vậy, có khi nào d1, d2 lấy giá trị âm hay không ? Nếu có hãy cho ví dụ minh họa. 
3. Tại sao phải so sánh ip với giá trị 0 trong các thuật toán Bresenham, MidPoint. Bản chất của việc 
so sánh này là gì? 
4. Cài đặt các thuật toán DDA, Bresenham, MidPoint vẽ đoạn thẳng qua hai điểm cho trước trong 
trường hợp tổng quát với hệ số góc m lấy giá trị bất kì. 
5. Người ta có thể cải thiện tốc độ cài đặt thuật toán vẽ đoạn thẳng bằng cách chỉ cần vẽ một nửa 
đoạn thẳng, phần còn lại lấy đối xứng nửa đoạn thẳng đã vẽ. Hãy cài đặt minh họa. 
6. Cho biết các điểm nguyên vẽ phát sinh khi sử dụng các thuật toán DDA, MidPoint cho các đoạn 
thẳng đi qua các điểm lần lượt là A1(5,10), B1(15,17); A2(-2,3), B2(-12,7); A3(6,3), B3(9,13); 
A4(2,4), B4(-5,14); A5(0,10), B5(15,10); A6(5,-1), B6(5,-11); 
7. Trình bày thuật toán MidPoint vẽ cung tròn 1/8, bán kính R, tâm I(xC, yC) và được giới hạn bởi : 
⎪⎪⎩
⎪⎪⎨
⎧
≤≤
≤≤
2
20
2
2
Ry
RxR
8. Sử dụng ý tưởng của thuật toán Bresenham, xây dựng thuật toán vẽ đường tròn có tâm là gốc tọa 
độ, bán kính R. 
9. Giải thích tại sao chỉ chọn cung 1/8 để vẽ rồi lấy đối xứng mà không mở rộng cho cung 1/16 hay 
1/32. 
10. Giải thích tại sao có thể thay công thức p0 = 5/4 - R bằng công thức p0 = 1- R khi cài đặt thuật toán 
MidPoint vẽ đường tròn. 
11. Trình bày thuật toán Bresenham vẽ đường tròn bán kính R, từ đó nhận xét về cách tiếp cận của 
thuật toán MidPoint có gì lợi hơn so với thuật toán Bresenham. 
12. Xây dựng và cài đặt thuật toán vẽ ellipse có tâm là gốc tọa độ với bán kính trục chính, bán kính 
trục phụ lần lượt là A, B. 
13. Dựa vào thuật toán vẽ đường tròn để xây dựng thủ tục vẽ một cung tròn (arc) tâm (x,y) bán kính R, 
biết góc bắt đầu và kết thúc của cung lần lượt là α, β.. 
14. Dựa vào thuật toán vẽ ellipse để xây dựng thủ tục vẽ một cung (pie slice) tâm (x,y) và bán kính 
trục chính, trục phụ lần lượt là A, B, góc bắt đầu và kết thúc của cung lần lượt là α, β. 
15. Hãy tìm hiểu các cài đặt tối ưu hơn cho các thuật toán vẽ đoạn thẳng và vẽ đường tròn, ellipse. 
16. Xây dựng và cài đặt thuật toán vẽ các parabol 
A
xy
2
= , và Axy =2 với A là số nguyên bất kì. 
17. Xây dựng và cài đặt thuật toán vẽ các hyperbol 12
2
2
2
=−
B
y
A
x , và 12
2
2
2
−=−
B
y
A
x với A, B là các 
số nguyên bất kì. 
18. Xây dựng và cài đặt thuật toán vẽ các đường cong sau : 
• )sin( θω += xAy , với A nguyên. 
• )cos( θω += xAy , với A nguyên. 
• 2Axy = , với A nguyên. 
• Axy /3= , với A nguyên. 
• 042422 =−+++ yxyx 
• 021618259 22 =−−+ xyx 
• 0100100 2 =−+ xxy 
• 07425 =−−+ yxxy 
• 0250025100 22 =+− yx 
19. Các bước chính của các thuật toán vẽ đường dạng ( )xfy = . Minh họa cho các trường hợp vẽ 
đường thẳng, đường tròn. 
20. Bản chất của quá trình vẽ các đường đơn giản theo từng điểm là rời rạc hóa và nguyên hóa. Hãy 
cho biết lí do tại sao, bước nào trong thuật toán tổng quát thể hiện hai ý trên. Minh họa bằng các 
đường đã học. 
21. Các thuật toán vẽ đường bao hàm rất lớn kĩ thuật tối ưu hóa chương trình. Hãy minh họa qua các 
đối tượng đã học. 
22. Ý nghĩa của danh sách kích hoạt AET trong thuật toán tô màu đa giác theo dòng quét. Cấu trúc dữ 
liệu và nguyên tắc hoạt động của AET. 
23. Cài đặt thuật toán tô màu đa giác theo dòng quét bằng cách dùng xâu liên kết thay vì dùng mảng 
như cài đặt minh họa. 
24. Cài đặt thuật toán tô màu theo đường biên không dùng đệ quy. 
25. Xây dựng và cài đặt thuật tô màu đường tròn, ellipse.