Tài liệu Đồ họa máy tính docx

Đồ họa máy tính

D- `Oˆ HO. A MAY T ´ ´INH I

Pha.m Tiˆe´n So.n

D- `a La.

t, 2005

Mu.

c lu.

L`o.

i n´oi d¯ˆa`u 7

1 C´ac thuˆa.

t to´an v˜e d¯u.`o

.ng cong trˆen thiˆe´t bi

raster 9

1.1 D- oa.n thˇa˙’ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.1.1 Thuˆa.

t to´an sˆo´ gia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.1.2 Thuˆa.

t to´an d¯iˆe˙’m gi˜u.a . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.1.3 Mˆo.

t sˆo´ vˆa´n d¯ˆe` liˆen quan d¯ˆe´n thuˆa.

t to´an v˜e d¯oa.n thˇa˙’ng . . . . . . . . 18

1.1.4 C´ac thuˆo. c t´ınh cu˙’a d¯oa.n thˇa˙’ng . . . . . . . . . . . . . . . . . . . . . 21

1.2 D- u

.`o

.ng tr`on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

1.2.1 D- ˆo´i x´u.ng t´am d¯iˆe˙’m . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

1.2.2 Thuˆa.

t to´an d¯iˆe˙’m gi˜u.a v˜e d¯u.`o

.ng tr`on . . . . . . . . . . . . . . . . . . 23

1.3 D- u

.`o

.ng cong ellipse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

1.3.1 Ellipse c´o da.ng ch´ınh tˇa´c . . . . . . . . . . . . . . . . . . . . . . . . . 29

1.3.2 Ellipse trong tru.`o

.ng ho.

.p tˆo˙’ng qu´at . . . . . . . . . . . . . . . . . . . 34

2 H`ınh ho.

c cu˙’a c´ac d¯u.`o

.ng cong v`a mˇa.

t cong 47

2.1 Mo.

˙’ d¯ˆa`u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

2.2 D- u

.`o

.ng cong Bezier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

2.2.1 Thuˆa.

t to´an de Casteljau . . . . . . . . . . . . . . . . . . . . . . . . . 48

2.2.2 D- a th´u.

c Bernstein v`a d¯u.`o

.ng cong Bezier . . . . . . . . . . . . . . . . 52

2.3 C´ac t´ınh chˆa´t cu˙’a d¯u.`o

.ng cong Bezier . . . . . . . . . . . . . . . . . . . . . . 55

2.3.1 D- iˆe` u khiˆe˙’n d¯i

.a phu.o

.ng . . . . . . . . . . . . . . . . . . . . . . . . . . 59

2.4 D- a th´u.

c t`u.ng kh´uc v`a c´ac h`am spline . . . . . . . . . . . . . . . . . . . . . . 60

2.4.1 Su.

˙’ du.ng c´ac h`am spline nhu.

c´ac h`am trˆo.n . . . . . . . . . . . . . . . 63

2.4.2 Xˆay du.

.ng c´ac h`am trˆo.n . . . . . . . . . . . . . . . . . . . . . . . . . 65

2.4.3 D- u

.`o

.ng 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.

˙’ du.ng c´ac knot bˆo.

i . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

2.4.6 Vector knot chuˆa˙’n . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

2.5 C´ac t´ınh chˆa´t cu˙’a d¯u.`o

.ng cong B-spline . . . . . . . . . . . . . . . . . . . . . 75

2.6 Nˆo.

i suy c´ac d¯iˆe˙’m d¯iˆe` u khiˆe˙’n bˇa`ng d¯u.`o

.ng cong B-spline . . . . . . . . . . . . 77

2.7 Thiˆe´t kˆe´ c´ac mˇa.

t 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 cu˙’a c´ac d¯ˆo´i tu.o.

.ng 83

3.1 Mo.

˙’ d¯ˆa`u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

3.2 Giao cu˙’a hai d¯oa.n thˇa˙’ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

3.2.1 Phˆan t´ıch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

3.2.2 Thuˆa.

t to´an x´ac d¯i

.nh giao hai d¯oa.n thˇa˙’ng . . . . . . . . . . . . . . . . 86

3.3 D- oa.n thˇa˙’ng v`a h`ınh ch˜u. nhˆa.

t . . . . . . . . . . . . . . . . . . . . . . . . . . 87

3.3.1 T`ım giao bˇa`ng c´ach gia˙’i hˆe. c´ac phu.o

.ng tr`ınh . . . . . . . . . . . . . . 89

3.3.2 Thuˆa.

t to´an chia nhi

. phˆan . . . . . . . . . . . . . . . . . . . . . . . . 89

3.3.3 Thuˆa.

t to´an Cohen-Sutherland . . . . . . . . . . . . . . . . . . . . . . 93

3.3.4 Thuˆa.

t to´an Liang-Barsky . . . . . . . . . . . . . . . . . . . . . . . . 97

3.4 Giao cu˙’a d¯oa.n thˇa˙’ng v`a d¯a gi´ac lˆo`i . . . . . . . . . . . . . . . . . . . . . . . 100

3.4.1 Vi

tr´ı tu.o

.ng d¯ˆo´i cu˙’a mˆo.

t d¯iˆe˙’m v´o.

i d¯u.`o

.ng thˇa˙’ng . . . . . . . . . . . . 100

3.4.2 Thuˆa.

t to´an t`ım giao cu˙’a d¯oa.n thˇa˙’ng v`a d¯a gi´ac lˆo`i . . . . . . . . . . 102

3.5 Giao hai d¯a gi´ac . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

3.5.1 Thuˆa.

t to´an Sutherland-Hodgman . . . . . . . . . . . . . . . . . . . . 108

3.5.2 Thuˆa.

t to´an Weiler-Atherton . . . . . . . . . . . . . . . . . . . . . . . 111

3.5.3 C´ac ph´ep to´an tˆa.p ho.

.p trˆen c´ac d¯a gi´ac . . . . . . . . . . . . . . . . 113

3.6 Ray tracing hai chiˆe` u: pha˙’n xa.

trong buˆo`ng k´ın . . . . . . . . . . . . . . . . 114

3.6.1 Vector pha˙’n xa.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

3.6.2 Giao cu˙’a tia s´ang v`a d¯u.`o

.ng thˇa˙’ng . . . . . . . . . . . . . . . . . . . 117

3.6.3 Giao cu˙’a tia s´ang v´o.

i d¯u.`o

.ng tr`on . . . . . . . . . . . . . . . . . . . . 121

3.6.4 Xˆay du.

.ng v´ı du.

ray tracing . . . . . . . . . . . . . . . . . . . . . . . 124

3.6.5 Buˆo`ng k´ın l`a ellipse . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126

4 Tˆo m`au v`ung 127

4.1 C´ac d¯i

.nh ngh˜ıa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127

4.1.1 V`ung d¯i

.nh ngh˜ıa bo.

˙’ i pixel . . . . . . . . . . . . . . . . . . . . . . . . 127

4.1.2 V`ung d¯i

.nh ngh˜ıa bo.

˙’ i d¯a gi´ac . . . . . . . . . . . . . . . . . . . . . . . 129

4.2 Thuˆa.

t to´an tˆo m`au theo vˆe´t dˆa`u loang . . . . . . . . . . . . . . . . . . . . . 129

4.3 Thuˆa.

t to´an tˆo m`au theo con cha.y . . . . . . . . . . . . . . . . . . . . . . . . 131

4.4 Thuˆa.

t to´an tˆo m`au theo biˆen . . . . . . . . . . . . . . . . . . . . . . . . . . 134

4.5 So s´anh c´ac thuˆa.

t to´an . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144

4.6 Tˆo m`au c´ac h`ınh ch˜u. nhˆa.

t . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145

4.7 Thuˆa.

t to´an tˆo m`au d¯a gi´ac . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147

4.7.1 C´ac d`ong qu´et ngang . . . . . . . . . . . . . . . . . . . . . . . . . . . 150

4.7.2 C´ac ma˙’nh vu. n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151

4.7.3 Liˆen kˆe´t ca.nh v`a thuˆa.

t to´an tr`an . . . . . . . . . . . . . . . . . . . . 151

4.7.4 Tˆo m`au c´ac d¯a gi´ac chˆo`ng nhau . . . . . . . . . . . . . . . . . . . . . 158

4.8 Tˆo m`au theo mˆa˜u tˆo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161

Phˆa`n phu.

lu.

c: Thu. viˆe.n graph2D.h 163

T`ai liˆe.u tham kha˙’o 171

L`o.

i n´oi d¯ˆa`

D- `ˆo ho.a m´ay t´ınh l`a mˆo.

t l˜ınh vu.

. c hˆa´p dˆa˜n cu˙’a khoa ho. c m´ay t´ınh. Ch´ung ta su.

˙’ du. ng d¯ˆo` ho.a

m´ay t´ınh nhu. mˆo.

t cˆong cu. d¯ˆe˙’ quan s´at thˆong tin trong nhiˆe` u l˜ınh vu.

. c kh´ac nhau, bao gˆo`m

khoa ho. c v`a cˆong nghˆe.

, ho´a ho. c, kiˆe´n tr´uc v`a gia˙’i tr´ı. C´ac chu.o

.ng tr`ınh d¯ˆo` ho.a tu.o

.ng t´ac

cho ph´ep ngu.`o

i su.

˙’ du.ng l`am viˆe.c theo c´ach tu.

. nhiˆen nhˆa´t: ngu.`o

i su.

˙’ du. ng cung cˆa´p thˆong

tin cho tr`ınh ´u.ng du. ng thˆong qua c´ac hoa.

t d¯ˆo.ng bˆen ngo`ai cu˙’a ho. v`a s˜e nhˆa.n d¯u.o

. c thˆong

tin tro.

˙’ la.

i bˇa`ng h`ınh a˙’nh. D- `ˆo ho.a m´ay t´ınh d¯ang gi´up con ngu.`o

i thay d¯ˆo˙’i vˆe` quan niˆe.m v`a

c´ach th´u.

c su.

˙’ du. ng m´ay t´ınh.

Gi´ao tr`ınh D- `ˆo ho. a m´ay t´ınh I cung cˆa´p mˆo.

t sˆo´ k˜y thuˆa.

t co. ba˙’n cu˙’a d¯ˆo` ho.a m´ay t´ınh

hai chiˆe` u. (D- `ˆo ho.a m´ay t´ınh ba chiˆe` u, mˆo.

t phˆa`n quan tro.ng khˆong thˆe˙’ thiˆe´u d¯u.o

. c s˜e d¯u.o

. c

d¯ˆe` cˆa.p trong mˆo.

t gi´ao tr`ınh kh´ac). D- ˆe˙’ c´o mˆo.

t khung ca˙’nh to`an diˆe.n v`a sˆau sˇa´c vˆe` nh˜u.ng

nguyˆen l´y v`a thu.

. c h`anh cu˙’a d¯ˆo` ho.a m´ay t´ınh, xem c´ac t`ai liˆe.u dˆa˜n [9] v`a [11]. C´ac phu.o

.ng

ph´ap phˆan t´ıch v`a thiˆe´t kˆe´ c´ac thuˆa.

t to´an trong gi´ao tr`ınh cho ph´ep sinh viˆen c´o thˆe˙’ viˆe´t

dˆe˜ d`ang c´ac chu.o

.ng tr`ınh minh ho.a. Gi´ao tr`ınh d¯u.o

. c biˆen soa.n cho c´ac d¯ˆo´i tu.o

. ng l`a sinh

viˆen To´an-Tin v`a Tin ho. c.

Gi´ao tr`ınh su.

˙’ du. ng ngˆon ng˜u. C d¯ˆe˙’ minh ho.a, tuy nhiˆen c´o thˆe˙’ dˆe˜ d`ang chuyˆe˙’n d¯ˆo˙’i

sang c´ac ngˆon ng˜u. kh´ac; v`a do d¯´o, sinh viˆen cˆa`n c´o mˆo.

t sˆo´ kiˆe´n th´u.

c vˆe` ngˆon ng˜u. C. Ngo`ai

ra, hˆa`u hˆe´t c´ac chu.o

.ng tr`ınh thao t´ac trˆen cˆa´u tr´uc d˜u.

liˆe.u nhu. danh s´ach liˆen kˆe´t, nˆen d¯`oi

ho˙’i sinh viˆen pha˙’i c´o nh˜u.ng k˜y nˇang lˆa.p tr`ınh tˆo´t.

Sinh viˆen c˜ung cˆa`n c´o co.

so.

˙’ to´an ho. c cu˙’a nh˜u.ng nˇam d¯ˆa`u d¯a.

i ho. c: hiˆe˙’u biˆe´t vˆe` d¯a.

i sˆo´

tuyˆe´n t´ınh v`a h`ınh ho. c gia˙’i t´ıch, ph´ep t´ınh vi t´ıch phˆan.

Mu. c d¯´ıch cu˙’a gi´ao tr`ınh l`a, o.

˙’ m´u.

c d¯ˆo. n`ao d¯´o, cho thˆa´y c´ac tr`ınh ´u.ng du.ng d¯ˆo` ho.a

d¯u.o

. c ta.o ra nhu.

thˆe´ n`ao: Ch´ung ta cˆa`n viˆe´t v`a cha.y thu.

˙’ c´ac chu.o

.ng tr`ınh. Mˆo.

t trong

nh˜u.ng mu. c d¯´ıch ch´ınh cu˙’a gi´ao tr`ınh l`a gi´up sinh viˆen nˇa´m v˜u.ng c´ac phu.o

.ng ph´ap, tru.´o

hˆe´t to´an ho. c ho´a c´ac kh´ac niˆe.m h`ınh ho. c v`a sau d¯´o chuyˆe˙’n ta˙’i th`anh c´ac d¯oa.n m˜a chu.o

.ng

tr`ınh.

Gi´ao tr`ınh bao gˆo`m bˆo´n chu.o

.ng v`a mˆo.

t phˆa`n phu.

lu. c v´o.

i nh˜u.ng nˆo.

i dung ch´ınh nhu.

• Chu.o

.ng th´u. nhˆa´t d¯ˆe` cˆa.p d¯ˆe´n c´ac phu.o

.ng ph´ap v˜e c´ac “nguyˆen so.” cu˙’a d¯ˆo` ho.a m´ay

t´ınh: d¯oa.n thˇa˙’ng, d¯u.`o

.ng tr`on v`a ellipse.

• Phˆan t´ıch v`a thiˆe´t kˆe´ bˇa`ng h`ınh ho. c l`a nˆo.

i dung ch´ınh cu˙’a Chu.o

.ng 2. Hˆa`u hˆe´t c´ac

phˆa`n mˆe` m d¯ˆo` ho.a d¯ˆe` u c´o nh˜u.ng ch´u.

c nˇang ta.o ra c´ac d¯u.`o

.ng cong du.

. a trˆen c´ac d¯iˆe˙’m

m`a ngu.`o

i su.

˙’ du.ng lu.

. a cho.n. Chu.o

.ng n`ay cung cˆa´p nh˜u.ng nguyˆen l´y v`a c´ach tiˆe´p cˆa.n

thu.

. c h`anh m`a c´ac tr`ınh ´u.ng du.ng d¯ˆo` ho.a ´ap du.ng.

• Chu.o

.ng 3 gia˙’i quyˆe´t b`ai to´an x´ac d¯i

.nh giao cu˙’a nh˜u.ng nguyˆen so. d¯ˆo` ho.a: Giao hai

d¯oa.n thˇa˙’ng, giao cu˙’a d¯oa.n thˇa˙’ng v`a d¯a gi´ac lˆo`i (bao h`am c´ac h`ınh ch˜u. nhˆa.

t) v`a giao

cu˙’a hai d¯a gi´ac. Cuˆo´i chu.o

.ng l`a mˆo.

t v´ı du. cu˙’a k˜y thuˆa.

t “ray tracing” hai chiˆe` u:

Chuyˆe˙’n d¯ˆo.ng cu˙’a tia s´ang trong buˆo`ng k´ın c´o ch´u.a c´ac “chu.´o

.ng nga.

i vˆa.

t”.

• Chu.o

.ng 4 d¯ˆe` cˆa.p d¯ˆe´n nh˜u.ng thuˆa.

t to´an tˆo m`au v`ung bˆa´t k`y: V`ung d¯i

.nh ngh˜ıa bo.

˙’ i

phˆa`n trong, bo.

˙’ i d¯u.`o

.ng biˆen v`a v`ung l`a d¯a gi´ac.

• Phˆa`n phu.

lu. c l`a thu. viˆe.n c´ac cˆa´u tr´uc d˜u.

liˆe.u v`a c´ac h`am cˆa`n thiˆe´t v`a thu.`o

.ng xuyˆen

su.

˙’ du.ng trong gi´ao tr`ınh.

Trong lˆa`n xuˆa´t ba˙’n th´u. hai n`ay, ch´ung tˆoi d¯u.a thˆem c´ac v´ı du.

t´ınh to´an nhˇa`m minh

ho.a cho phˆa`n l´y thuyˆe´t c˜ung nhu. gi´up sinh viˆen nˇa´m v˜u.ng kiˆe´n th´u.

c d¯˜a ho. c. Ngo`ai ra, c´ac

lˆo˜i trong xuˆa´t ba˙’n lˆa`n tru.´o

c c˜ung d¯˜a d¯u.o

. c chı˙’nh l´y; mˇa. c d`u vˆa.y, t´ac gia˙’ vˆa˜n mong c´o nh˜u.ng

d¯´ong g´op t`u. ba.n d¯o. c.

Tˆoi xin ca˙’m o.n nh˜u.ng gi´up d¯˜o. d¯˜a nhˆa.n d¯u.o

. c t`u. nhiˆe` u ngu.`o

i m`a khˆong thˆe˙’ liˆe.

t kˆe

hˆe´t, d¯ˇa. c biˆe.

t l`a c´ac ba.n sinh viˆen, trong qu´a tr`ınh biˆen soa.n gi´ao tr`ınh n`ay.

D- `a La.

t, ng`ay 10 th´ang 1 nˇam 2005

PHA. M Tiˆe´n So.n

Chu.o

.ng 1

C´ac thuˆa.

t to´an v˜e d¯u.`o

.ng cong trˆen

thiˆe´t bi

raster

Chu.o

.ng n`ay tr`ınh b`ay c´ac thuˆa.

t to´an v˜e d¯oa.n thˇa˙’ng, d¯u.`o

.ng tr`on v`a ellipse trˆen lattice

nguyˆen Z

. C´ac thuˆa.

t to´an chı˙’ thao t´ac trˆen nh˜u.ng sˆo´ nguyˆen v`a trong c´ac v`ong lˇa.p chı˙’ su.

˙’

du.ng ph´ep to´an cˆo.ng nˆen rˆa´t hiˆe.u qua˙’.

1.1 D- oa.n thˇa˙’

Thuˆa.

t to´an v˜e d¯oa.n thˇa˙’ng x´ac d¯i

.nh to.a d¯ˆo. cu˙’a c´ac pixel nˇa`m trˆen hoˇa. c gˆa`n v´o.

i d¯oa.n thˇa˙’ng

thu.

. c tˆe´ nhˆa´t. Vˆe` nguyˆen tˇa´c, ch´ung ta muˆo´n cho.n d˜ay c´ac pixel gˆa`n v´o.

i d¯oa.n thˇa˙’ng thu.

. c tˆe´

nhˆa´t v`a thˇa˙’ng nhˆa´t. X´et d¯oa.n thˇa˙’ng thu.

. c tˆe´ d¯u.o

. c xˆa´p xı˙’ v´o.

i mˆa.

t d¯ˆo. mˆo.

t pixel; ta cˆa`n c´o

nh˜u.ng t´ınh chˆa´t g`ı? V´o.

i c´ac d¯oa.n thˇa˙’ng c´o hˆe.

sˆo´ g´oc thuˆo. c d¯oa.n [−1, 1], c´o d¯´ung mˆo.

t pixel

d¯u.o

. c v˜e lˆen trˆen mˆo˜i cˆo.

t; v´o.

i c´ac d¯oa.n thˇa˙’ng m`a hˆe.

sˆo´ g´oc nˇa`m ngo`ai d¯oa.n n`ay, c´o d¯´ung

mˆo.

t pixel d¯u.o

. c v˜e trˆen mˆo˜i h`ang. Tˆa´t ca˙’ c´ac d¯oa.n thˇa˙’ng d¯u.o

. c v˜e v´o.

i c`ung mˆo.

t d¯ˆo.

s´ang,

khˆong phu.

thuˆo. c v`ao d¯ˆo. d`ai v`a hu.´o

.ng, v`a nhanh nhˆa´t c´o thˆe˙’ d¯u.o

. c. Thuˆa.

t to´an v˜e d¯oa.n

thˇa˙’ng c˜ung cˆa`n ch´u ´y d¯ˆe´n c´ac thuˆo. c t´ınh cu˙’a d¯oa.n thˇa˙’ng nhu. d¯ˆo.

rˆo.ng, kiˆe˙’u v˜e... Thˆa.m ch´ı

ch´ung ta muˆo´n cu.

. c tiˆe˙’u ho´a m´u.

c d¯ˆo.

rˇang cu.a do tiˆe´n tr`ınh r`o.

i ra. c ho´a d¯u.`o

.ng thˇa˙’ng thu.

. c

tˆe´ nh`o.

su.

˙’ du. ng k˜y thuˆa.

t antialiasing (xem [9], [11]) bˇa`ng c´ach ´ap du.ng kha˙’ nˇang d¯ˇa.

t cu.`o

.ng

d¯ˆo. cu˙’a mˆo˜i pixel trˆen c´ac thiˆe´t bi

. hiˆe˙’n thi

. m`a mˆo.

t pixel tu.o

.ng ´u.ng nhiˆe` u bit.

Tru.´o

c hˆe´t ch´ung ta chı˙’ d¯ˆe` cˆa.p d¯ˆe´n c´ac d¯oa.n thˇa˙’ng d¯ˆo.

rˆo.ng mˆo.

t pixel v`a c´o d¯´ung mˆo.

pixel trˆen mˆo˜i cˆo.

t (hoˇa. c h`ang d¯ˆo´i v´o.

i c´ac d¯oa.n thˇa˙’ng dˆo´c). Phˆa`n cuˆo´i chu.o

.ng s˜e d¯ˆe` cˆa.p

d¯ˆe´n d¯ˆo.

rˆo.ng c´ac nguyˆen so. v`a c´ac mˆa˜u v˜e.

Mˆo.

t c´ach h`ınh ho. c, ch´ung ta biˆe˙’u diˆe˜n mˆo.

t pixel nhu. mˆo.

t chˆa´m tr`on v´o.

i tˆam ta.

i vi

tr´ı (x, y) cu˙’a pixel trˆen lu.´o

i c´ac to.a d¯ˆo. nguyˆen Z

. Biˆe˙’u diˆe˜n n`ay l`a mˆo.

t xˆa´p xı˙’ th´ıch ho.

. p

nh´at cˇa´t ngang trong mˆo.

t chu k`y cu˙’a ch`um tia electron cu˙’a CRT; xˆa´p xı˙’ n`ay phu.

thuˆo. c v`ao

khoa˙’ng c´ach (tu`y thuˆo. c v`ao hˆe.

thˆo´ng) gi˜u.a c´ac vˆe´t trˆen m`an h`ınh hiˆe˙’n thi

. Trong mˆo.

t sˆo´

hˆe.

thˆo´ng, c´ac chˆa´m kˆe` nhau phu˙’ lˆa´p mˆo.

t phˆa`n lˆen nhau; v´o.

i nh˜u.ng hˆe.

thˆo´ng kh´ac c´o nh˜u.ng

khoa˙’ng c´ach gi˜u.a c´ac pixel d¯´u.ng kˆe` nhau; trong hˆa`u hˆe´t c´ac hˆe.

thˆo´ng, khoa˙’ng c´ach theo

chiˆe` u ngang nho˙’ ho.n theo chiˆe` u d¯´u.ng. Mˆo.

t kh´ac biˆe.

t n˜u.a tu`y theo hˆe.

thˆo´ng trong viˆe.c biˆe˙’u

diˆe˜n hˆe.

to.a d¯ˆo.

, chˇa˙’ng ha.n Macintosh xem c´ac pixel d¯u.o

. c d¯ˇa.

t ta.

i tˆam cu˙’a h`ınh ch˜u. nhˆa.

gi˜u.a c´ac d¯u.`o

.ng thˇa˙’ng kˆe` nhau cu˙’a lu.´o

i d¯iˆe` u khiˆe˙’n thay cho nˇa`m trˆen c´ac d¯u.`o

.ng thˇa˙’ng cu˙’a

lu.´o

i. Theo c´ach n`ay, c´ac h`ınh ch˜u. nhˆa.

t (x´ac d¯i.nh bo.

˙’ i hai g´oc) gˆo`m c´ac pixel thuˆo. c phˆa`n

trong cu˙’a n´o. D- i

.nh ngh˜ıa n`ay cho ph´ep c´ac v`ung d¯ˆo.

rˆo.ng bˇa`ng khˆong: H`ınh ch˜u. nhˆa.

t t`u.

(x, y) d¯ˆe´n (x, y) khˆong ch´u.a pixel n`ao, trong khi v´o.

i nh˜u.ng hˆe.

thˆo´ng kh´ac, c´o d¯´ung mˆo.

pixel ta.

i d¯iˆe˙’m n`ay. Du.´o

i d¯ˆay ch´ung ta s˜e biˆe˙’u diˆe˜n c´ac pixel nhu.

c´ac h`ınh tr`on r`o.

i nhau c´o

tˆam nˇa`m trˆen lu.´o

H`ınh 1.1 l`a ph´ong to cu˙’a d¯u.`o

.ng thˇa˙’ng thu.

. c tˆe´ v`a xˆa´p xı˙’ d¯ˆo.

rˆo.ng mˆo.

t pixel cu˙’a n´o.

C´ac pixel d¯u.o

. c v˜e tu.o

.ng ´u.ng c´ac h`ınh tr`on m`au d¯en v`a c´ac pixel khˆong d¯u.o

. c v˜e tu.o

.ng ´u.ng

h`ınh tr`on khˆong tˆo. Trˆen m`an h`ınh thu.

. c tˆe´, d¯u.`o

.ng k´ınh cu˙’a h`ınh tr`on biˆe˙’u diˆe˜n pixel l´o.n

ho.n khoa˙’ng c´ach gi˜u.a c´ac pixel kˆe` nhau, bo.

˙’ i vˆa.y biˆe˙’u diˆe˜n bˇa`ng k´y hiˆe.u cu˙’a ch´ung ta l`a

mˆo.

t ph´ong d¯a.

i m´u.

c d¯ˆo.

r`o.

i ra. c cu˙’a c´ac pixel.

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

. . . . .

✐ ✐ ✐ ✐ ✐

......

...... ②

② ②

H`ınh 1.1: D- oa.n thˇa˙’ng xˆa´p xı˙’ d¯u.o

. c biˆe˙’u diˆe˜n bo.

˙’ i c´ac h`ınh tr`on d¯en.

V`ı c´ac nguyˆen so.

trong hˆe.

thˆo´ng ch´ung ta x´ac d¯i

.nh trˆen lu.´o

i d¯iˆe` u khiˆe˙’n nguyˆen nˆen

c´ac to.a d¯ˆo. d¯ˆa`u cuˆo´i cu˙’a d¯oa.n thˇa˙’ng l`a nguyˆen. Thˆa.

t ra, nˆe´u ch´ung ta cˇa´t d¯oa.n thˇa˙’ng v´o.

h`ınh ch˜u. nhˆa.

t tru.´o

c khi hiˆe˙’n thi

. n´o th`ı to.a d¯ˆo. c´ac d¯iˆe˙’m d¯ˆa`u cuˆo´i cu˙’a d¯oa.n thˇa˙’ng c´o thˆe˙’

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

su.

˙’ d¯oa.n thˇa˙’ng c´o hˆe.

sˆo´ g´oc |m| ≤ 1; c´ac tru.`o

.ng ho.

. p kh´ac d¯u.o

. c xu.

˙’ l´y tu.o

.ng tu.

. Ho.n n˜u.a

tru.`o

.ng ho.

. p c´ac d¯oa.n thˇa˙’ng ngang, d¯´u.ng hoˇa. c c´o hˆe.

sˆo´ g´oc ±1 l`a tˆa`m thu.`o

.ng v`ı ch´ung chı˙’

d¯i qua c´ac pixel trˆen lu.´o

1.1.1 Thuˆa.

t to´an sˆo´ gia

X´et hai pixel A = (xA, yA) v`a B = (xB, yB) (t´uc c´ac phˆa`n tu.

˙’ cu˙’a lattice nguyˆen Z

). Phu.o

.ng

tr`ınh d¯u.`o

.ng thˇa˙’ng AB c´o da.ng y = mx+t, trong d¯´o hˆe.

sˆo´ g´oc m = dy/dx v`a t = yA −mxA.

C´ach d¯o.n gia˙’n nhˆa´t d¯ˆe˙’ v˜e d¯oa.n thˇa˙’ng AB l`a:

1. T´ınh hˆe.

sˆo´ g´oc m;

2. Tˇang x mˆo.

t d¯o.n vi

(kho.

˙’ i d¯ˆa`u t`u. d¯iˆe˙’m bˆen tr´ai nhˆa´t), v´o.

i mˆo˜i xi t´ınh yi = mxi + t v`a

sau d¯´o v˜e pixel ta.

i (xi

, byi + 0.5c)

Theo c´ach n`ay ta cho.n pixel tˆo´t nhˆa´t, t´u.

c l`a pixel m`a khoa˙’ng c´ach d¯ˆe´n d¯u.`o

.ng thˇa˙’ng thu.

. c

tˆe´ nho˙’ nhˆa´t. Phu.o

.ng ph´ap n`ay khˆong hiˆe.u qua˙’ do mˆo˜i bu.´o

c lˇa.p cˆa`n t´ınh mˆo.

t ph´ep nhˆan,

mˆo.

t ph´ep cˆo.ng v`a mˆo.

t ph´ep to´an l`am tr`on. Ta c´o thˆe˙’ khu.

˙’ ph´ep nhˆan bˇa`ng c´ach ch´u ´y rˇa`ng

yi+1 = mxi+1 + t

= m(xi + ∆x) + t

= yi + m∆x,

v`a nˆe´u bu.´o

c tˇang ∆x = 1 th`ı yi+1 = yi + m.

Do d¯´o nˆe´u x tˇang mˆo.

t d¯o.n vi

th`ı y tˇang m d¯o.n vi

. V´o.

i mo.

i d¯iˆe˙’m (xi

, yi) trˆen d¯oa.n

thˇa˙’ng ta biˆe´t rˇa`ng nˆe´u xi+1 = xi + 1 th`ı yi+1 = yi + m; t´u.

c l`a, c´ac gi´a tri

. x v`a y d¯u.o

. c t´ınh

theo c´ac gi´a tri

tru.´o

c d¯´o cu˙’a n´o (xem H`ınh 1.2). D- ˆay ch´ınh l`a “thuˆa.

t to´an sˆo´ gia”: v´o.

i mˆo˜i

bu.´o

c lˇa.p ta thu.

. c hiˆe.n c´ac ph´ep to´an sˆo´ gia du.

. a trˆen bu.´o

c tru.´o

Kho.

˙’ i ta.o ta g´an (x0, y0) l`a to.a d¯ˆo. nguyˆen cu˙’a d¯iˆe˙’m xuˆa´t ph´at, chˇa˙’ng ha.n A. Ch´u ´y

rˇa`ng trong tru.`o

.ng ho.

. p |m| > 1 nˆe´u x tˇang mˆo.

t d¯o.n vi

th`ı y tˇang ho.n mˆo.

t d¯o.n vi

. Do d¯´o

cˆa`n ho´an d¯ˆo˙’i vai tr`o cu˙’a x v`a y bˇa`ng c´ach g´an bu.´o

c tˇang mˆo.

t d¯o.n vi

. cho y v`a tˇang x mˆo.

lu.o

. ng ∆x =

∆y

m =

1K´y hiˆe.u [x], bxc v`a dxe tu.o

.ng ´u.ng l`a phˆa`n nguyˆen, l`am tr`on xuˆo´ng v`a l`am tr`on lˆen cu˙’a x.

. . . .

(xi

, yi)

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

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

...

(xi

, byic)

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

........

(xi + 1, yi + m)

(xi + 1, dyi + me)

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

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

...

D- u

.`o

.ng thˇa˙’ng

thu.

. c tˆe´

✇

✇ ✇

✇

H`ınh 1.2: T´ınh to´an sˆo´ 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 thˇa˙’ng qua hai d¯iˆe˙’m A v`a B c´o hˆe.

sˆo´

g´oc m =

∈ (0, 1). Ap du ´

. ng thuˆa.

t to´an sˆo´ gia ta d¯u.o

. c d˜ay c´ac d¯iˆe˙’m v˜e tˆo´t nhˆa´t nhu.

trong

ba˙’ng du.´o

i xi yi byi + 0.5c

0 2 0 0

1 3

2 4

3 5

4 6

5 7

6 8

7 9

Thu˙’ tu. c Line() du.´o

i d¯ˆay minh ho.a thuˆa.

t to´an v˜e d¯oa.n thˇa˙’ng t`u.

(x0, y0) d¯ˆe´n (x1, y1)

v´o.

i gi´a tri

. m`au V alue. D- iˆe˙’m kho.

˙’ i d¯ˆa`u l`a d¯iˆe˙’m bˆen tr´ai nhˆa´t. Ngo`ai ra ta chı˙’ x´et tru.`o

.ng ho.

. p

−1 ≤ m ≤ 1 v`ı c´ac tru.`o

.ng ho.

. p kh´ac c´o thˆe˙’ thu.

. c hiˆe.n do t´ınh d¯ˆo´i x´u.ng. Ho.n n˜u.a, ch´ung ta

c˜ung bo˙’ qua viˆe.c kiˆe˙’m tra c´ac tru.`o

.ng ho.

. p d¯ˇa. c biˆe.

t: d¯u.`o

.ng thˇa˙’ng nˇa`m ngang, d¯´u.ng, xiˆen

mˆo.

t g´oc ±450

. Ch´u ´y rˇa`ng, trong ngˆon ng˜u. C, (int)y bˇa`ng by + 0.5c.

void Line(int x_A, int y_A, int x_B, int y_B, int Value)

{

int x;

int dx, dy;

float y, m;

dx = x_B - x_A;

dy = y_B - y_A;

m = dy/(float)dx;

y = y0;

for (x = x_A; x <= x_B; x ++)

{

putpixel(x, (int)(y), Value);

y += m;

}

1.1.2 Thuˆa.

t to´an d¯iˆe˙’m gi˜u.a

Thu˙’ tu. c Line() thao t´ac trˆen c´ac sˆo´ thu.

. c y v`a m. Bresenham d¯˜a xˆay du.

. ng thuˆa.

t to´an [2] v˜e

d¯oa.n thˇa˙’ng chı˙’ su.

˙’ du. ng c´ac ph´ep to´an trˆen sˆo´ nguyˆen do d¯´o tr´anh go.

i h`am l`am tr`on v`a cho

ph´ep x´ac d¯i

.nh (xi+1, yi+1) theo sˆo´ gia du.

. a trˆen nh˜u.ng gi´a tri

. o

˙’ bu.´o

c tru.´o

c (xi

, yi). Thuˆa.

to´an n`ay c´o thˆe˙’ mo.

˙’ rˆo.ng da.ng dˆa´u chˆa´m d¯ˆo.ng d¯ˆo´i v´o.

i c´ac to.a d¯ˆo.

thu.

. c. Ho.n n˜u.a, phu.o

.ng

ph´ap cu˙’a Bresenham c´o thˆe˙’ d¯u.o

. c ´ap du.ng t´ınh to´an trˆen sˆo´ nguyˆen v˜e d¯u.`o

.ng tr`on mˇa. c d`u

n´o khˆong dˆe˜ d`ang mo.

˙’ rˆo.ng cho conic tu`y ´y. V`ı vˆa.y ch´ung ta su.

˙’ du. ng phu.o

.ng ph´ap tu.o

.ng

d¯ˆo´i kh´ac, thuˆa.

t to´an d¯iˆe˙’m gi˜u.a, d¯u.o

. c cˆong bˆo´ lˆa`n d¯ˆa`u tiˆen bo.

˙’ i Pitteway [16], [17] v`a d¯u.o

. c

ca˙’i tiˆe´n bo.

˙’ i Van Aken [26] v`a mˆo.

t sˆo´ t´ac gia˙’ kh´ac [28], [29]. Van Aken d¯˜a chı˙’ ra [26] d¯ˆo´i v´o.

c´ac d¯u.`o

.ng thˇa˙’ng v`a d¯u.`o

.ng tr`on v´o.

i d˜u.

liˆe.u nguyˆen, cˆong th´u.

c d¯iˆe˙’m gi˜u.a suy ra cˆong th´u.

cu˙’a Bresenham v`a do d¯´o sinh ra c`ung d˜ay c´ac pixel.

Khˆong mˆa´t t´ınh tˆo˙’ng qu´at, gia˙’ su.

˙’ hˆe.

sˆo´ g´oc m cu˙’a d¯u.`o

.ng thˇa˙’ng thuˆo. c khoa˙’ng (0, 1)

(c´ac tru.`o

.ng ho.

. p kh´ac c´o thˆe˙’ d¯u.o

. c xu.

˙’ l´y bo.

˙’ i c´ac ph´ep lˆa´y d¯ˆo´i x´u.ng mˆo.

t c´ach th´ıch ho.

. p qua

c´ac tru. c to.a d¯ˆo.

). Ta c˜ung k´y hiˆe.u d¯iˆe˙’m xuˆa´t ph´at l`a (xA, yA) v`a d¯iˆe˙’m kˆe´t th´uc l`a (xB, yB).

D- ˇa.

t dy := yB − yA, dx = xB − xA. Phu.o

.ng tr`ınh d¯u.`o

.ng thˇa˙’ng l qua hai d¯iˆe˙’m A v`a B x´ac

d¯i

.nh bo.

˙’ i

y =

dxx + t;

.......................... (l

−)

✇

H`ınh 1.3: Lu.´o

i c´ac pixel v`a vi

tr´ı d¯iˆe˙’m C, R, D, Q v`a M.

hay tu.o

.ng d¯u.o

.ng

f(x, y) := ax + by + c = 0,

trong d¯´o a = dy, b = −dx, v`a c = b × dx. K´y hiˆe.u c´ac nu.

˙’ a mˇa.

t phˇa˙’ng ngo`ai v`a nu.

˙’ a mˇa.

phˇa˙’ng trong x´ac d¯i

.nh bo.

˙’ i l tu.o

.ng ´u.ng bo.

˙’ i

+) := {(x, y) ∈ R2

| f(x, y) > 0},

−) := {(x, y) ∈ R2

| f(x, y) < 0}.

Y tu ´ .o

˙’ ng cu˙’a thuˆa.

t to´an d¯iˆe˙’m gi˜u.a l`a xˆay du.

. ng mˆo.

t d˜ay c´ac d¯iˆe˙’m v˜e “tˆo´t nhˆa´t” (xi

, yi)

bˇa´t d¯ˆa`u t`u. d¯iˆe˙’m (x0, y0) = (xA, yA). Kh´ai niˆe.m tˆo´t nhˆa´t o

˙’ d¯ˆay l`a nh˜u.ng d¯iˆe˙’m (xi

, yi) d¯u.o

. c

cho.n gˆa`n v´o.

i d¯u.`o

.ng thˇa˙’ng thu.

. c tˆe´ (da.ng liˆen tu. c) nhˆa´t. Theo gia˙’ thiˆe´t, 0 < m < 1, nˆen khi

x tˇang mˆo.

t lu.o

. ng ∆x th`ı y tˇang khˆong qu´a ∆y = m∆x d¯o.n vi

V`ı vˆa.y nˆe´u bu.´o

c th´u.

i cho.n d¯u.o

. c d¯iˆe˙’m v˜e tˆo´t nhˆa´t C := (xi

, yi) th`ı o.

˙’ bu.´o

c th´u.

i + 1

ta s˜e cho.n d¯iˆe˙’m v˜e (xi+1, yi+1), trong d¯´o xi+1 = xi + 1 v`a yi+1 = yi hoˇa. c yi+1 = yi + 1.

N´oi c´ach kh´ac, bu.´o

c th´u.

i + 1 ch´ung ta s˜e cho.n mˆo.

t trong hai pixel R := (xi + 1, yi) hoˇa. c

D := (xi + 1, yi + 1) (xem H`ınh 1.3). K´y hiˆe.u Q l`a giao d¯iˆe˙’m cu˙’a hai d¯u.`o

.ng thˇa˙’ng l v`a

x = xi + 1. Theo Bresenham, dˆa´u cu˙’a biˆe˙’u th´u.

c x´ac d¯i

.nh bo.

˙’ i hiˆe.u gi˜u.a hai khoa˙’ng c´ach t`u.

R v`a D d¯ˆe´n Q cho ph´ep x´ac d¯i

.nh pixel tˆo´t nhˆa´t o.

˙’ bu.´o

c i + 1. Trong thuˆa.

t to´an d¯iˆe˙’m gi˜u.a,

ta quan s´at vi

tr´ı cu˙’a d¯iˆe˙’m gi˜u.a M v`a c´ac nu.

˙’ a mˇa.

t phˇa˙’ng x´ac d¯i

.nh bo.

˙’ i d¯u.`o

.ng thˇa˙’ng l. Dˆe˜

d`ang chı˙’ ra rˇa`ng, nˆe´u M ∈ (l

+) th`ı pixel D gˆa`n v´o.

i d¯u.`o

.ng thˇa˙’ng l ho.n; nˆe´u M ∈ (l

−) th`ı

pixel R gˆa`n ho.n. D- u

.`o

.ng thˇa˙’ng l c´o thˆe˙’ d¯i ngang qua M; hoˇa. c ca˙’ hai pixel nˇa`m vˆe` c`ung

mˆo.

t nu.

˙’ a mˇa.

t phˇa˙’ng (l

+) (hoˇa. c (l

−)) nhu.ng trong bˆa´t c´u.

tru.`o

.ng ho.

. p n`ao, ta vˆa˜n cho.n d¯iˆe˙’m

gˆa`n v´o.

i l nhˆa´t. Ho.n n˜u.a, sai sˆo´-t´u.

c l`a khoa˙’ng c´ach gi˜u.a pixel d¯u.o

. c cho.n v`a d¯u.`o

.ng thˇa˙’ng

thu.

. c tˆe´ l-luˆon luˆon nho˙’ ho.n hoˇa. c bˇa`ng 1/2.

Thư viện tri thức trực tuyến

Tài liệu Đồ họa máy tính docx

Nội dung xem thử

Mô tả chi tiết

Tài liệu tương tự (6)

Tài liệu ĐỒ GỐM CỔ docx

Tài liệu Đồ án trung tâm nghiên cứu thực tại ảo docx

Tài liệu Đồ án cung cấp điện hoàn thành ppt

Tài liệu Đo lượng dịch vào ra ppt

Tài liệu Đồ án môn học “Thiết kế mạng lưới điện khu vực” ppt

Tài liệu Đồ án