Bài giảng 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

Nội dung text: Bài giảng 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

1. 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 1
2. 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 2
3.  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 tốn ◦ Tính tốn số nguyên nhanh hơn số thực ◦ Tránh các tính tố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 3
4. Phan Thị Hải Hờng – BM KHMT 4
5. Phan Thị Hải Hờng – BM KHMT 5
6.  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 6
7. 1. CÁC THUẬT TỐN VẼ ĐƯỜNG  1.1. Thuật tốn DDA (Digital Defferencial Analyzer) hay thuật tốn tăng dần.  1.2. Thuật tốn Bresenham.  1.3. Thuật tốn MidPoint (trung điểm). Phan Thị Hải Hờng – BM KHMT 7
8. 1.1. Thuật tố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 tốn nhân và một phép tốn cộng số thực. Phan Thị Hải Hờng – BM KHMT 8
9.  Để 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 9
10. Phan Thị Hải Hờng – BM KHMT 10
11. Phan Thị Hải Hờng – BM KHMT 11
12. Phan Thị Hải Hờng – BM KHMT 12
13. Thuật tốn DDA #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; k<steps; k++) { x += x_inc; y += y_inc; PutPixel (ROUND(x), ROUND(y),C); } } Phan Thị Hải Hờng – BM KHMT 13
14. Nhận xét DDA  Khử được phép nhân nhờ ysau = ytrước + m  Khi vẽ đoạn thẳng khá dài: Cộng dồn giá trị thực m vào y → tích lũy sai số → hàm làm trịn cĩ kết quả sai → xác định vị trí của điểm vẽ ra bị chệch hướng so với đường thẳng thực.  Vẫn hạn chế về mặt tốc độ do vẫn cịn phép tốn cộng số thực và làm trịn. Phan Thị Hải Hờng – BM KHMT 14
15. Thuật toán Bresenham  Đây là một trong những thuật tốn cổ nhất trong đồ họa máy tính.  Được Jack E. Bresenham thiết kế vào năm 1962 tại cơng ty IBM.  Được sử dụng rộng rãi, đặc biệt để vẽ đoạn thẳng trên màn hình máy tính, cả trong firmware lẫn trong phần cứng của card đồ họa hiện đại.  Ưu điểm: Chỉ sử dụng các lệnh cộng trừ số học và lệnh trên pixel, cĩ chi phí rẻ và phù hợp với kiến trúc sơ khai của máy tính.  Mở rộng của giải thuật này là giải thuật vẽ các Phanđường Thị Hải H congờng – BM bậcKHMT 2. 15
16. Thuật toán Bresenham  Giả sử vừa vẽ điểm tại (xi, yi), bây giờ phải xác định điểm sẽ vẽ là một trong 8 pixel liền kề: (xi+1, yi), (xi-1, yi), (xi, yi-1), (xi, yi+1)  dx=x2-x1; dy=y2-y1;  Hình dạng đoạn thẳng phụ thuộc vào các giá trị dx và dy ◦ dx=0 → đ/thẳng song song với trục y ◦ dy=0 → đ/thẳng song song với trục x ◦ dx>0 → tọa độ x biến thiên tăng dần ◦ dx abs(dy): y=f(x) ◦ Nếu abs(dx) < abs(dy): x=f(y) Phan Thị Hải Hờng – BM KHMT 16
17. Phan Thị Hải Hờng – BM KHMT 17
18. Tư tưởng thuật tốn d1 = y − yi d2 = (yi +1) − y Phan Thị Hải Hờng – BM KHMT 18
19. Tư tưởng thuật tốn  Nếu d1 - d2 < 0 → chọn điểm P1, tức là yi+1=yi.  Nếu d1 - d2 < 0 → chọn điểm P2, tức là yi+1=yi.+1  Xét pi = Dx(d1 − d2 ) = Dx(2y − 2yi −1) pi = Dx[2(m(xi +1) +b) − 2yi −1] Dy  m = pi = 2Dyxi − 2Dxyi + c Thay Dx ◦ Với c = 2Dy + (2b −1)Dx Dx 0 p  Do nên ( d 1 − d 2 ) cùng dấu i   tại bước thứ i ta xác định được dấu của  xác định được điểm cần chọn ở bước (i+1). Phan Thị Hải Hờng – BM KHMT 19
20.  Làm thế nào để tính được p i tại mỗi bước nhanh?  Ta cĩ: pi+1 − pi = (2Dyxi+1 − 2Dxyi+1 + c) − (2Dyxi − 2Dxyi + c) pi+1 − pi = 2Dy(xi+1 − xi ) − 2Dx( yi+1 − yi ) pi+1 − pi = 2Dy − 2Dx( yi+1 − yi ) do xi+1 = xi +1  Như vậy: Nếu pi 0: pi+1 = pi + 2Dy do yi+1 = yi Nếu pi 0: pi+1 = pi + 2Dy − 2Dx do yi+1 = yi +1 và ta có : p0 = 2Dyx0 − 2Dxy0 + c = 2Dyx0 − 2Dxy0 + 2Dy + (2b −1)Dx Dy Mà y = mx + b = x + b nên p = 2Dy − Dx 0 0 Dx 0 0 Phan Thị Hải Hờng – BM KHMT 20
21. Ví dụ  Tính tốn các điểm cần vẽ khi vẽ đoạn thẳng từ A đến B : Với A=(12,20) B=(22,27) Phan Thị Hải Hờng – BM KHMT 21
22. Phan Thị Hải Hờng – BM KHMT 22
23. Phan Thị Hải Hờng – BM KHMT 23
24. Thuật tốn Bresenham (0<m<1) void lineBres (int x1, int y1, int x2, int y2) { int Dx, Dy, p, Const1, Const2; int x, y; Dx = x2 - x1; Dy = y2 - y1; p = 2*Dy – Dx; Const1 = 2*Dy; Const2 = 2*(Dy-Dx); x = x1; y = y1; setpixel(x, y, Color); for(i=x1; i<=x2; i++) { if (p<0) p += Const1; else { p += Const2; y++; } x++; setpixel(x, y, Color); } } Phan Thị Hải Hờng – BM KHMT 24
25. Nhận xét Bresenham  Thuật tốn chỉ tính tốn với số nguyên  Nhân 2  dịch trái → tăng tốc độ đáng kể so với DDA  Cho kết quả tương tự DDA  Chú ý cài đặt vẽ đoạn thẳng với hệ số gĩc bất kỳ Phan Thị Hải Hờng – BM KHMT 25
26. Thuật tốn trung điểm (MidPoint)  Pitteway cơng bố năm 1967, Van Aken cải tiến 1984.  Giả sử ta đã chọn P để vẽ, xác định pixel tiếp theo tại E hay NE. Phan Thị Hải Hồng – BM KHMT 26
27. Thuật tốn trung điểm (MidPoint)  Giao của đường thẳng thực với x=xp+1 tại Q, M là trung điểm của NE và E.  Ý tưởng: Xét vị trí của M so với đường thẳng thực: ◦ Nếu M nằm phía dươí :chọn NE. ◦ Nếu M nằm phía trên :chọn E. =>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 27
28. Thuật tố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 d 0, 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) 1 = 2[a(xp +1) + b(y p + ) + c] 2 Phan Thị Hải Hờng – BM KHMT 28
29. Thuật tốn trung điểm (MidPoint)  Gọi giá trị d vừa tính là: 1 dold = 2[a(xp +1) + b(y p + ) + c] 2 ◦ Nếu vừa chọn E 1 1 dnew = F(xp + 2, y p + ) = 2[a(xp + 2) + b(y p + ) + c] 2 2 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 29
30. Thuật tốn trung điểm (MidPoint) ◦ Nếu vừa chọn NE 3 3 dnew = F(xp + 2, y p + ) = 2[a(xp + 2) + b(y p + ) + c] 2 2  dnew = dold + 2(a + b) = dold + 2(dy – dx)  ∆NE = 2(dy-dx) là số gia của điểm tiếp theo 30
31. Thuật tố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. 1 1 F(x0 +1, y0 + 2 ) = 2[a(x0 +1) + b(y0 + 2 ) + c] = b 2[ax0 + by0 + c + a + 2 ] = F(x0 + y0 ) + 2a + b ◦ → 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 31
32. Thuật tố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 32
33. Bài tập  Cài đặt các thuật tố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 tố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) Phan Thị Hải Hờng – BM KHMT 33