Một số thuật toán đồ họa cơ bản I. Vẽ đoạn thẳng Xét đoạn thẳng y = +b có hệ số góc 00. Làm sao để vẽ đoạn thẳng nối (x1,y1) (x2,y2) trong khi ta chỉ có thể ra lệnh cho màn hình vẽ từng điểm ảnh (kiểư như PutPixel của TP)? Làm sao vẽ đoạn thẳng nối 2 điểm này | Đồ họa máy tính - Khoa CNTT - ĐHSPHN Chương III Một số thuật toán đồ họa cơ bản I. Vẽ đoạn thẳng Xét đoạn thẳng y b có hệ số góc 0 m 1 ta chọn điểm đầu và điểm cuối sao cho dx x2-x1 0. Làm sao để vẽ đoạn thẳng nối x1 y1 x2 y2 trong khi ta chỉ có thể ra lệnh cho màn hình vẽ từng điểm ảnh kiểư như PutPixel của TP Bản chất của quá trình này là sự rời rạc hóa và nguyên hóa một đối tượng thực ở đây là đoạn thẳng thực - đoạn thẳng toán học trên màn hình sao cho cuối cùng ta có tập các Pixel trông giống đối tượng nhất. Bản chất của các thuật toán vẽ đoạn thẳng là đi tìm tập các pixel liền nhau sao cho trông chúng giống với đoạn thẳng thực nhất Thế nào là giống - Liên tục không đứt đoạn - Gần với đoạn thẳng thực đoạn thẳng toán học nhất Hơn nữa còn vấn đề tối ưu tốc độ nghĩa là thuật toán phải tô các pixel trong thời gian nhanh nhất Bài toán ta phải vẽ đoạn thẳng y b có hệ số góc 0 m 1 dx 0 các trường hợp khác đều có thể quy về trường hợp này Đầu tiên ta nhận xét với các đoạn thẳng dạng này nếu xi yi là điểm ảnh đã vẽ được ở bước thứ i điểm màu đen thì - chắc chắn xi 1 xi 1 - yi 1 yi hoặc yi 1 yi 1 do đó điểm ảnh ở bước i 1 tiếp theo chỉ có thể là 1 trong 2 trường hợp như hình vẽ. Vấn đề quy về việc chọn điểm nào trong hai điểm đó. http www. 39 Đồ họa máy tính - Khoa CNTT - ĐHSPHN 1. Thuât toán DDA vẽ đoạn thẳng Việc quyết định chọn yi 1 là yi hay yi 1 dựa vào phương trình của đoạn thẳng thực. Ta sẽ tính tọa độ của điểm y m xi 1 b thuộc về đoạn thẳng thực sau đó chọn điểm nào gần với nó nhất trong 2 điểm nghĩa là yi 1 round y round 1 b Như vây sẽ tốn 1 phép nhân và 1 phép cộng số thực. Để cải thiện tốc độ người ta dùng cách sau để khử phép nhân. Nhân xét rằng yi b yi 1 1 b yi 1 yi m Ví dụ Cho A 12 20 và B 22 27 ta có m http www. 40 Đồ họa máy tính - Khoa CNTT - ĐHSPHN i Xi yi y 0 12 20 20 1 13 21 2 14 21 3 15 22 4 16 23 5 17 24 6 18 24 7 19 25 8 20 26 9 21 26 10 22 27 27 Thuật
