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

ĐỒ HỌA RASTER
THUẬT TOÁN
VẼ ĐƯỜNG BẬC HAI
Giảng viên : Bùi Tiến Lên
Thuật toán vẽ đường bậc hai
Bước 1 Rút gọn đường cong cần vẽ (Dựa trên tính đối 
xứng của đường cong).
Bước 2 Phân vùng đường cong cần vẽ. Dựa trên kết 
quả của việc khảo sát hàm số đường cong cụ thể là sự 
biến thiên của đạo hàm để phân đường cong thành từng 
vùng khác nhau.
Bước 3 Xây dựng thuật toán MidPoint vẽ cho từng 
Trang 2
vùng.
Ví dụ
Bước 1 Rút gọn đường cong
Trang 3
Bước 2 Phân vùng đường cong
Tăng chậm Tăng nhanh
Trang 4
Giảm chậm Giảm nhanh
Bước 2 Phân vùng đường cong 
Đường cong 
giảm chậm
Đường cong 
giảm nhanh
Trang 5
Bước 3 Xây dựng thuật toán MidPoint
Thuật toán 1
Thuật toán 2
Trang 6
Ví dụ
dương) nguyên b (a, 1
b
y
a
x
 (E)
trình phương có ellipse đường vẽtoán thuật dựng Xây
2
2
2
2
=+
Trang 7
Ví dụ
+
−
=∈−=
a
ba
a
0x
sát khảo Bảng
xa
x
a
b
- y' có a] [0, x vớixa
a
b
 y
Hàm
22
2
22
22
B(0, b)
Trang 8
∞−
−
+
1
0
'y
0
ba
b
b
y
22
2
I
A(a, 0)
Ví dụ
Hàm kiểm tra bên trong / bên ngoài của ellipse
F(x, y) = b2x2 + a2y2 – a2b2
bên ngoài
Trang 9
bên trong
Ví dụ
Nhận xét điểm sáng thứ i
A(xi + 1, yi)
B(xi + 1, yi – 1)
Xây dựng biến fi
Trung điểm M của AB
i A
M
yi-1/2
yi
Trang 10
M(xi + 1, yi – 1/2)
Biến fi
fi = F(M)
B
xi xi+1
yi-1
Ví dụ
i
222
2
i
2
i
22
i
22
i
2
i
i
nguyên f tính thức Công
bab
4
a
yaxb2yaxbf
gốc f tính thức Công
−++−++=
Trang 11
222
2
i
2
i
22
i
22
i
2
i bab4
a
yaxb2yaxbf −+





+−++=
Ví dụ
Cách tính fi cải tiến
3) (2xb f f
thì 0 f nếu
ba –b 
4
a
 f
2
i
22
2
1
++=
<
+





=
Trang 12
 2) (–2ya 3) (2xbff
thì 0 fi nếu
i
2
i
2
i i
ii1i
+++ + = 
≥
1+
+
Ví dụ
Đặt 
M = b2(2xi + 3)
N = b2(2xi + 3) + a2(-2yi + 2)
Bảng biến thiên 
i xi yi M N
Trang 13
fi < 0 Tăng 1 Không Tăng 2b2 Tăng 2b2
fi >= 0 Tăng 1 Giảm 1 Tăng 2b2 Tăng 2a2 + 2b2
Ví dụ
Cách tính fi cải tiến cải tiến
222
2
222
1
thì 0 fi nếuthì 0 f nếu
3b b2a - 2a N
3b M
ba –b 4a f
≥<
+=
=
+=
Trang 14
222
22
i ii1i
i
b22a N2b N
2b M2b M
NffM f f
+=+=+
=+=+
 + = += 1++