Kỹ thuật về đồ họa - Chương 3

Chia sẻ: Trần Ngọc Phương | Ngày: | Loại File: PPT | Số trang:33

Thêm vào BST

Báo xấu

127
lượt xem 24
download

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

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 đô ̣ ve ̃ nhanh

Chủ đề:

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

Lưu

Nội dung Text: Kỹ thuật về đồ họa - Chương 3

KỸ THUÂT ĐỒ HOẠ ̣ KY (Computer Graphics) (Computer Chương 3: Cac đôi tượng đồ hoạ cơ sở ́ ́ ́ (tiêp) 1 Phan Thi Hai Hồng BM KHMT ̣ ̉
̀ ́ Bai toan Vẽ đoạn thẳng Bai 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 độ vẽ nhanh ́ ◦ 2 Phan Thi Hai Hồng – BM KHMT ̣ ̉
tắc tổng quát khi vẽ đồ họa:  Quy ◦ 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ẽ. 3 Phan Thi Hai Hồng – BM KHMT ̣ ̉
4 Phan Thi Hai Hồng – BM KHMT ̣ ̉
5 Phan Thi Hai Hồng – BM KHMT ̣ ̉
đoạn thẳng có hệ số góc:  Xét  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 độ. 6 Phan Thi Hai Hồng – BM KHMT ̣ ̉
1. CÁC THUÂT TOAN VẼ ĐƯỜ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). 7 Phan Thi Hai Hồng – BM KHMT ̣ ̉
1.1. Thuật toán DDA 1.1.  Việc quyết định chọn , dựa vào là hay 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. 8 Phan Thi Hai 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 9 Phan Thi Hai Hồng – BM KHMT ̣ ̉
10 Phan Thi Hai Hồng – BM KHMT ̣ ̉
11 Phan Thi Hai Hồng – BM KHMT ̣ ̉
12 Phan Thi Hai Hồng – BM KHMT ̣ ̉
Thuật toá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
Nhân ́ ̣ Nhân xet DDA Khử được phep nhân nhờ ysau = ytrước + m ́ vẽ đoạn thẳng khá dài: Cộng dồn giá trị Khi 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 ̃ toán cộng số thực và làm tròn. 14 Phan Thi Hai Hồng – BM KHMT ̣ ̉
Thuật toán Bresenham Thu là một trong những thuật toán cổ nhất trong Đây đồ 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 Thi Hai Hồng – BM KHMTậc 2. đường cong b 15 ̣ ̉
Thuật toán Bresenham Thu 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) 16 ◦ ̣ N̉ếu abs(dx) Phan Thi Hai Hồng – BM KHMT < abs(dy): x=f(y)
17 Phan Thi Hai Hồng – BM KHMT ̣ ̉
Tư tưởng thuât toan ̣ ́ d1 = y − yi d 2 = ( yi + 1) − y 18 Phan Thi Hai Hồng – BM KHMT ̣ ̉
Tư tưởng thuât toan ̣ ́ 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. pi = Dx(d1 − d 2 ) = Dx(2 y − 2 yi − 1) +1  Xet i = Dx[2(m( xi + 1) + b) − 2 yi − 1] ⇒p ́ Dy ⇒ pi = 2 Dyxi − 2 Dxyi + c m= Dx c = 2 Dy + (2b − 1) Dx Thay pi (d1 − d 2 ) ◦ Với > 0 Dx pi ̀ ́ Do nên cung dâu 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). 19 Phan Thi Hai Hồng – BM KHMT ̣ ̉
p thế nào để tính được i tại mỗi bước Làm nhanh? Ta co:i +1 − pi = ( 2 Dyxi +1 − 2 Dxyi +1 + c ) − (2 Dyxi − 2 Dxyi + c) p ́ ⇔ pi +1 − pi = 2 Dy( xi +1 − xi ) − 2 Dx( yi +1 − yi ) ⇔ pi +1 − pi = 2 Dy − 2 Dx( yi +1 − yi ) do xi +1 = xi + 1 Như Neáu i < 0 : pi +1 = pi + 2 Dy do yi +1 = yi ̣ vây: p Neáu i > 0 : pi +1 = pi + 2 Dy − 2 Dx do yi +1 = yi + 1 p vaøacoù 0 = 2 Dyx0 − 2 Dxy0 + c t :p = 2 Dyx0 − 2 Dxy0 + 2 Dy + ( 2b −1) Dx Dy Maø 0 = mx0 + b = x0 + b neân0 = 2 Dy − Dx y p Dx 20 Phan Thi Hai Hồng – BM KHMT ̣ ̉