Đồ họa máy tính
D
-
ˆ
O
`
HO
.
A M
´
AY T
´
INH I
Pha
.
m Tiˆe
´
n So
.
n
D
-
`a La
.
t, 2005
2

t to´an sˆo
´
gia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.1.2 Thuˆa
.
t to´an d¯iˆe
˙’
m gi˜u
.
a . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.1.3 Mˆo
.
t sˆo
´
vˆa
´
n d¯ˆe
`
liˆen quan d¯ˆe
´
n thuˆa
.
t to´an v˜e d¯oa
.
n thˇa
˙’
ng . . . . . . . . 18
1.1.4 C´ac thuˆo
.
c t´ınh cu

`o
.
ng tr`on . . . . . . . . . . . . . . . . . . 23
1.3 D
-
u
.
`o
.
ng cong ellipse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.3.1 Ellipse c´o da
.
ng ch´ınh tˇa
´
c . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.3.2 Ellipse trong tru
.
`o
.
ng ho
.
.
p tˆo
˙’
ng qu´at . . . . . . . . . . . . . . . . . . . 34
2 H`ınh ho
.
c cu
˙’
a c´ac d¯u

.
ng cong Bezier . . . . . . . . . . . . . . . . 52
2.3 C´ac t´ınh chˆa
´
t cu
˙’
a d¯u
.
`o
.
ng cong Bezier . . . . . . . . . . . . . . . . . . . . . . 55
2.3.1 D
-
iˆe
`
u khiˆe
˙’
n d¯i
.
a phu
.
o
.
ng . . . . . . . . . . . . . . . . . . . . . . . . . . 59
2.4 D
-
a th´u
.
c t`u
.

.
so
.
˙’
. . . . . . . . . . . . . . . . . . . . . . . . . 66
2.4.5 Su
.
˙’
du
.
ng c´ac knot bˆo
.
i . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
2.4.6 Vector knot chuˆa
˙’
n . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
2.5 C´ac t´ınh chˆa
´
t cu
˙’
a d¯u
.
`o
.
ng cong B-spline . . . . . . . . . . . . . . . . . . . . . 75
2.6 Nˆo
.
i suy c´ac d¯iˆe
˙’
m d¯iˆe

3.1 Mo
.
˙’
d¯ˆa
`
u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
3.2 Giao cu
˙’
a hai d¯oa
.
n thˇa
˙’
ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
3.2.1 Phˆan t´ıch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
4
3.2.2 Thuˆa
.
t to´an x´ac d¯i
.
nh giao hai d¯oa
.
n thˇa
˙’
ng . . . . . . . . . . . . . . . . 86
3.3 D
-
oa
.
n thˇa
˙’

.
n thˇa
˙’
ng v`a d¯a gi´ac lˆo
`
i . . . . . . . . . . . . . . . . . . . . . . . 100
3.4.1 Vi
.
tr´ı tu
.
o
.
ng d¯ˆo
´
i cu
˙’
a mˆo
.
t d¯iˆe
˙’
m v´o
.
i d¯u
.
`o
.
ng thˇa
˙’
ng . . . . . . . . . . . . 100
3.4.2 Thuˆa

`
ng k´ın . . . . . . . . . . . . . . . . 114
3.6.1 Vector pha
˙’
n xa
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
3.6.2 Giao cu
˙’
a tia s´ang v`a d¯u
.
`o
.
ng thˇa
˙’
ng . . . . . . . . . . . . . . . . . . . 117
3.6.3 Giao cu
˙’
a tia s´ang v´o
.
i d¯u
.
`o
.
ng tr`on . . . . . . . . . . . . . . . . . . . . 121
3.6.4 Xˆay du
.
.
ng v´ı du
.

t to´an tˆo m`au theo con cha
.
y . . . . . . . . . . . . . . . . . . . . . . . . 131
4.4 Thuˆa
.
t to´an tˆo m`au theo biˆen . . . . . . . . . . . . . . . . . . . . . . . . . . 134
4.5 So s´anh c´ac thuˆa
.
t to´an . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
4.6 Tˆo m`au c´ac h`ınh ch˜u
.
nhˆa
.
t . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
4.7 Thuˆa
.
t to´an tˆo m`au d¯a gi´ac . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
4.7.1 C´ac d`ong qu´et ngang . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
4.7.2 C´ac ma
˙’
nh vu
.
n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
4.7.3 Liˆen kˆe
´
t ca
.
nh v`a thuˆa
.
t to´an tr`an . . . . . . . . . . . . . . . . . . . . 151

ˆo
`
ho
.
a m´ay t´ınh l`a mˆo
.
t l˜ınh vu
.
.
c hˆa
´
p dˆa
˜
n cu
˙’
a khoa ho
.
c m´ay t´ınh. Ch´ung ta su
.
˙’
du
.
ng d¯ˆo
`
ho
.
a
m´ay t´ınh nhu
.
mˆo

.
a tu
.
o
.
ng t´ac
cho ph´ep ngu
.
`o
.
i su
.
˙’
du
.
ng l`am viˆe
.
c theo c´ach tu
.
.
nhiˆen nhˆa
´
t: ngu
.
`o
.
i su
.
˙’
du

`
ng h`ınh a
˙’
nh. D
-
ˆo
`
ho
.
a m´ay t´ınh d¯ang gi´up con ngu
.
`o
.
i thay d¯ˆo
˙’
i vˆe
`
quan niˆe
.
m v`a
c´ach th´u
.
c su
.
˙’
du
.
ng m´ay t´ınh.
Gi´ao tr`ınh D
-

.
a m´ay t´ınh ba chiˆe
`
u, mˆo
.
t phˆa
`
n quan tro
.
ng khˆong thˆe
˙’
thiˆe
´
u d¯u
.
o
.
.
c s˜e d¯u
.
o
.
.
c
d¯ˆe
`
cˆa
.
p trong mˆo
.

n [9] v`a [11]. C´ac phu
.
o
.
ng
ph´ap phˆan t´ıch v`a thiˆe
´
t kˆe
´
c´ac thuˆa
.
t to´an trong gi´ao tr`ınh cho ph´ep sinh viˆen c´o thˆe
˙’
viˆe
´
t
dˆe
˜
d`ang c´ac chu
.
o
.
ng tr`ınh minh ho
.
a. Gi´ao tr`ınh d¯u
.
o
.
.
c biˆen soa

˙’
i
sang c´ac ngˆon ng˜u
.
kh´ac; v`a do d¯´o, sinh viˆen cˆa
`
n c´o mˆo
.
t sˆo
´
kiˆe
´
n th´u
.
c vˆe
`
ngˆon ng˜u
.
C. Ngo`ai
ra, hˆa
`
u hˆe
´
t c´ac chu
.
o
.
ng tr`ınh thao t´ac trˆen cˆa
´
u tr´uc d˜u

a nh˜u
.
ng nˇam d¯ˆa
`
u d¯a
.
i ho
.
c: hiˆe
˙’
u biˆe
´
t vˆe
`
d¯a
.
i sˆo
´
tuyˆe
´
n t´ınh v`a h`ınh ho
.
c gia
˙’
i t´ıch, ph´ep t´ınh vi t´ıch phˆan.
Mu
.
c d¯´ıch cu
˙’
a gi´ao tr`ınh l`a, o

n viˆe
´
t v`a cha
.
y thu
.
˙’
c´ac chu
.
o
.
ng tr`ınh. Mˆo
.
t trong
nh˜u
.
ng mu
.
c d¯´ıch ch´ınh cu
˙’
a gi´ao tr`ınh l`a gi´up sinh viˆen nˇa
´
m v˜u
.
ng c´ac phu
.
o
.
ng ph´ap, tru
.

o
.
ng v`a mˆo
.
t phˆa
`
n phu
.
lu
.
c v´o
.
i nh˜u
.
ng nˆo
.
i dung ch´ınh nhu
.
sau:
• Chu
.
o
.
ng th´u
.
nhˆa
´
t d¯ˆe
`
cˆa

`
ng h`ınh ho
.
c l`a nˆo
.
i dung ch´ınh cu
˙’
a Chu
.
o
.
ng 2. Hˆa
`
u hˆe
´
t c´ac
phˆa
`
n mˆe
`
m d¯ˆo
`
ho
.
a d¯ˆe
`
u c´o nh˜u
.
ng ch´u
.

ng n`ay cung cˆa
´
p nh˜u
.
ng nguyˆen l´y v`a c´ach tiˆe
´
p cˆa
.
n
thu
.
.
c h`anh m`a c´ac tr`ınh ´u
.
ng du
.
ng d¯ˆo
`
ho
.
a ´ap du
.
ng.
• Chu
.
o
.
ng 3 gia
˙’
i quyˆe

t) v`a giao
cu
˙’
a hai d¯a gi´ac. Cuˆo
´
i chu
.
o
.
ng l`a mˆo
.
t v´ı du
.
cu
˙’
a k˜y thuˆa
.
t “ray tracing” hai chiˆe
`
u:
Chuyˆe
˙’
n d¯ˆo
.
ng cu
˙’
a tia s´ang trong buˆo
`
ng k´ın c´o ch´u
.

i
phˆa
`
n trong, bo
.
˙’
i d¯u
.
`o
.
ng biˆen v`a v`ung l`a d¯a gi´ac.
• Phˆa
`
n phu
.
lu
.
c l`a thu
.
viˆe
.
n c´ac cˆa
´
u tr´uc d˜u
.
liˆe
.
u v`a c´ac h`am cˆa
`
n thiˆe

`
n l´y thuyˆe
´
t c˜ung nhu
.
gi´up sinh viˆen nˇa
´
m v˜u
.
ng kiˆe
´
n th´u
.
c d¯˜a ho
.
c. Ngo`ai ra, c´ac
lˆo
˜
i trong xuˆa
´
t ba
˙’
n lˆa
`
n tru
.
´o
.
c c˜ung d¯˜a d¯u
.

.
d¯˜a nhˆa
.
n d¯u
.
o
.
.
c t`u
.
nhiˆe
`
u ngu
.
`o
.
i m`a khˆong thˆe
˙’
liˆe
.
t kˆe
hˆe
´
t, d¯ˇa
.
c biˆe
.
t l`a c´ac ba
.
n sinh viˆen, trong qu´a tr`ınh biˆen soa

.
raster
Chu
.
o
.
ng n`ay tr`ınh b`ay c´ac thuˆa
.
t to´an v˜e d¯oa
.
n thˇa
˙’
ng, d¯u
.
`o
.
ng tr`on v`a ellipse trˆen lattice
nguyˆen Z
2
. C´ac thuˆa
.
t to´an chı
˙’
thao t´ac trˆen nh˜u
.
ng sˆo
´
nguyˆen v`a trong c´ac v`ong lˇa
.
p chı

nh to
.
a d¯ˆo
.
cu
˙’
a c´ac pixel nˇa
`
m trˆen hoˇa
.
c gˆa
`
n v´o
.
i d¯oa
.
n thˇa
˙’
ng
thu
.
.
c tˆe
´
nhˆa
´
t. Vˆe
`
nguyˆen tˇa
´

c tˆe
´
d¯u
.
o
.
.
c xˆa
´
p xı
˙’
v´o
.
i mˆa
.
t d¯ˆo
.
mˆo
.
t pixel; ta cˆa
`
n c´o
nh˜u
.
ng t´ınh chˆa
´
t g`ı? V´o
.
i c´ac d¯oa
.

sˆo
´
g´oc nˇa
`
m ngo`ai d¯oa
.
n n`ay, c´o d¯´ung
mˆo
.
t pixel d¯u
.
o
.
.
c v˜e trˆen mˆo
˜
i h`ang. Tˆa
´
t ca
˙’
c´ac d¯oa
.
n thˇa
˙’
ng d¯u
.
o
.
.
c v˜e v´o

thˇa
˙’
ng c˜ung cˆa
`
n ch´u ´y d¯ˆe
´
n c´ac thuˆo
.
c t´ınh cu
˙’
a d¯oa
.
n thˇa
˙’
ng nhu
.
d¯ˆo
.
rˆo
.
ng, kiˆe
˙’
u v˜e Thˆa
.
m ch´ı
ch´ung ta muˆo
´
n cu
.
.

˙’
du
.
ng k˜y thuˆa
.
t antialiasing (xem [9], [11]) bˇa
`
ng c´ach ´ap du
.
ng kha
˙’
nˇang d¯ˇa
.
t cu
.
`o
.
ng
d¯ˆo
.
cu
˙’
a mˆo
˜
i pixel trˆen c´ac thiˆe
´
t bi
.
hiˆe
˙’

˙’
ng d¯ˆo
.
rˆo
.
ng mˆo
.
t pixel v`a c´o d¯´ung mˆo
.
t
pixel trˆen mˆo
˜
i cˆo
.
t (hoˇa
.
c h`ang d¯ˆo
´
i v´o
.
i c´ac d¯oa
.
n thˇa
˙’
ng dˆo
´
c). Phˆa
`
n cuˆo
´

.
t pixel nhu
.
mˆo
.
t chˆa
´
m tr`on v´o
.
i tˆam ta
.
i vi
.
tr´ı (x, y) cu
˙’
a pixel trˆen lu
.
´o
.
i c´ac to
.
a d¯ˆo
.
nguyˆen Z
2
. Biˆe
˙’
u diˆe
˜
n n`ay l`a mˆo

c v`ao hˆe
.
thˆo
´
ng) gi˜u
.
a c´ac vˆe
´
t trˆen m`an h`ınh hiˆe
˙’
n thi
.
. Trong mˆo
.
t sˆo
´
hˆe
.
thˆo
´
ng, c´ac chˆa
´
m kˆe
`
nhau phu
˙’
lˆa
´
p mˆo
.

˙’
ng c´ach theo
chiˆe
`
u ngang nho
˙’
ho
.
n theo chiˆe
`
u d¯´u
.
ng. Mˆo
.
t kh´ac biˆe
.
t n˜u
.
a tu`y theo hˆe
.
thˆo
´
ng trong viˆe
.
c biˆe
˙’
u
diˆe
˜
n hˆe

.
ng thˇa
˙’
ng kˆe
`
nhau cu
˙’
a lu
.
´o
.
i d¯iˆe
`
u khiˆe
˙’
n thay cho nˇa
`
m trˆen c´ac d¯u
.
`o
.
ng thˇa
˙’
ng cu
˙’
a
lu
.
´o
.

nhˆa
.
t t`u
.
(x, y) d¯ˆe
´
n (x, y) khˆong ch´u
.
a pixel n`ao, trong khi v´o
.
i nh˜u
.
ng hˆe
.
thˆo
´
ng kh´ac, c´o d¯´ung mˆo
.
t
pixel ta
.
i d¯iˆe
˙’
m n`ay. Du
.
´o
.
i d¯ˆay ch ´ung ta s˜e biˆe
˙’
u diˆe

d¯ˆo
.
rˆo
.
ng mˆo
.
t pixel cu
˙’
a n´o.
C´ac pixel d¯u
.
o
.
.
c v˜e tu
.
o
.
ng ´u
.
ng c´ac h`ınh tr`on m`au d¯en v`a c´ac pixel khˆong d¯u
.
o
.
.
c v˜e tu
.
o
.
ng ´u

˙’
i vˆa
.
y biˆe
˙’
u diˆe
˜
n bˇa
`
ng k´y hiˆe
.
u cu
˙’
a ch´ung ta l`a
mˆo
.
t ph´ong d¯a
.
i m´u
.
c d¯ˆo
.
r`o
.
i ra
.
c cu
˙’
a c´ac pixel.


.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
✐ ✐ ✐ ✐ ✐
✐ ✐ ✐ ✐ ✐
✐ ✐ ✐ ✐ ✐
✐ ✐ ✐ ✐ ✐
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

i c´ac h`ınh tr`on d¯en.
V`ı c´ac nguyˆen so
.
trong hˆe
.
thˆo
´
ng ch´ung ta x´ac d¯i
.
nh trˆen lu
.
´o
.
i d¯iˆe
`
u khiˆe
˙’
n nguyˆen nˆen
c´ac to
.
a d¯ˆo
.
d¯ˆa
`
u cuˆo
´
i cu
˙’
a d¯oa
.

.
c´ac d¯iˆe
˙’
m d¯ˆa
`
u cuˆo
´
i cu
˙’
a d¯oa
.
n thˇa
˙’
ng c´o thˆe
˙’
khˆong nguyˆen. (Ch´ung ta s˜e tha
˙’
o luˆa
.
n c´ac giao d¯iˆe
˙’
m khˆong nguyˆen trong Phˆa
`
n 1.1.3). Gia
˙’
10
su
.
˙’
d¯oa

.
n n˜u
.
a
tru
.
`o
.
ng ho
.
.
p c´ac d¯oa
.
n thˇa
˙’
ng ngang, d¯´u
.
ng hoˇa
.
c c´o hˆe
.
sˆo
´
g´oc ±1 l`a tˆa
`
m thu
.
`o
.
ng v`ı ch´ung chı

o
.
ng
tr`ınh d¯u
.
`o
.
ng thˇa
˙’
ng AB c´o da
.
ng y = mx +t, trong d¯´o hˆe
.
sˆo
´
g´oc m = dy/dx v`a t = y
A
−mx
A
.
C´ach d¯o
.
n gia
˙’
n nhˆa
´
t d¯ˆe
˙’
v˜e d¯oa
.

i
t´ınh y
i
= mx
i
+ t v`a
sau d¯´o v˜e pixel ta
.
i (x
i
, y
i
+ 0.5)
1
.
Theo c´ach n`ay ta cho
.
n pixel tˆo
´
t nhˆa
´
t, t´u
.
c l`a pixel m`a khoa
˙’
ng c´ach d¯ˆe
´
n d¯u
.
`o

`
n t´ınh mˆo
.
t ph´ep nhˆan,
mˆo
.
t ph´ep cˆo
.
ng v`a mˆo
.
t ph´ep to´an l`am tr`on. Ta c´o thˆe
˙’
khu
.
˙’
ph´ep nhˆan bˇa
`
ng c´ach ch´u ´y rˇa
`
ng
y
i+1
= mx
i+1
+ t
= m(x
i
+ ∆x) + t
= y
i

m (x
i
, y
i
) trˆen d¯oa
.
n
thˇa
˙’
ng ta biˆe
´
t rˇa
`
ng nˆe
´
u x
i+1
= x
i
+ 1 th`ı y
i+1
= y
i
+ m; t´u
.
c l`a, c´ac gi´a tri
.
x v`a y d¯u
.
o

.
c hiˆe
.
n c´ac ph´ep to´an sˆo
´
gia du
.
.
a trˆen bu
.
´o
.
c tru
.
´o
.
c.
Kho
.
˙’
i ta
.
o ta g´an (x
0
, y
0
) l`a to
.
a d¯ˆo
.

n mˆo
.
t d¯o
.
n vi
.
. Do d¯´o
cˆa
`
n ho´an d¯ˆo
˙’
i vai tr`o cu
˙’
a x v`a y bˇa
`
ng c´ach g´an bu
.
´o
.
c tˇang mˆo
.
t d¯o
.
n vi
.
cho y v`a tˇang x mˆo
.
t
lu
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
(x
i
, y
i
)
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

(x
i
+ 1, y
i
+ m)
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
D
-
u
.
`o
.
ng thˇa
˙’

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

˙’
m A v`a B c´o hˆe
.
sˆo
´
g´oc m =
3
7
∈ (0, 1).
´
Ap du
.
ng thuˆa
.
t to´an sˆo
´
gia ta d¯u
.
o
.
.
c d˜ay c´ac d¯iˆe
˙’
m v˜e tˆo
´
t nhˆa
´
t nhu
.
trong

2
5 7
15
7
2
6 8
18
7
3
7 9
21
7
3
Thu
˙’
tu
.
c Line() du
.
´o
.
i d¯ˆay minh ho
.
a thuˆa
.
t to´an v˜e d¯oa
.
n thˇa
˙’
ng t`u

˙’
x´et tru
.
`o
.
ng ho
.
.
p
−1 ≤ m ≤ 1 v`ı c´ac tru
.
`o
.
ng ho
.
.
p kh´ac c´o thˆe
˙’
thu
.
.
c hiˆe
.
n do t´ınh d¯ˆo
´
i x´u
.
ng. Ho
.
n n˜u

mˆo
.
t g´oc ±45
0
. Ch´u ´y rˇa
`
ng, trong ngˆon ng˜u
.
C, (int)y bˇa
`
ng y + 0.5.
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 <= x_B; x ++)
{
putpixel(x, (int)(y), Value);
y += m;
}
}
1.1.2 Thuˆa
.
t to´an d¯iˆe

ng c´ac ph´ep to´an trˆen sˆo
´
nguyˆen do d¯´o tr´anh go
.
i h`am l`am tr`on v`a cho
ph´ep x´ac d¯i
.
nh (x
i+1
, y
i+1
) theo sˆo
´
gia du
.
.
a trˆen nh˜u
.
ng gi´a tri
.
o
.
˙’
bu
.
´o
.
c tru
.
´o

.
thu
.
.
c. Ho
.
n n˜u
.
a, phu
.
o
.
ng
ph´ap cu
˙’
a Bresenham c´o thˆe
˙’
d¯u
.
o
.
.
c ´ap du
.
ng t´ınh to´an trˆen sˆo
´
nguyˆen v˜e d¯u
.
`o
.

t to´an d¯iˆe
˙’
m gi˜u
.
a, d¯u
.
o
.
.
c cˆong bˆo
´
lˆa
`
n d¯ˆa
`
u tiˆen bo
.
˙’
i Pitteway [16], [17] v`a d¯u
.
o
.
.
c
ca
˙’
i tiˆe
´
n bo
.

u nguyˆen, cˆong th´u
.
c d¯iˆe
˙’
m gi˜u
.
a suy ra cˆong th´u
.
c
cu
˙’
a Bresenham v`a do d¯´o sinh ra c`ung d˜ay c´ac pixel.
Khˆong mˆa
´
t t´ınh tˆo
˙’
ng qu´at, gia
˙’
su
.
˙’
hˆe
.
sˆo
´
g´oc m cu
˙’
a d¯u
.
`o

y d¯ˆo
´
i x´u
.
ng mˆo
.
t c´ach th´ıch ho
.
.
p qua
c´ac tru
.
c to
.
a d¯ˆo
.
). Ta c˜ung k´y hiˆe
.
u d¯iˆe
˙’
m xuˆa
´
t ph´at l`a (x
A
, y
A
) v`a d¯iˆe
˙’
m kˆe
´

d¯i
.
nh bo
.
˙’
i
y =
dy
dx
x + t;
13
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.


o
.
ng
f(x, y) := ax + by + c = 0,
trong d¯´o a = dy, b = − dx, v`a c = b × dx. K´y hiˆe
.
u c´ac nu
.
˙’
a mˇa
.
t phˇa
˙’
ng ngo`ai v`a nu
.
˙’
a mˇa
.
t
phˇa
˙’
ng trong x´ac d¯i
.
nh bo
.
˙’
i l tu
.
o
.

a l`a xˆay du
.
.
ng mˆo
.
t d˜ay c´ac d¯iˆe
˙’
m v˜e “tˆo
´
t nhˆa
´
t” (x
i
, y
i
)
bˇa
´
t d¯ˆa
`
u t`u
.
d¯iˆe
˙’
m (x
0
, y
0
) = (x
A

.
i d¯u
.
`o
.
ng thˇa
˙’
ng thu
.
.
c tˆe
´
(da
.
ng liˆen tu
.
c) nhˆa
´
t. Theo gia
˙’
thiˆe
´
t, 0 < m < 1, nˆen khi
x tˇang mˆo
.
t lu
.
o
.
.

, y
i
) th`ı o
.
˙’
bu
.
´o
.
c th´u
.
i + 1
ta s˜e cho
.
n d¯iˆe
˙’
m v˜e (x
i+1
, y
i+1
), trong d¯´o x
i+1
= x
i
+ 1 v`a y
i+1
= y
i
hoˇa
.

m cu
˙’
a hai d¯u
.
`o
.
ng thˇa
˙’
ng l v`a
x = x
i
+ 1. Theo Bresenham, dˆa
´
u cu
˙’
a biˆe
˙’
u th´u
.
c x´ac d¯i
.
nh bo
.
˙’
i hiˆe
.
u gi˜u
.
a hai khoa
˙’

m gi ˜u
.
a M v`a c´ac nu
.
˙’
a mˇa
.
t phˇa
˙’
ng x´ac d¯i
.
nh b o
.
˙’
i d¯u
.
`o
.
ng thˇa
˙’
ng l. Dˆe
˜
d`ang chı
˙’
ra rˇa
`
ng, nˆe
´
u M ∈ (l
+

˙’
d¯i ngang qua M; hoˇa
.
c ca
˙’
hai pixel nˇa
`
m vˆe
`
c`ung
mˆo
.
t nu
.
˙’
a mˇa
.
t phˇa
˙’
ng (l
+
) (hoˇa
.
c (l
−
)) nhu
.
ng trong bˆa
´
t c´u

˙’
ng c´ach gi˜u
.
a pixel d¯u
.
o
.
.
c cho
.
n v`a d¯u
.
`o
.
ng thˇa
˙’
ng
thu
.
.
c tˆe
´
l-luˆon luˆon nho
˙’
ho
.
n hoˇa
.
c bˇa
`

u cu
˙’
a n´o. Do d¯´o ta d¯i
.
nh ngh˜ıa biˆe
´
n quyˆe
´
t d¯i
.
nh
d
i
:= f(x
i
+ 1, y
i
+
1
2
)
= a(x
i
+ 1) + b(y
i
+
1
2
) + c.
Khi d¯´o

´
p ta cˆa
`
n x´ac d¯i
.
nh to
.
a d¯ˆo
.
d¯iˆe
˙’
m gi˜u
.
a M v`a do d¯´o biˆe
´
n quyˆe
´
t d¯i
.
nh d
i+1
o
.
˙’
bu
.
´o
.
c i + 1;
d˜ı nhiˆen d¯iˆe

i. Do d¯´o
d
i+1
= f(x
i
+ 2, y
i
+
1
2
) = a(x
i
+ 2) + b(y
i
+
1
2
) + c.
Nhu
.
ng
d
i
= a(x
i
+ 1) + b(y
i
+
1
2

´
n quyˆe
´
t d¯i
.
nh o
.
˙’
bu
.
´o
.
c kˆe
´
tiˆe
´
p t`u
.
biˆe
´
n quyˆe
´
t d¯i
.
nh o
.
˙’
bu
.
´o

˙’
m M c`ung tˇang mˆo
.
t d¯o
.
n vi
.
, nˆen
d
i+1
= f(x
i
+ 2, y
i
+
3
2
) = a(x
i
+ 2) + b(y
i
+
3
2
) + c.
V`a do d¯´o
d
i+1
= d
i

n (x
0
, y
0
) = (x
A
, y
A
) nˆen c´o thˆe
˙’
t´ınh tru
.
.
c tiˆe
´
p gi´a tri
.
kho
.
˙’
i
ta
.
o d
0
. Thˆa
.
t vˆa
.
y, d¯iˆe

2
) + c
= ax
0
+ by
0
+ c + a + b/2
= f(x
0
, y
0
) + a + b/2.
15
Nhu
.
ng (x
0
, y
0
) thuˆo
.
c d¯u
.
`o
.
ng thˇa
˙’
ng l nˆen f(x
0
, y

n pixel th´u
.
hai, th´u
.
ba, v.v. D
-
ˆe
˙’
khu
.
˙’
mˆa
˜
u sˆo
´
trong d
0
ta d¯i
.
nh ngh˜ıa la
.
i h`am f bˇa
`
ng c´ach nhˆan n´o cho 2; t´u
.
c l`a
f(x, y) = 2(ax + by + c). N´oi c´ach kh´ac, nhˆan 2 cho c´ac hˇa
`
ng sˆo
´

˙’
ng qu´at ho´a thuˆa
.
t to´an d¯iˆe
˙’
m gi˜u
.
a v˜e d¯oa
.
n thˇa
˙’
ng AB (trong tru
.
`o
.
ng ho
.
.
p x
A
< x
B
v`a 0 < m < 1) nhu
.
sau:
1. [Kho
.
˙’
i ta
.

su
.
˙’
o
.
˙’
bu
.
´o
.
c th´u
.
i ta c´o d¯iˆe
˙’
m v˜e tˆo
´
t nhˆa
´
t (x
i
, y
i
) v`a biˆe
´
n quyˆe
´
t d¯i
.
nh d
i

ng; ngu
.
o
.
.
c la
.
i, d¯ˇa
.
t
x
i+1
= x
i
+ 1;
y
i+1
=

y
i
nˆe
´
u d
i
≤ 0,
y
i
+ 1 nˆe
´

.
.
c la
.
i.
5. Thay i bˇa
`
ng (i + 1) v`a lˇa
.
p la
.
i Bu
.
´o
.
c 3.
V´ı du
.
1.1.2 Gia
˙’
su
.
˙’
A(2, 0), B(9, 3). Khi d¯´o d¯u
.
`o
.
ng thˇa
˙’
ng qua hai d¯iˆe

= 2dy = 6,
∆
D
= 2(dy − dx) = −8.
16
´
Ap du
.
ng thuˆa
.
t to´an d¯iˆe
˙’
m gi˜u
.
a ta c´o d˜ay c´ac d¯iˆe
˙’
m v˜e tˆo
´
t nhˆa
´
t nhu
.
trong ba
˙’
ng du
.
´o
.
i:
i x

du
.
ng phu
.
o
.
ng ph´ap sˆo
´
gia trong
V´ı du
.
1.1.1.
Ch´u ´y rˇa
`
ng, ph´ep t´ınh cˆa
`
n thiˆe
´
t d¯ˆo
´
i v´o
.
i d
i+1
trong mˆo
˜
i bu
.
´o
.

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 <= x_B; x++)
{
putpixel(x, y, Value);
if (d <= 0) d += DeltaR;
else
{
d += DeltaD;
17
y++;
}
}
}
1.1.3 Mˆo
.
t sˆo
´
vˆa
´
n d¯ˆe
`
liˆen quan d¯ˆe
´
n thuˆa
.

t d¯oa
.
n thˇa
˙’
ng
d¯u
.
o
.
.
c v˜e t`u
.
A d¯ˆe
´
n B ch´u
.
a c`ung tˆa
.
p c´ac pixel nhu
.
d¯oa
.
n thˇa
˙’
ng d¯u
.
o
.
.
c v˜e t`u

.
sai kh´ac
chı
˙’
c´o thˆe
˙’
xa
˙’
y ra ta
.
i nh ˜u
.
ng d¯iˆe
˙’
m v˜e m`a d¯u
.
`o
.
ng thˇa
˙’
ng d¯i qua d¯iˆe
˙’
m gi ˜u
.
a v`a biˆe
´
n quyˆe
´
t d¯i
.

˙’
m v˜e R, nhu
.
ng cho
.
n lu
.
.
a n`ay s˜e
sai lˆe
.
ch mˆo
.
t d¯o
.
n vi
.
theo th`anh phˆa
`
n y v´o
.
i pixel d¯u
.
o
.
.
c cho
.
n khi d¯i t`u
.

i v´o
.
i c´ac d¯oa
.
n thˇa
˙’
ng c´o hˆe
.
sˆo
´
g´oc bˆa
´
t k`y.
Phu
.
o
.
ng ph´ap ho´an d¯ˆo
˙’
i c´ac d¯iˆe
˙’
m d¯ˆa
`
u cuˆo
´
i cu
˙’
a d¯oa
.
n thˇa

˜
u thu
.
`o
.
ng “neo” nh˜u
.
ng dˆa
´
u hiˆe
.
u ta
.
i d¯iˆe
˙’
m xuˆa
´
t ph´at, c´o thˆe
˙’
l`a d¯iˆe
˙’
m
du
.
´o
.
i bˆen tr´ai, khˆong phu
.
thuˆo
.

.
i d¯iˆe
˙’
m xuˆa
´
t ph´at m`a khˆong tu
.
.
d¯ˆo
.
ng d¯ˆo
˙’
i
th`anh d¯iˆe
˙’
m du
.
´o
.
i bˆen tr´ai. Ngo`ai ra, nˆe
´
u thuˆa
.
t to´an luˆon luˆon d¯ˇa
.
t la
.
i c´ac d¯iˆe
˙’
m d¯ˆa

sang tr´ai v´o
.
i d¯oa
.
n thˇa
˙’
ng BA; d¯iˆe
`
u n`ay ta
.
o ra su
.
.
gi´an d¯oa
.
n trong qu´a tr`ınh v˜e, chˇa
˙’
ng ha
.
n
d¯a gi´ac, ta
.
i nh˜u
.
ng d¯ı
˙’
nh chung.
D
-
iˆe

.
n thˇa
˙’
ng sau khi d¯u
.
o
.
.
c cˇa
´
t bo
.
˙’
i mˆo
.
t trong c´ac thuˆa
.
t to´an
trong Phˆa
`
n 3.3. H`ınh 1.4(a) minh ho
.
a d¯oa
.
n thˇa
˙’
ng d¯u
.
o
.

nhu
.
ng tung d¯ˆo
.
y thu
.
.
c. Pixel (x
min
, mx
min
+ t + 0.5) trˆen ca
.
nh x = x
min
ch´ınh l`a pixel
d¯u
.
o
.
.
c v˜e ta
.
i ho`anh d¯ˆo
.
x
min
cu
˙’
a d¯oa

´
p ch´ung ta cˆa
`
n kho
.
˙’
i ta
.
o biˆe
´
n quyˆe
´
t d¯i
.
nh ta
.
i d¯iˆe
˙’
m gi˜u
.
a d¯oa
.
n
RD trong cˆo
.
t kˆe
´
bˆen. Cˆa
`
n ch´u ´y rˇa

˙’
a viˆe
.
c cho
.
n pixel R khi d = 0.
18
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.

x = x
min
y = y
min
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
(a)
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
② ② ② ②② ② ② ②
✐ ✐ ✐ ✐ ② ② ② ② ✐ ✐ ✐
② ② ② ②

y = y
min
−
1
2
•
I
D C
(b)
H`ınh 1.4: D
-
iˆe
˙’
m xuˆa
´
t ph´at nˇa
`
m trˆen biˆen h`ınh ch˜u
.
nhˆa

.
c hiˆe
.
n v˜e d¯oa
.
n thˇa
˙’
ng d¯u
.
o
.
.
c cˇa
´
t t`u
.
(x
min
, mx
min
+ t + 0.5) d¯ˆe
´
n (x
B
, y
B
) theo thuˆa
.
t to´an d¯iˆe
˙’

.
n khi d¯u
.
`o
.
ng thˇa
˙’
ng AB giao v´o
.
i d¯u
.
`o
.
ng thˇa
˙’
ng nˇa
`
m ngang nhu
.
trong H`ınh 1.4(b). Khi hˆe
.
sˆo
´
g´oc m rˆa
´
t nho
˙’
, c´o nhiˆe
`
u pixel nˇa

ng do qu´a tr`ınh t´ınh to´an giao d¯iˆe
˙’
m v´o
.
i d`ong qu´et y = y
min
v`a sau d¯´o
l`am tr`on ho`anh d¯ˆo
.
x ta d¯u
.
o
.
.
c pixel C khˆong pha
˙’
i pixel bˆen tr´ai nhˆa
´
t D trˆen d`ong n`ay. Du
.
.
a
trˆen h`ınh v˜e, ta thˆa
´
y rˇa
`
ng pixel bˆen tr´ai nhˆa
´
t D l`a pixel trˆen bˆen pha
˙’

I
, y
min
).
Cuˆo
´
i c`ung, thuˆa
.
t to´an d¯iˆe
˙’
m gi˜u
.
a c˜ung thu
.
.
c hiˆe
.
n tˆo
´
t trong tru
.
`o
.
ng ho
.
.
p c´ac d¯iˆe
˙’
m d¯ˆa
`

ng d¯ˆo
.
s´ang cu
˙’
a d¯oa
.
n thˇa
˙’
ng theo hˆe
.
sˆo
´
g´oc. X´et hai d¯oa
.
n thˇa
˙’
ng trong
H`ınh 1.5. D
-
oa
.
n thˇa
˙’
ng l
2
c´o hˆe
.
sˆo
´
g´oc 1 v`a do d¯´o c´o d¯ˆo

ng d¯ˆo
.
cu
˙’
a mˆo
˜
i pixel l`a I th`ı cu
.
`o
.
ng
d¯ˆo
.
trˆen mˆo
.
t d¯o
.
n vi
.
d¯ˆo
.
d`ai cu
˙’
a d¯oa
.
n thˇa
˙’
ng l
1
l`a I, trong khi cu

´
t, nhu
.
ng trˆen hˆe
.
thˆo
´
ng n-bit trˆen pixel ch´ung ta c´o thˆe
˙’
ca
˙’
i thiˆe
.
n d¯u
.
o
.
.
c t`ınh tra
.
ng n`ay
bˇa
`
ng c´ach d¯ˇa
.
t cu
.
`o
.
ng d¯ˆo

t h`ınh ch˜u
.
nhˆa
.
t c´o d¯ˆo
.
rˆo
.
ng he
.
p v`a t´ınh to´an th´ıch
ho
.
.
p c´ac cu
.
`o
.
ng d¯ˆo
.
v´o
.
i nhiˆe
`
u pixel trˆen mˆo
˜
i cˆo
.
t nˇa
`

.
ng tu`y ´y.
Ph´ac tha
˙’
o c´ac nguyˆen so
.
x´ac d¯i
.
nh bo
.
˙’
i c´ac d¯oa
.
n thˇa
˙’
ng. V´o
.
i c´ach v˜e c´ac d¯oa
.
n thˇa
˙’
ng,
ch´ung ta cˆa
`
n v˜e c´ac nguyˆen so
.
d¯u
.
o
.

ng c´ach xem n´o nhu
.
c´ac d¯oa
.
n thˇa
˙’
ng kˆe
`
nhau. C´ac h`ınh ch˜u
.
nhˆa
.
t v`a d¯a gi´ac l`a nh˜u
.
ng nguyˆen so
.
v`ung v`a c´o thˆe
˙’
v˜e c´ac ca
.
nh liˆen tiˆe
´
p nhu
.
ng d¯iˆe
`
u n`ay
dˆa
˜
n d¯ˆe

n`ay. Ch´u ´y rˇa
`
ng cˆa
`
n v˜e c´ac d¯ı
˙’
nh chung cu
˙’
a d¯u
.
`o
.
ng gˆa
´
p
kh´uc mˆo
.
t lˆa
`
n do viˆe
.
c v˜e hai lˆa
`
n c´o thˆe
˙’
l`am thay d¯ˆo
˙’
i m`au hoˇa
.
c d¯ˇa

.
n thˇa
˙’
ng nˇa
`
m gˆa
`
n nhau hoˇa
.
c cˇa
´
t nhau.
20

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
②
②
②
②
②
②
②

ng d¯ˆo
.
cu
˙’
a c´ac d¯u
.
`o
.
ng thˇa
˙’
ng theo hˆe
.
sˆo
´
g´oc.
1.1.4 C´ac thuˆo
.
c t´ınh cu
˙’
a d¯oa
.
n thˇa
˙’
ng
Thuˆo
.
c t´ınh mˆa
˜
u tˆo d¯oa
.

˙’
kiˆe
˙’
m tra c´o d¯ˇa
.
t d¯iˆe
˙’
m v˜e hay khˆong, chı
˙’
d¯ˇa
.
t khi d¯iˆe
`
u kiˆe
.
n
d¯´ung (gi´a tri
.
1). Ch´ung ta lu
.
u tr˜u
.
mˆa
˜
u v˜e nhu
.
mˆo
.
t chuˆo
˜

.
i sau khi v˜e 16 pixel. Ch´ung ta thay d`ong lˆe
.
nh khˆong d¯iˆe
`
u kiˆe
.
n
putpixel() trong thuˆa
.
t to´an v˜e d¯oa
.
n thˇa
˙’
ng d¯ˆe
˙’
xu
.
˙’
l´y tru
.
`o
.
ng ho
.
.
p n`ay; chˇa
˙’
ng ha
.

.
tu
.
o
.
ng ´u
.
ng mˆo
.
t lˆa
`
n lˇa
.
p v`a khˆong
tu
.
o
.
ng ´u
.
ng d¯ˆo
.
d`ai d¯o
.
n vi
.
do
.
c theo d¯oa
.

n thˇa
˙’
ng ngang
hay d¯´u
.
ng. D
-
iˆe
`
u n`ay l`a khˆong chˆa
´
p nhˆa
.
n d¯u
.
o
.
.
c v´o
.
i nh˜u
.
ng ´u
.
ng du
.
ng mang t´ınh ch´ınh x´ac
cao, chˇa
˙’
ng ha

a n´o. D
-
ˆo
.
rˆo
.
ng cu
˙’
a d¯oa
.
n thˇa
˙’
ng d¯u
.
o
.
.
c
xem nhu
.
mˆo
.
t d˜ay c´ac h`ınh ch˜u
.
nhˆa
.
t d¯ˇa
.
c v`a trong suˆo
´

c hiˆe
.
n tˆo
m`au trˆen t`u
.
ng h`ınh ch˜u
.
nhˆa
.
t mˆo
.
t; v´o
.
i c´ac d¯oa
.
n thˇa
˙’
ng ngang hoˇa
.
c d¯´u
.
ng, ta c´o thˆe
˙’
d`ung
lˆe
.
nh sao ch´ep c´ac h`ınh ch˜u
.
nhˆa
.

.
ng biˆen. Kiˆe
˙’
u d¯oa
.
n thˇa
˙’
ng thu
.
`o
.
ng d¯u
.
o
.
.
c su
.
˙’
du
.
ng d¯ˆe
˙’
x´ac d¯i
.
nh c´ac h`ınh ch˜u
.
nhˆa
.
t tu

-
u
.
`o
.
ng tr`on
X´et d¯u
.
`o
.
ng tr`on f(x, y) := x
2
+ y
2
−R
2
= 0. C´o mˆo
.
t v`ai c´ach d¯o
.
n gia
˙’
n v˜e d¯u
.
`o
.
ng tr`on nhu
.
ng
khˆong hiˆe

(c´ac cung kh´ac d¯u
.
o
.
.
c v˜e do t´ınh d¯ˆo
´
i x´u
.
ng) ta c´o thˆe
˙’
tˇang x t`u
.
0 d¯ˆe
´
n R (mˆo
˜
i bu
.
´o
.
c mˆo
.
t d¯o
.
n
vi
.
) v`a gia
˙’

ng khi gi´a tri
.
x gˆa
`
n v´o
.
i R v`ı tiˆe
´
p tuyˆe
´
n v´o
.
i d¯u
.
`o
.
ng tr`on
ta
.
i nh˜u
.
ng d¯iˆe
˙’
m tu
.
o
.
ng ´u
.
ng tiˆe

.
ng lˆo
˜
hˆo
˙’
ng l`a v˜e c´ac d¯iˆe
˙’
m (R cos θ, R sin θ)
v´o
.
i θ thay d¯ˆo
˙’
i t`u
.
0 d¯ˆe
´
n 90
0
.
1.2.1 D
-
ˆo
´
i x´u
.
ng t´am d¯iˆe
˙’
m
Ch´ung ta c´o thˆe
˙’

i gˆo
´
c v`ı nˆe
´
u khˆong ta thu
.
.
c hiˆe
.
n ph´ep ti
.
nh
tiˆe
´
n t`u
.
tˆam vˆe
`
gˆo
´
c to
.
a d¯ˆo
.
. Nˆe
´
u d¯iˆe
˙’
m (x, y) nˇa
`

.
ng tr`on. V´o
.
i d¯u
.
`o
.
ng tr`on tˆam
ta
.
i gˆo
´
c, t´am d¯iˆe
˙’
m d¯ˆo
´
i x´u
.
ng c´o thˆe
˙’
d¯u
.
o
.
.
c hiˆe
˙’
n thi
.
bˇa

`
n ch´u ´y rˇa
`
ng khˆong nˆen go
.
i thu
˙’
tu
.
c CirclePoints() khi x = y do c´o bˆo
´
n pixel d¯u
.
o
.
.
c
v˜e hai lˆa
`
n; ta chı
˙’
cˆa
`
n thay d¯ˆo
˙’
i d¯oa
.
n m˜a xu
.
˙’

ho
.
n c´ach d¯u
.
a ra o
.
˙’
trˆen. Ch´ung ta nˆeu thuˆa
.
t to´an tu
.
o
.
ng tu
.
.
, su
.
˙’
du
.
ng tiˆeu chuˆa
˙’
n d¯iˆe
˙’
m gi˜u
.
a, m`a trong tru
.
`o

`
n x´et cung mˆo
.
t phˆa
`
n t´am d¯u
.
`o
.
ng tr`on:
(C
1
) := {(x, y) ∈ R
2
| x
2
+ y
2
= R
2
, 0 ≤ y < x}
v`a su
.
˙’
du
.
ng thu
˙’
tu
.

y
x
. Suy ra
−1 <
dx
dy
≤ 0 v´o
.
i mo
.
i (x, y) ∈ (C
1
). Do d¯´o, khi y tˇang mˆo
.
t d¯o
.
n vi
.
th`ı x gia
˙’
m khˆong qu´a
mˆo
.
t d¯o
.
n vi
.
. V`ı vˆa
.
y, gia

),
th`ı bu
.
´o
.
c kˆe
´
tiˆe
´
p cˆa
`
n cho
.
n mˆo
.
t trong hai pixel T := (x
i
, y
i
+ 1) hoˇa
.
c D := (x
i
− 1, y
i
+ 1)
(xem H`ınh 1.6). Tu
.
o
.

ng tr`on ho
.
n ta x´et h`am lˆa
´
y gi´a tri
.
ta
.
i d¯iˆe
˙’
m gi ˜u
.
a M = (x
i
−
1
2
, y
i
+ 1) cu
˙’
a
hai d¯iˆe
˙’
m v˜e n`ay. Dˆe
˜
d`ang ch´u
.
ng minh rˇa
`

.
`o
.
ng tr`on (tu
.
o
.
ng d¯u
.
o
.
ng
f(M) > 0) th`ı D gˆa
`
n d¯u
.
`o
.
ng tr`on ho
.
n. Tru
.
`o
.
ng ho
.
.
p M nˇa
`
m trˆen d¯u

i
−
1
2
)
2
+ (y
i
+ 1)
2
− R
2
.
Nˆe
´
u d
i
< 0 th`ı cho
.
n T v`a d¯iˆe
˙’
m gi˜u
.
a kˆe
´
tiˆe
´
p c´o tung d¯ˆo
.
tˇang mˆo

i+1
= d
i
+ (2y
i
+ 3); suy ra bu
.
´o
.
c tˇang ∆
T
:= 2y
i
+ 3.
23
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
D
✇
C
✇
T
✇
H`ınh 1.6: Lu
.
´o
.
i pixel trong thuˆa
.
t to´an d¯iˆe
˙’
m gi˜u
.
a v˜e d¯u
.
`o
.
ng tr`on.
Nˆe
´
u d

d
i+1
= f(x
i
−
3
2
, y
i
+ 2) = (x
i
−
3
2
)
2
+ (y
i
+ 2)
2
− R
2
.
Suy ra d
i+1
= d
i
+ 2y
i
− 2x

.
´o
.
c tˇang ∆
R
v`a ∆
D
l`a c´ac hˇa
`
ng sˆo
´
;
tuy nhiˆen, trong tru
.
`o
.
ng ho
.
.
p d¯u
.
`o
.
ng cong bˆa
.
c hai, ∆
T
v`a ∆
D
l`a c´ac h`am phu

.
´o
.
c
lˇa
.
p du
.
.
a v`ao c´ac gi´a tri
.
x v`a y cu
˙’
a pixel d¯u
.
o
.
.
c cho
.
n trong bu
.
´o
.
c lˇa
.
p tru
.
´o
.

.
˙’
i ta
.
o
ban d¯ˆa
`
u c´o to
.
a d¯ˆo
.
(R, 0) nˆen d¯iˆe
˙’
m gi˜u
.
a c´o to
.
a d¯ˆo
.
(R −
1
2
, 1) v`a do d¯´o d
0
= f(R −
1
2
, 1) =
(R −
1

1. [Kho
.
˙’
i ta
.
o] D
-
ˇa
.
t x
0
= R , y
0
= 0, d
0
= 5/4 − R.
2. Gia
˙’
su
.
˙’
o
.
˙’
bu
.
´o
.
c th´u
.

a trˆen (x
i
, y
i
).
24