ĐỒ HỌA MÁY TÍNH
Dương Anh Đức, Lê Đình Duy Các thuật toán vẽ đường 1/22
C
C
a
a
ù
ù
c
ct
t
h
h
u
u
a
a
ä
ä
t
tt
t
o
o
a

a
ã
ã
n
nn
n
h
h
a
a
ä
ä
p
p
• Giả sử tọa độ các điểm nguyên sau khi xấp xỉ đối
tượng thực lần lượt là
(
)
,
0
,
,
=
i
y
x
ii

(điểm đen chính là
(
)
ii
y
x
,
).Hay nói cách khác :
(
)
(
)
1
,
1
,
11
±
±
=
++ iiii
y
x
y
x
.
• Dáng điệu của đường sẽ cho ta gợi ý khi chọn một
trong tám điểm trên. Cách chọn các điểm như thế
nào sẽ tùy thuộc vào từng thuật toán trên cơ sở xem
xét tới vấn đề tối ưu tốc độ.

nv
v
e
e
õ
õđ
đ
ư
ư
ơ
ơ
ø
ø
n
n
g
gt
t
h
h
a

11
,
++ ii
y
x
ở bước thứ (i+1) sẽ là một
trong hai trường hợp như hình vẽ sau :
{ }



+∈
+=
+
+
1,
1
1
1
iii
ii
yyy
xx
• 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 độ.
(x
i
+1, y
i
+1)

o
a
a
ù
ù
n
nD
D
D
D
A
A(
(
D
D
i
i
g
g
i
i
t
t
a


A
A
n
n
a
a
l
l
y
y
z
z
e
e
r
r
)
)
• Việc quyết đònh chọn
1+i
y
là
i
y
hay
1
+
i
y

m
y
i
i
=
++=
+1
1
• Nếu tính trực tiếp giá trò thực y ở mỗi bước từ
phương trình
b
mx
y
+
=
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. Để 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 :
(
)
b
x
m
b
mx
y
iisau
++=+=

Begin
m=Dy/Dx;
x=x1;
y=y1;
putpixel(x, Round(y), c);
x<x2
Yes
No
x=x+1;
y=y+m;
putpixel(x, Round(y),c);
End
ĐỒ HỌA MÁY TÍNH
Dương Anh Đức, Lê Đình Duy Các thuật toán vẽ đường 5/22
• Ví dụ : Cho A(12, 20) và B(22, 27), ta có m= 0.7
i
i
x
x
i
i
y
y
i
i
y
y
0
0
1

2
1
1
4
4
2
2
1
1
2
2
1
1
.
.
4
4
3
3
1
1
5
5
2
2
2
2
2
2
2

8
2
2
0
0
9
9
2
2
1
1
1
1
0
0
2
2
2
2
2
2
7
7
• Cài đặt minh họa thuật toán DDA
#define Round(a) int(a+0.5)
int Color = GREEN;
void LineDDA (int x1, int y1, int x2, int y2)
{
int x = x1;
float y = y1;

a
ù
ù
n
nB
B
r
r
e
e
s
s
e
e
n
n
h
h
a
a
m
m
• Gọi
(
)
y
x

• Xét tất cả các vò trí tương đối của y so với
i
y
và
1
+
i
y
, việc chọn điểm
(
)
11
,
++ ii
y
x
là S hay P phụ thuộc
vào việc so sánh d
1
và d
2
hay dấu của
21
d
d
−
:
♦ Nếu
0
21

2
2
21
−−=−=
ii
y
y
Dx
d
d
Dx
p
(
)
(
)
[
]
1
2
1
2
−
−
+
+
=
⇒
iii
y

m =
vào phương trình trên ta được :
c
Dxy
Dyx
p
iii
+−=
2
2
, với
(
)
Dx
b
Dy
c
1
2
2
−
+
=
.
• Nhận xét rằng nếu tại bước thứ i ta xác đònh được
dấu của
i
p
thì xem như ta xác đònh được điểm cần
chọn ở bước (i+1).

)
iiiiii
y
y
Dx
x
x
Dy
p
p
−
−
−
=
−
⇔
+++ 111
2
2
(
)
1

do

,
2
2
111
+

p
ii
2
1
+
=
+
do ta chọn
ii
y
y
=
+1
.
♦ Ngược lại, nếu
0
≥
i
p
, thì
Dx
Dy
p
p
ii
2
2
1
−
+

c
Dxy
Dyx
p
1
2
2
2
2
2
2
00000
−−+−=+−=
• Do
(
)
00
,
y
x
là điểm nguyên thuộc về đoạn thẳng
nên ta có
bx
Dx
Dy
bmxy +=+=
000
. Thế vào phương
trình trên ta suy ra :
Dx

• Ví dụ : Cho A(12, 20) và B(22, 27),
• Ta có
♦ Dx = 22-12 = 10, Dy=27-20=7
♦ Const1 = 2Dy = 14, Const2 = 2(Dy – Dx) = -6
♦ p
0
= 2Dy – Dx = 14-10 = 4
i
i
x
x
i
i
y
y
i
i
p
p
i
i
0
0
1
1
2
2
2
2
0

2
3
3
1
1
5
5
2
2
2
2
6
6
4
4
1
1
6
6
2
2
3
3
0
0
5
5
1
1
7

5
2
2
8
8
2
2
0
0
2
2
6
6
-
-
4
4
9
9
2
2
1
1
2
2
6
6
1
1
0

để tính
i
p
bằng các phép toán đơn giản trên số nguyên.
♦ Thuật toán này cho kết quả tương tự như thuật toán
DDA.
ĐỒ HỌA MÁY TÍNH
Dương Anh Đức, Lê Đình Duy Các thuật toán vẽ đường 10/22
• Cài đặt minh họa thuật toán Bresenham
void LineBres (int x1, int y1, int x2, int y2)
{
int Dx, Dy, p, Const1, Const2;
int x, y;
Dx = x2 - x1;
Dy = y2 - y1;
p = 2*Dy - Dx; // Dy <<1 - Dx
Const1 = 2*Dy; // Dy <<1
Const2 = 2*(Dy-Dx); // (Dy-Dx) <<1
x = x1;
y = y1;
putpixel(x, y, Color);
for(i=x1; i<x2; i++)
{
if (p<0)
p += Const1;
else
{
p += Const2;
y++;
}
M
M
i
i
d
d
P
P
o
o
i
i
n
n
t
t
• Thuật toán MidPoint đưa ra cách chọn
1+i
y
là
i
y
hay
1
+
i
y
bằng cách so sánh điểm thực Q

x
x
B
y
y
A
−=−−=−=
• Đặt
(
)
C
By
Ax
y
x
F
+
+
=
,
, ta có nhận xét :
( )
(
)
( )
( )










++==
2
1
,12MidPoint2
iii
yxFFp
.
♦ Nếu
0
<
i
p
, điểm MidPoint nằm phía trên đoạn thẳng.
Lúc này điểm thực Q nằm dưới điểm MidPoint nên ta
chọn S, tức là
ii
y
y
=
+1
.
♦ Ngược lại, nếu
0
≥
i

,12
2
1
,12
111 iiiiii
yxFyxFpp
( ) ( )






+






+++−






+



−
−
=
−
+
=
−
⇔
+++ 111
2
2
2
2
• Như vậy :
♦
Dy
p
p
ii
2
1
+
=
+
, nếu
0
<
i
p
do ta chọn

• Ta tính giá trò
0
p

ứng với điểm ban đầu
(
)
00
,
y
x
, với
nhận xét rằng
(
)
00
,
y
x
là điểm thuộc về đoạn thẳng,
tức là có :
0
00
=++
C
By
Ax
( )



B
A
B
A
C
By
Ax
p
−=+=++++=⇒
2
2
2
2
000
ĐỒ HỌA MÁY TÍNH
Dương Anh Đức, Lê Đình Duy Các thuật toán vẽ đường 13/22
C
C
a
a
â
â
u
uh
h
o
o

1
hay d
2
âm hay không ? Cho ví dụ
minh họa.
• Tại sao phải so sánh giá trò p
i
với 0 trong các thuật
toán MidPoint và Bresenham, bản chất của việc so
sánh này là gì ?
• Tại sao phải nhân F(MidPoint) với 2 khi gán cho p
i
theo công thức p
i
=2*F(MidPoint) ?
ĐỒ HỌA MÁY TÍNH
Dương Anh Đức, Lê Đình Duy Các thuật toán vẽ đường 14/22
• Cài đặt thuật toán cho trường hợp 0 ≤ m ≤ 1, Dx<0.
Ta sử dụng thuật toán với trường hợp 0 ≤ m ≤ 1,
Dx>0 đã cài đặt cộng thêm một số thay đổi sau :
♦ Thay biểu thức x=x+1 bằng x=x-1 và y=y+1 bằng y=y-1 vì
trong trường hợp này x và y đều giảm dần.
♦ Nhận xét rằng khi p<0 ta gán p=p+Const1, như vậy để
hướng đến sự cân bằng Const1 phải là một giá trò dương.
Tương tự như vậy, khi p≥0 ta gán p=p+Const2, Const2
phải là giá trò âm.
♦ Từ nhận xét trên, trong các công thức ta sẽ thay Dx
bằng abs(Dx), Dy bằng abs(Dy).
• Mở rộng thuật toán trên để vẽ đoạn thẳng trong
trường hợp m bất kì.

ơ
ø
ø
n
n
g
gt
t
r
r
o
o
ø
ø
n
nb
b
a
a
è
è
n
n
g

M
i
i
d
d
P
P
o
o
i
i
n
n
t
t
• Do tính đối xứng của đường tròn (C) nên ta chỉ cần
vẽ cung (C
1/8
) là cung 1/8 đường tròn, sau đó lấy đối
xứng. Cung (C
1/8
) được mô tả như sau (cung của phần
tô xám trong hình vẽ) :








là điểm nguyên đã tìm
được ở bước thứ i, thì điểm
(
)
11
,
++ ii
y
x
ở bước thứ
(i+1) là sự lựa chọn giữa S và P.
• Như vậy :
{ }



−∈
+=
+
+
1,
1
1
1
iii
ii
yyy
xx
• Đặt
(

i
x
i
+1
Q(x
i
+1, y)
ĐỒ HỌA MÁY TÍNH
Dương Anh Đức, Lê Đình Duy Các thuật toán vẽ đường 17/22
• Xét
( )






−+==
2
1
,1MidPoint
iii
yxFFp
. Ta có :
♦ Nếu
0
<
i
p
, điểm MidPoint nằm trong đường tròn. Lúc


−+−






−+=−
+++
2
1
,1
2
1
,1
111 iiiiii
yxFyxFpp
( ) ( )








−



2
1
1
2
1
1 RyxRyxpp
iiiiii
(
)
(
)
iiiiiii
yyyyxpp −−−++=−⇔
+++ 1
22
11
32
• Vậy :
♦
3
2
1
+
+
=
+ iii
x
p
p
, nếu

do ta chọn
1
1
−=
+ ii
y
y
.
•
0
p

ứng với điểm ban đầu
(
)
(
)
R
y
x
,
0
,
00
=
.
RRFyxFp −=




No
p<0
Yes
p=p+2*x+3;
No
p=p+2(x-y)+5;
y=y-1
x=x+1;
Put8Pixel(x,y,c);
End
ĐỒ HỌA MÁY TÍNH
Dương Anh Đức, Lê Đình Duy Các thuật toán vẽ đường 19/22
Cài đặt minh họa thuật toán MidPoint vẽ đường tròn
void CircleMidPoint (int R)
{
int x, y;
x = 0;
y = R;
Put8Pixel(x, y);
p = 1 - R; // 5/4-R
while (x < y)
{
if (p < 0)
p += 2*x + 3;
else
{
p += 2*(x -y) + 5;
y ;
}
x++;

1
1
D
D
e
e
l
l
t
t
a
a
2
2
0
0
0
0
1
1
5
5
-
-
1
1
4
4
1
1

1
1
4
4
+
+
2
2
*
*
(
(
0
0
)
)
+
+
3
3
5
5
-
-
2
2
3
3
2
2

3
3
7
7
-
-
2
2
1
1
3
3
3
3
1
1
5
5
1
1
-
-
6
6
+
+
2
2
*
*

8
8
1
1
+
+
2
2
*
*
(
(
3
3
-
-
1
1
5
5
)
)
+
+
5
5
1
1
1
1

(
(
4
4
)
)
+
+
3
3
1
1
3
3
-
-
1
1
3
3
6
6
6
6
1
1
4
4
6
6

7
7
7
7
1
1
3
3
-
-
5
5
6
6
+
+
2
2
(
(
6
6
-
-
1
1
4
4
)
)

2
2
(
(
7
7
)
)
+
+
3
3
1
1
9
9
-
-
5
5
9
9
9
9
1
1
2
2
7
7

1
1
1
1
0
0
1
1
0
0
1
1
1
1
6
6
7
7
+
+
2
2
(
(
9
9
-
-
1
1

+
+
2
2
(
(
1
1
0
0
-
-
1
1
1
1
)
)
+
+
5
5
2
2
5
5
7
7
Nhận xét :
• Nếu đặt Delta1 = 2*x+3, Delta2 = 2*(x-y)+5 thì
c
c
o
o
n
n
i
i
c
c
s
sv
v
a
a
ø
øm
m
o
o
ä
ä

n
n
g
gk
k
h
h
a
a
ù
ù
c
c
Phương trình tổng quát của các đường conics có dạng :
0
22
=+++++ FEyDxCyBxyAx
. Giá trò của các hằng
số A, B, C, D, E, F sẽ quyết đònh dạng của đường conics, cụ
thể là nếu:





>
=


+∈
+=
+
+
(*) 1,
1
1
1
iii
ii
yyy
xx
♦ Nếu
0
)
(
'
1
≤
≤
−
x
f
thì
{ }



−∈

1
1
iii
ii
xxx
yy
♦ Nếu
1
)
(
'
−<
x
f
thì
{ }



−∈
+=
+
+
(*) 1,
1
1
1
iii
ii
xxx

p
cần phải chú ý sao cho thao tác tính
i
p
sau
này hạn chế phép toán trên số thực.
• Bước 4 : Tìm mối liên quan của
1+i
p
và
i
p
bằng
cách xét hiệu
ii
p
p
−
+1
.
• Bước 5 : Tính
0
p
và hoàn chỉnh thuật toán.
B
B
a
a
ø
ø

≤≤
≤≤
2
2
0
2
2
Ry
RxR
• p dụng các bước trên để vẽ đoạn thẳng trong
trường hợp tổng quát.
• Hãy trình bày khung chính của thuật toán vẽ ellipse,
parabol, hyperbol dựa vào các bước trên.