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

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.
Nội dung trích xuất từ tài liệu:
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 RASTERCÁC THUẬT TOÁNVẼ ĐƯỜNG THẲNG Giảng viên : Bùi Tiến LênBài toán vẽ đường thẳngInput (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 2Bài toán vẽ đường thẳng Trang 3Mộ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 4Phân loại đường thẳng Tăng chậm Tăng nhanh Giảm chậm Giảm nhanh Trang 5Giải quyếtThuật toán DDAThuật toán Bresenham Trang 6Thuật toán DDAThuật toán DDA Trang 8Trường hợp 1Đoạn thẳng tăng chậm và điểm đầu ở bên trái.Thuật toánBước 1 Xác định điểm đầu tiên 1 x1 = X1 y1 = Y1Bước 2 Xác định những điểm tiếp theo 2 3 … nLặp xi < X2 xi+1 = xi + 1 y = mxi+1 + b yi+1 = Round(y) Trang 9Trường hợp 1Cải tiến tính yXé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 10Trường hợp 2Đoạn thẳng tăng nhanh và điểm đầu ở bên dưới.Thuật toánBước 1 Xác định điểm đầu tiên x1 = X1 y1 = Y1Bước 2 Xác định những điểm tiếp theoLặp yi < Y2 yi+1 = yi + 1 x = yi+1/m – b/m xi+1 = Round(x) Trang 11Trường hợp 2Cải tiến tính xXé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 12Thuật toán BresenhamTrường hợp 1Dự đoán điểm sáng thứ i+1 B i A Trang 14Trường hợp 1Xâ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 15Trường hợp 1Cách tính pi pi = 2∆yxi – 2∆xyi + 2∆xY1 – 2∆yX1 + 2∆y – ∆x Trang 16Trường hợp 1Đoạn thẳng tăng chậm và điểm đầu ở bên trái.Thuật toánBước 1 Xác định điểm đầu tiên x1 = X1 y1 = Y1Bước 2 Xác định những điểm tiếp theoLặp xi < X2 pi = … pi < 0 xi+1 = xi + 1 yi+1 = yi pi >= 0 xi+1 = xi + 1 yi+1 = yi + 1 Trang 17Trường hợp 1Cá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 18Trường hợp 2Dự đoán điểm sáng thứ i+1 A B i Trang 19Trường hợp 2Xaâ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