Thuật toán vẽ đoạn thẳng

Dẫn nhập Các thuật toán vẽ các đối tượng đồ hoạ cơ sở như: điểm, đường, đa giác, …, phụ thuộc nhiều vào thiết bị hiển thị Hầu hết các ứng dụng đồ họa đều sử dụng các công cụ vẽ này làm nền tảng Bút trong máy vẽ được di chuyển nhờ một motor bước, nên nó chỉ có thể di chuyển tới những vị trí rời rạc. Cách biểu diễn tọa độ Vẽ đoạn thẳng Trong đồ hoạ vector 1. Di chuyển tới điểm đầu 2. Bật chùm tia điệntử 3. Di chuyển tới điểmcuối 4. Tắt chùm tia điệntử Trong đồ hoạ Raster-scan, vẽ đường chuyển thành vẽ nối từng điểm ảnh Chùm điệntử di chuyển theo hướng xác định (trái qua phải, trên xuống dưới) Vùng đệm màn hình lưutrữ thông tin của điểm ảnh tương ứng (cường độ sáng, màu, …) Yêu cầu Đoạnthẳng lý tưởng Ideal line Rasterized line Các điểm ảnh phải càng gần đoạn thẳng lý tưởng càng tốt Độ dày, độ sáng đều nhau Các điểm ảnh phải liên tục không ngắt discontinuities (gaps in the line) Tốc độ vẽ nhanh nhất có thể, vì vẽ đoạn thẳng là thao tác cơ bản trong tất cả các hệ đồ họa Phương trình đoạn thẳng Thuật toán Slope-Intercept Trường hợp lỗi? Thuật toán thực hiện lặp theo trục x, nên khi đoạn thẳng có hệ số góc lớn hơn 1 thì các điểm ảnh sẽ trở nên ngắt quãng Sửa lỗi? Kiểm tra hệ số góc m. Nếu m > 1 thì thực hiện lặp theo trục y (hoán đổivai trò x với y) Thuật toán Slope-Intercept Thuật toán Slope-Intercept (tt.) Đánh giá, cải tiến? Thuật toán DDA – Digita Differential Analyzer Yêu cầu khác Tốc độ nhanh hơnnếu không sử dụng các phép toán trên số thực Các điểm đầu, cuốicủa đoạnthẳng nằm ngoài khung nhìn? Hạn chế sự lởm chởm răng cưa của đoạn thẳng Độ dày của đoạn thẳng (>1)? Kiểu đoạnthẳng? Ý tưởng của thuật toán Lưu đồ Thuật toán Bresenham Thuật toán Bresenham Thuật toán Bresenham (tt.) Một thuật toán đơn giản Kết quả Hệ số góc của các điểm trên đường tròn thay đổi. Khi nó lớn hơn 1 sẽ dẫn tới các điểm ảnh trên đường tròn không liên tục Các điểm ảnh trên đường tròn có tính chất đối xứng qua tâm Tính đối xứng của đường tròn Đối xứng 8 hướng? Một điểm ảnh (x,y) của đường tròn tâm tại gốc toạ độ có 3 điểm ảnh đối xứng qua trục hoành và trục tung là (-x,y), (x,-y) và (-x,-y) Và 4 điểm đối xứng qua đường phân giác (y,x), (-y,x), (y,-x), (-y,-x) Tăng tốc độ vẽ gấp 8 lần Chương trình cải tiến Chương trình cải tiến (tt.) Kết quả Tốc độ vẽ được cải thiện Loại bỏ được sự không liên tục của các điểm ảnh trên đường tròn Tuy nhiên vẫn còn tốn nhiều thời gian tính toán các phép: +,-,*, lấy căn trên số thực Thuật toán MidPoint vẽ đường tròn Lưu đồ Thuật toán MidPoint Thuật toán vẽ đường tròn MidPoint Thuật toán vẽ đường tròn MidPoint (tt.) circlePoints Ý tưởng vẽ các đường cong conic