Đồ họa Raster - Các thuật toán vẽ đường thẳng (Phần 1)

ĐỒ HỌA RASTER
CÁC THUẬT TOÁN
VẼ ĐƯỜNG THẲNG
Giảng viên : Bùi Tiến Lên
Bài toán vẽ đường thẳng
Input
(X1, Y1) (X2, Y2)
Output 
{(x1, y1) (x2, y2) … (xn, yn)} là những điểm sáng “nằm 
trên” đường thẳng 
Trang 2
(X1, Y1)
(X2, Y2)
Một số công thức cơ bản của đường thẳng
m
b
m
y
x
bmxy
−=
+=
(X
2
, Y
2
)
Trang 3
11
12
12
mXYb
x
y
XX
YY
m
−=
∆
∆
=
−
−
=
(X
1
, Y
1
)
Phân loại đường thẳng
Tăng chậm Tăng nhanh
Trang 4
Giảm chậm Giảm nhanh
Giải quyết
Thuật toán DDA
Thuật toán Bresenham
Trang 5
Thuật toán DDA
Trường hợp 1
Đoạn thẳng tăng chậm và điểm đầu ở bên trái.
Thuật toán
Bước 1 Xác định điểm đầu tiên
x1 = X1
y1 = Y1
Bước 2 Xác định những điểm tiếp theo
1
2 3 n…
Trang 7
Lặp xi < X2
xi+1 = xi + 1
y = mxi+1 + b
yi+1 = Round(y)
Trường hợp 1
Cải tiến tính y
Xét hai điểm sáng liên tiếp nhau
i
i+1
(xi, ycũ)
(xi+1, ymới)
Trang 8
Công thức liên hệ
y đầu là Y1
ymới = ycũ + m
Trường hợp 2
Đoạn thẳng tăng nhanh và điểm đầu ở bên dưới.
Thuật toán
Bước 1 Xác định điểm đầu tiên
x1 = X1
y1 = Y1
Bước 2 Xác định những điểm tiếp theo
Trang 9
Lặp yi < Y2
yi+1 = yi + 1
x = yi+1/m – b/m
xi+1 = Round(x)
Trường hợp 2
Cải tiến tính x
Xét hai điểm sáng liên tiếp nhau
Công thức liên hệ
i
i+1
(xc, yi)
(xmới, yi+1)
Trang 10
x đầu là X1
xmới = xcũ + k
12
12
YY
XX
k
−
−
=
Bài toán mở rộng
Input
(X1, Y1, C1) (X2, Y2, C2)
Output 
{(x1, y1, c1) (x2, y2, c2) … (xn, yn, cn)} là những điểm 
sáng “nằm trên” đường thẳng và có màu khác nhau
(X2, Y2, C2)
Trang 11
(X1, Y1, C1)
Thuật toán Bresenham
Trường hợp 1
Dự đoán điểm sáng thứ i+1
B
Trang 13
i A
Trường hợp 1
Xây dựng biến pi
y = m(xi+1) + b
d1 = y - yi
d2 = yi + 1 - y
pi = ∆x(d1 - d2)
Byi+1
y
C
d2
d1
Trang 14
i A
xi xi+1
yi
Trường hợp 1
Khoảng cách d1, d2 hay khoảng cách h1, h2 ?
B
C
d2
h2
Trang 15
A
xi+1
d1
h1
Trường hợp 1
Cách tính pi
pi = 2∆yxi – 2∆xyi + 2∆xY1 – 2∆yX1 + 2∆y – ∆x
Trang 16
Trường hợp 1
Đoạn thẳng tăng chậm và điểm đầu ở bên trái.
Thuật toán
Bước 1 Xác định điểm đầu tiên
x1 = X1
y1 = Y1
Bước 2 Xác định những điểm tiếp theo
Lặp x < X
Trang 17
i 2
pi = …
pi < 0 
xi+1 = xi + 1
yi+1 = yi
pi >= 0
xi+1 = xi + 1
yi+1 = yi + 1
Trường hợp 1
Cách tính pi cải tiến
p1 = 2∆y - ∆x
pi < 0 :
pi+1 = pi + 2∆y
pi >= 0 :
p = pi + 2∆y - 2∆x
Trang 18
i+1
Trường hợp 2
Dự đoán điểm sáng thứ i+1
A B
Trang 19
i
Trường hợp 2
A Byi+1
C
d2d1
i2
i1
i
i
x1xd
xxd
m
b
m
1y
x
p biến dựng Xây
−+=
−=
−
+
=
Trang 20
i
xi xi+1
yi
x
( )21i ddyp −∆=
Trường hợp 2
Cách tính pi
p1 = 2∆x - ∆y
pi < 0 :
pi+1 = pi + 2∆x
pi >= 0 :
p = pi + 2∆x - 2∆y
Trang 21
i+1
Trường hợp 2
Thuật toán
Bước 1 Xác định điểm đầu tiên
x1 = X1
y1 = Y1
Bước 2 Xác định những điểm tiếp theo
Lặp xi < X2
Trang 22
pi < 0 
xi+1 = xi
yi+1 = yi + 1
pi >= 0
xi+1 = xi + 1
yi+1 = yi + 1