Đồ họa máy tính
D` HOA MAY T´
ˆ
-O . ´ INH I
Pham Tiˆn So.n
. ´
e
-a .
D` Lat, 2005
2
Muc luc
. .
L`.i n´i d` u
o o ¯ˆ a 7
1 C´c thuˆt to´n v˜ d .`.ng cong trˆn thiˆt bi raster
a a
. a e ¯u o e ´
e . 9
1.1 - . ˙
’
Doan thˇng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
a 9
1.1.1 a
. a o ´
Thuˆt to´n sˆ gia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.1.2 Thuˆt to´n d iˆ’m gi˜.a . . . . . . . . . . . . . . . . . . . . . . . . . .
a
. a ¯e ˙ u 13
1.1.3 . ´ ´ e
o o a ¯ˆ e ´
¯e a
. a e ¯ . ˙
’
Mˆt sˆ vˆ n d` liˆn quan dˆn thuˆt to´n v˜ d oan thˇng . . . . . . . .
a 18
1.1.4 o ınh ˙ ¯ .
’ ˙
’
C´c thuˆc t´ cua d oan thˇng . . . . . . . . . . . . . . . . . . . . .
a . a 21
1.2 Du.`.ng tr`n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
- o o 22
1.2.1 Dˆi x´.ng t´m d iˆ’m . . . . . . . . . . . . . . . . . . . . . . . . . . . .
-o u
´ a ¯e ˙ 22
1.2.2 Thuˆt to´n d iˆ’m gi˜.a v˜ d u.`.ng tr`n . . . . . . . . . . . . . . . . . .
a
. a ¯e ˙ u e ¯ o o 23
1.3 Du.`.ng cong ellipse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
- o 28
1.3.1 o . ´
Ellipse c´ dang ch´ tˇc . . . . . . . . . . . . . . . . . . . . . . . . .
ınh a 29
1.3.2 Ellipse trong tru.`.ng ho.p tˆ’ng qu´t . . . . . . . . . . . . . . . . . . .
o . o ˙ a 34
2 H` hoc cu a c´c d .`.ng cong v` mˇt cong
ınh . ˙
’ a ¯u o a a. 47
2.1 Mo. d` u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
˙ ¯a
’ ˆ 47
3
2.2 Du.`.ng cong Bezier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
- o 48
2.2.1 Thuˆt to´n de Casteljau . . . . . . . . . . . . . . . . . . . . . . . . .
a
. a 48
2.2.2 Da th´.c Bernstein v` d u.`.ng cong Bezier . . . . . . . . . . . . . . . .
- u a ¯ o 52
2.3 C´c t´ chˆ t cua d u.`.ng cong Bezier . . . . . . . . . . . . . . . . . . . . . .
´ ’
a ınh a ˙ ¯ o 55
2.3.1 Diˆu khiˆ’n d .a phu.o.ng . . . . . . . . . . . . . . . . . . . . . . . . . .
- `
e ˙
e ¯i 59
2.4 Da th´.c t`.ng kh´c v` c´c h`m spline . . . . . . . . . . . . . . . . . . . . . .
- u u u a a a 60
2.4.1 Su. dung c´c h`m spline nhu. c´c h`m trˆn . . . . . . . . . . . . . . .
˙ .
’ a a a a o
. 63
2.4.2 Xˆy du.ng c´c h`m trˆn . . . . . . . . . . . . . . . . . . . . . . . . .
a . a a o
. 65
2.4.3 Du.`.ng cong spline v` c´c h`m co. so. . . . . . . . . . . . . . . . . . .
- o a a a ˙
’ 66
2.4.4 C´c h`m B-spline co. so. . . . . . . . . . . . . . . . . . . . . . . . . .
a a ˙
’ 66
2.4.5 Su. dung c´c knot bˆi . . . . . . . . . . . . . . . . . . . . . . . . . . .
˙ .
’ a o
. 71
2.4.6 Vector knot chuˆ’n . . . . . . . . . . . . . . . . . . . . . . . . . . . .
a˙ 73
2.5 C´c t´ chˆ t cua d u.`.ng cong B-spline . . . . . . . . . . . . . . . . . . . . .
´ ’
a ınh a ˙ ¯ o 75
2.6 Nˆi suy c´c d iˆ’m d iˆu khiˆ’n bˇ ng d u.`.ng cong B-spline . . . . . . . . . . . .
o
. ˙
a ¯ e ¯` e ˙ a
e ` ¯ o 77
2.7 ´ ´
Thiˆt kˆ c´c mˇt Bezier v` B-spline . . . . . . . . . . . . . . . . . . . . . . .
e e a a
. a 80
2.7.1 Patch Bezier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
2.7.2 D´n c´c patch Bezier . . . . . . . . . . . . . . . . . . . . . . . . . . .
a a 81
2.7.3 Patch spline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
3 Giao cu a c´c d oi tu.o.ng
˙
’ a ¯ˆ ´ . 83
3.1 Mo. d` u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
˙ ¯a
’ ˆ 83
3.2 ˙
’ ˙
’
Giao cua hai d oan thˇng . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
¯ . a 83
3.2.1 Phˆn t´
a ıch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
4
3.2.2 . a a ¯. ¯ . ˙
’
Thuˆt to´n x´c d inh giao hai d oan thˇng . . . . . . . . . . . . . . . .
a a 86
3.3 Doan thˇng v` h` ch˜. nhˆt . . . . . . . . . . . . . . . . . . . . . . . . . .
- . ˙
’
a a ınh u a . 87
3.3.1 T` giao bˇ ng c´ch giai hˆ c´c phu.o.ng tr` . . . . . . . . . . . . . .
ım `
a a ˙ e a
’ . ınh 89
3.3.2 Thuˆt to´n chia nhi phˆn . . . . . . . . . . . . . . . . . . . . . . . .
a
. a . a 89
3.3.3 Thuˆt to´n Cohen-Sutherland . . . . . . . . . . . . . . . . . . . . . .
a
. a 93
3.3.4 Thuˆt to´n Liang-Barsky
a
. a . . . . . . . . . . . . . . . . . . . . . . . . 97
3.4 ˙ ¯ .
’ ˙
’ a `
Giao cua d oan thˇng v` d a gi´c lˆi . . . . . . . . . . . . . . . . . . . . . . . 100
a a ¯ o
3.4.1 Vi tr´ tu.o.ng d ˆi cua mˆt d iˆ’m v´.i d u.`.ng thˇng . . . . . . . . . . . . 100
. ı ´ ’
¯o ˙ o ¯e
. ˙ o ¯ o ˙
’
a
3.4.2 ˙ ¯ .
’ ˙
’ a `
Thuˆt to´n t` giao cua d oan thˇng v` d a gi´c lˆi . . . . . . . . . . 102
a
. a ım a a ¯ o
3.5 Giao hai d a gi´c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
¯ a
3.5.1 Thuˆt to´n Sutherland-Hodgman . . . . . . . . . . . . . . . . . . . . 108
a
. a
3.5.2 Thuˆt to´n Weiler-Atherton . . . . . . . . . . . . . . . . . . . . . . . 111
a
. a
3.5.3 C´c ph´p to´n tˆp ho.p trˆn c´c d a gi´c . . . . . . . . . . . . . . . . 113
a e a a . . e a ¯ a
3.6 ` ˙
’ `
Ray tracing hai chiˆu: phan xa trong buˆng k´ . . . . . . . . . . . . . . . . 114
e . o ın
3.6.1 ˙
’
Vector phan xa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
.
3.6.2 Giao cua tia s´ng v` d u.`.ng thˇng
˙
’ a a ¯ o ˙
’
a . . . . . . . . . . . . . . . . . . . 117
3.6.3 Giao cua tia s´ng v´.i d u.`.ng tr`n . . . . . . . . . . . . . . . . . . . . 121
˙
’ a o ¯ o o
3.6.4 Xˆy du.ng v´ du ray tracing . . . . . . . . . . . . . . . . . . . . . . . 124
a . ı .
3.6.5 `
Buˆng k´ l` ellipse . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
o ın a
4 Tˆ m`u v` ng
o a u 127
4.1 C´c d inh ngh˜ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
a ¯. ıa
4.1.1 V`ng d inh ngh˜ bo.i pixel . . . . . . . . . . . . . . . . . . . . . . . . 127
u ¯. ıa ˙
’
5
4.1.2 V`ng d inh ngh˜ bo.i d a gi´c . . . . . . . . . . . . . . . . . . . . . . . 129
u ¯. ıa ˙ ¯
’ a
4.2 e `
´ a
Thuˆt to´n tˆ m`u theo vˆt dˆu loang . . . . . . . . . . . . . . . . . . . . . 129
a
. a o a
4.3 Thuˆt to´n tˆ m`u theo con chay . . . . . . . . . . . . . . . . . . . . . . . . 131
a
. a o a .
4.4 Thuˆt to´n tˆ m`u theo biˆn . . . . . . . . . . . . . . . . . . . . . . . . . . 134
a
. a o a e
4.5 So s´nh c´c thuˆt to´n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
a a a
. a
4.6 Tˆ m`u c´c h` ch˜. nhˆt . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
o a a ınh u a .
4.7 Thuˆt to´n tˆ m`u d a gi´c . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
a
. a o a ¯ a
4.7.1 C´c d`ng qu´t ngang . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
a o e
4.7.2 ˙
’
C´c manh vun
a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
4.7.3 ´
Liˆn kˆt canh v` thuˆt to´n tr`n . . . . . . . . . . . . . . . . . . . . 151
e e . a a
. a a
4.7.4 o a a ¯ a `
Tˆ m`u c´c d a gi´c chˆng nhau . . . . . . . . . . . . . . . . . . . . . 158
o
4.8 ˜
Tˆ m`u theo mˆ u tˆ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
o a a o
Phˆn phu luc: Thu. viˆn graph2D.h
`
a . . e
. 163
a e . ˙
’
T`i liˆu tham kha o 171
6
L`.i n´i d` u
o o ¯ˆ a
D` hoa m´y t´ l` mˆt l˜ vu.c hˆ p dˆ n cua khoa hoc m´y t´
-ˆ .
o a ınh a o ınh . a a ˙
. ´ ˜ ’ . a ınh. Ch´ng ta su. dung d` hoa
u ˙ .
’ ¯ˆ .
o
m´y t´ nhu. mˆt cˆng cu dˆ’ quan s´t thˆng tin trong nhiˆu l˜ vu.c kh´c nhau, bao gˆm
a ınh o o
. . ¯e˙ a o ` ınh .
e a `o
´ u a ˙ ı. a
’
khoa hoc v` cˆng nghˆ, ho´ hoc, kiˆn tr´c v` giai tr´ C´c chu .o.ng tr` d` hoa tu.o.ng t´c
. a o e. a . e ınh ¯o .
ˆ a
cho ph´p ngu.`.i su. dung l`m viˆc theo c´ch tu. nhiˆn nhˆ t: ngu.`.i su. dung cung cˆ p thˆng
e o ˙ .’ a e
. a . e ´
a o ˙ .’ ´
a o
tin cho tr` u
ınh ´ .ng dung thˆng qua c´c hoat d ong bˆn ngo`i cua ho v` s˜ nhˆn d u.o.c thˆng
o a a ˙’
. . ¯ˆ. e . a e a ¯ . . o
tin tro. lai bˇ ng h` anh. D` hoa m´y t´ d ang gi´p con ngu.`.i thay d ˆ’i vˆ quan niˆm v`
˙ . `
’ a ınh ˙’ -ˆ .
o a ınh ¯ u o ˙ e
¯o ` e. a
a .c su. dung m´y t´
c´ch th´ ˙ .
u ’ a ınh.
Gi´o tr` D` hoa m´y t´ I cung cˆ p mˆt sˆ k˜ thuˆt co. ban cua d` hoa m´y t´
a ınh - ˆ .
o a ınh ´
a . ´
o o y a
. ˙
’ ˙ ¯ˆ .
’ o a ınh
`e -ˆ .
hai chiˆu. (D` hoa m´y t´ ba chiˆu, mˆt phˆn quan trong khˆng thˆ’ thiˆu d u . e ¯ .
o a ınh `e o `a o e˙ e ¯
´ .o.c s˜ d u.o.c
. .
d` cˆp trong mˆt gi´o tr` kh´c). Dˆ’ c´ mˆt khung canh to`n diˆn v` sˆu sˇc vˆ nh˜.ng
¯ˆ a
e . o a
. ınh a -e o o
˙ . ˙
’ a e a a a `
. ´ e u
nguyˆn l´ v` thu a
e y a . .c h`nh cua d` hoa m´y t´
˙ ¯ˆ .
’ o a ınh, xem c´c t`i liˆu dˆn [9] v` [11]. C´c phu.o.ng
a a e a ˜ a a
.
ph´p phˆn t´ v` thiˆt kˆ c´c thuˆt to´n trong gi´o tr` cho ph´p sinh viˆn c´ thˆ’ viˆt
a a ıch a ´ ´
e e a a. a a ınh e e o e e ˙ ´
dˆ d`ng c´c chu.o.ng tr` minh hoa. Gi´o tr` d u.o.c biˆn soan cho c´c d ˆi tu.o.ng l` sinh
˜ a
e a ınh . a ınh ¯ . e . a ¯o´ . a
viˆn To´n-Tin v` Tin hoc.
e a a .
Gi´o tr` su. dung ngˆn ng˜. C dˆ’ minh hoa, tuy nhiˆn c´ thˆ’ dˆ d`ng chuyˆ’n d o’i
a ınh ˙ .
’ o u ¯e˙ . e o e ˜ a˙ e ˙
e ¯ˆ ˙
sang c´c ngˆn ng˜. kh´c; v` do d o, sinh viˆn cˆn c´ mˆt sˆ kiˆn th´.c vˆ ngˆn ng˜. C. Ngo`i
a o u a a ¯´ e ` o o o e
a . ´ ´ u ` o
e u a
`
a e a ´
ra, hˆu hˆt c´c chu .o.ng tr` thao t´c trˆn cˆ u tr´c d˜. liˆu nhu. danh s´ch liˆn kˆt, nˆn d oi
ınh a e a ´ u u e a e e ´ e ¯`
.
hoi sinh viˆn phai c´ nh˜.ng k˜ nˇng lˆp tr` tˆt.
˙
’ e ˙ o u
’ y a a
. ınh o ´
Sinh viˆn c˜ng cˆn c´ co. so. to´n hoc cua nh˜.ng nˇm d` u d ai hoc: hiˆ’u biˆt vˆ d ai sˆ
e u ` o
a ˙ a . ˙
’ ’ u a ¯ˆ ¯ . .
a e˙ e ` ¯. o
´ e ´
´ ˙ ıch, e ınh
’
tuyˆn t´ v` h` hoc giai t´ ph´p t´ vi t´ phˆn.
e ınh a ınh . ıch a
Muc d´ cua gi´o tr` l`, o. m´.c d o n`o d ´, cho thˆ y c´c tr` u.ng dung d` hoa
. ¯ıch ˙ ’ a ınh a ˙ u ¯ˆ a ¯o
’ . ´
a a ınh ´ . ¯ˆ .
o
¯ .o.c tao ra nhu. thˆ n`o: Ch´ng ta cˆn viˆt v` chay thu. c´c chu.o.ng tr`
du . . ´
e a u `a ´
e a . ˙ a
’ ınh. Mˆt trong
o.
nh˜ u.ng muc d´ ch´ cua gi´o tr` l` gi´p sinh viˆn nˇm v˜.ng c´c phu.o.ng ph´p, tru.´.c
˙
’ ´
. ¯ıch ınh a ınh a u e a u a a o
hˆt to´n hoc ho´ c´c kh´c niˆm h` hoc v` sau d ´ chuyˆ’n tai th`nh c´c d oan m˜ chu
e´ a a a a e ınh . a ¯o ˙ ’
e ˙ a a ¯ . a .o.ng
. .
tr`
ınh.
7
Gi´o tr` bao gˆm bˆn chu.o.ng v` mˆt phˆn phu luc v´.i nh˜.ng nˆi dung ch´ nhu.
a ınh `
o ´
o a o. `
a . . o u o
. ınh
sau:
• Chu.o.ng th´. nhˆ t d` cˆp dˆn c´c phu.o.ng ph´p v˜ c´c “nguyˆn so.” cua d` hoa m´y
u ´ e .
a ¯ˆ a ¯e a ´ a e a e ˙ ¯o .
’ ˆ a
ınh: d oan thˇng, d u.`.ng tr`n v` ellipse.
t´ ¯ . ˙
’
a ¯ o o a
• Phˆn t´ v` thiˆt kˆ bˇ ng h` hoc l` nˆi dung ch´ cua Chu.o.ng 2. Hˆu hˆt c´c
a ıch a e e `
´ ´ a ınh . a o . ınh ˙ ’ `
a e a´
phˆn mˆm d` hoa d` u c´ nh˜
`a ` ¯ˆ . ¯ˆ o u
e o e .ng ch´.c nˇng tao ra c´c d u.`.ng cong du.a trˆn c´c d iˆ’m
u a a ¯ o e a ¯e ˙
. .
m` ngu.`.i su. dung lu.a chon. Chu.o.ng n`y cung cˆ p nh˜.ng nguyˆn l´ v` c´ch tiˆp cˆn
a o ˙ .
’ . . a ´
a u e y a a ´ .
e a
.c h`nh m` c´c tr` u.ng dung d` hoa ´p dung.
thu a a a ınh ´ ¯o . a
ˆ
. . .
• Chu.o.ng 3 giai quyˆt b`i to´n x´c d inh giao cua nh˜.ng nguyˆn so. d` hoa: Giao hai
˙
’ ´
e a a a ¯. ˙
’ u e ¯ˆ .
o
d oan thˇng, giao cua d oan thˇng v` d a gi´c lˆi (bao h`m c´c h` ch˜. nhˆt) v` giao
¯ . ˙
’
a ˙ ¯ .
’ a˙
’ a ¯ a `o a a ınh u a . a
˙
’ ´
cua hai d a gi´c. Cuˆi chu
¯ a o .o.ng l` mˆt v´ du cua k˜ thuˆt “ray tracing” hai chiˆu:
a o ı . ˙ ’ y a `
e
. .
Chuyˆ’n d ong cua tia s´ng trong buˆng k´ c´ ch´.a c´c “chu.´.ng ngai vˆt”.
˙
e ¯ˆ . ˙
’ a `
o ın o u a o . a .
• Chu.o.ng 4 d` cˆp dˆn nh˜.ng thuˆt to´n tˆ m`u v`ng bˆ t k`: V`ng d inh ngh˜ bo.i
¯ˆ a ¯e
e . ´ u a. a o a u ´
a y u ¯. ıa ˙
’
` ˙
’.i d u.`.ng biˆn v` v`ng l` d a gi´c.
phˆn trong, bo ¯ o
a e a u a ¯ a
• Phˆn phu luc l` thu. viˆn c´c cˆ u tr´c d˜. liˆu v` c´c h`m cˆn thiˆt v` thu.`.ng xuyˆn
`
a . . a e a a
. ´ u u e a a a `
. a ´
e a o e
su. dung trong gi´o tr`
˙ .
’ a ınh.
Trong lˆn xuˆ t ban th´. hai n`y, ch´ng tˆi d u.a thˆm c´c v´ du t´ to´n nhˇ m minh
`a ´ ’
a ˙ u a u o ¯ e a ı . ınh a `
a
` y ´
hoa cho phˆn l´ thuyˆt c˜ng nhu u
a e u . gi´p sinh viˆn nˇm v˜.ng kiˆn th´.c d ˜ hoc. Ngo`i ra, c´c
e a ´ u ´
e u ¯a . a a
.
lˆi trong xuˆ t ban lˆn tru.´.c c˜ng d a d u.o.c chınh l´; mˇc d` vˆy, t´c gia vˆn mong c´ nh˜.ng
˜
o a ˙ `
´ ’ a o u ¯˜ ¯ . ˙
’ y a u a a
. . ’ ˜
˙ a o u
¯o o u . ban d oc.
d ´ng g´p t` . ¯ .
Tˆi xin cam o.n nh˜.ng gi´p d o. d ˜ nhˆn d u.o.c t`. nhiˆu ngu.`.i m` khˆng thˆ’ liˆt kˆ
o ˙
’ u u ¯˜ ¯a a ¯ . u
. `
e o a o ˙ .
e e e
´
hˆt, d ac biˆt l` c´c ban sinh viˆn, trong qu´ tr` biˆn soan gi´o tr` n`y.
e ¯ˇ . e a a .
. e a ınh e . a ınh a
-a .
D` Lat, ng`y 10 th´ng 1 nˇm 2005
a a a
PHAM Tiˆn So.n
. ´
e
8
Chu.o.ng 1
C´c thuˆt to´n v˜ d .`.ng cong trˆn
a a
. a e ¯u o e
´
thiˆt bi raster
e .
Chu.o.ng n`y tr` b`y c´c thuˆt to´n v˜ d oan thˇng, d u.`.ng tr`n v` ellipse trˆn lattice
a ınh a a a
. a e ¯ . ˙
’
a ¯ o o a e
2
a a a ˙
’
nguyˆn Z . C´c thuˆt to´n chı thao t´c trˆn nh˜
e a e u.ng sˆ nguyˆn v` trong c´c v`ng lˇp chı su.
´
o e a a o a ˙ ˙
’ ’
. .
. a o . e a´ e . ˙
’
dung ph´p to´n cˆng nˆn rˆ t hiˆu qua.
e
1.1 - . ˙
’
Doan thˇ ng
a
Thuˆt to´n v˜ d oan thˇng x´c d .nh toa d o cua c´c pixel nˇ m trˆn hoˇc gˆn v´.i d oan thˇng
a
. a e¯ . a˙
’ a ¯i . ¯ˆ ˙ a
. ’ `
a e a ` o ¯ .
. a ˙
’
a
thu.c tˆ nhˆ t. Vˆ nguyˆn tˇc, ch´ng ta muˆn chon d˜y c´c pixel gˆn v´.i d oan thˇng thu.c tˆ
. e a´ ´ `e e a ´ u ´
o . a a ` o ¯ .
a a˙
’ . e ´
´ ˙
’ ´ ˙
’ .c tˆ d u.o.c xˆ p xı v´.i mˆt d o mˆt pixel; ta cˆn c´
nhˆ t v` thˇng nhˆ t. X´t d oan thˇng thu e ¯ . a ˙ o
a a a a e ¯ . a . ´ ´ ’ a ¯ˆ o
. . . ` o
a
nh˜.ng t´ chˆ t g` V´.i c´c d oan thˇng c´ hˆ sˆ g´c thuˆc d oan [−1, 1], c´ d ung mˆt pixel
u ´
ınh a ı? o a ¯ . ˙
’
a . ´
o e o o o ¯ .
. o ¯´ o
.
.o.c v˜ lˆn trˆn mˆ i cˆt; v´.i c´c d oan thˇng m` hˆ sˆ g´c nˇ m ngo`i d oan n`y, c´ d ung
du . e e
¯ e ˜ .
o o o a ¯ . ˙
’
a a e o o `
´ a a ¯ . a o ¯´
.
mˆt pixel d u.o.c v˜ trˆn mˆ i h`ng. Tˆ t ca c´c d oan thˇng d u.o.c v˜ v´.i c`ng mˆt d o s´ng,
o. ¯ . e e ˜
o a ´ ’
a ˙ a ¯ . ˙
’
a ¯ . e o u o ¯ˆ a
. .
khˆng phu thuˆc v`o d ˆ d`i v` hu o
o o a ¯o a a .´.ng, v` nhanh nhˆ t c´ thˆ’ d u.o.c. Thuˆt to´n v˜ d oan
a ´
a o e ¯ . ˙ a a e ¯ .
. . . .
˙
’
a u `
a u ´ ¯e a ´ o ınh ˙ ¯ . ’
thˇng c˜ng cˆn ch´ y dˆn c´c thuˆc t´ cua d oan thˇng nhu ¯o o ˙
’
a . d ˆ rˆng, kiˆ’u v˜... Thˆm ch´
˙
e e a ı
. . . .
ch´ng ta muˆn cu e
u ´ .
o .c tiˆ’u ho´ m´.c d o rˇng cu.a do tiˆn tr` r`.i rac ho´ d u.`.ng thˇng thu.c
˙ a u ¯ˆ a ´
e ınh o . a ¯ o ˙
’
a
. .
´ . su. dung k˜ thuˆt antialiasing (xem [9], [11]) bˇ ng c´ch ´p dung kha nˇng d ˇt cu.`.ng
tˆ nh` ˙ .
e o ’ y a `
a a a ˙ a ¯a
’ o
. . .
d ˆ cua mˆ i pixel trˆn c´c thiˆt bi hiˆ’n thi m` mˆt pixel tu
¯o ˙ ˜ ´ ˙ .o.ng u.ng nhiˆu bit.
`
. ’ o e a e . e . a o . ´ e
Tru.´.c hˆt ch´ng ta chı d` cˆp dˆn c´c d oan thˇng d o rˆng mˆt pixel v` c´ d ung mˆt
o e ´ u ’ e . ´
˙ ¯ˆ a ¯e a ¯ . ˙
’
a ¯ˆ o
. . o
. a o ¯´ o.
pixel trˆn mˆ o
e o . a a ´ o
¯o .i c´c d oan thˇng dˆc). Phˆn cuˆi chu.o.ng s˜ d` cˆp
˜i cˆt (hoˇc h`ng d ˆi v´ a ¯ . ˙
’
a ´
o `a ´
o e ¯ˆ a
e .
.
9
dˆn d o rˆng c´c nguyˆn so. v` c´c mˆ u v˜.
´ . .
¯e ¯ˆ o a e a a ˜
a e
Mˆt c´ch h` hoc, ch´ng ta biˆ’u diˆn mˆt pixel nhu. mˆt chˆ m tr`n v´.i tˆm tai vi
o a
. ınh . u e˙ ˜
e o
. o
. ´
a o o a . .
.´.i c´c toa d o nguyˆn Z2 . Biˆ’u diˆn n`y l` mˆt xˆ p xı th´ ho.p
˙ ˜ a a o a ˙ ıch .
˙
’
tr´ (x, y) cua pixel trˆn lu o a . ¯ˆ
ı e . e e e . ´ ’
´ y ˙’
nh´t cˇt ngang trong mˆt chu k` cua ch`m tia electron cua CRT; xˆ p xı n`y phu thuˆc v`o
a a o
. u ˙
’ ´ ’
a ˙ a . o a
.
.a c´c vˆt trˆn m`n h` hiˆ’n thi. Trong mˆt sˆ
˙
˙
’
khoang c´ch (tu` thuˆc v`o hˆ thˆng) gi˜ a e
a y o a e o
. . ´ u ´ e a ınh e . . ´
o o
hˆ thˆng, c´c chˆ m kˆ nhau phu lˆ p mˆt phˆn lˆn nhau; v´.i nh˜.ng hˆ thˆng kh´c c´ nh˜.ng
. ´
e o a a `
´ e ’ ´
˙ a o. ` e
a o u . ´
e o a o u
˙
’
khoang c´ch gi˜ a
a u .a c´c pixel d u.ng kˆ nhau; trong hˆu hˆt c´c hˆ thˆng, khoang c´ch theo
¯´ `e ` ´
a e a e o ´ ˙
’ a
.
chiˆu ngang nho ho.n theo chiˆu d u.ng. Mˆt kh´c biˆt n˜.a tu` theo hˆ thˆng trong viˆc biˆ’u
`
e ˙
’ ` ¯´
e o. a e u
. y . ´
e o e. e˙
diˆn hˆ toa d o, chˇng han Macintosh xem c´c pixel d u.o.c d at tai tˆm cua h` ch˜. nhˆt
˜ e . ¯ˆ
e . . a˙
’ . a ¯ . ¯ˇ . a . ˙
’ ınh u a
.
.a c´c d u.`.ng thˇng kˆ nhau cua lu.´.i d iˆu khiˆ’n thay cho nˇ m trˆn c´c d u.`.ng thˇng cua
gi˜ a ¯ o
u a˙
’ `
e ˙
’ o ¯e ` e ˙ `
a e a ¯ o ˙
a’ ˙
’
.´.i. Theo c´ch n`y, c´c h` ch˜. nhˆt (x´c d inh bo.i hai g´c) gˆm c´c pixel thuˆc phˆn
lu o a a a ınh u a a ¯. ˙
’ o `
o a o `
a
. .
trong cua n´. D.nh ngh˜ n`y cho ph´p c´c v`ng d ˆ rˆng bˇ ng khˆng: H` ch˜. nhˆt t`.
˙ o -i
’ ıa a e a u ¯o o . . `
a o ınh u a u
.
´
(x, y) dˆn (x, y) khˆng ch´
¯e o u.a pixel n`o, trong khi v´.i nh˜.ng hˆ thˆng kh´c, c´ d ung mˆt
a o u e o ´ a o ¯´ o
. .
pixel tai d iˆ
. ¯e ˙m n`y. Du.´.i d ay ch´ng ta s˜ biˆ’u diˆn c´c pixel nhu. c´c h` tr`n r`.i nhau c´
’ a o ¯ˆ u e e ˙ ˜ a
e a ınh o o o
a `
tˆm nˇ m trˆn lu o
a e .´.i.
H` 1.1 l` ph´ng to cua d u.`.ng thˇng thu.c tˆ v` xˆ p xı d o rˆng mˆt pixel cua n´.
ınh a o ˙ ¯ o
’ ˙
’
a ´ ´ ’ . .
. e a a ˙ ¯ˆ o o. ˙
’ o
a ¯ .o.c v˜ tu.o.ng u.ng c´c h` tr`n m`u d en v` c´c pixel khˆng d u.o.c v˜ tu.o.ng u.ng
C´c pixel d u . e ´ a ınh o a ¯ a a o ¯ . e ´
h` tr`n khˆng tˆ. Trˆn m`n h` thu.c tˆ, d u.`.ng k´ cua h` tr`n biˆ’u diˆn pixel l´.n
ınh o o o e a ınh . e ¯ o ´ ınh ˙ ınh o
’ e˙ ˜
e o
ho.n khoang c´ch gi˜.a c´c pixel kˆ nhau, bo.i vˆy biˆ’u diˆn bˇ ng k´ hiˆu cua ch´ng ta l`
˙
’ a u a `
e ˙ a
’ . e˙ ˜ a
e ` y e ˙
’ u a
.
mˆt ph´ng d ai m´.c d o r`.i rac cua c´c pixel.
o
. o ¯. u ¯ˆ o . ˙ a
. ’
.
. .
. .
. .
. .
.
.
.
. .
.
. .
.
. .
.
. .
.
.
.
.
. .
.
. .
.
. .
.
. .
.
.
.
.
. .
. .
. .
. .
.
............i
............
.
.
.
i .
.
.
.
.
. i .
.
.
.
.
. i .
.
.
.
.
.
.
i
.
. ...................... ...................... .......................................................
.
....................................................................................................
.
.
.
.
.
. .
.
. .
.
. .
.
. .
.
.
.
.
. .
.
. .
.
. .
.
. .
.
.
.
.
. .
.
. .
.
. .
.
. .
.
.
.
. .
. .
. .
. .
. ...
.
.
. .
. .
. .
. . ....
. . .....
.
.
.
.
.
.
.
.
.
.
.
.
. . ......
.
.
.
.
.
.
.
.
.
.
.
.
. ....
....
.. .
.
. . . . .... .
.... .
i.
.
.
.
.
i .
.
.
.
.
.
i .
.
.
.
.
.
i
y .
.
..
. ... .
. ..
. .......
.
..
.
i
y
.
.................................................................................................................
.............................................................................. ..................................
. .
.
.
.
.
.
. .
.
. .
.
. . .
.
.....
....
.
.
.
. . . .
..... .
.
.
.
.
.
.
.
.
. .....
.. .
. . .
.
.
.
.
.
.
.
.
.
.
. ..
. ....
.... .
.
.
.
.
.
. .
. . .......
. .... .
. .
.
.
.
. .
.
. . .... ..
.
....... .
.
. .
.
.
. . .
.... . .
.
.
.
.
.
. ...
.. .
. . .
.
.
.
.
.
. . .... .
.... . . .
i.
.
. i
y .
. . .
.. ..
..
i
y . i .
. i
.
.
.................................................................................................................
............................................................................... .................................
.
.
.
.
.
. . ....
. .......
.
.
.
. .
.
.
. .
.
.
.
.
.
. .
....
...
. .
.
. .
.
. .
.
.
. .
.. . . .
.
.
. .... .
.... .
.. .
. . .
.
.
.
.
.
.
.
.
.
.
. ..
. ....
.... .
.
.
.
.
.
.
.
.
.
.
. .......
. .... .
. .
. .
. .
.
. .... .
.
....... .
.
. .
.
. .
.
. .
.
.
.
....
. .
. .
. .
. .
.
....
.. .
. .
. .
. .
. .
.
.... .
.... .
..
.. i
y.
.
.
i .
.
.
.
.
.
i .
.
.
.
.
i .
.
.
.
.
. i
.
.
.................................................................................................................
.................................. ............................................ .................................
. . .
.
.
.
.
. .
. .
. .
. .
.
.
. .
. .
. .
. .
.
.
.
. .
.
. .
.
. .
.
. .
.
.
.
.
. .
.
. .
.
. .
.
. .
.
.
H` 1.1: Doan thˇng xˆ p xı d u.o.c biˆ’u diˆn bo.i c´c h` tr`n d en.
ınh - . ˙
’
a ´ ’
a ˙ ¯ . e˙ ˜
e ˙ a ınh o ¯
’
V` c´c nguyˆn so. trong hˆ thˆng ch´ng ta x´c d inh trˆn lu.´.i d iˆu khiˆ’n nguyˆn nˆn
ı a e . ´
e o u a ¯. e o ¯` e e˙ e e
c´c toa d o d` u cuˆi cua d oan thˇng l` nguyˆn. Thˆt ra, nˆu ch´ng ta cˇt d oan thˇng v´.i
a . ¯ˆ ¯ˆ . a ´ ’
o ˙ ¯ . ˙
’
a a e a
. ´
e u ´
a ¯ . ˙
’
a o
h` ch˜
ınh u . nhˆt tru.´.c khi hiˆ’n thi n´ th` toa d ˆ c´c d iˆ’m d` u cuˆi cua d oan thˇng c´ thˆ’
a o e˙ ˙ ´ ’
o ˙ ¯ . ˙
’ ˙
. . o ı . ¯o a ¯ e ¯ˆ
. a a o e
khˆng nguyˆn. (Ch´ng ta s˜ thao luˆn c´c giao d iˆ’m khˆng nguyˆn trong Phˆn 1.1.3). Gia
o e u e ˙ ’ a a
. ¯e˙ o e `a ˙
’
10
su. d oan thˇng c´ hˆ sˆ g´c |m| ≤ 1; c´c tru.`.ng ho.p kh´c d u.o.c xu. l´ tu.o.ng tu.. Ho.n n˜.a
˙ ¯ .
’ ˙
’
a . ´
o e o o a o . a ¯ . ˙ y
’ . u
.`.ng ho.p c´c d oan thˇng ngang, d u.ng hoˇc c´ hˆ sˆ g´c ±1 l` tˆm thu.`.ng v` ch´ng chı
˙
’
tru o . a ¯ . a ¯´ . ´
a o e o o
. a `a o ı u ˙
’
d i qua c´c pixel trˆn lu.´.i.
¯ a e o
1.1.1 a
. a o ´
Thuˆt to´n sˆ gia
X´t hai pixel A = (xA , yA ) v` B = (xB , yB ) (t´c c´c phˆn tu. cua lattice nguyˆn Z2 ). Phu.o.ng
e a u a ` ˙ ˙
a ’ ’ e
tr` d u.`.ng thˇng AB c´ dang y = mx + t, trong d o hˆ sˆ g´c m = dy/dx v` t = yA − mxA .
ınh ¯ o a˙
’ o . . ´
¯´ e o o a
C´ch d o
a ¯ .n gian nhˆ t dˆ’ v˜ d oan thˇng AB l`:
˙
’ ´ ˙
a ¯e e ¯ . ˙
’
a a
. ´
1. T´ hˆ sˆ g´c m;
ınh e o o
2. Tˇng x mˆt d o.n vi (kho.i d` u t`. d iˆ’m bˆn tr´i nhˆ t), v´.i mˆ i xi t´ yi = mxi + t v`
a o ¯
. . ˙ ¯ˆ u ¯ e
’ a ˙ e a ´
a o o ˜ ınh a
sau d ´ v˜ pixel tai (xi , yi + 0.5 )1 .
¯o e .
Theo c´ch n`y ta chon pixel tˆt nhˆ t, t´.c l` pixel m` khoang c´ch dˆn d u.`.ng thˇng thu.c
a a . ´
o ´
a u a a ˙
’ ´
a ¯e ¯ o ˙
’
a .
´ ˙ ’ a ´
tˆ nho nhˆ t. Phu
e .o.ng ph´p n`y khˆng hiˆu qua do mˆ i bu.´.c lˇp cˆn t´ mˆt ph´p nhˆn,
a a o e ˙
’ ˜
o o a ` ınh o
. . a . e a
mˆt ph´p cˆng v` mˆt ph´p to´n l`m tr`n. Ta c´ thˆ’ khu e
o e o a o e a a o o e ˙ ˙ ’. ph´p nhˆn bˇ ng c´ch ch´ y rˇ ng
a ` a a u´ `a
. . .
yi+1 = mxi+1 + t
= m(xi + ∆x) + t
= yi + m∆x,
v` nˆu bu.´.c tˇng ∆x = 1 th` yi+1 = yi + m.
a e´ o a ı
Do d o nˆu x tˇng mˆt d o.n vi th` y tˇng m d o.n vi. V´.i moi d iˆ’m (xi , yi ) trˆn d oan
¯´ e ´ a o ¯
. . ı a ¯ . o . ¯e˙ e ¯ .
thˇng ta biˆt rˇ ng nˆu xi+1 = xi + 1 th` yi+1 = yi + m; t´.c l`, c´c gi´ tri x v` y d u.o.c t´
˙
a’ e `
´ a ´
e ı u a a a . a ¯ . ınh
a a . .´.c d ´ cua n´ (xem H` 1.2). Dˆy ch´ l` “thuˆt to´n sˆ gia”: v´.i mˆi
theo c´c gi´ tri tru o ¯o ˙ o ’ ınh -a ınh a a ´
a o o o ˜
.
bu.´.c lˇp ta thu.c hiˆn c´c ph´p to´n sˆ gia du.a trˆn bu.´.c tru.´.c.
o a . . e a
. e a o´ . e o o
Kho.i tao ta g´n (x0 , y0 ) l` toa d o nguyˆn cua d iˆ’m xuˆ t ph´t, chˇng han A. Ch´ y
˙ .
’ a a . ¯ˆ . e ˙ ¯e
’ ˙ a´ a ˙
’
a . u´
rˇ ng trong tru.`.ng ho.p |m| > 1 nˆu x tˇng mˆt d o.n vi th` y tˇng ho.n mˆt d o.n vi. Do d ´
`
a o . ´
e a o ¯
. . ı a o ¯
. . ¯o
`
a a ¯ˆ ˙ o ˙ ’ a `
a a a .´.c tˇng mˆt d o.n vi cho y v` tˇng x mˆt
cˆn ho´n d o’i vai tr` cua x v` y bˇ ng c´ch g´n bu o a o ¯ a a o
. . .
.o.ng ∆x =
lu . ∆y 1
= m.
m
1
K´ hiˆu [x], x v` x tu.o.ng u.ng l` phˆn nguyˆn, l`m tr`n xuˆng v` l`m tr`n lˆn cua x.
y e . a ´ a ` a e a o ´
o a a o e ˙
’
11
Du.`.ng thˇng
- o ˙
’
. . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
a
.
. .
. .
. .
.
.c tˆ
. ´
. . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
thu e ....
....
.
.
.
. .
. .
. .
. ....
....
.
. .
. .
. .
. ...
...
.
.
.
.
.
.
.
.
. w .
.
.
. . . . .
....
................................................................................................
.................................................... ....................
................................................
........................ . . .
. ...... . .
.
.
. .
.
. .
.
. ....
.
...
.
. . . ....
.
.
. .
. .
. .... .
.... .
.
.
. .
.
. .
.
. ......
.... .
.
.
.
.
. .
.
. .
.
. ....
....
.
.
.
. . ......
(xi + 1, yi + m ) .........
......... .........
.........
.
.
.
.
.
..........
.
..........
. ..
. .......
.
.
.
.
.
.
.
.
. ....
... .
... .
.
. .......
.
....
..
....
.
.
.
.
.
.
.
.
.
. .............. .
. .......... . . .... .
....
.
. .
.
.
.
.
.
.
.
w
..... .
.
. .... .
.
. .....
.. .. .
..
w .
.
.
.
.
.
.
......................................................................... ..............................................
.........................................................................................................................
. .
.
.
.
.
.
. .
.....
. .. .
.
. .
.
.
.
(xi , yi ) ...........
...........
.
.
.
.
.
.
.
.
. ....
.
....
.
. .
. ...
.... ...
.... .....
.
......
.......
..
. ..
. .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...........
........... ...........
........... . . .....
.
. .......
. . ..
.
. .. .
.
. .
.
.
............. . ....
............. . ... . .
. ...
. .. .
.
. .
.
.
.......
.. . .
.......
.... .
. .. .
. .
.
. .. . .
...................
..................
..
..
.
. w
........ .............................................................................................
.. .
... .
.
.
.
.
.
.
.
....
..
.
.
.
.
.
.
.
......................................................................................................
. .
.
.
. ....
....
. .. . .
.... .
... .
..
. .
.
.
. ..
..
.
.
. .
.
.
. . .
.
. ....
.... . ... .
... .
.
. ..
..
.
.
. .
.
.
....
.... .
....
... .
.
. .
.
. ..
..
.
.
. .
.
.
.
....
... .
.
. .
.
. ..
.
.
. .
.
.
.....
... .
.
. .
.
.
..
..
.
.
. .
.
.
.....
... .
.
. .
.
. ..
.. .
.
.
. .
.
.
.....
... .
.
. .
.
. .. .
.. .
. .
.
.
.....
... .
.
.
.
.
.
.
.
.. . . .
.
.
.....
... . . .. .
.. . .
.
..
. ...
... ..
..
(xi , yi ) (xi + 1, yi + m)
´ ˙
’
H` 1.2: T´ to´n sˆ gia cua (xi , yi ).
ınh ınh a o
V´ du 1.1.1 Gia su. A(2, 0), B(9, 3). Khi d ´ d u.`.ng thˇng qua hai d iˆ’m A v` B c´ hˆ sˆ
ı . ˙ ˙
’ ’ ¯o ¯ o ˙
’
a ¯e˙ a . ´
o e o
g´c m = 3 ∈ (0, 1). Ap dung thuˆt to´n sˆ gia ta d u.o.c d˜y c´c d iˆ’m v˜ tˆt nhˆ t nhu. trong
o 7
´ . a
. a o ´ ¯ . a a ¯e ˙ e o´ a´
˙
’ .´.i:
bang du o
i xi yi yi + 0.5
0 2 0 0
3
1 3 7
0
6
2 4 7
1
9
3 5 7
1
12
4 6 7
2
15
5 7 7
2
18
6 8 7
3
21
7 9 7
3
Thu tuc Line() du.´.i d ay minh hoa thuˆt to´n v˜ d oan thˇng t`. (x0 , y0 ) dˆn (x1 , y1 )
˙ .
’ o ¯ˆ . a
. a e ¯ . ˙
’
a u ´
¯e
v´.i gi´ tri m`u V alue. Diˆ’m kho.i d` u l` d iˆ’m bˆn tr´i nhˆ t. Ngo`i ra ta chı x´t tru.`.ng ho.p
o a . a - e˙ ˙ ¯ˆ a ¯ e
’ a ˙ e a ´
a a ˙ e
’ o .
−1 ≤ m ≤ 1 v` c´c tru o
ı a .`.ng ho.p kh´c c´ thˆ’ thu.c hiˆn do t´ d oi x´.ng. Ho.n n˜.a, ch´ng ta
a o e ˙ . e ´ u
ınh ¯ˆ u u
. .
c˜ng bo qua viˆc kiˆ’m tra c´c tru o
u ˙
’ e e˙ a .`.ng ho.p d ac biˆt: d u.`.ng thˇng nˇ m ngang, d u.ng, xiˆn
˙
’ `
. . ¯ˇ . e ¯ o
. a a ¯´ e
mˆt g´c ±450 . Ch´ y rˇ ng, trong ngˆn ng˜. C, (int)y bˇ ng y + 0.5 .
o o
. u´ ` a o u `
a
void Line(int x_A, int y_A, int x_B, int y_B, int Value)
{
12
int x;
int dx, dy;
float y, m;
dx = x_B - x_A;
dy = y_B - y_A;
m = dy/(float)dx;
y = y0;
for (x = x_A; x D w
....
....
. ..
....
....
....
....
....
(l− ) M .......
...... ....
....
....
. ..
....
...
....
....
....
....
....
....
....
... Q
w ....
....
. ..
....
.... w
....
....
...
C ....
....
. ..
....
....
....
R
....
....
....
...
....
....
. ..
....
....
....
. ....
....
....
....
....
....
.. .
....
...
...
(l+ )
l
H` 1.3: Lu.´.i c´c pixel v` vi tr´ d iˆ’m C, R, D, Q v` M.
ınh o a a . ı ¯e ˙ a
hay tu.o.ng d u.o.ng
¯
f (x, y) := ax + by + c = 0,
trong d ´ a = dy, b = −dx, v` c = b × dx. K´ hiˆu c´c nu.a mˇt phˇng ngo`i v` nu.a mˇt
¯o a y e a ˙
. ’ a
. ˙
’
a a a ˙ ’ a
.
phˇ˙ ng trong x´c d .nh bo.i l tu.o.ng u.ng bo.i
’
a a ¯i ˙
’ ´ ˙
’
(l+ ) := {(x, y) ∈ R2 | f (x, y) > 0},
(l− ) := {(x, y) ∈ R2 | f (x, y) < 0}.
Y tu.o.ng cua thuˆt to´n d iˆ’m gi˜.a l` xˆy du.ng mˆt d˜y c´c d iˆ’m v˜ “tˆt nhˆ t” (xi , yi )
´ ˙
’ ˙
’ a. a ¯e˙ u a a . o a a ¯e
. ˙ e o ´ ´
a
a ¯ˆ u ˙
´ a . d iˆ’m (x , y ) = (x , y ). Kh´i niˆm tˆt nhˆ t o. d ˆy l` nh˜.ng d iˆ’m (x , y ) d u.o.c
bˇt d` u t` ¯ e a e ´
o ´ ’
a ˙ ¯a a u ¯e ˙
0 0 A A . i i ¯ .
chon gˆn v´.i d u.`.ng thˇng thu.c tˆ (dang liˆn tuc) nhˆ t. Theo gia thiˆt, 0 < m < 1, nˆn khi
. ` o ¯ o
a a˙
’ ´
. e . e . ´
a ˙
’ ´
e e
x tˇng mˆt lu .
a o .o.ng ∆x th` y tˇng khˆng qu´ ∆y = m∆x d o.n vi.
ı a o a ¯
. .
V` vˆy nˆu bu.´.c th´. i chon d u.o.c d iˆ’m v˜ tˆt nhˆ t C := (xi , yi ) th` o. bu.´.c th´. i + 1
ı a e
. ´ o u . ¯ . ¯e ˙ e o´ a´ ı ˙ ’ o u
ta s˜ chon d iˆ’m v˜ (xi+1 , yi+1 ), trong d o xi+1 = xi + 1 v` yi+1 = yi hoˇc yi+1 = yi + 1.
e . ¯e ˙ e ¯´ a a
.
N´i c´ch kh´c, bu o
o a a .´.c th´. i + 1 ch´ng ta s˜ chon mˆt trong hai pixel R := (x + 1, y ) hoˇc
u u e . o a
. i i .
D := (xi + 1, yi + 1) (xem H` 1.3). K´ hiˆu Q l` giao d iˆ’m cua hai d u o
ınh y e a ¯e ˙ ˙
’ ¯ .`.ng thˇng l v`
a˙
’ a
.
x = xi + 1. Theo Bresenham, dˆ u cua biˆ’u th´.c x´c d inh bo.i hiˆu gi˜.a hai khoang c´ch t`.
´ ˙
a ’ e˙ u a ¯. ˙
’ e
. u ˙’ a u
a ´
¯e e a ¯. o´
R v` D dˆn Q cho ph´p x´c d inh pixel tˆt nhˆ t o ´ ’
a ˙ . bu.´.c i + 1. Trong thuˆt to´n d iˆ’m gi˜.a,
o a a ¯e ˙ u
.
ta quan s´t vi tr´ cua d iˆ’m gi˜.a M v` c´c nu.a mˇt phˇng x´c d inh bo.i d u.`.ng thˇng l. Dˆ
a . ı ˙ ¯e ’ ˙ u a a ˙ ’ a
. ˙
’
a a ¯. ˙ ¯ o
’ ˙
’
a ˜
e
a ˙
’ ` ´ +
d`ng chı ra rˇ ng, nˆu M ∈ (l ) th` pixel D gˆn v´ ¯ o
a e ı `
a o .i d u.`.ng thˇng l ho.n; nˆu M ∈ (l− ) th`
˙
’
a ´
e ı
pixel R gˆn ho.n. Du.`.ng thˇng l c´ thˆ’ d i ngang qua M ; hoˇc ca hai pixel nˇ m vˆ c`ng
`
a - o ˙
’
a o e ¯˙ a ˙
. ’ `
a ` u
e
o ˙
mˆt nu ’.a mˇt phˇng (l+ ) (hoˇc (l− )) nhu.ng trong bˆ t c´. tru.`.ng ho.p n`o, ta vˆ n chon d iˆ’m
a ˙
’
a a ´
a u o a ˜
a ˙
. . . . . ¯e
gˆn v´.i l nhˆ t. Ho.n n˜.a, sai sˆ-t´.c l` khoang c´ch gi˜.a pixel d u.o.c chon v` d u.`.ng thˇng
`
a o ´
a u ´
o u a ˙
’ a u ¯ . . a ¯ o ˙
a’
.c tˆ l-luˆn luˆn nho ho.n hoˇc bˇ ng 1/2.
a `
. ´
thu e o o ˙
’ . a
14
Dˆ’ ´p dung thuˆt to´n d iˆ’m gi˜.a, chı cˆn t´ f (M ) = f (xi + 1, yi + 1 ) v` kiˆ’m tra
-ea
˙ . a
. a ¯e ˙ u ˙ ` ınh
’ a 2
a e ˙
´ ˙ o
a ’ ¯o ¯. ıa e ´ ´
dˆ u cua n´. Do d ´ ta d inh ngh˜ biˆn quyˆt d. nh
e ¯i
di := f (xi + 1, yi + 1 )
2
1
= a(xi + 1) + b(yi + 2 ) + c.
Khi d ´
¯o
´
1. Nˆu di > 0 chon pixel D;
e .
´
2. Nˆu di < 0 chon pixel R;
e .
´
3. Nˆu di = 0 chon mˆt trong hai pixel R hoˇc D, do d ´ chon R.
e . o
. a
. ¯o .
Kˆ tiˆp ta cˆn x´c d inh toa d ˆ d iˆ’m gi˜.a M v` do d o biˆn quyˆt d .nh di+1 o. bu.´.c i + 1;
´ ´
e e `
a a ¯. . ¯o ¯ e
. ˙ u a ¯´ e ´ ´
e ¯i ˙
’ o
d˜ nhiˆn d iˆu n`y phu thuˆc v`o viˆc chon pixel R hoˇc D. Nˆu chon R th` ho`nh d o d iˆ’m
ı e ¯` e a . o a
. e
. . a
. ´
e . ı a ¯ˆ ¯ e
. ˙
M tˇng mˆt d o.n vi v` tung d o khˆng d o’i. Do d o
a o ¯
. . a ¯ˆ o ¯ˆ
. ˙ ¯´
1 1
di+1 = f (xi + 2, yi + ) = a(xi + 2) + b(yi + ) + c.
2 2
Nhu.ng
1
di = a(xi + 1) + b(yi + ) + c.
2
Suy ra di+1 = di + a.
K´ hiˆu sˆ gia d u.o.c cˆng thˆm khi R d u.o.c chon l` ∆R := a = dy. N´i c´ch kh´c, ta
. ´
y e o ¯ . o . e ¯ . . a o a a
c´ thˆ’ suy ra biˆn quyˆt d .nh o
o e ˙ ´
e ´
e ¯i ˙
’. bu.´.c kˆ tiˆp t`. biˆn quyˆt d inh o. bu.´.c hiˆn h`nh bˇ ng
´ ´
o e e u e ´ ´
e ¯. ˙
’ o e a `
a
.
o. e ´
o a o `
a ˙ ınh . a .
’
c´ch cˆng thˆm sˆ gia ∆R m` khˆng cˆn phai t´ lai gi´ tri f (M ).
a
Nˆu chon D th` ho`nh d o v` tung d o d iˆ’m M c`ng tˇng mˆt d o.n vi, nˆn
´
e . ı a ¯ˆ a
. ¯ˆ ¯ e
. ˙ u a o ¯
. . e
3 3
di+1 = f (xi + 2, yi + ) = a(xi + 2) + b(yi + ) + c.
2 2
V` do d ´
a ¯o
di+1 = di + a + b.
K´ hiˆu sˆ gia d u.o.c cˆng v`o di+1 sau khi chon D l` ∆D := a + b = dy − dx.
. ´
y e o ¯ . o . a . a
V` o. bu.´.c d` u tiˆn, ta chon (x0 , y0 ) = (xA , yA ) nˆn c´ thˆ’ t´ tru.c tiˆp gi´ tri kho.i
ı ˙
’ o ¯aˆ e . ˙
e o e ınh . ´
e a . ˙
’
tao d0 . Thˆt vˆy, d iˆ’m gi˜.a d` u tiˆn c´ toa d ˆ (x0 + 1, y0 + 1 ), v`
. a a ¯e
. . ˙ u ¯ˆ a e o . ¯o . 2
a
f (x0 + 1, y0 + 1 ) = a(x0 + 1) + b(y0 + 2 ) + c
2
1
= ax0 + by0 + c + a + b/2
= f (x0 , y0 ) + a + b/2.
15
Nhu.ng (x0 , y0 ) thuˆc d u.`.ng thˇng l nˆn f (x0 , y0 ) = 0; do d ´ gi´ tri kho.i d` u cua biˆn
o ¯ o
. ˙
’
a e ¯o a . ˙ ¯ˆ
’ a ˙
’ ´
e
´
quyˆt d .nh l` d0 = a + b/2 = dy − dx/2. Su .
e ¯i a ˙
’. dung d ta c´ thˆ’ chon pixel th´. hai, th´.
o e ˙ . u u
0
-e˙ ’. mˆu sˆ trong d ta d inh ngh˜ lai h`m f bˇ ng c´ch nhˆn n´ cho 2; t´.c l`
ba, v.v. Dˆ’ khu a o
˙ ˜ ´ ¯. ıa . a `
a a a o u a
0
a a a a ` ´
o a e ´ ´
f (x, y) = 2(ax + by + c). N´i c´ch kh´c, nhˆn 2 cho c´c hˇ ng sˆ a, b, c v` biˆn quyˆt d inh;
o a e ¯.
m` d iˆu n`y khˆng anh hu.o.ng dˆn dˆ u cua biˆn quyˆt d .nh.
a ¯`e a o ˙ ’ ˙
’ ´ ´ ˙
¯e a ’ ´
e ´
e ¯i
Tˆ’ng qu´t ho´ thuˆt to´n d iˆ’m gi˜.a v˜ d oan thˇng AB (trong tru.`.ng ho.p xA < xB
o˙ a a a
. a ¯e ˙ u e ¯ . ˙
’
a o .
v` 0 < m < 1) nhu
a . sau:
1. [Kho.i tao] Dˇt dx = xB − xA , dy = yB − yA , d0 = 2dy − dx, ∆R = 2dy, ∆D = 2(dy −
˙ . -a
’ .
dx), x0 = xA , y0 = yA .
2. Gia su. o. bu.´.c th´. i ta c´ d iˆ’m v˜ tˆt nhˆ t (xi , yi ) v` biˆn quyˆt d .nh di .
˙ ˙ ˙
’ ’ ’ o u o ¯e ˙ e o´ ´
a a e ´ ´
e ¯i
e e a
. -a ¯e
3. [V˜ pixel hiˆn h`nh] Dˇt d iˆ’m v˜ tai (xi , yi ).
. ˙ e .
4. [Cˆp nhˆt] Nˆu xi = xB , thuˆt to´n d`.ng; ngu.o.c lai, d at
a
. a
. ´
e a
. a u . . ¯ˇ .
xi+1 = xi + 1;
yi ´
nˆu di ≤ 0,
e
yi+1 =
yi + 1 nˆu ngu.o.c lai;
´
e . .
di + ∆R nˆ´u di ≤ 0,
e
di+1 =
di + ∆D nˆu ngu.o.c lai.
´
e . .
5. Thay i bˇ ng (i + 1) v` lˇp lai Bu.´.c 3.
`
a a a .
. o
V´ du 1.1.2 Gia su. A(2, 0), B(9, 3). Khi d ´ d u.`.ng thˇng qua hai d iˆ’m A v` B c´ hˆ sˆ
ı . ˙ ˙
’ ’ ¯o ¯ o ˙
’
a ¯e ˙ a . ´
o e o
g´c m = 3 ∈ (0, 1). Dˆ d`ng kiˆ’m tra rˇ ng
o 7
˜ a
e e˙ `
a
dx = xB − xA = 7,
dy = yB − yA = 3,
d0 = 2dy − dx = −1,
∆R = 2dy = 6,
∆D = 2(dy − dx) = −8.
16
Ap dung thuˆt to´n d iˆ’m gi˜.a ta c´ d˜y c´c d iˆ’m v˜ tˆt nhˆ t nhu. trong bang du.´.i:
´ . a
. a ¯e ˙ u o a a ¯e ˙ e o´ ´
a ˙
’ o
i xi yi di
0 2 0 −1
1 3 0 5
2 4 1 −3
3 5 1 3
4 6 2 −5
5 7 2 1
6 8 3 −7
7 9 3 −1
Hiˆ’n nhiˆn rˇ ng c´c kˆt qua n`y tr`ng v´.i kˆt qua khi su. dung phu.o.ng ph´p sˆ gia trong
e˙ e ` a a e ´ ˙ a
’ u o e ´ ˙
’ ˙ .
’ a o ´
V´ du 1.1.1.
ı .
Ch´ y rˇ ng, ph´p t´ cˆn thiˆt d oi v´.i di+1 trong mˆ i bu.´.c lˇp l` ph´p cˆng v` khˆng
u´ ` a e ınh ` a ´ ´
e ¯ˆ o ˜
o o a a e o
. . a o
c´ ph´p nhˆn. Ho
o e a .n n˜.a, v`ng lˇp ho`n to`n d o.n gian nhu. trong thu tuc MidPointLine()
u o a a a ¯ ˙
’ ˙ .
’
.
du.´.i d ˆy:
o ¯a
void MidPointLine(int x_A, int y_A, int x_B, int y_B, int Value)
{
int x, y, d, dx, dy, DeltaR, DeltaD;
dx = x_B - x_A;
dy = y_B - y_A;
d = 2*dy - dx;
DeltaR = 2*dy;
DeltaD = 2*(dy - dx);
y = y_A;
for (x = x_A; x y++;
}
}
}
1.1.3 . ´ ´
o o a ¯ˆ e e ¯ˆ´ a
. a e ¯oa ˙
’
Mˆt sˆ vˆ n d` liˆn quan d e n thuˆt to´n v˜ d . n thˇ ng
a
Th´. tu. cua c´c d e’m d` u cuˆi. Trong mˆt u.ng dung ta cˆn d `i hoi mˆt d oan thˇng
u . ˙ ’ a ¯iˆ ˙ ¯ˆ a ´
o o ´
. . ` ¯o ˙
a ’ o ¯ .
. ˙
’
a
d u.o.c v˜ t`. A dˆn B ch´.a c`ng tˆp c´c pixel nhu. d oan thˇng d u.o.c v˜ t`. B dˆn A; n´i
¯ . e u ¯e ´ u u a a
. ¯ . ˙
’
a ¯ . e u ´
¯e o
c´ch kh´c, d oan thˇng d u.o.c v˜ khˆng phu thuˆc v`o th´. tu. c´c d iˆ’m d` u cuˆi. Su. sai kh´c
a a ¯ . ˙’
a ¯ . e o . o a
. u . a ¯ e ¯a ˙ ˆ ´
o . a
chı c´ thˆ’ xay ra tai nh˜
˙ o e ˙
’ ˙ ’ u.ng d iˆ’m v˜ m` d u.`.ng thˇng d i qua d iˆ’m gi˜.a v` biˆn quyˆt d inh
¯e ˙ e a ¯ o ˙
’
a ¯ ¯e˙ u a e ´ ´
e ¯.
.
bˇ ng khˆng; trong tru.`.ng ho.p n`y, d i t`. tr´i sang phai ch´ng ta chon d iˆ’m v˜ R. Do t´
`
a o o . a ¯ u a ˙
’ u . ¯e ˙ e ınh
´
d ˆi x´
¯o u .ng, khi d i t`. phai sang tr´i v` d = 0 l˜ ra ta chon d iˆ’m v˜ R, nhu.ng chon lu.a n`y s˜
¯ u ˙
’ a a e ˙
. ¯e e . . a e
sai lˆch mˆt d o.n vi theo th`nh phˆn y v´.i pixel d u.o.c chon khi d i t`. tr´i sang phai. Do d ´
e
. o ¯
. . a `
a o ¯ . . ¯ u a ˙
’ ¯o
u `
ch´ng ta cˆn chon pixel D khi d i t`
a ¯ u . phai sang tr´i trong tru.`.ng ho.p d = 0. L´ luˆn tu.o.ng
˙
’ a o y a
. . .
. d oi v´.i c´c d oan thˇng c´ hˆ sˆ g´c bˆ t k`.
˙’
. ´
tu ¯ˆ o a ¯ . a . ´
o e o o a y ´
Phu.o.ng ph´p ho´n d o’i c´c d iˆ’m d` u cuˆi cua d oan thˇng dˆ’ thuˆt to´n xu. l´ theo
a ˙
a ¯ˆ a ¯ e ¯ˆ ˙ a ´ ’
o ˙ ¯ . ˙
’
a ¯e˙ a
. a ˙ y
’
c`ng hu.´.ng khˆng thu.c hiˆn ch´ x´c khi ch´ng ta v˜ c´c d oan thˇng theo mˆ u tˆ. C´c
u o o . e
. ınh a u e a ¯ . ˙
’
a ˜
a o a
d oan thˇng v˜ theo mˆ u thu.`.ng “neo” nh˜.ng dˆ u hiˆu tai d iˆ’m xuˆ t ph´t, c´ thˆ’ l` d iˆ’m
¯ . a˙
’ e ˜
a o u ´
a e . ¯e
. ˙ a´ a o e a ¯e˙ ˙
du.´.i bˆn tr´i, khˆng phu thuˆc v`o hu.´.ng di chuyˆ’n. Dˇc biˆt, v´.i mˆu tˆ chˆ m-gach,
o e a o . o a
. o e˙ -a. e
. o ˜
a o a ´ .
chˇng han 111100, ch´ng ta muˆn v˜ mˆ u n`y tai d iˆ’m xuˆ t ph´t m` khˆng tu ¯o ¯o
˙
’
a u ´ ˜
o e a a . ¯e ˙ ´
a a a o . d ˆng d ˆ’i
˙
. . .
th`nh d iˆ’m du.´.i bˆn tr´i. Ngo`i ra, nˆu thuˆt to´n luˆn luˆn d at lai c´c d iˆ’m d` u cuˆi
a ¯e ˙ o e a a ´
e a
. a o o ¯ˇ . a ¯ e ¯a
. ˙ ˆ ´
o
. tu. ch´ tˇc, ta cˆn di chuyˆ’n t`. tr´i sang phai v´.i d oan thˇng AB v` t`. phai
theo th´ . ınh a
u ´ `a ˙
e u a ˙ o ¯ .
’ ˙
’
a a u ˙
’
sang tr´i v´.i d oan thˇng BA; d iˆu n`y tao ra su. gi´n d oan trong qu´ tr` v˜, chˇng han
a o ¯ . ˙
’
a ¯`e a . . a ¯ . a ınh e ˙
’
a .
d a gi´c, tai nh˜
¯ a u.ng d ınh chung.
¯˙’
.
- e
Diˆ’m xuˆ t ph´t nˇ m trˆn canh cu a d gi´c cˇt. Mˆt vˆ n d` kh´c ch´ng ta cˆn
˙ a´ a `
a e . ˙ ¯a a a
’ ´ o a ¯ˆ a
. ´ e u `
a
˙’.a d ˆ’i thuˆt to´n dˆ’ v˜ c´c d oan thˇng sau khi d u.o.c cˇt bo.i mˆt trong c´c thuˆt to´n
su ¯o ˙ a ˙
a ¯e e a ¯ . ˙
’
a ¯ . a ˙ ´ ’ o a a a
. . .
trong Phˆn 3.3. H` 1.4(a) minh hoa d oan thˇng d u.o.c cˇt bo.i canh bˆn tr´i, x = xmin ,
`a ınh . ¯ . ˙
’
a ¯ . a ˙ .´ ’ e a
˙
’
cua h` ch˜
ınh u . nhˆt. Giao d iˆ’m cua d oan thˇng v` canh bˆn tr´i c´ ho`nh d ˆ x nguyˆn
a ¯e ˙ ˙ ¯ .
’ ˙
’
a a . e a o a ¯o e
. .
nhu.ng tung d o y thu.c. Pixel (xmin , mxmin + t + 0.5 ) trˆn canh x = xmin ch´ l` pixel
¯ˆ. . e . ınh a
¯ .o.c v˜ tai ho`nh d o x
du . e . a ˙ ¯ .
’ ˙
’
¯ˆ min cua d oan thˇng tru o
a .´.c khi cˇt theo thuˆt to´n d iˆ’m gi˜.a2 . V´.i
´
a a a ¯e˙ u o
. .
˙
’.i tao d a biˆt, kˆ tiˆp ch´ng ta cˆn kho.i tao biˆn quyˆt d inh tai d iˆ’m gi˜.a d oan
pixel kho . ¯˜ e ´ e e ´ ´ u `
a ˙ .
’ ´
e ´
e ¯. ˙
. ¯e u ¯ .
. ´ ` u´ `
RD trong cˆt kˆ bˆn. Cˆn ch´ y rˇ ng, c´ch l`m n`y tao ra d˜y ch´ x´c c´c pixel, trong
o e e a a a a a . a ınh a a
2
Khi mxmin + t nˇ m gi˜.a hai d u.`.ng thˇng ngang kˆ nhau, ch´ng ta cˆn l`m tr`n xuˆng. Dˆy l` hˆ qua
`
a u ¯ o ˙
’
a `
e u ` a
a o ´
o -a a e . ˙
’
˙ a viˆc chon pixel R khi d = 0.
’
cu e
. .
18
x = xmin
.
.
. .
.
.
. .
.
.
.
. .
.
.
.
. .
.
.
.
. .
.
.
. .
.
.
. ..
..
.
. .
.
. .....
.....
. . .....
.....
.
.
.
.
.
.
.
. i
D.
.
.
.
.
.
. .....
.....
...........................................................................................
.....................................................................
. .
.
.....
.....
.....
.....
....................................................................
............................................. . . ... .
...
.
.
. .
. .....
.....
. .
. .....
.....
.
.
. .
. .....
.....
. .
. .....
.....
M—
.
. .
. ...
...
.
.
. .
. .....
.....
. .
. .....
.....
.
. . .....
.....
(xmin , mxmin + t + 0.5 ) ........
........
........ . .
........ . .
y
....... .
...... .
.
.
.
i
.
.
.
.
.
. .....
. .....
. .........
.....
.....
.......................................... .............................................................................................
.........................................................................................................................................
.... .. ... . ...
..
.
. . .
... .
. .....
..... .
.
(xmin , mxmin + t) •
.
.................. .. . .........
.................. . . . .......
.
......... .....
...... . ....
.. . .
.....
.. .
.
.
R
.
.
.
.
.
.
.
..
.. ..... .
..... . . .
.
..
.. .....
..... .
.
.
.
.
.
.
..
.. .....
..... .
.
. .
.
.. .....
..... .
.
.
.
.
.
.........
......... .
..
. .....
..... .
.
.
.
.............................................................................................................................
..............................................................................................................................
.
.
...
.. .
. .
.
..
.. .
..
.. .....
..... .
.
.
.
.
.
.
.
..
.. .....
..... .
.
. .
.
.....
..... .
. .
.
.
.....
.... .
.
.
.
.
.
.
.
.
. .
.
.
.
.
. .
.
.
. .
.
. .
.
. .
.
...............................................................................................................
. ...................... ........................................................................................
. . y = ymin
(a)
x = .xmin
.
.
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
.
.
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
.
.
. .
.
. .
.
. .
.
. .
.
. .
.
. .
.
. .
.
. .
.
. .
.
. .
.
.
. .
...
.
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .......
. .....
.
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .......
.......
.
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .......
.......
.
.
.
.
.
. .
.
. .
.
. .
.
. .
.
. .
.
. .
.
. .
.
. .
.
. . ..........
.
.
. .......
. . . . . . . . . . .......
.......
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
y .
.
. . y ..... .
. ..... ..... . y
..................................................................................................................................................................................................................
. .
............................................................... ................................... .............................................................................................................
. .
y
.
.
. .
. .
. .
. .
. .
. .
. .
. .
. .......
...
.......
.
.
.
.
.
.
.
.
. .
.
. .
.
. .
.
. .
.
. .
.
. .
.
. . ............ .
.
. ..........
.
.
. .
.
.
.
. .
.
. .
.
. .
.
. .
.
. .
.
. .
.
. .
.
. .... ..
.......
. .
... .
. .
.
. .
.
.
.
.
.
.
.
.
. .
.
. .
.
. .
.
. .
.
. .
.
. . .. ......... .
............
. .
.
. .
.
.
. . . . . . . .......
....... . . .
iD y yC y
.
. .
. .
. .
. .
. .
. .
. . .
... .
. .
. .
.
.
. . . . . . . ...........
..........
. . . .
i.
.
. i .
.
.
.
.
.
.
.
i
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. .... .....
. ..... ..
.
....... .
..
...
.
.
.
.
.
.
.
.
.
.
.
y .
.
.
.
.
.
.
i .
.
.
.
.
.
.
i .
.
.
.
.
.
.
i
. ................. ................................... .......................................... ............ .........................................................................................
.......................................................................................................................................................................................................
. . y = ymin
y = ymin − 1 ... ... ... ... ..
.
.
.
.
.
.
.
.
.
.
.
.... .... .... .... .... ... ... . .. ... ... . .. ............
.
.
.
.
.
.
.
..
. ........
I• .
. ... ...
. ...
.
.
.
..
....... .
. ............. .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..... ... ... . ... ... ... ... ... ... ... ... .. . ... ... ... ... ... .... ... ...
.
..
.
.
.
.
.. .... .... .... .... .... .... .... ............. .... ..... .... .... .... .... .... .... .... .... .... .... .... .... .... .... ..... .... ....
.
.
.
.
.
.
.
.
.
.
..
2 .
.
. .
.
. .
.
... .. .
.......
....... .
.
. .
.
. .
.
. .
.
. .
.
. .
.
. .
.
.
.
. . .. ......... .
.
. ............. . .
. .
. .
. .
. .
. .
. .
.
y = ymin − 1 y y .
.
.
. ........... .
.
.............
. . y
. ...
.
.
. y
.
.
.
.
.
.
.
.
.
.
y .
.
.
.
.
.
y .
.
.
.
.
y .
.
.
.
.
y .
.
.
.
.
.
.
.
.
.
.
.
.
........................... ........................................................................ ...........................................................................................................
.................................................................................................................................................................................................................
. . . . .
.
.
.
.
..... .
..... .
... .
.. .
. .
.
. .
.
. .
.
. .
.
. .
.
. .
.
. .
.
. .
.
. .
.
.
...
... .......
....... . .
.
. .
.
. .
.
. .
.
. .
.
. .
.
. .
.
. .
.
. .
.
.
...
.. .......
.......
.
.
. .
.
. .
.
. .
.
. .
.
. .
.
. .
.
. .
.
. .
.
. .
.
.
...
... .......
....... .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. .
. .
. .
. .
. .
. .
. .
. .
. .
.
.
.
. .
.
. .
.
. .
.
. .
.
. .
.
. .
.
. .
.
. .
.
. .
.
.
(b)
H` 1.4: Diˆ’m xuˆ t ph´t nˇ m trˆn biˆn h` ch˜. nhˆt. (a) Giao v´.i canh d u.ng. (b) Giao
ınh - e˙ ´
a a ` a e e ınh u a . o . ¯´
.i canh ngang.
v´ .
o
19
Copyright by webtailieu.net