Bài giảng Đồ họa Raster - Chương 1, Phần 1: Các thuật toán vẽ đường thẳng - Bùi Tiến Liên

Nội dung text: Bài giảng Đồ họa Raster - Chương 1, Phần 1: Các thuật toán vẽ đường thẳng - Bùi Tiến Liên

1. ĐỒ HỌA RASTER CÁC THUẬT TỐN VẼ ĐƯỜNG THẲNG Giảng viên : Bùi Tiến Lên
2. Bài tố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 (X2, Y2) (X1, Y1) Trang 2
3. Bài tốn vẽ đường thẳng Trang 3
4. Một số cơng thức cơ bản của đường thẳng (X2, Y2) y = mx + b y b x = − m m Y − Y y m = 2 1 = X2 − X1 x b = Y1 − mX1 (X1, Y1) Trang 4
5. Phân loại đường thẳng Tăng chậm Tăng nhanh Giảm chậm Giảm nhanh Trang 5
6. Giải quyết Thuật tốn DDA Thuật tốn Bresenham Trang 6
7. Thuật tốn DDA
8. Thuật tốn DDA Trang 8
9. Trường hợp 1 Đoạn thẳng tăng chậm và điểm đầu ở bên trái. Thuật tốn Bước 1 Xác định điểm đầu tiên 1 x1 = X1 y1 = Y1 Bước 2 Xác định những điểm tiếp theo 2 3 n Lặp xi < X2 xi+1 = xi + 1 y = mxi+1 + b yi+1 = Round(y) Trang 9
10. Trường hợp 1 Cải tiến tính y Xét hai điểm sáng liên tiếp nhau i (xi, ycũ) i+1 (xi+1, ymới) Cơng thức liên hệ y đầu là Y1 ymới = ycũ + m Trang 10
11. Trường hợp 2 Đoạn thẳng tăng nhanh và điểm đầu ở bên dưới. Thuật tố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 < Y2 yi+1 = yi + 1 x = yi+1/m – b/m xi+1 = Round(x) Trang 11
12. Trường hợp 2 Cải tiến tính x Xét hai điểm sáng liên tiếp nhau i (xc, yi) i+1 (xmới, yi+1) Cơng thức liên hệ X − X k = 2 1 Y2 − Y1 x đầu là X1 xmới = xcũ + k Trang 12
13. Thuật tốn Bresenham
14. Trường hợp 1 Dự đốn điểm sáng thứ i+1 B i A Trang 14
15. Trường hợp 1 Xây dựng biến pi yi+1 B y = m(xi+1) + b d2 d1 = y - yi y d2 = yi + 1 - y C p = x(d - d ) i 1 2 d1 yi i A xi xi+1 Trang 15
16. Trường hợp 1 Cách tính pi pi = 2 yxi – 2 xyi + 2 xY1 – 2 yX1 + 2 y – x Trang 16
17. Trường hợp 1 Đoạn thẳng tăng chậm và điểm đầu ở bên trái. Thuật tố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 17
18. 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 18
19. Trường hợp 2 Dự đốn điểm sáng thứ i+1 A B i Trang 19
20. Trường hợp 2 Xây dựng biến p C i yi+1 A B y + 1 b x = i − m m d d1 = xi − x d1 2 d2 = xi + 1− x pi = y(d1 − d2 ) yi i xi x xi+1 Trang 20
21. Trường hợp 2 Cách tính pi p1 = 2 x - y pi = 0 : pi+1 = pi + 2 x - 2 y Trang 21
22. Trường hợp 2 Thuật tố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 22