Bài giảng Đồ họa raster: Các thuật toán vẽ đường thẳng - Bùi Tiến Lên

Chia sẻ: Na Na | Ngày: | Loại File: PPT | Số trang:22

Thêm vào BST

Báo xấu

189
lượt xem 25
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Đồ họa raster: Các thuật toán vẽ đường thẳng - Bùi Tiến Lên

ĐỒ HỌA RASTER CÁC THUẬT TOÁN VẼ ĐƯỜNG THẲNG Giảng viên : Bùi Tiến Lên
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 (X 2 , Y 2 ) (X 1 , Y 1 ) Trang 2
Bài toán vẽ đường thẳng Trang 3
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 Y2 − Y1 ∆y m= = X 2 − X1 ∆x b = Y1 − mX1 (X1, Y1) Trang 4
Phân loại đường thẳng Tăng chậm Tăng nhanh Giảm chậm Giảm nhanh Trang 5
Giải quyết Thuật toán DDA Thuật toán Bresenham Trang 6
Thuật toán DDA
Thuật toán DDA Trang 8
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 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
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
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 < Y2 yi+1 = yi + 1 x = yi+1/m – b/m xi+1 = Round(x) Trang 11
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 2 − X1 k= Y2 − Y1 x đầu là X1 xmới = xcũ + k Trang 12
Thuật toán Bresenham
Trường hợp 1 Dự đoán điểm sáng thứ i+1 B i A Trang 14
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 d1 pi = ∆x(d1 - d2) yi i A xi xi+1 Trang 15
Trường hợp 1 Cách tính pi pi = 2∆yxi – 2∆xyi + 2∆xY1 – 2∆yX1 + 2∆y – ∆x Trang 16
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 < X2 pi = … pi < 0 xi+1 = xi + 1 yi+1 = yi pi >= 0 xi+1 = xi + 1 yi+1 = yi + 1 Trang 17
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 pi >= 0 : pi+1 = pi + 2∆y - 2∆x Trang 18
Trường hợp 2 Dự đoán điểm sáng thứ i+1 A B i Trang 19
Trường hợp 2 Xaây döïngbieán i p C yi+1 A B yi + 1 b x= − m m d1 = xi − x d1 d2 d2 = xi + 1− x pi = ∆y( d1 − d2 ) yi i xi x xi+1 Trang 20