Chương 1
CÁC GiẢI THUẬT SINH THỰC THỂ
CƠ SỞ
Giảng viên: Nguyễn Viết Cường
NỘI DUNG
•
Các đối tượng đồ họa cơ sở
–
Hệ tọa độ thực và hệ tọa độ thiết bị
–
Điểm và đoạn thẳng
•
Các giải thuật xây dựng các thực thể cơ sở
–
Giải thuật vẽ đường thẳng thông thường
–
Thuật toán DDA (Digital Differential Analizer)
–
Giải thuật Bresenham
–
Giải thuật trung điểm-Midpoint
–
Giải thuật sinh đường tròn
–
Giải thuật sinh đường tròn Midpoint
–
Giải thuật sinh đường ellipse
–
Giải thuật sinh ký tự
–

5
P
wc
(x, y)
P
wc
(x, y)
x
max
y
max
x
y
O O
HỆ TỌA ĐỘ THẾ GiỚI THỰC VÀ THIẾT BỊ
HCMUS - 2009
HCMUS - 2009
Bài giảng Đồ họa máy tính – Đặng Nguyễn Đức Tiến - Vũ Quốc Hoàng - Lê Phong
Bài giảng Đồ họa máy tính – Đặng Nguyễn Đức Tiến - Vũ Quốc Hoàng - Lê Phong
6
6
x
y
O
c
r
O
Quy ước bàn tay phải
Quy ước bàn tay trái
HỆ TỌA ĐỘ THẾ GiỚI THỰC VÀ THIẾT BỊ

2
) như sau:
(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

2
-y
1
)/(x
2
-x
1
))x
1
 y = mx + b
Trong đó: m = (y
2
-y
1
)/(x
2
-x
1
) độ dốc hay hệ số góc của đường b =
y
1
- kx
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)
ĐIỂM VÀ ĐOẠN THẲNG
+ Biểu diễn không tường minh: ax+by+c=0
–
Ta có
(y2-y1)x - (x2-x1)y + (x2-x1)y1 - (y2-y1)x1 = 0

2
ta chọn đơn vị nhỏ nhất của màn hình ∆x=1.
GIẢI THUẬT VẼ ĐOẠN THẲNG THÔNG THƯỜNG
•
Lưu đồ giải thuật:
Input: x
1
, x
2
,
y
1
, y
2
, color
x =x
1,
y = y
1
x < x
2

y = y + (x-x
1
)*(y
2
-y
1
)/(x
2

, y
i
+1}
THUẬT TOÁN DDA (Digital Differential Analizer)
•
Việc quyết định chọn y
i+1
là y
i
hay y
i
+1 dựa vào
đường thẳng y=mx+b
•
Tính toạ độ điểm (x
i
+1,y) thuộc về đoạn thẳng
thực, tiếp đó y
i+1
sẽ trị sau khi làm tròn tung độ y
y=m(x
i
+1)+b=y
i
+m
y
i+1
= round(y)
THUẬT TOÁN DDA (Digital Differential Analizer)
•

•
Yêu cầu: về nhà sinh viên tự cài đặt thuật toán
THUẬT TOÁN BRESENHAM
•
Giả sử đường cong được xấp xỉ
thành các điểm lần lượt là (x
i
,y
i
).
Các điểm này có tọa độ nguyên và
được hiển thị trên màn hình.
•
Bài toán đặt ra là nếu biết được
tọa độ (x
i
,y
i
) của bước thứ i, thì
điểm ở bước i+1 là (x
i+1
,y
i+1
) sẽ
được xác định như thế nào.
•
Trong trường hợp hệ số góc
0≤m≤1, chúng ta có x
i+1
=x

1
) và (x
2
,
y
2
) là y=mx+b với
m=Dy/Dx và b=y
1
- mx
1
.
•
Đặt d
1
=y-y
i
và d
2
=(y
i
+1)-y,
do đó việc chọn tọa độ của
y
i+1
phụ thuộc vào d
1
và d
2


=x
i
+1
S
d
2
d
1
(x
i+1
,y=f(x
i+1
))
THUẬT TOÁN BRESENHAM
d
1
- d
2
= (2y – 2y
i
– 1) là một số thực do chứa m
Xét p
i
= Dx (d
1
- d
2
) = Dx (2y - 2y
i
- 1)

+ C)
= 2Dy – 2Dx(y
i+1
– y
i
)
Từ đây, ta suy ra cách tính p
i+1
theo p
i
:
–
Nếu p
i
<0 thì y
i+1
=y
i
nên p
i+1
= p
i
+ 2Dy
–
Ngược lại thì y
i+1
=y
i
+1 nên p
i+1

1
và d
2
sao
cho d
1
là độ lệch từ y đến
điểm hiện hành y
i
- Xác định p
i
sao cho p
i

cùng dấu với (d
1
– d
2
) và
mang giá trị nguyên
- Tính p
i+1
theo p
i
theo 2
trường hợp p
i
<0 và p
i
>

AB
+ Nếu M ở trên đoạn
thẳng AB thì chọn B còn
+ Nếu M ở dưới đoạn
thẳng AB chọn A
Công thức đơn giản hơn, tạo
được các điểm tương tự như với
Bresenham
d = f(x
i
+ 1, y
i
+ 1/2) là
trung điểm của đoạn AB
GIẢI THUẬT TRUNG ĐIỂM –Mid Point
So sánh hay kiểm tra M sẽ được thay bằng việc xét giá trị
d.
- d > 0 điểm B được chọn khi đó y
i+1
= y
i

- nếu d<0 điểm A được chọn khi đó y
i+1
=y
i
+ 1
Trường hợp d = 0 chúng ta có thể chọn điểm bất kỳ hoặc
A, hoặc B.
Sử dụng phương pháp biểu diễn không tường minh ta có:

i+1
– d
i
= a+b
Hay d
i+1
= d
i
+ dy - dx
+ Nếu chọn B (d>0) thì M sẽ tăng theo x
d
i+1
=f(x
i
+2,y
i
+1/2) = a(x
i
+2) +b(y
i
+1/2) +c
d
i+1
- d
i
= a
Hay d
i+1
= d
i

1
,y
1
) = 0
Vậy d
1
= a+ b/2 = dy - dx/2