NỘI DUNG
1 Vẽ đường thẳng a Thuật toán Bressenham
Thuật toán Bresenham xác định cách chọn điểm y tiếp theo, có thể là yi hoặc yi + 1, bằng cách so sánh khoảng cách giữa điểm thực y với hai điểm lân cận Điểm nào gần với điểm thực hơn sẽ được chọn làm điểm vẽ tiếp theo.
Gọi y là giá trị thực (giá trị chính xác) của đường thẳng tại x ở bước thứ i +
Gọi d 1 là khoảng cách từ y đến y i
Gọi d 2 là khoảng cách từ y đến y i + 1
ĐỒ HỌA HAI CHIỀU
Vẽ đường thẳng
Thuật toán Bresenham xác định điểm y i + 1 bằng cách so sánh khoảng cách giữa điểm thực y và hai điểm lân cận Điểm nào gần với điểm thực hơn sẽ được chọn làm điểm vẽ tiếp theo.
Gọi y là giá trị thực (giá trị chính xác) của đường thẳng tại x ở bước thứ i +
Gọi d 1 là khoảng cách từ y đến y i
Gọi d 2 là khoảng cách từ y đến y i + 1
Để thực hiện phép toán với số thực m = d1 - d2, ta cần khử phân số bằng cách nhân cả hai vế với dx Do đó, ta đặt Pi = dx(d1 - d2).
Thay vào phương trình trên ta được:
P i = 2dyx i – 2dxy i + c với c = 2dy + (2b - 1)dx Mặt khác dx ≥ 0 với mọi trường hợp
⇨ dấu của P i cùng dấu với d 1 – d 2
Giả sử khoảng cách giữa hai điểm y i + 1 và y i là p Khi x tăng thêm 1 đơn vị, khoảng cách p sẽ cộng thêm một giá trị c Tuy nhiên, sự gia tăng của khoảng cách p không diễn ra theo cách tuyến tính, do đó, cần tìm một công thức tổng quát cho các trường hợp, cụ thể là P i + 1 = ? P i.
Hình 1.6 Thuật toán Midpoint đưa ra cách chọn điểm y i + 1 là y i hay y i + 1 bằng cách so sánh điểm thực Q(x i + 1 , y) với điểm Midpoint là trung điểm của S và
P Nếu điểm Q nằm dưới điểm Midpoint thì ta chọn điểm S là điểm vẽ tiếp theo Ngược lại, nếu điểm Q nằm trên điểm Midpoint thì ta chọn P Ta có dạng tổng quát của PT đường thẳng:
Vị trí tương đối của điểm Midpoint (x, y) với đường thẳng:
+ F(x, y) < 0 nếu (x, y) nằm phía trên đường thẳng
+ F(x, y) = 0 nếu (x, y) thuộc về đường thẳng
+ F(x, y) > 0 nếu (x, y) nằm phía dưới của đường thẳng Lúc này việc chọn các điểm S, P ở trên được đưa về việc xét dấu của p i + 1 – p i = 2F(x i + 1 + 1, y i + 1 + ) – 2F(x i + 1, y i + )
Vậy p i + 1 = p i + 2Dy nếu p i < 0 do ta chọn y i + 1 = y i p i + 1 = p i + 2Dy – 2Dx nếu p i ≥ 0 do ta chọn y i + 1 = y i + 1
Ta tính giá trị p 1 ứng với điểm ban đầu (x 1 , y 1 ) với nhận xét rằng điểm
(x 1 , y 1 ) là điểm thuộc đường thẳng, tức là có Ax 1 + By 1 + C = 0 p ⇨ 1 = 2F(x 1 + 1, y 1 + ) = 2[A(x 1 + 1) + B(y 1 + ) + C] ⇨ p 1 = 2(Ax 1 + By 1 + C) + 2A + B p = 2A + B
Ta thấy kết quả của thuật toán Midpoint tương tự thuật toán Bresenham như đã nói ở trên.
Giống của thuật toán Bresenham
Vẽ đường tròn
Giả sử (x i , y i ) đã vẽ được, điểm kế tiếp là (x i + 1, y i ) hoặc (x i +1, y i -1)
Hình 1.10 là: Từ phương trình: x 2 + y 2 = R 2 ta tính được giá trị y thực ứng với x i + 1 y 2 = R 2 - (x i + 1) 2 Đặt: d 1 = y i 2 - y 2 = y i 2 - R 2 + (x i + 1) 2 d 2 = y 2 - (y i - 1) 2 = R 2 - (x i + 1) 2 - (y i - 1) 2
Nếu : chọn p i ≥ 0 y i + 1 = y i –1 (4) ⇒ p i + 1 = p i + 4(x i - y i ) + 10 Ta chọn điểm đầu tiên cần vẽ (0, R), (2) ta có: p 1 = 3 - theo
Tóm lại: Ta có thuật toán vẽ đường tròn:
• Bước 1: Chọn điểm đầu tiên cần vẽ (x 1 , y 1 ) = (0, R)
• Bước 2: Tính P đầu tiên: p 1 = 3 - 2R Nếu p < 0: chọn điểm kế tiếp là (x i +1, y i ) Ngược lại chọn ủiểm (x i + 1,y i - 1)
Ngược lại: p i + 1 = p i + 4(x i - y i ) + 10 Khi đó: Nếu p i + 1 < 0: chọn điểm kế tiếp là(x i + 1 , y i + 1 ) Ngược lại chọn điểm (x i + 1 , y i + 1 -1)
• Bước 4: Lặp lại bước 3 cho đến khi x = y.
Thuật toán Đường tròn có tâm O(xc, yc) = (0, 0), bán kinh r có phương trình: x 2 + y 2 = r 2 => x 2 + y 2 - r 2 = 0 Đặt f(x, y) = x 2 + y 2 - r 2
Với mọi điểm P(x, y) nằm trong hệ tọa độ Oxy, ta có:
P(x, y) nằm trên đường tròn O nếu f(x, y) = 0
P(x, y) nằm ngoài đường tròn O nếu f(x, y) > 0
P(x, y) nằm trong đường tròn O nếu f(x, y)< 0
Đường tròn có tính đối xứng qua các cung 1/8, cho phép xác định tọa độ (x, y) của một điểm thuộc cung đó.
Trong cung 1/8 thứ nhất do khoảng biến thiên của x lớn hơn khoảng biến thiên của y, nên xi+1 = xi + 1.
Giả sử ta đã vẽ được (Xi, Yi) ở bước thứ i, ta cần xác định (Xi+1, Yi+1) ở bước thứ i + 1.
Ta có hình như sau:
Hình 1.15 Tính F i Đặt Fi = F(X, Y - 1/2), ta hình có công thức:
Nếu Fi >= 0 (Xi + 1, Y) gần với Yi - 1 => Yi + 1 = Yi -1
Fi + 1 - Fi = 2Xi + 3 + (Yi+12 - Yi2) + (Yi+1 - Yi) (*)
Nếu Fi < 0 thì Fi + 1 = Fi + 2Xi + 3, do ta thay thế Yi+1 = Yi vào (*)
Nếu Fi >= 0 thì Fi + 1 = Fi + 2(Xi - Yi) + 5, do thay thế Yi+1 = Yi -1 vào (*) Tính giá trị F đầu tiên
Thay Xi = 0 và Yi = R trong công thức trên ta có được: F = 5/4 - R
Thuật Toán Tô Màu Tràn
Đường biên trong thuật toán tô loang được xác định bởi tập hợp các đỉnh của một đa giác, với màu sắc của tất cả các điểm trên đường biên được biểu thị bằng một giá trị duy nhất Bắt đầu từ một điểm nằm trong vùng tô, thuật toán kiểm tra các điểm lân cận để xác định xem chúng đã được tô màu hay là điểm biên Nếu điểm lân cận không phải là điểm đã tô hoặc điểm biên, nó sẽ được tô màu Quá trình này lặp lại cho đến khi không còn điểm nào có thể tô thêm.
Hình 1.19 -Bước 1: Kẻ vùng biên cần tô.
-Bước 2: Xác định một điểm (x,y) bên trong vùng cần tô.
-Bước 3: Tô điểm (x,y) sau đó tô loang những điểm lân cận.
Thuật toán tô màu theo đường quét
Mỗi dòng quét sẽ xác định phần giao của đa giác và dòng quét, sau đó tô màu các pixel thuộc đoạn giao đó Để tìm các đoạn giao, ta xác định giao điểm giữa dòng quét và các cạnh của đa giác, sau đó sắp xếp các giao điểm theo thứ tự tăng dần của hoành độ Các đoạn giao được hình thành bởi từng cặp giao điểm.
Để tìm ymin và ymax, ta xác định giá trị nhỏ nhất và lớn nhất trong tập hợp các tung độ của các đỉnh của đa giác đã cho Với mỗi dòng quét y = k, trong khoảng từ ymin đến ymax, ta thực hiện lặp để xử lý các giá trị tương ứng.
Tìm tất cả các hoành độ giao điểm của dòng quét y = k với các cạnh của đa giác.
Sắp xếp các hoành độ giao điểm theo thứ tự tăng dần : x 0 ,x 1 , , x n ,
Tô màu các đoạn thẳng trên đường thẳng y = k lần lượt được giới hạn bởi các cặp (x 0 , x 1 ), ( x 1 ,x 2 ), , x 2k , x 2k+1 ).
Nếu chỉ dừng lại ở việc cài đặt mà không cải tiến, chúng ta sẽ gặp phải một số vấn đề Cụ thể, không phải tất cả các cạnh của đa giác đều cắt qua mỗi dòng quét, dẫn đến việc cần tìm giao điểm sẽ trở nên tốn thời gian Do đó, để tăng tốc độ, cần thiết phải tìm ra phương pháp hạn chế số lượng cạnh cần xác định giao điểm cho mỗi dòng quét.
Việc xác định giao điểm giữa các cạnh của đa giác và dòng quét đòi hỏi các phép toán phức tạp như nhân và chia trên số thực, dẫn đến giảm tốc độ thuật toán Nếu số giao điểm giữa các cạnh và dòng quét là lẻ, việc nhóm các cặp giao điểm liên tiếp để tạo thành các đoạn tô có thể không chính xác, đặc biệt khi dòng quét đi qua các đỉnh của đa giác.
Việc xác định giao điểm của dòng quét với các cạnh ngang là một trường hợp đặc biệt cần xử lý thích hợp Để giảm số lượng cạnh cần tìm giao điểm, ta áp dụng công thức hệ số góc: x k+1 = x k + 1/m, với m là hệ số góc của cạnh và x k+1, x k lần lượt là hoành độ giao điểm của một cạnh với dòng quét y=k và y=k+1 Khi tính số giao điểm qua đỉnh đơn điệu, ta xác định là 1, còn qua đỉnh cực trị thì tính là 0 hoặc 2.
Phát Triển Ứng dụng Đồ Họa 2D
Phát biểu bài toán
Dựa trên kiến thức về Đồ Họa 2 chiều, nhóm chúng tôi đã phát triển một ứng dụng mô phỏng bàn cờ 2D sử dụng thư viện đồ họa Graphics Chúng tôi áp dụng thuật toán Bressenham để vẽ đường thẳng, từ đó tạo nên hình ảnh bàn cờ một cách chính xác và hiệu quả.