Đồ họa máy tính
Tài liệu Đồ họa máy tính: Đồ họa máy tính D- O`ˆ HO. A MA´Y TI´NH I Pha.m Tieˆ´n So .n D- a` La.t, 2005 2 Mu.c lu. c Lo`.i no´i d¯a`ˆu 7 1 Ca´c thuaˆ.t toa´n ve˜ d¯u .`o.ng cong treˆn thieˆ´t bi. raster 9 1.1 D- oa.n tha˙ˇ’ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.1.1 Thuaˆ. t toa´n soˆ´ gia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.1.2 Thuaˆ. t toa´n d¯ieˆ˙’m giu˜ .a . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.1.3 Moˆ.t soˆ´ vaˆ´n d¯e`ˆ lieˆn quan d¯eˆ´n thuaˆ. t toa´n ve˜ d¯oa.n tha˙ˇ’ng . . . . . . . . 18 1.1.4 Ca´c thuoˆ.c t´ınh cu˙’a d¯oa.n tha˙ˇ’ng . . . . . . . . . . . . . . . . . . . . . 21 1.2 D- u.`o.ng tro`n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.2.1 D- oˆ´i xu´.ng ta´m d¯ieˆ˙’m . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.2.2 Thuaˆ. t toa´n d¯ieˆ˙’m giu˜ .a ve˜ d¯u.`o.ng tro`n . . . . . . . . . . . . . . . . . . 23 1.3 D- u.`o.ng cong ellipse . . . . . . ....
Bạn đang xem trước 20 trang mẫu tài liệu Đồ họa máy tính, để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
Đồ họa máy tính
D- O`ˆ HO. A MA´Y TI´NH I
Pha.m Tieˆ´n So
.n
D- a` La.t, 2005
2
Mu.c lu. c
Lo`.i no´i d¯a`ˆu 7
1 Ca´c thuaˆ.t toa´n ve˜ d¯u
.`o.ng cong treˆn thieˆ´t bi. raster 9
1.1 D- oa.n tha˙ˇ’ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.1.1 Thuaˆ. t toa´n soˆ´ gia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.1.2 Thuaˆ. t toa´n d¯ieˆ˙’m giu˜
.a . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.1.3 Moˆ.t soˆ´ vaˆ´n d¯e`ˆ lieˆn quan d¯eˆ´n thuaˆ. t toa´n ve˜ d¯oa.n tha˙ˇ’ng . . . . . . . . 18
1.1.4 Ca´c thuoˆ.c t´ınh cu˙’a d¯oa.n tha˙ˇ’ng . . . . . . . . . . . . . . . . . . . . . 21
1.2 D- u.`o.ng tro`n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.2.1 D- oˆ´i xu´.ng ta´m d¯ieˆ˙’m . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.2.2 Thuaˆ. t toa´n d¯ieˆ˙’m giu˜
.a ve˜ d¯u.`o.ng tro`n . . . . . . . . . . . . . . . . . . 23
1.3 D- u.`o.ng cong ellipse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.3.1 Ellipse co´ da.ng ch´ınh taˇ´c . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.3.2 Ellipse trong tru.`o.ng ho.
.p toˆ˙’ng qua´t . . . . . . . . . . . . . . . . . . . 34
2 Hı`nh ho.c cu˙’a ca´c d¯u
.`o.ng cong va` maˇ.t cong 47
2.1 Mo.’˙ d¯a`ˆu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3
2.2 D- u.`o.ng cong Bezier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.2.1 Thuaˆ. t toa´n de Casteljau . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.2.2 D- a thu´.c Bernstein va` d¯u.`o.ng cong Bezier . . . . . . . . . . . . . . . . 52
2.3 Ca´c t´ınh chaˆ´t cu˙’a d¯u.`o.ng cong Bezier . . . . . . . . . . . . . . . . . . . . . . 55
2.3.1 D- ie`ˆu khieˆ˙’n d¯i.a phu
.o.ng . . . . . . . . . . . . . . . . . . . . . . . . . . 59
2.4 D- a thu´.c tu`.ng khu´c va` ca´c ha`m spline . . . . . . . . . . . . . . . . . . . . . . 60
2.4.1 Su.’˙ du.ng ca´c ha`m spline nhu
. ca´c ha`m troˆ.n . . . . . . . . . . . . . . . 63
2.4.2 Xaˆy du.
.ng ca´c ha`m troˆ.n . . . . . . . . . . . . . . . . . . . . . . . . . 65
2.4.3 D- u.`o.ng cong spline va` ca´c ha`m co. so.’˙ . . . . . . . . . . . . . . . . . . 66
2.4.4 Ca´c ha`m B-spline co. so.’˙ . . . . . . . . . . . . . . . . . . . . . . . . . 66
2.4.5 Su.’˙ du.ng ca´c knot boˆ. i . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
2.4.6 Vector knot chuaˆ˙’n . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
2.5 Ca´c t´ınh chaˆ´t cu˙’a d¯u.`o.ng cong B-spline . . . . . . . . . . . . . . . . . . . . . 75
2.6 Noˆ. i suy ca´c d¯ieˆ˙’m d¯ie`ˆu khieˆ˙’n ba`ˇng d¯u
.`o.ng cong B-spline . . . . . . . . . . . . 77
2.7 Thieˆ´t keˆ´ ca´c maˇ.t Bezier va` B-spline . . . . . . . . . . . . . . . . . . . . . . . 80
2.7.1 Patch Bezier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
2.7.2 Da´n ca´c patch Bezier . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
2.7.3 Patch spline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
3 Giao cu˙’a ca´c d¯oˆ´i tu.o.
.ng 83
3.1 Mo.’˙ d¯a`ˆu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
3.2 Giao cu˙’a hai d¯oa.n tha˙ˇ’ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
3.2.1 Phaˆn t´ıch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
4
3.2.2 Thuaˆ. t toa´n xa´c d¯i.nh giao hai d¯oa.n tha˙ˇ’ng . . . . . . . . . . . . . . . . 86
3.3 D- oa.n tha˙ˇ’ng va` h`ınh chu˜
. nhaˆ. t . . . . . . . . . . . . . . . . . . . . . . . . . . 87
3.3.1 T`ım giao ba`ˇng ca´ch gia˙’i heˆ. ca´c phu
.o.ng tr`ınh . . . . . . . . . . . . . . 89
3.3.2 Thuaˆ. t toa´n chia nhi. phaˆn . . . . . . . . . . . . . . . . . . . . . . . . 89
3.3.3 Thuaˆ. t toa´n Cohen-Sutherland . . . . . . . . . . . . . . . . . . . . . . 93
3.3.4 Thuaˆ. t toa´n Liang-Barsky . . . . . . . . . . . . . . . . . . . . . . . . 97
3.4 Giao cu˙’a d¯oa.n tha˙ˇ’ng va` d¯a gia´c lo`ˆi . . . . . . . . . . . . . . . . . . . . . . . 100
3.4.1 Vi. tr´ı tu
.o.ng d¯oˆ´i cu˙’a moˆ. t d¯ieˆ˙’m vo´
.i d¯u.`o.ng tha˙ˇ’ng . . . . . . . . . . . . 100
3.4.2 Thuaˆ. t toa´n t`ım giao cu˙’a d¯oa.n tha˙ˇ’ng va` d¯a gia´c lo`ˆi . . . . . . . . . . 102
3.5 Giao hai d¯a gia´c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
3.5.1 Thuaˆ. t toa´n Sutherland-Hodgman . . . . . . . . . . . . . . . . . . . . 108
3.5.2 Thuaˆ. t toa´n Weiler-Atherton . . . . . . . . . . . . . . . . . . . . . . . 111
3.5.3 Ca´c phe´p toa´n taˆ.p ho.
.p treˆn ca´c d¯a gia´c . . . . . . . . . . . . . . . . 113
3.6 Ray tracing hai chie`ˆu: pha˙’n xa. trong buo`ˆng k´ın . . . . . . . . . . . . . . . . 114
3.6.1 Vector pha˙’n xa. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
3.6.2 Giao cu˙’a tia sa´ng va` d¯u.`o.ng tha˙ˇ’ng . . . . . . . . . . . . . . . . . . . 117
3.6.3 Giao cu˙’a tia sa´ng vo´.i d¯u.`o.ng tro`n . . . . . . . . . . . . . . . . . . . . 121
3.6.4 Xaˆy du.
.ng v´ı du. ray tracing . . . . . . . . . . . . . . . . . . . . . . . 124
3.6.5 Buo`ˆng k´ın la` ellipse . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
4 Toˆ ma`u vu`ng 127
4.1 Ca´c d¯i.nh ngh˜ıa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
4.1.1 Vu`ng d¯i.nh ngh˜ıa bo
.’˙ i pixel . . . . . . . . . . . . . . . . . . . . . . . . 127
5
4.1.2 Vu`ng d¯i.nh ngh˜ıa bo
.’˙ i d¯a gia´c . . . . . . . . . . . . . . . . . . . . . . . 129
4.2 Thuaˆ. t toa´n toˆ ma`u theo veˆ´t da`ˆu loang . . . . . . . . . . . . . . . . . . . . . 129
4.3 Thuaˆ. t toa´n toˆ ma`u theo con cha.y . . . . . . . . . . . . . . . . . . . . . . . . 131
4.4 Thuaˆ. t toa´n toˆ ma`u theo bieˆn . . . . . . . . . . . . . . . . . . . . . . . . . . 134
4.5 So sa´nh ca´c thuaˆ. t toa´n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
4.6 Toˆ ma`u ca´c h`ınh chu˜. nhaˆ. t . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
4.7 Thuaˆ. t toa´n toˆ ma`u d¯a gia´c . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
4.7.1 Ca´c do`ng que´t ngang . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
4.7.2 Ca´c ma˙’nh vu.n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
4.7.3 Lieˆn keˆ´t ca.nh va` thuaˆ. t toa´n tra`n . . . . . . . . . . . . . . . . . . . . 151
4.7.4 Toˆ ma`u ca´c d¯a gia´c cho`ˆng nhau . . . . . . . . . . . . . . . . . . . . . 158
4.8 Toˆ ma`u theo maˆ˜u toˆ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
Pha`ˆn phu. lu. c: Thu
. vieˆ.n graph2D.h 163
Ta`i lieˆ.u tham kha˙’o 171
6
Lo`.i no´i d¯a`ˆu
D- o`ˆ ho.a ma´y t´ınh la` moˆ. t l˜ınh vu
.
. c haˆ´p daˆ˜n cu˙’a khoa ho.c ma´y t´ınh. Chu´ng ta su
.’˙ du.ng d¯o`ˆ ho.a
ma´y t´ınh nhu. moˆ.t coˆng cu. d¯eˆ˙’ quan sa´t thoˆng tin trong nhie`ˆu l˜ınh vu
.
. c kha´c nhau, bao go`ˆm
khoa ho.c va` coˆng ngheˆ., hoa´ ho.c, kieˆ´n tru´c va` gia˙’i tr´ı. Ca´c chu
.o.ng tr`ınh d¯o`ˆ ho.a tu
.o.ng ta´c
cho phe´p ngu.`o.i su.’˙ du.ng la`m vieˆ.c theo ca´ch tu
.
. nhieˆn nhaˆ´t: ngu
.`o.i su.’˙ du.ng cung caˆ´p thoˆng
tin cho tr`ınh u´.ng du.ng thoˆng qua ca´c hoa.t d¯oˆ.ng beˆn ngoa`i cu˙’a ho. va` se˜ nhaˆ.n d¯u
.o.. c thoˆng
tin tro.’˙ la. i ba`ˇng h`ınh a˙’nh. D- o`ˆ ho.a ma´y t´ınh d¯ang giu´p con ngu
.`o.i thay d¯oˆ˙’i ve`ˆ quan nieˆ.m va`
ca´ch thu´.c su.’˙ du.ng ma´y t´ınh.
Gia´o tr`ınh D- o`ˆ ho. a ma´y t´ınh I cung caˆ´p moˆ.t soˆ´ ky˜ thuaˆ. t co
. ba˙’n cu˙’a d¯o`ˆ ho.a ma´y t´ınh
hai chie`ˆu. (D- o`ˆ ho.a ma´y t´ınh ba chie`ˆu, moˆ. t pha`ˆn quan tro.ng khoˆng theˆ˙’ thieˆ´u d¯u
.o.. c se˜ d¯u
.o.. c
d¯e`ˆ caˆ.p trong moˆ.t gia´o tr`ınh kha´c). D- eˆ˙’ co´ moˆ. t khung ca˙’nh toa`n dieˆ.n va` saˆu saˇ´c ve`ˆ nhu˜
.ng
nguyeˆn ly´ va` thu.. c ha`nh cu˙’a d¯o`ˆ ho.a ma´y t´ınh, xem ca´c ta`i lieˆ.u daˆ˜n [9] va` [11]. Ca´c phu
.o.ng
pha´p phaˆn t´ıch va` thieˆ´t keˆ´ ca´c thuaˆ. t toa´n trong gia´o tr`ınh cho phe´p sinh vieˆn co´ theˆ˙’ vieˆ´t
de˜ˆ da`ng ca´c chu.o.ng tr`ınh minh ho.a. Gia´o tr`ınh d¯u
.o.. c bieˆn soa.n cho ca´c d¯oˆ´i tu
.o.. ng la` sinh
vieˆn Toa´n-Tin va` Tin ho.c.
Gia´o tr`ınh su.’˙ du.ng ngoˆn ngu˜
. C d¯eˆ˙’ minh ho.a, tuy nhieˆn co´ theˆ˙’ de˜ˆ da`ng chuyeˆ˙’n d¯oˆ˙’i
sang ca´c ngoˆn ngu˜. kha´c; va` do d¯o´, sinh vieˆn ca`ˆn co´ moˆ. t soˆ´ kieˆ´n thu´
.c ve`ˆ ngoˆn ngu˜. C. Ngoa`i
ra, ha`ˆu heˆ´t ca´c chu.o.ng tr`ınh thao ta´c treˆn caˆ´u tru´c du˜. lieˆ.u nhu
. danh sa´ch lieˆn keˆ´t, neˆn d¯o`i
ho˙’i sinh vieˆn pha˙’i co´ nhu˜.ng ky˜ naˇng laˆ.p tr`ınh toˆ´t.
Sinh vieˆn cu˜ng ca`ˆn co´ co. so.’˙ toa´n ho.c cu˙’a nhu˜
.ng naˇm d¯a`ˆu d¯a. i ho.c: hieˆ˙’u bieˆ´t ve`ˆ d¯a. i soˆ´
tuyeˆ´n t´ınh va` h`ınh ho.c gia˙’i t´ıch, phe´p t´ınh vi t´ıch phaˆn.
Mu. c d¯ı´ch cu˙’a gia´o tr`ınh la`, o
.’˙ mu´.c d¯oˆ. na`o d¯o´, cho thaˆ´y ca´c tr`ınh u´
.ng du.ng d¯o`ˆ ho.a
d¯u.o.. c ta.o ra nhu
. theˆ´ na`o: Chu´ng ta ca`ˆn vieˆ´t va` cha.y thu
.’˙ ca´c chu.o.ng tr`ınh. Moˆ.t trong
nhu˜.ng mu. c d¯ı´ch ch´ınh cu˙’a gia´o tr`ınh la` giu´p sinh vieˆn naˇ´m vu˜
.ng ca´c phu.o.ng pha´p, tru.´o.c
heˆ´t toa´n ho.c hoa´ ca´c kha´c nieˆ.m h`ınh ho.c va` sau d¯o´ chuyeˆ˙’n ta˙’i tha`nh ca´c d¯oa.n ma˜ chu
.o.ng
tr`ınh.
7
Gia´o tr`ınh bao go`ˆm boˆ´n chu.o.ng va` moˆ.t pha`ˆn phu. lu. c vo´
.i nhu˜.ng noˆ. i dung ch´ınh nhu
.
sau:
• Chu.o.ng thu´. nhaˆ´t d¯e`ˆ caˆ.p d¯eˆ´n ca´c phu.o.ng pha´p ve˜ ca´c “nguyeˆn so.” cu˙’a d¯o`ˆ ho.a ma´y
t´ınh: d¯oa.n tha˙ˇ’ng, d¯u
.`o.ng tro`n va` ellipse.
• Phaˆn t´ıch va` thieˆ´t keˆ´ ba`ˇng h`ınh ho.c la` noˆ. i dung ch´ınh cu˙’a Chu.o.ng 2. Ha`ˆu heˆ´t ca´c
pha`ˆn me`ˆm d¯o`ˆ ho.a d¯e`ˆu co´ nhu˜
.ng chu´.c naˇng ta.o ra ca´c d¯u
.`o.ng cong du.. a treˆn ca´c d¯ieˆ˙’m
ma` ngu.`o.i su.’˙ du.ng lu
.
. a cho.n. Chu
.o.ng na`y cung caˆ´p nhu˜.ng nguyeˆn ly´ va` ca´ch tieˆ´p caˆ.n
thu.. c ha`nh ma` ca´c tr`ınh u´
.ng du.ng d¯o`ˆ ho.a a´p du.ng.
• Chu.o.ng 3 gia˙’i quyeˆ´t ba`i toa´n xa´c d¯i.nh giao cu˙’a nhu˜.ng nguyeˆn so. d¯o`ˆ ho.a: Giao hai
d¯oa.n tha˙ˇ’ng, giao cu˙’a d¯oa.n tha˙ˇ’ng va` d¯a gia´c lo`ˆi (bao ha`m ca´c h`ınh chu˜
. nhaˆ. t) va` giao
cu˙’a hai d¯a gia´c. Cuoˆ´i chu.o.ng la` moˆ. t v´ı du. cu˙’a ky˜ thuaˆ. t “ray tracing” hai chie`ˆu:
Chuyeˆ˙’n d¯oˆ.ng cu˙’a tia sa´ng trong buo`ˆng k´ın co´ chu´
.a ca´c “chu.´o.ng nga. i vaˆ. t”.
• Chu.o.ng 4 d¯e`ˆ caˆ.p d¯eˆ´n nhu˜.ng thuaˆ. t toa´n toˆ ma`u vu`ng baˆ´t ky`: Vu`ng d¯i.nh ngh˜ıa bo.’˙ i
pha`ˆn trong, bo.’˙ i d¯u.`o.ng bieˆn va` vu`ng la` d¯a gia´c.
• Pha`ˆn phu. lu. c la` thu. vieˆ.n ca´c caˆ´u tru´c du˜. lieˆ.u va` ca´c ha`m ca`ˆn thieˆ´t va` thu.`o.ng xuyeˆn
su.’˙ du.ng trong gia´o tr`ınh.
Trong la`ˆn xuaˆ´t ba˙’n thu´. hai na`y, chu´ng toˆi d¯u.a theˆm ca´c v´ı du. t´ınh toa´n nha`ˇm minh
ho.a cho pha`ˆn ly´ thuyeˆ´t cu˜ng nhu
. giu´p sinh vieˆn naˇ´m vu˜.ng kieˆ´n thu´.c d¯a˜ ho.c. Ngoa`i ra, ca´c
loˆ˜i trong xuaˆ´t ba˙’n la`ˆn tru.´o.c cu˜ng d¯a˜ d¯u.o.. c chı˙’nh ly´; maˇ.c du` vaˆ.y, ta´c gia˙’ vaˆ˜n mong co´ nhu˜
.ng
d¯o´ng go´p tu`. ba.n d¯o.c.
Toˆi xin ca˙’m o.n nhu˜.ng giu´p d¯o˜. d¯a˜ nhaˆ.n d¯u
.o.. c tu`
. nhie`ˆu ngu.`o.i ma` khoˆng theˆ˙’ lieˆ.t keˆ
heˆ´t, d¯aˇ. c bieˆ.t la` ca´c ba.n sinh vieˆn, trong qua´ tr`ınh bieˆn soa.n gia´o tr`ınh na`y.
D- a` La.t, nga`y 10 tha´ng 1 naˇm 2005
PHA. M Tieˆ´n So
.n
8
Chu.o.ng 1
Ca´c thuaˆ.t toa´n ve˜ d¯u
.`o.ng cong treˆn
thieˆ´t bi. raster
Chu.o.ng na`y tr`ınh ba`y ca´c thuaˆ. t toa´n ve˜ d¯oa.n tha˙ˇ’ng, d¯u
.`o.ng tro`n va` ellipse treˆn lattice
nguyeˆn Z2. Ca´c thuaˆ. t toa´n chı˙’ thao ta´c treˆn nhu˜.ng soˆ´ nguyeˆn va` trong ca´c vo`ng laˇ.p chı˙’ su.’˙
du.ng phe´p toa´n coˆ.ng neˆn raˆ´t hieˆ.u qua˙’.
1.1 D- oa.n tha˙ˇ’ng
Thuaˆ. t toa´n ve˜ d¯oa.n tha˙ˇ’ng xa´c d¯i.nh to.a d¯oˆ. cu˙’a ca´c pixel naˇ`m treˆn hoaˇ.c ga`ˆn vo´
.i d¯oa.n tha˙ˇ’ng
thu.. c teˆ´ nhaˆ´t. Ve`ˆ nguyeˆn taˇ´c, chu´ng ta muoˆ´n cho.n da˜y ca´c pixel ga`ˆn vo´
.i d¯oa.n tha˙ˇ’ng thu
.
. c teˆ´
nhaˆ´t va` tha˙ˇ’ng nhaˆ´t. Xe´t d¯oa.n tha˙ˇ’ng thu
.
. c teˆ´ d¯u
.o.. c xaˆ´p xı˙’ vo´
.i maˆ. t d¯oˆ. moˆ. t pixel; ta ca`ˆn co´
nhu˜.ng t´ınh chaˆ´t g`ı? Vo´.i ca´c d¯oa.n tha˙ˇ’ng co´ heˆ. soˆ´ go´c thuoˆ.c d¯oa.n [−1, 1], co´ d¯u´ng moˆ.t pixel
d¯u.o.. c ve˜ leˆn treˆn moˆ˜i coˆ. t; vo´
.i ca´c d¯oa.n tha˙ˇ’ng ma` heˆ. soˆ´ go´c na`ˇm ngoa`i d¯oa.n na`y, co´ d¯u´ng
moˆ.t pixel d¯u
.o.. c ve˜ treˆn moˆ˜i ha`ng. Taˆ´t ca˙’ ca´c d¯oa.n tha˙ˇ’ng d¯u
.o.. c ve˜ vo´
.i cu`ng moˆ.t d¯oˆ. sa´ng,
khoˆng phu. thuoˆ.c va`o d¯oˆ. da`i va` hu
.´o.ng, va` nhanh nhaˆ´t co´ theˆ˙’ d¯u.o.. c. Thuaˆ. t toa´n ve˜ d¯oa.n
tha˙ˇ’ng cu˜ng ca`ˆn chu´ y´ d¯eˆ´n ca´c thuoˆ.c t´ınh cu˙’a d¯oa.n tha˙ˇ’ng nhu
. d¯oˆ. roˆ.ng, kieˆ˙’u ve˜... Thaˆ.m ch´ı
chu´ng ta muoˆ´n cu.. c tieˆ˙’u hoa´ mu´
.c d¯oˆ. raˇng cu
.a do tieˆ´n tr`ınh ro`.i ra.c hoa´ d¯u
.`o.ng tha˙ˇ’ng thu.. c
teˆ´ nho`. su.’˙ du.ng ky˜ thuaˆ. t antialiasing (xem [9], [11]) baˇ`ng ca´ch a´p du.ng kha˙’ naˇng d¯aˇ. t cu
.`o.ng
d¯oˆ. cu˙’a moˆ˜i pixel treˆn ca´c thieˆ´t bi. hieˆ˙’n thi. ma` moˆ.t pixel tu
.o.ng u´.ng nhie`ˆu bit.
Tru.´o.c heˆ´t chu´ng ta chı˙’ d¯e`ˆ caˆ.p d¯eˆ´n ca´c d¯oa.n tha˙ˇ’ng d¯oˆ. roˆ.ng moˆ.t pixel va` co´ d¯u´ng moˆ.t
pixel treˆn moˆ˜i coˆ. t (hoaˇ.c ha`ng d¯oˆ´i vo´
.i ca´c d¯oa.n tha˙ˇ’ng doˆ´c). Pha`ˆn cuoˆ´i chu
.o.ng se˜ d¯e`ˆ caˆ.p
9
d¯eˆ´n d¯oˆ. roˆ.ng ca´c nguyeˆn so
. va` ca´c maˆ˜u ve˜.
Moˆ.t ca´ch h`ınh ho.c, chu´ng ta bieˆ˙’u die˜ˆn moˆ.t pixel nhu
. moˆ.t chaˆ´m tro`n vo´
.i taˆm ta. i vi.
tr´ı (x, y) cu˙’a pixel treˆn lu.´o.i ca´c to.a d¯oˆ. nguyeˆn Z2. Bieˆ˙’u die˜ˆn na`y la` moˆ. t xaˆ´p xı˙’ th´ıch ho.. p
nha´t caˇ´t ngang trong moˆ.t chu ky` cu˙’a chu`m tia electron cu˙’a CRT; xaˆ´p xı˙’ na`y phu. thuoˆ.c va`o
khoa˙’ng ca´ch (tuy` thuoˆ.c va`o heˆ. thoˆ´ng) giu˜
.a ca´c veˆ´t treˆn ma`n h`ınh hieˆ˙’n thi.. Trong moˆ.t soˆ´
heˆ. thoˆ´ng, ca´c chaˆ´m ke`ˆ nhau phu˙’ laˆ´p moˆ.t pha`ˆn leˆn nhau; vo´
.i nhu˜.ng heˆ. thoˆ´ng kha´c co´ nhu˜
.ng
khoa˙’ng ca´ch giu˜.a ca´c pixel d¯u´.ng ke`ˆ nhau; trong ha`ˆu heˆ´t ca´c heˆ. thoˆ´ng, khoa˙’ng ca´ch theo
chie`ˆu ngang nho˙’ ho.n theo chie`ˆu d¯u´.ng. Moˆ.t kha´c bieˆ.t nu˜
.a tuy` theo heˆ. thoˆ´ng trong vieˆ.c bieˆ˙’u
die˜ˆn heˆ. to.a d¯oˆ. , cha˙ˇ’ng ha.n Macintosh xem ca´c pixel d¯u
.o.. c d¯aˇ. t ta. i taˆm cu˙’a h`ınh chu˜
. nhaˆ. t
giu˜.a ca´c d¯u.`o.ng tha˙ˇ’ng ke`ˆ nhau cu˙’a lu.´o.i d¯ie`ˆu khieˆ˙’n thay cho naˇ`m treˆn ca´c d¯u.`o.ng tha˙ˇ’ng cu˙’a
lu.´o.i. Theo ca´ch na`y, ca´c h`ınh chu˜. nhaˆ. t (xa´c d¯i.nh bo
.’˙ i hai go´c) go`ˆm ca´c pixel thuoˆ.c pha`ˆn
trong cu˙’a no´. D- i.nh ngh˜ıa na`y cho phe´p ca´c vu`ng d¯oˆ. roˆ.ng ba`ˇng khoˆng: Hı`nh chu˜
. nhaˆ. t tu`
.
(x, y) d¯eˆ´n (x, y) khoˆng chu´.a pixel na`o, trong khi vo´.i nhu˜.ng heˆ. thoˆ´ng kha´c, co´ d¯u´ng moˆ.t
pixel ta. i d¯ieˆ˙’m na`y. Du
.´o.i d¯aˆy chu´ng ta se˜ bieˆ˙’u die˜ˆn ca´c pixel nhu. ca´c h`ınh tro`n ro`.i nhau co´
taˆm na`ˇm treˆn lu.´o.i.
Hı`nh 1.1 la` pho´ng to cu˙’a d¯u.`o.ng tha˙ˇ’ng thu.. c teˆ´ va` xaˆ´p xı˙’ d¯oˆ. roˆ.ng moˆ.t pixel cu˙’a no´.
Ca´c pixel d¯u.o.. c ve˜ tu
.o.ng u´.ng ca´c h`ınh tro`n ma`u d¯en va` ca´c pixel khoˆng d¯u.o.. c ve˜ tu
.o.ng u´.ng
h`ınh tro`n khoˆng toˆ. Treˆn ma`n h`ınh thu.. c teˆ´, d¯u
.`o.ng k´ınh cu˙’a h`ınh tro`n bieˆ˙’u die˜ˆn pixel lo´.n
ho.n khoa˙’ng ca´ch giu˜.a ca´c pixel ke`ˆ nhau, bo.’˙ i vaˆ.y bieˆ˙’u die˜ˆn baˇ`ng ky´ hieˆ.u cu˙’a chu´ng ta la`
moˆ. t pho´ng d¯a. i mu´
.c d¯oˆ. ro`
.i ra.c cu˙’a ca´c pixel.
...............................................................................................................................................................................................................................
...............................................................................................................................................................................................................................
...............................................................................................................................................................................................................................
...............................................................................................................................................................................................................................
....
....
....
....
....
...
....
....
....
....
....
....
....
....
....
....
...
....
....
....
....
....
....
....
....
....
....
...
....
....
....
....
....
....
....
....
....
....
...
....
....
....
....
....
.
....
....
....
....
....
...
....
....
....
....
....
....
....
....
....
....
...
....
....
....
....
....
....
....
....
....
....
...
....
....
....
....
....
....
....
....
....
....
...
....
....
....
....
....
.
....
....
....
....
....
...
....
....
....
....
....
....
....
....
....
....
...
....
....
....
....
....
....
....
....
....
....
...
....
....
....
....
....
....
....
....
....
....
...
....
....
....
....
....
.
....
....
....
....
....
...
....
....
....
....
....
....
....
....
....
....
...
....
....
....
....
....
....
....
....
....
....
...
....
....
....
....
....
....
....
....
....
....
...
....
....
....
....
....
.
....
....
....
....
....
...
....
....
....
....
....
....
....
....
....
....
...
....
....
....
....
....
....
....
....
....
....
...
....
....
....
....
....
....
....
....
....
....
...
....
....
....
....
....
.
i i i i i
i i i i i
i i i i i
i i i i i
...................................................................................................................................................................................................................................... y
y y
y y
Hı`nh 1.1: D- oa.n tha˙ˇ’ng xaˆ´p xı˙’ d¯u
.o.. c bieˆ˙’u die˜ˆn bo
.’˙ i ca´c h`ınh tro`n d¯en.
Vı` ca´c nguyeˆn so. trong heˆ. thoˆ´ng chu´ng ta xa´c d¯i.nh treˆn lu
.´o.i d¯ie`ˆu khieˆ˙’n nguyeˆn neˆn
ca´c to.a d¯oˆ. d¯a`ˆu cuoˆ´i cu˙’a d¯oa.n tha˙ˇ’ng la` nguyeˆn. Thaˆ. t ra, neˆ´u chu´ng ta caˇ´t d¯oa.n tha˙ˇ’ng vo´
.i
h`ınh chu˜. nhaˆ. t tru
.´o.c khi hieˆ˙’n thi. no´ th`ı to.a d¯oˆ. ca´c d¯ieˆ˙’m d¯a`ˆu cuoˆ´i cu˙’a d¯oa.n tha˙ˇ’ng co´ theˆ˙’
khoˆng nguyeˆn. (Chu´ng ta se˜ tha˙’o luaˆ.n ca´c giao d¯ieˆ˙’m khoˆng nguyeˆn trong Pha`ˆn 1.1.3). Gia˙’
10
su.’˙ d¯oa.n tha˙ˇ’ng co´ heˆ. soˆ´ go´c |m| ≤ 1; ca´c tru.`o.ng ho.. p kha´c d¯u.o.. c xu.’˙ ly´ tu.o.ng tu.. . Ho.n nu˜.a
tru.`o.ng ho.. p ca´c d¯oa.n tha˙ˇ’ng ngang, d¯u´
.ng hoaˇ.c co´ heˆ. soˆ´ go´c ±1 la` ta`ˆm thu.`o.ng v`ı chu´ng chı˙’
d¯i qua ca´c pixel treˆn lu.´o.i.
1.1.1 Thuaˆ.t toa´n soˆ´ gia
Xe´t hai pixel A = (xA, yA) va` B = (xB, yB) (tu´c ca´c pha`ˆn tu
.’˙ cu˙’a lattice nguyeˆn Z2). Phu.o.ng
tr`ınh d¯u.`o.ng tha˙ˇ’ng AB co´ da.ng y = mx+ t, trong d¯o´ heˆ. soˆ´ go´c m = dy/dx va` t = yA−mxA.
Ca´ch d¯o.n gia˙’n nhaˆ´t d¯eˆ˙’ ve˜ d¯oa.n tha˙ˇ’ng AB la`:
1. T´ınh heˆ. soˆ´ go´c m;
2. Taˇng x moˆ.t d¯o
.n vi. (kho
.’˙ i d¯a`ˆu tu`. d¯ieˆ˙’m beˆn tra´i nhaˆ´t), vo´.i moˆ˜i xi t´ınh yi = mxi + t va`
sau d¯o´ ve˜ pixel ta. i (xi, byi + 0.5c)1.
Theo ca´ch na`y ta cho.n pixel toˆ´t nhaˆ´t, tu´
.c la` pixel ma` khoa˙’ng ca´ch d¯eˆ´n d¯u.`o.ng tha˙ˇ’ng thu.. c
teˆ´ nho˙’ nhaˆ´t. Phu.o.ng pha´p na`y khoˆng hieˆ.u qua˙’ do moˆ˜i bu
.´o.c laˇ.p ca`ˆn t´ınh moˆ.t phe´p nhaˆn,
moˆ.t phe´p coˆ.ng va` moˆ.t phe´p toa´n la`m tro`n. Ta co´ theˆ˙’ khu
.’˙ phe´p nhaˆn ba`ˇng ca´ch chu´ y´ ra`ˇng
yi+1 = mxi+1 + t
= m(xi +∆x) + t
= yi +m∆x,
va` neˆ´u bu.´o.c taˇng ∆x = 1 th`ı yi+1 = yi +m.
Do d¯o´ neˆ´u x taˇng moˆ.t d¯o
.n vi. th`ı y taˇng m d¯o
.n vi.. Vo´
.i mo. i d¯ieˆ˙’m (xi, yi) treˆn d¯oa.n
tha˙ˇ’ng ta bieˆ´t ra`ˇng neˆ´u xi+1 = xi + 1 th`ı yi+1 = yi +m; tu´
.c la`, ca´c gia´ tri. x va` y d¯u
.o.. c t´ınh
theo ca´c gia´ tri. tru
.´o.c d¯o´ cu˙’a no´ (xem Hı`nh 1.2). D- aˆy ch´ınh la` “thuaˆ. t toa´n soˆ´ gia”: vo´
.i moˆ˜i
bu.´o.c laˇ.p ta thu
.
. c hieˆ.n ca´c phe´p toa´n soˆ´ gia du
.
. a treˆn bu
.´o.c tru.´o.c.
Kho.’˙ i ta.o ta ga´n (x0, y0) la` to.a d¯oˆ. nguyeˆn cu˙’a d¯ieˆ˙’m xuaˆ´t pha´t, cha˙ˇ’ng ha.n A. Chu´ y´
ra`ˇng trong tru.`o.ng ho.. p |m| > 1 neˆ´u x taˇng moˆ.t d¯o.n vi. th`ı y taˇng ho.n moˆ.t d¯o.n vi.. Do d¯o´
ca`ˆn hoa´n d¯oˆ˙’i vai tro` cu˙’a x va` y ba`ˇng ca´ch ga´n bu.´o.c taˇng moˆ.t d¯o
.n vi. cho y va` taˇng x moˆ.t
lu.o.. ng ∆x =
∆y
m
= 1
m
.
1Ky´ hieˆ.u [x], bxc va` dxe tu.o.ng u´.ng la` pha`ˆn nguyeˆn, la`m tro`n xuoˆ´ng va` la`m tro`n leˆn cu˙’a x.
11
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
.....................................................................................................................................................................................................................................
.....................................................................................................................................................................................................................................
.....................................................................................................................................................................................................................................
(xi, yi) ....................................................................................................
(xi, byic)
.....
.....
.....
.....
.....
....
.....
.....
.....
.....
.....
.......
(xi + 1, yi +m)
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
...
.....
.....
.....
.....
.....
.....
.........
(xi + 1, dyi +me)..............................................................................................
D- u.`o.ng tha˙ˇ’ng
thu.. c teˆ´
........
........
........
........
.....
........
........
........
........
........
........
........
........
......
........
........
......
........
........
........
......
........
........
........
........
........
.......
........
.. ...
........
........
........
........
..
w
w w
w
Hı`nh 1.2: T´ınh toa´n soˆ´ gia cu˙’a (xi, yi).
Vı´ du. 1.1.1 Gia˙’ su
.’˙ A(2, 0), B(9, 3). Khi d¯o´ d¯u.`o.ng tha˙ˇ’ng qua hai d¯ieˆ˙’m A va` B co´ heˆ. soˆ´
go´c m = 3
7
∈ (0, 1). A´p du.ng thuaˆ. t toa´n soˆ´ gia ta d¯u.o.. c da˜y ca´c d¯ieˆ˙’m ve˜ toˆ´t nhaˆ´t nhu. trong
ba˙’ng du.´o.i:
i xi yi byi + 0.5c
0 2 0 0
1 3 3
7
0
2 4 6
7
1
3 5 9
7
1
4 6 12
7
2
5 7 15
7
2
6 8 18
7
3
7 9 21
7
3
Thu˙’ tu. c Line() du
.´o.i d¯aˆy minh ho.a thuaˆ. t toa´n ve˜ d¯oa.n tha˙ˇ’ng tu`
. (x0, y0) d¯eˆ´n (x1, y1)
vo´.i gia´ tri. ma`u V alue. D- ieˆ˙’m kho
.’˙ i d¯a`ˆu la` d¯ieˆ˙’m beˆn tra´i nhaˆ´t. Ngoa`i ra ta chı˙’ xe´t tru.`o.ng ho.. p
−1 ≤ m ≤ 1 v`ı ca´c tru.`o.ng ho.. p kha´c co´ theˆ˙’ thu.. c hieˆ.n do t´ınh d¯oˆ´i xu´.ng. Ho.n nu˜.a, chu´ng ta
cu˜ng bo˙’ qua vieˆ.c kieˆ˙’m tra ca´c tru
.`o.ng ho.. p d¯aˇ. c bieˆ.t: d¯u
.`o.ng tha˙ˇ’ng na`ˇm ngang, d¯u´.ng, xieˆn
moˆ.t go´c ±450. Chu´ y´ ra`ˇng, trong ngoˆn ngu˜. C, (int)y ba`ˇng by + 0.5c.
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 Thuaˆ.t toa´n d¯ieˆ˙’m giu˜
.a
Thu˙’ tu. c Line() thao ta´c treˆn ca´c soˆ´ thu
.
. c y va` m. Bresenham d¯a˜ xaˆy du
.
. ng thuaˆ. t toa´n [2] ve˜
d¯oa.n tha˙ˇ’ng chı˙’ su
.’˙ du.ng ca´c phe´p toa´n treˆn soˆ´ nguyeˆn do d¯o´ tra´nh go. i ha`m la`m tro`n va` cho
phe´p xa´c d¯i.nh (xi+1, yi+1) theo soˆ´ gia du
.
. a treˆn nhu˜
.ng gia´ tri. o
.’˙ bu.´o.c tru.´o.c (xi, yi). Thuaˆ. t
toa´n na`y co´ theˆ˙’ mo.’˙ roˆ.ng da.ng daˆ´u chaˆ´m d¯oˆ.ng d¯oˆ´i vo´
.i ca´c to.a d¯oˆ. thu
.
. c. Ho
.n nu˜.a, phu.o.ng
pha´p cu˙’a Bresenham co´ theˆ˙’ d¯u.o.. c a´p du.ng t´ınh toa´n treˆn soˆ´ nguyeˆn ve˜ d¯u
.`o.ng tro`n maˇ.c du`
no´ khoˆng de˜ˆ da`ng mo.’˙ roˆ.ng cho conic tuy` y´. Vı` vaˆ.y chu´ng ta su
.’˙ du.ng phu
.o.ng pha´p tu.o.ng
d¯oˆ´i kha´c, thuaˆ. t toa´n d¯ieˆ˙’m giu˜
.a, d¯u.o.. c coˆng boˆ´ la`ˆn d¯a`ˆu tieˆn bo
.’˙ i Pitteway [16], [17] va` d¯u.o.. c
ca˙’i tieˆ´n bo.’˙ i Van Aken [26] va` moˆ. t soˆ´ ta´c gia˙’ kha´c [28], [29]. Van Aken d¯a˜ chı˙’ ra [26] d¯oˆ´i vo´
.i
ca´c d¯u.`o.ng tha˙ˇ’ng va` d¯u.`o.ng tro`n vo´.i du˜. lieˆ.u nguyeˆn, coˆng thu´
.c d¯ieˆ˙’m giu˜.a suy ra coˆng thu´.c
cu˙’a Bresenham va` do d¯o´ sinh ra cu`ng da˜y ca´c pixel.
Khoˆng maˆ´t t´ınh toˆ˙’ng qua´t, gia˙’ su.’˙ heˆ. soˆ´ go´c m cu˙’a d¯u
.`o.ng tha˙ˇ’ng thuoˆ.c khoa˙’ng (0, 1)
(ca´c tru.`o.ng ho.. p kha´c co´ theˆ˙’ d¯u
.o.. c xu
.’˙ ly´ bo.’˙ i ca´c phe´p laˆ´y d¯oˆ´i xu´.ng moˆ.t ca´ch th´ıch ho
.
. p qua
ca´c tru. c to.a d¯oˆ. ). Ta cu˜ng ky´ hieˆ.u d¯ieˆ˙’m xuaˆ´t pha´t la` (xA, yA) va` d¯ieˆ˙’m keˆ´t thu´c la` (xB, yB).
D- aˇ. t dy := yB − yA, dx = xB − xA. Phu.o.ng tr`ınh d¯u.`o.ng tha˙ˇ’ng l qua hai d¯ieˆ˙’m A va` B xa´c
d¯i.nh bo
.’˙ i
y =
dy
dx
x+ t;
13
........
........
........
........
........
........
........
........
........
........
........
........
........
........
........
........
........
........
........
........
........
........
........
........
........
........
........
...
.............(l−)
(l+)
M
Qw
C
w
R
wD
l
Hı`nh 1.3: Lu.´o.i ca´c pixel va` vi. tr´ı d¯ieˆ˙’m C,R,D,Q va` M.
hay tu.o.ng d¯u.o.ng
f(x, y) := ax+ by + c = 0,
trong d¯o´ a = dy, b = −dx, va` c = b × dx. Ky´ hieˆ.u ca´c nu.’˙ a maˇ. t pha˙ˇ’ng ngoa`i va` nu.’˙ a maˇ. t
pha˙ˇ’ng trong xa´c d¯i.nh bo
.’˙ i l tu.o.ng u´.ng bo.’˙ i
(l+) := {(x, y) ∈ R2 | f(x, y) > 0},
(l−) := {(x, y) ∈ R2 | f(x, y) < 0}.
Y´ tu.o.’˙ ng cu˙’a thuaˆ. t toa´n d¯ieˆ˙’m giu˜
.a la` xaˆy du.. ng moˆ.t da˜y ca´c d¯ieˆ˙’m ve˜ “toˆ´t nhaˆ´t” (xi, yi)
baˇ´t d¯a`ˆu tu`. d¯ieˆ˙’m (x0, y0) = (xA, yA). Kha´i nieˆ.m toˆ´t nhaˆ´t o
.’˙ d¯aˆy la` nhu˜.ng d¯ieˆ˙’m (xi, yi) d¯u
.o.. c
cho.n ga`ˆn vo´
.i d¯u.`o.ng tha˙ˇ’ng thu.. c teˆ´ (da.ng lieˆn tu. c) nhaˆ´t. Theo gia˙’ thieˆ´t, 0 < m < 1, neˆn khi
x taˇng moˆ.t lu
.o.. ng ∆x th`ı y taˇng khoˆng qua´ ∆y = m∆x d¯o
.n vi..
Vı` vaˆ.y neˆ´u bu
.´o.c thu´. i cho.n d¯u
.o.. c d¯ieˆ˙’m ve˜ toˆ´t nhaˆ´t C := (xi, yi) th`ı o
.’˙ bu.´o.c thu´. i+ 1
ta se˜ cho.n d¯ieˆ˙’m ve˜ (xi+1, yi+1), trong d¯o´ xi+1 = xi + 1 va` yi+1 = yi hoaˇ.c yi+1 = yi + 1.
No´i ca´ch kha´c, bu.´o.c thu´. i + 1 chu´ng ta se˜ cho.n moˆ.t trong hai pixel R := (xi + 1, yi) hoaˇ.c
D := (xi + 1, yi + 1) (xem Hı`nh 1.3). Ky´ hieˆ.u Q la` giao d¯ieˆ˙’m cu˙’a hai d¯u
.`o.ng tha˙ˇ’ng l va`
x = xi + 1. Theo Bresenham, daˆ´u cu˙’a bieˆ˙’u thu´
.c xa´c d¯i.nh bo
.’˙ i hieˆ.u giu˜
.a hai khoa˙’ng ca´ch tu`.
R va` D d¯eˆ´n Q cho phe´p xa´c d¯i.nh pixel toˆ´t nhaˆ´t o
.’˙ bu.´o.c i+ 1. Trong thuaˆ. t toa´n d¯ieˆ˙’m giu˜
.a,
ta quan sa´t vi. tr´ı cu˙’a d¯ieˆ˙’m giu˜
.a M va` ca´c nu.’˙ a maˇ.t pha˙ˇ’ng xa´c d¯i.nh bo
.’˙ i d¯u.`o.ng tha˙ˇ’ng l. De˜ˆ
da`ng chı˙’ ra raˇ`ng, neˆ´u M ∈ (l+) th`ı pixel D ga`ˆn vo´.i d¯u.`o.ng tha˙ˇ’ng l ho.n; neˆ´u M ∈ (l−) th`ı
pixel R ga`ˆn ho.n. D- u.`o.ng tha˙ˇ’ng l co´ theˆ˙’ d¯i ngang qua M ; hoaˇ.c ca˙’ hai pixel naˇ`m ve`ˆ cu`ng
moˆ.t nu
.’˙ a maˇ.t pha˙ˇ’ng (l
+) (hoaˇ.c (l
−)) nhu.ng trong baˆ´t cu´. tru.`o.ng ho.. p na`o, ta vaˆ˜n cho.n d¯ieˆ˙’m
ga`ˆn vo´.i l nhaˆ´t. Ho.n nu˜.a, sai soˆ´-tu´.c la` khoa˙’ng ca´ch giu˜.a pixel d¯u.o.. c cho.n va` d¯u
.`o.ng tha˙ˇ’ng
thu.. c teˆ´ l-luoˆn luoˆn nho˙’ ho
.n hoaˇ.c ba`ˇng 1/2.
14
D- eˆ˙’ a´p du.ng thuaˆ. t toa´n d¯ieˆ˙’m giu˜
.a, chı˙’ ca`ˆn t´ınh f(M) = f(xi + 1, yi +
1
2
) va` kieˆ˙’m tra
daˆ´u cu˙’a no´. Do d¯o´ ta d¯i.nh ngh˜ıa bieˆ´n quyeˆ´t d¯i.nh
di := f(xi + 1, yi +
1
2
)
= a(xi + 1) + b(yi +
1
2
) + c.
Khi d¯o´
1. Neˆ´u di > 0 cho.n pixel D;
2. Neˆ´u di < 0 cho.n pixel R;
3. Neˆ´u di = 0 cho.n moˆ.t trong hai pixel R hoaˇ.c D, do d¯o´ cho.n R.
Keˆ´ tieˆ´p ta ca`ˆn xa´c d¯i.nh to.a d¯oˆ. d¯ieˆ˙’m giu˜
.a M va` do d¯o´ bieˆ´n quyeˆ´t d¯i.nh di+1 o
.’˙ bu.´o.c i + 1;
d˜ı nhieˆn d¯ie`ˆu na`y phu. thuoˆ.c va`o vieˆ.c cho.n pixel R hoaˇ.c D. Neˆ´u cho.n R th`ı hoa`nh d¯oˆ. d¯ieˆ˙’m
M taˇng moˆ.t d¯o
.n vi. va` tung d¯oˆ. khoˆng d¯oˆ˙’i. Do d¯o´
di+1 = f(xi + 2, yi +
1
2
) = a(xi + 2) + b(yi +
1
2
) + c.
Nhu.ng
di = a(xi + 1) + b(yi +
1
2
) + c.
Suy ra di+1 = di + a.
Ky´ hieˆ.u soˆ´ gia d¯u
.o.. c coˆ.ng theˆm khi R d¯u
.o.. c cho.n la` ∆R := a = dy. No´i ca´ch kha´c, ta
co´ theˆ˙’ suy ra bieˆ´n quyeˆ´t d¯i.nh o
.’˙ bu.´o.c keˆ´ tieˆ´p tu`. bieˆ´n quyeˆ´t d¯i.nh o
.’˙ bu.´o.c hieˆ.n ha`nh baˇ`ng
ca´ch coˆ.ng theˆm soˆ´ gia ∆R ma` khoˆng ca`ˆn pha˙’i t´ınh la. i gia´ tri. f(M).
Neˆ´u cho.n D th`ı hoa`nh d¯oˆ. va` tung d¯oˆ. d¯ieˆ˙’m M cu`ng taˇng moˆ.t d¯o
.n vi., neˆn
di+1 = f(xi + 2, yi +
3
2
) = a(xi + 2) + b(yi +
3
2
) + c.
Va` do d¯o´
di+1 = di + a+ b.
Ky´ hieˆ.u soˆ´ gia d¯u
.o.. c coˆ.ng va`o di+1 sau khi cho.n D la` ∆D := a+ b = dy − dx.
Vı` o.’˙ bu.´o.c d¯a`ˆu tieˆn, ta cho.n (x0, y0) = (xA, yA) neˆn co´ theˆ˙’ t´ınh tru
.
. c tieˆ´p gia´ tri. kho
.’˙ i
ta.o d0. Thaˆ.t vaˆ.y, d¯ieˆ˙’m giu˜
.a d¯a`ˆu tieˆn co´ to.a d¯oˆ. (x0 + 1, y0 +
1
2
), va`
f(x0 + 1, y0 +
1
2
) = a(x0 + 1) + b(y0 +
1
2
) + c
= ax0 + by0 + c+ a+ b/2
= f(x0, y0) + a+ b/2.
15
Nhu.ng (x0, y0) thuoˆ.c d¯u
.`o.ng tha˙ˇ’ng l neˆn f(x0, y0) = 0; do d¯o´ gia´ tri. kho
.’˙ i d¯a`ˆu cu˙’a bieˆ´n
quyeˆ´t d¯i.nh la` d0 = a + b/2 = dy − dx/2. Su.’˙ du.ng d0 ta co´ theˆ˙’ cho.n pixel thu´. hai, thu´.
ba, v.v. D- eˆ˙’ khu.’˙ maˆ˜u soˆ´ trong d0 ta d¯i.nh ngh˜ıa la. i ha`m f ba`ˇng ca´ch nhaˆn no´ cho 2; tu´
.c la`
f(x, y) = 2(ax + by + c). No´i ca´ch kha´c, nhaˆn 2 cho ca´c haˇ`ng soˆ´ a, b, c va` bieˆ´n quyeˆ´t d¯i.nh;
ma` d¯ie`ˆu na`y khoˆng a˙’nh hu.o.’˙ ng d¯eˆ´n daˆ´u cu˙’a bieˆ´n quyeˆ´t d¯i.nh.
Toˆ˙’ng qua´t hoa´ thuaˆ. t toa´n d¯ieˆ˙’m giu˜
.a ve˜ d¯oa.n tha˙ˇ’ng AB (trong tru
.`o.ng ho.. p xA < xB
va` 0 < m < 1) nhu. sau:
1. [Kho.’˙ i ta.o] D- aˇ. t dx = xB − xA, dy = yB − yA, d0 = 2dy − dx,∆R = 2dy,∆D = 2(dy −
dx), x0 = xA, y0 = yA.
2. Gia˙’ su.’˙ o.’˙ bu.´o.c thu´. i ta co´ d¯ieˆ˙’m ve˜ toˆ´t nhaˆ´t (xi, yi) va` bieˆ´n quyeˆ´t d¯i.nh di.
3. [Ve˜ pixel hieˆ.n ha`nh] D- aˇ. t d¯ieˆ˙’m ve˜ ta. i (xi, yi).
4. [Caˆ.p nhaˆ. t] Neˆ´u xi = xB, thuaˆ. t toa´n du`
.ng; ngu.o.. c la. i, d¯aˇ. t
xi+1 = xi + 1;
yi+1 =
{
yi neˆ´u di ≤ 0,
yi + 1 neˆ´u ngu
.o.. c la. i;
di+1 =
{
di +∆R neˆ´u di ≤ 0,
di +∆D neˆ´u ngu
.o.. c la. i.
5. Thay i ba`ˇng (i+ 1) va` laˇ.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 tha˙ˇ’ng qua hai d¯ieˆ˙’m A va` B co´ heˆ. soˆ´
go´c m = 3
7
∈ (0, 1). De˜ˆ da`ng kieˆ˙’m tra ra`ˇng
dx = xB − xA = 7,
dy = yB − yA = 3,
d0 = 2dy − dx = −1,
∆R = 2dy = 6,
∆D = 2(dy − dx) = −8.
16
A´p du.ng thuaˆ. t toa´n d¯ieˆ˙’m giu˜
.a ta co´ da˜y ca´c d¯ieˆ˙’m ve˜ toˆ´t nhaˆ´t nhu. trong ba˙’ng du.´o.i:
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
Hieˆ˙’n nhieˆn ra`ˇng ca´c keˆ´t qua˙’ na`y tru`ng vo´.i keˆ´t qua˙’ khi su.’˙ du.ng phu
.o.ng pha´p soˆ´ gia trong
Vı´ du. 1.1.1.
Chu´ y´ ra`ˇng, phe´p t´ınh ca`ˆn thieˆ´t d¯oˆ´i vo´.i di+1 trong moˆ˜i bu
.´o.c laˇ.p la` phe´p coˆ.ng va` khoˆng
co´ phe´p nhaˆn. Ho.n nu˜.a, vo`ng laˇ.p hoa`n toa`n d¯o
.n gia˙’n nhu. trong thu˙’ tu. c MidPointLine()
du.´o.i d¯aˆy:
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 <= x_B; x++)
{
putpixel(x, y, Value);
if (d <= 0) d += DeltaR;
else
{
d += DeltaD;
17
y++;
}
}
}
1.1.3 Moˆ.t soˆ´ vaˆ´n d¯e`ˆ lieˆn quan d¯eˆ´n thuaˆ.t toa´n ve˜ d¯oa.n tha˙ˇ’ng
Thu´. tu.. cu˙’a ca´c d¯ieˆ˙’m d¯a`ˆu cuoˆ´i. Trong moˆ.t u´
.ng du.ng ta ca`ˆn d¯o`i ho˙’i moˆ. t d¯oa.n tha˙ˇ’ng
d¯u.o.. c ve˜ tu`
. A d¯eˆ´n B chu´.a cu`ng taˆ.p ca´c pixel nhu
. d¯oa.n tha˙ˇ’ng d¯u
.o.. c ve˜ tu`
. B d¯eˆ´n A; no´i
ca´ch kha´c, d¯oa.n tha˙ˇ’ng d¯u
.o.. c ve˜ khoˆng phu. thuoˆ.c va`o thu´
. tu.. ca´c d¯ieˆ˙’m d¯a`ˆu cuoˆ´i. Su
.
. sai kha´c
chı˙’ co´ theˆ˙’ xa˙’y ra ta. i nhu˜
.ng d¯ieˆ˙’m ve˜ ma` d¯u.`o.ng tha˙ˇ’ng d¯i qua d¯ieˆ˙’m giu˜.a va` bieˆ´n quyeˆ´t d¯i.nh
ba`ˇng khoˆng; trong tru.`o.ng ho.. p na`y, d¯i tu`
. tra´i sang pha˙’i chu´ng ta cho.n d¯ieˆ˙’m ve˜ R. Do t´ınh
d¯oˆ´i xu´.ng, khi d¯i tu`. pha˙’i sang tra´i va` d = 0 le˜ ra ta cho.n d¯ieˆ˙’m ve˜ R, nhu
.ng cho.n lu
.
. a na`y se˜
sai leˆ.ch moˆ.t d¯o
.n vi. theo tha`nh pha`ˆn y vo´
.i pixel d¯u.o.. c cho.n khi d¯i tu`
. tra´i sang pha˙’i. Do d¯o´
chu´ng ta ca`ˆn cho.n pixel D khi d¯i tu`
. pha˙’i sang tra´i trong tru.`o.ng ho.. p d = 0. Ly´ luaˆ.n tu
.o.ng
tu.. d¯oˆ´i vo´
.i ca´c d¯oa.n tha˙ˇ’ng co´ heˆ. soˆ´ go´c baˆ´t ky`.
Phu.o.ng pha´p hoa´n d¯oˆ˙’i ca´c d¯ieˆ˙’m d¯a`ˆu cuoˆ´i cu˙’a d¯oa.n tha˙ˇ’ng d¯eˆ˙’ thuaˆ. t toa´n xu
.’˙ ly´ theo
cu`ng hu.´o.ng khoˆng thu.. c hieˆ.n ch´ınh xa´c khi chu´ng ta ve˜ ca´c d¯oa.n tha˙ˇ’ng theo maˆ˜u toˆ. Ca´c
d¯oa.n tha˙ˇ’ng ve˜ theo maˆ˜u thu
.`o.ng “neo” nhu˜.ng daˆ´u hieˆ.u ta. i d¯ieˆ˙’m xuaˆ´t pha´t, co´ theˆ˙’ la` d¯ieˆ˙’m
du.´o.i beˆn tra´i, khoˆng phu. thuoˆ.c va`o hu
.´o.ng di chuyeˆ˙’n. D- aˇ.c bieˆ.t, vo´
.i maˆ˜u toˆ chaˆ´m-ga.ch,
cha˙ˇ’ng ha.n 111100, chu´ng ta muoˆ´n ve˜ maˆ˜u na`y ta. i d¯ieˆ˙’m xuaˆ´t pha´t ma` khoˆng tu
.
. d¯oˆ.ng d¯oˆ˙’i
tha`nh d¯ieˆ˙’m du.´o.i beˆn tra´i. Ngoa`i ra, neˆ´u thuaˆ. t toa´n luoˆn luoˆn d¯aˇ. t la. i ca´c d¯ieˆ˙’m d¯a`ˆu cuoˆ´i
theo thu´. tu.. ch´ınh taˇ´c, ta ca`ˆn di chuyeˆ˙’n tu`
. tra´i sang pha˙’i vo´.i d¯oa.n tha˙ˇ’ng AB va` tu`
. pha˙’i
sang tra´i vo´.i d¯oa.n tha˙ˇ’ng BA; d¯ie`ˆu na`y ta.o ra su
.
. gia´n d¯oa.n trong qua´ tr`ınh ve˜, cha˙ˇ’ng ha.n
d¯a gia´c, ta. i nhu˜
.ng d¯ı˙’nh chung.
D- ieˆ˙’m xuaˆ´t pha´t na`ˇm treˆn ca.nh cu˙’a d¯a gia´c caˇ´t. Moˆ.t vaˆ´n d¯e`ˆ kha´c chu´ng ta ca`ˆn
su.’˙ a d¯oˆ˙’i thuaˆ. t toa´n d¯eˆ˙’ ve˜ ca´c d¯oa.n tha˙ˇ’ng sau khi d¯u
.o.. c caˇ´t bo
.’˙ i moˆ. t trong ca´c thuaˆ. t toa´n
trong Pha`ˆn 3.3. Hı`nh 1.4(a) minh ho.a d¯oa.n tha˙ˇ’ng d¯u
.o.. c caˇ´t bo
.’˙ i ca.nh beˆn tra´i, x = xmin,
cu˙’a h`ınh chu˜. nhaˆ. t. Giao d¯ieˆ˙’m cu˙’a d¯oa.n tha˙ˇ’ng va` ca.nh beˆn tra´i co´ hoa`nh d¯oˆ. x nguyeˆn
nhu.ng tung d¯oˆ. y thu
.
. c. Pixel (xmin, bmxmin + t + 0.5c) treˆn ca.nh x = xmin ch´ınh la` pixel
d¯u.o.. c ve˜ ta. i hoa`nh d¯oˆ. xmin cu˙’a d¯oa.n tha˙ˇ’ng tru
.´o.c khi caˇ´t theo thuaˆ. t toa´n d¯ieˆ˙’m giu˜
.a2. Vo´.i
pixel kho.’˙ i ta.o d¯a˜ bieˆ´t, keˆ´ tieˆ´p chu´ng ta ca`ˆn kho
.’˙ i ta.o bieˆ´n quyeˆ´t d¯i.nh ta. i d¯ieˆ˙’m giu˜
.a d¯oa.n
RD trong coˆ. t keˆ´ beˆn. Ca`ˆn chu´ y´ ra`ˇng, ca´ch la`m na`y ta.o ra da˜y ch´ınh xa´c ca´c pixel, trong
2Khi mxmin + t na`ˇm giu˜.a hai d¯u.`o.ng tha˙ˇ’ng ngang ke`ˆ nhau, chu´ng ta ca`ˆn la`m tro`n xuoˆ´ng. D- aˆy la` heˆ. qua˙’
cu˙’a vieˆ.c cho.n pixel R khi d = 0.
18
................................................................................................................................................................................................................................................................................................................................................................................................................
x = xmin
y = ymin...
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
..
........................................................................................................................................................................................................................................................................
........................................................................................................................................................................................................................................................................
........................................................................................................................................................................................................................................................................
...........
...........
...........
...........
...........
......
...........
...........
...........
...........
...........
...........
..........
...........
...........
...........
...........
...........
...........
...........
...........
...........
...........
...........
...........
...........
...........
...........
. ......
...........
...........
...........
...........
...........
•
y i
R
iD
—M
(xmin, bmxmin + t+ 0.5c) ...................................................
(xmin,mxmin + t).........................................................
(a)
...............................................................................................................................................................................................................................................................................................................................................................................................................................................................................
..........................................................................................................................................................................................................................................................................................................................................................................................................................y = ymin − 1
........................................................................................................................................................................................................................................................................................................................................................................................................................
x = xmin
y = ymin
...............
................
................
...............
...............
................
..........
...............
...............
................
...............
...............
................
................
...............
...........
...............
................
................
...............
...............
................
...............
...............
...........
...............
................
...............
...............
................
...........
....
....
....
....
....
....
...
....
...
....
....
....
....
....
....
....
....
...
....
....
....
....
....
....
....
....
...
....
....
....
....
....
....
....
....
.
....
....
....
....
....
....
....
....
...
....
....
....
....
....
....
....
....
...
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
...
....
....
....
....
....
....
....
....
...
....
....
...
....
....
....
....
....
...
....
....
....
....
....
....
....
....
...
....
....
....
....
....
....
....
....
.
....
....
....
....
....
....
....
....
...
....
....
....
....
..
....
....
....
...
....
....
....
....
....
....
....
....
...
....
....
....
....
....
....
....
....
.
....
....
....
....
....
....
....
....
...
....
....
....
....
....
....
....
....
...
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
...
....
....
....
....
....
....
....
....
...
....
....
....
....
....
....
....
....
...
....
....
....
....
....
....
....
...
....
....
....
....
....
....
....
....
...
....
....
....
....
....
....
....
....
...
....
....
....
....
....
....
....
....
...
....
....
...
....
....
....
....
....
...
....
....
....
....
....
....
....
....
.
....
....
....
....
....
....
....
....
...
....
....
....
....
....
....
....
....
...
....
....
....
....
...
....
....
....
...
....
....
....
....
....
....
....
....
.
....
....
....
....
....
....
....
....
...
....
....
....
....
....
....
....
....
...
....
....
....
....
....
....
....
...
....
....
....
....
....
....
....
....
...
....
....
....
....
....
....
....
....
...
....
....
....
....
....
....
....
....
...
....
....
....
....
....
....
....
....
...
...
....
....
....
....
....
....
....
.
y y y yy y y y
i i i i y y y y i i i
y y y y
....... ....... ....... ....... ..... ....... ....... ..... ....... ....... ...... ....... . ....... ....... ....... ....... ....... ...... ....... ....... ..... ....... ....... ..... ....... ....... ..... ....... ....... ....... ....... .......y = ymin − 12 •I
D C
(b)
Hı`nh 1.4: D- ieˆ˙’m xuaˆ´t pha´t na`ˇm treˆn bieˆn h`ınh chu˜. nhaˆ. t. (a) Giao vo´
.i ca.nh d¯u´
.ng. (b) Giao
vo´.i ca.nh ngang.
19
khi caˇ´t d¯u.`o.ng tha˙ˇ’ng theo d¯u.`o.ng bieˆn xmin va` sau d¯o´ thu
.
. c hieˆ.n ve˜ d¯oa.n tha˙ˇ’ng d¯u
.o.. c caˇ´t tu`
.
(xmin, bmxmin + t+ 0.5c) d¯eˆ´n (xB, yB) theo thuaˆ. t toa´n d¯ieˆ˙’m giu˜.a se˜ cho da˜y d¯ieˆ˙’m ve˜ khoˆng
ch´ınh xa´c do d¯u.`o.ng tha˙ˇ’ng sau khi caˇ´t co´ heˆ. soˆ´ go´c kha´c m.
Tru.`o.ng ho.. p phu´
.c ta.p ho
.n khi d¯u.`o.ng tha˙ˇ’ng AB giao vo´.i d¯u.`o.ng tha˙ˇ’ng na`ˇm ngang nhu.
trong Hı`nh 1.4(b). Khi heˆ. soˆ´ go´c m raˆ´t nho˙’, co´ nhie`ˆu pixel naˇ`m treˆn do`ng que´t y = ymin
tu.o.ng u´.ng ca.nh beˆn du
.´o.i cu˙’a h`ınh chu˜. nhaˆ. t. Chu´ng ta muoˆ´n bao ha`m ca´c pixel na`y trong
h`ınh chu˜. nhaˆ. t, nhu
.ng do qua´ tr`ınh t´ınh toa´n giao d¯ieˆ˙’m vo´.i do`ng que´t y = ymin va` sau d¯o´
la`m tro`n hoa`nh d¯oˆ. x ta d¯u
.o.. c pixel C khoˆng pha˙’i pixel beˆn tra´i nhaˆ´t D treˆn do`ng na`y. Du
.
. a
treˆn h`ınh ve˜, ta thaˆ´y ra`ˇng pixel beˆn tra´i nhaˆ´t D la` pixel treˆn beˆn pha˙’i giao d¯ieˆ˙’m I cu˙’a d¯oa.n
tha˙ˇ’ng AB va` d¯u.`o.ng tha˙ˇ’ng y = ymin − 12 . Do d¯o´, ta chı˙’ ca`ˆn t`ım I va` la`m tro`n leˆn hoa`nh d¯oˆ. ;
pixel d¯a`ˆu tieˆn D ch´ınh la` (dxIe, ymin).
Cuoˆ´i cu`ng, thuaˆ. t toa´n d¯ieˆ˙’m giu˜
.a cu˜ng thu.. c hieˆ.n toˆ´t trong tru
.`o.ng ho.. p ca´c d¯ieˆ˙’m d¯a`ˆu
cuoˆ´i co´ to.a d¯oˆ. thu
.
. c; kha´c bieˆ.t duy nhaˆ´t la` bu
.´o.c taˇng va` ca´c phe´p toa´n thao ta´c treˆn soˆ´
thu.. c.
Thay d¯oˆ˙’i cu.`o.ng d¯oˆ. sa´ng cu˙’a d¯oa.n tha˙ˇ’ng theo heˆ. soˆ´ go´c. Xe´t hai d¯oa.n tha˙ˇ’ng trong
Hı`nh 1.5. D- oa.n tha˙ˇ’ng l2 co´ heˆ. soˆ´ go´c 1 va` do d¯o´ co´ d¯oˆ. da`i baˇ`ng
√
2 la`ˆn d¯oˆ. da`i cu˙’a l1. Chu´ng
ta d¯aˇ. t cu`ng soˆ´ (10) pixel treˆn moˆ˜i d¯oa.n tha˙ˇ’ng. Neˆ´u cu
.`o.ng d¯oˆ. cu˙’a moˆ˜i pixel la` I th`ı cu
.`o.ng
d¯oˆ. treˆn moˆ.t d¯o
.n vi. d¯oˆ. da`i cu˙’a d¯oa.n tha˙ˇ’ng l1 la` I, trong khi cu˙’a l2 la` I/
√
2; su.. khoˆng nhaˆ´t
qua´n na`y de˜ˆ da`ng pha´t hieˆ.n bo
.’˙ i ngu.`o.i quan sa´t. Treˆn ma`n h`ınh d¯o.n saˇ´c, khoˆng co´ ca´ch gia˙’i
quyeˆ´t, nhu.ng treˆn heˆ. thoˆ´ng n-bit treˆn pixel chu´ng ta co´ theˆ˙’ ca˙’i thieˆ.n d¯u
.o.. c t`ınh tra.ng na`y
ba`ˇng ca´ch d¯aˇ. t cu
.`o.ng d¯oˆ. la` moˆ. t ha`m cu˙’a heˆ. soˆ´ go´c. Ky˜ thuaˆ. t antialiasing cho keˆ´t qua˙’ toˆ´t
ho.n ba`ˇng ca´ch xem d¯oa.n tha˙ˇ’ng nhu
. moˆ.t h`ınh chu˜
. nhaˆ. t co´ d¯oˆ. roˆ.ng he.p va` t´ınh toa´n th´ıch
ho.. p ca´c cu
.`o.ng d¯oˆ. vo´
.i nhie`ˆu pixel treˆn moˆ˜i coˆ. t na`ˇm trong hoaˇ.c ga`ˆn h`ınh chu˜
. nhaˆ. t (xem [9],
[11]). Ngoa`i ra coi d¯oa.n tha˙ˇ’ng nhu
. h`ınh chu˜. nhaˆ. t cu˜ng cho phe´p ta.o ca´c d¯oa.n tha˙ˇ’ng vo´
.i d¯oˆ.
roˆ.ng tuy` y´.
Pha´c tha˙’o ca´c nguyeˆn so. xa´c d¯i.nh bo
.’˙ i ca´c d¯oa.n tha˙ˇ’ng. Vo´
.i ca´ch ve˜ ca´c d¯oa.n tha˙ˇ’ng,
chu´ng ta ca`ˆn ve˜ ca´c nguyeˆn so. d¯u.o.. c xaˆy du
.
. ng tu`
. ca´c d¯oa.n tha˙ˇ’ng nhu
. theˆ´ na`o? Ca´c d¯u.`o.ng
gaˆ´p khu´c co´ theˆ˙’ d¯u.o.. c ve˜ ba`ˇng ca´ch xem no´ nhu
. ca´c d¯oa.n tha˙ˇ’ng ke`ˆ nhau. Ca´c h`ınh chu˜
.
nhaˆ. t va` d¯a gia´c la` nhu˜
.ng nguyeˆn so. vu`ng va` co´ theˆ˙’ ve˜ ca´c ca.nh lieˆn tieˆ´p nhu
.ng d¯ie`ˆu na`y
daˆ˜n d¯eˆ´n moˆ.t soˆ´ pixel na`ˇm ngoa`i vu`ng d¯i.nh ngh˜ıa bo
.’˙ i nguyeˆn so.-xem ca´c Pha`ˆn 4.6 va` 4.7
ve`ˆ nhu˜.ng thuaˆ. t toa´n xu
.’˙ ly´ vaˆ´n d¯e`ˆ na`y. Chu´ y´ raˇ`ng ca`ˆn ve˜ ca´c d¯ı˙’nh chung cu˙’a d¯u.`o.ng gaˆ´p
khu´c moˆ.t la`ˆn do vieˆ.c ve˜ hai la`ˆn co´ theˆ˙’ la`m thay d¯oˆ˙’i ma`u hoaˇ.c d¯aˇ. t ma`u ne`ˆn khi vieˆ´t trong
cheˆ´ d¯oˆ. XOR treˆn ma`n h`ınh, hoaˇ.c taˇng cu
.`o.ng d¯oˆ. gaˆ´p d¯oˆi ta. i d¯o´. Thaˆ. t ra co´ nhu˜
.ng pixel
kha´c la` chung cu˙’a hai d¯oa.n tha˙ˇ’ng na`ˇm ga`ˆn nhau hoaˇ.c caˇ´t nhau.
20
.......................................................................................................................................................................................
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
.........
............................................................................................................................
..............................................................................................................................................................................
..............................................................................................................................................................................
..............................................................................................................................................................................
..............................................................................................................................................................................
..............................................................................................................................................................................
..............................................................................................................................................................................
....
....
...
....
....
...
....
....
...
....
....
...
....
....
...
....
....
...
....
....
...
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
..
....
....
...
....
....
...
....
....
...
....
....
...
....
....
...
....
....
...
....
....
...
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
..
....
....
...
....
....
...
....
....
...
....
....
...
....
....
...
....
....
...
....
....
...
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
..
....
....
...
....
....
...
....
....
...
....
....
...
....
....
...
....
....
...
....
....
...
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
..
....
....
...
....
....
...
....
....
...
....
....
...
....
....
...
....
....
...
....
....
...
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
..
....
....
...
....
....
...
....
....
...
....
....
...
....
....
...
....
....
...
....
....
...
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
..
....
....
...
....
....
...
....
....
...
....
....
...
....
....
...
....
....
...
....
....
...
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
..
....
....
...
....
....
...
....
....
...
....
....
...
....
....
...
....
....
...
....
....
...
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
..
....
....
..
....
....
..
....
....
..
....
....
...
....
....
...
....
....
...
....
....
..
....
....
....
....
....
...
yyy
yyy
yyy
yD- u.`o.ng tha˙ˇ’ng l2
yyyyyyyyyyD- u.`o.ng tha˙ˇ’ng l1
Hı`nh 1.5: Thay d¯oˆ˙’i cu.`o.ng d¯oˆ. cu˙’a ca´c d¯u
.`o.ng tha˙ˇ’ng theo heˆ. soˆ´ go´c.
1.1.4 Ca´c thuoˆ.c t´ınh cu˙’a d¯oa.n tha˙ˇ’ng
Thuoˆ.c t´ınh maˆ˜u toˆ d¯oa.n tha˙ˇ’ng co´ theˆ˙’ a˙’nh hu
.o.’˙ ng d¯eˆ´n nhu˜.ng nguyeˆn so. kha´c. No´i chung
ta ca`ˆn su.’˙ du.ng d¯ie`ˆu kieˆ.n logic d¯eˆ˙’ kieˆ˙’m tra co´ d¯aˇ. t d¯ieˆ˙’m ve˜ hay khoˆng, chı˙’ d¯aˇ. t khi d¯ie`ˆu kieˆ.n
d¯u´ng (gia´ tri. 1). Chu´ng ta lu
.u tru˜. maˆ˜u ve˜ nhu. moˆ.t chuoˆ˜i d¯oˆ. da`i Tile Size (thu
.`o.ng la` lu˜y
thu`.a cu˙’a 2: No´i chung Tile Size = 16) la` maˆ˜u co´ kieˆ˙’u Bool (cha˙ˇ’ng ha.n, 16 bit nguyeˆn);
do d¯o´ maˆ˜u toˆ d¯u.o.. c laˇ.p la. i sau khi ve˜ 16 pixel. Chu´ng ta thay do`ng leˆ.nh khoˆng d¯ie`ˆu kieˆ.n
putpixel() trong thuaˆ. t toa´n ve˜ d¯oa.n tha˙ˇ’ng d¯eˆ˙’ xu
.’˙ ly´ tru.`o.ng ho.. p na`y; cha˙ˇ’ng ha.n,
if bitstring[i % 16] putpixel(x, y, value);
trong d¯o´ chı˙’ soˆ´ i la` moˆ. t bieˆ´n taˇng mo´
.i trong vo`ng laˇ.p beˆn trong cu˙’a thuaˆ. t toa´n. Tuy nhieˆn,
ca´ch la`m na`y co´ moˆ. t ha.n cheˆ´ la` do moˆ˜i bit trong maˇ.t na. tu
.o.ng u´.ng moˆ.t la`ˆn laˇ.p va` khoˆng
tu.o.ng u´.ng d¯oˆ. da`i d¯o
.n vi. do.c theo d¯oa.n tha˙ˇ’ng neˆn d¯oˆ. da`i cu˙’a ne´t ve˜ thay d¯oˆ˙’i theo heˆ. soˆ´
go´c cu˙’a d¯oa.n tha˙ˇ’ng; ne´t ve˜ cu˙’a d¯oa.n tha˙ˇ’ng xieˆn se˜ da`i ho
.n ne´t ve˜ cu˙’a d¯oa.n tha˙ˇ’ng ngang
hay d¯u´.ng. D- ie`ˆu na`y la` khoˆng chaˆ´p nhaˆ.n d¯u
.o.. c vo´
.i nhu˜.ng u´.ng du.ng mang t´ınh ch´ınh xa´c
cao, cha˙ˇ’ng ha.n trong thieˆ´t keˆ´ coˆng nghieˆ.p, va` do d¯o´ ca´c ne´t ve˜ ca`ˆn t´ınh la. i sao cho phu
.o.ng
pha´p ve˜ d¯oa.n tha˙ˇ’ng khoˆng phu. thuoˆ.c va`o heˆ. soˆ´ go´c cu˙’a no´. D- oˆ. roˆ.ng cu˙’a d¯oa.n tha˙ˇ’ng d¯u
.o.. c
xem nhu. moˆ.t da˜y ca´c h`ınh chu˜
. nhaˆ. t d¯aˇ. c va` trong suoˆ´t d¯u
.o.. c d¯aˇ. t xen ke˜ nhau ma` ca´c d¯ı˙’nh
cu˙’a no´ d¯u.o.. c t´ınh ch´ınh xa´c theo ha`m phu. thuoˆ.c kieˆ˙’u ve˜ d¯oa.n tha˙ˇ’ng. Sau d¯o´ thu
.
. c hieˆ.n toˆ
ma`u treˆn tu`.ng h`ınh chu˜. nhaˆ. t moˆ. t; vo´
.i ca´c d¯oa.n tha˙ˇ’ng ngang hoaˇ.c d¯u´
.ng, ta co´ theˆ˙’ du`ng
leˆ.nh sao che´p ca´c h`ınh chu˜
. nhaˆ. t.
Kieˆ˙’u d¯oa.n tha˙ˇ’ng va` kieˆ˙’u bu´t ve˜ co´ a˙’nh hu
.o.’˙ ng laˆ˜n nhau trong ca´c nguyeˆn so. lieˆn quan
d¯eˆ´n d¯oˆ. roˆ.ng d¯u
.`o.ng bieˆn. Kieˆ˙’u d¯oa.n tha˙ˇ’ng thu
.`o.ng d¯u.o.. c su
.’˙ du.ng d¯eˆ˙’ xa´c d¯i.nh ca´c h`ınh chu˜
.
nhaˆ. t tu
.o.ng u´.ng ca´c ne´t ve˜ va` moˆ˜i h`ınh chu˜. nhaˆ. t d¯u
.o.. c toˆ ma`u vo´
.i maˆ˜u bu´t d¯u.o.. c cho.n.
21
1.2 D- u.`o.ng tro`n
Xe´t d¯u.`o.ng tro`n f(x, y) := x2+y2−R2 = 0. Co´ moˆ.t va`i ca´ch d¯o.n gia˙’n ve˜ d¯u.`o.ng tro`n nhu.ng
khoˆng hieˆ.u qua˙’.
D- eˆ˙’ ve˜ moˆ. t pha`ˆn tu
. d¯u.`o.ng tro`n trong go´c pha`ˆn tu. thu´. nhaˆ´t
{(x, y) ∈ R2 | x ≥ 0, y ≥ 0}
(ca´c cung kha´c d¯u.o.. c ve˜ do t´ınh d¯oˆ´i xu´
.ng) ta co´ theˆ˙’ taˇng x tu`. 0 d¯eˆ´n R (moˆ˜i bu.´o.c moˆ.t d¯o
.n
vi.) va` gia˙’i y =
√
R2 − x2. Phu.o.ng pha´p na`y khoˆng hieˆ.u qua˙’ do su.’˙ du.ng phe´p nhaˆn va` laˆ´y
caˇn baˆ.c hai. Ngoa`i ra co´ nhu˜
.ng loˆ˜ hoˆ˙’ng khi gia´ tri. x ga`ˆn vo´
.i R v`ı tieˆ´p tuyeˆ´n vo´.i d¯u.`o.ng tro`n
ta. i nhu˜
.ng d¯ieˆ˙’m tu.o.ng u´.ng tieˆ´n d¯eˆ´n d¯u.`o.ng tha˙ˇ’ng song song vo´.i tru. c tung. Phu
.o.ng pha´p
kha´c tu.o.ng tu.. , cu˜ng khoˆng hieˆ.u qua˙’, tra´nh nhu˜
.ng loˆ˜ hoˆ˙’ng la` ve˜ ca´c d¯ieˆ˙’m (R cos θ,R sin θ)
vo´.i θ thay d¯oˆ˙’i tu`. 0 d¯eˆ´n 900.
1.2.1 D- oˆ´i xu´.ng ta´m d¯ieˆ˙’m
Chu´ng ta co´ theˆ˙’ gia˙’m bo´.t qua´ tr`ınh t´ınh toa´n du.. a treˆn t´ınh d¯oˆ´i xu´
.ng cu˙’a d¯u.`o.ng tro`n qua
ca´c tru. c ch´ınh. Chı˙’ ca`ˆn xe´t d¯u
.`o.ng tro`n taˆm ta. i goˆ´c v`ı neˆ´u khoˆng ta thu
.
. c hieˆ.n phe´p ti.nh
tieˆ´n tu`. taˆm ve`ˆ goˆ´c to.a d¯oˆ. . Neˆ´u d¯ieˆ˙’m (x, y) na`ˇm treˆn d¯u
.`o.ng tro`n th`ı ba˙’y d¯ieˆ˙’m
(x,−y), (y, x), (y,−x), (−x,−y), (−y,−x), (−y, x), (−x, y)
cu˜ng na`ˇm treˆn d¯u.`o.ng tro`n.
Do d¯o´ ta chı˙’ ca`ˆn ve˜ moˆ. t cung 45
0 va` tu`. d¯o´ sinh ra d¯u.`o.ng tro`n. Vo´.i d¯u.`o.ng tro`n taˆm
ta. i goˆ´c, ta´m d¯ieˆ˙’m d¯oˆ´i xu´
.ng co´ theˆ˙’ d¯u.o.. c hieˆ˙’n thi. ba`ˇng thu˙’ tu. c sau (ma` de˜ˆ da`ng toˆ˙’ng qua´t
hoa´ vo´.i ca´c d¯u.`o.ng tro`n taˆm tuy` y´):
void CirclePoints(int x, int y, int Value)
{
putpixel(x, y, Value);
putpixel(y, x, Value);
putpixel(y, -x, Value);
putpixel(x, -y, Value);
putpixel(-x, -y, Value);
putpixel(-y, -x, Value);
22
putpixel(-y, x, Value);
putpixel(-x, y, Value);
}
Ca`ˆn chu´ y´ raˇ`ng khoˆng neˆn go. i thu˙’ tu. c CirclePoints() khi x = y do co´ boˆ´n pixel d¯u
.o.. c
ve˜ hai la`ˆn; ta chı˙’ ca`ˆn thay d¯oˆ˙’i d¯oa.n ma˜ xu
.’˙ ly´ d¯ie`ˆu kieˆ.n bieˆn.
1.2.2 Thuaˆ.t toa´n d¯ieˆ˙’m giu˜
.a ve˜ d¯u.`o.ng tro`n
Bresenham [3] d¯a˜ tr`ınh ba`y moˆ.t phu
.o.ng pha´p ve˜ d¯u.`o.ng tro`n hieˆ.u qua˙’ ho
.n ca´ch d¯u.a ra o.’˙
treˆn. Chu´ng ta neˆu thuaˆ. t toa´n tu
.o.ng tu.. , su
.’˙ du.ng tieˆu chuaˆ˙’n d¯ieˆ˙’m giu˜
.a, ma` trong tru.`o.ng
ho.. p ba´n k´ınh va` ca´c to.a d¯oˆ. cu˙’a taˆm la` nhu˜
.ng soˆ´ nguyeˆn se˜ cho cu`ng moˆ.t keˆ´t qua˙’ ca´c pixel
toˆ´t nhaˆ´t.
Ta chı˙’ ca`ˆn xe´t cung moˆ.t pha`ˆn ta´m d¯u
.`o.ng tro`n:
(C1) := {(x, y) ∈ R2 | x2 + y2 = R2, 0 ≤ y < x}
va` su.’˙ du.ng thu˙’ tu. c CirclePoints() d¯eˆ˙’ hieˆ˙’n thi. ca´c pixel treˆn toa`n d¯u
.`o.ng tro`n. Vi phaˆn
phu.o.ng tr`ınh f(x, y) := x2 + y2 − r2 = 0 ta d¯u.o.. c 2xdx + 2ydy = 0. Neˆn dxdy = − yx . Suy ra
−1 < dx
dy
≤ 0 vo´.i mo. i (x, y) ∈ (C1). Do d¯o´, khi y taˇng moˆ.t d¯o.n vi. th`ı x gia˙’m khoˆng qua´
moˆ.t d¯o
.n vi.. Vı` vaˆ.y, gia˙’ su
.’˙ o.’˙ bu.´o.c thu´. i chu´ng ta cho.n d¯u
.o.. c d¯ieˆ˙’m ve˜ toˆ´t nhaˆ´t C := (xi, yi),
th`ı bu.´o.c keˆ´ tieˆ´p ca`ˆn cho.n moˆ.t trong hai pixel T := (xi, yi + 1) hoaˇ.c D := (xi − 1, yi + 1)
(xem Hı`nh 1.6). Tu.o.ng tu.. thuaˆ. t toa´n d¯ieˆ˙’m giu˜
.a ve˜ d¯u.`o.ng tha˙ˇ’ng, d¯eˆ˙’ cho.n moˆ.t trong hai
pixel ga`ˆn vo´.i d¯u.`o.ng tro`n ho.n ta xe´t ha`m laˆ´y gia´ tri. ta. i d¯ieˆ˙’m giu˜
.a M = (xi − 12 , yi + 1) cu˙’a
hai d¯ieˆ˙’m ve˜ na`y. De˜ˆ da`ng chu´.ng minh raˇ`ng, neˆ´u d¯ieˆ˙’m M na`ˇm trong d¯u.`o.ng tro`n (tu.o.ng
d¯u.o.ng f(M) < 0) th`ı T ga`ˆn d¯u.`o.ng tro`n ho.n; va` M naˇ`m ngoa`i d¯u.`o.ng tro`n (tu.o.ng d¯u.o.ng
f(M) > 0) th`ı D ga`ˆn d¯u.`o.ng tro`n ho.n. Tru.`o.ng ho.. p M na`ˇm treˆn d¯u
.`o.ng tro`n (tu´.c f(M) = 0)
ta co´ theˆ˙’ cho.n moˆ.t trong hai, do d¯o´ cho.n pixel D.
D- aˇ. t
di := f(M) = f(xi − 1
2
, yi + 1) = (xi − 1
2
)2 + (yi + 1)
2 −R2.
Neˆ´u di < 0 th`ı cho.n T va` d¯ieˆ˙’m giu˜
.a keˆ´ tieˆ´p co´ tung d¯oˆ. taˇng moˆ.t d¯o
.n vi.. Neˆn
di+1 = f(xi − 1
2
, yi + 2) = (xi − 1
2
)2 + (yi + 2)
2 −R2;
va` do d¯o´ di+1 = di + (2yi + 3); suy ra bu
.´o.c taˇng ∆T := 2yi + 3.
23
.............
M
.....
.....
.....
.....
....
....
....
....
....
....
....
....
.....
.....
......
........
.........
..........
...........
...
Dw
C
w
Tw
Hı`nh 1.6: Lu.´o.i pixel trong thuaˆ. t toa´n d¯ieˆ˙’m giu˜
.a ve˜ d¯u.`o.ng tro`n.
Neˆ´u di ≥ 0 th`ı cho.n D va` d¯ieˆ˙’m giu˜.a keˆ´ tieˆ´p co´ hoa`nh d¯oˆ. gia˙’m moˆ.t d¯o.n vi. va` tung d¯oˆ.
taˇng moˆ.t d¯o
.n vi.. Neˆn
di+1 = f(xi − 3
2
, yi + 2) = (xi − 3
2
)2 + (yi + 2)
2 −R2.
Suy ra di+1 = di + 2yi − 2xi + 5. Do d¯o´ bu.´o.c taˇng ∆D := 2(yi − xi) + 5.
Nhaˇ´c la. i la`, trong tru
.`o.ng ho.. p d¯u
.`o.ng tha˙ˇ’ng, ca´c bu.´o.c taˇng ∆R va` ∆D la` ca´c ha`ˇng soˆ´;
tuy nhieˆn, trong tru.`o.ng ho.. p d¯u
.`o.ng cong baˆ.c hai, ∆T va` ∆D la` ca´c ha`m phu. thuoˆ.c va`o ca´c
to.a d¯oˆ. cu˙’a d¯ieˆ˙’m ve˜ hieˆ.n ha`nh (xi, yi). Ca´c ha`m na`y co´ theˆ˙’ t´ınh toa´n tru
.
. c tieˆ´p ta. i moˆ˜i bu
.´o.c
laˇ.p du
.
. a va`o ca´c gia´ tri. x va` y cu˙’a pixel d¯u
.o.. c cho.n trong bu
.´o.c laˇ.p tru
.´o.c. T´ınh toa´n nhu.
vaˆ.y khoˆng hieˆ.u qua˙’ do ca´c ha`m na`y la` tuyeˆ´n t´ınh (xem Nhaˆ.n xe´t 1.2.1).
Cuoˆ´i cu`ng ca`ˆn t´ınh d0. Vo´
.i gia˙’ thieˆ´t ba´n k´ınh nguyeˆn, ta bieˆ´t ra`ˇng pixel kho.’˙ i ta.o
ban d¯a`ˆu co´ to.a d¯oˆ. (R, 0) neˆn d¯ieˆ˙’m giu˜
.a co´ to.a d¯oˆ. (R − 12 , 1) va` do d¯o´ d0 = f(R − 12 , 1) =
(R− 1
2
)2 + 1−R2 = 5
4
−R. Toˆ˙’ng keˆ´t ta co´ thuaˆ. t toa´n ve˜ d¯u.`o.ng tro`n taˆm ta. i goˆ´c to.a d¯oˆ. va`
ba´n k´ınh R nhu. sau:
1. [Kho.’˙ i ta.o] D- aˇ. t x0 = R, y0 = 0, d0 = 5/4−R.
2. Gia˙’ su.’˙ o.’˙ bu.´o.c thu´. i ta co´ d¯ieˆ˙’m ve˜ toˆ´t nhaˆ´t (xi, yi) va` bieˆ´n quyeˆ´t d¯i.nh di.
3. [Ve˜ pixel hieˆ.n ha`nh] D- aˇ. t ta´m d¯ieˆ˙’m ve˜ du
.
. a treˆn (xi, yi).
24
4. [Caˆ.p nhaˆ. t] Neˆ´u xi = yi, thuaˆ. t toa´n du`
.ng; ngu.o.. c la. i, d¯aˇ. t
xi+1 =
{
xi neˆ´u di < 0,
xi − 1 neˆ´u ngu.o.. c la. i;
yi+1 = yi + 1;
di+1 =
{
di + 2yi + 3 neˆ´u di < 0,
di + 2(yi − xi) + 5 neˆ´u ngu.o.. c la. i.
5. Thay i ba`ˇng (i+ 1) va` laˇ.p la. i Bu
.´o.c 3.
Nhaˆ.n xe´t 1.2.1 (i) Vaˆ´n d¯e`ˆ vo´
.i thuaˆ. t toa´n vu`
.a tr`ınh ba`y, ta la`m vieˆ.c treˆn ca´c soˆ´ thu
.
. c v`ı
kho.’˙ i ta.o bieˆ´n quyeˆ´t d¯i.nh la` soˆ´ thu
.
. c. Maˇ.c du` co´ theˆ˙’ de˜ˆ da`ng ca˙’i tieˆ´n d¯eˆ˙’ xu
.’˙ ly´ cho d¯u.`o.ng
tro`n co´ taˆm hoaˇ.c ba´n k´ınh khoˆng nguyeˆn, ta se˜ tr`ınh ba`y ca´ch t´ınh toa´n soˆ´ nguyeˆn hieˆ.u qua˙’
ho.n. No´i ca´ch kha´c ta se˜ khu.’˙ ca´c maˆ˜u soˆ´ trong chu.o.ng tr`ınh.
D- a`ˆu tieˆn, xe´t bieˆ´n mo´.i hi = di − 14 va` thay di bo.’˙ i hi + 14 trong thuaˆ. t toa´n. Khi d¯o´ ta
kho.’˙ i ta.o h0 = 1− R va` so sa´nh di < 0 tu.o.ng d¯u.o.ng hi < −14 . Tuy nhieˆn, do h0 nguyeˆn va`
d¯u.o.. c taˇng bo
.’˙ i ca´c gia´ tri. nguyeˆn (∆T va` ∆D) neˆn chı˙’ ca`ˆn so sa´nh hi < 0. Nhu
. vaˆ.y, chu´ng
ta co´ thuaˆ. t toa´n ve˜ d¯u
.`o.ng tro`n chı˙’ su.’˙ du.ng ca´c soˆ´ nguyeˆn nhu
. du.´o.i d¯aˆy; d¯eˆ˙’ nhaˆ´t qua´n vo´.i
thuaˆ. t toa´n ve˜ d¯oa.n tha˙ˇ’ng, ta thay h la` d.
void MidPointCircle(int R, int Value)
{
int x, y, d;
x = R;
y = 0;
d = 1 - R;
CirclePoints(x, y, Value);
while (y < x)
{
if (d < 0)
{
d += 2*y + 3;
y++;
}
else
{
25
d += 2*(y - x) + 5;
x-- ;
y++;
}
CirclePoints(x, y, Value);
}
}
(ii) Chu´ng ta co`n co´ theˆ˙’ ca˙’i tieˆ´n toˆ´t ho.n thuaˆ. t toa´n d¯ieˆ˙’m giu˜
.a ve˜ d¯u.`o.ng tro`n nhu. sau. Chu´
y´ ra`ˇng ca´c ha`m ∆ la` phu.o.ng tr`ınh tuyeˆ´n t´ınh va` co´ theˆ˙’ t´ınh tru.. c tieˆ´p. Tuy nhieˆn du`ng
phu.o.ng pha´p sai phaˆn baˆ. c moˆ. t-hai d¯eˆ˙’ xa´c d¯i.nh chu´ng hieˆ.u qua˙’ ho
.n: u.´o.c lu.o.. ng ha`m ta. i
hai d¯ieˆ˙’m ve˜ ke`ˆ nhau, t´ınh hieˆ.u (trong tru
.`o.ng ho.. p d¯a thu´
.c, luoˆn luoˆn cho d¯a thu´.c baˆ.c thaˆ´p
ho.n) va` a´p du.ng hieˆ.u trong moˆ˜i bu
.´o.c laˇ.p.
Neˆ´u cho.n T trong bu
.´o.c laˇ.p keˆ´ tieˆ´p th`ı d¯ieˆ˙’m hieˆ.n ha`nh se˜ di chuyeˆ˙’n tu`
. (xi, yi) d¯eˆ´n
(xi, yi + 1). Ta bieˆ´t raˇ`ng, sai phaˆn baˆ.c moˆ.t ∆T ta. i (xi, yi) ba`ˇng 2yi + 3. Do d¯o´ ∆T ta. i
(xi, yi + 1) ba`ˇng 2(yi + 1) + 3. Suy ra sai phaˆn baˆ.c hai ∆T,i+1 −∆T,i = 2. Tu.o.ng tu.. , ∆D ta. i
(xi, yi) baˇ`ng 2(yi−xi)+ 5. Do d¯o´ ∆D ta. i (xi, yi +1) ba`ˇng 2(yi +1−xi)+ 5. Suy ra sai phaˆn
baˆ.c hai ∆D,i+1 −∆D,i = 2.
Neˆ´u cho.n D trong bu
.´o.c laˇ.p keˆ´ tieˆ´p th`ı d¯ieˆ˙’m hieˆ.n ha`nh di chuyeˆ˙’n tu`
. (xi, yi) d¯eˆ´n
(xi−1, yi+1). Do d¯o´ ∆T ta. i (xi, yi) ba`ˇng 2(yi+1)+3, va` sai phaˆn baˆ.c hai ∆T,i+1−∆T,i = 2.
Tu.o.ng tu.. , ∆D ta. i (xi − 1, yi + 1) ba`ˇng 2[(yi + 1) − (xi − 1)] + 5. Suy ra sai phaˆn baˆ.c hai
∆D,i+1 −∆D,i = 4.
Vaˆ.y thuaˆ. t toa´n ca˙’i bieˆn go`ˆm ca´c bu
.´o.c: (1) cho.n pixel du
.
. a treˆn daˆ´u cu˙’a bieˆ´n quyeˆ´t
d¯i.nh di d¯u
.o.. c xa´c d¯i.nh trong bu
.´o.c laˇ.p tru
.´o.c; (2) caˆ.p nhaˆ. t bieˆ´n quyeˆ´t d¯i.nh di theo ∆T hoaˇ.c
∆D; (3) caˆ.p nhaˆ. t ca´c ha`m ∆; va` (4) di chuyeˆ˙’n d¯eˆ´n pixel keˆ´ tieˆ´p. ∆T va` ∆D d¯u
.o.. c kho
.’˙ i ta.o
du.. a treˆn pixel ban d¯a`ˆu (R, 0).
Vı´ du. 1.2.2 Gia˙’ su
.’˙ d¯u.`o.ng tro`n co´ taˆm O(0, 0) ba´n k´ınh R = 20. Ta co´
x0 = R = 20,
y0 = 0,
d0 = 1−R = −19,
∆T,0 = 3,
∆D,0 = −2R + 5 = −35.
A´p du.ng thuaˆ. t toa´n d¯ieˆ˙’m giu˜
.a ve˜ d¯u.`o.ng tro`n ta d¯u.o.. c da˜y ca´c d¯ieˆ˙’m ve˜ toˆ´t nhaˆ´t (treˆn cung
26
moˆ.t pha`ˆn ta´m trong go´c pha`ˆn tu
. thu´. nhaˆ´t) nhu. trong ba˙’ng du.´o.i:
i xi yi di ∆T,i ∆D,i
0 20 0 −19 3 −35
1 20 1 −16 5 −33
2 20 2 −11 7 −31
3 20 3 −4 9 −29
4 20 4 5 11 −27
5 19 5 −22 13 −23
6 19 6 −9 15 −21
7 19 7 6 17 −19
8 18 8 −13 19 −15
9 18 9 6 21 −13
10 17 10 −7 23 −9
11 17 11 16 25 −7
12 16 12 9 27 −3
13 15 13 6 29 1
14 14 14 7 31 5
Thu˙’ tu. c ve˜ d¯u
.`o.ng tro`n theo phu.o.ng pha´p sai phaˆn baˆ.c hai nhu
. sau:
void MidPointCircle(int R, int Value)
{
int x, y, d, DeltaT, DeltaD;
x = R;
y = 0;
d = 1 - R;
DeltaT = 3;
DeltaD = -2*R + 5;
CirclePoints(x, y, Value);
while (y < x)
{
if (d < 0)
{
d += DeltaT;
DeltaT += 2;
27
DeltaD += 2;
y++;
}
else
{
d += DeltaD;
DeltaT += 2;
DeltaD += 4;
x--;
y++;
}
CirclePoints(x, y, Value);
}
}
1.3 D- u.`o.ng cong ellipse
Ca´c d¯u.`o.ng cong conic d¯u.o.. c nghieˆn cu´
.u tu`. raˆ´t laˆu. Co´ theˆ˙’ xem no´ nhu. giao cu˙’a moˆ.t maˇ.t
pha˙ˇ’ng vo´.i moˆ. t maˇ. t no´n. No´ cu˜ng co´ theˆ˙’ d¯u
.o.. c xa´c d¯i.nh nhu
. taˆ.p ca´c d¯ieˆ˙’m na`o d¯o´, cha˙ˇ’ng
ha.n d¯u
.`o.ng tro`n, ma` khoa˙’ng ca´ch d¯eˆ´n moˆ.t d¯ieˆ˙’m khoˆng d¯oˆ˙’i. Trong h`ınh ho.c gia˙’i t´ıch, ca´c
conic d¯u.o.. c xem nhu
. ca´c taˆ.p con cu˙’a R
2 : Chu´ng ta d¯i.nh ngh˜ıa moˆ.t conic nhu
. taˆ.p ho
.
. p ca´c
d¯ieˆ˙’m (x, y) ∈ R2 thoa˙’ ma˜n phu.o.ng tr`ınh
Ax2 +Bxy + Cy2 +Dx+ Ey + F = 0.
vo´.i ca´c soˆ´ thu.. c A,B,C,D,E, F na`o d¯o´. Vieˆ.c phaˆn loa. i conic (trong tru
.`o.ng ho.. p kha´c troˆ´ng)
la` hyperbol, ellipse hay la` parabol phu. thuoˆ.c va`o daˆ´u cu˙’a bieˆ.t thu´
.c
δ := B2 − 4AC
du.o.ng, aˆm, hay baˇ`ng khoˆng (xem [12]).
Maˇ.t kha´c, ellipse la` moˆ. t trong nhu˜
.ng nguyeˆn so. cu˙’a d¯o`ˆ ho.a ma´y t´ınh thu
.`o.ng xuyeˆn
d¯u.o.. c su
.’˙ du.ng trong ca´c u´
.ng du.ng d¯o`ˆ ho.a. Do d¯o´ co´ raˆ´t nhie`ˆu nghieˆn cu´
.u nha`ˇm d¯u.a ra
nhu˜.ng thuaˆ. t toa´n hu˜
.u hieˆ.u d¯eˆ˙’ ve˜ ca´c ellipse treˆn ca´c thieˆ´t bi. hieˆ˙’n thi. raster (xem [26], [16],
[17], [28]).
Thuaˆ. t toa´n d¯ieˆ˙’m giu˜
.a ve˜ d¯u.`o.ng tha˙ˇ’ng va` d¯u.`o.ng tro`n cu˜ng co´ theˆ˙’ a´p du.ng d¯eˆ˙’ ve˜ ca´c
d¯u.`o.ng cong conic toˆ˙’ng qua´t. Mu. c d¯ı´ch cu˙’a pha`ˆn na`y la`:
28
1. Ve˜ ellipse “ch´ınh taˇ´c” vo´.i taˆm ta. i goˆ´c to.a d¯oˆ. (0, 0) cho bo
.’˙ i phu.o.ng tr`ınh
b2x2 + a2y2 − a2b2 = 0
trong d¯o´ 2a la` d¯oˆ. da`i tru. c ch´ınh Ox va` 2b la` d¯oˆ. da`i tru. c phu. Oy.
2. Ve˜ ellipse trong tru.`o.ng ho.. p baˆ´t ky`.
1.3.1 Ellipse co´ da.ng ch´ınh taˇ´c
D- eˆ˙’ d¯o.n gia˙’n, do t´ınh d¯oˆ´i xu´.ng, chu´ng ta chı˙’ ca`ˆn ve˜ ellipse na`ˇm trong go´c pha`ˆn tu. thu´. nhaˆ´t:
(EI) := {(x, y) ∈ R2 | f(x, y) := b2x2 + a2y2 − a2b2 = 0, x ≥ 0, y ≥ 0}.
Cu˜ng chu´ y´ raˇ`ng, ca´c ellipse ch´ınh taˇ´c taˆm ta. i to.a d¯oˆ. nguyeˆn co´ theˆ˙’ d¯u
.a ve`ˆ taˆm ta. i goˆ´c to.a
d¯oˆ. ba`ˇng phe´p ti.nh tieˆ´n. Thuaˆ. t toa´n tr`ınh ba`y o
.’˙ d¯aˆy cu˙’a Da Silva [6] la` su.. toˆ˙’ng ho
.
. p ca´c
phu.o.ng pha´p cu˙’a Pitteway [16], Van Aken [26] va` Kappel [10].
Phaˆn t´ıch
Y´ tu.o.’˙ ng cu˙’a ca´c phu.o.ng pha´p d¯u.o.. c tr`ınh ba`y trong pha`ˆn sau la` xuaˆ´t pha´t tu`
. pixel (x0, y0)
na`o d¯o´ treˆn cung (EI) chu´ng ta xaˆy du
.
. ng moˆ.t da˜y ca´c pixel “toˆ´t nhaˆ´t” (xn, yn). Kha´i nieˆ.m
toˆ´t nhaˆ´t o.’˙ d¯aˆy d¯u.o.. c hieˆ˙’u la` cho.n da˜y ca´c pixel (xn, yn) ga`ˆn vo´
.i d¯u.`o.ng cong thu.. c teˆ´ (o
.’˙ da.ng
lieˆn tu. c) nhaˆ´t.
Treˆn cung (EI) ta chia la`m hai vu`ng (E
1
I ) va` (E
2
I ). Bieˆn giu˜
.a hai vu`ng xa´c d¯i.nh bo
.’˙ i
d¯ieˆ˙’m treˆn ellipse ma` tieˆ´p tuyeˆ´n vo´.i d¯u.`o.ng cong ta. i d¯o´ co´ heˆ. soˆ´ go´c ba`ˇng −1 (Hı`nh 1.7);
tu´.c la` ta. i d¯ieˆ˙’m ma` ca´c tha`nh pha`ˆn cu˙’a vector gradient ∇f(x, y) := (∂f∂x , ∂f∂y )t co´ d¯oˆ. lo´.n baˇ`ng
nhau. Tha`nh pha`ˆn ∂f
∂y
nho˙’ ho.n tha`nh pha`ˆn ∂f
∂x
trong vu`ng thu´. nhaˆ´t va` ngu.o.. c la. i trong vu`ng
thu´. hai. Ch´ınh xa´c la`
(E1I ) := {(x, y) ∈ (EI) |
df
dy
≤ df
dx
}.
va`
(E2I ) := {(x, y) ∈ (EI) |
df
dy
≥ df
dx
}.
Do d¯o´, neˆ´u ta. i vi. tr´ı d¯ieˆ˙’m giu˜
.a xa˙’y ra a2(yi + 1) ≥ b2(xi − 12) th`ı chu´ng ta chuyeˆ˙’n tu`. vu`ng
thu´. nhaˆ´t sang vu`ng thu´. hai.
29
....
....
.....
.....
.....
....
....
.....
......
........
.........
...........
.............
..................
..........................................
............
............
............
............
............
............
............
............
............
.
(E1I )
(E2I )
....
....
....
....
....
.......
....
................................................................................................................................................................................................
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
.........
∇f(x, y)
Hı`nh 1.7: Hai vu`ng cu˙’a ellipse.
Tu`. phu.o.ng tr`ınh xa´c d¯i.nh ellipse, cung (EI) xa´c d¯i.nh bo
.’˙ i ca´c caˇ.p to.a d¯oˆ. (x, y) vo´
.i
y = b
√
1− x2
a2
. Do d¯o´ ta co´ theˆ˙’ vieˆ´t la. i
(E1I ) := {(x, y) ∈ (EI) |
dy
dx
≤ −1}.
va`
(E2I ) := {(x, y) ∈ (EI) | − 1 ≤
dy
dx
≤ 0}.
Xe´t vu`ng thu´. nhaˆ´t
Trong tru.`o.ng ho.. p na`y, ca´c d¯ieˆ˙’m treˆn cung (E
1
I ) thoa˙’
dy
dx
≤ −1. Do d¯o´ −1 ≤ dx
dy
≤ 0. Suy ra
khi y taˇng moˆ.t d¯o
.n vi. th`ı x gia˙’m khoˆng qua´ moˆ.t d¯o
.n vi.. Vı` vaˆ.y neˆ´u bu
.´o.c thu´. i cho.n d¯u
.o.. c
d¯ieˆ˙’m ve˜ toˆ´t nhaˆ´t C := (xi, yi) th`ı o
.’˙ bu.´o.c thu´. (i + 1) ta se˜ cho.n d¯ieˆ˙’m ve˜ (xi+1, yi+1), trong
d¯o´ yi+1 = yi + 1 va` xi+1 = xi hoaˇ.c xi+1 = xi − 1. No´i ca´ch kha´c, bu.´o.c thu´. (i+ 1) chu´ng ta
se˜ cho.n moˆ.t trong hai pixel T := (xi, yi + 1) hoaˇ.c D := (xi − 1, yi + 1) (xem Hı`nh 1.8).
Tu.o.ng tu.. thuaˆ. t toa´n d¯ieˆ˙’m giu˜
.a ve˜ d¯u.`o.ng tha˙ˇ’ng va` d¯u.`o.ng tro`n, ta ca`ˆn u.´o.c lu.o.. ng ha`m
f(x, y) ta. i d¯ieˆ˙’m giu˜
.a M := (xi − 12 , yi + 1) cu˙’a hai pixel T va` D va` su.’˙ du.ng daˆ´u cu˙’a f(M)
d¯eˆ˙’ xa´c d¯i.nh vi. tr´ı cu˙’a M vo´
.i ellipse, va` do d¯o´ xa´c d¯i.nh pixel na`o ga`ˆn vo´
.i ellipse ho.n. Xe´t
bieˆ´n quyeˆ´t d¯i.nh
di := f(M) = f(xi − 1
2
, yi + 1) = b
2(x2i − xi +
1
4
) + a2(y2i + 2yi + 1)− a2b2.
Neˆ´u di chuyeˆ˙’n tu`. pixel hieˆ.n ha`nh d¯eˆ´n pixel T th`ı d¯ieˆ˙’m giu˜
.a co´ tung d¯oˆ. taˇng moˆ.t d¯o
.n vi.,
30
.............
M
....
....
....
....
....
....
....
.....
.....
.....
.....
.....
....
....
....
....
....
.....
.....
........
..........
............
Dw
C
w
Tw
Hı`nh 1.8: D- ieˆ˙’m giu˜.a M va` ca´c pixel T va` D.
neˆn
di+1 = f(xi − 1
2
, yi + 2) = b
2(x2i − xi +
1
4
) + a2(y2i + 4yi + 4)− a2b2.
Do d¯o´ di+1 = di + a
2(2yi + 3) vo´
.i bu.´o.c taˇng ∆T := a
2(2yi + 3).
Khi di chuyeˆ˙’n tu`. pixel hieˆ.n ha`nh d¯eˆ´n pixel D th`ı d¯ieˆ˙’m giu˜
.a co´ hoa`nh d¯oˆ. gia˙’m moˆ.t
d¯o.n vi. va` tung d¯oˆ. taˇng moˆ.t d¯o
.n vi., neˆn
di+1 = f(xi − 3
2
, yi + 2) = b
2(x2i − 3xi +
9
4
) + a2(y2i + 4yi + 4)− a2b2.
Suy ra di+1 = di+ b
2(−2xi+2)+a2(2yi+3) vo´.i bu.´o.c taˇng ∆D := b2(−2xi+2)+a2(2yi+3).
Baˆy gio`. ta ca`ˆn t´ınh gia´ tri. kho
.’˙ i ta.o. Gia˙’ thieˆ´t a va` b nguyeˆn, ellipse baˇ´t d¯a`ˆu ta. i (a, 0)
va` d¯ieˆ˙’m giu˜.a d¯a`ˆu tieˆn co´ to.a d¯oˆ. (a− 12 , 1). Do d¯o´
d0 = a
2 − ab2 + b2/4.
Vo´.i moˆ˜i bu.´o.c laˇ.p trong vu`ng thu´
. nhaˆ´t, chu´ng ta khoˆng chı˙’ kieˆ˙’m tra bieˆ´n quyeˆ´t d¯i.nh di va`
caˆ.p nhaˆ. t ca´c ha`m ∆ ma` co`n xe´t d¯a˜ keˆ´t thu´c vu`ng thu´
. nhaˆ´t chu.a du.. a treˆn vector gradient
ta. i d¯ieˆ˙’m giu˜
.a cu˙’a d¯oa.n TD. Vaˆ.y da˜y {(xi, yi)}i≥0 d¯u.o.. c xaˆy du.. ng theo quy na.p thoˆng qua
da˜y bieˆ´n quyeˆ´t d¯i.nh {di} nhu. sau:
1. [Kho.’˙ i ta.o] D- aˇ. t x0 = a; y0 = 0; d0 = a
2 − ab2 + b2/4.
2. [Keˆ´t thu´c?] Neˆ´u a2(yi + 1) ≥ b2(xi − 12) th`ı du`.ng (keˆ´t thu´c vu`ng thu´. nhaˆ´t) va` chuyeˆ˙’n
sang ve˜ vu`ng thu´. hai.
3. [Caˆ.p nhaˆ. t] Ngu
.o.. c la. i
31
• Ve˜ boˆ´n pixel: (xi, yi), (xi,−yi), (−xi, yi), (−xi,−yi).
• Neˆ´u di < 0 th`ı d¯aˇ. t
di+1 = di + a
2(2yi + 3),
xi+1 = xi.
• Ngu.o.. c la. i d¯aˇ. t
di+1 = di + b
2(−2xi + 2) + a2(2yi + 3),
xi+1 = xi − 1.
4. D- aˇ. t yi+1 = yi + 1, thay i bo
.’˙ i i+ 1 va` chuyeˆ˙’n sang Bu.´o.c 2.
Xe´t vu`ng thu´. hai
Ba`ˇng ca´c laˆ.p luaˆ.n tu
.o.ng tu.. , trong d¯o´ thay d¯oˆ˙’i vai tro` cu˙’a x va` y ta co´ theˆ˙’ ve˜ cung thu´
.
hai. Thaˆ. t vaˆ.y, treˆn vu`ng thu´
. hai (E2I ) ta co´ −1 ≤ dydx ≤ 0. Neˆn khi x gia˙’m moˆ.t d¯o.n vi. th`ı
y taˇng khoˆng qua´ moˆ.t d¯o
.n vi.. Vı` vaˆ.y, gia˙’ thieˆ´t o
.’˙ bu.´o.c thu´. i ta cho.n d¯u
.o.. c d¯ieˆ˙’m ve˜ toˆ´t
nhaˆ´t C := (xi, yi) th`ı bu
.´o.c keˆ´ tieˆ´p (i + 1) ta se˜ cho.n pixel (xi+1, yi+1) vo´
.i xi+1 = xi − 1 va`
yi+1 = yi hoaˇ.c yi+1 = yi + 1. No´i ca´ch kha´c, bu
.´o.c thu´. (i + 1) chu´ng ta se˜ cho.n moˆ.t trong
hai pixel L := (xi − 1, yi) hoaˇ.c D := (xi − 1, yi + 1) (xem Hı`nh 1.9).
Ta laˆ´y pixel d¯u.o.. c ve˜ o
.’˙ bu.´o.c cuoˆ´i cu˙’a vu`ng thu´. nhaˆ´t la` pixel kho.’˙ i ta.o (x0, y0) cu˙’a
vu`ng thu´. hai. Trong vu`ng na`y chu´ng ta ca`ˆn cho.n moˆ.t trong hai pixel L hoaˇ.c D. D- aˇ. t M la`
d¯ieˆ˙’m giu˜.a cu˙’a d¯oa.n LD; tu´
.c M co´ to.a d¯oˆ. la` (xi− 1, yi + 12). Tu.o.ng tu.. nhu. treˆn, ta co´ d¯ieˆ˙’m
M na`ˇm trong, treˆn hay ngoa`i ellipse neˆ´u va` chı˙’ neˆ´u bieˆ˙’u thu´.c f(M) aˆm, baˇ`ng khoˆng hay
du.o.ng tu.o.ng u´.ng. D- aˇ. t
di := f(M) = f(xi − 1, yi + 1
2
) = b2(x2i − 2xi + 1) + a2(y2i + yi +
1
4
)− a2b2.
Neˆ´u di chuyeˆ˙’n tu`. pixel hieˆ.n ha`nh d¯eˆ´n pixel L th`ı d¯ieˆ˙’m giu˜
.a co´ hoa`nh d¯oˆ. gia˙’m moˆ.t d¯o
.n vi.,
neˆn
di+1 = f(xi − 2, yi + 1
2
) = b2(x2i − 4xi + 4) + a2(y2i + yi +
1
4
)− a2b2.
Do d¯o´ di+1 = di + b
2(−2xi + 3) vo´.i bu.´o.c taˇng ∆L := b2(−2xi + 3).
Khi di chuyeˆ˙’n tu`. pixel hieˆ.n ha`nh d¯eˆ´n pixel D th`ı d¯ieˆ˙’m giu˜
.a co´ hoa`nh d¯oˆ. gia˙’m moˆ.t
d¯o.n vi. va` tung d¯oˆ. taˇng moˆ.t d¯o
.n vi., neˆn
di+1 = f(xi − 2, yi + 3
2
) = b2(x2i − 4xi + 4) + a2(y2i + 3yi +
9
4
)− a2b2.
Suy ra di+1 = di+ b
2(−2xi+3)+a2(2yi+2) vo´.i bu.´o.c taˇng ∆D := b2(−2xi+3)+a2(2yi+2).
32
.............M
......................................................................................................
Dw
C
wLw
Hı`nh 1.9: D- ieˆ˙’m giu˜.a M va` ca´c pixel L va` D.
Cuoˆ´i cu`ng ta ca`ˆn kho.’˙ i ta.o bieˆ´n quyeˆ´t d¯i.nh d0 trong vu`ng thu´
. hai: neˆ´u pixel cuoˆ´i cu`ng
E d¯u.o.. c cho.n trong vu`ng thu´
. nhaˆ´t la` (xE, yE) th`ı d¯aˇ. t d0 := f(xE − 1, yE + 12). Chu´ng ta keˆ´t
thu´c ve˜ vu`ng thu´. hai khi hoa`nh d¯oˆ. xi = 0. Ta co´ ca´c bu
.´o.c moˆ ta˙’ cho vu`ng thu´. hai nhu. sau:
1. [Kho.’˙ i ta.o] D- aˇ. t (x0, y0) = (xE, yE) va` d0 = b
2(x2E − 2xE + 1) + a2(y2E + yE + 14)− a2b2.
2. [Keˆ´t thu´c?] Neˆ´u (xi = 0) th`ı du`
.ng (keˆ´t thu´c vu`ng thu´. hai);
3. [Caˆ.p nhaˆ. t] Ngu
.o.. c la. i
• Ve˜ boˆ´n pixel: (xi, yi), (xi,−yi), (−xi, yi), (−xi,−yi).
• Neˆ´u di > 0 th`ı d¯aˇ. t
di+1 = di + b
2(−2xi + 3),
yi+1 = yi.
• Ngu.o.. c la. i d¯aˇ. t
di+1 = di + b
2(−2xi + 3) + a2(2yi + 2),
yi+1 = yi + 1.
4. D- aˇ. t xi+1 = xi − 1, thay i bo.’˙ i i+ 1 va` chuyeˆ˙’n sang Bu.´o.c 2.
Nhaˆ.n xe´t 1.3.1 (i) Trong tru
.`o.ng ho.. p ca´c to.a d¯oˆ. taˆm ellipse va` ca´c ba´n k´ınh a, b nguyeˆn,
d¯eˆ˙’ tra´nh t´ınh toa´n treˆn soˆ´ thu.. c, chu´ng ta co´ theˆ˙’ khu
.’˙ phaˆn soˆ´ va` chı˙’ a´p du.ng ca´c phe´p toa´n
treˆn soˆ´ nguyeˆn.
(ii) Cu˜ng co´ theˆ˙’ t´ınh ca´c ha`m ∆ tru.. c tieˆ´p trong moˆ˜i bu
.´o.c laˇ.p hoaˇ.c su
.’˙ du.ng phu
.o.ng pha´p
sai phaˆn baˆ.c hai nhu
. trong thuaˆ. t toa´n ve˜ d¯u
.`o.ng tro`n. Chu´ng ta co´ theˆ˙’ ve˜ ca´c ellipse qua
33
Hı`nh 1.10: (a) Hı`nh vuoˆng bao d¯u.`o.ng tro`n. (b) Hı`nh vuoˆng va` h`ınh tro`n qua phe´p bieˆ´n
d¯oˆ˙’i.
phe´p quay va` ca´c ellipse co´ “d¯oˆ. da`ˆy” he.p; tu´
.c vo´.i nhu˜.ng tru.`o.ng ho.. p |a| ¿ 1 ¿ |b| hoaˇ.c
ngu.o.. c la. i (xem [6]).
1.3.2 Ellipse trong tru.`o.ng ho.. p toˆ˙’ng qua´t
Trong pha`ˆn tru.´o.c ta d¯a˜ xaˆy du.. ng thuaˆ. t toa´n ve˜ d¯u
.`o.ng cong ellipse ma` ca´c tru. c cu˙’a no´ song
song vo´.i ca´c tru. c to.a d¯oˆ. cu˙’a maˇ. t pha˙ˇ’ng. Pha`ˆn na`y xaˆy du
.
. ng thuaˆ. t toa´n, du
.
. a treˆn phu
.o.ng
pha´p d¯ieˆ˙’m giu˜.a cu˙’a Van Aken, d¯eˆ˙’ ve˜ ca´c d¯u.`o.ng cong conic toˆ˙’ng qua´t bao go`ˆm ca´c ellipse,
hyperbol va` parabol. Thuaˆ. t toa´n na`y du
.
. a treˆn thuaˆ. t toa´n ve˜ d¯u
.`o.ng cong cu˙’a Pitteway [16]
d¯u.a ra naˇm 1967, hai naˇm sau khi Bresenham coˆng boˆ´ thuaˆ. t toa´n ve˜ d¯u
.`o.ng tha˙ˇ’ng [4].
Thuaˆ. t toa´n conic chia la`m hai pha`ˆn ta´ch bieˆ.t: D- aˇ.c ta˙’ conic co´ da.ng toˆ˙’ng qua´t
f(x, y) := Ax2 +Bxy + Cy2 +Dx+ Ey + F = 0.
vo´.i A,B,C,E, F la` ca´c heˆ. soˆ´ thu
.
. c. Phu
.o.ng pha´p xa´c d¯i.nh conic baˇ`ng phu
.o.ng tr`ınh f(x, y) =
0 kho´ h`ınh dung h`ınh ho.c va` do d¯o´ ta se˜ kha˙’o sa´t moˆ. t ca´ch kha´c. Chu´ng ta se˜ chı˙’ tr`ınh ba`y
ve`ˆ ellipse, nhu.ng nhu˜.ng ly´ luaˆ.n tu
.o.ng tu.. co´ theˆ˙’ a´p du.ng cho lo´
.p ca´c d¯u.`o.ng cong hyperbol
va` parabol.
D- u.`o.ng tro`n taˆm O(0, 0) ba´n k´ınh d¯o.n vi.:
x2 + y2 = 1
na`ˇm trong h`ınh vuoˆng V.
34
Xe´t phe´p bieˆ´n d¯oˆ˙’i affine T treˆn maˇ.t pha˙ˇ’ng R
2. Khi d¯o´ a´nh xa. T bieˆ´n d¯oˆ˙’i h`ınh vuoˆng
V tha`nh h`ınh b`ınh ha`nh va` d¯u.`o.ng tro`n bieˆ´n d¯oˆ˙’i tha`nh ellipse (Hı`nh 1.10). Ca´c d¯ieˆ˙’m giu˜.a
P,Q cu˙’a ca´c ca.nh cu˙’a h`ınh b`ınh ha`nh naˇ`m treˆn ellipse. Ca´c d¯ieˆ˙’m P,Q va` taˆm J cu˙’a h`ınh
b`ınh ha`nh xa´c d¯i.nh duy nhaˆ´t moˆ.t h`ınh b`ınh ha`nh va` do d¯o´ xa´c d¯i.nh duy nhaˆ´t ellipse. Nhaˆ.n
xe´t ra`ˇng neˆ´u co´ theˆ˙’ xa´c d¯i.nh ca´c heˆ. soˆ´ trong tru
.`o.ng ho.. p taˆm ellipse la` goˆ´c to.a d¯oˆ. th`ı chu´ng
ta cu˜ng co´ theˆ˙’ xu.’˙ ly´ trong tru.`o.ng ho.. p toˆ˙’ng qua´t. Ta chı˙’ ca`ˆn a´p du.ng phe´p ti.nh tieˆ´n d¯eˆ´n
taˆm J . (Dı˜ nhieˆn, d¯ie`ˆu na`y chı˙’ d¯u´ng khi J co´ ca´c to.a d¯oˆ. nguyeˆn). Vı` vaˆ.y co´ theˆ˙’ gia˙’ thieˆ´t J
la` goˆ´c to.a d¯oˆ. va` P,Q la` nhu˜
.ng d¯ieˆ˙’m d¯a˜ d¯u.o.. c bieˆ´n d¯oˆ˙’i tu
.o.ng u´.ng. Chu´ng ta gia˙’ thieˆ´t ra`ˇng
cung (ngaˇ´n) cu˙’a ellipse d¯i.nh hu
.´o.ng ngu.o.. c chie`ˆu kim d¯o`ˆng ho`ˆ (quanh taˆm J) tu`
. P d¯eˆ´n Q;
ngu.o.. c la. i, hoa´n d¯oˆ˙’i P va` Q.
D- eˆ˙’ xa´c d¯i.nh phu
.o.ng tr`ınh ellipse ta ca`ˆn t`ım phe´p bieˆ´n d¯oˆ˙’i affine trong R2 ca´c d¯ieˆ˙’m(
1
0
)
va`
(
0
1
)
tu.o.ng u´.ng leˆn P =
(
xP
yP
)
va` Q =
(
xQ
yQ
)
. Phe´p bieˆ´n d¯oˆ˙’i T trong tru.`o.ng
ho.. p na`y xa´c d¯i.nh bo
.’˙ i: (
x
y
)
7→
(
xP xQ
yP yQ
)(
x
y
)
.
Phe´p bieˆ´n d¯oˆ˙’i T bieˆ´n d¯oˆ˙’i ca´c d¯ieˆ˙’m treˆn d¯u.`o.ng tro`n:(
1
0
)
cos(α) +
(
0
1
)
sin(α),
vo´.i α ∈ [0, 1], tha`nh ca´c d¯ieˆ˙’m treˆn ellipse:(
x
y
)
=
(
xP
yP
)
cos(α) +
(
xQ
yQ
)
sin(α).
Chu´ y´ ra`ˇng cos2(α) + sin2(α) = 1. Suy ra ca´c heˆ. soˆ´ cu˙’a phu
.o.ng tr`ınh xa´c d¯i.nh ellipse la`
A = y2P + y
2
Q, B = −2(xPyP + xQyQ), C = x2P + x2Q,
D = 0, E = 0, F = −(xPyQ − yPxQ)2.
Baˆy gio`. ti.nh tieˆ´n ellipse theo vector
−→
PJ, ta d¯u.o.. c ellipse mo´
.i co´ taˆm ta. i −P, tu´.c la`
thay x = x+ xP , y = y+ yP va`o phu
.o.ng tr`ınh ellipse ta d¯u.o.. c phu
.o.ng tr`ınh xa´c d¯i.nh ellipse
mo´.i
A(x+ xP )
2 +B(x+ xP )(y + yP ) + C(y + yP )
2 +D(x+ xP ) + E(y + yP ) + F =
A
′
x2 +B
′
xy + C
′
y2 +D
′
x+ E
′
y + F
′
= 0,
trong d¯o´
A
′
= A, B
′
= B, C
′
= C,
D
′
= 2yQ(xPyQ − yPxQ), E ′ = −2xQ(xPyQ − yPxQ), F ′ = 0.
35
(a) (b)
....
.....
...........
.......................................................................................................................................................................................................................................
.............
...........
.........
........
........
......
.....
.....
....
....
....
....
....
....
.....
.....
.....
....
....
....
....
....
....
1
........................
2
.................
3
.........................
4
....
....
....
....
.
5
....
....
....
....
....
....
6
....
....
....
....
.
7
.........................
8......
....
....
...
.........................................................................................................................................................................................................
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
...
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
.............................................................................................................................................................................................
1 ..
............
.............
............
......2
.....
.....
.....
.....
.....
.....
.....
.....
.
.....
3
.....
.....
.....
.....
.....
.....
.....
.....
......
4
..........
..........
..........
..........
. .....
5......................................... ..... 6
.........................................
.....
7
..........................................
....
8 ..............................................
Cung Di chuyeˆ˙’n ba`n co`. Di chuyeˆ˙’n che´o
∆x ∆y ∆x ∆y
1 1 0 1 1
2 0 1 1 1
3 0 1 −1 1
4 −1 0 −1 1
5 −1 0 −1 −1
6 0 −1 −1 −1
7 0 −1 1 −1
8 1 0 1 −1
(c)
Hı`nh 1.11: (a) Ta´m cung ve˜. (b) Ellipse vo´.i phe´p phaˆn hoa.ch. (c) Hu
.´o.ng di chuyeˆ˙’n tu.o.ng
u´.ng.
36
Nhaˆ.n xe´t raˇ`ng goˆ´c to.a d¯oˆ. na`ˇm treˆn ellipse mo´
.i co´ taˆm ta. i −P, va` neˆ´u ta ve˜ d¯u.o.. c
ellipse mo´.i na`y th`ı se˜ ve˜ d¯u.o.. c ellipse ban d¯a`ˆu. Vı` A,B,C khoˆng thay d¯oˆ˙’i qua phe´p ti.nh
tieˆ´n, neˆn d¯eˆ˙’ gia˙’n tieˆ.n, ta se˜ k´ı hieˆ.u D va` C thay cho D
′
, C
′
(trong d¯o´ D va` E ban d¯a`ˆu ba`ˇng
0).
Tieˆ´n tr`ınh tieˆ´p theo la` ve˜ ellipse. Chu´ng ta chia tha`nh ta´m cung ve˜. Ca´c cung ve˜ cho
bieˆ´t hu.´o.ng di chuyeˆ˙’n trong thuaˆ. t toa´n. Trong cung thu´
. nhaˆ´t ta di chuyeˆ˙’n sang pha˙’i va` di
chuyeˆ˙’n che´o leˆn. Co´ hai ca´ch di chuyeˆ˙’n, go. i la` di chuyeˆ˙’n ba`n co`
. hoaˇ.c di chuyeˆ˙’n che´o, phu.
thuoˆ.c va`o moˆ.t hoaˇ.c ca˙’ hai to.a d¯oˆ. thay d¯oˆ˙’i. Hı`nh 1.11 minh ho.a ta´m cung ve˜, ca´c cung
tu.o.ng u´.ng moˆ.t ellipse va` ba˙’ng chı˙’ ra hu
.´o.ng di chuyeˆ˙’n trong moˆ˜i tru.`o.ng ho.. p.
Thuaˆ. t toa´n du
.´o.i d¯aˆy chia la`m hai bu.´o.c laˇ.p kha´c nhau - moˆ.t la`ˆn theo ca´c cung d¯a´nh
soˆ´ le˙’, keˆ´t thu´c khi d¯a. t d¯eˆ´n bieˆn cung che´o va` moˆ. t d¯oˆ´i vo´
.i ca´c cung chaˇ˜n, keˆ´t thu´c khi d¯a. t
d¯eˆ´n bieˆn ba`n co`.. D- eˆ˙’ xa´c d¯i.nh ca´c cung kho
.’˙ i d¯a`ˆu, ta nhaˆ.n xe´t ra`ˇng vector gradient
∇f(x, y) :=
( ∂f
∂x
∂f
∂y
)
=
(
2Ax+By +D
Bx+ 2Cy + E
)
vuoˆng go´c vo´.i tieˆ´p tuyeˆ´n cu˙’a conic ta. i d¯ieˆ˙’m d¯u
.o.. c t´ınh. Chu´ng ta su
.’˙ du.ng ca´c to.a d¯oˆ.
cu˙’a vector ∇f(x, y) = (∂f
∂x
, ∂f
∂y
)t d¯eˆ˙’ xa´c d¯i.nh hu
.´o.ng di chuyeˆ˙’n (ba`ˇng ca´ch quay 900 ngu.o.. c
chie`ˆu kim d¯o`ˆng ho`ˆ) va` do d¯o´ hu.´o.ng di chuyeˆ˙’n cu˙’a cung ve˜. Vı` d¯ieˆ˙’m baˇ´t d¯a`ˆu la` (0, 0) neˆn
∇f(0, 0) = (D,E). Thu˙’ tu. c GetOctant() nhaˇ`m phaˆn loa. i ca´c cung xuaˆ´t pha´t theo vector
na`y.
char GetOctant(int D, int E)
{
if ((D > 0) && (E < 0))
if (D < -E) return 1;
else return 2;
if ...
}
D- eˆ˙’ a´p du.ng thuaˆ. t toa´n d¯ieˆ˙’m giu˜
.a, vo´.i moˆ˜i cung ca`ˆn xa´c d¯i.nh gia´ tri. cu˙’a bieˆ´n quyeˆ´t
d¯i.nh d va` phu
.o.ng pha´p caˆ.p nhaˆ. t no´. Khi di chuyeˆ˙’n theo d¯u
.`o.ng che´o ta se˜ caˆ.p nhaˆ. t d ba`ˇng
moˆ.t bieˆ´n v; khi di chuyeˆ˙’n theo ba`n co`
., ta se˜ taˇng no´ bo.’˙ i bieˆ´n u. Neˆ´u f(x, y) la` phu.o.ng
tr`ınh ellipse th`ı d la` gia´ tri. cu˙’a ha`m f ta. i d¯ieˆ˙’m giu˜
.a cu˙’a d¯oa.n noˆ´i hai pixel co´ theˆ˙’ d¯u
.o.. c
cho.n trong bu
.´o.c keˆ´ tieˆ´p.
Vı` f(x, y) 0 tu.o.ng u´.ng beˆn ngoa`i ellipse
neˆn d < 0 khi ellipse d¯i ph´ıa ngoa`i d¯ieˆ˙’m giu˜.a va` do d¯o´ ta cho.n d¯ieˆ˙’m ngoa`i; ngu
.o.. c la. i khi
37
d > 0 ta cho.n d¯ieˆ˙’m trong; vo´
.i d = 0, cho.n moˆ.t trong hai. Co´ theˆ˙’ cho.n theo ca´ch cu˙’a Van
Aken: d¯oˆ´i vo´.i ca´c cung d¯a´nh soˆ´ le˙’ ta se˜ di chuyeˆ˙’n ba`n co`. khi d < 0 va` di chuyeˆ˙’n che´o neˆ´u
ngu.o.. c la. i. Vo´
.i ca´c cung d¯a´nh soˆ´ chaˇ˜n, ta di chuyeˆ˙’n che´o khi d < 0 va` ba`n co`. neˆ´u ngu.o.. c la. i.
Trong cung thu´. nhaˆ´t, gia˙’ su.’˙ o.’˙ bu.´o.c thu´. i ta cho.n d¯u
.o.. c pixel toˆ´t nhaˆ´t C := (xi, yi).
Ky´ hieˆ.u di la` gia´ tri. quyeˆ´t d¯i.nh cho.n giu˜
.a R := (xi + 1, yi) va` D := (xi + 1, yi + 1). Ky´ hieˆ.u
ui+1 va` vi+1 la` ca´c d¯a. i lu
.o.. ng coˆ.ng va`o di d¯eˆ˙’ ta.o di+1. Khi d¯o´ chu´ng ta ca`ˆn thu
.
. c hieˆ.n vo´
.i
moˆ˜i pixel la`
1. D- aˇ. t d¯ieˆ˙’m ve˜ ta. i pixel (xi, yi);
2. Cho.n pixel keˆ´ tieˆ´p (xi+1, yi+1) du
.
. a treˆn di;
3. Caˆ.p nhaˆ. t ui+1 va` vi+1 tu`
. ui, vi treˆn co
. so.’˙ cho.n lu
.
. a o
.’˙ Bu.´o.c 2;
4. Caˆ.p nhaˆ. t di+1 tu`
. di du
.
. a treˆn ui+1 hoaˇ.c vi+1;
5. Kieˆ˙’m tra thay d¯oˆ˙’i cung ve˜.
Nhaˇ´c la. i la` di+1 co´ theˆ˙’ d¯u
.o.. c t´ınh tu`
. di ba`ˇng ky˜ thuaˆ. t sai phaˆn. Gia˙’ thieˆ´t la` d¯ang o
.’˙ cung
ve˜ d¯a`ˆu tieˆn, d¯ieˆ˙’m ve˜ toˆ´t nhaˆ´t la` (xi, yi) va` ta co´ bieˆ´n quyeˆ´t d¯i.nh di = f(xi + 1, yi +
1
2
) d¯eˆ˙’
cho.n pixel keˆ´ tieˆ´p. Neˆ´u di di chuyeˆ˙’n theo ba`n co`
. th`ı xi+1 = xi + 1 va` yi+1 = yi. Do d¯o´ bieˆ´n
quyeˆ´t d¯i.nh mo´
.i di+1 = f(xi + 2, yi +
1
2
).Suy ra
ui+1 = di+1 − di
= A(xi + 2)
2 +B(xi + 2)(yi +
1
2
) + C(yi +
1
2
)2
+D(xi + 2) + E(yi +
1
2
) + F
−A(xi + 1)2 +B(xi + 1)(yi + 1
2
) + C(yi +
1
2
)2
+D(xi + 1) + E(yi +
1
2
) + F
= A[2(xi + 1) + 1] +B(yi +
1
2
) +D
= A(2xi + 1) + B(yi +
1
2
) +D + 2A.
Maˇ.t kha´c, neˆ´u di chuyeˆ˙’n theo hu
.´o.ng che´o th`ı di = f(xi + 2, yi +
3
2
) va` bu.´o.c taˇng la`
vi+1 = di+1 − di
= (2A+B)xi+1 + (B + 2C)yi+1 + A+
B
2
+D + E
= (2A+B)xi + (B + 2C)yi + A+
B
2
+D + E + [2A+ 2B + 2C].
38
Neˆ´u d¯aˇ. t
ui = A(2xi + 1) + B(yi +
1
2
) +D
th`ı vo´.i vieˆ.c di chuyeˆ˙’n ba`n co`
. ta co´ ui+1 = ui + 2A. Tu
.o.ng tu.. , neˆ´u d¯aˇ. t
vi = (2A+B)xi + (B + 2C)yi + A+
B
2
+D + E
th`ı khi di chuyeˆ˙’n che´o ta co´ vi+1 = vi + (2A+ 2B + 2C).
D- eˆ˙’ lu.u giu˜. nhu˜.ng gia´ tri. ui va` vi d¯oˆ´i vo´
.i hai ca´ch di chuyeˆ˙’n ba`n co`. va` che´o, ta ca`ˆn
caˆ.p nhaˆ. t nhu˜
.ng gia´ tri. na`y keˆ˙’ ca˙’ khi chu´ng khoˆng d¯u
.o.. c su
.’˙ du.ng. Do d¯o´,
• vo´.i di chuyeˆ˙’n ba`n co`.
vi+1 = (2A+B)xi+1 + (B + 2C)yi+1 + A+B/2 +D + E
= (2A+B)(xi + 1) + (B + 2C)yi + A+B/2 +D + E
= vi + 2A+B;
• d¯oˆ´i vo´.i di chuyeˆ˙’n che´o,
ui+1 = ui + 2A+B.
D- aˇ. t k1 := 2A, k2 := 2A + B, va` k3 := 2A + 2B + 2C. Khi d¯o´ ta co´ thu˙’ tu. c caˆ.p nhaˆ. t
ca´c bieˆ´n u va` v nhu. sau:
• Di chuyeˆ˙’n ba`n co`.
ui+1 = ui + k1, vi+1 = vi + k2.
• Di chuyeˆ˙’n che´o
ui+1 = ui + k2, vi+1 = vi + k3.
Baˆy gio`. kha˙’o sa´t vieˆ.c thay d¯oˆ˙’i cung ve˜. Nhaˆ.n xe´t ra`ˇng chu´ng ta keˆ´t thu´c ve˜ cung (E
1)
khi vector gradient ∇f(x, y) ty˙’ leˆ. vo´.i vector
(
1
−1
)
. No´i ca´ch kha´c, chu´ng ta keˆ´t thu´c ve˜
cung (E1) khi toˆ˙’ng cu˙’a hai tha`nh pha`ˆn cu˙’a vector ∇f(x, y) ba`ˇng khoˆng (Hı`nh 1.12).
Maˇ.t kha´c, de˜ˆ da`ng kieˆ˙’m tra raˇ`ng
∂f
∂x
= ui − k2
2
,
∂f
∂y
+
∂f
∂y
= vi − k2
2
.
39
.....
........................................................................................................................................................................................................................
..........
.........
........
.....
.....
....
....
....
....
....
....
....
....
....
.....
.....
.....
.....
.....
.....
....
....
....
....
....
....
....
.....
....
..................
........................
.........................
Vector na`y naˇ`m treˆn d¯u.`o.ng tha˙ˇ’ng co´ heˆ. soˆ´ go´c -11
2
Hı`nh 1.12: Trong cung thu´. nhaˆ´t, toˆ˙’ng ca´c tha`nh pha`ˆn cu˙’a vector gradient aˆm. Khi d¯i va`o
cung thu´. hai, toˆ˙’ng na`y d¯oˆ˙’i daˆ´u.
Do d¯o´, daˆ´u cu˙’a bieˆ˙’u thu´.c vi − k22 cho bieˆ´t d¯a˜ keˆ´t thu´c ve˜ cung (E1) hay chu.a. Tu.o.ng
tu.. , keˆ´t thu´c ve˜ cung (E
2) xa´c d¯i.nh bo
.’˙ i daˆ´u ui − k22 .
Keˆ´ tieˆ´p chu´ng ta ca`ˆn xa´c d¯i.nh ca´c bieˆ´n quyeˆ´t d¯i.nh di va` ui, vi cu˙’a cung thu´
. hai khi
ta keˆ´t thu´c cung thu´. nhaˆ´t; chu´ng vaˆ˜n tu.o.ng u´.ng vo´.i ca´c bieˆ´n taˇng d¯oˆ´i vo´.i di chuyeˆ˙’n che´o
va` ba`n co`.. Nhu.ng ca´c di chuyeˆ˙’n ba`n co`. baˆy gio`. la` d¯u´.ng thay v`ı ngang va` di d¯u
.o.. c xa´c d¯i.nh
bo.’˙ i f(xi +
1
2
, yi + 1) thay cho f(xi + 1, yi +
1
2
).
Ky´ hieˆ.u d
′
i, u
′
i, v
′
i trong vu`ng thu´
. hai thay cho di, ui, vi (vo´
.i cu`ng y´ ngh˜ıa). De˜ˆ da`ng
kieˆ˙’m tra ra`ˇng
d
′
i − di = f(xi +
1
2
, yi + 1)− f(xi + 1, yi + 1
2
)
=
vi
2
− ui + 3
8
k3 − 1
2
k2,
v
′
i − vi = (2A+B)xi + (B + 2C)yi +
B
2
+ C +D + E
−(2A+B)xi(B + 2C)yi + A+ B
2
+D + E
= −A+ C,
u
′
i − ui = vi − ui −
k2
2
+
k3
2
.
Ho.n nu˜.a,
k
′
3 = k3, k
′
2 = k3 − k2, k
′
1 = k1 − 2k2 + k3.
Nhu. vaˆ.y chu´ng ta d¯a˜ co´ ca´c d¯ie`ˆu ca`ˆn thieˆ´t d¯eˆ˙’ ve˜ ellipse, ı´t nhaˆ´t la` hai cung. Chu´ng ta bao
ha`m heˆ. soˆ´ F (tha`nh pha`ˆn ha`ˇng trong phu
.o.ng tr`ınh xa´c d¯i.nh conic) trong d¯oa.n ma˜ maˇ.c du`
d¯ang gia˙’ su.’˙ no´ ba`ˇng 0; vo´.i conic toˆ˙’ng qua´t, taˆm co´ theˆ˙’ co´ to.a d¯oˆ. khoˆng nguyeˆn va` do d¯o´
d¯ieˆ˙’m baˇ´t d¯a`ˆu (d¯eˆ˙’ ve˜) co´ theˆ˙’ khoˆng na`ˇm treˆn ellipse (trong tru.`o.ng ho.. p na`y F co´ theˆ˙’ kha´c
0).
40
Sau d¯oa.n ma˜ minh ho.a thuaˆ. t toa´n trong chu
.o.ng tr`ınh Conic.cpp la` thu˙’ tu. c Conjugate()
nha`ˇm xa´c d¯i.nh ca´c heˆ. soˆ´ cu˙’a moˆ.t ellipse (taˆm ta. i goˆ´c to.a d¯oˆ. ) tu`
. ca´c d¯ieˆ˙’m lieˆn ho.. p P va`
Q : Hı`nh b`ınh ha`nh co´ ca´c d¯ı˙’nh la` P +Q,P −Q,−P −Q va` −P +Q bao quanh ellipse va`
ellipse tieˆ´p xu´c vo´.i ca´c ca.nh cu˙’a h`ınh b`ınh ha`nh.
D- oa.n ma˜ keˆ´t thu´c khi d¯i heˆ´t cung cuoˆ´i cu`ng. D- eˆ˙’ ve˜ ellipse khe´p k´ın, ca`ˆn d¯eˆ´m soˆ´ ca´c
bu.´o.c di chuyeˆ˙’n ca`ˆn thieˆ´t d¯eˆ˙’ d¯a. t to´
.i pixel xuaˆ´t pha´t (ba`i taˆ.p).
void Conic (long xs, long ys, long xe, long ye)
{
long x, y;
long octant, octantCount;
int dxsquare, dysquare, dxdiag, dydiag;
long d, u, v, k1, k2, k3;
long dfdx, dfdy;
long tmp;
octant = GetOctant(D, E);
switch (octant)
{
case 1:
{
d = round(A + B/2 + C/4 + D + E/2 + F);
u = round(A + B/2 + D);
v = round(A + B/2 + D + E);
k1 = 2*A;
k2 = (2*A + B);
k3 = k2 + B + 2*C;
dxsquare = 1;
dysquare = 0;
dxdiag = 1;
dydiag = 1;
break;
}
case 2:
{
41
d = round(A/4 + B/2 + C + D/2 + E + F);
u = round(B/2 + C + E);
v = round(B/2 + C + D + E);
k1 = 2*C;
k2 = B + 2*C;
k3 = 2*A + 2*B + 2*C;
dxsquare = 0;
dysquare = 1;
dxdiag = 1;
dydiag = 1;
break;
}
...
}
x = xe - xs;
y = ye - ys;
dfdx = (2*A*x + B*y + D);
dfdy = (B*x + 2*C*y + E);
octantCount = GetOctant(dfdx, dfdy) - octant;
if (octantCount <= 0) octantCount += 8;
x = xs;
y = ys;
while (octantCount > 0)
{
if (octant % 2)
{
while (v <= k2/2)
{
putpixel(x, y, Value);
if (d < 0)
{
x += dxsquare;
y += dysquare;
u += k1;
v += k2;
42
d += u;
}
else
{
x += dxdiag;
y += dydiag;
u += k2;
v += k3;
d += v;
}
}
d += v/2 - u + 3*k3/8 - k2/2;
u = -u + v + k3/2 - k2/2;
v += k3/2 - k2;
k1 = k1 - 2*k2 + k3;
k2 = k3 - k2;
tmp = dxsquare;
dxsquare = -dysquare;
dysquare = tmp;
}
else
{
while (u < k2/2)
{
putpixel(x, y, Value);
if (d < 0)
{
x += dxdiag;
y += dydiag;
u += k2;
v += k3;
d += v;
}
else
{
x += dxsquare;
y += dysquare;
43
u += k1;
v += k2;
d += u;
}
}
d = d + u - v + k1 - k2;
v = 2*u - v + k1 -k2;
u = u + k1 - k2;
k3 = 4*(k1 - k2) + k3;
k2 = 2*k1 - k2;
tmp = dxdiag;
dxdiag = -dydiag;
dydiag = tmp;
}
octant++;
if (octant > 8) octant -= 8;
octantCount--;
}
....
}
void Conjugate (long xp, long yp, long xq, long yq)
{
long xprod, tmp, xe, ye;
xprod = xp*yq - xq*yp;
if (xprod != 0)
{
if (xprod < 0)
{
tmp = xp; xp = xq; xq = tmp;
tmp = yp; yp = yq; yq = tmp;
xprod = -xprod;
}
A = yp*yp + yq*yq;
B = -2*(xp*yp + xq*yq);
44
C = xp*xp + xq*xq;
D = 2*yq*xprod;
E = -2*xq*xprod;
F = 0;
xe = xp;
ye = yp;
Conic(xp, yp, xe, ye);
}
}
D- ie`ˆu d¯a´ng nga.c nhieˆn la` d¯oa.n ma˜ caˆ.p nhaˆ. t ca´c gia´ tri. trong hai cung ve˜ d¯a`ˆu tieˆn cu˜ng thu
.
. c
hieˆ.n d¯u´ng vo´
.i ca´c cung ve˜ co`n la. i. Cuoˆ´i cu`ng, nhu
. trong Hı`nh 1.13, d¯oˆi khi moˆ.t bu
.´o.c di
chuyeˆ˙’n che´o trong thuaˆ. t toa´n baˇng qua ph´ıa beˆn kia cu˙’a ellipse; ngh˜ıa la` no´ thay d¯oˆ˙’i nhie`ˆu
cung ve˜ ta. i moˆ. t tho`
.i d¯ieˆ˙’m. Khi d¯ie`ˆu na`y xa˙’y ra, thuaˆ. t toa´n ta.o ra moˆ.t da˜y ca´c pixel ra kho˙’i
quy˜ d¯a.o cu˙’a ellipse. Nhaˆ.n xe´t raˇ`ng d¯aˆy la` moˆ. t da.ng cu˙’a aliasing-t´ınh hieˆ.u f(x, y) d¯u
.o.. c laˆ´y
maˆ˜u chu´.a ca´c ta`ˆn soˆ´ raˆ´t cao chuyeˆ˙’n tha`nh ca´c d¯ieˆ˙’m nguyeˆn.
Pratt d¯e`ˆ xuaˆ´t moˆ. t phu
.o.ng a´n gia´i quyeˆ´t nhu. sau [18]. Trong khi thuaˆ. t toa´n di chuyeˆ˙’n
trong cung ve˜ thu´. nhaˆ´t, vieˆ.c baˇng che´o qua ellipse se˜ tu
.o.ng u´.ng su.. thay d¯oˆ˙’i nhanh hu
.´o.ng
cu˙’a vector gradient. Thaˆ. t vaˆ.y, trong cung ve˜ thu´
. nhaˆ´t vector gradient luoˆn luoˆn co´ tha`nh
pha`ˆn theo y aˆm va` tha`nh pha`ˆn theo x du.o.ng. Sau khi baˇng qua ellipse, ta se˜ d¯eˆ´n moˆ.t d¯ieˆ˙’m
trong cung ve˜ 3, 4, 5 hoaˇ.c 6. Chu´ng ta xa´c d¯i.nh d¯u
.`o.ng tha˙ˇ’ng phaˆn ca´ch giu˜.a ca´c cung
ve˜ na`y va` ca´c cung ve˜ 7, 8, 1 va` 2 baˇ`ng ca´ch cho tha`nh pha`ˆn x cu˙’a vector gradient baˇ`ng
khoˆng-tu´.c la` 2Ax + By + D = 0. Vı` ui = 2Axi + Byi + D + A + B/2 neˆn co´ theˆ˙’ su
.’˙ du.ng
bieˆ´n ui d¯eˆ˙’ xa´c d¯i.nh hieˆ.n tu
.o.. ng baˇng che´o xa˙’y ra. Ly´ luaˆ.n tu
.o.ng tu.. vo´
.i ca´c cung ve˜ kha´c.
D- eˆ˙’ co´ theˆm thoˆng tin ve`ˆ ca´c thuaˆ. t toa´n ve˜ conic, xem Pitt1, [18], [6].
..................................................................................................................................................................................
..................................................................................................................................................................................
..................................................................................................................................................................................
..................................................................................................................................................................................
..................................................................................................................................................................................
..................................................................................................................................................................................
..................................................................................................................................................................................
..................................................................................................................................................................................
....
....
...
....
....
....
...
....
....
....
....
....
....
....
....
....
....
....
....
...
....
....
....
...
....
....
....
....
....
....
....
....
....
....
.
....
....
...
....
....
....
...
....
....
....
....
....
....
....
....
....
....
....
....
...
....
....
....
...
....
....
....
....
....
....
....
....
....
....
.
....
....
...
....
....
....
...
....
....
....
....
....
....
....
....
....
....
....
....
...
....
....
....
...
....
....
....
....
....
....
....
....
....
....
.
....
....
...
....
....
....
...
....
....
....
....
....
....
....
....
....
....
....
....
...
....
....
....
...
....
....
....
....
....
....
....
....
....
....
.
....
....
...
....
....
....
...
....
....
....
....
....
....
....
....
....
....
....
....
...
....
....
....
...
....
....
....
....
....
....
....
....
....
....
.
....
....
...
....
....
....
...
....
....
....
....
....
....
....
....
....
....
....
....
...
....
....
....
...
....
....
....
....
....
....
....
....
....
....
.
....
....
...
....
....
....
...
....
....
....
....
....
....
....
....
....
....
....
....
...
....
....
....
...
....
....
....
....
....
....
....
....
....
....
.
....
....
...
....
....
....
...
....
....
....
...
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
.
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
.
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
.
..........................................................................................................................................................................
........................
.....................
..........
..............
........y y y y y
y y
y y
y
Hı`nh 1.13: Thuaˆ. t toa´n sai trong tru
.`o.ng ho.. p ellipse he.p.
Wu va` Rokne [28] xaˆy du.. ng moˆ.t phu
.o.ng pha´p kha´c ve˜ conic phu` ho.. p vo´
.i thieˆ´t bi. hieˆ˙’n
45
thi. ca´c mu´
.c xa´m. Thay cho vieˆ.c taˇng moˆ.t pixel ta. i moˆ. t tho`
.i d¯ieˆ˙’m, thuaˆ. t toa´n taˇng moˆ.t
khoˆ´i ca´c pixel. Gia˙’ su.’˙ chu´ng ta di chuyeˆ˙’n theo chie`ˆu ngang va` d¯oˆ. cong lo`ˆi leˆn. Neˆ´u chu´ng
ta d¯a˜ ve˜ pixel (x, y) va` sau hai bu.´o.c laˇ.p chu´ng ta ve˜ pixel (x+2, y+2) th`ı pixel trung gian
d¯u.o.. c noˆ. i suy la` (x+1, y+1). Tu
.o.ng tu.. , neˆ´u sau hai bu
.´o.c laˇ.p ta ve˜ pixel (x+2, y) th`ı pixel
trung gian d¯u.o.. c noˆ. i suy la` (x + 1, y). Neˆ´u sau hai bu
.´o.c laˇ.p la` pixel (x + 2, y + 1) th`ı ca`ˆn
cho.n moˆ.t trong hai pixel (x+ 1, y) hoaˇ.c (x+ 1, y + 1). Treˆn ma`n h`ınh gia´ tri. xa´m, chu´ng ta
co´ theˆ˙’ hieˆ˙’n thi. ca˙’ hai pixel na`y nhu
.ng vo´.i cu.`o.ng d¯oˆ. sa´ng moˆ.t nu
.’˙ a. Do d¯o´ ta. i moˆ˜i bu
.´o.c laˇ.p,
ta ve˜ hai pixel cu`ng moˆ.t lu´c va` v`ı vaˆ.y gia˙’m tho`
.i gian thu.. c hieˆ.n t´ınh toa´n. Ta. i choˆ˜ noˆ´i cu˙’a
hai cung ve˜, thuaˆ. t toa´n ca`ˆn tra´nh vieˆ.c ve˜ cho`ˆng leˆn nhau va` khoˆng qua´ kho´ d¯eˆ˙’ gia˙’i quyeˆ´t
d¯ie`ˆu na`y. Hieˆ˙’n nhieˆn thuaˆ. t toa´n chı˙’ phu` ho
.
. p vo´
.i nhu˜.ng thieˆ´t bi. hieˆ˙’n thi. gia´ tri. xa´m, nhu
.ng
no´ minh ho.a co´ theˆ˙’ d¯o
.n gia˙’n hoa´ qua´ tr`ınh xu.’˙ ly´ khi co´ theˆ˙’ a´p du.ng ky˜ thuaˆ. t antialiasing.
46
Chu.o.ng 2
Hı`nh ho.c cu˙’a ca´c d¯u
.`o.ng cong va` maˇ.t
cong
Mu.c d¯ı´ch ch´ınh cu˙’a chu
.o.ng na`y la` tr`ınh ba`y ca´c phu.o.ng pha´p ve˜ d¯u.`o.ng cong Bezier va`
B-spline. D- aˆy la` hai d¯u.`o.ng cong thu.`o.ng d¯u.o.. c su
.’˙ du.ng trong ca´c pha`ˆn me`ˆm d¯o`ˆ ho.a.
2.1 Mo.’˙ d¯a`ˆu
Chu.o.ng na`y tr`ınh ba`y phu.o.ng pha´p h`ınh ho.c nhaˇ`m phaˆn t´ıch va` thieˆ´t keˆ´ ca´c d¯u
.`o.ng cong
va` maˇ.t cong du
.´o.i da.ng ca´c phu
.o.ng tr`ınh tham soˆ´ va` do d¯o´ cho phe´p de˜ˆ da`ng ve˜ no´.
Ngu.o.. c vo´
.i ca´c d¯u.`o.ng cong va` maˇ.t cong du
.
. a treˆn ca´c phu
.o.ng tr`ınh toa´n ho.c tu
.o.ng
d¯oˆ´i d¯o.n gia˙’n nhu. ellipse cho bo.’˙ i P (t) = (a cos(2pit), b sin(2pit)), ca´c coˆng cu. ma` chu´ng ta
tr`ınh ba`y du.´o.i d¯aˆy cho phe´p ngu.`o.i thieˆ´t keˆ´ xaˆy du.. ng nhu˜
.ng h`ınh da.ng kha´c nhau du
.
. a treˆn
du˜. lieˆ.u cho tru
.´o.c va` co´ theˆ˙’ d¯ie`ˆu khieˆ˙’n chu´ng moˆ.t ca´ch de˜ˆ da`ng thoˆng qua moˆ.t taˆ.p nhu˜
.ng
d¯ieˆ˙’m ma` ta go. i la` ca´c “d¯ieˆ˙’m d¯ie`ˆu khieˆ˙’n”. Vieˆ.c xaˆy du
.
. ng moˆ.t d¯u
.`o.ng cong (hay maˇ.t cong)
tuy` y´ la` raˆ´t kho´ neˆ´u khoˆng bieˆ´t tru.´o.c phu.o.ng tr`ınh xa´c d¯i.nh no´. Tuy nhieˆn, vo´
.i ca´ch tieˆ´p
caˆ.n mo´
.i, ta co´ theˆ˙’ ta.o ra nhu˜
.ng h`ınh da.ng mong muoˆ´n ba`ˇng ca´ch chı˙’nh, su
.’˙ a vi. tr´ı ca´c d¯ieˆ˙’m
d¯ie`ˆu khieˆ˙’n-d¯ie`ˆu na`y thu.. c hieˆ.n de˜ˆ da`ng ba`ˇng qua´ tr`ınh tu
.o.ng ta´c giu˜.a ngu.`o.i thieˆ´t keˆ´ va`
ma´y t´ınh.
Phu.o.ng pha´p xaˆy du.. ng d¯u
.`o.ng cong o.’˙ d¯aˆy la` moˆ. t nhaˆn toˆ´ co
. ba˙’n trong la˜nh vu.. c a´p
du.ng ma´y t´ınh va`o thieˆ´t keˆ´ ca´c maˆ˜u h`ınh ho.c (computer aided geometric design-CAGD) va`
thu.`o.ng du`ng trong coˆng ngheˆ. cheˆ´ ta.o. Chu
.o.ng na`y d¯e`ˆ caˆ.p moˆ.t soˆ´ phu
.o.ng pha´p thieˆ´t keˆ´
47
ca´c d¯u.`o.ng cong va` maˇ.t cong. Co´ nhie`ˆu ca´ch tieˆ´p caˆ.n (xem, cha˙ˇ’ng ha.n [1], [7], [8]), nhu
.ng
o.’˙ d¯aˆy cho.n vieˆ.c thieˆ´t keˆ´ su
.’˙ du.ng ca´c d¯u
.`o.ng cong Bezier va` B-spline. Lo´.p d¯u.`o.ng cong na`y
raˆ´t quen thuoˆ.c trong ca´c u´
.ng du.ng CAD (computer-aided design) .
Các file đính kèm theo tài liệu này:
Đồ họa máy tính.pdf
