›
›

Giáo trình Đồ họa máy tính I (Phần 1) - Phạm Tiến Sơn

Download
`
ˆ
´
´
-
DO HOA MAY TINH I  
.
.
´
Pham Tiˆen Son  
.
-
D`a Lat, 2005  
.
2
Muc luc  
. .  
.
`
L`oi n´oi d¯ˆau  
7
. .  
1 C´ac thuˆat to´an v˜e d¯u`ong cong trˆen thiˆet bi raster  
´
9
.
.
-
˙’  
1.1 Doan thˇang . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
9
.
´
1.1.1 Thuaˆt to´an sˆo gia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11  
.
.
˙’  
1.1.2 Thuaˆt to´an d¯iˆem giu˜a . . . . . . . . . . . . . . . . . . . . . . . . . . 13  
.
˙’  
1.1.3 Mˆot sˆo vˆan d¯ˆe liˆen quan d¯ˆen thuaˆt to´an v˜e d¯oan thˇang . . . . . . . . 18  
´ ´  
`
´
.
.
.
˙’  
1.1.4 C´ac thuoˆc t´ınh cua d¯oan thˇang . . . . . . . . . . . . . . . . . . . . . 21  
˙’  
.
.
. .  
-
1.2 Du`ong tr`on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22  
.
-
˙’  
´
1.2.1 Dˆoi xu´ng t´am d¯iˆem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22  
.
. .  
˙’  
1.2.2 Thuaˆt to´an d¯iˆem giu˜a v˜e d¯u`ong tr`on . . . . . . . . . . . . . . . . . . 23  
.
. .  
-
1.3 Du`ong cong ellipse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28  
´
1.3.1 Ellipse c´o dang ch´ınh tˇac . . . . . . . . . . . . . . . . . . . . . . . . . 29  
.
. .  
.
˙’  
1.3.2 Ellipse trong tru`ong hop tˆong qu´at . . . . . . . . . . . . . . . . . . . 34  
.
. .  
˙’  
2 H`ınh hoc cua c´ac d¯u`ong cong v`a mˇat cong  
47  
.
.
.
`
˙’  
2.1 Mo d¯aˆu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47  
3
. .  
-
2.2 Du`ong cong Bezier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48  
2.2.1 Thuaˆt to´an de Casteljau . . . . . . . . . . . . . . . . . . . . . . . . . 48  
.
.
. .  
-
2.2.2 Da thu´c Bernstein v`a d¯u`ong cong Bezier . . . . . . . . . . . . . . . . 52  
. .  
´
˙’  
2.3 C´ac t´ınh chˆat cua d¯u`ong cong Bezier . . . . . . . . . . . . . . . . . . . . . . 55  
. .  
2.3.1 Diˆeu khiˆen d¯ia phuong . . . . . . . . . . . . . . . . . . . . . . . . . . 59  
-
˙’  
`
.
.
.
-
2.4 Da thu´c tu`ng khu´c v`a c´ac h`am spline . . . . . . . . . . . . . . . . . . . . . . 60  
.
.
˙’  
2.4.1 Su dung c´ac h`am spline nhu c´ac h`am trˆon . . . . . . . . . . . . . . . 63  
.
.
.
2.4.2 Xˆay dung c´ac h`am trˆon . . . . . . . . . . . . . . . . . . . . . . . . . 65  
.
.
. .  
. .  
˙’  
-
2.4.3 Du`ong cong spline v`a c´ac h`am co so . . . . . . . . . . . . . . . . . . 66  
. .  
˙’  
2.4.4 C´ac h`am B-spline co so . . . . . . . . . . . . . . . . . . . . . . . . . 66  
.
˙’  
2.4.5 Su dung c´ac knot bˆoi . . . . . . . . . . . . . . . . . . . . . . . . . . . 71  
.
.
˙’  
2.4.6 Vector knot chuaˆn . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73  
. .  
2.5 C´ac t´ınh chˆat cua d¯u`ong cong B-spline . . . . . . . . . . . . . . . . . . . . . 75  
´
˙’  
. .  
2.6 Nˆoi suy c´ac d¯iˆem d¯iˆeu khiˆen bˇang d¯u`ong cong B-spline . . . . . . . . . . . . 77  
˙’  
˙’  
`
`
.
´
´
2.7 Thiˆet kˆe c´ac mˇat Bezier v`a B-spline . . . . . . . . . . . . . . . . . . . . . . . 80  
.
2.7.1 Patch Bezier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80  
2.7.2 D´an c´ac patch Bezier . . . . . . . . . . . . . . . . . . . . . . . . . . . 81  
2.7.3 Patch spline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82  
. .  
´
˙’  
3 Giao cua c´ac d¯ˆoi tuong  
83  
.
.
`
˙’  
3.1 Mo d¯aˆu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83  
˙’  
˙’  
3.2 Giao cua hai d¯oan thˇang . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83  
.
3.2.1 Phˆan t´ıch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84  
4
˙’  
3.2.2 Thuaˆt to´an x´ac d¯inh giao hai d¯oan thˇang . . . . . . . . . . . . . . . . 86  
.
.
.
.
-
˙’  
3.3 Doan thˇang v`a h`ınh chu˜ nhˆat . . . . . . . . . . . . . . . . . . . . . . . . . . 87  
.
.
. .  
3.3.1 T`ım giao bˇang c´ach giai hˆe c´ac phuong tr`ınh . . . . . . . . . . . . . . 89  
`
˙’  
.
3.3.2 Thuaˆt to´an chia nhi phˆan . . . . . . . . . . . . . . . . . . . . . . . . 89  
.
.
3.3.3 Thuaˆt to´an Cohen-Sutherland . . . . . . . . . . . . . . . . . . . . . . 93  
.
3.3.4 Thuaˆt to´an Liang-Barsky . . . . . . . . . . . . . . . . . . . . . . . . 97  
.
˙’  
3.4 Giao cua d¯oan thˇang v`a d¯a gi´ac lˆoi . . . . . . . . . . . . . . . . . . . . . . . 100  
`
˙’  
.
. .  
.
. .  
˙’  
˙’  
´
˙’  
3.4.1 Vi tr´ı tuong d¯ˆoi cua mˆot d¯iˆem v´oi d¯u`ong thˇang . . . . . . . . . . . . 100  
.
.
˙’  
3.4.2 Thuaˆt to´an t`ım giao cua d¯oan thˇang v`a d¯a gi´ac lˆoi . . . . . . . . . . 102  
`
˙’  
.
.
3.5 Giao hai d¯a gi´ac . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107  
3.5.1 Thuaˆt to´an Sutherland-Hodgman . . . . . . . . . . . . . . . . . . . . 108  
.
3.5.2 Thuaˆt to´an Weiler-Atherton . . . . . . . . . . . . . . . . . . . . . . . 111  
.
.
3.5.3 C´ac ph´ep to´an tˆap hop trˆen c´ac d¯a gi´ac . . . . . . . . . . . . . . . . 113  
.
.
`
`
˙’  
3.6 Ray tracing hai chiˆeu: phan xa trong buˆong k´ın . . . . . . . . . . . . . . . . 114  
.
˙’  
3.6.1 Vector phan xa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115  
.
. .  
3.6.2 Giao cua tia s´ang v`a d¯u`ong thˇang . . . . . . . . . . . . . . . . . . . 117  
˙’  
˙’  
˙’  
.
. .  
3.6.3 Giao cua tia s´ang v´oi d¯u`ong tr`on . . . . . . . . . . . . . . . . . . . . 121  
.
3.6.4 Xˆay dung v´ı du ray tracing . . . . . . . . . . . . . . . . . . . . . . . 124  
.
.
`
3.6.5 Buˆong k´ın l`a ellipse . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126  
4 Tˆo m`au vu`ng  
127  
4.1 C´ac d¯inh ngh˜ıa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127  
.
.
˙’  
4.1.1 Vu`ng d¯inh ngh˜ıa boi pixel . . . . . . . . . . . . . . . . . . . . . . . . 127  
.
5
.
˙’  
4.1.2 Vu`ng d¯inh ngh˜ıa boi d¯a gi´ac . . . . . . . . . . . . . . . . . . . . . . . 129  
.
´
`
4.2 Thuaˆt to´an tˆo m`au theo vˆet dˆau loang . . . . . . . . . . . . . . . . . . . . . 129  
.
4.3 Thuaˆt to´an tˆo m`au theo con chay . . . . . . . . . . . . . . . . . . . . . . . . 131  
.
.
4.4 Thuaˆt to´an tˆo m`au theo biˆen . . . . . . . . . . . . . . . . . . . . . . . . . . 134  
.
4.5 So s´anh c´ac thuaˆt to´an . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144  
.
.
4.6 Tˆo m`au c´ac h`ınh chu˜ nhˆat . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145  
.
4.7 Thuaˆt to´an tˆo m`au d¯a gi´ac . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147  
.
4.7.1 C´ac d`ong qu´et ngang . . . . . . . . . . . . . . . . . . . . . . . . . . . 150  
˙’  
4.7.2 C´ac manh vun . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151  
.
´
4.7.3 Liˆen kˆet canh v`a thuˆat to´an tr`an . . . . . . . . . . . . . . . . . . . . 151  
.
.
`
4.7.4 Tˆo m`au c´ac d¯a gi´ac chˆong nhau . . . . . . . . . . . . . . . . . . . . . 158  
˜
4.8 Tˆo m`au theo mˆau tˆo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161  
.
`
Phˆan phu luc: Thu viˆen graph2D.h  
163  
171  
. .  
.
˙’  
T`ai liˆeu tham khao  
.
6
.
`
L`oi n´oi d¯ˆau  
.
.
-
˜
`
´
`
˙’  
˙’  
Dˆo hoa m´ay t´ınh l`a mˆot l˜ınh vuc hˆap dˆan cua khoa hoc m´ay t´ınh. Chu´ng ta su dung d¯ˆo hoa  
.
.
.
.
.
.
.
.
˙’  
m´ay t´ınh nhu mˆot cˆong cu d¯ˆe quan s´at thˆong tin trong nhiˆeu l˜ınh vuc kh´ac nhau, bao gˆom  
`
`
.
.
.
. .  
. .  
´
`
˙’  
khoa hoc v`a cˆong nghˆe, ho´a hoc, kiˆen tru´c v`a giai tr´ı. C´ac chuong tr`ınh d¯oˆ hoa tuong t´ac  
.
.
.
.
. .  
.
.
. .  
.
´
´
˙’  
˙’  
cho ph´ep ngu`oi su dung l`am viˆec theo c´ach tu nhiˆen nhˆat: ngu`oi su dung cung cˆap thˆong  
.
.
.
.
.
. .  
˙’  
. .  
tin cho tr`ınh u´ng dung thˆong qua c´ac hoat d¯ˆong bˆen ngo`ai cua ho v`a s˜e nhˆan d¯uoc thˆong  
.
.
.
.
.
.
.
-
˙’  
`
`
`
˙’  
˙’  
tin tro lai bˇang h`ınh anh. Dˆo hoa m´ay t´ınh d¯ang giu´p con ngu`oi thay d¯ˆoi vˆe quan niˆem v`a  
.
.
.
.
.
˙’  
c´ach thu´c su dung m´ay t´ınh.  
.
.
-
`
´
´
`
˙’  
˙’  
Gi´ao tr`ınh Dˆo hoa m´ay t´ınh I cung cˆap mˆot sˆo ky˜ thuaˆt co ban cua d¯ˆo hoa m´ay t´ınh  
.
.
.
.
. .  
. .  
-
˙’  
`
`
`
`
´
hai chiˆeu. (Dˆo hoa m´ay t´ınh ba chiˆeu, mˆot phˆan quan trong khˆong thˆe thiˆeu d¯uoc s˜e d¯uoc  
.
.
.
.
.
.
-
˙’  
´
`
`
˙’  
d¯ˆe cˆap trong mˆot gi´ao tr`ınh kh´ac). Dˆe c´o mˆot khung canh to`an diˆen v`a sˆau sˇac vˆe nhu˜ng  
.
.
.
.
.
. .  
˜
`
˙’  
nguyˆen ly´ v`a thuc h`anh cua d¯ˆo hoa m´ay t´ınh, xem c´ac t`ai liˆeu dˆan [9] v`a [11]. C´ac phuong  
.
.
.
˙’  
ph´ap phˆan t´ıch v`a thiˆet kˆe c´ac thuaˆt to´an trong gi´ao tr`ınh cho ph´ep sinh viˆen c´o thˆe viˆet  
´
´
´
.
. .  
. .  
. .  
˜
´
dˆe d`ang c´ac chuong tr`ınh minh hoa. Gi´ao tr`ınh d¯uoc biˆen soan cho c´ac d¯ˆoi tuong l`a sinh  
.
.
.
.
viˆen Toa´n-Tin v`a Tin hoc.  
.
.
.
˙’  
˙’  
˙’  
˙’  
˜
˙’  
Gi´ao tr`ınh su dung ngˆon ngu˜ C d¯ˆe minh hoa, tuy nhiˆen c´o thˆe dˆe d`ang chuyˆen d¯oˆi  
.
.
.
.
.
`
´
´
`
sang c´ac ngˆon ngu˜ kh´ac; v`a do d¯´o, sinh viˆen cˆan c´o mˆot sˆo kiˆen thu´c vˆe ngˆon ngu˜ C. Ngo`ai  
.
. .  
.
.
`
´
´
´
ra, hˆau hˆet c´ac chuong tr`ınh thao t´ac trˆen cˆau tru´c du˜ liˆeu nhu danh s´ach liˆen kˆet, nˆen d¯o`i  
.
.
´
˙’  
˙’  
hoi sinh viˆen phai c´o nhu˜ng ky˜ nˇang lˆap tr`ınh tˆot.  
.
. .  
.
˙’  
`
`
´ `  
´
˙’  
˙’  
Sinh viˆen cu˜ng cˆan c´o co so to´an hoc cua nhu˜ng nˇam d¯ˆau d¯ai hoc: hiˆeu biˆet vˆe d¯ai sˆo  
.
.
.
.
´
˙’  
tuyˆen t´ınh v`a h`ınh hoc giai t´ıch, ph´ep t´ınh vi t´ıch phˆan.  
.
.
.
.
´
`
˙’  
˙’  
Muc d¯´ıch cua gi´ao tr`ınh l`a, o mu´c d¯oˆ n`ao d¯´o, cho thˆay c´ac tr`ınh u´ng dung d¯ˆo hoa  
.
.
.
.
. .  
.
.
. .  
´
`
´
˙’  
d¯uoc tao ra nhu thˆe n`ao: Chu´ng ta cˆan viˆet v`a chay thu c´ac chuong tr`ınh. Mˆot trong  
.
.
.
.
.
.
. .  
. .  
. .  
´
˙’  
nhu˜ng muc d¯´ıch ch´ınh cua gi´ao tr`ınh l`a giu´p sinh viˆen nˇam vu˜ng c´ac phuong ph´ap, tru´oc  
.
˙’  
´
˙’  
hˆet to´an hoc ho´a c´ac kh´ac niˆem h`ınh hoc v`a sau d¯´o chuyˆen tai th`anh c´ac d¯oan m˜a chuong  
.
.
.
.
tr`ınh.  
7
. .  
.
.
.
`
´
`
Gi´ao tr`ınh bao gˆom bˆon chuong v`a mˆot phˆan phu luc v´oi nhu˜ng nˆoi dung ch´ınh nhu  
.
. .  
.
sau:  
. .  
.
. .  
.
´
`
´
`
˙’  
• Chuong thu´ nhˆat d¯ˆe cˆap d¯ˆen c´ac phuong ph´ap v˜e c´ac “nguyˆen so” cua d¯oˆ hoa m´ay  
.
.
. .  
t´ınh: d¯oan thˇang, d¯u`ong tr`on v`a ellipse.  
˙’  
.
. .  
• Phˆan t´ıch v`a thiˆet kˆe bˇang h`ınh hoc l`a nˆoi dung ch´ınh cua Chuong 2. Hˆau hˆet c´ac  
`
´
´
`
´
˙’  
. .  
.
.
.
.
.
˙’  
phˆan mˆem d¯ˆo hoa d¯ˆeu c´o nhu˜ng chu´c nˇang tao ra c´ac d¯u`ong cong dua trˆen c´ac d¯iˆem  
`
`
`
`
.
.
.
. .  
.
.
. .  
.
´
´
˙’  
m`a ngu`oi su dung lua chon. Chuong n`ay cung cˆap nhu˜ng nguyˆen ly´ v`a c´ach tiˆep cˆan  
.
.
.
.
.
.
`
thuc h`anh m`a c´ac tr`ınh u´ng dung d¯ˆo hoa ´ap dung.  
.
.
.
.
. .  
.
.
´
`
˙’  
˙’  
• Chuong 3 giai quyˆet b`ai to´an x´ac d¯inh giao cua nhu˜ng nguyˆen so d¯ˆo hoa: Giao hai  
.
.
.
˙’  
˙’  
`
˙’  
d¯oan thˇang, giao cua d¯oan thˇang v`a d¯a gi´ac lˆoi (bao h`am c´ac h`ınh chu˜ nhˆat) v`a giao  
.
.
.
. .  
´
`
˙’  
˙’  
cua hai d¯a gi´ac. Cuˆoi chuong l`a mˆot v´ı du cua ky˜ thuˆat “ray tracing” hai chiˆeu:  
.
.
.
.
. .  
˙’  
`
˙’  
Chuyˆen d¯oˆng cua tia s´ang trong buˆong k´ın c´o chu´a c´ac “chu´ong ngai vˆat”.  
.
.
.
. .  
.
.
`
´
. .  
´
˙’  
• Chuong 4 d¯ˆe cˆap d¯ˆen nhu˜ng thuaˆt to´an tˆo m`au vu`ng bˆat ky`: Vu`ng d¯inh ngh˜ıa boi  
.
.
.
.
`
˙’  
phˆan trong, boi d¯u`ong biˆen v`a vu`ng l`a d¯a gi´ac.  
.
.
. .  
`
´
`
´
• Phˆan phu luc l`a thu viˆen c´ac cˆau tru´c du˜ liˆeu v`a c´ac h`am cˆan thiˆet v`a thu`ong xuyˆen  
. .  
.
.
.
˙’  
su dung trong gi´ao tr`ınh.  
.
.
.
`
`
´
˙’  
Trong lˆan xuˆat ban thu´ hai n`ay, chu´ng tˆoi d¯ua thˆem c´ac v´ı du t´ınh to´an nhˇam minh  
.
.
.
.
´
`
´
´
hoa cho phˆan ly´ thuyˆet cu˜ng nhu giu´p sinh viˆen nˇam vu˜ng kiˆen thu´c d¯˜a hoc. Ngo`ai ra, c´ac  
.
.
. .  
. .  
.
˜
˜
˙’  
´
`
˙’  
˙’  
lˆoi trong xuˆat ban lˆan tru´oc cu˜ng d¯a˜ d¯uoc chınh ly´; mˇac du` vˆay, t´ac gia vˆan mong c´o nhu˜ng  
.
.
.
.
d¯´ong g´op tu` ban d¯oc.  
.
.
.
.
.
. .  
.
. .  
˙’  
`
˙’  
Tˆoi xin cam on nhu˜ng giu´p d¯o˜ d¯˜a nhˆan d¯uoc tu` nhiˆeu ngu`oi m`a khˆong thˆe liˆet kˆe  
.
.
.
´
hˆet, d¯ˇac biˆet l`a c´ac ban sinh viˆen, trong qu´a tr`ınh biˆen soan gi´ao tr`ınh n`ay.  
.
.
.
.
-
D`a Lat, ng`ay 10 th´ang 1 nˇam 2005  
.
.
´
PHAM Tiˆen Son  
.
8
. .  
Chuong 1  
. .  
C´ac thuˆat to´an v˜e d¯u`ong cong trˆen  
.
´
thiˆet bi raster  
.
. .  
. .  
˙’  
Chuong n`ay tr`ınh b`ay c´ac thuaˆt to´an v˜e d¯oan thˇang, d¯u`ong tr`on v`a ellipse trˆen lattice  
.
.
2
.
.
´
˙’  
˙’ ˙’  
nguyˆen  
C´ac thuˆat to´an chı thao t´ac trˆen nhu˜ng sˆo nguyˆen v`a trong c´ac v`ong lˇap chı su  
.
.
´
˙’  
dung ph´ep to´an cˆong nˆen rˆat hiˆeu qua.  
.
.
.
-
˙’  
1.1 Doan thˇang  
.
.
˙’  
`
˙’  
`
˙’  
Thuˆat to´an v˜e d¯oan thˇang x´ac d¯inh toa d¯oˆ cua c´ac pixel nˇam trˆen hoˇac gˆan v´oi d¯oan thˇang  
.
.
.
.
.
.
.
.
.
.
´
˙’  
´
thuc tˆe nhˆat. Vˆe nguyˆen tˇac, chu´ng ta muoˆn chon d˜ay c´ac pixel gˆan v´oi d¯oan thˇang thuc tˆe  
´
´
`
´
`
.
.
.
.
.
. .  
.
˙’  
˙’  
´
´
´
´
`
˙’  
nhˆat v`a thˇang nhˆat. X´et d¯oan thˇang thuc tˆe d¯uoc xˆap xı v´oi mˆat d¯oˆ mˆot pixel; ta cˆan c´o  
.
.
.
.
.
.
.
.
˙’  
´
´
nhu˜ng t´ınh chˆat g`ı? V´oi c´ac d¯oan thˇang c´o hˆe sˆo g´oc thuoˆc d¯oan [−1 1] c´o d¯u´ng mˆot pixel  
.
.
.
.
`
.
. .  
.
˜
˙’  
´
d¯uoc v˜e lˆen trˆen mˆoi cˆot; v´oi c´ac d¯oan thˇang m`a hˆe sˆo g´oc nˇam ngo`ai d¯oan n`ay, c´o d¯u´ng  
.
.
.
.
.
. .  
. .  
.
˜
˙’  
´
˙’  
mˆot pixel d¯uoc v˜e trˆen mˆoi h`ang. Tˆat ca c´ac d¯oan thˇang d¯uoc v˜e v´oi cu`ng mˆot d¯oˆ s´ang,  
.
.
.
.
.
.
. .  
. .  
˙’  
´
khˆong phu thuoˆc v`ao d¯ˆo d`ai v`a hu´ong, v`a nhanh nhˆat c´o thˆe d¯uoc. Thuˆat to´an v˜e d¯oan  
.
.
.
.
.
.
.
˙’  
˙’  
˙’  
`
´
˙’  
thˇang cu˜ng cˆan chu´ y´ d¯ˆen c´ac thuoˆc t´ınh cua d¯oan thˇang nhu d¯ˆo rˆong, kiˆeu v˜e... Thˆam ch´ı  
.
.
. .  
.
.
.
.
.
. .  
.
˙’  
˙’  
´
´
chu´ng ta muoˆn cuc tiˆeu ho´a mu´c d¯oˆ rˇang cua do tiˆen tr`ınh r`oi rac ho´a d¯u`ong thˇang thuc  
.
.
.
.
. .  
˙’  
. .  
`
´
˙’  
tˆe nh`o su dung ky˜ thuˆat antialiasing (xem [9], [11]) bˇang c´ach ´ap dung kha nˇang d¯ˇat cu`ong  
.
.
.
.
. .  
.
˙’  
˜
´
`
˙’  
d¯ˆo cua mˆoi pixel trˆen c´ac thiˆet bi hiˆen thi m`a mˆot pixel tuong u´ng nhiˆeu bit.  
.
.
.
.
. .  
Tru´oc hˆet chu´ng ta chı d¯ˆe cˆap d¯ˆen c´ac d¯oan thˇang d¯ˆo rˆong mˆot pixel v`a c´o d¯u´ng mˆot  
˙’  
´
`
´
˙’  
.
.
. .  
.
.
.
. .  
˜
˙’  
´
´
`
´
`
pixel trˆen mˆoi cˆot (hoˇac h`ang d¯ˆoi v´oi c´ac d¯oan thˇang dˆoc). Phˆan cuˆoi chuong s˜e d¯ˆe cˆap  
.
.
.
.
9
.
˜
´
d¯ˆen d¯oˆ rˆong c´ac nguyˆen so v`a c´ac mˆau v˜e.  
. .  
.
.
˙’  
Mˆot c´ach h`ınh hoc, chu´ng ta biˆeu diˆen mˆot pixel nhu mˆot chaˆm tr`on v´oi tˆam tai vi  
.
˜
´
.
.
.
.
.
. .  
2
.
˙’  
Biˆeu diˆen n`ay l`a mˆot xˆap xı th´ıch hop  
˜
´
˙’  
˙’  
tr´ı (  
) cua pixel trˆen lu´oi c´ac toa d¯oˆ nguyˆen  
.
.
.
.
´
´
˙’  
˙’  
´
khoang c´ach (tuy` thuˆoc v`ao hˆe thˆong) giu˜a c´ac vˆet trˆen m`an h`ınh hiˆen thi. Trong mˆot sˆo  
˙’  
nh´at cˇat ngang trong mˆot chu ky` cua chu`m tia electron cua CRT; xˆap xı n`ay phu thuoˆc v`ao  
.
.
.
.
˙’  
´
´
˙’  
.
.
.
.
.
.
.
´
´
`
´
`
´
˙’  
hˆe thˆong, c´ac chaˆm kˆe nhau phu lˆap mˆot phˆan lˆen nhau; v´oi nhu˜ng hˆe thˆong kh´ac c´o nhu˜ng  
.
.
.
.
.
`
`
´
´
˙’  
˙’  
khoang c´ach giu˜a c´ac pixel d¯u´ng kˆe nhau; trong hˆau hˆet c´ac hˆe thˆong, khoang c´ach theo  
.
.
.
.
˙’  
chiˆeu ngang nho hon theo chiˆeu d¯u´ng. Mˆot kh´ac biˆet nu˜a tuy` theo hˆe thˆong trong viˆec biˆeu  
`
`
´
˙’  
diˆen hˆe toa d¯oˆ, chˇang han Macintosh xem c´ac pixel d¯uoc d¯aˇt tai tˆam cua h`ınh chu˜ nhˆat  
.
.
.
.
. .  
.
˜
˙’  
˙’  
. .  
.
.
.
.
.
.
.
. .  
. .  
. .  
˙’  
˙’  
`
˙’  
`
`
˙’  
˙’  
giu˜a c´ac d¯u`ong thˇang kˆe nhau cua lu´oi d¯iˆeu khiˆen thay cho nˇam trˆen c´ac d¯u`ong thˇang cua  
. .  
.
.
`
`
˙’  
trong cua n´o. Dinh ngh˜ıa n`ay cho ph´ep c´ac vu`ng d¯ˆo rˆong bˇang khˆong: H`ınh chu˜ nhˆat tu`  
lu´oi. Theo c´ach n`ay, c´ac h`ınh chu˜ nhˆat (x´ac d¯inh boi hai g´oc) gˆom c´ac pixel thuˆoc phˆan  
.
.
.
.
.
-
`
˙’  
.
. .  
.
.
.
.
´
´
) khˆong chu´a pixel n`ao, trong khi v´oi nhu˜ng hˆe thˆong kh´ac, c´o d¯u´ng mˆot  
. .  
(
) d¯ˆen (  
. .  
.
.
˙’  
˙’  
˜
pixel tai d¯iˆem n`ay. Du´oi d¯aˆy chu´ng ta s˜e biˆeu diˆen c´ac pixel nhu c´ac h`ınh tr`on r`oi nhau c´o  
.
. .  
`
tˆam nˇam trˆen lu´oi.  
. .  
.
˙’  
´
´
˙’  
˙’  
˙’  
H`ınh 1.1 l`a ph´ong to cua d¯u`ong thˇang thuc tˆe v`a xˆap xı d¯oˆ rˆong mˆot pixel cua n´o.  
.
. .  
.
. .  
. .  
.
. .  
. .  
.
C´ac pixel d¯uoc v˜e tuong u´ng c´ac h`ınh tr`on m`au d¯en v`a c´ac pixel khˆong d¯uoc v˜e tuong u´ng  
.
.
.
. .  
.
˙’  
˜
´
˙’  
h`ınh tr`on khˆong tˆo. Trˆen m`an h`ınh thuc tˆe, d¯u`ong k´ınh cua h`ınh tr`on biˆeu diˆen pixel l´on  
.
.
.
.
˙’  
˜
`
`
˙’  
˙’  
˙’  
hon khoang c´ach giu˜a c´ac pixel kˆe nhau, boi vˆay biˆeu diˆen bˇang ky´ hiˆeu cua chu´ng ta l`a  
.
.
.
.
˙’  
mˆot ph´ong d¯ai mu´c d¯ˆo r`oi rac cua c´ac pixel.  
.
.
.
.
. .  
.
-
˙’  
˙’  
˜
´
˙’  
˙’  
H`ınh 1.1: Doan thˇang xˆap xı d¯uoc biˆeu diˆen boi c´ac h`ınh tr`on d¯en.  
.
.
.
. .  
˙’  
´
`
V`ı c´ac nguyˆen so trong hˆe thˆong chu´ng ta x´ac d¯inh trˆen lu´oi d¯iˆeu khiˆen nguyˆen nˆen  
.
.
.
˙’  
´
˙’  
`
´
´
˙’  
c´ac toa d¯ˆo d¯ˆau cuˆoi cua d¯oan thˇang l`a nguyˆen. Thˆat ra, nˆeu chu´ng ta cˇat d¯oan thˇang v´oi  
.
.
.
.
.
.
. .  
˙’  
˙’  
˙’  
˙’  
˙’  
`
´
˙’  
h`ınh chu˜ nhˆat tru´oc khi hiˆen thi n´o th`ı toa d¯ˆo c´ac d¯iˆem d¯ˆau cuˆoi cua d¯oan thˇang c´o thˆe  
.
.
.
.
.
˙’  
`
˙’  
khˆong nguyˆen. (Chu´ng ta s˜e thao luˆan c´ac giao d¯iˆem khˆong nguyˆen trong Phˆan 1.1.3). Gia  
.
10  
.
. .  
.
. .  
.
. .  
. .  
.
.
.
˙’  
´
˙’  
˙’  
su d¯oan thˇang c´o hˆe sˆo g´oc | | ≤ 1; c´ac tru`ong hop kh´ac d¯uoc xu ly´ tuong tu. Hon nu˜a  
.
.
.
.
.
. .  
.
.
˙’  
. .  
´
`
˙’  
tru`ong hop c´ac d¯oan thˇang ngang, d¯u´ng hoˇac c´o hˆe sˆo g´oc ±1 l`a tˆam thu`ong v`ı chu´ng chı  
d¯i qua c´ac pixel trˆen lu´oi.  
.
.
.
.
´
1.1.1 Thuˆat to´an sˆo gia  
.
.
. .  
`
˙’ ˙’  
X´et hai pixel = (  
) v`a = (  
c´o dang  
) (tu´c c´ac phˆan tu cua lattice nguyˆen 2) Phuong  
´
. .  
˙’  
tr`ınh d¯u`ong thˇang  
.
=
+ trong d¯´o hˆe sˆo g´oc  
.
=
v`a =  
−
.
˙’  
˙’  
´
˙’  
C´ach d¯on gian nhˆat d¯ˆe v˜e d¯oan thˇang  
l`a:  
.
´
1. T´ınh hˆe sˆo g´oc  
;
.
.
.
.
.
˙’  
˜
`
´
˙’  
2. Tˇang mˆot d¯on vi (khoi d¯ˆau tu` d¯iˆem bˆen tr´ai nhˆat), v´oi mˆoi t´ınh  
=
+ v`a  
.
.
sau d¯´o v˜e pixel tai ( b + 0 5c)1.  
.
.
. .  
.
˙’  
´
´
´
˙’  
. .  
Theo c´ach n`ay ta chon pixel tˆot nhˆat, tu´c l`a pixel m`a khoang c´ach d¯ˆen d¯u`ong thˇang thuc  
.
.
. .  
˜
´
´
`
˙’  
˙’  
tˆe nho nhˆat. Phuong ph´ap n`ay khˆong hiˆeu qua do mˆoi bu´oc lˇap cˆan t´ınh mˆot ph´ep nhˆan,  
.
.
.
.
˙’  
`
`
˙’  
mˆot ph´ep cˆong v`a mˆot ph´ep to´an l`am tr`on. Ta c´o thˆe khu ph´ep nhˆan bˇang c´ach chu´ y´ rˇang  
.
.
.
=
=
=
+
+1  
+1  
(
+ ∆ ) +  
∆
+
. .  
v`a nˆeu bu´oc tˇang ∆ = 1 th`ı  
´
=
+
+1  
.
.
.
˙’  
´
Do d¯o´ nˆeu tˇang mˆot d¯on vi th`ı tˇang  
d¯on vi. V´oi moi d¯iˆem (  
) trˆen d¯oan  
.
.
.
.
.
.
. .  
˙’  
`
´
´
thˇang ta biˆet rˇang nˆeu  
. .  
=
+ 1 th`ı  
=
+1  
+
; tu´c l`a, c´ac gi´a tri v`a d¯uoc t´ınh  
+1  
.
.
.
-
˜
´
˙’  
theo c´ac gi´a tri tru´oc d¯´o cua n´o (xem H`ınh 1.2). Dˆay ch´ınh l`a “thuaˆt to´an sˆo gia”: v´oi mˆoi  
.
.
. .  
.
.
. .  
. .  
´
bu´oc lˇap ta thuc hiˆen c´ac ph´ep to´an sˆo gia dua trˆen bu´oc tru´oc.  
.
.
.
.
.
˙’  
0) l`a toa d¯oˆ nguyˆen cua d¯iˆem xuˆat ph´at, chˇang han  
˙’  
´
˙’  
Khoi tao ta g´an (  
˙’  
Chu´ y´  
0
.
.
.
.
. .  
.
.
.
.
`
´
rˇang trong tru`ong hop | | 1 nˆeu tˇang mˆot d¯on vi th`ı tˇang hon mˆot d¯on vi. Do d¯´o  
.
.
.
.
.
. .  
.
˙’  
`
`
˙’  
cˆan ho´an d¯oˆi vai tr`o cua v`a bˇang c´ach g´an bu´oc tˇang mˆot d¯on vi cho v`a tˇang mˆot  
.
.
.
∆
1
. .  
luong ∆ =  
.
=
1
b c  
d e  
11  
. .  
-
˙’  
Du`ong thˇang  
.
´
thuc tˆe  
.
(
+ 1 d + e)  
(
)
(
b c)  
(
+ 1  
+
)
´
˙’  
H`ınh 1.2: T´ınh to´an sˆo gia cua (  
)
.
. .  
˙’  
˙’  
´
˙’ ˙’  
V´ı du 1.1.1 Gia su (2 0) (9 3) Khi d¯´o d¯u`ong thˇang qua hai d¯iˆem v`a  
c´o hˆe sˆo  
.
.
3
. .  
.
´
˙’  
´
´
´
g´oc  
˙’  
=
∈ (0 1) Ap dung thuaˆt to´an sˆo gia ta d¯uoc d˜ay c´ac d¯iˆem v˜e tˆot nhˆat nhu trong  
.
.
.
7
. .  
bang du´oi:  
b + 0 5c  
0
1
2
3
4
5
6
7
2
3
4
5
6
7
8
9
0
3
7
6
7
9
7
12  
7
15  
7
0
0
1
1
2
2
3
3
18  
7
21  
7
. .  
.
˙’  
´
˙’  
Thu tuc Line() du´oi d¯aˆy minh hoa thuˆat to´an v˜e d¯oan thˇang tu` (  
0) d¯ˆen (  
)
0
1
1
.
.
.
.
.
.
. .  
.
-
˙’  
˙’  
`
´
˙’  
˙’  
v´oi gi´a tri m`au  
Diˆem khoi d¯ˆau l`a d¯iˆem bˆen tr´ai nhˆat. Ngo`ai ra ta chı x´et tru`ong hop  
.
.
. .  
.
.
.
.
.
˙’  
´
−1 ≤ ≤ 1 v`ı c´ac tru`ong hop kh´ac c´o thˆe thuc hiˆen do t´ınh d¯oˆi xu´ng. Hon nu˜a, chu´ng ta  
.
.
.
. .  
.
. .  
.
˙’  
˙’  
`
˙’  
cu˜ng bo qua viˆec kiˆem tra c´ac tru`ong hop d¯aˇc biˆet: d¯u`ong thˇang nˇam ngang, d¯u´ng, xiˆen  
.
.
.
.
0
.
`
`
mˆot g´oc ±45 Chu´ y´ rˇang, trong ngˆon ngu˜ C, (int) bˇang b + 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 Thuˆat to´an d¯iˆem giu˜a  
.
.
.
´
˙’  
Thu tuc Line() thao t´ac trˆen c´ac sˆo thuc v`a  
Bresenham d¯˜a xˆay dung thuaˆt to´an [2] v˜e  
. .  
.
.
.
˙’  
´
˙’ ˙’  
d¯oan thˇang chı su dung c´ac ph´ep to´an trˆen sˆo nguyˆen do d¯´o tr´anh goi h`am l`am tr`on v`a cho  
.
.
.
.
.
.
. .  
. .  
´
˙’  
ph´ep x´ac d¯inh (  
.
+1) theo sˆo gia dua trˆen nhu˜ng gi´a tri o bu´oc tru´oc (  
) Thuˆat  
.
+1  
.
.
.
.
.
.
.
. .  
˙’  
´
´
´
˙’  
to´an n`ay c´o thˆe mo rˆong dang dˆau chaˆm d¯ˆong d¯oˆi v´oi c´ac toa d¯ˆo thuc. Hon nu˜a, phuong  
.
.
.
.
.
.
. .  
. .  
˙’  
´
˙’  
ph´ap cua Bresenham c´o thˆe d¯uoc ´ap dung t´ınh to´an trˆen sˆo nguyˆen v˜e d¯u`ong tr`on mˇac du`  
.
.
.
.
.
. .  
. .  
˜
˙’  
˙’  
n´o khˆong dˆe d`ang mo rˆong cho conic tuy` y´. V`ı vˆay chu´ng ta su dung phuong ph´ap tuong  
.
.
.
.
. .  
.
. .  
˙’  
´
´ `  
`
˙’  
d¯ˆoi kh´ac, thuaˆt to´an d¯iˆem giu˜a, d¯uoc cˆong bˆo lˆan d¯ˆau tiˆen boi Pitteway [16], [17] v`a d¯uoc  
.
.
.
.
.
´
´
´
˙’  
˙’  
˙’  
˙’  
cai tiˆen boi Van Aken [26] v`a mˆot sˆo t´ac gia kh´ac [28], [29]. Van Aken d¯˜a chı ra [26] d¯ˆoi v´oi  
.
. .  
. .  
.
.
.
.
.
˙’  
˙’  
c´ac d¯u`ong thˇang v`a d¯u`ong tr`on v´oi du˜ liˆeu nguyˆen, cˆong thu´c d¯iˆem giu˜a suy ra cˆong thu´c  
.
˙’  
cua Bresenham v`a do d¯´o sinh ra cu`ng d˜ay c´ac pixel.  
.
. .  
cua d¯u`ong thˇang thuoˆc khoang (0 1)  
˙’  
Khˆong mˆat t´ınh tˆong qu´at, gia su hˆe sˆo g´oc  
˙’  
´
´
˙’ ˙’  
˙’  
˙’  
.
.
. .  
.
. .  
.
.
.
.
˙’  
´
´
˙’  
˙’  
˙’  
(c´ac tru`ong hop kh´ac c´o thˆe d¯uoc xu ly´ boi c´ac ph´ep lˆay d¯oˆi xu´ng mˆot c´ach th´ıch hop qua  
.
.
.
.
˙’  
´
´
c´ac truc toa d¯oˆ). Ta cu˜ng ky´ hiˆeu d¯iˆem xuˆat ph´at l`a (  
) v`a d¯iˆem kˆet thu´c l`a (  
˙’  
)
.
.
.
.
. .  
. .  
-
˙’  
Dˇat  
:=  
−
=
−
Phuong tr`ınh d¯u`ong thˇang qua hai d¯iˆem v`a  
x´ac  
.
.
˙’  
d¯inh boi  
.
=
+ ;  
13  
−
( )  
+
( )  
. .  
˙’  
H`ınh 1.3: Lu´oi c´ac pixel v`a vi tr´ı d¯iˆem  
v`a  
.
. .  
. .  
hay tuong d¯uong  
(
) :=  
+
+ = 0  
.
.
˙’  
˙’  
˙’  
trong d¯´o  
=
= −  
v`a = ×  
Ky´ hiˆeu c´ac nua mˇat phˇang ngo`ai v`a nua mˇat  
.
.
.
.
. .  
.
.
˙’  
˙’  
˙’  
phˇang trong x´ac d¯inh boi tuong u´ng boi  
.
+
( ) := {(  
) ∈ R2 | (  
) ∈ R2 | (  
)
)
0}  
0}  
−
( ) := {(  
. .  
˙’  
.
.
´
˙’  
˙’  
´
´
˙’  
Y tuong cua thuˆat to´an d¯iˆem giu˜a l`a xˆay dung mˆot d˜ay c´ac d¯iˆem v˜e “tˆot nhˆat” (  
)
.
.
.
.
.
.
. .  
˙’  
bˇat d¯ˆau tu` d¯iˆem (  
˙’  
´
`
´
´
˙’  
0) = (  
) Kh´ai niˆem tˆot nhˆat o d¯ˆay l`a nhu˜ng d¯iˆem (  
) d¯uoc  
.
0
.
.
. .  
.
˙’  
`
´
´
´
˙’  
chon gˆan v´oi d¯u`ong thˇang thuc tˆe (dang liˆen tuc) nhˆat. Theo gia thiˆet, 0  
1 nˆen khi  
.
.
.
.
.
. .  
.
tˇang mˆot luong ∆ th`ı tˇang khˆong qu´a ∆ = ∆ d¯on vi.  
.
.
.
. .  
.
. .  
.
. .  
˙’  
´
´
´
˙’  
V`ı vˆay nˆeu bu´oc thu´ chon d¯uoc d¯iˆem v˜e tˆot nhˆat := (  
) th`ı o bu´oc thu´ + 1  
.
.
.
˙’  
ta s˜e chon d¯iˆem v˜e (  
+1) trong d¯o´  
=
+ 1 v`a  
=
hoˇac  
=
+1  
+ 1  
+1  
+1  
+1  
.
.
. .  
.
N´oi c´ach kh´ac, bu´oc thu´ + 1 chu´ng ta s˜e chon mˆot trong hai pixel := ( + 1 ) hoˇac  
.
.
.
. .  
˙’  
˙’  
˙’  
:= ( + 1 + 1) (xem H`ınh 1.3). Ky´ hiˆeu  
l`a giao d¯iˆem cua hai d¯u`ong thˇang v`a  
.
.
.
.
.
˙’  
´
˙’  
˙’  
˙’  
=
+ 1 Theo Bresenham, dˆau cua biˆeu thu´c x´ac d¯inh boi hiˆeu giu˜a hai khoang c´ach tu`  
.
.
.
. .  
.
˙’  
´
´
´
˙’  
v`a d¯ˆen cho ph´ep x´ac d¯inh pixel tˆot nhˆat o bu´oc + 1 Trong thuˆat to´an d¯iˆem giu˜a,  
.
.
.
.
.
. .  
˙’  
ta quan s´at vi tr´ı cua d¯iˆem giu˜a  
˙’  
˙’  
˜
˙’  
˙’  
˙’  
v`a c´ac nua mˇat phˇang x´ac d¯inh boi d¯u`ong thˇang Dˆe  
.
.
.
+
.
. .  
.
−
`
˙’  
´
`
´
˙’  
d`ang chı ra rˇang, nˆeu  
∈ ( ) th`ı pixel  
gˆan v´oi d¯u`ong thˇang hon; nˆeu  
∈ ( ) th`ı  
.
. .  
-
˙’  
˙’  
`
`
`
˙’  
pixel  
gˆan hon. Du`ong thˇang c´o thˆe d¯i ngang qua ; hoˇac ca hai pixel nˇam vˆe cu`ng  
.
.
+
−
.
.
. .  
.
˙’  
˙’  
˜
´
˙’  
mˆot nua mˇat phˇang ( ) (hoˇac ( )) nhung trong bˆat cu´ tru`ong hop n`ao, ta vˆan chon d¯iˆem  
.
.
.
.
.
.
.
.
.
.
. .  
. .  
˙’  
`
´
´
˙’  
gˆan v´oi nhˆat. Hon nu˜a, sai sˆo-tu´c l`a khoang c´ach giu˜a pixel d¯uoc chon v`a d¯u`ong thˇang  
.
.
.
.
`
´
˙’  
thuc tˆe -luˆon luˆon nho hon hoˇac bˇang 1/2.  
.
.
14  
1
2
.
-
˙’  
˙’  
˙’  
`
˙’  
Dˆe ´ap dung thuaˆt to´an d¯iˆem giu˜a, chı cˆan t´ınh ( ) = ( + 1 + ) v`a kiˆem tra  
.
.
´
´
´
˙’  
dˆau cua n´o. Do d¯´o ta d¯inh ngh˜ıa biˆen quyˆet d¯inh  
.
.
1
:=  
=
(
(
+ 1 + )  
2
1
2
+ 1) + ( + ) +  
Khi d¯´o  
´
1. Nˆeu  
0 chon pixel  
;
.
´
2. Nˆeu  
0 chon pixel  
;
.
´
3. Nˆeu = 0 chon mˆot trong hai pixel hoˇac  
do d¯´o chon  
.
.
.
.
.
.
. .  
˙’  
Kˆe tiˆep ta cˆan x´ac d¯inh toa d¯ˆo d¯iˆem giu˜a  
´ ´  
`
´
´
˙’  
v`a do d¯o´ biˆen quyˆet d¯inh  
o bu´oc + 1;  
˙’  
+1  
.
.
.
.
`
´
d˜ı nhiˆen d¯iˆeu n`ay phu thuˆoc v`ao viˆec chon pixel hoˇac  
Nˆeu chon th`ı ho`anh d¯oˆ d¯iˆem  
.
.
.
.
.
.
.
.
˙’  
tˇang mˆot d¯on vi v`a tung d¯oˆ khˆong d¯oˆi. Do d¯o´  
.
.
.
1
1
= ( + 2 + ) = ( + 2) + ( + ) +  
+1  
2
2
.
Nhung  
1
= ( + 1) + ( + ) +  
2
Suy ra  
=
+
+1  
. .  
. .  
´
Ky´ hiˆeu sˆo gia d¯uoc cˆong thˆem khi d¯uoc chon l`a ∆ :=  
=
.
N´oi c´ach kh´ac, ta  
. .  
`
.
.
.
.
.
.
. .  
.
˙’  
´
´
´ ´  
´
´
˙’  
˙’  
c´o thˆe suy ra biˆen quyˆet d¯inh o bu´oc kˆe tiˆep tu` biˆen quyˆet d¯inh o bu´oc hiˆen h`anh bˇang  
.
.
.
´
`
˙’  
c´ach cˆong thˆem sˆo gia ∆ m`a khˆong cˆan phai t´ınh lai gi´a tri (  
)
.
.
.
.
˙’  
Nˆeu chon th`ı ho`anh d¯oˆ v`a tung d¯oˆ d¯iˆem  
´
cu`ng tˇang mˆot d¯on vi, nˆen  
.
.
.
.
.
3
3
= ( + 2 + ) = ( + 2) + ( + ) +  
+1  
2
2
V`a do d¯´o  
=
+ +  
+1  
. .  
´
Ky´ hiˆeu sˆo gia d¯uoc cˆong v`ao  
sau khi chon l`a ∆ := + =  
.
−
+1  
.
.
.
.
. .  
.
.
˙’  
`
´
˙’  
˙’  
V`ı o bu´oc d¯aˆu tiˆen, ta chon (  
0) = (  
) nˆen c´o thˆe t´ınh truc tiˆep gi´a tri khoi  
0
.
.
.
1
2
.
˙’  
Thˆat vˆay, d¯iˆem giu˜a d¯ˆau tiˆen c´o toa d¯ˆo ( 0 + 1 0 + ) v`a  
`
tao  
.
0
.
.
.
.
1
2
1
(
0 + 1 0 + ) =  
( 0 + 1) + ( 0 + ) +  
2
=
=
+
0 + + +  
0) + +  
2
0
(
2
0
15  
.
. .  
0) thuoˆc d¯u`ong thˇang nˆen (  
.
˙’  
`
´
˙’  
˙’  
Nhung (  
0) = 0; do d¯´o gi´a tri khoi d¯ˆau cua biˆen  
0
0
.
.
.
.
.
˙’  
´
˙’  
2 Su dung  
quyˆet d¯inh l`a  
=
˜
+
´
2 =  
−
ta c´o thˆe chon pixel thu´ hai, thu´  
.
0
0
.
.
.
.
-
˙’  
`
˙’  
ba, v.v. Dˆe khu mˆau sˆo trong  
ta d¯inh ngh˜ıa lai h`am bˇang c´ach nhˆan n´o cho 2; tu´c l`a  
0
.
.
`
´
´ ´  
v`a biˆen quyˆet d¯inh;  
.
(
) = 2(  
+
+ ) N´oi c´ach kh´ac, nhˆan 2 cho c´ac hˇang sˆo  
. .  
`
´
´
´
´
˙’  
˙’  
˙’  
m`a d¯iˆeu n`ay khˆong anh huong d¯ˆen dˆau cua biˆen quyˆet d¯inh.  
.
.
. .  
.
˙’  
˙’  
˙’  
Tˆong qu´at ho´a thuˆat to´an d¯iˆem giu˜a v˜e d¯oan thˇang  
(trong tru`ong hop  
.
.
.
.
v`a 0  
1) nhu sau:  
.
-
˙’  
1. [Khoi tao] Dˇat  
=
−
=
−
= 2  
−
∆ = 2 ∆ = 2(  
−
0
.
.
)
=
=
0
0
. . . .  
˙’ ˙’ ˙’  
.
˙’  
2. Gia su o bu´oc thu´ ta c´o d¯iˆem v˜e tˆot nhˆat (  
´
´
´
´
) v`a biˆen quyˆet d¯inh  
.
-
˙’  
3. [V˜e pixel hiˆen h`anh] Dˇat d¯iˆem v˜e tai (  
)
.
.
.
.
. .  
´
4. [Cˆap nhˆat] Nˆeu  
=
thuˆat to´an du`ng; nguoc lai, d¯aˇt  
.
.
.
.
.
.
=
=
+ 1;  
+1  
+1  
´
nˆeu ≤ 0  
. .  
´
+ 1 nˆeu nguoc lai;  
.
.
´
+ ∆ nˆeu ≤ 0  
=
+1  
. .  
´
+ ∆ nˆeu nguoc lai.  
.
.
. .  
5. Thay bˇang ( + 1) v`a lˇap lai Bu´oc 3.  
`
.
.
.
. .  
˙’  
˙’  
´
˙’ ˙’  
V´ı du 1.1.2 Gia su (2 0) (9 3) Khi d¯´o d¯u`ong thˇang qua hai d¯iˆem v`a  
c´o hˆe sˆo  
.
.
3
˙’  
˜
`
g´oc  
=
∈ (0 1) Dˆe d`ang kiˆem tra rˇang  
7
=
=
−
−
−
=
=
7
3
= 2  
= −1  
=
0
∆
∆
= 2  
6
= 2(  
−
) = −8  
16  
.
.
. .  
´
˙’  
˙’  
´
´
˙’  
Ap dung thuaˆt to´an d¯iˆem giu˜a ta c´o d˜ay c´ac d¯iˆem v˜e tˆot nhˆat nhu trong bang du´oi:  
.
.
0
1
2
3
4
5
6
7
2
3
4
5
6
7
8
9
0
0
1
1
2
2
3
3
−1  
5
−3  
3
−5  
1
−7  
−1  
.
.
. .  
˙’  
`
´
´
´
˙’  
˙’  
˙’  
Hiˆen nhiˆen rˇang c´ac kˆet qua n`ay tru`ng v´oi kˆet qua khi su dung phuong ph´ap sˆo gia trong  
.
V´ı du 1.1.1.  
.
.
. .  
trong mˆoi bu´oc lˇap l`a ph´ep cˆong v`a khˆong  
`
˜
`
´
´
Chu´ y´ rˇang, ph´ep t´ınh cˆan thiˆet d¯oˆi v´oi  
+1  
.
.
.
.
.
.
˙’  
˙’  
c´o ph´ep nhˆan. Hon nu˜a, v`ong lˇap ho`an to`an d¯on gian nhu trong thu tuc MidPointLine()  
.
.
. .  
du´oi d¯ˆay:  
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 Mˆot sˆo vˆan d¯ˆe liˆen quan d¯ˆen thuˆat to´an v˜e d¯oan thˇang  
´ ´  
`
´
.
.
.
.
.
.
˙’  
Thu´ tu cua c´ac d¯iˆem d¯ˆau cuˆoi. Trong mˆot u´ng dung ta cˆan d¯`oi hoi mˆot d¯oan thˇang  
˙’  
`
´
`
˙’  
˙’  
.
.
.
.
.
. .  
.
.
.
. .  
.
˙’  
´
d¯ˆen  
´
d¯uoc v˜e tu`  
chu´a cu`ng tˆap c´ac pixel nhu d¯oan thˇang d¯uoc v˜e tu`  
d¯ˆen ; n´oi  
.
.
.
.
.
. .  
. .  
˙’  
˙’  
`
´
c´ach kh´ac, d¯oan thˇang d¯uoc v˜e khˆong phu thuˆoc v`ao thu´ tu c´ac d¯iˆem d¯aˆu cuˆoi. Su sai kh´ac  
.
.
.
.
.
.
.
. .  
.
˙’  
˙’  
˙’  
˙’  
´
´
˙’  
˙’  
chı c´o thˆe xay ra tai nhu˜ng d¯iˆem v˜e m`a d¯u`ong thˇang d¯i qua d¯iˆem giu˜a v`a biˆen quyˆet d¯inh  
.
.
. .  
.
.
˙’  
`
˙’  
bˇang khˆong; trong tru`ong hop n`ay, d¯i tu` tr´ai sang phai chu´ng ta chon d¯iˆem v˜e  
Do t´ınh  
.
.
.
.
.
.
˙’  
´
˙’  
d¯ˆoi xu´ng, khi d¯i tu` phai sang tr´ai v`a = 0 l˜e ra ta chon d¯iˆem v˜e  
nhung chon lua n`ay s˜e  
.
.
.
.
.
. .  
.
`
˙’  
sai lˆech mˆot d¯on vi theo th`anh phˆan v´oi pixel d¯uoc chon khi d¯i tu` tr´ai sang phai. Do d¯´o  
.
.
.
.
.
.
. .  
.
. .  
`
˙’  
chu´ng ta cˆan chon pixel khi d¯i tu` phai sang tr´ai trong tru`ong hop = 0 Ly´ luˆan tuong  
.
.
.
.
.
˙’  
tu d¯oˆi v´oi c´ac d¯oan thˇang c´o hˆe sˆo g´oc bˆat ky`.  
´
´
´
.
.
.
. .  
.
˙’  
˙’  
˙’  
˙’  
`
´
˙’  
˙’  
Phuong ph´ap ho´an d¯ˆoi c´ac d¯iˆem d¯ˆau cuˆoi cua d¯oan thˇang d¯ˆe thuˆat to´an xu ly´ theo  
.
.
. .  
.
˙’  
˜
cu`ng hu´ong khˆong thuc hiˆen ch´ınh x´ac khi chu´ng ta v˜e c´ac d¯oan thˇang theo mˆau tˆo. C´ac  
.
.
.
. .  
.
˙’  
˙’  
˙’  
˙’  
˜
´
´
d¯oan thˇang v˜e theo mˆau thu`ong “neo” nhu˜ng dˆau hiˆeu tai d¯iˆem xuˆat ph´at, c´o thˆe l`a d¯iˆem  
.
.
.
. .  
. .  
.
-
˙’  
˜
´
du´oi bˆen tr´ai, khˆong phu thuoˆc v`ao hu´ong di chuyˆen. Dˇac biˆet, v´oi mˆau tˆo chaˆm-gach,  
.
.
.
.
.
.
˙’  
˙’  
˙’  
˜
´
´
chˇang han 111100, chu´ng ta muˆon v˜e mˆau n`ay tai d¯iˆem xuˆat ph´at m`a khˆong tu d¯ˆong d¯ˆoi  
.
.
.
.
. .  
˙’  
˙’  
´
`
´
th`anh d¯iˆem du´oi bˆen tr´ai. Ngo`ai ra, nˆeu thuˆat to´an luˆon luˆon d¯aˇt lai c´ac d¯iˆem d¯aˆu cuˆoi  
.
.
.
.
.
.
.
.
˙’  
´
˙’  
`
˙’  
˙’  
theo thu´ tu ch´ınh tˇac, ta cˆan di chuyˆen tu` tr´ai sang phai v´oi d¯oan thˇang  
v`a tu` phai  
˙’  
.
.
.
.
˙’  
`
sang tr´ai v´oi d¯oan thˇang  
; d¯iˆeu n`ay tao ra su gi´an d¯oan trong qu´a tr`ınh v˜e, chaˇng han  
.
.
.
.
.
.
˙’  
d¯a gi´ac, tai nhu˜ng d¯ınh chung.  
.
-
˙’  
`
´
´
´
`
`
˙’  
Diˆem xuˆat ph´at nˇam trˆen canh cua d¯a gi´ac cˇat. Mˆot vˆan d¯ˆe kh´ac chu´ng ta cˆan  
.
.
.
. .  
.
˙’  
˙’  
˙’  
´
˙’  
˙’  
sua d¯ˆoi thuaˆt to´an d¯ˆe v˜e c´ac d¯oan thˇang sau khi d¯uoc cˇat boi mˆot trong c´ac thuˆat to´an  
.
.
.
.
.
. .  
.
˙’  
´
`
˙’  
trong Phˆan 3.3. H`ınh 1.4(a) minh hoa d¯oan thˇang d¯uoc cˇat boi canh bˆen tr´ai,  
=
min  
.
.
.
.
.
˙’  
˙’  
˙’  
˙’  
cua h`ınh chu˜ nhˆat. Giao d¯iˆem cua d¯oan thˇang v`a canh bˆen tr´ai c´o ho`anh d¯ˆo nguyˆen  
.
.
.
.
.
.
nhung tung d¯oˆ thuc. Pixel (  
b
+ + 0 5c) trˆen canh  
=
ch´ınh l`a pixel  
min  
min  
min  
.
.
.
. .  
. .  
˙’  
˙’ ´  
˙’  
cua d¯oan thˇang tru´oc khi cˇat theo thuaˆt to´an d¯iˆem giu˜a . V´oi  
. .  
. 2  
.
d¯uoc v˜e tai ho`anh d¯oˆ  
min  
.
.
.
.
.
.
˙’  
´
´ ´  
`
´
´
˙’  
˙’  
pixel khoi tao d¯a˜ biˆet, kˆe tiˆep chu´ng ta cˆan khoi tao biˆen quyˆet d¯inh tai d¯iˆem giu˜a d¯oan  
.
.
.
.
.
`
´
`
trong cˆot kˆe bˆen. Cˆan chu´ y´ rˇang, c´ach l`am n`ay tao ra d˜ay ch´ınh x´ac c´ac pixel, trong  
.
.
2
min  
18  
=
min  
—
(
b
min + + 0 5c)  
min  
(
min + )  
min  
•
=
min  
(a)  
=
min  
=
min  
1
2
•
=
=
−
min  
min − 1  
(b)  
.
.
.
-
˙’  
`
´
H`ınh 1.4: Diˆem xuˆat ph´at nˇam trˆen biˆen h`ınh chu˜ nhˆat. (a) Giao v´oi canh d¯u´ng. (b) Giao  
.
.
.
v´oi canh ngang.  
.
19  
. .  
. .  
.
. .  
.
´
˙’  
˙’  
´
khi cˇat d¯u`ong thˇang theo d¯u`ong biˆen  
´
v`a sau d¯´o thuc hiˆen v˜e d¯oan thˇang d¯uoc cˇat tu`  
min  
.
.
.
.
.
˙’  
˙’  
(
b
min + + 0 5c) d¯ˆen (  
ch´ınh x´ac do d¯u`ong thˇang sau khi cˇat c´o hˆe sˆo g´oc kh´ac  
) theo thuˆat to´an d¯iˆem giu˜a s˜e cho d˜ay d¯iˆem v˜e khˆong  
min  
.
. .  
˙’  
´
´
.
. .  
.
.
.
. .  
.
. .  
.
˙’  
˙’  
`
Tru`ong hop phu´c tap hon khi d¯u`ong thˇang  
giao v´oi d¯u`ong thˇang nˇam ngang nhu  
`
`
.
.
´
´
˙’  
trong H`ınh 1.4(b). Khi hˆe sˆo g´oc  
rˆat nho, c´o nhiˆeu pixel nˇam trˆen d`ong qu´et  
=
min  
.
. .  
.
. .  
.
´
˙’  
tuong u´ng canh bˆen du´oi cua h`ınh chu˜ nhˆat. Chu´ng ta muoˆn bao h`am c´ac pixel n`ay trong  
.
.
.
.
.
˙’  
h`ınh chu˜ nhˆat, nhung do qu´a tr`ınh t´ınh to´an giao d¯iˆem v´oi d`ong qu´et  
=
v`a sau d¯´o  
.
min  
.
. .  
´
˙’  
l`am tr`on ho`anh d¯oˆ ta d¯uoc pixel khˆong phai pixel bˆen tr´ai nhˆat trˆen d`ong n`ay. Dua  
.
.
.
˙’  
`
´
´
˙’  
˙’  
trˆen h`ınh v˜e, ta thˆay rˇang pixel bˆen tr´ai nhˆat l`a pixel trˆen bˆen phai giao d¯iˆem cua d¯oan  
.
1
2
. .  
v`a d¯u`ong thˇang  
˙’  
thˇang  
˙’  
`
˙’  
=
−
)
Do d¯´o, ta chı cˆan t`ım v`a l`am tr`on lˆen ho`anh d¯oˆ;  
min  
min  
.
`
pixel d¯ˆau tiˆen ch´ınh l`a (d e  
˙’  
.
.
. .  
.
˙’  
´
´
`
Cuˆoi cu`ng, thuˆat to´an d¯iˆem giu˜a cu˜ng thuc hiˆen tˆot trong tru`ong hop c´ac d¯iˆem d¯ˆau  
.
.
.
.
.
. .  
´
´
´
cuˆoi c´o toa d¯ˆo thuc; kh´ac biˆet duy nhˆat l`a bu´oc tˇang v`a c´ac ph´ep to´an thao t´ac trˆen sˆo  
.
.
.
.
.
thuc.  
.
. .  
˙’  
˙’  
˙’  
´
˙’  
Thay d¯ˆoi cu`ong d¯ˆo s´ang cua d¯oan thˇang theo hˆe sˆo g´oc. X´et hai d¯oan thˇang trong  
.
.
.
.
√
-
˙’  
`
´
`
˙’  
H`ınh 1.5. Doan thˇang c´o hˆe sˆo g´oc 1 v`a do d¯o´ c´o d¯oˆ d`ai bˇang 2 lˆan d¯oˆ d`ai cua  
Chu´ng  
. .  
2
1
.
´
.
.
.
. .  
˜
˙’  
˜
´
˙’  
ta d¯ˇat cu`ng sˆo (10) pixel trˆen mˆoi d¯oan thˇang. Nˆeu cu`ong d¯ˆo cua mˆoi pixel l`a th`ı cu`ong  
.
.
.
√
.
.
˙’  
d¯ˆo trˆen mˆot d¯on vi d¯ˆo d`ai cua d¯oan thˇang l`a trong khi cua l`a  
´
˙’  
˙’  
2; su khˆong nhˆat  
1
2
.
.
. .  
.
.
.
. .  
.
˜
´
˙’  
˙’  
qu´an n`ay dˆe d`ang ph´at hiˆen boi ngu`oi quan s´at. Trˆen m`an h`ınh d¯on sˇac, khˆong c´o c´ach giai  
.
.
. .  
˙’  
´
´
˙’  
quyˆet, nhung trˆen hˆe thˆong -bit trˆen pixel chu´ng ta c´o thˆe cai thiˆen d¯uoc t`ınh trang n`ay  
.
.
.
.
. .  
`
´
´
´
˙’  
˙’  
bˇang c´ach d¯aˇt cu`ong d¯ˆo l`a mˆot h`am cua hˆe sˆo g´oc. Ky˜ thuaˆt antialiasing cho kˆet qua tˆot  
.
.
.
.
.
.
.
.
`
˙’  
hon bˇang c´ach xem d¯oan thˇang nhu mˆot h`ınh chu˜ nhˆat c´o d¯oˆ rˆong hep v`a t´ınh to´an th´ıch  
.
.
.
. .  
.
.
. .  
.
.
˜
`
`
`
hop c´ac cu`ong d¯oˆ v´oi nhiˆeu pixel trˆen mˆoi cˆot nˇam trong hoˇac gˆan h`ınh chu˜ nhˆat (xem [9],  
.
.
.
.
.
.
.
.
˙’  
˙’  
[11]). Ngo`ai ra coi d¯oan thˇang nhu h`ınh chu˜ nhˆat cu˜ng cho ph´ep tao c´ac d¯oan thˇang v´oi d¯ˆo  
.
.
.
.
.
rˆong tuy` y´.  
.
.
.
.
˙’  
˙’  
. .  
˙’  
˙’  
Ph´ac thao c´ac nguyˆen so x´ac d¯inh boi c´ac d¯oan thˇang. V´oi c´ach v˜e c´ac d¯oan thˇang,  
.
.
.
.
. .  
.
.
.
˙’  
`
´
chu´ng ta cˆan v˜e c´ac nguyˆen so d¯uoc xˆay dung tu` c´ac d¯oan thˇang nhu thˆe n`ao? C´ac d¯u`ong  
.
.
.
. .  
.
.
˙’  
`
˙’  
´
`
gˆap khu´c c´o thˆe d¯uoc v˜e bˇang c´ach xem n´o nhu c´ac d¯oan thˇang kˆe nhau. C´ac h`ınh chu˜  
.
.
.
.
.
˙’  
´
`
nhˆat v`a d¯a gi´ac l`a nhu˜ng nguyˆen so vu`ng v`a c´o thˆe v˜e c´ac canh liˆen tiˆep nhung d¯iˆeu n`ay  
.
.
.
.
˜
`
´
´
`
˙’  
dˆan d¯ˆen mˆot sˆo pixel nˇam ngo`ai vu`ng d¯inh ngh˜ıa boi nguyˆen so-xem c´ac Phˆan 4.6 v`a 4.7  
.
.
.
.
. .  
`
`
´
`
`
´
˙’  
˙’  
˙’  
vˆe nhu˜ng thuaˆt to´an xu ly´ vˆan d¯ˆe n`ay. Chu´ y´ rˇang cˆan v˜e c´ac d¯ınh chung cua d¯u`ong gˆap  
.
˙’  
˙’  
`
`
`
´
khu´c mˆot lˆan do viˆec v˜e hai lˆan c´o thˆe l`am thay d¯ˆoi m`au hoˇac d¯aˇt m`au nˆen khi viˆet trong  
.
.
.
.
. .  
.
´
´
chˆe d¯oˆ XOR trˆen m`an h`ınh, hoˇac tˇang cu`ong d¯ˆo gˆap d¯ˆoi tai d¯o´. Thˆat ra c´o nhu˜ng pixel  
.
.
.
.
.
˙’  
`
´
`
˙’  
kh´ac l`a chung cua hai d¯oan thˇang nˇam gˆan nhau hoˇac cˇat nhau.  
.
.
20  
Tải về để xem bản đầy đủ
pdf 82 trang yennguyen 25380 Free
Download
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Đồ họa máy tính I (Phần 1) - Phạm Tiến Sơn", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • pdfgiao_trinh_do_hoa_may_tinh_i_phan_1_pham_tien_son.pdf