›
›

Bài giảng Đồ họa máy tính - Các thuật toán vẽ đường

Download
ÑOÀ HOÏA MAÙY TÍNH  
Caùc thuaät toaùn veõ ñöôøng  
ù ä ù õ ø  
Daãn nhaäp  
ã
ä
· Giaû söû toïa ñoä caùc ñieåm nguyeân sau khi xaáp xæ ñoái  
(
xi , yi ,i = 0,...  
)
töôïng thöïc laàn löôït laø  
. Ñaây laø caùc ñieåm  
nguyeân seõ ñöôïc hieån thò treân maøn hình.  
(
xi , yi  
nguyeân xaùc ñònh ôû böôùc thöù i, ñieåm nguyeân tieáp theo  
xi+1, yi+1  
)
· Baøi toaùn ñaët ra laø neáu bieát ñöôïc  
laø toïa ñoä  
(
)
seõ ñöôïc xaùc ñònh nhö theá naøo.  
· Ñoái töôïng hieån thò treân löôùi nguyeân ñöôïc lieàn neùt,  
(
xi+1, yi+1  
)
coù theå choïn chæ laø moät trong  
caùc ñieåm maø  
taùm ñieåm ñöôïc ñaùnh soá töø 1 ñeán 8 trong hình sau  
(
xi , yi
)  
(ñieåm ñen chính laø  
xi+1, yi+1 xi ± 1, yi ± 1  
)
.
).Hay noùi caùch khaùc :  
(
)
=
(
4
5
6
3
2
1
8
7
· Daùng ñieäu cuûa ñöôøng seõ cho ta gôïi yù khi choïn moät  
trong taùm ñieåm treân. Caùch choïn caùc ñieåm nhö theá  
naøo seõ tuøy thuoäc vaøo töøng thuaät toaùn treân cô sôû xem  
xeùt tôùi vaán ñeà toái öu toác ñoä.  
Döông Anh Ñöùc, Leâ Ñình Duy  
Caùc thuaät toaùn veõ ñöôøng 1/22  
ÑOÀ HOÏA MAÙY TÍNH  
Thuaät toaùn veõ ñöôøng thaúng  
ä ù õ ø ú  
0 < m < 1  
Dx > 0  
· Xeùt ñoaïn thaúng coù heä soá goùc  
vaø  
.
(
xi , yi  
)
laø ñieåm  
· Vôùi caùc ñoaïn thaúng daïng naøy, neáu  
ñaõ xaùc ñònh ñöôïc ôû böôùc thöù i (ñieåm maøu ñen) thì  
xi+1, yi+1  
(
)
ôû böôùc thöù (i+1) seõ laø moät  
ñieåm caàn choïn  
trong hai tröôøng hôïp nhö hình veõ sau :  
x = x + 1  
yi+1 Î {yi , yi + 1}  
ì
í
î
i+1  
i
(xi+1, yi+1)  
2
1
yi  
(xi+1, yi)  
xi  
· Vaán ñeà coøn laïi, laø caùch choïn moät trong hai ñieåm treân  
nhö theá naøo ñeå coù theå toái öu veà maët toác ñoä.  
Döông Anh Ñöùc, Leâ Ñình Duy  
Caùc thuaät toaùn veõ ñöôøng 2/22  
ÑOÀ HOÏA MAÙY TÍNH  
Thuaät toaùn DDA (Digital Differential Analyzer)  
ä
ù
yi+1  
yi  
y + 1  
· Vieäc quyeát ñònh choïn  
laø  
hay  
y = mx + b  
, döïa vaøo  
i
phöông trình cuûa ñoaïn thaúng  
. Nghóa laø,  
(
xi + 1, y
)
 
thuoäc veà ñoaïn  
ta seõ tính toïa ñoä cuûa ñieåm  
yi+1  
thaúng thöïc. Tieáp ñoù,  
seõ laø giaù trò sau khi laøm  
troøn giaù trò tung ñoä y.  
y = m  
(
xi + 1  
)
+ b  
· Nhö vaäy :  
yi+1 = Round(y)  
(xi+1, Round(y))  
(xi+1, y)  
(xi, yi)  
· Neáu tính tröïc tieáp giaù trò thöïc y ôû moãi böôùc töø  
y = mx + b  
phöông trình  
thì phaûi caàn moät pheùp toaùn  
nhaân vaø moät pheùp toaùn coäng soá thöïc. Ñeå caûi thieän  
toác ñoä, ngöôøi ta tính giaù trò thöïc cuûa y ôû moãi böôùc  
theo caùch sau ñeå khöû pheùp tính nhaân treân soá thöïc :  
ysau = mxi+1 + b = m  
ytröôùc = mxi + b  
Þ ysau = ytröôùc + m  
(
xi + 1
)
+ b  
· Nhaän xeùt raèng :  
Döông Anh Ñöùc, Leâ Ñình Duy  
Caùc thuaät toaùn veõ ñöôøng 3/22  
ÑOÀ HOÏA MAÙY TÍNH  
Löu ñoà thuaät toaùn DDA  
Begin  
m=Dy/Dx;  
x=x1;  
y=y1;  
putpixel(x, Round(y), c);  
No  
x<x2  
Yes  
x=x+1;  
y=y+m;  
putpixel(x, Round(y),c);  
End  
Döông Anh Ñöùc, Leâ Ñình Duy  
Caùc thuaät toaùn veõ ñöôøng 4/22  
ÑOÀ HOÏA MAÙY TÍNH  
· Ví duï : Cho A(12, 20) vaø B(22, 27), ta coù m= 0.7  
i
0
1
2
3
4
5
6
7
8
9
10  
xi  
yi  
y
20  
20.7  
21.4  
22.1  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
20  
21  
21  
22  
27  
· Caøi ñaët minh hoïa thuaät toaù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  
Döông Anh Ñöùc, Leâ Ñình Duy  
Caùc thuaät toaùn veõ ñöôøng 5/22  
ÑOÀ HOÏA MAÙY TÍNH  
Thuaät toaùn Bresenham  
ä
ù
(xi+1, y)  
P
yi+1  
y
d2  
d1  
S
yi  
xi  
xi+1  
(
xi + 1, y
)
 
· Goïi  
laø ñieåm thuoäc ñoaïn thaúng. Ta coù:  
(
xi + 1
)
+ b  
y = m  
.
d1 = y - yi  
( )  
d2 = yi + 1 - y  
· Ñaët  
yi  
· Xeùt taát caû caùc vò trí töông ñoái cuûa y so vôùi  
vaø  
laø S hay P phuï thuoäc  
d1 - d2  
y + 1  
xi+1, yi+1  
( )  
, vieäc choïn ñieåm  
vaøo vieäc so saùnh d1 vaø d2 hay daáu cuûa  
i
:
yi+1 = yi  
.
d - d < 0  
¨ Neáu  
, ta seõ choïn ñieåm S, töùc laø  
1
2
d - d ³ 0  
¨ Ngöôïc laïi, neáu  
yi+1 = yi + 1  
, ta seõ choïn ñieåm P, töùc laø  
1
2
pi = Dx  
(
d1 - d2  
)
= Dx  
(
2y - 2yi - 1  
)
· Xeùt  
Þ pi = Dx  
[
2
(
m  
(
xi + 1  
)
+ b  
)
- 2yi - 1  
]
Döông Anh Ñöùc, Leâ Ñình Duy  
Caùc thuaät toaùn veõ ñöôøng 6/22  
ÑOÀ HOÏA MAÙY TÍNH  
Dy  
Dx  
m =  
· Thay  
vaøo phöông trình treân ta ñöôïc :  
p = 2Dyx - 2Dxy + c  
(
)
c = 2Dy + 2b- 1 Dx  
, vôùi  
.
i
i
i
· Nhaän xeùt raèng neáu taïi böôùc thöù i ta xaùc ñònh ñöôïc  
pi  
daáu cuûa  
thì xem nhö ta xaùc ñònh ñöôïc ñieåm caàn  
choïn ôû böôùc (i+1).  
· Ta coù :  
pi+1 - pi =  
(
2Dyxi+1 - 2Dxyi+1 + c  
)
-
(
2Dyxi - 2Dxyi + c  
)
Û pi+1 - pi = 2Dy  
(
xi+1 - xi  
)
- 2Dx  
(
yi+1 - yi
)  
Û pi+1 - pi = 2Dy- 2Dx  
(
yi+1 - yi  
)
, do xi+1 = xi + 1  
pi  
pi+1  
· Töø ñaây ta coù theå suy ra caùch tính  
töø  
nhö sau :  
pi < 0  
yi+1 = yi  
pi+1 = pi + 2Dy  
¨ Neáu  
thì  
do ta choïn  
.
p ³ 0  
pi+1 = p + 2Dy - 2Dx  
¨ Ngöôïc laïi, neáu  
, thì  
.
, do  
i
i
y = y + 1  
ta choïn  
i+1  
i
p0  
(
ñöôïc tính töø ñieåm veõ ñaàu tieân  
x0 , y0
)  
· Giaù trò  
theo coâng thöùc :  
p0 = 2Dyx0 - 2Dxy0 + c = 2Dyx0 - 2Dxy0 + 2Dy- 2b- 1 Dx  
( )  
(
x0 , y0  
)
laø ñieåm nguyeân thuoäc veà ñoaïn thaúng  
· Do  
Dy  
y0 = mx0 + b =  
x0 + b  
neân ta coù  
. Theá vaøo phöông  
Dx  
p = 2Dy - Dx  
trình treân ta suy ra :  
.
0
Döông Anh Ñöùc, Leâ Ñình Duy  
Caùc thuaät toaùn veõ ñöôøng 7/22  
ÑOÀ HOÏA MAÙY TÍNH  
Löu ñoà thuaät toaùn Bresenham  
Begin  
p=2Dy-Dx;  
Const1=2Dy;  
Const2=2(Dy-Dx);  
x=x1;  
y=y1;  
putpixel(x, y, c);  
No  
x<x2  
Yes  
No  
p<0  
Yes  
p=p+Const1;  
p=p+Const2;  
y=y+1  
x=x+1;  
putpixel(x,y,c);  
End  
Döông Anh Ñöùc, Leâ Ñình Duy  
Caùc thuaät toaùn veõ ñöôøng 8/22  
ÑOÀ HOÏA MAÙY TÍNH  
· Ví duï : Cho A(12, 20) vaø B(22, 27),  
· Ta coù  
¨ Dx = 22-12 = 10, Dy=27-20=7  
¨ Const1 = 2Dy = 14, Const2 = 2(Dy – Dx) = -6  
¨ p0 = 2Dy – Dx = 14-10 = 4  
i
0
1
2
3
4
5
6
7
8
9
10  
xi  
yi  
pi  
4
-2  
12  
6
0
-6  
8
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
20  
21  
21  
22  
23  
24  
24  
25  
26  
26  
27  
2
-4  
10  
4
· Nhaän xeùt  
¨ Thuaät toaùn Bresenham chæ laøm vieäc treân soá nguyeân vaø  
caùc thao taùc treân soá nguyeân chæ laø pheùp coäng vaø pheùp  
dòch bit (pheùp nhaân 2) ñieàu naøy laø moät caûi tieán laøm taêng  
toác ñoä ñaùng keå so vôùi thuaät toaùn DDA. YÙ töôûng chính cuûa  
pi  
thuaät toaùn naèm ôû choã xeùt daáu  
tieáp, vaø söû duïng coâng thöùc truy hoài  
baèng caùc pheùp toaùn ñôn giaûn treân soá nguyeân.  
ñeå quyeát ñònh ñieåm keá  
pi+1 - pi  
pi  
ñeå tính  
¨ Thuaät toaùn naøy cho keát quaû töông töï nhö thuaät toaùn  
DDA.  
Döông Anh Ñöùc, Leâ Ñình Duy  
Caùc thuaät toaùn veõ ñöôøng 9/22  
ÑOÀ HOÏA MAÙY TÍNH  
· Caøi ñaët minh hoïa thuaät toaùn Bresenham  
void LineBres (int x1, int y1, int x2, int y2)  
{
int Dx, Dy, p, Const1, Const2;  
int x, y;  
Dx  
Dy  
= x2 - x1;  
= 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  
Döông Anh Ñöùc, Leâ Ñình Duy  
Caùc thuaät toaùn veõ ñöôøng 10/22  
ÑOÀ HOÏA MAÙY TÍNH  
Thuaät toaùn MidPoint  
ä
ù
yi+1  
yi  
)
· Thuaät toaùn MidPoint ñöa ra caùch choïn  
laø  
(
xi + 1, y  
baèng caùch so saùnh ñieåm thöïc Q  
yi + 1  
hay  
vôùi ñieåm MidPoint laø trung ñieåm cuûa S vaø P. Ta coù :  
¨ Neáu ñieåm Q naèm döôùi ñieåm MidPoint, ta choïn S.  
¨ Neáu ñieåm Q naèm treân ñieåm MidPoint ta choïn P.  
Q(xi+1, y)  
P
yi+1  
yi  
MidPoint  
S
xi  
xi+1  
· Ta coù daïng toång quaùt cuûa phöông trình ñöôøng thaúng :  
Ax + By + C = 0  
A = y2 - y1, B = - x2 - x1 ,C = x2 y1 - x1 y2  
( )  
vôùi  
F x, y = Ax + By + C  
( )  
· Ñaët  
, ta coù nhaän xeùt :  
ì
ï
< 0,neáu  
= 0,neáu  
> 0,neáu  
(
(
(
x,y  
x,y  
x,y  
)
)
)
naèm phía treân ñöôøng thaúng  
thuoäc veàñöôøng thaúng  
naèm phía döôùi ñöôøng thaúng.  
F
(
x, y  
)
í
ï
î
Döông Anh Ñöùc, Leâ Ñình Duy  
Caùc thuaät toaùn veõ ñöôøng 11/22  
ÑOÀ HOÏA MAÙY TÍNH  
· Luùc naøy vieäc choïn caùc ñieåm S, P ôû treân ñöôïc ñöa veà  
1
æ
ö
pi = 2F  
(
MidPoint = 2F x +1, y +  
)
ç
÷
i
i
vieäc xeùt daáu cuûa  
.
2
è
ø
p < 0  
¨ Neáu  
, ñieåm MidPoint naèm phía treân ñoaïn thaúng.  
i
Luùc naøy ñieåm thöïc Q naèm döôùi ñieåm MidPoint neân ta  
y = y  
choïn S, töùc laø  
.
i+1  
i
p ³ 0  
¨ Ngöôïc laïi, neáu  
, ñieåm MidPoint naèm phía döôùi  
i
ñoaïn thaúng. Luùc naøy ñieåm thöïc Q naèm treân ñieåm  
y = y + 1  
MidPoint neân ta choïn P, töùc laø  
.
i+1  
i
· Maët khaùc :  
1
2
1
2
æ
ö
÷
ø
æ
ö
÷
ø
pi+1 - p = 2F x + 1, yi+1  
+
- 2F x + 1, y +  
ç
ç
i
i+1  
i
i
è
è
é
ù
é
ù
1
2
1
2
æ
ö
÷
æ
ö
÷
ø
)
Û p - p = 2 A  
(
xi+1 + 1  
)
+ B y +  
+ C - 2 A  
(
xi + 1  
)
+ B y +  
+ C  
ç
ç
i+1  
i
i+1  
i
ê
ú
ê
ú
è
ø
è
ë
û
ë
û
Û pi+1 - pi = 2A + 2B  
(
yi+1 - yi  
)
= 2Dy - 2Dx
(
yi+1 - yi  
· Nhö vaäy :  
pi < 0  
yi+1 = yi  
.
pi+1 = p + 2Dy  
¨
¨
, neáu  
do ta choïn  
i
pi ³ 0  
pi+1 = p + 2Dy - 2Dx  
,
neáu  
do  
ta  
choïn  
i
yi+1 = y + 1  
.
i
p0  
(
(
x0, y0
)  
, vôùi  
· Ta tính giaù trò  
öùng vôùi ñieåm ban ñaàu  
x0 , y0  
)
nhaän xeùt raèng  
laø ñieåm thuoäc veà ñoaïn thaúng,  
Ax + By + C = 0  
töùc laø coù :  
0
0
é
ù
1
2
1
2
æ
ö
÷
ø
æ
ö
÷
ø
p = 2F x + 1, y +  
= 2 A  
(
x0 + 1  
)
+ B y +  
+ C  
ç
ç
0
0
0
0
ê
ú
è
è
ë
û
Þ p0 = 2  
(
Ax0 + By0 + C  
)
+ 2A + B = 2A + B = 2Dy - Dx  
Döông Anh Ñöùc, Leâ Ñình Duy  
Caùc thuaät toaùn veõ ñöôøng 12/22  
ÑOÀ HOÏA MAÙY TÍNH  
Caâu hoûi kieåm tra  
â
û
å
· Xeùt thuaät toaùn Bresenham, vôùi caùch ñaët d1 vaø d2 nhö  
treân, coù khi naøo d1 hay d2 aâm hay khoâng ? Cho ví duï  
minh hoïa.  
· Taïi sao phaûi so saùnh giaù trò pi vôùi 0 trong caùc thuaät  
toaùn MidPoint vaø Bresenham, baûn chaát cuûa vieäc so  
saùnh naøy laø gì ?  
· Taïi sao phaûi nhaân F(MidPoint) vôùi 2 khi gaùn cho pi  
theo coâng thöùc pi=2*F(MidPoint) ?  
Döông Anh Ñöùc, Leâ Ñình Duy  
Caùc thuaät toaùn veõ ñöôøng 13/22  
ÑOÀ HOÏA MAÙY TÍNH  
· Caøi ñaët thuaät toaùn cho tröôøng hôïp 0 £ m £ 1, Dx<0.  
Ta söû duïng thuaät toaùn vôùi tröôøng hôïp 0 £ m £ 1,  
Dx>0 ñaõ caøi ñaët coäng theâm moät soá thay ñoåi sau :  
¨ Thay bieåu thöùc x=x+1 baèng x=x-1 vaø y=y+1 baèng y=y-1 vì  
trong tröôøng hôïp naøy x vaø y ñeàu giaûm daàn.  
¨ Nhaän xeùt raèng khi p<0 ta gaùn p=p+Const1, nhö vaäy ñeå  
höôùng ñeán söï caân baèng Const1 phaûi laø moät giaù trò döông.  
Töông töï nhö vaäy, khi p³ 0 ta gaùn p=p+Const2, Const2  
phaûi laø giaù trò aâm.  
¨ Töø nhaän xeùt treân, trong caùc coâng thöùc ta seõ thay Dx  
baèng abs(Dx), Dy baèng abs(Dy).  
· Môû roäng thuaät toaùn treân ñeå veõ ñoaïn thaúng trong  
tröôøng hôïp m baát kì.  
¨ Tröôøng hôïp ñaëc bieät m=¥ : Ñoaïn thaúng song song truïc  
tung neân raát ñôn giaûn khi veõ.  
¨ Tröôøng hôïp –1 £ m £ 1 : Söû duïng caùc coâng thöùc cuûa thuaät  
toaùn veõ trong tröôøng hôïp 0£ m £ 1, Dx>0 vaø thay ñoåi moät  
soá ñieåm sau :  
v Neáu Dx<0 thì böôùc nhaûy cuûa x seõ thay baèng –1.  
Töông töï neáu Dy<0, böôùc nhaûy cuûa y cuõng seõ laø –1.  
v Thay Dx baèng abs(Dx), Dy=abs(Dy) trong taát caû caùc  
coâng thöùc coù chöùa Dx, Dy.  
¨ Tröôøng hôïp m £ -1 hay m ³ 1 :  
v Thay ñoåi vai troø cuûa x vaø y, nghóa laø thay x baèng y, y  
baèng x, Dx baèng Dy, Dy baèng Dx trong taát caû caùc  
coâng thöùc.  
v Thöïc hieän nguyeân taéc veà böôùc nhaûy, thay ñoåi coâng  
thöùc Dx, Dy nhö trong tröôøng hôïp –1 £ m £ 1  
Döông Anh Ñöùc, Leâ Ñình Duy  
Caùc thuaät toaùn veõ ñöôøng 14/22  
ÑOÀ HOÏA MAÙY TÍNH  
Veõ ñöôøng troøn baèng thuaät toaùn MidPoint  
õ
ø
ø
è
ä
ù
· Do tính ñoái xöùng cuûa ñöôøng troøn (C) neân ta chæ caàn  
veõ cung (C1/8) laø cung 1/8 ñöôøng troøn, sau ñoù laáy ñoái  
xöùng. Cung (C1/8) ñöôïc moâ taû nhö sau (cung cuûa phaàn  
toâ xaùm trong hình veõ) :  
ì
2
2
0 £ x £ R  
ï
ï
í
ï
2
R
£ y £ R  
ï
2
î
(-x,y)  
(x,y)  
(-y,x)  
(y,x)  
R
2
(-y,-x)  
(y,-x)  
(-x,-y)  
(x,-y)  
· Nhö vaäy neáu coù (x, y) Î (C1/8) thì caùc ñieåm : (y, x), (y,-  
x), (x,-y), (-x,-y), (-y,-x), (-y,x), (-x,y) seõ thuoäc (C).  
Döông Anh Ñöùc, Leâ Ñình Duy  
Caùc thuaät toaùn veõ ñöôøng 15/22  
ÑOÀ HOÏA MAÙY TÍNH  
· Choïn ñieåm baét ñaàu ñeå veõ laø ñieåm (0,R).  
(
xi , yi
)  
laø ñieåm nguyeân ñaõ tìm  
· Döïa vaøo hình veõ, neáu  
ñöôïc ôû böôùc thöù i, thì ñieåm  
(i+1) laø söï löïa choïn giöõa S vaø P.  
(
xi+1, yi+1
)  
ôû böôùc thöù  
x = x + 1  
ì
í
î
i+1  
i
· Nhö vaäy :  
yi+1 Î  
{yi , yi - 1}  
Q(xi+1, y)  
S
yi  
MidPoint  
P
yi-1  
xi  
xi+1  
F
(
x, y
)  
= x2 + y2 - R2  
, ta coù :  
· Ñaët  
ì < 0,neáu  
(
(
(
x,y  
x,y  
x,y  
)
)
)
naèm trong ñöôøng troøn  
naèm treân ñöôøng troøn  
naèm ngoaøi ñöôøng troøn.  
ï
F
(
x, y  
)
= 0,neáu  
> 0,neáu  
í
ï
î
Döông Anh Ñöùc, Leâ Ñình Duy  
Caùc thuaät toaùn veõ ñöôøng 16/22  
ÑOÀ HOÏA MAÙY TÍNH  
1
2
æ
ö
÷
ø
pi = F  
(MidPoint  
)
= F x + 1, y -  
ç
i
i
· Xeùt  
. Ta coù :  
è
p < 0  
¨ Neáu  
, ñieåm MidPoint naèm trong ñöôøng troøn. Luùc  
i
naøy ñieåm thöïc Q gaàn S hôn neân ta choïn S, töùc  
laø yi+1 = yi  
.
p ³ 0  
¨ Ngöôïc laïi, neáu  
, ñieåm MidPoint naèm ngoaøi ñöôøng  
i
troøn. Luùc naøy ñieåm thöïc Q gaàn P hôn neân ta choïn P, töùc  
laø yi+1 = yi - 1.  
· Maët khaùc :  
1
2
1
2
æ
ö
÷
ø
æ
ö
÷
ø
p - p = F x + 1, y -  
- F x + 1, y -  
ç
ç
i+1  
i
i+1  
i+1  
i
i
è
è
2
2
é
ù é  
- R2 -  
ù
ú
û
1
2
1
2
æ
ö
æ
ö
Û p - p =  
(
x + 1 2  
)
+ y -  
(
x + 1 2  
)
+ y -  
- R2  
ê
ç
÷
ø
ú ê  
ç
÷
ø
i+1  
i
i+1  
i+1  
i
i
è
è
ê
ë
ú ê  
û ë  
ú
Û p - p = 2x + 3+  
(
y2 - y2  
)
-
y - y  
( )  
i+1  
i
i
i+1  
i
i+1  
i
· Vaäy :  
pi < 0  
p = p + 2x + 3  
yi+1 = yi  
.
¨
¨
, neáu  
do ta choïn  
i+1  
i
i
pi ³ 0  
pi+1 = p + 2x - 2y + 5  
, neáu  
do ta choïn  
i
i
i
y = y - 1  
.
i+1  
i
p0  
(
x0 , y0  
)
=
0, R  
( )  
.
·
öùng vôùi ñieåm ban ñaàu  
1
2
1
2
5
4
æ
ö
÷
ø
æ
ö
÷
ø
p = F x + 1, y -  
= F 1, R -  
=
- R  
ç
ç
0
0
0
è
è
Döông Anh Ñöùc, Leâ Ñình Duy  
Caùc thuaät toaùn veõ ñöôøng 17/22  
ÑOÀ HOÏA MAÙY TÍNH  
Löu ñoà thuaät toaùn MidPoint veõ ñöôøng troøn  
Begin  
p=5/4-R;  
x=0;  
y=R;  
Put8Pixel(x, y, c);  
No  
x<y  
Yes  
No  
p<0  
Yes  
p=p+2*x+3;  
p=p+2(x-y)+5;  
y=y-1  
x=x+1;  
Put8Pixel(x,y,c);  
End  
Döông Anh Ñöùc, Leâ Ñình Duy  
Caùc thuaät toaùn veõ ñöôøng 18/22  
ÑOÀ HOÏA MAÙY TÍNH  
Caøi ñaët minh hoïa thuaät toaùn MidPoint veõ ñöôøng troø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++;  
Put8Pixel(x, y);  
}
} // CircleMidPoint  
Döông Anh Ñöùc, Leâ Ñình Duy  
Caùc thuaät toaùn veõ ñöôøng 19/22  
ÑOÀ HOÏA MAÙY TÍNH  
· Ví duï : Veõ ñöôøng troøn taâm I(0,0), baùn kính R=15.  
i
0
1
2
3
4
5
6
7
8
9
10  
11  
xi  
0
1
2
3
4
5
6
7
8
9
10  
11  
yI  
pi  
Delta1 Delta2  
15  
15  
15  
15  
14  
14  
14  
13  
13  
12  
11  
10  
-14 1-15  
-11 -14+2*(0)+3  
-6 -11+2*(1)+3  
3
5
7
9
11  
13  
15  
17  
19  
21  
23  
25  
-25  
-23  
-21  
-19  
-15  
-13  
-11  
-7  
1
-6+2*(2)+3  
-18 1+2*(3-15)+5  
-7 -18+2*(4)+3  
6
-5 6+2(6-14)+5  
12 -5+2(7)+3  
7
6
9
-7+2*(5)+3  
-5  
-1  
12+2(8-13)+5  
7+2(9-12)+5  
6+2(10-11)+5  
3
7
Nhaän xeùt :  
· Neáu ñaët Delta1 = 2*x+3, Delta2 = 2*(x-y)+5 thì  
¨ Do moãi böôùc ñeàu taêng x neân sau moãi laàn laëp giaù trò  
Delta1 luoân taêng 2.  
¨ Do y bò giaûm 1 khi gaëp p³ 0 vaø giöõ nguyeân giaù trò trong  
tröôøng hôïp ngöôïc laïi neân neáu laàn laëp tröôùc giaù trò p³ 0  
thì giaù trò Delta2 seõ ñöôïc taêng 4 vaø neáu laàn laëp tröôùc giaù  
trò p<0 thì giaù trò Delta2 seõ ñöôïc taêng 2 maø thoâi.  
· Haõy toái öu hoùa caøi ñaët thuaät toaùn MidPoint veõ ñöôøng  
troøn töø nhaän xeùt treân.  
Döông Anh Ñöùc, Leâ Ñình Duy  
Caùc thuaät toaùn veõ ñöôøng 20/22  
Tải về để xem bản đầy đủ
pdf 22 trang Thùy Anh 27/04/2022 8360
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Đồ họa máy tính - Các thuật toán vẽ đường", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • pdfbai_giang_do_hoa_may_tinh_cac_thuat_toan_ve_duong.pdf