Bài giảng Đồ họa raster: Các thuật toán vẽ đường thẳng có nội dung trình bày bài toán vẽ đường thẳng, một số công thức cơ bản của đường thẳng, phân loại đường thẳng, thuật toán DDA, thuật toán Bresenham và các bài tập áp dụng minh họa cho các nội dung trên. | ĐỒ HỌA RASTER CÁC THUẬT TOÁN VẼ ĐƯỜNG THẲNG Giảng viên : Bùi Tiến Lên Trang Bài toán vẽ đường thẳng Input (X1, Y1) (X2, Y2) Output {(x1, y1) (x2, y2) (xn, yn)} là những điểm sáng “nằm trên” đường thẳng Bài toán vẽ đường thẳng Trang Trang Một số công thức cơ bản của đường thẳng (X1, Y1) (X2, Y2) Trang Phân loại đường thẳng Tăng chậm Tăng nhanh Giảm chậm Giảm nhanh Trang Giải quyết Thuật toán DDA Thuật toán Bresenham Thuật toán DDA Thuật toán DDA Trang Trang Trường hợp 1 Đoạn thẳng tăng chậm và điểm đầu ở bên trái. Thuật toán Bước 1 Xác định điểm đầu tiên x1 = X1 y1 = Y1 Bước 2 Xác định những điểm tiếp theo Lặp xi Trang Trường hợp 1 Cải tiến tính y Xét hai điểm sáng liên tiếp nhau Công thức liên hệ i i+1 (xi, ycũ) (xi+1, ymới) y đầu là Y1 ymới = ycũ + m Trang Trường hợp 2 Đoạn thẳng tăng nhanh và điểm đầu ở bên dưới. Thuật toán Bước 1 Xác định điểm đầu tiên x1 = X1 y1 = Y1 Bước 2 Xác định những điểm tiếp theo Lặp yi Trang Trường hợp 2 Cải tiến tính x Xét hai điểm sáng liên tiếp nhau Công thức liên hệ i i+1 (xc, yi) (xmới, yi+1) x đầu là X1 xmới = xcũ + k Thuật toán Bresenham Trang Trường hợp 1 Dự đoán điểm sáng thứ i+1 i A B Trang Trường hợp 1 Xây dựng biến pi y = m(xi+1) + b d1 = y - yi d2 = yi + 1 - y pi = x(d1 - d2) i A B xi xi+1 yi+1 yi y C d2 d1 Trang Trường hợp 1 Cách tính pi pi = 2 yxi – 2 xyi + 2 xY1 – 2 yX1 + 2 y – x Trang Trường hợp 1 Đoạn thẳng tăng chậm và điểm đầu ở bên trái. Thuật toán Bước 1 Xác định điểm đầu tiên x1 = X1 y1 = Y1 Bước 2 Xác định những điểm tiếp theo Lặp xi = 0 xi+1 = xi + 1 yi+1 = yi + 1 Trang Trường hợp 1 Cách tính pi cải tiến p1 = 2 y - x pi = 0 : pi+1 = pi + 2 y - 2 x Trang Trường hợp 2 Dự đoán điểm sáng thứ i+1 i A B Trang Trường hợp 2 i A B xi xi+1 yi+1 yi x C d2 d1 Trang Trường hợp 2 Cách tính pi p1 = 2 x - y pi = 0 : pi+1 = pi + 2 x - 2 y Trang Trường hợp 2 Thuật toán Bước 1 Xác định điểm đầu tiên x1 = X1 y1 = Y1 Bước 2 Xác định những điểm tiếp theo Lặp xi = 0 xi+1 = xi + 1 yi+1 = yi + 1 | ĐỒ HỌA RASTER CÁC THUẬT TOÁN VẼ ĐƯỜNG THẲNG Giảng viên : Bùi Tiến Lên Trang Bài toán vẽ đường thẳng Input (X1, Y1) (X2, Y2) Output {(x1, y1) (x2, y2) (xn, yn)} là những điểm sáng “nằm trên” đường thẳng Bài toán vẽ đường thẳng Trang Trang Một số công thức cơ bản của đường thẳng (X1, Y1) (X2, Y2) Trang Phân loại đường thẳng Tăng chậm Tăng nhanh Giảm chậm Giảm nhanh Trang Giải quyết Thuật toán DDA Thuật toán Bresenham Thuật toán DDA Thuật toán DDA Trang Trang Trường hợp 1 Đoạn thẳng tăng chậm và điểm đầu ở bên trái. Thuật toán Bước 1 Xác định điểm đầu tiên x1 = X1 y1 = Y1 Bước 2 Xác định những điểm tiếp theo Lặp xi Trang Trường hợp 1 Cải tiến tính y Xét hai điểm sáng liên tiếp nhau Công thức liên hệ i i+1 (xi, ycũ) (xi+1, ymới) y đầu là Y1 ymới = ycũ + m Trang Trường hợp 2 Đoạn thẳng tăng nhanh và điểm đầu ở bên dưới. Thuật toán Bước 1 Xác định điểm đầu tiên x1 = X1 y1 = Y1 Bước 2 Xác .
