Download miễn phí Bài giảng Đồ họa máy tính - Các thuật toán vễ đường
Câu hỏi kiểm tra
· Xét thuật toán Bresenham, với cách đặt d1và d2nhưtrên, có khi nào d1hay d2
âm hay không ? Cho ví dụminh họa.
· Tại sao phải so sánh giá trị pi 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 bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
ĐỒ HỌA MÁY TÍNHDương Anh Đức, Lê Đình Duy Các thuật toán vẽ đường 1/22
Cáùc thuậät toáùn vẽõ đườøng
Dẫãn nhậä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,, =iyx ii . Đây là các điểm
nguyên sẽ được hiển thị trên màn hình.
· Bài toán đặt ra là nếu biết được ( )ii yx , là tọa độ
nguyên xác định ở bước thứ i, điểm nguyên tiếp theo
( )11 , ++ ii yx sẽ được xác định như thế nào.
· Đối tượng hiển thị trên lưới nguyên được liền nét,
các điểm mà ( )11 , ++ ii yx có thể chọn chỉ là một trong
tám điểm được đánh số từ 1 đến 8 trong hình sau
(điểm đen chính là ( )ii yx , ).Hay nói cách khác :
( ) ( )1,1, 11 ±±=++ iiii yxyx .
· 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 độ.
1
23
876
5
4
ĐỒ HỌA MÁY TÍNH
Dương Anh Đức, Lê Đình Duy Các thuật toán vẽ đường 2/22
Thuậät toáùn vẽõ đườøng thẳúng
· Xét đoạn thẳng có hệ số góc 10 Dx .
· Với các đoạn thẳng dạng này, nếu ( )ii yx , là điểm
đã xác định được ở bước thứ i (điểm màu đen) thì
điểm cần chọn ( )11 , ++ ii yx ở 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 độ.
(xi+1, yi+1)
1
2
(xi+1, yi)
xi
yi
ĐỒ HỌA MÁY TÍNH
Dương Anh Đức, Lê Đình Duy Các thuật toán vẽ đường 3/22
Thuậät toáùn DDA (Digital Differential Analyzer)
· Việc quyết định chọn 1+iy là iy hay 1+iy , dựa vào
phương trình của đoạn thẳng bmxy += . Nghĩa là,
ta sẽ tính tọa độ của điểm ( )yxi ,1+ thuộc về đoạn
thẳng thực. Tiếp đó, 1+iy sẽ là giá trị sau khi làm
tròn giá trị tung độ y.
· Như vậy :
( )
( )yRoundy
bxmy
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 bmxy += 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 : ( ) bxmbmxy iisau ++=+= + 11
bmxy itrước +=
myy trướcsau +=Þ
(xi, yi)
(xi+1, y)
(xi+1, Round(y))
ĐỒ HỌA MÁY TÍNH
Dương Anh Đức, Lê Đình Duy Các thuật toán vẽ đường 4/22
Lưu đồ thuật toán DDA
Begin
m=Dy/Dx;
x=x1;
y=y1;
putpixel(x, Round(y), c);
x
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 xi yi y
0 12 20 20
1 13 21 20.7
2 14 21 21.4
3 15 22 22.1
4 16
5 17
6 18
7 19
8 20
9 21
10 22 27
· 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
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
Thuậät toáùn Bresenham
· Gọi ( )yxi ,1+ là điểm thuộc đoạn thẳng. Ta có:
( ) bxmy i ++= 1 .
· Đặt ( ) yyd
yyd
i
i
-+=
-=
12
1
· Xét tất cả các vị trí tương đối của y so với iy và
1+iy , việc chọn điểm ( )11 , ++ ii yx là S hay P phụ thuộc
vào việc so sánh d1 và d2 hay dấu của 21 dd - :
¨ Nếu 021 <- dd , ta sẽ chọn điểm S, tức là ii yy =+1 .
¨ Ngược lại, nếu 021 ³- dd , ta sẽ chọn điểm P, tức là
11 +=+ ii yy
· Xét ( ) ( )12221 --=-= ii yyDxddDxp
( )( )[ ]1212 --++=Þ iii ybxmDxp
(xi+1, y)
P
S
xi xi+1
yi
yi+1
y
d1
d2
ĐỒ 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
Dym = 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 ip 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+ip từ ip như sau :
¨ Nếu 0
ta chọn 11 +=+ ii yy .
· Giá trị 0p đượ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ó bxDx
Dybmxy +=+= 000 . Thế vào phương
trình trên ta suy ra : DxDyp -= 20 .
ĐỒ 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
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
¨ p0 = 2Dy – Dx = 14-10 = 4
i xi yi pi
0 12 20 4
1 13 21 -2
2 14 21 12
3 15 22 6
4 16 23 0
5 17 24 -6
6 18 24 8
7 19 25 2
8 20 26 -4
9 21 26 10
10 22 27 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 ip để quyết định điểm kế
tiếp, và sử dụng công thức truy hồi ii pp -+1 để tính ip
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
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
Thuậät toáùn MidPoint
· Thuật toán MidPoint đưa ra cách chọn 1+iy là iy
hay 1+iy bằng cách so sánh điểm thực Q ( )yxi ,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(xi+1, y)
P
S
xi xi+1
yi
yi+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
chọn S, tức là ii yy =+1 .
¨ Ngược lại, nếu 0³ip , đ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 ...