Đồ họa máy tính - Chương 3: Một số thuật toán đồ họa cơ bản

Một số thuật toán đồ họa cơ bản I. Vẽ đoạn thẳngXét đoạn thẳng y = m.x +b có hệ số góc 00. Làm sao để vẽ đoạn thẳng nối (x1,y1) (x2,y2) trong khi ta chỉ có thể ra lệnh cho màn hình vẽ từng điểm ảnh (kiểư như PutPixel của TP)? Làm sao vẽ đoạn thẳng nối 2 điểm này
Nội dung trích xuất từ tài liệu:
Đồ họa máy tính - Chương 3: Một số thuật toán đồ họa cơ bảnĐồ họa máy tính - Khoa CNTT - ĐHSPHN Chương III: Một số thuật toán đồ họa cơ bảnI. Vẽ đoạn thẳngXét đoạn thẳng y = m.x +b có hệ số góc 0Đồ họa máy tính - Khoa CNTT - ĐHSPHN1. Thuật toán DDA vẽ đoạn thẳng Việc quyết định chọn yi+1 là yi hay yi+1 dựa vào phương trình của đoạn thẳng thực. (xi+1, round(y)) y (xi , yi) (xi+1, y)Ta sẽ tính tọa độ của điểm y = m (xi +1) + b thuộc về đoạn thẳng thực, sau đó chọn điểmnào gần với nó nhất trong 2 điểm, nghĩa là yi+1 = round(y) = round(m.xi+1 +b)Như vậy sẽ tốn 1 phép nhân và 1 phép cộng số thực. Để cải thiện tốc độ, người ta dùng cáchsau để khử phép nhân. Nhận xét rằng: yi = m.xi + b yi+1 = m.xi+1 +b ⇒ yi+1 = yi + m Begin Lưu đồ thuật toán DDA m:=dy/dx ; x:=x1; y:=y1; putpixel(x,round(y)); No x < x2 ? End Yes x:=x+1; y:=y+m; PutPixel(x,round(y));Ví dụ: Cho A(12,20) và B(22,27), ta có m=0.7http://www.ebook.edu.vn 40Đồ họa máy tính - Khoa CNTT - ĐHSPHN i xi yi y 0 12 20 20 1 13 21 20.7 2 14 21 21.4 3 15 22 22.1 4 16 23 22.8 5 17 24 23.5 6 18 24 24.2 7 19 25 24.9 8 20 26 25.6 9 21 26 26.3 10 22 27 27Thuật toán DDA vẽ đoạn thẳng{ Vẽ đoạn thẳng trong trường hợp 0Đồ họa máy tính - Khoa CNTT - ĐHSPHN2. Thuật toán Bresenham vẽ đoạn thẳng (xi+1,y) yi+1 P d2 y d1 yi S xi+1 xiTrong hình vẽ (xi+1,y) là điểm thuộc đoạn thẳng thực, ta có: y = m(xi+1) + b. Giả sử ở bướci ta đã xác định được điểm (xi,yi).Đặt d1 = y – y1 ; d2 = (yi +1) - y ;Việc chọn điểm tiếp theo (xi+1, yi+1) là S hay P tùy thuộc vào việc d1 lớn hơn hay nhỏ hơn d2,nói cách khác là phụ thuộc vào dấu của (d1 – d2) • Nếu d1 – d2 0, ta sẽ chọn P, tức là yi+1 = yi+1Đặt pi = dx (d1 – d2).Thay d1 = y – y1 ; d2 = (yi +1) – y vào ta có pi = dx (2y - 2yi -1)Thay y = mxi+b = dy(xi+1)/dx + b vào ta có pi = 2dx [dy(xi+1)/dx +b] – 2yidx –dx = 2xidy – 2yidx +C với C = 2dy + (2b-1)dx là hằng số.Ta nhận xét rằng, nếu tại bước thứ i ta xác định được dấu của pi thì sẽ xác định được điểmcần tô ở bước i+1.Làm sao để tính giá trị của pi ? ta dùng phương pháp “lũy tiến” như sau.Ta có:pi+1 –pi = (2xi+1dy – 2yi+1dx +C) - (2xidy – 2yidx +C) = 2dy -2dx(yi+1 – yi) • Nếu pi0 thì điểm được chọn là P, tức là yi+1 = yi+1 ⇒ pi+1 = pi +2dy -2dxCuối cùng, giá trị p0 được tính từ điểm ảnh đầu tiên (x0, y0) theo công thức saup0 = 2x0dy – 2y0dx + cThay giá trị của c vào, chú ý rằng điểm đầu (x0, y0) cũng thuộc đoạn thẳng thực nên y0 =mx0 + b = x0dy/dx + b, suy ra p0 = 2dy -dxtóm lại là:http://www.ebook.edu.vn 42Đồ họa máy tính - Khoa CNTT - ĐHSPHN p0 p2 y1 ... p1 y0 y2 ...Ví dụ: Cho A(12,20) và B(22,27), ta códx = 22 – 12 = 10 ; dy = 27 – 20 = 7;c1 = 2dy = 14 ; c2 = 2(dy-dx) = -6;p0 = 2Dy – dx = 4 i xi yi pi 0 12 20 4 1 13 21 -2 2 14 21 12 3 15 22 6 4 16 23 0 5 17 24 -6 6 18 24 8 7 19 25 2 8 20 ...