ĐỒ 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
1
2
2
2
2
0
0
2
2
0
0
1
1
1
1
3
3
2
2
1
1
2
2
0
0
.
.
7
7
2
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
2
.
.
1
1
4
4
1
1
6
6
5
5
1
1
7
7
6
6
1
1
8
8
7
7
1
1
9
9
8
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;
float m = float(y2-y1)/(x2-x1);
putpixel(x, Round(y), Color);
for(int i=x1; i<x2; i++)
{
x++;
y +=m;
putpixel(x, Round(y), Color);
}
} // LineDDA
ĐỒ HỌA MÁY TÍNH
Dương Anh Đức, Lê Đình Duy Các thuật toán vẽ đường 6/22
T
T
h
h
u
u
a
a
ä
ä
t
t
t
t
o
o
a
a
ù
ù
n
n
B
B
r
r
e
e
s
s
e
e
n
n
h
h
a
a
m
m
• Gọi
( )
yx
i
,1+
là điểm thuộc đoạn thẳng. Ta có:
( )
bxmy
i
++= 1
.
• Đặt
( )
yyd
yyd
i
i
−+=
−=
1
2
1
• 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
yx
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
dd −
:
♦ Nếu
0
21
<− dd
, ta sẽ chọn điểm S, tức là
ii
yy =
+1
.
♦ Ngược lại, nếu
0
21
≥− dd
, ta sẽ chọn điểm P, tức là
1
1
+=
+ ii
yy
• Xét
( ) ( )
122
21
−−=−=
ii
yyDxddDxp
( )( )
[ ]
1212 −−++=⇒
iii
ybxmDxp
(x
i
+1, y)
P
S
x
i
x
i
+1
y
i
y
i
+1
y
d
1
d
2
ĐỒ HỌA MÁY TÍNH
Dương Anh Đức, Lê Đình Duy Các thuật toán vẽ đường 7/22
• Thay
Dx
Dy
m =
vào phương trình trên ta được :
cDxyDyxp
iii
+−= 22
, với
( )
DxbDyc 122 −+=
.
• 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).
• Ta có :
( ) ( )
cDxyDyxcDxyDyxpp
iiiiii
+−−+−=−
+++
2222
111
( ) ( )
iiiiii
yyDxxxDypp −−−=−⇔
+++ 111
22
( )
1 do ,22
111
+=−−=−⇔
+++ iiiiii
xxyyDxDypp
• Từ đây ta có thể suy ra cách tính
1+i
p
từ
i
p
như sau :
♦ Nếu
0<
i
p
thì
Dypp
ii
2
1
+=
+
do ta chọn
ii
yy =
+1
.
♦ Ngược lại, nếu
0≥
i
p
, thì
DxDypp
ii
22
1
−+=
+
, do
ta chọn
1
1
+=
+ ii
yy
.
• Giá trò
0
p
được tính từ điểm vẽ đầu tiên
( )
00
, yx
theo công thức :
( )
DxbDyDxyDyxcDxyDyxp 1222222
00000
−−+−=+−=
• Do
( )
00
, yx
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 :
DxDyp −= 2
0
.
ĐỒ HỌA MÁY TÍNH
Dương Anh Đức, Lê Đình Duy Các thuật toán vẽ đường 8/22
Lưu đồ thuật toán Bresenham
Begin
p=2Dy-Dx;
Const1=2Dy;
Const2=2(Dy-Dx);
x=x1;
y=y1;
putpixel(x, y, c);
x<x2
Yes
No
p<0
Yes
p=p+Const1;
No
p=p+Const2;
y=y+1
x=x+1;
putpixel(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 9/22
• 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
0
4
4
1
1
1
1
3
3
2
2
1
1
-
-
2
2
2
2
1
1
4
4
2
2
1
1
1
1
2
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
7
2
2
4
4
-
-
6
6
6
6
1
1
8
8
2
2
4
4
8
8
7
7
1
1
9
9
2
2
5
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
0
1
1
0
0
2
2
2
2
2
2
7
7
4
4
• Nhận xét
♦ Thuật toán Bresenham chỉ làm việc trên số nguyên và
các thao tác trên số nguyên chỉ là phép cộng và phép
dòch bit (phép nhân 2) điều này là một cải tiến làm tăng
tốc độ đáng kể so với thuật toán DDA. Ý tưởng chính của
thuật toán nằm ở chỗ xét dấu
i
p
để quyết đònh điểm kế
tiếp, và sử dụng công thức truy hồi
ii
pp −
+1
để 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++;
}
x++;
putpixel(x, y, Color);
}
} // LineBres
ĐỒ HỌA MÁY TÍNH
Dương Anh Đức, Lê Đình Duy Các thuật toán vẽ đường 11/22
T
T
h
h
u
u
a
a
ä
ä
t
t
t
t
o
o
a
a
ù
ù
n
n
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
( )
yx
i
,1+
với điểm MidPoint là trung điểm của S và P. Ta có :
♦ Nếu điểm Q nằm dưới điểm MidPoint, ta chọn S.
♦ Nếu điểm Q nằm trên điểm MidPoint ta chọn P.
• Ta có dạng tổng quát của phương trình đường thẳng :
0=++ CByAx
với
( )
21121212
,, yxyxCxxByyA −=−−=−=
• Đặt
( )
CByAxyxF ++=,
, ta có nhận xét :
( )
( )
( )
( )
>
=
<
thẳng. đường dưới phía nằm yx, nếu,0
thẳng đường vềthuộc yx, nếu,0
thẳng đường trên phía nằm yx, nếu,0
, yxF
Q(x
i
+1, y)
P
S
x
i
x
i
+1
y
i
y
i
+1
MidPoint
ĐỒ HỌA MÁY TÍNH
Dương Anh Đức, Lê Đình Duy Các thuật toán vẽ đường 12/22
• Lúc này việc chọn các điểm S, P ở trên được đưa về
việc xét dấu của
( )
++==
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
yy =
+1
.
♦ Ngược lại, nếu
0≥
i
p
, điểm MidPoint nằm phía dưới
đoạn thẳng. Lúc này điểm thực Q nằm trên điểm
MidPoint nên ta chọn P, tức là
1
1
+=
+ ii
yy
.
• Mặt khác :
++−
++=−
+++
2
1
,12
2
1
,12
111 iiiiii
yxFyxFpp
( ) ( )
+
+++−
+
+++=−⇔
+++
CyBxACyBxApp
iiiiii
2
1
12
2
1
12
111
( ) ( )
iiiiii
yyDxDyyyBApp −−=−+=−⇔
+++ 111
2222
• Như vậy :
♦
Dypp
ii
2
1
+=
+
, nếu
0<
i
p
do ta chọn
ii
yy =
+1
.
♦
DxDypp
ii
22
1
−+=
+
, nếu
0≥
i
p
do ta chọn
1
1
+=
+ ii
yy
.
• Ta tính giá trò
0
p
ứng với điểm ban đầu
( )
00
, yx
, với
nhận xét rằng
( )
00
, yx
là điểm thuộc về đoạn thẳng,
tức là có :
0
00
=++ CByAx
( )
+
+++=
++= CyBxAyxFp
2
1
12
2
1
,12
00000
( )
DxDyBABACByAxp −=+=++++=⇒ 2222
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
u
h
h
o
o
û
û
i
i
k
k
i
i
e
e
å
å
m
m
t
t
r
r
a
a
• Xét thuật toán Bresenham, với cách đặt d
1
và d
2
như
trên, có khi nào d
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ì.
♦ Trường hợp đặc biệt m=∞ : Đoạn thẳng song song trục
tung nên rất đơn giản khi vẽ.
♦ Trường hợp –1 ≤ m ≤ 1 : Sử dụng các công thức của thuật
toán vẽ trong trường hợp 0≤ m ≤ 1, Dx>0 và thay đổi một
số điểm sau :
v Nếu Dx<0 thì bước nhảy của x sẽ thay bằng –1.
Tương tự nếu Dy<0, bước nhảy của y cũng sẽ là –1.
v Thay Dx bằng abs(Dx), Dy=abs(Dy) trong tất cả các
công thức có chứa Dx, Dy.
♦ Trường hợp m ≤ -1 hay m ≥ 1 :
v Thay đổi vai trò của x và y, nghóa là thay x bằng y, y
bằng x, Dx bằng Dy, Dy bằng Dx trong tất cả các
công thức.
v Thực hiện nguyên tắc về bước nhảy, thay đổi công
thức Dx, Dy như trong trường hợp –1 ≤ m ≤ 1
Không có nhận xét nào:
Đăng nhận xét