Chương 3: Các đối tượng đồ hoạ cơ sở (tiếp)

KỸ THUẬT ĐỒ HOẠ  (Computer Graphics) Chương 3: Các đối tượng đồ hoạ cơ sở (tiếp) Phan Thị Hải Hồng - BM KHMT * Bài toán Vẽ đoạn thẳng Input: điểm đầu (x1, y1), điểm cuối (x2, y2), màu tô C. Thực chất việc vẽ đường thẳng là việc định màu cho các pixel rời rạc. Do tọa độ pixel chỉ là số nguyên nên khái niệm “thẳng” chỉ là gần đúng. Yêu cầu chất lượng đường vẽ Hình dạng liên tục Độ dày và độ sáng đều Các pixel gần đường “lý tưởng” được hiển thị Tốc độ vẽ nhanh Phan Thị Hải Hồng – BM KHMT * Quy tắc tổng quát khi vẽ đồ họa: Cộng và trừ nhanh hơn nhân Nhân nhanh hơn chia Sử dụng bảng để đánh giá hàm rời rạc nhanh hơn tính toán Tính toán số nguyên nhanh hơn số thực Tránh các tính toán không cần thiết nhờ nhận ra các trường hợp đặc biệt của đường vẽ. Phan Thị Hải Hồng – BM KHMT * Phan Thị Hải Hồng – BM KHMT * Phan Thị Hải Hồng – BM KHMT * Xét đoạn thẳng có hệ số góc: Nếu là điểm đã xác định được ở bước thứ i (điểm màu đen) thì điểm cần chọn ở bước thứ (i+1) sẽ là một trong hai trường hợp: Vấn đề còn lại là cách chọn một trong hai điểm trên như thế nào để có thể tối ưu về mặt tốc độ. Phan Thị Hải Hồng – BM KHMT *  1. CÁC THUẬT TOÁN VẼ ĐƯỜNG 1.1. Thuật toán DDA (Digital Defferencial Analyzer) hay thuật toán tăng dần. 1.2. Thuật toán Bresenham. 1.3. Thuật toán MidPoint (trung điểm). Phan Thị Hải Hồng – BM KHMT * 1.1. Thuật toán DDA Việc quyết định chọn là hay , dựa vào phương trình của đoạn thẳng Nếu tính trực tiếp giá trị thực y ở mỗi bước từ phương trình thì phải cần một phép toán nhân và một phép toán cộng số thực. Phan Thị Hải Hồng – BM KHMT * Để cải thiện tốc độ, người ta tính giá trị thực của y ở mỗi bước theo cách sau để khử phép tính nhân trên số thực. Nhận xét rằng: ysau = ytrước =  ysau = ytrước + m Phan Thị Hải Hồng – BM KHMT * Phan Thị Hải Hồng – BM KHMT * Phan Thị Hải Hồng – BM KHMT * Phan Thị Hải Hồng – BM KHMT * * #define ROUND(a) ((int)(a+0.5)) void lineDDA (int xa, int ya, int xb, int yb) { int dx = xb - xa, dy = yb - ya, steps, k; float x_inc, y_inc, x = xa, y = ya; if (abs (dx) > abs (dy)) steps = abs (dx); else steps = abs (dy); x_inc = dx / (float) steps; x= x1; y_inc = dy / (float) steps; y= y1; PutPixel (ROUND(x), ROUND(y),C); for (k=0; k0  tọa độ x biến thiên tăng dần dx abs(dy): y=f(x) Nếu abs(dx) Nhiệm vụ: xác định vị trí của M so với đường thẳng. Phan Thị Hải Hồng – BM KHMT * Thuật toán trung điểm (MidPoint) * Phương trình đường thẳng: F(x,y) = ax+by+c Giá trị hàm tại M: F(M) = F(xp+1, yp+1/2) = d Nếu d0, M nằm phía trên  chọn E Nếu d=0, chọn E hay NE tuỳ ý Xét F(x,y) = (ax+by+c)  Xét cho F(x,y) = 2(ax+by+c) Phan Thị Hải Hồng – BM KHMT Thuật toán trung điểm (MidPoint) * Gọi giá trị d vừa tính là: Nếu vừa chọn E dnew- dold =2a = 2dy Do a = dy; b = -dx (xuất phát từ PT chính tắc của đường thẳng)  ∆ε = 2dy là số gia của điểm tiếp theo khi chọn E Phan Thị Hải Hồng – BM KHMT Thuật toán trung điểm (MidPoint) Nếu vừa chọn NE dnew = dold + 2(a + b) = dold + 2(dy – dx) ∆NE = 2(dy-dx) là số gia của điểm tiếp theo * Thuật toán trung điểm (MidPoint) * Tính giá trị khởi đầu của d Giả sử vẽ đoạn thẳng từ (x0,y0) đến (x1,y1)  trung điểm thứ nhất có tọa độ (x0+1,y0+1/2), F(x0,y0) = 0.  dstart= 2a + b mà a = dy, b = -dx Do vậy, ta có dstart=2dy-dx; ∆E=2dy; ∆NE=2(dy-dx) Phan Thị Hải Hồng – BM KHMT Thuật toán trung điểm (MidPoint) * void MidpointLine(int x1,y1,x2,y2,C) { Int dx = x2-x1, dy = y2-y1; Int d = 2*dy-dx; Int ∆E = 2*dy, ∆NE = 2*(dy-dx); x=x1;y=y1; PutPixel(x,y,C); while (x < x2) { if (d<= 0) { d += ∆NE; x++ } else { d += ∆E; x++; y++; } PutPixel(x,y,C); }} Phan Thị Hải Hồng – BM KHMT Thuật toán trung điểm (MidPoint) Bài tập Phan Thị Hải Hồng – BM KHMT * Cài đặt các thuật toán DDA, Bresenham, MidPoint vẽ đoạn thẳng qua hai điểm cho trước trong trường hợp tổng quát với hệ số góc m lấy giá trị bất kì. Người ta có thể cải thiện tốc độ cài đặt thuật toán vẽ đoạn thẳng bằng cách chỉ cần vẽ một nửa đoạn thẳng, phần còn lại lấy đối xứng nửa đoạn thẳng đã vẽ. Hãy cài đặt minh họa. Vẽ đường thẳng với nét đứt. Vẽ đường thẳng với nét đậm. Vẽ đường thẳng với màu nhạt dần từ (x1,y1) đến (x2,y2)