NỘI DUNG
1 Vẽ đường thẳng a Thuật toán Bressenham
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ớ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, giúp tối ưu hóa quá trình vẽ đường thẳng.
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 quyết định chọn điểm y i + 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
Để thực hiện phép toán với số thực m = d1 – d2, ta cần tuân thủ nguyên tắc chỉ sử dụng số nguyên Để khử phân số, ta nhân cả hai vế với dx, từ đó đặt P i = dx(d1 – d2).
Thay m = 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
Ta lại có: P i + 1 = 2dyx i + 1 – 2dxy i + 1 + c
Giả sử khoảng cách giữa các điểm y i và y i + 1 là p Khi xem xét việc chọn điểm trên hay điểm dưới gần với điểm thực hơn, mỗi 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, khoảng cách p không tăng lên theo cách tuyến tính, do đó chúng ta cần tìm ra công thức tổng để mô tả mối quan hệ này.
Thuật toán Midpoint giúp xác định điểm tiếp theo 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 giữa S và P Nếu Q nằm dưới Midpoint, ta chọn S làm điểm vẽ tiếp theo; ngược lại, nếu Q nằm trên Midpoint, ta chọn P Dạng tổng quát của phương trình đường thẳng cũng được áp dụng trong thuật toán này.
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]
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ử (xi, yi) đã vẽ được, điểm kế tiếp là (xi + 1, yi) hoặc (xi +1, yi -1)
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 là: 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 p i ≥ 0: chọn 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), theo (2) ta có: p 1 = 3 - 2R
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 điểm 1/8, cho phép xác định tọa độ của 7 điểm khác tương ứng với một điểm có tọa độ (x, y) thuộc một cung nào đó.
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 Fi Đặ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
Thuật toán Đường biên trong thuật toán tô loang xác định bởi tập hợp các đỉnh của đa giác, với đường biên được mô tả bằng màu sắc duy nhất Bắt đầu từ một điểm bên 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 hoặc là điểm biên hay chưa Nếu điểm lân cận không được tô và không phải là đ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ô được.
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 lần quét, chúng ta xác định phần giao giữa dòng quét và đa giác, sau đó tô màu các pixel trong đoạn giao đó Để tìm các đoạn giao, cần 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 từ các đoạn thẳng được giới hạn bởi từng cặp giao điểm.
Tìm ymin và ymax là xác định giá trị nhỏ nhất và lớn nhất của tập hợp các tung độ tại các đỉnh của đa giác đã cho Đối với mỗi giá trị y = k trong khoảng từ ymin đến ymax, thực hiện lặp lại các bước cần thiết.
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 : x0 ,x1 , , xn ,
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 (x0, x1), ( x1 ,x2), , x2k, x2k+1).
Nhưng nếu chỉ dừng ở mức này và chuyển sang cài đặt thì chúng ta sẽ gặp phải một số vấn đề như sau:
Để tối ưu hóa tốc độ trong quá trình quét, cần hạn chế số lượng cạnh của đa giác cần tìm giao điểm cho mỗi dòng quét, vì không phải tất cả các cạnh đều cắt dòng quét.
Việc xác định giao điểm giữa các cạnh của đa giác và các dòng quét thường gặp phải các phép toán phức tạp như nhân và chia trên số thực Sử dụng phương pháp giải hệ phương trình để tìm giao điểm có thể làm giảm tốc độ của thuật toán.
Nếu số giao điểm giữa các cạnh của đa giác và dòng quét là lẻ, việc nhóm các giao điểm liên tiếp để tạo thành các đoạn tô có thể không chính xác Tình huống này xảy ra 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 nằm ngang là một trường hợp đặc biệt cần xử lý một cách thích hợp Để giảm thiểu số lượng cạnh cần tìm giao điểm, ta áp dụng công thức hệ số góc: xk+1 = xk + 1/m, trong đó m là hệ số góc của cạnh; xk+1 và xk 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 Đối với trường hợp giao điểm đi qua đỉnh đơn điệu, ta xác định số giao điểm là 1, còn với đỉnh cực trị, số giao điểm được 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ẽ các đường thẳng, từ đó tạo ra bàn cờ một cách chính xác và hiệu quả.
