YOMEDIA
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
129
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
AMBIENT/
Chủ đề:
Nội dung Text: Kỹ thuật về đồ họa - Chương 3
- KỸ THUÂT ĐỒ HOẠ
̣
KY
(Computer Graphics)
(Computer
Chương 3: Cac đôi tượng đồ hoạ 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 độ vẽ 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 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).
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
̣ ̉
Thêm tài liệu vào bộ sưu tập có sẵn:
Báo xấu
LAVA
ERROR:connection to 10.20.1.100:9315 failed (errno=111, msg=Connection refused)
ERROR:connection to 10.20.1.100:9315 failed (errno=111, msg=Connection refused)
Đang xử lý...
Thêm vào BST
Báo xấu
