DHTM Thuật toán cơ sở
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (1.43 MB, 178 trang )
1
BÀI GIẢNG
ĐỒ HỌA MÁY TÍNH
GV: Vũ Đức Huy
SĐT: 0912316373
Bộ môn: HTTT-ĐHCNHN
EMail:
Thời lượng:
Số tín chỉ: 03
Lên lớp: 20
TH: 25
Bài tập lớn + Bảo vệ: 15
2
BÀI GIẢNG
ĐỒ HỌA MÁY TÍNH
Các điểm:
Kiểm tra định kỳ: 02
Kiểm tra thường xuyên: Không định trước
Thi: Kết quả BTL
Chuyên cần:01
3
Tài liệu tham khảo
[1] James D.Foley, Andrie van Dam, Steven K.Feiner, Jonhn F.
Hughes, Computer Graphics Principles and Practice, Addison
Wesley, 1994.
[2] Hoàng Kiếm, Dương Anh Đức, Lê Đình Duy, Vũ Hải Quân. Giáo
trình cơ sở Đồ hoạ Máy tính, NXB Giáo dục, 2000.
[3] Lê Tấn Hùng, Huỳnh Quyết Thắng. Kỹ thuật đồ hoạ máy tính,
NXB khoa học và kỹ thuật, 2002.
[4] Học viện công nghệ bưu chính viễn thông. Kỹ thuật đồ họa (lưu
hành nội bộ)
[5] Lương Chi Mai. Nhập môn Đồ họa máy tính, NXB Khoa học và
kỹ thuật.
[6] Steven Harrington, Computer Graphics A Programming
Approach, McGraw Hill International Edition, 1987.
[7] Gerald Farin, Curves and Surfaces for Computer Aided
Geometric Design A Practical Guide, Academic Press Inc, 1990.
4
CHƯƠNG 2
CÁC THUẬT TOÁN CƠ SỞ
5
2.1. CÁC THUẬT TOÁN VẼ ĐƯỜNG THẲNG
6
2.1.1. Một số khái niệm
Điểm
Điểm là thành phần cơ sở được định nghĩa trong một
hệ tọa độ. Đối với hệ tọa độ hai chiều mỗi điểm được
xác định bởi cặp tọa độ (x, y).
Ngoài thông tin về tọa độ, điểm còn có thuộc tính là
màu sắc.
Thủ tục vẽ một điểm (x,y) với mầu c: Putpixel(x,y,c)
7
2.1.1. Một số khái niệm
Đoạn thẳng
Biểu diễn tường minh: y = f(x)
Phương trình đoạn thẳng đi qua 2 điểm P (x
1
,y
1
) và
Q(x
2
,y
2
):
(y-y
1
)/( x-x
1
) = ( y
2
-y
1
)/( x
2
-x
1
)
(y-y
1
)(x
2
-x
1
)=(x-x
1
)(y
2
-y
1
)
(x
2
-x
1
)y=(y
2
-y
1
)x + y
1
(x
2
-x
1
) - x
1
(y
2
-y
1
)
y = ((y
2
-y
1
)/(x
2
-x
1
))x + y
1
- ((y
2
-y
1
)/(x
2
-x
1
))x
1
y = mx + b
m = (y
2
-y
1
)/(x
2
-x
1
) Độ dốc hay hệ số góc của
đường
b = y
1
- mx
1
Đoạn chắn trên trục y
Δy = mΔx (tức là khi x thay đổi thì y thay đổi
theo)
8
2.1.1. Một số khái niệm
Đoạn thẳng
Biểu diễn tường minh: y = f(x)
9
2.1.1. Một số khái niệm
Đoạn thẳng
Biểu diễn không tường minh: Ax+By+C=0
Ta có
(y
2
-y
1
)x - (x
2
-x
1
)y + (x
2
-x
1
)y
1
- (y
2
-y
1
)x
1
= 0
(y
2
-y
1
)x - (x
2
-x
1
)y + x
2
y
1
- x
1
y
2
= 0
Tổng quát: Ax + By + C = 0
Với:
A = (y
2
-y
1
)
B = -(x
2
-x
1
)
C = x
2
y
1
- x
1
y
2
10
2.1.1. Một số khái niệm
Đoạn thẳng
Biểu diễn thông qua tham số:
P(t) = P
1
+ t(P
2
- P
1
) t €[0,1]
x(t) = x
1
+ t( x
2
- x
1
)
y (t)= y
1
+ t(y
2
- y
1
)
11
2.1.2. Giải thuật làm tròn
12
2.1.2. Giải thuật làm tròn
Cho phương trình đường thẳng d: y = mx+b
m = (y
2
-y
1
)/(x
2
-x
1
)
b = y
1
- mx
1
Trường hợp d//Oy
Gán x=x
1
; y =y
1
;
Lặp
Putpixel(x,y,c);
y = y+1;
Tới khi y =y
2
;
13
2.1.2. Giải thuật làm tròn
Trường hợp d//Ox
Gán x=x
1
; y =y
1
;
Lặp
Putpixel(x,y,c);
x = x+1;
Tới khi x =x
2
;
14
2.1.2. Giải thuật làm tròn
Trường hợp d gần Ox
Gán x=x
1
; y =y
1
;m = (y
2
-y
1
)/(x
2
-x
1
);b = y
1
- m*x
1
;
Lặp
Putpixel(x,round(y),c);
x = x+1;
y = m*x+b
Tới khi x =x
2
;
15
2.1.2. Giải thuật làm tròn
Trường hợp d gần Oy: x = (1/m)y – b/m
Gán x=x
1
; y =y
1
;m = (y
2
-y
1
)/(x
2
-x
1
);b = y
1
- m*x
1
;
Lặp
Putpixel(round(x),y,c);
y = y+1;
x = (1/m)*y-b/m
Tới khi y =y
2
;
16
2.1.2. Giải thuật làm tròn
Nhận xét:
Thao tác với số thực
Sử dụng phép nhân, chia số thực
Sử dụng hàm làm tròn
Tốn bộ nhớ, chạy chậm
17
2.1.3. Giải thuật DDA
Cho phương trình đường
thẳng d: y = mx+b
m = (y
2
-y
1
)/(x
2
-x
1
)
b = y
1
- mx
1
18
2.1.3. Giải thuật DDA
Giả sử vẽ được (x
i
,y
i
)
Tiếp theo, chọn y
i+1
là y
i
hay y
i
+1 dựa vào phương
trình của đường thẳng d .
19
2.1.3. Giải thuật DDA
Thay x
i
+1 vào phương
trình đường thẳng d:
y
i+1
= m(x
i
+1)+b
y
i+1
= mx
i
+ b + m
y
i+1
= y
i
+ m
20
2.1.3. Giải thuật DDA
Lưu đồ thuật toán
21
2.1.3. Giải thuật DDA
Thủ tục
22
2.1.3. Giải thuật DDA
Nhận xét:
Cải thiện tốc độ: Sử dụng công thức y
i+1
= y
i
+ m thay
cho y = mx + b, tránh phép nhân số thực.
Sai số tích lũy do việc cộng số thực m vào y, điểm vẽ
chệch hướng với đường thẳng thực khi đường thẳng
dài.
Tốc độ vẫn chậm (sử dụng cộng số thực, làm tròn).
23
2.1.4. Giải thuật Bresenham
Mục tiêu
Hạn chế tối đa các phép toán trên số thực trong thuật
toán.
24
2.1.4. Giải thuật Bresenham
Cho phương trình đường
thẳng d: y = mx+b
dx = x
2
-x
1
dy = y
2
-y
1
m = dy/dx
b = y
1
- mx
1
25
2.1.4. Giải thuật Bresenham
Không mất tính tổng
quát, xét 0<m<1
Giả sử vẽ được
(x
i
,y
i
)
Vấn đề:
Chọn điểm tiếp theo?
R
