Đồ họa máy tính

Chia sẻ: vanthanh8990

Đồ họa máy tính là lĩnh vực hấp dẫn trong khoa học máy tính.Chúng được sử dụng như công cụ để quan sát thông tin trong nhiều lĩnh vực khác nhau, bao gồm khoa học công nghệ, hóa học, kiến trúc và giải trí. Các chương trình đồ họa tương tác cho phép người sử dụng làm việc theo cách tự nhiên.

Bạn đang xem 20 trang mẫu tài liệu này, vui lòng download file gốc để xem toàn bộ.

Nội dung Text: Đồ họa máy tính

Đồ họa máy tính
D` HOA MAY T´
ˆ
-O . ´ INH I


Pham Tiˆn So.n
. ´
e


-a .
D` Lat, 2005
2
Muc luc
. .


L`.i n´i d` u
o o ¯ˆ a 7


1 C´c thuˆt to´n v˜ d .`.ng cong trˆn thiˆt bi raster
a a
. a e ¯u o e ´
e . 9

1.1 - . ˙

Doan thˇng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
a 9

1.1.1 a
. a o ´
Thuˆt to´n sˆ gia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

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

1.1.3 . ´ ´ e
o o a ¯ˆ e ´
¯e a
. a e ¯ . ˙

Mˆt sˆ vˆ n d` liˆn quan dˆn thuˆt to´n v˜ d oan thˇng . . . . . . . .
a 18

1.1.4 o ınh ˙ ¯ .
’ ˙

C´c thuˆc t´ cua d oan thˇng . . . . . . . . . . . . . . . . . . . . .
a . a 21

1.2 Du.`.ng tr`n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
- o o 22

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

1.2.2 Thuˆt to´n d iˆ’m gi˜.a v˜ d u.`.ng tr`n . . . . . . . . . . . . . . . . . .
a
. a ¯e ˙ u e ¯ o o 23

1.3 Du.`.ng cong ellipse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
- o 28

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

1.3.2 Ellipse trong tru.`.ng ho.p tˆ’ng qu´t . . . . . . . . . . . . . . . . . . .
o . o ˙ a 34


2 H` hoc cu a c´c d .`.ng cong v` mˇt cong
ınh . ˙
’ a ¯u o a a. 47

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


3
2.2 Du.`.ng cong Bezier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
- o 48

2.2.1 Thuˆt to´n de Casteljau . . . . . . . . . . . . . . . . . . . . . . . . .
a
. a 48

2.2.2 Da th´.c Bernstein v` d u.`.ng cong Bezier . . . . . . . . . . . . . . . .
- u a ¯ o 52

2.3 C´c t´ chˆ t cua d u.`.ng cong Bezier . . . . . . . . . . . . . . . . . . . . . .
´ ’
a ınh a ˙ ¯ o 55

2.3.1 Diˆu khiˆ’n d .a phu.o.ng . . . . . . . . . . . . . . . . . . . . . . . . . .
- `
e ˙
e ¯i 59

2.4 Da th´.c t`.ng kh´c v` c´c h`m spline . . . . . . . . . . . . . . . . . . . . . .
- u u u a a a 60

2.4.1 Su. dung c´c h`m spline nhu. c´c h`m trˆn . . . . . . . . . . . . . . .
˙ .
’ a a a a o
. 63

2.4.2 Xˆy du.ng c´c h`m trˆn . . . . . . . . . . . . . . . . . . . . . . . . .
a . a a o
. 65

2.4.3 Du.`.ng cong spline v` c´c h`m co. so. . . . . . . . . . . . . . . . . . .
- o a a a ˙
’ 66

2.4.4 C´c h`m B-spline co. so. . . . . . . . . . . . . . . . . . . . . . . . . .
a a ˙
’ 66

2.4.5 Su. dung c´c knot bˆi . . . . . . . . . . . . . . . . . . . . . . . . . . .
˙ .
’ a o
. 71

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

2.5 C´c t´ chˆ t cua d u.`.ng cong B-spline . . . . . . . . . . . . . . . . . . . . .
´ ’
a ınh a ˙ ¯ o 75

2.6 Nˆi suy c´c d iˆ’m d iˆu khiˆ’n bˇ ng d u.`.ng cong B-spline . . . . . . . . . . . .
o
. ˙
a ¯ e ¯` e ˙ a
e ` ¯ o 77

2.7 ´ ´
Thiˆt kˆ c´c mˇt Bezier v` B-spline . . . . . . . . . . . . . . . . . . . . . . .
e e a a
. a 80

2.7.1 Patch Bezier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

2.7.2 D´n c´c patch Bezier . . . . . . . . . . . . . . . . . . . . . . . . . . .
a a 81

2.7.3 Patch spline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82


3 Giao cu a c´c d oi tu.o.ng
˙
’ a ¯ˆ ´ . 83

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

3.2 ˙
’ ˙

Giao cua hai d oan thˇng . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
¯ . a 83

3.2.1 Phˆn t´
a ıch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84


4
3.2.2 . a a ¯. ¯ . ˙

Thuˆt to´n x´c d inh giao hai d oan thˇng . . . . . . . . . . . . . . . .
a a 86

3.3 Doan thˇng v` h` ch˜. nhˆt . . . . . . . . . . . . . . . . . . . . . . . . . .
- . ˙

a a ınh u a . 87

3.3.1 T` giao bˇ ng c´ch giai hˆ c´c phu.o.ng tr` . . . . . . . . . . . . . .
ım `
a a ˙ e a
’ . ınh 89

3.3.2 Thuˆt to´n chia nhi phˆn . . . . . . . . . . . . . . . . . . . . . . . .
a
. a . a 89

3.3.3 Thuˆt to´n Cohen-Sutherland . . . . . . . . . . . . . . . . . . . . . .
a
. a 93

3.3.4 Thuˆt to´n Liang-Barsky
a
. a . . . . . . . . . . . . . . . . . . . . . . . . 97

3.4 ˙ ¯ .
’ ˙
’ a `
Giao cua d oan thˇng v` d a gi´c lˆi . . . . . . . . . . . . . . . . . . . . . . . 100
a a ¯ o

3.4.1 Vi tr´ tu.o.ng d ˆi cua mˆt d iˆ’m v´.i d u.`.ng thˇng . . . . . . . . . . . . 100
. ı ´ ’
¯o ˙ o ¯e
. ˙ o ¯ o ˙

a

3.4.2 ˙ ¯ .
’ ˙
’ a `
Thuˆt to´n t` giao cua d oan thˇng v` d a gi´c lˆi . . . . . . . . . . 102
a
. a ım a a ¯ o

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

3.5.1 Thuˆt to´n Sutherland-Hodgman . . . . . . . . . . . . . . . . . . . . 108
a
. a

3.5.2 Thuˆt to´n Weiler-Atherton . . . . . . . . . . . . . . . . . . . . . . . 111
a
. a

3.5.3 C´c ph´p to´n tˆp ho.p trˆn c´c d a gi´c . . . . . . . . . . . . . . . . 113
a e a a . . e a ¯ a

3.6 ` ˙
’ `
Ray tracing hai chiˆu: phan xa trong buˆng k´ . . . . . . . . . . . . . . . . 114
e . o ın

3.6.1 ˙

Vector phan xa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
.

3.6.2 Giao cua tia s´ng v` d u.`.ng thˇng
˙
’ a a ¯ o ˙

a . . . . . . . . . . . . . . . . . . . 117

3.6.3 Giao cua tia s´ng v´.i d u.`.ng tr`n . . . . . . . . . . . . . . . . . . . . 121
˙
’ a o ¯ o o

3.6.4 Xˆy du.ng v´ du ray tracing . . . . . . . . . . . . . . . . . . . . . . . 124
a . ı .

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


4 Tˆ m`u v` ng
o a u 127

4.1 C´c d inh ngh˜ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
a ¯. ıa

4.1.1 V`ng d inh ngh˜ bo.i pixel . . . . . . . . . . . . . . . . . . . . . . . . 127
u ¯. ıa ˙



5
4.1.2 V`ng d inh ngh˜ bo.i d a gi´c . . . . . . . . . . . . . . . . . . . . . . . 129
u ¯. ıa ˙ ¯
’ a

4.2 e `
´ a
Thuˆt to´n tˆ m`u theo vˆt dˆu loang . . . . . . . . . . . . . . . . . . . . . 129
a
. a o a

4.3 Thuˆt to´n tˆ m`u theo con chay . . . . . . . . . . . . . . . . . . . . . . . . 131
a
. a o a .

4.4 Thuˆt to´n tˆ m`u theo biˆn . . . . . . . . . . . . . . . . . . . . . . . . . . 134
a
. a o a e

4.5 So s´nh c´c thuˆt to´n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
a a a
. a

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

4.7 Thuˆt to´n tˆ m`u d a gi´c . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
a
. a o a ¯ a

4.7.1 C´c d`ng qu´t ngang . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
a o e

4.7.2 ˙

C´c manh vun
a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151

4.7.3 ´
Liˆn kˆt canh v` thuˆt to´n tr`n . . . . . . . . . . . . . . . . . . . . 151
e e . a a
. a a

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

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


Phˆn phu luc: Thu. viˆn graph2D.h
`
a . . e
. 163


a e . ˙

T`i liˆu tham kha o 171




6
L`.i n´i d` u
o o ¯ˆ a

D` hoa m´y t´ l` mˆt l˜ vu.c hˆ p dˆ n cua khoa hoc m´y t´
-ˆ .
o a ınh a o ınh . a a ˙
. ´ ˜ ’ . a ınh. Ch´ng ta su. dung d` hoa
u ˙ .
’ ¯ˆ .
o
m´y t´ nhu. mˆt cˆng cu dˆ’ quan s´t thˆng tin trong nhiˆu l˜ vu.c kh´c nhau, bao gˆm
a ınh o o
. . ¯e˙ a o ` ınh .
e a `o
´ u a ˙ ı. a

khoa hoc v` cˆng nghˆ, ho´ hoc, kiˆn tr´c v` giai tr´ C´c chu .o.ng tr` d` hoa tu.o.ng t´c
. a o e. a . e ınh ¯o .
ˆ a
cho ph´p ngu.`.i su. dung l`m viˆc theo c´ch tu. nhiˆn nhˆ t: ngu.`.i su. dung cung cˆ p thˆng
e o ˙ .’ a e
. a . e ´
a o ˙ .’ ´
a o
tin cho tr` u
ınh ´ .ng dung thˆng qua c´c hoat d ong bˆn ngo`i cua ho v` s˜ nhˆn d u.o.c thˆng
o a a ˙’
. . ¯ˆ. e . a e a ¯ . . o
tin tro. lai bˇ ng h` anh. D` hoa m´y t´ d ang gi´p con ngu.`.i thay d ˆ’i vˆ quan niˆm v`
˙ . `
’ a ınh ˙’ -ˆ .
o a ınh ¯ u o ˙ e
¯o ` e. a
a .c su. dung m´y t´
c´ch th´ ˙ .
u ’ a ınh.

Gi´o tr` D` hoa m´y t´ I cung cˆ p mˆt sˆ k˜ thuˆt co. ban cua d` hoa m´y t´
a ınh - ˆ .
o a ınh ´
a . ´
o o y a
. ˙
’ ˙ ¯ˆ .
’ o a ınh
`e -ˆ .
hai chiˆu. (D` hoa m´y t´ ba chiˆu, mˆt phˆn quan trong khˆng thˆ’ thiˆu d u . e ¯ .
o a ınh `e o `a o e˙ e ¯
´ .o.c s˜ d u.o.c
. .
d` cˆp trong mˆt gi´o tr` kh´c). Dˆ’ c´ mˆt khung canh to`n diˆn v` sˆu sˇc vˆ nh˜.ng
¯ˆ a
e . o a
. ınh a -e o o
˙ . ˙
’ a e a a a `
. ´ e u
nguyˆn l´ v` thu a
e y a . .c h`nh cua d` hoa m´y t´
˙ ¯ˆ .
’ o a ınh, xem c´c t`i liˆu dˆn [9] v` [11]. C´c phu.o.ng
a a e a ˜ a a
.
ph´p phˆn t´ v` thiˆt kˆ c´c thuˆt to´n trong gi´o tr` cho ph´p sinh viˆn c´ thˆ’ viˆt
a a ıch a ´ ´
e e a a. a a ınh e e o e e ˙ ´
dˆ d`ng c´c chu.o.ng tr` minh hoa. Gi´o tr` d u.o.c biˆn soan cho c´c d ˆi tu.o.ng l` sinh
˜ a
e a ınh . a ınh ¯ . e . a ¯o´ . a
viˆn To´n-Tin v` Tin hoc.
e a a .

Gi´o tr` su. dung ngˆn ng˜. C dˆ’ minh hoa, tuy nhiˆn c´ thˆ’ dˆ d`ng chuyˆ’n d o’i
a ınh ˙ .
’ o u ¯e˙ . e o e ˜ a˙ e ˙
e ¯ˆ ˙
sang c´c ngˆn ng˜. kh´c; v` do d o, sinh viˆn cˆn c´ mˆt sˆ kiˆn th´.c vˆ ngˆn ng˜. C. Ngo`i
a o u a a ¯´ e ` o o o e
a . ´ ´ u ` o
e u a
`
a e a ´
ra, hˆu hˆt c´c chu .o.ng tr` thao t´c trˆn cˆ u tr´c d˜. liˆu nhu. danh s´ch liˆn kˆt, nˆn d oi
ınh a e a ´ u u e a e e ´ e ¯`
.
hoi sinh viˆn phai c´ nh˜.ng k˜ nˇng lˆp tr` tˆt.
˙
’ e ˙ o u
’ y a a
. ınh o ´

Sinh viˆn c˜ng cˆn c´ co. so. to´n hoc cua nh˜.ng nˇm d` u d ai hoc: hiˆ’u biˆt vˆ d ai sˆ
e u ` o
a ˙ a . ˙
’ ’ u a ¯ˆ ¯ . .
a e˙ e ` ¯. o
´ e ´
´ ˙ ıch, e ınh

tuyˆn t´ v` h` hoc giai t´ ph´p t´ vi t´ phˆn.
e ınh a ınh . ıch a

Muc d´ cua gi´o tr` l`, o. m´.c d o n`o d ´, cho thˆ y c´c tr` u.ng dung d` hoa
. ¯ıch ˙ ’ a ınh a ˙ u ¯ˆ a ¯o
’ . ´
a a ınh ´ . ¯ˆ .
o
¯ .o.c tao ra nhu. thˆ n`o: Ch´ng ta cˆn viˆt v` chay thu. c´c chu.o.ng tr`
du . . ´
e a u `a ´
e a . ˙ a
’ ınh. Mˆt trong
o.
nh˜ u.ng muc d´ ch´ cua gi´o tr` l` gi´p sinh viˆn nˇm v˜.ng c´c phu.o.ng ph´p, tru.´.c
˙
’ ´
. ¯ıch ınh a ınh a u e a u a a o
hˆt to´n hoc ho´ c´c kh´c niˆm h` hoc v` sau d ´ chuyˆ’n tai th`nh c´c d oan m˜ chu
e´ a a a a e ınh . a ¯o ˙ ’
e ˙ a a ¯ . a .o.ng
. .
tr`
ınh.


7
Gi´o tr` bao gˆm bˆn chu.o.ng v` mˆt phˆn phu luc v´.i nh˜.ng nˆi dung ch´ nhu.
a ınh `
o ´
o a o. `
a . . o u o
. ınh
sau:


• Chu.o.ng th´. nhˆ t d` cˆp dˆn c´c phu.o.ng ph´p v˜ c´c “nguyˆn so.” cua d` hoa m´y
u ´ e .
a ¯ˆ a ¯e a ´ a e a e ˙ ¯o .
’ ˆ a
ınh: d oan thˇng, d u.`.ng tr`n v` ellipse.
t´ ¯ . ˙

a ¯ o o a

• Phˆn t´ v` thiˆt kˆ bˇ ng h` hoc l` nˆi dung ch´ cua Chu.o.ng 2. Hˆu hˆt c´c
a ıch a e e `
´ ´ a ınh . a o . ınh ˙ ’ `
a e a´
phˆn mˆm d` hoa d` u c´ nh˜
`a ` ¯ˆ . ¯ˆ o u
e o e .ng ch´.c nˇng tao ra c´c d u.`.ng cong du.a trˆn c´c d iˆ’m
u a a ¯ o e a ¯e ˙
. .
m` ngu.`.i su. dung lu.a chon. Chu.o.ng n`y cung cˆ p nh˜.ng nguyˆn l´ v` c´ch tiˆp cˆn
a o ˙ .
’ . . a ´
a u e y a a ´ .
e a
.c h`nh m` c´c tr` u.ng dung d` hoa ´p dung.
thu a a a ınh ´ ¯o . a
ˆ
. . .

• Chu.o.ng 3 giai quyˆt b`i to´n x´c d inh giao cua nh˜.ng nguyˆn so. d` hoa: Giao hai
˙
’ ´
e a a a ¯. ˙
’ u e ¯ˆ .
o
d oan thˇng, giao cua d oan thˇng v` d a gi´c lˆi (bao h`m c´c h` ch˜. nhˆt) v` giao
¯ . ˙

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

• Chu.o.ng 4 d` cˆp dˆn nh˜.ng thuˆt to´n tˆ m`u v`ng bˆ t k`: V`ng d inh ngh˜ bo.i
¯ˆ a ¯e
e . ´ u a. a o a u ´
a y u ¯. ıa ˙

` ˙
’.i d u.`.ng biˆn v` v`ng l` d a gi´c.
phˆn trong, bo ¯ o
a e a u a ¯ a

• Phˆn phu luc l` thu. viˆn c´c cˆ u tr´c d˜. liˆu v` c´c h`m cˆn thiˆt v` thu.`.ng xuyˆn
`
a . . a e a a
. ´ u u e a a a `
. a ´
e a o e
su. dung trong gi´o tr`
˙ .
’ a ınh.


Trong lˆn xuˆ t ban th´. hai n`y, ch´ng tˆi d u.a thˆm c´c v´ du t´ to´n nhˇ m minh
`a ´ ’
a ˙ u a u o ¯ e a ı . ınh a `
a
` y ´
hoa cho phˆn l´ thuyˆt c˜ng nhu u
a e u . gi´p sinh viˆn nˇm v˜.ng kiˆn th´.c d ˜ hoc. Ngo`i ra, c´c
e a ´ u ´
e u ¯a . a a
.
lˆi trong xuˆ t ban lˆn tru.´.c c˜ng d a d u.o.c chınh l´; mˇc d` vˆy, t´c gia vˆn mong c´ nh˜.ng
˜
o a ˙ `
´ ’ a o u ¯˜ ¯ . ˙
’ y a u a a
. . ’ ˜
˙ a o u
¯o o u . ban d oc.
d ´ng g´p t` . ¯ .

Tˆi xin cam o.n nh˜.ng gi´p d o. d ˜ nhˆn d u.o.c t`. nhiˆu ngu.`.i m` khˆng thˆ’ liˆt kˆ
o ˙
’ u u ¯˜ ¯a a ¯ . u
. `
e o a o ˙ .
e e e
´
hˆt, d ac biˆt l` c´c ban sinh viˆn, trong qu´ tr` biˆn soan gi´o tr` n`y.
e ¯ˇ . e a a .
. e a ınh e . a ınh a

-a .
D` Lat, ng`y 10 th´ng 1 nˇm 2005
a a a

PHAM Tiˆn So.n
. ´
e




8
Chu.o.ng 1

C´c thuˆt to´n v˜ d .`.ng cong trˆn
a a
. a e ¯u o e
´
thiˆt bi raster
e .

Chu.o.ng n`y tr` b`y c´c thuˆt to´n v˜ d oan thˇng, d u.`.ng tr`n v` ellipse trˆn lattice
a ınh a a a
. a e ¯ . ˙

a ¯ o o a e
2
a a a ˙

nguyˆn Z . C´c thuˆt to´n chı thao t´c trˆn nh˜
e a e u.ng sˆ nguyˆn v` trong c´c v`ng lˇp chı su.
´
o e a a o a ˙ ˙
’ ’
. .
. a o . e a´ e . ˙

dung ph´p to´n cˆng nˆn rˆ t hiˆu qua.
e




1.1 - . ˙

Doan thˇ ng
a

Thuˆt to´n v˜ d oan thˇng x´c d .nh toa d o cua c´c pixel nˇ m trˆn hoˇc gˆn v´.i d oan thˇng
a
. a e¯ . a˙
’ a ¯i . ¯ˆ ˙ a
. ’ `
a e a ` o ¯ .
. a ˙

a
thu.c tˆ nhˆ t. Vˆ nguyˆn tˇc, ch´ng ta muˆn chon d˜y c´c pixel gˆn v´.i d oan thˇng thu.c tˆ
. e a´ ´ `e e a ´ u ´
o . a a ` o ¯ .
a a˙
’ . e ´
´ ˙
’ ´ ˙
’ .c tˆ d u.o.c xˆ p xı v´.i mˆt d o mˆt pixel; ta cˆn c´
nhˆ t v` thˇng nhˆ t. X´t d oan thˇng thu e ¯ . a ˙ o
a a a a e ¯ . a . ´ ´ ’ a ¯ˆ o
. . . ` o
a
nh˜.ng t´ chˆ t g` V´.i c´c d oan thˇng c´ hˆ sˆ g´c thuˆc d oan [−1, 1], c´ d ung mˆt pixel
u ´
ınh a ı? o a ¯ . ˙

a . ´
o e o o o ¯ .
. o ¯´ o
.
.o.c v˜ lˆn trˆn mˆ i cˆt; v´.i c´c d oan thˇng m` hˆ sˆ g´c nˇ m ngo`i d oan n`y, c´ d ung
du . e e
¯ e ˜ .
o o o a ¯ . ˙

a a e o o `
´ a a ¯ . a o ¯´
.
mˆt pixel d u.o.c v˜ trˆn mˆ i h`ng. Tˆ t ca c´c d oan thˇng d u.o.c v˜ v´.i c`ng mˆt d o s´ng,
o. ¯ . e e ˜
o a ´ ’
a ˙ a ¯ . ˙

a ¯ . e o u o ¯ˆ a
. .
khˆng phu thuˆc v`o d ˆ d`i v` hu o
o o a ¯o a a .´.ng, v` nhanh nhˆ t c´ thˆ’ d u.o.c. Thuˆt to´n v˜ d oan
a ´
a o e ¯ . ˙ a a e ¯ .
. . . .
˙

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

a . d ˆ rˆng, kiˆ’u v˜... Thˆm ch´
˙
e e a ı
. . . .
ch´ng ta muˆn cu e
u ´ .
o .c tiˆ’u ho´ m´.c d o rˇng cu.a do tiˆn tr` r`.i rac ho´ d u.`.ng thˇng thu.c
˙ a u ¯ˆ a ´
e ınh o . a ¯ o ˙

a
. .
´ . su. dung k˜ thuˆt antialiasing (xem [9], [11]) bˇ ng c´ch ´p dung kha nˇng d ˇt cu.`.ng
tˆ nh` ˙ .
e o ’ y a `
a a a ˙ a ¯a
’ o
. . .
d ˆ cua mˆ i pixel trˆn c´c thiˆt bi hiˆ’n thi m` mˆt pixel tu
¯o ˙ ˜ ´ ˙ .o.ng u.ng nhiˆu bit.
`
. ’ o e a e . e . a o . ´ e

Tru.´.c hˆt ch´ng ta chı d` cˆp dˆn c´c d oan thˇng d o rˆng mˆt pixel v` c´ d ung mˆt
o e ´ u ’ e . ´
˙ ¯ˆ a ¯e a ¯ . ˙

a ¯ˆ o
. . o
. a o ¯´ o.
pixel trˆn mˆ o
e o . a a ´ o
¯o .i c´c d oan thˇng dˆc). Phˆn cuˆi chu.o.ng s˜ d` cˆp
˜i cˆt (hoˇc h`ng d ˆi v´ a ¯ . ˙

a ´
o `a ´
o e ¯ˆ a
e .
.

9
dˆn d o rˆng c´c nguyˆn so. v` c´c mˆ u v˜.
´ . .
¯e ¯ˆ o a e a a ˜
a e

Mˆt c´ch h` hoc, ch´ng ta biˆ’u diˆn mˆt pixel nhu. mˆt chˆ m tr`n v´.i tˆm tai vi
o a
. ınh . u e˙ ˜
e o
. o
. ´
a o o a . .
.´.i c´c toa d o nguyˆn Z2 . Biˆ’u diˆn n`y l` mˆt xˆ p xı th´ ho.p
˙ ˜ a a o a ˙ ıch .
˙

tr´ (x, y) cua pixel trˆn lu o a . ¯ˆ
ı e . e e e . ´ ’
´ y ˙’
nh´t cˇt ngang trong mˆt chu k` cua ch`m tia electron cua CRT; xˆ p xı n`y phu thuˆc v`o
a a o
. u ˙
’ ´ ’
a ˙ a . o a
.
.a c´c vˆt trˆn m`n h` hiˆ’n thi. Trong mˆt sˆ
˙
˙

khoang c´ch (tu` thuˆc v`o hˆ thˆng) gi˜ a e
a y o a e o
. . ´ u ´ e a ınh e . . ´
o o
hˆ thˆng, c´c chˆ m kˆ nhau phu lˆ p mˆt phˆn lˆn nhau; v´.i nh˜.ng hˆ thˆng kh´c c´ nh˜.ng
. ´
e o a a `
´ e ’ ´
˙ a o. ` e
a o u . ´
e o a o u
˙

khoang c´ch gi˜ a
a u .a c´c pixel d u.ng kˆ nhau; trong hˆu hˆt c´c hˆ thˆng, khoang c´ch theo
¯´ `e ` ´
a e a e o ´ ˙
’ a
.
chiˆu ngang nho ho.n theo chiˆu d u.ng. Mˆt kh´c biˆt n˜.a tu` theo hˆ thˆng trong viˆc biˆ’u
`
e ˙
’ ` ¯´
e o. a e u
. y . ´
e o e. e˙
diˆn hˆ toa d o, chˇng han Macintosh xem c´c pixel d u.o.c d at tai tˆm cua h` ch˜. nhˆt
˜ e . ¯ˆ
e . . a˙
’ . a ¯ . ¯ˇ . a . ˙
’ ınh u a
.
.a c´c d u.`.ng thˇng kˆ nhau cua lu.´.i d iˆu khiˆ’n thay cho nˇ m trˆn c´c d u.`.ng thˇng cua
gi˜ a ¯ o
u a˙
’ `
e ˙
’ o ¯e ` e ˙ `
a e a ¯ o ˙
a’ ˙

.´.i. Theo c´ch n`y, c´c h` ch˜. nhˆt (x´c d inh bo.i hai g´c) gˆm c´c pixel thuˆc phˆn
lu o a a a ınh u a a ¯. ˙
’ o `
o a o `
a
. .
trong cua n´. D.nh ngh˜ n`y cho ph´p c´c v`ng d ˆ rˆng bˇ ng khˆng: H` ch˜. nhˆt t`.
˙ o -i
’ ıa a e a u ¯o o . . `
a o ınh u a u
.
´
(x, y) dˆn (x, y) khˆng ch´
¯e o u.a pixel n`o, trong khi v´.i nh˜.ng hˆ thˆng kh´c, c´ d ung mˆt
a o u e o ´ a o ¯´ o
. .
pixel tai d iˆ
. ¯e ˙m n`y. Du.´.i d ay ch´ng ta s˜ biˆ’u diˆn c´c pixel nhu. c´c h` tr`n r`.i nhau c´
’ a o ¯ˆ u e e ˙ ˜ a
e a ınh o o o
a `
tˆm nˇ m trˆn lu o
a e .´.i.

H` 1.1 l` ph´ng to cua d u.`.ng thˇng thu.c tˆ v` xˆ p xı d o rˆng mˆt pixel cua n´.
ınh a o ˙ ¯ o
’ ˙

a ´ ´ ’ . .
. e a a ˙ ¯ˆ o o. ˙
’ o
a ¯ .o.c v˜ tu.o.ng u.ng c´c h` tr`n m`u d en v` c´c pixel khˆng d u.o.c v˜ tu.o.ng u.ng
C´c pixel d u . e ´ a ınh o a ¯ a a o ¯ . e ´
h` tr`n khˆng tˆ. Trˆn m`n h` thu.c tˆ, d u.`.ng k´ cua h` tr`n biˆ’u diˆn pixel l´.n
ınh o o o e a ınh . e ¯ o ´ ınh ˙ ınh o
’ e˙ ˜
e o
ho.n khoang c´ch gi˜.a c´c pixel kˆ nhau, bo.i vˆy biˆ’u diˆn bˇ ng k´ hiˆu cua ch´ng ta l`
˙
’ a u a `
e ˙ a
’ . e˙ ˜ a
e ` y e ˙
’ u a
.
mˆt ph´ng d ai m´.c d o r`.i rac cua c´c pixel.
o
. o ¯. u ¯ˆ o . ˙ a
. ’

.
. .
. .
. .
. .
.
.
.
. .
.
. .
.
. .
.
. .
.
.
.
.
. .
.
. .
.
. .
.
. .
.
.
.
.
. .
. .
. .
. .
.
............i
............
.
.
.
i .
.
.
.
.
. i .
.
.
.
.
. i .
.
.
.
.
.
.
i
.
. ...................... ...................... .......................................................
.
....................................................................................................
.
.
.
.
.
. .
.
. .
.
. .
.
. .
.
.
.
.
. .
.
. .
.
. .
.
. .
.
.
.
.
. .
.
. .
.
. .
.
. .
.
.
.
. .
. .
. .
. .
. ...
.
.
. .
. .
. .
. . ....
. . .....
.
.
.
.
.
.
.
.
.
.
.
.
. . ......
.
.
.
.
.
.
.
.
.
.
.
.
. ....
....
.. .
.
. . . . .... .
.... .
i.
.
.
.
.
i .
.
.
.
.
.
i .
.
.
.
.
.
i
y .
.
..
. ... .
. ..
. .......
.
..
.
i
y
.
.................................................................................................................
.............................................................................. ..................................
. .
.
.
.
.
.
. .
.
. .
.
. . .
.
.....
....
.
.
.
. . . .
..... .
.
.
.
.
.
.
.
.
. .....
.. .
. . .
.
.
.
.
.
.
.
.
.
.
. ..
. ....
.... .
.
.
.
.
.
. .
. . .......
. .... .
. .
.
.
.
. .
.
. . .... ..
.
....... .
.
. .
.
.
. . .
.... . .
.
.
.
.
.
. ...
.. .
. . .
.
.
.
.
.
. . .... .
.... . . .
i.
.
. i
y .
. . .
.. ..
..
i
y . i .
. i
.
.
.................................................................................................................
............................................................................... .................................
.
.
.
.
.
. . ....
. .......
.
.
.
. .
.
.
. .
.
.
.
.
.
. .
....
...
. .
.
. .
.
. .
.
.
. .
.. . . .
.
.
. .... .
.... .
.. .
. . .
.
.
.
.
.
.
.
.
.
.
. ..
. ....
.... .
.
.
.
.
.
.
.
.
.
.
. .......
. .... .
. .
. .
. .
.
. .... .
.
....... .
.
. .
.
. .
.
. .
.
.
.
....
. .
. .
. .
. .
.
....
.. .
. .
. .
. .
. .
.
.... .
.... .
..
.. i
y.
.
.
i .
.
.
.
.
.
i .
.
.
.
.
i .
.
.
.
.
. i
.
.
.................................................................................................................
.................................. ............................................ .................................
. . .
.
.
.
.
. .
. .
. .
. .
.
.
. .
. .
. .
. .
.
.
.
. .
.
. .
.
. .
.
. .
.
.
.
.
. .
.
. .
.
. .
.
. .
.
.




H` 1.1: Doan thˇng xˆ p xı d u.o.c biˆ’u diˆn bo.i c´c h` tr`n d en.
ınh - . ˙

a ´ ’
a ˙ ¯ . e˙ ˜
e ˙ a ınh o ¯


V` c´c nguyˆn so. trong hˆ thˆng ch´ng ta x´c d inh trˆn lu.´.i d iˆu khiˆ’n nguyˆn nˆn
ı a e . ´
e o u a ¯. e o ¯` e e˙ e e
c´c toa d o d` u cuˆi cua d oan thˇng l` nguyˆn. Thˆt ra, nˆu ch´ng ta cˇt d oan thˇng v´.i
a . ¯ˆ ¯ˆ . a ´ ’
o ˙ ¯ . ˙

a a e a
. ´
e u ´
a ¯ . ˙

a o
h` ch˜
ınh u . nhˆt tru.´.c khi hiˆ’n thi n´ th` toa d ˆ c´c d iˆ’m d` u cuˆi cua d oan thˇng c´ thˆ’
a o e˙ ˙ ´ ’
o ˙ ¯ . ˙
’ ˙
. . o ı . ¯o a ¯ e ¯ˆ
. a a o e
khˆng nguyˆn. (Ch´ng ta s˜ thao luˆn c´c giao d iˆ’m khˆng nguyˆn trong Phˆn 1.1.3). Gia
o e u e ˙ ’ a a
. ¯e˙ o e `a ˙



10
su. d oan thˇng c´ hˆ sˆ g´c |m| ≤ 1; c´c tru.`.ng ho.p kh´c d u.o.c xu. l´ tu.o.ng tu.. Ho.n n˜.a
˙ ¯ .
’ ˙

a . ´
o e o o a o . a ¯ . ˙ y
’ . u
.`.ng ho.p c´c d oan thˇng ngang, d u.ng hoˇc c´ hˆ sˆ g´c ±1 l` tˆm thu.`.ng v` ch´ng chı
˙

tru o . a ¯ . a ¯´ . ´
a o e o o
. a `a o ı u ˙

d i qua c´c pixel trˆn lu.´.i.
¯ a e o



1.1.1 a
. a o ´
Thuˆt to´n sˆ gia

X´t hai pixel A = (xA , yA ) v` B = (xB , yB ) (t´c c´c phˆn tu. cua lattice nguyˆn Z2 ). Phu.o.ng
e a u a ` ˙ ˙
a ’ ’ e
tr` d u.`.ng thˇng AB c´ dang y = mx + t, trong d o hˆ sˆ g´c m = dy/dx v` t = yA − mxA .
ınh ¯ o a˙
’ o . . ´
¯´ e o o a
C´ch d o
a ¯ .n gian nhˆ t dˆ’ v˜ d oan thˇng AB l`:
˙
’ ´ ˙
a ¯e e ¯ . ˙

a a



. ´
1. T´ hˆ sˆ g´c m;
ınh e o o

2. Tˇng x mˆt d o.n vi (kho.i d` u t`. d iˆ’m bˆn tr´i nhˆ t), v´.i mˆ i xi t´ yi = mxi + t v`
a o ¯
. . ˙ ¯ˆ u ¯ e
’ a ˙ e a ´
a o o ˜ ınh a
sau d ´ v˜ pixel tai (xi , yi + 0.5 )1 .
¯o e .


Theo c´ch n`y ta chon pixel tˆt nhˆ t, t´.c l` pixel m` khoang c´ch dˆn d u.`.ng thˇng thu.c
a a . ´
o ´
a u a a ˙
’ ´
a ¯e ¯ o ˙

a .
´ ˙ ’ a ´
tˆ nho nhˆ t. Phu
e .o.ng ph´p n`y khˆng hiˆu qua do mˆ i bu.´.c lˇp cˆn t´ mˆt ph´p nhˆn,
a a o e ˙
’ ˜
o o a ` ınh o
. . a . e a
mˆt ph´p cˆng v` mˆt ph´p to´n l`m tr`n. Ta c´ thˆ’ khu e
o e o a o e a a o o e ˙ ˙ ’. ph´p nhˆn bˇ ng c´ch ch´ y rˇ ng
a ` a a u´ `a
. . .

yi+1 = mxi+1 + t
= m(xi + ∆x) + t
= yi + m∆x,

v` nˆu bu.´.c tˇng ∆x = 1 th` yi+1 = yi + m.
a e´ o a ı

Do d o nˆu x tˇng mˆt d o.n vi th` y tˇng m d o.n vi. V´.i moi d iˆ’m (xi , yi ) trˆn d oan
¯´ e ´ a o ¯
. . ı a ¯ . o . ¯e˙ e ¯ .
thˇng ta biˆt rˇ ng nˆu xi+1 = xi + 1 th` yi+1 = yi + m; t´.c l`, c´c gi´ tri x v` y d u.o.c t´
˙
a’ e `
´ a ´
e ı u a a a . a ¯ . ınh
a a . .´.c d ´ cua n´ (xem H` 1.2). Dˆy ch´ l` “thuˆt to´n sˆ gia”: v´.i mˆi
theo c´c gi´ tri tru o ¯o ˙ o ’ ınh -a ınh a a ´
a o o o ˜
.
bu.´.c lˇp ta thu.c hiˆn c´c ph´p to´n sˆ gia du.a trˆn bu.´.c tru.´.c.
o a . . e a
. e a o´ . e o o

Kho.i tao ta g´n (x0 , y0 ) l` toa d o nguyˆn cua d iˆ’m xuˆ t ph´t, chˇng han A. Ch´ y
˙ .
’ a a . ¯ˆ . e ˙ ¯e
’ ˙ a´ a ˙

a . u´
rˇ ng trong tru.`.ng ho.p |m| > 1 nˆu x tˇng mˆt d o.n vi th` y tˇng ho.n mˆt d o.n vi. Do d ´
`
a o . ´
e a o ¯
. . ı a o ¯
. . ¯o
`
a a ¯ˆ ˙ o ˙ ’ a `
a a a .´.c tˇng mˆt d o.n vi cho y v` tˇng x mˆt
cˆn ho´n d o’i vai tr` cua x v` y bˇ ng c´ch g´n bu o a o ¯ a a o
. . .
.o.ng ∆x =
lu . ∆y 1
= m.
m



1
K´ hiˆu [x], x v` x tu.o.ng u.ng l` phˆn nguyˆn, l`m tr`n xuˆng v` l`m tr`n lˆn cua x.
y e . a ´ a ` a e a o ´
o a a o e ˙



11
Du.`.ng thˇng
- o ˙

. . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
a
.
. .
. .
. .
.
.c tˆ
. ´
. . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
thu e ....
....
.
.
.
. .
. .
. .
. ....
....
.
. .
. .
. .
. ...
...
.
.
.
.
.
.
.
.
. w .
.
.
. . . . .
....
................................................................................................
.................................................... ....................
................................................
........................ . . .
. ...... . .
.
.
. .
.
. .
.
. ....
.
...
.
. . . ....
.
.
. .
. .
. .... .
.... .
.
.
. .
.
. .
.
. ......
.... .
.
.
.
.
. .
.
. .
.
. ....
....
.
.
.
. . ......
(xi + 1, yi + m ) .........
......... .........
.........
.
.
.
.
.
..........
.
..........
. ..
. .......
.
.
.
.
.
.
.
.
. ....
... .
... .
.
. .......
.
....
..
....
.
.
.
.
.
.
.
.
.
. .............. .
. .......... . . .... .
....
.
. .
.
.
.
.
.
.
.
w
..... .
.
. .... .
.
. .....
.. .. .
..
w .
.
.
.
.
.
.
......................................................................... ..............................................
.........................................................................................................................
. .
.
.
.
.
.
. .
.....
. .. .
.
. .
.
.
.
(xi , yi ) ...........
...........
.
.
.
.
.
.
.
.
. ....
.
....
.
. .
. ...
.... ...
.... .....
.
......
.......
..
. ..
. .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...........
........... ...........
........... . . .....
.
. .......
. . ..
.
. .. .
.
. .
.
.
............. . ....
............. . ... . .
. ...
. .. .
.
. .
.
.
.......
.. . .
.......
.... .
. .. .
. .
.
. .. . .
...................
..................
..
..
.
. w
........ .............................................................................................
.. .
... .
.
.
.
.
.
.
.
....
..
.
.
.
.
.
.
.
......................................................................................................
. .
.
.
. ....
....
. .. . .
.... .
... .
..
. .
.
.
. ..
..
.
.
. .
.
.
. . .
.
. ....
.... . ... .
... .
.
. ..
..
.
.
. .
.
.
....
.... .
....
... .
.
. .
.
. ..
..
.
.
. .
.
.
.
....
... .
.
. .
.
. ..
.
.
. .
.
.
.....
... .
.
. .
.
.
..
..
.
.
. .
.
.
.....
... .
.
. .
.
. ..
.. .
.
.
. .
.
.
.....
... .
.
. .
.
. .. .
.. .
. .
.
.
.....
... .
.
.
.
.
.
.
.
.. . . .
.
.
.....
... . . .. .
.. . .
.
..
. ...
... ..
..



(xi , yi ) (xi + 1, yi + m)



´ ˙

H` 1.2: T´ to´n sˆ gia cua (xi , yi ).
ınh ınh a o

V´ du 1.1.1 Gia su. A(2, 0), B(9, 3). Khi d ´ d u.`.ng thˇng qua hai d iˆ’m A v` B c´ hˆ sˆ
ı . ˙ ˙
’ ’ ¯o ¯ o ˙

a ¯e˙ a . ´
o e o
g´c m = 3 ∈ (0, 1). Ap dung thuˆt to´n sˆ gia ta d u.o.c d˜y c´c d iˆ’m v˜ tˆt nhˆ t nhu. trong
o 7
´ . a
. a o ´ ¯ . a a ¯e ˙ e o´ a´
˙
’ .´.i:
bang du o
i xi yi yi + 0.5
0 2 0 0
3
1 3 7
0
6
2 4 7
1
9
3 5 7
1
12
4 6 7
2
15
5 7 7
2
18
6 8 7
3
21
7 9 7
3


Thu tuc Line() du.´.i d ay minh hoa thuˆt to´n v˜ d oan thˇng t`. (x0 , y0 ) dˆn (x1 , y1 )
˙ .
’ o ¯ˆ . a
. a e ¯ . ˙

a u ´
¯e
v´.i gi´ tri m`u V alue. Diˆ’m kho.i d` u l` d iˆ’m bˆn tr´i nhˆ t. Ngo`i ra ta chı x´t tru.`.ng ho.p
o a . a - e˙ ˙ ¯ˆ a ¯ e
’ a ˙ e a ´
a a ˙ e
’ o .
−1 ≤ m ≤ 1 v` c´c tru o
ı a .`.ng ho.p kh´c c´ thˆ’ thu.c hiˆn do t´ d oi x´.ng. Ho.n n˜.a, ch´ng ta
a o e ˙ . e ´ u
ınh ¯ˆ u u
. .
c˜ng bo qua viˆc kiˆ’m tra c´c tru o
u ˙
’ e e˙ a .`.ng ho.p d ac biˆt: d u.`.ng thˇng nˇ m ngang, d u.ng, xiˆn
˙
’ `
. . ¯ˇ . e ¯ o
. a a ¯´ e
mˆt g´c ±450 . Ch´ y rˇ ng, trong ngˆn ng˜. C, (int)y bˇ ng y + 0.5 .
o o
. u´ ` a o u `
a


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


12
int x;
int dx, dy;
float y, m;


dx = x_B - x_A;
dy = y_B - y_A;
m = dy/(float)dx;
y = y0;


for (x = x_A; x 0},
(l− ) := {(x, y) ∈ R2 | f (x, y) < 0}.


Y tu.o.ng cua thuˆt to´n d iˆ’m gi˜.a l` xˆy du.ng mˆt d˜y c´c d iˆ’m v˜ “tˆt nhˆ t” (xi , yi )
´ ˙
’ ˙
’ a. a ¯e˙ u a a . o a a ¯e
. ˙ e o ´ ´
a
a ¯ˆ u ˙
´ a . d iˆ’m (x , y ) = (x , y ). Kh´i niˆm tˆt nhˆ t o. d ˆy l` nh˜.ng d iˆ’m (x , y ) d u.o.c
bˇt d` u t` ¯ e a e ´
o ´ ’
a ˙ ¯a a u ¯e ˙
0 0 A A . i i ¯ .

chon gˆn v´.i d u.`.ng thˇng thu.c tˆ (dang liˆn tuc) nhˆ t. Theo gia thiˆt, 0 < m < 1, nˆn khi
. ` o ¯ o
a a˙
’ ´
. e . e . ´
a ˙
’ ´
e e
x tˇng mˆt lu .
a o .o.ng ∆x th` y tˇng khˆng qu´ ∆y = m∆x d o.n vi.
ı a o a ¯
. .

V` vˆy nˆu bu.´.c th´. i chon d u.o.c d iˆ’m v˜ tˆt nhˆ t C := (xi , yi ) th` o. bu.´.c th´. i + 1
ı a e
. ´ o u . ¯ . ¯e ˙ e o´ a´ ı ˙ ’ o u
ta s˜ chon d iˆ’m v˜ (xi+1 , yi+1 ), trong d o xi+1 = xi + 1 v` yi+1 = yi hoˇc yi+1 = yi + 1.
e . ¯e ˙ e ¯´ a a
.
N´i c´ch kh´c, bu o
o a a .´.c th´. i + 1 ch´ng ta s˜ chon mˆt trong hai pixel R := (x + 1, y ) hoˇc
u u e . o a
. i i .
D := (xi + 1, yi + 1) (xem H` 1.3). K´ hiˆu Q l` giao d iˆ’m cua hai d u o
ınh y e a ¯e ˙ ˙
’ ¯ .`.ng thˇng l v`

’ a
.
x = xi + 1. Theo Bresenham, dˆ u cua biˆ’u th´.c x´c d inh bo.i hiˆu gi˜.a hai khoang c´ch t`.
´ ˙
a ’ e˙ u a ¯. ˙
’ e
. u ˙’ a u
a ´
¯e e a ¯. o´
R v` D dˆn Q cho ph´p x´c d inh pixel tˆt nhˆ t o ´ ’
a ˙ . bu.´.c i + 1. Trong thuˆt to´n d iˆ’m gi˜.a,
o a a ¯e ˙ u
.
ta quan s´t vi tr´ cua d iˆ’m gi˜.a M v` c´c nu.a mˇt phˇng x´c d inh bo.i d u.`.ng thˇng l. Dˆ
a . ı ˙ ¯e ’ ˙ u a a ˙ ’ a
. ˙

a a ¯. ˙ ¯ o
’ ˙

a ˜
e
a ˙
’ ` ´ +
d`ng chı ra rˇ ng, nˆu M ∈ (l ) th` pixel D gˆn v´ ¯ o
a e ı `
a o .i d u.`.ng thˇng l ho.n; nˆu M ∈ (l− ) th`
˙

a ´
e ı
pixel R gˆn ho.n. Du.`.ng thˇng l c´ thˆ’ d i ngang qua M ; hoˇc ca hai pixel nˇ m vˆ c`ng
`
a - o ˙

a o e ¯˙ a ˙
. ’ `
a ` u
e
o ˙
mˆt nu ’.a mˇt phˇng (l+ ) (hoˇc (l− )) nhu.ng trong bˆ t c´. tru.`.ng ho.p n`o, ta vˆ n chon d iˆ’m
a ˙

a a ´
a u o a ˜
a ˙
. . . . . ¯e
gˆn v´.i l nhˆ t. Ho.n n˜.a, sai sˆ-t´.c l` khoang c´ch gi˜.a pixel d u.o.c chon v` d u.`.ng thˇng
`
a o ´
a u ´
o u a ˙
’ a u ¯ . . a ¯ o ˙
a’
.c tˆ l-luˆn luˆn nho ho.n hoˇc bˇ ng 1/2.
a `
. ´
thu e o o ˙
’ . a

14
Dˆ’ ´p dung thuˆt to´n d iˆ’m gi˜.a, chı cˆn t´ f (M ) = f (xi + 1, yi + 1 ) v` kiˆ’m tra
-ea
˙ . a
. a ¯e ˙ u ˙ ` ınh
’ a 2
a e ˙
´ ˙ o
a ’ ¯o ¯. ıa e ´ ´
dˆ u cua n´. Do d ´ ta d inh ngh˜ biˆn quyˆt d. nh
e ¯i

di := f (xi + 1, yi + 1 )
2
1
= a(xi + 1) + b(yi + 2 ) + c.

Khi d ´
¯o


´
1. Nˆu di > 0 chon pixel D;
e .
´
2. Nˆu di < 0 chon pixel R;
e .
´
3. Nˆu di = 0 chon mˆt trong hai pixel R hoˇc D, do d ´ chon R.
e . o
. a
. ¯o .


Kˆ tiˆp ta cˆn x´c d inh toa d ˆ d iˆ’m gi˜.a M v` do d o biˆn quyˆt d .nh di+1 o. bu.´.c i + 1;
´ ´
e e `
a a ¯. . ¯o ¯ e
. ˙ u a ¯´ e ´ ´
e ¯i ˙
’ o
d˜ nhiˆn d iˆu n`y phu thuˆc v`o viˆc chon pixel R hoˇc D. Nˆu chon R th` ho`nh d o d iˆ’m
ı e ¯` e a . o a
. e
. . a
. ´
e . ı a ¯ˆ ¯ e
. ˙
M tˇng mˆt d o.n vi v` tung d o khˆng d o’i. Do d o
a o ¯
. . a ¯ˆ o ¯ˆ
. ˙ ¯´
1 1
di+1 = f (xi + 2, yi + ) = a(xi + 2) + b(yi + ) + c.
2 2
Nhu.ng
1
di = a(xi + 1) + b(yi + ) + c.
2
Suy ra di+1 = di + a.

K´ hiˆu sˆ gia d u.o.c cˆng thˆm khi R d u.o.c chon l` ∆R := a = dy. N´i c´ch kh´c, ta
. ´
y e o ¯ . o . e ¯ . . a o a a
c´ thˆ’ suy ra biˆn quyˆt d .nh o
o e ˙ ´
e ´
e ¯i ˙
’. bu.´.c kˆ tiˆp t`. biˆn quyˆt d inh o. bu.´.c hiˆn h`nh bˇ ng
´ ´
o e e u e ´ ´
e ¯. ˙
’ o e a `
a
.
o. e ´
o a o `
a ˙ ınh . a .

c´ch cˆng thˆm sˆ gia ∆R m` khˆng cˆn phai t´ lai gi´ tri f (M ).
a

Nˆu chon D th` ho`nh d o v` tung d o d iˆ’m M c`ng tˇng mˆt d o.n vi, nˆn
´
e . ı a ¯ˆ a
. ¯ˆ ¯ e
. ˙ u a o ¯
. . e
3 3
di+1 = f (xi + 2, yi + ) = a(xi + 2) + b(yi + ) + c.
2 2
V` do d ´
a ¯o
di+1 = di + a + b.
K´ hiˆu sˆ gia d u.o.c cˆng v`o di+1 sau khi chon D l` ∆D := a + b = dy − dx.
. ´
y e o ¯ . o . a . a

V` o. bu.´.c d` u tiˆn, ta chon (x0 , y0 ) = (xA , yA ) nˆn c´ thˆ’ t´ tru.c tiˆp gi´ tri kho.i
ı ˙
’ o ¯aˆ e . ˙
e o e ınh . ´
e a . ˙

tao d0 . Thˆt vˆy, d iˆ’m gi˜.a d` u tiˆn c´ toa d ˆ (x0 + 1, y0 + 1 ), v`
. a a ¯e
. . ˙ u ¯ˆ a e o . ¯o . 2
a

f (x0 + 1, y0 + 1 ) = a(x0 + 1) + b(y0 + 2 ) + c
2
1

= ax0 + by0 + c + a + b/2
= f (x0 , y0 ) + a + b/2.

15
Nhu.ng (x0 , y0 ) thuˆc d u.`.ng thˇng l nˆn f (x0 , y0 ) = 0; do d ´ gi´ tri kho.i d` u cua biˆn
o ¯ o
. ˙

a e ¯o a . ˙ ¯ˆ
’ a ˙
’ ´
e
´
quyˆt d .nh l` d0 = a + b/2 = dy − dx/2. Su .
e ¯i a ˙
’. dung d ta c´ thˆ’ chon pixel th´. hai, th´.
o e ˙ . u u
0
-e˙ ’. mˆu sˆ trong d ta d inh ngh˜ lai h`m f bˇ ng c´ch nhˆn n´ cho 2; t´.c l`
ba, v.v. Dˆ’ khu a o
˙ ˜ ´ ¯. ıa . a `
a a a o u a
0

a a a a ` ´
o a e ´ ´
f (x, y) = 2(ax + by + c). N´i c´ch kh´c, nhˆn 2 cho c´c hˇ ng sˆ a, b, c v` biˆn quyˆt d inh;
o a e ¯.
m` d iˆu n`y khˆng anh hu.o.ng dˆn dˆ u cua biˆn quyˆt d .nh.
a ¯`e a o ˙ ’ ˙
’ ´ ´ ˙
¯e a ’ ´
e ´
e ¯i

Tˆ’ng qu´t ho´ thuˆt to´n d iˆ’m gi˜.a v˜ d oan thˇng AB (trong tru.`.ng ho.p xA < xB
o˙ a a a
. a ¯e ˙ u e ¯ . ˙

a o .
v` 0 < m < 1) nhu
a . sau:



1. [Kho.i tao] Dˇt dx = xB − xA , dy = yB − yA , d0 = 2dy − dx, ∆R = 2dy, ∆D = 2(dy −
˙ . -a
’ .
dx), x0 = xA , y0 = yA .


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


e e a
. -a ¯e
3. [V˜ pixel hiˆn h`nh] Dˇt d iˆ’m v˜ tai (xi , yi ).
. ˙ e .


4. [Cˆp nhˆt] Nˆu xi = xB , thuˆt to´n d`.ng; ngu.o.c lai, d at
a
. a
. ´
e a
. a u . . ¯ˇ .

xi+1 = xi + 1;
yi ´
nˆu di ≤ 0,
e
yi+1 =
yi + 1 nˆu ngu.o.c lai;
´
e . .
di + ∆R nˆ´u di ≤ 0,
e
di+1 =
di + ∆D nˆu ngu.o.c lai.
´
e . .


5. Thay i bˇ ng (i + 1) v` lˇp lai Bu.´.c 3.
`
a a a .
. o



V´ du 1.1.2 Gia su. A(2, 0), B(9, 3). Khi d ´ d u.`.ng thˇng qua hai d iˆ’m A v` B c´ hˆ sˆ
ı . ˙ ˙
’ ’ ¯o ¯ o ˙

a ¯e ˙ a . ´
o e o
g´c m = 3 ∈ (0, 1). Dˆ d`ng kiˆ’m tra rˇ ng
o 7
˜ a
e e˙ `
a


dx = xB − xA = 7,
dy = yB − yA = 3,
d0 = 2dy − dx = −1,
∆R = 2dy = 6,
∆D = 2(dy − dx) = −8.

16
Ap dung thuˆt to´n d iˆ’m gi˜.a ta c´ d˜y c´c d iˆ’m v˜ tˆt nhˆ t nhu. trong bang du.´.i:
´ . a
. a ¯e ˙ u o a a ¯e ˙ e o´ ´
a ˙
’ o

i xi yi di
0 2 0 −1
1 3 0 5
2 4 1 −3
3 5 1 3
4 6 2 −5
5 7 2 1
6 8 3 −7
7 9 3 −1

Hiˆ’n nhiˆn rˇ ng c´c kˆt qua n`y tr`ng v´.i kˆt qua khi su. dung phu.o.ng ph´p sˆ gia trong
e˙ e ` a a e ´ ˙ a
’ u o e ´ ˙
’ ˙ .
’ a o ´
V´ du 1.1.1.
ı .


Ch´ y rˇ ng, ph´p t´ cˆn thiˆt d oi v´.i di+1 trong mˆ i bu.´.c lˇp l` ph´p cˆng v` khˆng
u´ ` a e ınh ` a ´ ´
e ¯ˆ o ˜
o o a a e o
. . a o
c´ ph´p nhˆn. Ho
o e a .n n˜.a, v`ng lˇp ho`n to`n d o.n gian nhu. trong thu tuc MidPointLine()
u o a a a ¯ ˙
’ ˙ .

.
du.´.i d ˆy:
o ¯a


void MidPointLine(int x_A, int y_A, int x_B, int y_B, int Value)
{
int x, y, d, dx, dy, DeltaR, DeltaD;


dx = x_B - x_A;
dy = y_B - y_A;
d = 2*dy - dx;
DeltaR = 2*dy;
DeltaD = 2*(dy - dx);
y = y_A;


for (x = x_A; x 0 th` d ˇt
e ı ¯a.
di+1 = di + b2 (−2xi + 3),
yi+1 = yi .

• Ngu.o.c lai d ˇt
. . ¯a .
di+1 = di + b2 (−2xi + 3) + a2 (2yi + 2),
yi+1 = yi + 1.

4. Dˇt xi+1 = xi − 1, thay i bo.i i + 1 v` chuyˆ’n sang Bu.´.c 2.
-a
. ˙
’ a e˙ o


Nhˆn x´t 1.3.1 (i) Trong tru.`.ng ho.p c´c toa d o tˆm ellipse v` c´c b´n k´ a, b nguyˆn,
a. e o . a . ¯ˆ a . a a a ınh e
dˆ’ tr´nh t´ to´n trˆn sˆ thu.c, ch´ng ta c´ thˆ’ khu. phˆn sˆ v` chı ´p dung c´c ph´p to´n
˙
¯e a ınh a ´
e o . u o e ˙ ˙ ’ ´
a o a ˙a ’ . a e a
e o ´
trˆn sˆ nguyˆn.
e

(ii) C˜ng c´ thˆ’ t´ c´c h`m ∆ tru.c tiˆp trong mˆi bu.´.c lˇp hoˇc su. dung phu.o.ng ph´p
u ˙
o e ınh a a . ´
e ˜
o o a . a ˙ .
. ’ a
sai phˆn bˆc hai nhu
a a . trong thuˆt to´n v˜ d u.`.ng tr`n. Ch´ng ta c´ thˆ’ v˜ c´c ellipse qua
a a e ¯ o o u ˙
o e e a
. .

33
H` 1.10: (a) H` vuˆng bao d u.`.ng tr`n. (b) H` vuˆng v` h` tr`n qua ph´p biˆn
ınh ınh o ¯ o o ınh o a ınh o e ´
e
d ˆ’i.
¯o ˙

ph´p quay v` c´c ellipse c´ “d o dˆy” hep; t´.c v´.i nh˜.ng tru.`.ng ho.p |a|
e a a o ¯ˆ `
. a . u o u o . 1 |b| hoˇc
a
.
.o.c lai (xem [6]).
ngu . .



1.3.2 Ellipse trong tru.`.ng ho.p tˆ’ng qu´t
o . o˙ a

Trong phˆn tru.´.c ta d a xˆy du.ng thuˆt to´n v˜ d u.`.ng cong ellipse m` c´c truc cua n´ song
`a o ¯˜ a . a
. a e¯ o a a . ˙ o’
song v´.i c´c truc toa d o cua mˇt phˇng. Phˆn n`y xˆy du.ng thuˆt to´n, du.a trˆn phu.o.ng
o a . . ¯ˆ ˙. ’ a
. ˙

a `
a a a . a. a . e
ph´p d iˆ’m gi˜
a ¯e ˙ u.a cua Van Aken, dˆ’ v˜ c´c d u.`.ng cong conic tˆ’ng qu´t bao gˆm c´c ellipse,
˙
’ ˙
¯e e a ¯ o o˙ a `
o a
hyperbol v` parabol. Thuˆt to´n n`y du.a trˆn thuˆt to´n v˜ d u.`.ng cong cua Pitteway [16]
a a
. a a . e a
. a e¯ o ˙

d u.a ra nˇm 1967, hai nˇm sau khi Bresenham cˆng bˆ thuˆt to´n v˜ d u.`.ng thˇng [4].
¯ a a o ´
o a
. a e ¯ o ˙

a

a
. a a ` a
a e -a ˙
Thuˆt to´n conic chia l`m hai phˆn t´ch biˆt: Dˇc ta conic c´ dang tˆ’ng qu´t
. . ’ o . o˙ a

f (x, y) := Ax2 + Bxy + Cy 2 + Dx + Ey + F = 0.

v´.i A, B, C, E, F l` c´c hˆ sˆ thu.c. Phu.o.ng ph´p x´c d inh conic bˇ ng phu.o.ng tr` f (x, y) =
o . ´
a a e o . a a ¯. `
a ınh
o ınh ınh . a ¯´ e ˙ a o a

0 kh´ h` dung h` hoc v` do d o ta s˜ khao s´t mˆt c´ch kh´c. Ch´ng ta s˜ chı tr` b`y
. a u e ˙ ınh a

vˆ ellipse, nhu.ng nh˜.ng l´ luˆn tu.o.ng tu. c´ thˆ’ ´p dung cho l´.p c´c d u.`.ng cong hyperbol
`
e u y a . . o ea ˙ . o a ¯ o
v` parabol.
a

Du.`.ng tr`n tˆm O(0, 0) b´n k´ d o.n vi:
- o o a a ınh ¯ .

x2 + y 2 = 1

`
nˇ m trong h` vuˆng V.
a ınh o


34
X´t ph´p biˆn d o’i affine T trˆn mˇt phˇng R2 . Khi d o ´nh xa T biˆn d o’i h` vuˆng
e e ´
e ¯ˆ ˙ e a
. ˙

a ¯´ a . ´ ˙
e ¯ˆ ınh o
V th`nh h` b` h`nh v` d u o
a ınh ınh a a ¯ .`.ng tr`n biˆn d o’i th`nh ellipse (H` 1.10). C´c d iˆ’m gi˜.a
o ´
e ¯ˆ ˙ a ınh a ¯e ˙ u
P, Q cua c´c canh cua h` b` h`nh nˇ m trˆn ellipse. C´c d iˆ’m P, Q v` tˆm J cua h`
˙ a .
’ ˙ ınh ınh a
’ `
a e a ¯e ˙ a a ˙ ınh

ınh a a ¯i ´ o ınh ınh a
a . a ¯´ a ¯. ´
b` h`nh x´c d .nh duy nhˆ t mˆt h` b` h`nh v` do d o x´c d inh duy nhˆ t ellipse. Nhˆn
a a
.
e ` ´ ˙ .`.ng ho.p tˆm ellipse l` gˆc toa d ˆ th` ch´ng
x´t rˇ ng nˆu c´ thˆ’ x´c d .nh c´c hˆ sˆ trong tru o
a e o e a ¯i a e o. ´ . a ´
a o . ¯o ı u
.
ta c˜ng c´ thˆ
u o e ˙ xu. l´ trong tru.`.ng ho.p tˆ’ng qu´t. Ta chı cˆn ´p dung ph´p tinh tiˆn dˆn
’ ˙ y
’ o . o ˙ a ˙ ` a
’ a . e . ´ ´
e ¯e
tˆm J. (D˜ nhiˆn, d iˆu n`y chı d ung khi J c´ c´c toa d o nguyˆn). V` vˆy c´ thˆ’ gia thiˆt J
a ı e ¯` e a ˙ ¯´
’ o a . ¯ˆ . e ı a o e ˙
. ˙ ’ ´
e
l` gˆc toa d ˆ v` P, Q l` nh˜.ng d iˆ’m d ˜ d u.o.c biˆn d ˆ’i tu.o.ng u.ng. Ch´ng ta gia thiˆt rˇ ng
´
a o . ¯o a . a u ˙
¯ e ¯a ¯ . ´
e ¯o ˙ ´ u ˙
’ e `
´ a
cung (ngˇn) cua ellipse d .nh hu.´.ng ngu.o.c chiˆu kim d` ng hˆ (quanh tˆm J) t`. P dˆn Q;
´
a ˙
’ ¯i o . `
e ¯ˆ
o `
o a u ´
¯e
ngu.o.c lai, ho´n d o’i P v` Q.
. . a ¯ˆ˙ a

Dˆ’ x´c d inh phu.o.ng tr` ellipse ta cˆn t` ph´p biˆn d o’i affine trong R2 c´c d iˆ’m
- e a ¯.
˙ ınh ` ım e
a ´
e ¯ˆ ˙ a ¯e ˙
1 0 xP xQ
v`
a tu.o.ng u.ng lˆn P =
´ e v` Q =
a . Ph´p biˆn d o’i T trong tru.`.ng
e ´
e ¯ˆ ˙ o
0 1 yP yQ
ho.p n`y x´c d .nh bo.i:
. a a ¯i ˙

x xP xQ x
→ .
y yP yQ y
Ph´p biˆn d o’i T biˆn d o’i c´c d iˆ’m trˆn d u.`.ng tr`n:
e ´
e ¯ˆ ˙ ´ ˙
e ¯ˆ a ¯ e ˙ e ¯ o o
1 0
cos(α) + sin(α),
0 1

v´.i α ∈ [0, 1], th`nh c´c d iˆ’m trˆn ellipse:
o a a ¯e ˙ e
x xP xQ
= cos(α) + sin(α).
y yP yQ

Ch´ y rˇ ng cos2 (α) + sin2 (α) = 1. Suy ra c´c hˆ sˆ cua phu.o.ng tr` x´c d inh ellipse l`
u´ ` a . ´ ’
a e o ˙ ınh a ¯. a
2 2
A = yP + yQ , B = −2(xP yP + xQ yQ ), C = x2 + x2 ,
P Q
D = 0, E = 0, F = −(xP yQ − yP xQ )2 .

−→
Bˆy gi`. tinh tiˆn ellipse theo vector P J, ta d u.o.c ellipse m´.i c´ tˆm tai −P, t´.c l`
a o . ´
e ¯ . o o a . u a
thay x = x + xP , y = y + yP v`o phu
a .o.ng tr` ellipse ta d u.o.c phu.o.ng tr` x´c d inh ellipse
ınh ¯ . ınh a ¯.
m´.i
o

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 y 2 + D x + E y + F = 0,

trong d ´
¯o

A = A, B = B, C = C,
D = 2yQ (xP yQ − yP xQ ), E = −2xQ (xP yQ − yP xQ ), F = 0.

35
...
... .
. ...
.
...
... .
. ...
...
...
... .
.
. ...
...
...
... .
. ...
..
...
... .
.
. .....
... .
...
... .
. .. .
.
...
... ..
.. .
. . ...
... .
.
.. . ..
... ...
... .
...
...
...
...
...
...
...
.....
.
...
.
.
.
.
.
.
.
.
.
..
..
...
..
..
..
...
...
...
...
.
.
.
.
.
.
.
.
4 ...
.
...
...
.
...
... .
.. .
. .
..
...
... ....
........................
.................... ...
... .....
...
...
...
...
.
..
..
.
.
.
.
.
. .
.
..
.
...
...
...
... 5 .....
.....
..
.. ......
...... ... ....
...
...
.
...
...
...
...
...
...
..
.
..
..
.
.
.
.
.
.
.
.
.
..
...
.
.

...
...
...
...
...
...
...
...
....
....
....
....
...
.. ..
3
..
..
.
.
. ............
.....
.....
....
. ...
... .
. ..
.. ...
... .............
..
...
... ...
...
....
.... ....
.... ....
.... ....
...
...
...
...
...
...3 2
...
... . ....
.
.
.
.
.
.
.
...
...
..
...
...
.....
.....
..... .
..... .
.....
......
..
. ...
...
...
... ...
.
...
.
...
...
.
..
.
.
.
.
.
.
... . .....
..... ... ....
... .. ..
..
4 ... . ....
... . ...
.. .
.
. ..
... . ... 1
.....................................................................................................
.. .
...
....
......................................................................................................
... ....
... ...
..
..
..
. ..
..
..
.
.
.... ..
.. .... ..
.. ...
..
.. 5 . ... . .....
... . .....
.
... . ...
... . ...
.
8 6 ..
.
..
..
..
...
...
...
.
..
2
.....
..... ...
... .
.
. ...
... ....
.... ....
.... .
.. ...
...
..........
.. ...
.. . ... . ...
...
. ....
.. ..
.. .
.....
.....
. ...
...
...
...
..
..
6 7 .
.
.
.
.
.
.
.
...
...
...
...
...
...
...
....
.... .... .
.... .
.....
....
...
. .............
............. .
.
.
.
.
.
.
.

...
...
..
....
...
... ...
... ....
...
... ...
...
....
... .. .
.
. .
.. ...
... .
.
. ....
....
...
...
....
... ... .
.
. .
.. ...
... ..
..
..
. ....
.... ..
...
...
..
..
...
...
...
.
.
.
.
.
.
.
. .
.
.
.
.
.
.
.
.
..
..
..
..
...
...
...
...
...
...
7 ..
...
.......
.....
..
... . ...................
... ................... ..
... ......
......
..
.. .....
.....
... . . .

...
...
. ...
...
...
...
..
..
.
..
..
...
.
.
.. .
.
.
.
.
.
.
.
.
.
.
...
..
..
..
...
..
.
...
...
...
...
...
...
...
... ...
...
...
...
...
..
8
.
.
.
.
.
.
.
.
.
1
. .
....
... .
.
. ...
... .
.
.
. ...
...
.
.
. ...
...
...
.
....
...
.
.
. ...
...
...
....
...
.
.
. ...
...
....
... .
.
. ..
.



(a) (b)

Cung Di chuyˆ’n b`n c`.
˙
e a o Di chuyˆ’n ch´o
e˙ e
∆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` 1.11: (a) T´m cung v˜. (b) Ellipse v´.i ph´p phˆn hoach. (c) Hu.´.ng di chuyˆ’n tu.o.ng
ınh a e o e a . o e˙
u.ng.
´




36
Nhˆn x´t rˇ ng gˆc toa d ˆ nˇ m trˆn ellipse m´.i c´ tˆm tai −P, v` nˆu ta v˜ d u.o.c
a e a
. ` o . ¯o `
´ . a e o o a . a e ´ e ¯ .
.i n`y th` s˜ v˜ d u.o.c ellipse ban d` u. V` A, B, C khˆng thay d ˆ’i qua ph´p tinh
ellipse m´ a
o ı e e ¯ . ¯a
ˆ ı o ¯o ˙ e .
tiˆn, nˆn dˆ’ gian tiˆn, ta s˜ k´ hiˆu D v` C thay cho D , C (trong d o D v` E ban d` u bˇ ng
´
e e ¯e ˙ ˙ ’ e
. e ı e . a ¯´ a ¯a `
ˆ a
0).

´ ´
Tiˆn tr` tiˆp theo l` v˜ ellipse. Ch´ng ta chia th`nh t´m cung v˜. C´c cung v˜ cho
e ınh e a e u a a e a e
biˆt hu.´.ng di chuyˆ’n trong thuˆt to´n. Trong cung th´. nhˆ t ta di chuyˆ’n sang phai v` di
´
e o e˙ a
. a u a ´ e˙ ˙ a

chuyˆ’n ch´o lˆn. C´ hai c´ch di chuyˆ’n, goi l` di chuyˆ’n b`n c`. hoˇc di chuyˆ’n ch´o, phu
e˙ e e o a e˙ . a ˙
e a o a . e˙ e .
thuˆc v`o mˆt hoˇc ca
o a
. o. a
. ˙ hai toa d o thay d o’i. H` 1.11 minh hoa t´m cung v˜, c´c cung
’ . ¯ˆ . ¯ˆ˙ ınh . a e a
tu.o.ng u.ng mˆt ellipse v` bang chı ra hu.´.ng di chuyˆ’n trong mˆ i tru.`.ng ho.p.
´ o a ˙’ ˙
’ o e˙ ˜
o o
. .

Thuˆt to´n du.´.i d ay chia l`m hai bu.´.c lˇp kh´c nhau - mˆt lˆn theo c´c cung d ´nh
a
. a o ¯ˆ a o a . a o `
. a a ¯a
´ ’ ´
o ˙ e u ¯ . ¯e´ e e a o ¯o o ´
sˆ le, kˆt th´c khi d at dˆn biˆn cung ch´o v` mˆt d ˆi v´ a.i c´c cung chˇn, kˆt th´c khi d at
˜
a ´
e u ¯.
.
dˆn biˆn b`n c`.. Dˆ’ x´c d .nh c´c cung kho.i d` u, ta nhˆn x´t rˇ ng vector gradient
¯e´ e a o - e a ¯i˙ a ˙ ¯a
’ ˆ a e `
. a
∂f
∂x
2Ax + By + D
f (x, y) := ∂f =
∂y
Bx + 2Cy + E
vuˆng g´c v´.i tiˆp tuyˆn cua conic tai d iˆ’m d u.o.c t´
o o o e ´ ´
e ˙
’ ˙ ˙. .

. ¯ e ¯ . ınh. Ch´ng ta su dung c´c toa d o
u a . ¯ˆ .

cu ∂f ∂f t
¯e˙ a ¯i .´.ng di chuyˆ’n (bˇ ng c´ch quay 900 ngu.o.c
˙ a vector f (x, y) = ( ∂x , ∂y ) dˆ’ x´c d .nh hu o e˙ `
a a .
chiˆu kim d` ng hˆ) v` do d o hu o
`
e ¯o
ˆ ` a
o ¯´ .´.ng di chuyˆ’n cua cung v˜. V` d iˆ’m bˇt d` u l` (0, 0) nˆn
e˙ ˙ ’ e ı ¯e˙ ´ a
a ¯ˆ a e
˙ .
’ `
a a . a a´
f (0, 0) = (D, E). Thu tuc GetOctant() nhˇ m phˆn loai c´c cung xuˆ t ph´t theo vector
a
n`y.
a


char GetOctant(int D, int E)
{
if ((D > 0) && (E < 0))
if (D < -E) return 1;
else return 2;
if ...
}


Dˆ’ ´p dung thuˆt to´n d iˆ’m gi˜.a, v´.i mˆ i cung cˆn x´c d inh gi´ tri cua biˆn quyˆt
-ea
˙ . a
. a ¯e ˙ u o ˜
o `a a ¯. a . ˙ ’ ´
e ´
e
d .nh d v` phu.o.ng ph´p cˆp nhˆt n´. Khi di chuyˆ’n theo d u.`.ng ch´o ta s˜ cˆp nhˆt d bˇ ng
¯i a a a . a o
. e˙ ¯ o e e a . a
. `
a
mˆt biˆn v; khi di chuyˆ’n theo b`n c`
o ´
e e ˙ a o ., ta s˜ tˇng n´ bo.i biˆn u. Nˆu f (x, y) l` phu.o.ng
e a o ˙ ’ ´
e ´
e a
.
tr` ellipse th` d l` gi´ tri cua h`m f tai d iˆ’m gi˜.a cua d oan nˆi hai pixel c´ thˆ’ d u.o.c
ınh ı a a . ˙ ’ a . ¯e ˙ u ˙ ¯ .
’ ´
o ˙
o e ¯ .
.´.c kˆ tiˆp.
chon trong bu o e e ´ ´
.

V` f (x, y) < 0 tu.o.ng u.ng bˆn trong ellipse v` f (x, y) > 0 tu.o.ng u.ng bˆn ngo`i ellipse
ı ´ e a ´ e a
nˆn d < 0 khi ellipse d i ph´ ngo`i d iˆ’m gi˜ a
e ¯ ıa a ¯e ˙ u .a v` do d o ta chon d iˆ’m ngo`i; ngu.o.c lai khi
¯´ ˙
. ¯e a . .

37
d > 0 ta chon d iˆ’m trong; v´.i d = 0, chon mˆt trong hai. C´ thˆ’ chon theo c´ch cua Van
. ¯e ˙ o . o
. o e .˙ a ˙

´
Aken: d ˆi v´ a
¯o o .i c´c cung d ´nh sˆ le ta s˜ di chuyˆ’n b`n c`. khi d < 0 v` di chuyˆ’n ch´o nˆu
¯a ´ ’
o ˙ e ˙
e a o a e˙ e e ´
ngu.o.c lai. V´.i c´c cung d ´nh sˆ chˇn, ta di chuyˆ’n ch´o khi d < 0 v` b`n c`. nˆu ngu.o.c lai.
. . o a ¯a ´ ˜
o a e ˙ e a a o e ´ . .

Trong cung th´. nhˆ t, gia su. o. bu.´.c th´. i ta chon d u.o.c pixel tˆt nhˆ t C := (xi , yi ).
u ´
a ˙ ˙ ˙
’ ’ ’ o u . ¯ . ´
o ´
a
K´ hiˆu di l` gi´ tri quyˆt d .nh chon gi˜.a R := (xi + 1, yi ) v` D := (xi + 1, yi + 1). K´ hiˆu
y e . a a . ´
e ¯i . u a y e .
a a ¯. .o.ng cˆng v`o d dˆ’ tao d . Khi d o ch´ng ta cˆn thu.c hiˆn v´.i
ui+1 v` vi+1 l` c´c d ai lu .
a o a i ¯e ˙ . i+1 ¯´ u `
a e o
. . .
˜
mˆi pixel l`
o a

-a ¯e
1. Dˇt d iˆ’m v˜ tai pixel (xi , yi );
. ˙ e .

2. Chon pixel kˆ tiˆp (xi+1 , yi+1 ) du.a trˆn di ;
. ´ ´
e e . e

3. Cˆp nhˆt ui+1 v` vi+1 t`. ui , vi trˆn co. so. chon lu.a o. Bu.´.c 2;
a
. a
. a u e ˙
’ . . ˙ ’ o

4. Cˆp nhˆt di+1 t`. di du.a trˆn ui+1 hoˇc vi+1 ;
a
. a
. u . e a
.

5. Kiˆ’m tra thay d o’i cung v˜.
e˙ ¯ˆ ˙ e


Nhˇc lai l` di+1 c´ thˆ’ d u.o.c t´ t`. di bˇ ng k˜ thuˆt sai phˆn. Gia thiˆt l` d ang o. cung
´
a . a ˙
o e ¯ . ınh u `
a y a. a ˙’ ´
e a ¯ ˙

v˜ d` u tiˆn, d iˆ’m v˜ tˆt nhˆ t l` (xi , yi ) v` ta c´ biˆn quyˆt d .nh di = f (xi + 1, yi + 1 ) dˆ’
e ¯ˆa e ¯e ˙ e o ´ ´
a a a o e ´ ´
e ¯i 2
¯e˙
chon pixel kˆ tiˆp. Nˆu di di chuyˆ’n theo b`n c`. th` xi+1 = xi + 1 v` yi+1 = yi . Do d ´ biˆn
. ´ ´
e e ´
e e˙ a o ı a ¯o e ´
´ .i d = f (x + 2, y + 1 ).Suy ra
quyˆt d .nh m´ i+1
e ¯i o i i 2

ui+1 = di+1 − di
1 1
= A(xi + 2)2 + B(xi + 2)(yi + ) + C(yi + )2
2 2
1
+D(xi + 2) + E(yi + ) + F
2
1 1
−A(xi + 1) + B(xi + 1)(yi + ) + C(yi + )2
2
2 2
1
+D(xi + 1) + E(yi + ) + F
2
1
= A[2(xi + 1) + 1] + B(yi + ) + D
2
1
= A(2xi + 1) + B(yi + ) + D + 2A.
2
a a ´
e e .´.ng ch´o th` d = f (x + 2, y + 3 ) v` bu.´.c tˇng l`
Mˇt kh´c, nˆu di chuyˆ’n theo hu o
˙ e ı i a o a a
. i i 2

vi+1 = di+1 − di
B
= (2A + B)xi+1 + (B + 2C)yi+1 + A + +D+E
2
B
= (2A + B)xi + (B + 2C)yi + A + + D + E + [2A + 2B + 2C].
2

38
´ .
Nˆu d at
e ¯ˇ
1
ui = A(2xi + 1) + B(yi + ) + D
2
th` v´.i viˆc di chuyˆ’n b`n c`. ta c´ ui+1 = ui + 2A. Tu.o.ng tu., nˆu d ˇt
ı o e . ˙
e a o o ´ .
. e ¯a
B
vi = (2A + B)xi + (B + 2C)yi + A + +D+E
2
th` khi di chuyˆ’n ch´o ta c´ vi+1 = vi + (2A + 2B + 2C).
ı e˙ e o

Dˆ’ lu.u gi˜. nh˜.ng gi´ tri ui v` vi d ˆi v´.i hai c´ch di chuyˆ’n b`n c`. v` ch´o, ta cˆn
-e ˙ u u a . a ´
¯o o a ˙
e a o a e `
a
cˆp nhˆt nh˜.ng gi´ tri n`y kˆ’ ca khi ch´ng khˆng d u.o.c su. dung. Do d ´,
a
. a
. u a . a e ˙ ˙ ’ u o ¯ . ˙ . ’ ¯o


• v´.i di chuyˆ’n b`n c`.
o ˙
e a o

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 oi v´.i di chuyˆ’n ch´o,
´
¯ˆ o e˙ e
ui+1 = ui + 2A + B.


-a. ¯´ o ˙ . a

Dˇt k1 := 2A, k2 := 2A + B, v` k3 := 2A + 2B + 2C. Khi d o ta c´ thu tuc cˆp nhˆt
a . a
.
a ´
c´c biˆn u v` v nhu
e a . sau:


• Di chuyˆ’n b`n c`.
˙
e a o
ui+1 = ui + k1 , vi+1 = vi + k2 .

• Di chuyˆ’n ch´o
e˙ e
ui+1 = ui + k2 , vi+1 = vi + k3 .


Bˆy gi`. khao s´t viˆc thay d ˆ’i cung v˜. Nhˆn x´t rˇ ng ch´ng ta kˆt th´c v˜ cung (E 1 )
a o ˙ a e
’ . ¯o˙ e a e `
. a u ´
e u e
1
khi vector gradient f (x, y) ty lˆ v´.i vector
˙ e o
’ . o a a u ´
. N´i c´ch kh´c, ch´ng ta kˆt th´c v˜
e u e
−1
cung (E 1 ) khi tˆ’ng cua hai th`nh phˆn cua vector f (x, y) bˇ ng khˆng (H` 1.12).
o˙ ˙
’ a `a ˙ ’ `
a o ınh

Mˇt kh´c, dˆ d`ng kiˆ’m tra rˇ ng
a
. a ˜ a
e e˙ `
a

∂f k2 ∂f ∂f k2
= ui − , + = vi − .
∂x 2 ∂y ∂y 2

39
................
.......
...........
.....
.....
...
...
.. ..... ..
.... ..
..
....
.... .
.....
... .
.
.
.
. ...
... ..
.
...
...
.
.
.
....
...
.
..............
. ............
.
. ...
...
.
.
.
...
... .
.
.
. ...
... .
..
..
.. ..
.
..
.. ..
.
..
.. ..
..
..
..
.
..
..
..
..
.. 2
..
.
. ..
.
.
. ..
..
.
..
. ...
...
.. ..
..
.
.
. ...
...
.
. ......
... ..
.
.
. ... .....
... .....
.
.
. . ...
... ...
...
.
. ...
... ...
..
.
.. ...
...
... ...
...
....
Vector n`y nˇ m trˆn d u.`.ng thˇng c´ hˆ sˆ g´c -1
.. ....
...
...
....
......................
...............
.
.
.
.
.
....
....
..
..
1 a a ` e ¯ o ˙

a . ´
o e o o
.
.
.
.
.
.
.
.
.




H` 1.12: Trong cung th´. nhˆ t, tˆ’ng c´c th`nh phˆn cua vector gradient ˆm. Khi d i v`o
ınh u a o ´ ˙ a a `
a ˙
’ a ¯ a
cung th´
u. hai, tˆ’ng n`y d o’i dˆ u.
o˙ a ¯ˆ a˙ ´

Do d o, dˆ u cua biˆ’u th´.c vi − k22 cho biˆt d a kˆt th´c v˜ cung (E 1 ) hay chu.a. Tu.o.ng
¯´ a ´ ˙ ’ e˙ u ´
e ¯˜ e ´ u e
tu., kˆt th´c v˜ cung (E 2 ) x´c d .nh bo.i dˆ u ui − k22 .
. e ´ u e a ¯i ’ ´
˙ a

Kˆ tiˆp ch´ng ta cˆn x´c d .nh c´c biˆn quyˆt d inh di v` ui , vi cua cung th´. hai khi
´ ´
e e u `
a a ¯i a ´
e ´
e ¯. a ˙
’ u
ta kˆt th´c cung th´. nhˆ t; ch´ng vˆ n tu.o.ng u.ng v´.i c´c biˆn tˇng d oi v´.i di chuyˆ’n ch´o
´
e u u a ´ u a˜ ´ o a ´
e a ¯ˆ o ´ e˙ e
v` b`n c`
a a o .. Nhu.ng c´c di chuyˆ’n b`n c`. bˆy gi`. l` d u.ng thay v` ngang v` d d u.o.c x´c d inh
a ˙
e a o a o a ¯´ ı a i ¯ . a ¯.
bo.i f (x + 1 , y + 1) thay cho f (x + 1, y + 1 ).
˙
’ i 2 i i i 2


K´ hiˆu di , ui , vi trong v`ng th´. hai thay cho di , ui , vi (v´.i c`ng y ngh˜
y e . u u o u ´ ˜ a
ıa). Dˆ d`ng
e
kiˆ’m tra rˇ ng
e˙ `
a
1 1
di − di = f (xi + , yi + 1) − f (xi + 1, yi + )
2 2
vi 3 1
= − ui + k3 − k2 ,
2 8 2
B
vi − vi = (2A + B)xi + (B + 2C)yi + + C + D + E
2
B
−(2A + B)xi (B + 2C)yi + A + + D + E
2
= −A + C,
k2 k3
ui − ui = v i − ui − + .
2 2
Ho.n n˜.a,
u

k3 = k3 , k 2 = k3 − k2 , k1 = k1 − 2k2 + k3 .

Nhu. vˆy ch´ng ta d a c´ c´c d iˆu cˆn thiˆt dˆ’ v˜ ellipse, ´ nhˆ t l` hai cung. Ch´ng ta bao
a. u ¯˜ o a ¯ ` ` e a ´ ˙
e ¯e e ´
ıt a a u
h`m hˆ sˆ F (th`nh phˆn hˇ ng trong phu.o.ng tr` x´c d inh conic) trong d oan m˜ mˇc d`
a . ´
e o a a `
` a ınh a ¯. ¯ . a a u.
d ang gia
¯ . n´ bˇ ng 0; v´.i conic tˆ’ng qu´t, tˆm c´ thˆ’ c´ toa d ˆ khˆng nguyˆn v` do d ´
˙ su o `
’ ˙’ a o o˙ a a o e ˙ o . ¯o o e a ¯o
.
d iˆ’m bˇt d` u (dˆ’ v˜) c´ thˆ’ khˆng nˇ m trˆn ellipse (trong tru o
¯e ˙ ´ ˆ ˙
a ¯a ¯e e o e o ˙ `
a e .`.ng ho.p n`y F c´ thˆ’ kh´c
a o e a˙
.
0).


40
Sau d oan m˜ minh hoa thuˆt to´n trong chu.o.ng tr` Conic.cpp l` thu tuc Conjugate()
¯ . a . a a
. ınh a ˙ . ’
` . c´c d iˆ’m liˆn ho.p P v`
˙
. ´ ’
a e o ˙ . a ´
nhˇ m x´c d inh c´c hˆ sˆ cua mˆt ellipse (tˆm tai gˆc toa d ˆ) t` a ¯ e
a a ¯. o . o . ¯o u . e . a
ınh ınh a o a ¯˙’
Q : H` b` h`nh c´ c´c d ınh l` P + Q, P − Q, −P − Q v` −P + Q bao quanh ellipse v`
a a a
ellipse tiˆp x´c v´.i c´c canh cua h` b` h`nh.
´
e u o a . ˙ ınh ınh a


- . a e ´ u ¯ e ´ ´
o u -e e
Doan m˜ kˆt th´c khi d i hˆt cung cuˆi c`ng. Dˆ’ v˜ ellipse kh´p k´ cˆn dˆm sˆ c´c
˙ e ın, ` ¯e
a ´ o a
´
bu.´.c di chuyˆ’n cˆn thiˆt dˆ’ d at t´.i pixel xuˆ t ph´t (b`i tˆp).
o ˙ a
e ` ´ ˙
e ¯e ¯ . o ´
a a a a.


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)
{
if (octant % 2)
{
while (v 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);
}
}


Diˆu d ´ng ngac nhiˆn l` d oan m˜ cˆp nhˆt c´c gi´ tri trong hai cung v˜ d` u tiˆn c˜ng thu.c
- ` ¯a
e . e a¯ . a a . a a a .
. e ¯a e u
ˆ .
.i c´c cung v˜ c`n lai. Cuˆi c`ng, nhu. trong H` 1.13, d oi khi mˆt bu.´.c di
hiˆn d ung v´ a
e ¯´ o e o . ´
o u ınh ¯ˆ o o
. .
chuyˆ’n ch´o trong thuˆt to´n bˇng qua ph´ bˆn kia cua ellipse; ngh˜ l` n´ thay d o’i nhiˆu
e˙ e a
. a a ıa e ˙’ ıa a o ¯ˆ˙ `
e
cung v˜ tai mˆt th`.i d iˆ’m. Khi d iˆu n`y xay ra, thuˆt to´n tao ra mˆt d˜y c´c pixel ra khoi
e . o . o ¯e ˙ ¯` e a ˙ ’ a
. a . o a a
. ˙’
˙
’ `
a e a ¯ˆ a o . ˙
’ .o.c lˆ y
qu˜ d ao cua ellipse. Nhˆn x´t rˇ ng d ay l` mˆt dang cua aliasing-t´ hiˆu f (x, y) d u . a
y ¯. ınh e ¯ ´
. . .
mˆu ch´.a c´c tˆn sˆ rˆ t cao chuyˆ’n th`nh c´c d iˆ’m nguyˆn.
˜
a u a ` o a
a ´ ´ e˙ a a ¯e ˙ e

Pratt d` xuˆ t mˆt phu.o.ng ´n gi´i quyˆt nhu. sau [18]. Trong khi thuˆt to´n di chuyˆ’n
e ´ o
¯ˆ a . a a e´ a
. a e˙
trong cung v˜ th´. nhˆ t, viˆc bˇng ch´o qua ellipse s˜ tu.o.ng u.ng su. thay d o’i nhanh hu.´.ng
e u a ´ e a
. e e ´ . ¯ˆ ˙ o
˙

cua vector gradient. Thˆt vˆy, trong cung v˜ th´
a a . nhˆ t vector gradient luˆn luˆn c´ th`nh
e u a ´ o o o a
. .
phˆn theo y ˆm v` th`nh phˆn theo x du.o.ng. Sau khi bˇng qua ellipse, ta s˜ dˆn mˆt d iˆ’m
`
a a a a `
a a e ¯e ´ o ¯e
. ˙
trong cung v˜ 3, 4, 5 hoˇc 6. Ch´ng ta x´c d inh d u.`.ng thˇng phˆn c´ch gi˜.a c´c cung
e a
. u a ¯. ¯ o a˙
’ a a u a
e a `
a a a `
a ˙

v˜ n`y v` c´c cung v˜ 7, 8, 1 v` 2 bˇ ng c´ch cho th`nh phˆn x cua vector gradient bˇ ng
e a a a `
a
khˆng-t´ a
o u .c l` 2Ax + By + D = 0. V` u = 2Ax + By + D + A + B/2 nˆn c´ thˆ’ su. dung
ı i e o e ˙ .˙ ’
i i

biˆn ui dˆ’ x´c d .nh hiˆn tu.o.ng bˇng ch´o xay ra. L´ luˆn tu.o.ng tu. v´.i c´c cung v˜ kh´c.
´
e ˙
¯e a ¯i e
. . a e ˙ ’ y a . . o a e a
-e o e
Dˆ’ c´ thˆm thˆng tin vˆ c´c thuˆt to´n v˜ conic, xem Pitt1, [18], [6].
˙ o ` a
e a. a e
.
.
. .
.
. .
.
. .
.
. .
.
. .
.
. .
.
. .
.
. .
.
. .
.
.
.
. .
. .
. .
. .
. .
. .
. .
. .
. .
.
..........................................................................................
...........................................................................................
.
. .
. .
. .
. .
. .
. .
. .
. .
. .
.
.
. .
. .
. .
. .
. .
. .
. .
. .
. .
.
.
. .
. .
. .
. .
. .
. .
. .
. .
. .
.
. . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...........................................................................................
..........................................................................................
. .
.
y.
.
.
.
.
.
.
. .
. .
. .
. .
. .
. .
. .
. .
. .
.
.
. .
. .
. .
. .
. .
. .
. .
. .
. .
.
.
......
.....
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
y .
......................................................................................
. . . .
......................................................................................
. .
.
.
.
.
.
.
.
.
.
.
. .
. .
. .
. .
. .
. .
. .
. .
. .
.
. . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
y .
.
.
.
.
.
.
.
.
.
...........................................................................................
..........................................................................................
. .
.
.
.
.
.
.
.
.
. .
. .
. .
. .
. .
. .
. .
. .
. .
.
.
. .
. .
. .
. .
. .
. .
. .
. .
. .
.
.
......
.....
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
y .
.
.
.
.
.
.
.
.
.
.
.
.
......................................................................................
. . . .
......................................................................................
. .
.
.
.
.
.
.
.
.
.
.
. .
. .
. .
. .
. .
. .
. .
. .
. .
.
. . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
y .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. . .
.
.
.
.
...........................................................................................
..........................................................................................
.
.
.
.
.
.
.
. . . . . . ................. .
.... .. ... .
.
.
. .
.
. .
.
. .
.
. ................... ....... . ...... .
. .
. ..... .........
.
.
. .
. .... . .
.
.
.
.
...............
.....
.
.
.
.
. ........
.
.
.
............
.
.
.
.
y . . .
. ................................................................................
................ .
.
.
.
. .............
. .
.
.
..........
.
..
.
.
.
.
.
.
.
...........................................................................................
. . .....
.... .. .
. .
.
.
.
. ....... . .
. .
.......... ..
. .
. . .
............... ....
. ...... ..... .
. . .
.
. .
.
. .
.
. .
.
.
............................. ..
.... ......... ............
.. ..... ..
. .
. .
. .
. .
. .
. .
. .
.
y y y y
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...........................................................................................
..........................................................................................
.
.
.
.
.
.
.
.
.
.
. .
. .
. .
. .
. .
. .
. .
. .
. .
.




H` 1.13: Thuˆt to´n sai trong tru.`.ng ho.p ellipse hep.
ınh a
. a o . .

Wu v` Rokne [28] xˆy du.ng mˆt phu.o.ng ph´p kh´c v˜ conic ph` ho.p v´.i thiˆt bi hiˆ’n
a a . o
. a a e u . o ´
e . e ˙


45
thi c´c m´.c x´m. Thay cho viˆc tˇng mˆt pixel tai mˆt th`.i d iˆ’m, thuˆt to´n tˇng mˆt
. a u a e a
. o
. . o. o ¯e ˙ a
. a a o
.
´i c´c pixel. Gia su u
khˆ a
o ˙ ˙
’ ’ . ch´ng ta di chuyˆ’n theo chiˆu ngang v` d o cong lˆi lˆn. Nˆu ch´ng
e˙ `
e a ¯ˆ ` e
o ´
e u
.
a .´.c lˇp ch´ng ta v˜ pixel (x + 2, y + 2) th` pixel trung gian
ta d a v˜ pixel (x, y) v` sau hai bu o a
¯˜ e u e ı
.
d u.o.c nˆi suy l` (x + 1, y + 1). Tu.o.ng tu., nˆu sau hai bu.´.c lˇp ta v˜ pixel (x + 2, y) th` pixel
¯ . o . a . e ´ o a . e ı
¯ .o.c nˆi suy l` (x + 1, y). Nˆu sau hai bu.´.c lˇp l` pixel (x + 2, y + 1) th` cˆn
trung gian d u . o a ´
e o a a ı `
a
. .
chon mˆt trong hai pixel (x + 1, y) hoˇc (x + 1, y + 1). Trˆn m`n h` gi´ tri x´m, ch´ng ta
. o. a
. e a ınh a . a u
c´ thˆ’ hiˆ’n thi ca hai pixel n`y nhu
˙ ˙ .ng v´.i cu.`.ng d ˆ s´ng mˆt nu.a. Do d o tai mˆ i bu.´.c lˇp,
˜
o e e . ˙
’ a o o ¯o a . o ˙
. ’ ¯´ . o o a .
ta v˜ hai pixel c`ng mˆt l´c v` v` vˆy gia
e u o u a ı a
. . ˙ m th`.i gian thu.c hiˆn t´ to´n. Tai chˆ nˆi cua
’ o . e ınh a
. . ˜ o ˙
o ´ ’
hai cung v˜, thuˆt to´n cˆn tr´nh viˆc v˜ chˆng lˆn nhau v` khˆng qu´ kh´ dˆ’ giai quyˆt
e a
. a ` a a e e `
. o e a o a o ¯e ˙˙ ’ ´
e
d iˆu n`y. Hiˆ’n nhiˆn thuˆt to´n chı ph` ho.p v´.i nh˜.ng thiˆt bi hiˆ’n thi gi´ tri x´m, nhu.ng
¯` e a e˙ e a
. a ˙ u .
’ o u ´
e . e ˙ . a . a
n´ minh hoa c´ thˆ’ d o
o ˙ .n gian ho´ qu´ tr` xu. l´ khi c´ thˆ’ ´p dung k˜ thuˆt antialiasing.
˙
’ a a ınh ˙ y ’ ˙
. o e ¯ o ea . y a
.




46
Chu.o.ng 2

H` hoc cu a c´c d .`.ng cong v` mˇt
ınh . ˙
’ a ¯u o a a.
cong

Muc d´ ch´ cua chu.o.ng n`y l` tr` b`y c´c phu.o.ng ph´p v˜ d u.`.ng cong Bezier v`
. ¯ıch ınh ˙ ’ a a ınh a a a e ¯ o a
-a a .`.ng cong thu.`.ng d u.o.c su. dung trong c´c phˆn mˆm d` hoa.
B-spline. Dˆy l` hai d u o
¯ o ¯ . ˙ . ’ a `
a ` ¯ˆ .
e o



2.1 Mo. d` u
˙ ¯ˆ
’ a

Chu.o.ng n`y tr` b`y phu.o.ng ph´p h` hoc nhˇ m phˆn t´ v` thiˆt kˆ c´c d u.`.ng cong
a ınh a a ınh . `
a a ıch a ´ ´
e e a ¯ o
.´.i dang c´c phu.o.ng tr` tham sˆ v` do d ´ cho ph´p dˆ d`ng v˜ n´.
v` mˇt cong du o .
a a a ınh ´
o a ¯o e ˜ a
e e o
.

Ngu.o.c v´.i c´c d u.`.ng cong v` mˇt cong du.a trˆn c´c phu.o.ng tr` to´n hoc tu.o.ng
. o a ¯ o a a . . e a ınh a .
´
d ˆi d o
¯o ¯ .n gian nhu. ellipse cho bo.i P (t) = (a cos(2πt), b sin(2πt)), c´c cˆng cu m` ch´ng ta
˙
’ ˙
’ a o a u
.
tr` b`y du o ¯ˆ
ınh a .´.i d ay cho ph´p ngu.`.i thiˆt kˆ xˆy du.ng nh˜.ng h` dang kh´c nhau du.a trˆn
e o ´ ´
e e a u ınh . a e
. .
d˜ e. liˆu cho tru.´.c v` c´ thˆ’ d iˆu khiˆ’n ch´ng mˆt c´ch dˆ d`ng thˆng qua mˆt tˆp nh˜.ng
u . o a o e ¯` ˙ e e˙ u o a ˜ a
e o o a u
. . .
d iˆ’m m` ta goi l` c´c “d iˆ’m d iˆu khiˆ’n”. Viˆc xˆy du.ng mˆt d u.`.ng cong (hay mˇt cong)
¯e ˙ a . a a ¯ e ¯` ˙ e e˙ e a
. . o ¯ o
. a.
´ o e ´
tu` y l` rˆ t kh´ nˆu khˆng biˆt tru o
y´ a a o ´
e .´.c phu.o.ng tr` x´c d inh n´. Tuy nhiˆn, v´.i c´ch tiˆp
ınh a ¯. o e o a ´
e
cˆn m´.i, ta c´ thˆ’ tao ra nh˜.ng h` dang mong muˆn bˇ ng c´ch chınh, su.a vi tr´ c´c d iˆ’m
a. o o e . ˙ u ınh . o `
´ a a ˙
’ ˙ . ı a ¯e
’ ˙
d iˆu khiˆ’n-d iˆu n`y thu
¯` e ˙
e ¯` e a .c hiˆn dˆ d`ng bˇ ng qu´ tr` tu.o.ng t´c gi˜.a ngu.`.i thiˆt kˆ v`
e ˜ a e `
a a ınh a u o ´ ´
e e a
. .
m´y t´
a ınh.

Phu.o.ng ph´p xˆy du.ng d u.`.ng cong o. d ˆy l` mˆt nhˆn tˆ co. ban trong l˜nh vu.c ´p
a a . ¯ o ˙ ¯a a o
’ . a o ´ ˙
’ a . a
. ´ ´
e e a ˜
dung m´y t´ v`o thiˆt kˆ c´c mˆu h` hoc (computer aided geometric design-CAGD) v`
a ınh a a ınh . a
.`.ng d`ng trong cˆng nghˆ chˆ tao. Chu.o.ng n`y d` cˆp mˆt sˆ phu.o.ng ph´p thiˆt kˆ
thu o u o . ´
e e . a ¯ˆ a
e . . ´
o o a ´ ´
e e


47
c´c d u.`.ng cong v` mˇt cong. C´ nhiˆu c´ch tiˆp cˆn (xem, chˇng han [1], [7], [8]), nhu.ng
a ¯ o a a . o ` a
e ´ .
e a ˙

a .
. d ay chon viˆc thiˆt kˆ su. dung c´c d u.`.ng cong Bezier v` B-spline. L´.p d u.`.ng cong n`y
˙ ¯ˆ

o e ´ e ˙ .
e ´ ’ a ¯ o a o ¯ o a
. .

rˆ t quen thuˆc trong c´c u
o a ´.ng dung CAD (computer-aided design) .
. .

Dˆ’ d o.n gian, ch´ng ta bˇt d` u v´.i c´c d u.`.ng cong phˇng P (t) = (x(t), y(t)) v` sau
-e ¯
˙ ˙
’ u ´ a
a ¯ˆ o a ¯ o ˙

a a
¯o ˙ .
’. rˆng cho nh˜.ng mˇt cong (c´c d u.`.ng cong ba chiˆu P (t) = (x(t), y(t), z(t)) dˆ d`ng
d ´ mo o u a a ¯ o `
e ˜ a
e
.
suy ra t`. d o).
u ¯´



2.2 Du.`.ng cong Bezier
- o

Ch´ng ta s˜ tr` b`y thuˆt to´n de Casteljau (xem [7]) xˆy du.ng mˆt c´ch h` hoc d u.`.ng
u e ınh a a. a a . o a
. ınh . ¯ o
cong P (t) du .a trˆn mˆt tˆp c´c d iˆ’m d iˆu khiˆ’n. Phu.o.ng ph´p n`y dˆ d`ng suy ra c´c
e o a a ¯ e ¯` ˙ e e˙ a a ˜ a e a
. . .
d u.`.ng cong Bezier-l` nh˜.ng d oi tu.o.ng co. ban trong CAGD. De Casteljau (nˇm 1959), d ˆc
¯ o a u ¯ˆ ´ . ˙
’ a ¯o.
lˆp v´
a o .i Bezier (nˇm 1962), d u.a ra phu.o.ng ph´p thiˆt kˆ mˆt d u.`.ng cong m` sau n`y goi l`
a ¯ a ´ ´ .
e e o ¯ o a a . a
.
d u.`.ng cong Bezier. Du.`.ng cong n`y l` nh˜.ng th`nh phˆn trong c´c hˆ thˆng CAD d u.o.c
¯ o - o a a u a `
a . ´
a e o ¯ .
˙
’. dung trong hai cˆng ty Citro¨n v` R´nault dˆ’ tao ra c´c h` dang bˆn ngo`i cua xe ˆ
su . o e a e ˙
¯e . a ınh . e a ˙’ o
tˆ.
o



2.2.1 Thuˆt to´n de Casteljau
a
. a

Thuˆt to´n de Casteljau su. dung mˆt d˜y c´c d iˆ’m d iˆu khiˆ’n dˆ’ xˆy du.ng v´.i mˆ i gi´ tri t
a
. a ˙ .
’ o a a ¯ e ¯`
. ˙ e ˙
e ¯e a˙ . ˜
o o a .
trong d oan [0, 1] tu.o.ng u.ng v´.i mˆt d iˆ’m P (t). Do d ´ thuˆt to´n sinh ra mˆt d˜y c´c d iˆ’m
¯ . ´ o o ¯e
. ˙ ¯o a
. a o a a ¯e
. ˙
. mˆt tˆp c´c d iˆ’m cho tru.´.c. Khi c´c d iˆ’m d iˆu khiˆ’n thay d o’i, d u.`.ng cong s˜ thay d ˆ’i
t` o a a ¯ e
u . . ˙ o ˙
a ¯ e ¯` e e˙ ˙
¯ˆ ¯ o e ¯o ˙
theo. C´ch xˆy du.ng du.a trˆn mˆt loat c´c ph´p nˆi suy tuyˆn t´ v` do d o rˆ t dˆ d`ng
a a . . e o
. . a e o . ´
e ınh a ¯´ a ˜ a
´ e
´
giao tiˆp. Ngo`i ra, phu
e a .o.ng ph´p c˜ng suy ra nhiˆu t´ chˆ t h˜.u ´ cua d u.`.ng cong.
a u ` ınh a u ıch ˙ ¯ o
e ´ ’



Parabol du.a trˆn ba d e’m
. e ¯iˆ˙


a
. ˙

a e ¯e ˙ -a
Trong mˇt phˇng R2 x´t ba d iˆ’m P0 , P1 , P2 . Dˇt
.
1
P0 (t) := (1 − t)P0 + tP1 ,
1
P1 (t) := (1 − t)P1 + tP2 ,

trong d ´ t ∈ [0, 1]. N´i c´ch kh´c, v´.i mˆ i t ∈ [0, 1], c´c d iˆ’m P0 (t) v` P1 (t) nˇ m trˆn c´c
¯o o a a o ˜
o a ¯e ˙ 1
a 1 `
a e a


d oan thˇng P0 P1 v` P1 P2 tu
¯ . a .o.ng u.ng. Lˇp lai ph´p nˆi suy tuyˆn t´ trˆn c´c d iˆ’m m´.i
´ a . e o ´
e ınh e a ¯ e ˙ o
. .

48
P1
(a) ..
....
...
.. ....
.. ........
.. ...
...
..
.. ...
...
..
..
...
...
...
..
.. ...
...
1
P0 (t) ..
..
..
.... ...
..... ....
.. .... .
... .
...
...
...
...
...
...
...
..
..
..
..
•... ..
.. ..
.. ... .....
. ... .....
..
.
. .... ... 1
..
..
..
.. 2
P0 (t)
... ...
.....
.....
.
...P1 (t)
...
...
..
..
...
...
...
...
...
P0 ...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
.
P2
P....1
(b) .
. . ..
.
.. .....
.. .....
..
.. ...
...
..
..
...
...
...
..
..
...
...
...
..
.. ...
...
..
.. ...
...
...
..
..
...
...
...
.. .. .................
.. .........................
@t = 0 • ... . ...
..........
.....
.
....
• ......
..........
....
...
...
...
...
.... .....
.
.... .....
...
...
..
. .... ...
.... ...
..
..
. ... ...
... ...
@0.3
..
.. @0.5 • ... ...
... ...
... ..
... ..
... ...
... ...
P0 ......
......
.....
.......
.....
@0.7 .
.....
....
....
...
...
..
...
...
....
....
@t = 1
...
...
...
...
...
...
...
...
.
P2
H` 2.1: Thuˆt to´n de Casteljau cho ba d iˆ’m d iˆu khiˆ’n.
ınh a
. a ˙
¯ e ¯` e e˙


P0 (t) v` P1 (t) (v´.i c`ng gi´ tri t) ta d u.o.c (H` 2.1(a))
1
a 1 o u a . ¯ . ınh

2 1 1
P0 (t) = (1 − t)P0 (t) + tP1 (t).

Qu˜ t´ cua P (t) := P0 (t) khi t thay d o’i trong d oan [0, 1] s˜ cho ta d u.`.ng cong nhu. H`
y ıch ˙
’ 2
¯ˆ ˙ ¯ . e ¯ o ınh
2.1(b).

˜ a
e ˙
’ `
Dˆ d`ng chı ra rˇ ng
a

P (t) = (1 − t)2 P0 + 2t(1 − t)P1 + t2 P2 .

Suy ra P (t) l` d u.`.ng cong parabol theo biˆn t.
a ¯ o ´
e


V´ du 2.2.1 Phu.o.ng tr` d u.`.ng cong Bezier P (t) tu.o.ng u.ng ba d iˆ’m d iˆu khiˆ’n
ı . ınh ¯ o ´ ˙
¯ e ¯` e e˙

P0 (0, 0), P1 (2, 2), P2 (6, 0)

l`
a

P (t) = (1 − t)2 P0 + 2t(1 − t)P1 + t2 P2
= (1 − t)2 (0, 0) + 2(1 − t)t(2, 2) + t2 (6, 0)
= (2t2 + 4t, −4t2 + 4t).


Tˆ’ng qu´t cho tru.`.ng ho.p sˆ d iˆ’m d iˆu khiˆ’n ≥ 3 ta c´:
o˙ a o ´ ˙
. o ¯ e ¯` e e˙ o


49
Thuˆt to´n de Casteljau cho L + 1 d e’m d ` u khiˆ’n
a
. a ˙
¯iˆ ¯iˆ e e˙


Trong mˇt phˇng R2 x´t L + 1 d iˆ’m P0 , P1 , . . . , PL . V´.i mˆi gi´ tri t cho tru.´.c, ta xˆy du.ng
a
. ˙

a e ¯e˙ ˜
o o a . o a .
.`.ng cong P L (t) nhu. sau:
theo quy nap d u o
. ¯ 0



1. [Kho.i tao] Dˇt r = 0 v` Pir (t) := Pi v´.i moi i = 0, 1, . . . , L − r.
˙ . -a
’ . a o .

2. [Kˆt th´c?] Nˆu r = L d`.ng; ngu.o.c lai d ˇt
´
e u ´
e u . . ¯a .

Pir+1 (t) = (1 − t)Pir (t) + tPi+1 (t),
r



v´.i i = 0, 1, . . . , L − r − 1.
o

3. Thay r bo.i r + 1 v` chuyˆ’n sang Bu.´.c 2.
˙
’ a e˙ o


Kˆt th´c, ta d u.o.c d u.`.ng cong Bezier P (t) := P0 (t) tu.o.ng u.ng c´c d iˆ’m, goi l` d iˆ’m d iˆu
e´ u ¯ . ¯ o L
´ a ¯e ˙ ˙
. a ¯ e ¯`
e
khiˆ’n, P0 , P1 , . . . , PL . Da gi´c tao bo.i c´c d iˆ’m d iˆu khiˆ’n goi l` d a gi´c d iˆu khiˆ’n.
e˙ - a . ˙ a ¯ e ¯`
’ ˙ e e˙ . a ¯ a ¯` e e˙

H` 2.2 minh hoa d u.`.ng cong Bezier du.a trˆn bˆn d iˆ’m d iˆu khiˆ’n v` d iˆ’m P (0.5),
ınh . ¯ o . e o ¯ e ¯`
´ ˙ e ˙
e a ¯e ˙
tu.o.ng u.ng gi´ tri t = 0.5, trˆn d u.`.ng cong u.ng v´.i t = 0.5. Hiˆ’n nhiˆn d ˆy l` d u.`.ng cong
´ a . e ¯ o ´ o e˙ e ¯a a ¯ o
¯ .c bˆc ba.
d a th´ a
u .

P2
........
........
.......
.......
.......
....... ..
..
. .....
.......
P1 ....
...
...
....... . .
.......
... ...
.......
........ .. ...
......... . ....
. ....
...
..
..
..
..
..
..
.......
..... ...
.. ...
... . .... ....
...
.
..
.
. ................... .. .... ...
..................
..
.
.
.
.
.
. ..

... ...............
.. ..............
...... .....
.
.
............
. ..
.
.
. ....
. ...
....... ... ......
.......
..... ... ...
.....
.... ..
....
.
.
.
.. . .....
.. .... ..
.... ..
... ..
.
.
.
.
.
.
. ... .....
. ... .....
...
........
P (0.5) ... ..
... ..
... .
... .
.....
....
....
.
...
... . ..
.
... ....
.. ....
..
...
..
.
.
. .. ..
..
..
.. .. ..
..
. ..
. .. ..
..
.
. ..
. ..
.
..
...

.
.
..
..
.
.
.
.
..
..
.. P3
.
.
.

P0
H` 2.2: Du.`.ng cong Bezier v´.i bˆn d iˆ’m d iˆu khiˆ’n.
ınh - o o o ¯ e ¯`
´ ˙ e e˙




V˜ d .`.ng cong Bezier bˇ ng thuˆt to´n Casteljau
e ¯u o `
a a
. a


Thu tuc sau t´ P (t) theo thuˆt to´n de Casteljau du.a trˆn mang P [] gˆm N umV ertices
˙ .
’ ınh a
. a . e ˙
’ `
o
d iˆ’m d iˆu khiˆ’n:
˙
¯ e ¯` e e˙


Point2D Casteljau(float t)


50
{
Point2D Q[MaxVertices];
int i, r;


for (i = 0; i 0 th` hˆ bˆ t phu.o.ng
e ` .
´ o ’ ´
˙ o a . ´
ı e a
tr` vˆ nghiˆm; trong tru.`.ng ho.p n`y, d oan thˇng AB giao v´.i h` ch˜. nhˆt (R) bˇ ng
ınh o e
. o . a ¯ . a˙
’ o ınh u a
. `
a
´ .o.c lai d ˇt
trˆng. Ngu . . ¯a
o .
q
t0 := max{0, max{ pi | pi > 0, i = 0, 1, 2, 3}},
i
q
t1 := min{1, min{ pi | pi < 0, i = 0, 1, 2, 3}}.
i


Khi d ´ hˆ bˆ t phu.o.ng tr` tu.o.ng d u.o.ng v´.i
. ´
¯o e a ınh ¯ o

t0 ≤ t ≤ t1 .

Diˆu n`y chı ra rˇ ng d oan thˇng AB giao v´.i h` ch˜. nhˆt (R) kh´c trˆng chı nˆu t0 < t1 ;
- `
e a ˙
’ ` ¯ .
a ˙

a o ınh u a . a o ´ ’ ´
˙ e
v` trong tru.`.ng ho.p n`y,
a o . a

AB ∩ (R) = {P (t) | t ∈ [t0 , t1 ]}.

Trˆn co. so. nh˜.ng phˆn t´ trˆn, ta c´ thuˆt to´n chi tiˆt sau:
e ˙
’ u a ıch e o a
. a ´
e


1. T´ pi , qi v´.i i = 0, 1, 2, 3.
ınh o

2. Kho.i tao i = 0 v` t0 = 0, t1 = 1.
˙ .
’ a

3. Nˆu pi = 0 v` qi > 0 kˆt luˆn AB ∩ (R) = ∅; thuˆt to´n d`.ng.
´
e a ´ a
e . a
. a u


98
4. Nˆu pi > 0 d ˇt t0 = max{t0 , pi }. Chuyˆ’n sang Bu.´.c 7.
´
e ¯a.
q
i
e˙ o

5. Nˆu pi < 0 d ˇt t1 = min{t1 , pi }. Chuyˆ’n sang Bu.´.c 7.
´
e ¯a.
q
i
e˙ o

6. Nˆu t0 > t1 kˆt luˆn AB ∩ (R) = ∅; thuˆt to´n d`.ng.
´
e ´ a
e . a
. a u

7. Nˆu i < 3 thay i = i + 1 v` lˇp lai Bu.´.c 3; ngu.o.c lai, kˆt luˆn AB ∩ (R) = CD, trong
´
e a a .
. o . . e ´ a .
do
¯´
C = A + t0 (B − A),
D = A + t1 (B − A).


. o ı . ˙
. ’
V´ du 3.3.4 H` 3.8 minh hoa mˆt v´ du cua thuˆt to´n Lang-Barsky.
ı . ınh a
. a
7
B
6 ...
...
• ..
...
...
.


...
...
...
...
...
... @t1 = 1
...
...
...
...
...
...
5 ...
...
.
...
...
...
...
...
...
...
D ...
...
.
...
...
...
...
... 2
...
4 ...
...
...
...
...
...
... @t1 = 3
...
...
(R) ....
...
...
...
...
...
...
...
...
...
3 ...
...
...
...
...
...
...
...
C ...
...
...
...
...
...
. ...
...
...
2 ...
...
...
...
...
...
...
...
... 1
...
...
...
...
.
...
... @t0 = 5
...
...
1 A • ...
...


@t0 = 0

1 2 3 4 5 6 7 8 9

o ı . ˙
. ’
H` 3.8: Mˆt v´ du cua thuˆt to´n Liang-Barsky.
ınh a
. a



V´ du 3.3.5 X´t h` ch˜. nhˆt
ı . e ınh u a .

R := {(x, y) ∈ R2 |0 ≤ x ≤ 8, 0 ≤ y ≤ 4}

v` hai d iˆ’m A(−1, −2) v` B(10, 9). Phu.o.ng tr` tham sˆ d oan thˇng AB c´ dang
a ¯e ˙ a ınh ´
o ¯ . ˙

a o .

(1 − t)A + tB.

Ta cˆn giai hˆ c´c bˆ t phu.o.ng
`
a ˙ e a a
’ . ´ tr`
ınh

0
 ≤ t ≤ 1,
0 ≤ (1 − t)(−1) + t(10) ≤ 8,


0 ≤ (1 − t)(−2) + t(9) ≤ 4.

99
Hay tu.o.ng d u.o.ng
¯ 
 0 ≤ t ≤ 1,

1 ≤ 11t ≤ 9,


2 ≤ 11t ≤ 6.
Vˆy
a
.
2 6
≤t≤ .
11 11
Suy ra giao cua d oan thˇng AB v` h` ch˜. nhˆt l` d oan thˇng nˆi hai d iˆ’m C v` D trong
˙ ¯ .
’ ˙

a a ınh u a a ¯ .
. ˙

a ´
o ¯e ˙ a

¯o
2 2
C = (1 − )A + B
11 11
9 2
= (−1, −2) + (10, 9) = (1, 0).
11 11
v`
a
6 6
D = (1 − )A + B
11 11
5 6
= (−1, −2) + (10, 9) = (5, 4).
11 11



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

3.4.1 Vi tr´ tu.o.ng d oi cu a mˆt d e’m v´.i d .`.ng thˇ ng
. ı ´ ’
¯ˆ ˙ o ¯iˆ
. ˙ o ¯u o ˙

a

Trong nhiˆu u.ng dung ta thu.`.ng quan tˆm kh´i niˆm nu.a mˇt phˇng trong v` nu.a mˇt
` ´
e . o a a e . ˙
’ a. ˙

a a ˙’ a
.
phˇ˙ ng ngo`i x´c d .nh bo.i mˆt d u.`.ng thˇng (xem Chu.o.ng 1). Kh´i niˆm n`y liˆn quan mˆt

a a a ¯i ˙
’ o ¯ o
. ˙

a a e . a e a
.
´ ´
e ¯e a ˙ ¯

thiˆt dˆn ph´p vector cua d u o .`.ng thˇng.
˙

a

Nhˇc lai l` phu.o.ng tr` tˆ’ng qu´t cua d u.`.ng thˇng l c´ dang
´
a . a ınh o˙ a ˙ ¯ o
’ ˙

a o .

ax + by + c = 0.

Hay tu.o.ng d u.o.ng
¯
ax + by = −c.
−→
N´i c´ch kh´c, l = {P ∈ R2 | OP , n = D}, trong d ´ n = (a, b)t l` ph´p vector cua d u.`.ng
o a a ¯o a a ˙ ¯ o



thˇng v` D = −c. K´ hiˆu
a y e .
−→
(l+ ) := {P ∈ R2 | OP , n > D},
−→
(l− ) := {P ∈ R2 | OP , n < D},

100
n Q
.
.
.
..
..
.
..
.
.
.
• .
...
...
.
Nu.a mˇt phˇng ngo`i (l− )
˙’ a
. ˙

a a
.
.
.
. ..
..
..
.
. .
.
.
. .
. ..
..
.
.
...
.
.
. ..
.. .
.
. .
.
.
.
. ....
...
.
.
.
.
.
. . .
.
...
...
.
.
.
.
.
. θ
. ..... ..
....... ..
.. ..
.
.
.
.
.
.
.
.
.
. .
. ...
. ... .
.
.
.
.
.. .
.
.
... .
...............................................................................................................................................
l / / / / / / / / / / / / / / / / / / / / / / /
....................................
................................... .. .
..............................................................................................................................................
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
A .
.
.
.
.
.
.
.
.
...
..
..
.
.


Nu.a mˇt phˇng trong (l+ )
˙’ a
. ˙

a

H` 3.9: Vi tr´ tu.o.ng d oi cua d iˆ’m Q v´.i d u.`.ng thˇng l.
ınh . ı ´ ’
¯ˆ ˙ ¯ e ˙ o ¯ o ˙

a

l` c´c nu.a mˇt phˇng ngo`i v` nu.a mˇt phˇng trong x´c d .nh bo.i l (xem H` 3.9).
a a ˙ ’ a
. ˙

a a a ˙ ’ a
. ˙

a a ¯i ˙
’ ınh

Vˆ n d` d at ra o. d ˆy l` v´.i mˆt d iˆ’m Q t`y y trong mˇt phˇng, h˜y x´c d .nh d iˆ’m
´ e .
a ¯ˆ ¯ˇ ˙ ¯a a o
’ o ¯e
. ˙ u ´ a. ˙

a a a ¯i ¯e˙
Q nˇ m trong nu.a mˇt phˇng n`o? Gia su. A l` d iˆ’m nˇ m trˆn d u.`.ng thˇng l. K´ hiˆu θ l`
`
a ˙
’ a. ˙

a a ˙ ˙
’ ’ a ¯e ˙ `
a e ¯ o ˙

a y e . a
−→
g´c gi˜.a vector n v` vector AQ . Dˆ d`ng thˆ y rˇ ng g´c θ nho ho.n 900 nˆu Q thuˆc nu.a
o u a ˜ a
e a `
´ a o ˙
’ ´
e o ˙
. ’
−→
˙

mˇt phˇng ngo`i v` do d ´ n, AQ > 0. Tu
a a a a ¯o .o.ng tu., g´c θ l´.n ho.n 900 nˆu Q thuˆc nu.a mˇt
´ o ˙ ’
. −→
. o o e . a.
phˇ˙ ng trong v` do d o n, AQ < 0. Cuˆi c`ng, g´c θ bˇ ng 900 nˆu Q thuˆc d u.`.ng thˇng l
a’ a ¯´ ´
o u o `
a ´
e o ¯ o
. ˙

a
−→
v` do d ´ n, AQ = 0. Vˆy
a ¯o a
.
−→
´
1. Q ∈ (l+ ) nˆu n, AQ > 0.
e
−→
´
2. Q ∈ (l− ) nˆu n, AQ < 0.
e
−→
´
3. Q ∈ l nˆu n, AQ = 0.
e


u´ `
Ch´ y rˇ ng
a
−→
n, AQ > 0
tu.o.ng d u.o.ng
¯
−→
n, OQ > D.
Do d ´ ta c´ thˆ’ viˆt lai tiˆu chuˆ’n kiˆ’m tra d iˆ’m Q thuˆc nu.a mˇt phˇng n`o nhu. sau:
¯o ˙ ´
o e e . e a˙ e˙ ¯e ˙ o ˙
. ’ a
. ˙

a a

−→
´
1. Q ∈ (l+ ) nˆu n, OQ > D.
e
−→
´
2. Q ∈ (l− ) nˆu n, OQ < D.
e
−→
´
3. Q ∈ l nˆu n, OQ = D.
e


Chˇng han, gˆc toa d o (0, 0) thuˆc nu.a mˇt phˇng ngo`i nˆu v` chı nˆu D < 0.
˙

a . ´
o . ¯ˆ . o ˙
. ’ a
. ˙

a ´
a e a ˙ e ’ ´


101
...
...
... ..
... ..
... ...
... ..
..
....
... ..
..
...
... ..
..
...
... ..
....
... ..
..
. ...
... ..
..
. ...
... ..
...
...
.
..
..
....
... ..
..
. ...
... ..
..
. ...
... ..
..
. ...
... ..
..
.
.
.
.
.
.
.
...
...
(R) ..
..
..
..
.. ......
......
......
......
......
...... B
.
. .. ......
......
.
. ..
.. ......
......
.
.
. ..
.. ........ ... ......
......
.
.
.
. ..........
....
.
. ........
.........
. ......
......
.
.
. ......
...... ..
..
.
. .........
...... ..
..
.
. ......
......
.
.
. ......
......
..
..
. ......
...... ..
.
. ......
......
..
.
...........
. ...... ..
..
. ......
...
. ..
..
...
... ...... .
...... .. ..
......
...... . ..
A ..
.. .
.
.
.
.
.
.
. . ...
...
...
...
.
.
.
.
. ....
...
.
.
. ...
...
.
. ...
..
.
.
. ...
...
.
.
. ...
...
.........................................................
. .......................................................
.




˙ ¯ .
’ ˙
’ a `
H` 3.10: Giao cua d oan thˇng v` d a gi´c lˆi.
ınh a a ¯ o



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


Nˇm 1978, Cyrus v` Beck [5] d a xˆy du.ng thuˆt to´n x´c d .nh giao cua d oan thˇng v` d a
a a ¯˜ a . a
. a a ¯i ˙ ¯ .
’ ˙

a a ¯
gi´c lˆi v` c´ thˆ’ mo. rˆng dˆ d`ng trong ba chiˆu. H` ch˜. nhˆt l` mˆt tru.`.ng ho.p d ac
a ` a o e ˙ o
o ˙ ’ . ˜ a
e `e ınh u a a o . . o . ¯ˇ .
biˆt cua d a gi´c lˆi v` do d o c´ thˆ’ ´p dung thuˆt to´n n`y. Thuˆt to´n Liang-Barsky tr`
e ˙ ¯
. ’ a ` a
o ¯´ o e a ˙ . a
. a a a. a ınh
b`y trong phˆn tru.´.c du.a trˆn c´ch tiˆp cˆn cua Cyrus v` Beck. Thuˆt to´n Cyrus-Beck
a `
a o . e a ´ .
e a ˙
’ a a
. a
.a trˆn tiˆu chuˆ’n loai bo d o.n gian bˇ ng c´ch x´t vi tr´ tu.o.ng d ˆi cua mˆt d iˆ’m v´.i mˆt
˙ ’ ` ´ ’ ˙
du. e e a . ˙ ¯’ ˙ a a e . ı ¯o ˙ o ¯e
. o o .
du o
¯ .`.ng thˇng.
˙

a

Nhˇc lai l` trong thuˆt to´n Cohen-Sutherland, d ˆi v´.i c´c d oan thˇng khˆng nˇ m
´
a . a a
. a ´
¯o o a ¯ . ˙

a o `
a
trong h` ch˜. nhˆt hoˇc bi loai bo ho`n to`n, ta cˆn t´ toa d ˆ giao d iˆ’m (x, y) cua d oan
ınh u a . a . . ˙ a
. ’ a ` ınh . ¯o
a . ¯e ˙ ˙ ¯ .

˙

thˇng v´
a o .i mˆt canh n`o d ´ bˇ ng c´ch thˆ gi´ tri d ˜ biˆt x hoˇc y v`o phu.o.ng tr` canh
o . a ¯o a ` a ´
e a . ¯a e ´ a a ınh .
. .
d u.ng hay ngang tu.o.ng u.ng. Tuy nhiˆn, trong thuˆt to´n tham sˆ ho´ d oan thˇng, ta s˜
¯´ ´ e a. a ´
o a ¯ . ˙

a e
t` c´c gi´ tri tham sˆ t trong khoang biˆ’u diˆn cua d oan thˇng cho d iˆ’m giao cua d u o
ım a a . ´
o ˙
’ e˙ ˜ ˙ ¯ .
e ’ ˙

a ¯e ˙ ˙ ¯
’ .`.ng
thˇng v` canh d u.o.c x´t. N´i chung, v` tˆ t ca c´c canh s˜ giao v´.i d u.`.ng thˇng, nˆn bˆn
˙

a a . ¯ . e o ´ ’
ı a ˙ a . e o ¯ o a˙
’ e o ´
a . ` ¯ .o.c t´
gi´ tri t cˆn d u . ınh. V´
a o .i mˆt loat c´c ph´p so s´nh d o.n gian s˜ cho biˆt c´c tham sˆ
o ˙ e
’ ´ ´
. . a e a ¯ e a o
trong bˆn gi´ tri n`y tu.o.ng u.ng v´.i c´c d iˆ’m giao thu.c su.. Sau d o c´c toa d o (x, y) cua
o´ a . a ´ o a ¯e ˙ . . ¯´ a . ¯ˆ . ˙

o a ¯e ¯ .o.c x´c d inh. N´i chung c´ch tiˆp cˆn n`y s˜ tiˆt kiˆm th`.i gian
mˆt hoˇc hai giao d iˆ’m d u . a ¯.
˙ o a ´ .
e a a e e ´ e o
. . .
ho.n thuˆt to´n cˇt x´n Cohen-Sutherland do n´ tr´nh v`ng lˇp cˆn thiˆt dˆ’ cˇt nhiˆu canh
a. a a e´ o a o a `
. a ´ ˙ ´
e ¯e a `e .
˙
’ ınh u
cua h` ch˜ . nhˆt. Ho.n n˜.a, c´c ph´p t´ trong khˆng gian tham sˆ 1D d o.n gian ho.n
a u a e ınh o ´
o ¯ ˙’
.
trong khˆng gian 2D.
o

Gia su. d a gi´c lˆi (R) d u.o.c d .nh ngh˜ nhu. mˆt d˜y c´c d ınh Pi = (xi , yi ), i =
˙ ˙ ¯
’ ’ a ` o ¯ . ¯i ıa o a a ¯˙
. ’
0, 1, . . . , L, trong hˆ toa d o thu.c v´.i P0 = PL . Muc d´ cua phˆn n`y l` loai bo nh˜.ng phˆn
e . ¯ˆ . o
. . . ¯ıch ˙ ’ ` a a . ˙ u
a ’ `
a
˙ ¯ .
’ ˙
’ `
cua d oan thˇng AB khˆng nˇ m trong “cu o
a o a ˙’.a sˆ’” (R) (H` 3.10).
˙ ınh


102
K´ hiˆu li , i = 0, 1, . . . , L, l` d u.`.ng thˇng d i qua hai d ınh liˆn tiˆp Pi v` Pi+1 . Dˇt
y e . a ¯ o ˙

a ¯ ¯˙’ e ´
e a -a
.

−→
+
(li ) := {P ∈ R2 | OP , ni > Di },
−→

(li ) := {P ∈ R2 | OP , ni < Di },

l` c´c nu.a mˇt phˇng ngo`i v` mˇt phˇng trong x´c d inh bo.i li , trong d ´ ni l` ph´p vector
a a ˙ ’ a. ˙

a a a a . ˙

a a ¯. ˙
’ ¯o a a
cua li d u.o.c chon hu.´.ng ra nu.a mˇt phˇng ngo`i v` Di l` hˇ ng sˆ n`o d ´. V` (R) l` mˆt
˙
’ ¯ . . o ˙
’ a
. ˙

a a a a ` a ´
o a ¯o ı a o .
` i, nˆn phˆn trong cua d a gi´c (R) ch´ l` giao cua c´c nu
tˆp lˆ e
a o `
a ˙ ¯
’ a ınh a ˙ a ˙
’ ’.a mˇt phˇng bˆn trong cua
a ˙

a e ˙

. .
˜
mˆi canh x´c d .nh bo
o . a ¯i ˙
’.i (R); t´.c l`
u a

L

(R) = (li ). (3.3)
i=0




Y tu.o.ng cua thuˆt to´n nhu. sau. V´.i mˆi d u.`.ng thˇng li , i = 0, 1, . . . , L, ch´ng ta
´ ˙
’ ˙
’ a
. a o ˜
o ¯ o a˙
’ u
˙
’ .a mˇt phˇng ngo`i x´c d inh bo.i l v` cˆp nhˆt
˙

. ˙ `’ a ˙ ¯ .

loai bo phˆn cua d oan thˇng AB thuˆc nu
a o ˙
. ’ a
. a a a ¯. ˙ i a a
’ . a
.

AB = AB ∩ (li ). Nˆu o´ ’
e ˙ . bu.´.c n`o d o AB ⊂ (l+ ) th` kˆt luˆn giao cua d oan thˇng v` d a
o a ¯´ ´ a
ı e ˙ ¯
’ a˙
’ a ¯
i .
a ` `
o a o´ .o.c lai, o. bu.´.c cuˆi c`ng phˆn d oan thˇng AB c`n lai s˜ nˇ m bˆn
gi´c lˆi bˇ ng trˆng; ngu . . ˙ ’ o ´
o u ` ¯ .
a ˙

a o . e ` a e
ınh a ` ` ım.
trong (R) ch´ l` phˆn giao cˆn t`
a a

Dˆ’ dˆ d`ng xu. l´, ch´ng ta biˆ’u diˆn AB o. dang tham sˆ
-e ˜ a
˙ e ˙ y
’ u e˙ ˜
e ˙ .
’ ´
o


P (t) = A + ct

−−−→
trong d o c = BA l` vector chı phu.o.ng cua d u.`.ng thˇng AB. Khi t = 0, P (t) d at tai d iˆ’m
¯´ a ˙
’ ˙ ¯ o
’ ˙

a ¯ˇ . ¯ e
. ˙
A v` t = 1, P (t) d at tai d iˆ’m B. Ta n´i P (t) “di chuyˆ’n” t`. A dˆn B khi t tˇng t`. 0 dˆn
a ¯ˇ . ¯ e
. ˙ o e˙ u ´
¯e a u ¯e ´
1 v` c l` hu.´.ng di chuyˆ’n.
a a o e˙

Khi x´t d u.`.ng thˇng li ch´ng ta su. dung hai gi´ tri tin v` tout dˆ’ x´c d .nh pham vi
e ¯ o a˙
’ u ˙ .
’ a . a ˙
¯e a ¯i .
thay d o’i cua tham sˆ t d oi v´ ¯ .
˙ ’
¯ˆ ˙ ´
o ¯ˆ o ´ .i d oan thˇng AB c`n lai. T´.c l`, du.a trˆn c´c tham sˆ n`y

’ o . u a . e a ´
o a
ch´ng ta c´ thˆ’ x´c d .nh phˆn c`n lai cua d oan AB o
u ˙
o e a ¯i ` o . ˙ ¯ .
a ’ ˙
’. bu.´.c d ang x´t ch´ l` tˆp c´c d iˆ’m
o ¯ e ınh a a a ¯ e ˙
.
P (t) v´.i tin ≤ t ≤ tout . L´c ban d` u tin = 0 v` tout = 1. Khoang thay d o’i cua tham sˆ t s˜
o u ¯aˆ a ˙
’ ˙ ’
¯ˆ ˙ ´
o e
tiˆp tuc co lai khi kiˆ’m tra v´ o .
´
e . e˙ o.i mˆt canh m´.i v` nh˜.ng phˆn khˆng nˇ m trong d a gi´c (R)
o a u `
a o `
a ¯ a
. .
s˜ bi loai bo. Nˆu o. bu.´.c n`o d ´, khoang n`y bˇ ng trˆng thuˆt to´n s˜ kˆt th´c v` ta c´
e . . ˙ ’ ´ ’
e ˙ o a ¯o ˙’ a a ` ´
o a
. a e e ´ u a o
˙ ¯ .
’ ˙

giao cua d oan thˇng AB v´ ¯
a o.i d a gi´c (R) bˇ ng trˆng. Trong tru.`.ng ho.p ngu.o.c lai, d oan
a `
a ´
o o . . . ¯ .
o . e a ¯. `
c`n lai [tin , tout ] s˜ x´c d inh phˆn giao AB ∩ (R).
a

X´t d u.`.ng thˇng li d i qua hai d ınh Pi v` Pi+1 . C´ hai tru.`.ng ho.p xay ra:
e ¯ o ˙

a ¯ ¯˙’ a o o . ˙



103
Du.`.ng thˇ ng li song song v´.i d . n thˇ ng AB.
- o ˙

a o ¯oa ˙

a


Du.`.ng thˇng li song song v´.i d oan thˇng AB nˆu ph´p vector ni vuˆng g´c v´.i vector c;
- o a˙
’ o ¯ . a˙
’ ´
e a o o o
u.c l` n , c = 0. Trong tru.`.ng ho.p n`y, d oan thˇng AB nˇ m ho`n to`n trong nu.a mˇt
t´ a i o a ¯ . ˙
a’ `
a a a ˙
’ a
. .
phˇa˙ ng ngo`i (li ) hoˇc nu.a mˇt phˇng trong (li ). Dˆ’ kiˆ’m tra tru.`.ng ho.p n`o xay ra, ta
’ a +
a
. ˙
’ a. a˙
’ − -e e
˙ ˙ o . a ˙

−−−→
chı cˆn x´t vi tr´ tu.o.ng d oi cua mˆt d iˆ’m, chˇng han A, v´.i d u.`.ng thˇng li . Dˇt a = OA .
˙ ` e . ı
’ a ´ ’
¯ˆ ˙ o ¯e
. ˙ ˙

a . o ¯ o ˙

a -a.
Khi d ´¯o


1. Doan thˇng AB thuˆc nu.a mˇt phˇng trong (li ) nˆu ni , a < Di . Trong tru.`.ng ho.p
- . ˙

a o ˙
. ’ a. ˙

a − ´
e o .
` n cˆp nhˆt lai c´c tham sˆ tin v` tout .
n`y ta khˆng cˆ a
a o a . a . a
. ´
o a

2. Ngu.o.c lai, nˆu ni , a > Di th` d oan thˇng AB thuˆc nu.a mˇt phˇng ngo`i (li ) v` do
. . e ´ ı¯ . ˙

a o ˙
. ’ a
. ˙

a a + a
¯´ ı a
. a e´
d o theo (3.3) th` AB ∩ (R) = ∅; thuˆt to´n kˆt th´c.
u



Du.`.ng thˇ ng li khˆng song song v´.i d . n thˇ ng AB.
- o ˙

a o o ¯oa ˙

a


Nˆu d u.`.ng thˇng li khˆng song song v´.i AB th` gi´ tri ni , c kh´c khˆng v` li phai cˇt
´
e ¯ o ˙

a o o ı a . a o a ’ ´
˙ a
d u.`.ng thˇng qua hai d iˆ’m A, B; t´.c l` tˆn tai ti sao cho P (ti ) ∈ li . Dˆ d`ng kiˆ’m tra rˇ ng
¯ o ˙

a ¯e ˙ u a ` . o ˜ a
e e˙ `
a

Di − ni , a
ti = .
ni , c

Cˆn lu.u y mˆu sˆ trong biˆ’u th´.c trˆn c´ thˆ’ bˇ ng khˆng. Dˆ’ d iˆu n`y khˆng xay ra, thuˆt
`a ´ a o˜ ´ e˙ u e o e a ˙ ` o - e ¯`
˙ e a o ˙
’ a
.
to´n cˆn kiˆ’m tra
a ` a e˙


• ni = 0 (t´.c l`, ph´p vector phai kh´c vector khˆng); v`
u a a ˙
’ a o a

• c = 0 (t´.c l` A = B).
u a


C´ hai tru.`.ng ho.p nhu. trong H` 3.11:
o o . ınh


1. Di v`o. Doan thˇng AB d i t`. nu.a mˇt phˇng ngo`i (li ) v`o nu.a mˇt phˇng trong
- a - . ˙

a ¯ u ˙ ’ a
. ˙

a a + a ˙’ a
. ˙

a

(li ) (H` 3.11(a)).
ınh

2. Di ra. Doan thˇng AB d i t`. nu.a mˇt phˇng trong (li ) ra nu.a mˇt phˇng ngo`i (li )
- - . ˙

a ¯ u ˙ ’ a
. ˙

a −
˙’ a
. ˙

a a +
(H` 3.11(b)).
ınh


104
A
(a) n
.
..
.
..
.
..
Nu.a mˇt phˇng ngo`i
˙’ a
. ˙

a a
.
..
. .
. .
..
..
.
... .
.
..
.
.
.
.
.
.
. .
. .
.
. . .
.
...............................................................................................
. .
li //////////////////////////////////
.....................................................
.......... .................
.
.
..
..
..
..
...
..
.
.. .
.
.
.
.
.
.
.......................................................................
.
.
.
.
.
.
.
.
.
.. . ...
...
..
.. .
. ..
. ..
.
.
..
.. .
.
. .
.
.. .
. .
.
.. . .
..
..
..
..
..
c
.
.
..
.
..
.
..
.
.
.
.
.
.t
.
.
.
.

.. .. ..
. ..
..
..
..
. .
. .
. .
....
..
˙

Nu.a mˇt phˇng trong
a ˙

a
..
..
..
..
.. .......
.......
.......
.......
......
........
....... ..
.
.
..
...
.
..............
....... .. .
..
..
.

B

A Nu.a mˇt phˇng ngo`i
˙’ a
. ˙

a a
(b) n
..
.
..
.
...
..
..
.. t
.
..
. .
.. .
..
.
..
.. .
. ..
..
..
.
.
... .
.
. .
...
.
. .
. .
.
.
. . .
......................... .....................................................................
.
li //////////////////////////////////
.............................
.......... ................
.
.
..
..
..
..
..
..
.
..
.
.. .
.
.
.
.
.
.
...............................................................................................
.
.
.
.
.
.
.
.
.. .. .
.
..
.. .
. .. .
.
..
.. .
.
. ..
.. .
. .
.
.. . .

Nu.a mˇt phˇng trong
.
.
. ..
..
..
..
..
..
..
c .
.
..
.
..
.
.. ..
˙’.
.
.
.
.
.
.
a
. ˙

a
..
.. . ..
. .
. .
.. . .
....
. ..
.. ......
.. ....... ..
. ..... ..
.. .......
.......
..
.. .......
.......
.
.
..............
.... .....
..
.
.

B

H` 3.11: Doan thˇng AB d i v`o hay d i ra nu.a mˇt phˇng x´c d .nh bo.i li .
ınh - . ˙

a ¯ a ¯ ˙’ a
. ˙

a a ¯i ˙


Dˆ’ x´c d inh tru.`.ng ho.p n`o xay ra, ch´ng ta x´t g´c θ ho.p bo.i c´c vector c v` ni .
- e a ¯.
˙ o . a ˙
’ u e o . ˙ a
’ a
´
e o ˙

Nˆu g´c θ nho ho .n 900 (t´.c l` n , c > 0) th` tu.o.ng u.ng d i ra; ngu.o.c lai u.ng v´.i d i v`o.
u a i ı ´ ¯ . . ´ o ¯ a

Trong tru.`.ng ho.p d i v`o, th` phˆn u.ng v´.i t < ti nˇ m ngo`i d a gi´c (R) v` do d ´ cˆn
o . ¯ a ı ` ´a o `
a a ¯ a a ¯o ` a
.o.c lai, nˆu d i ra, phˆn u.ng v´.i t > t nˇ m ngo`i d a gi´c
cˆp nhˆt lai tin := max(tin , ti ). Ngu . .
a
. a .
. ´
e ¯ ` ´
a o i `
a a ¯ a
(R) v` do d ´ cˆp nhˆt lai tout := min(tout , ti ).
a ¯o a . a .
.

Ch´ y rˇ ng, o. bu.´.c n`o d o nˆu xay ra tru.`.ng ho.p tin > tout th` thuˆt to´n s˜ kˆt
u ´ `a ˙
’ o a ¯´ e ´ ˙
’ o . ı a
. a e e ´
u `
th´c: phˆn giao AB ∩ (R) = ∅.
a

Trong tru.`.ng ho.p ngu.o.c lai, o. bu.´.c cuˆi c`ng, AB ∩ (R) l` d oan thˇng tu.o.ng u.ng
o . . . ˙ ’ o ´
o u a ¯ . ˙

a ´
hai d iˆ’m d` u cuˆi P (tin ) v` P (tout ).
˙
¯ e ¯ˆ a o´ a

H`m Cyrus Beck() tra vˆ tri False nˆu giao cua d oan thˇng AB v` d a gi´c (R) (d u.o.c
a ˙ ` .
’ e ´
e ˙ ¯ .
’ ˙

a a¯ a ¯ .
lu.u trong danh s´ch Poly kiˆ’u VertPtr2D) bˇ ng trˆng; ngu.o.c lai l` True v` phˆn giao l`
a e˙ `
a ´
o . . a a ` a a
¯ . o.i. Dˆ’ ho`n thiˆn thu tuc, ch´ng ta cˆn phai thˆm c´c d`ng lˆnh kiˆ’m tra c´c
d oan AB m´ - e a ˙ e ˙ .
’ u `
a ˙
’ e a o e e˙ a
. .
¯`
d iˆu kiˆn biˆn.
e e
. e


Boolean Cyrus_Beck(Point2D *A, Point2D *B, VertPtr2D Poly)
{
float t_in = 0, t_out = 1, t_hit, Denom, D;
Point2D F, S;


105
Vector2D c, n, f, a;
VertPtr2D Tempt = Poly;


if (Tempt == NULL) return False;


F = Tempt->Vertex;
c.dx = (*B).x - (*A).x;
c.dy = (*B).y - (*A).y;
a.dx = (*A).x;
a.dy = (*A).y;


while ((Tempt = Tempt->Next) != NULL)
{
S = Tempt->Vertex;
n.dx = (S.y - F.y);
n.dy = (F.x - S.x);


f.dx = F.x;
f.dy = F.y;


D = Dot2D(n, f);


if ((Denom = Dot2D(n, c)) == 0.0)
if (Dot2D(n, a) > 0.0) return False;
else
{
t_hit = (D - Dot2D(n, a)) / Denom;
if (Denom > 0.0)
{
if (t_out > t_hit) t_out = t_hit;
}
else
{
if (t_in < t_hit) t_in = t_hit;
}


if (t_in > t_out) return False;


106
}
F = S;
}


F.x = (1 - t_in)*(*A).x + t_in*(*B).x;
F.y = (1 - t_in)*(*A).y + t_in*(*B).y;
S.x = (1 - t_out)*(*A).x + t_out*(*B).x;
S.y = (1 - t_out)*(*A).y + t_out*(*B).y;
*A = F;
*B = S;


return True;
}



Ch´ y rˇ ng dˆ d`ng mo. rˆng thuˆt to´n trong khˆng gian ba chiˆu cho b`i to´n x´c
u´ ` a ˜ a
e ˙ o
’ . a. a o `e a a a
¯i ˙
’ o ¯ .
. ˙

a a o ¯
. e `
d .nh giao cua mˆt d oan thˇng v` mˆt d a diˆn lˆi.
. o




3.5 Giao hai d gi´c
¯a a

Trong hˆu hˆt c´c u.ng dung, c´c d a gi´c d u.o.c d inh ngh˜ nhu. mˆt d˜y c´c d ınh trong hˆ
` ´
a e a ´ . a ¯ a ¯ . ¯. ıa o a a ¯˙
. ’ e
.
.c. Mˆt cu.a sˆ’ c˜ng d u.o.c d inh ngh˜ nhu. vˆy v` trong nhiˆu tru.`.ng ho.p ch´ng
o ˙ o ˙ u ¯ . ¯. `
toa d ˆ thu
. ¯o .
. . ’ ıa a a
. e o . u
o e ` ¯ˆ
´ ´
ta muˆn v˜ phˆn d oi tu .
a .o.ng nˇ m bˆn trong cu.a sˆ’ x´c d inh bo.i d a gi´c.
`
a e ’ ˙
˙ o a ¯. ˙ ¯
’ a

V´.i d ˆi tu.o.ng l` mˆt d oan thˇng, ta c´ thˆ’ ´p dung phu.o.ng ph´p Cyrus-Beck trong
o ¯o ´ . a o ¯ .
. a˙
’ o ea ˙ . a
` ˙
’ .o.c cˇt d oi v´.i mˆ i d u.`.ng biˆn cua d a gi´c, v` c´c d iˆ’m d` u cuˆi
´ ´
Phˆn 3.4: d oan thˇng d u . a ¯ˆ o o ¯ o
a ¯ . a ¯ ˜ e ˙ ¯
’ a ˙
a a ¯ e ¯ˆ a o´
d u.o.c h` th`nh. V´.i c´c d ˆi tu.o.ng l` d a gi´c th` viˆc t` giao (hay cˇt x´n) c´ phˆn ph´.c
¯ . ınh a o a ¯o ´ . a¯ a ı e ım
. ´
a e o ` a u
tap ho .n bo.i v` trong qu´ tr` xu. l´ thuˆt to´n cˇt, mˆt d a gi´c c´ thˆ’ bi phˆn manh th`nh
˙ ı
’ a ınh ˙ y ’ a a a ´ o ¯ ˙
a o e . a ˙
’ a
. . .
nhiˆu d a gi´c con kh´c nhu. trong H` 3.12. Da gi´c c´ thˆ’ d u.o.c tˆ m`u v´.i mˆ u tˆ cho
` ¯
e a a ınh - ˙
a o e ¯ . o a o ˜
a o
.´.c v` do d o c´c manh d a gi´c phai d u.o.c nˆi kˆt v´.i mˆ u tˆ d ´.
tru o a ¯´ a ˙
’ ¯ a ´ ´
˙ ¯ . o e o a o ¯o
’ ˜

Ta s˜ quy u.´.c rˇ ng d a gi´c bi cˇt l` d a gi´c d oi tu.o.ng (S). Cu.a sˆ’ s˜ d u.o.c goi l` d a
e o ` a ¯ ´
a . a a ¯ a ¯ˆ ´ . ˙
˙ o e ¯ .
’ . a ¯
gi´c cˇt (C). Vˆ n d` d ˇt ra l` l`m sao tao ra mˆt danh s´ch c´c d ınh cua phˆn giao gi˜.a
a a ´ ´ e .
a ¯ˆ ¯a a a . o
. a a ¯˙’ ˙
’ `
a u
hai d a gi´c n`y?
¯ a a

Trong nh˜.ng phˆn sau, ch´ng ta s˜ x´t hai phu.o.ng ph´p:
u `
a u e e a


107
............................................
............................................
.....
..... .
.
.
....
.... .
.
.....
..... .
.
..
. .....
..... .
.
.
..
. .....
.....
.
.
.
.
. .
. ...
.....
.. ..........................................
......................................... . .
.
.
.. .
. ...
. .
.
..
..
.
.
. ...
...
.
.
.
..
..
.
.
. . ...
...
.
.
.
.
.. .
.
. ...
... .
.
.
..
.. .
.
. ...
... .
.
..............
.............
. ...
...
.
.
.
.
...
... .
.
.
...
... .
.
...
...
.
.
.
...
...
.
.
(C)— ...
...
.
...
... — (S)
.
.
.
.
.
.
.
. ...
...
.
.
.
.
...
... .
.
.
...
... .
.
. ...
...
.
.
.
.
...
... .
.
.
...
... .
.
....
...
.
.
.
.
...
... .
.
.............................................................
.............................................................
...
.
.
.




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

` ˙

Phˆn giao cua hai d a gi´c
a ¯ a
H` 3.12: Giao hai d a gi´c.
ınh ¯ a

1. Thuˆt to´n Sutherland-Hodgman [25]. Phu.o.ng ph´p n`y ho`n to`n d o.n gian v` thu.c
a
. a a a a a ¯ ˙ a .

hiˆn qu´ tr` cˇt mˆt d a gi´c bˆ t k` v´.i mˆt d a gi´c lˆi. Cu.a sˆ’ h` ch˜. nhˆt l`
e
. a ınh a ´ o ¯
. ´
a a y o o ¯
. a `o ˙
˙ o ınh u
’ a a
.
.`.ng ho.p d ˇc biˆt cua c´c d a gi´c lˆi. Thuˆt to´n n`y c´ thˆ’ sinh thˆm nh˜.ng
mˆt tru o
o ˙ a ¯
’ ` ˙
. . ¯a . e
. a o a. a a o e e u
.i v` do d ´ cˆn loai bo sau khi kˆt th´c.
¯o ` ´
canh m´ a
. o a . ˙ ’ e u

2. Thuˆt to´n Weiler-Atherton [27]. C´ch tiˆp cˆn n`y ph´.c tap ho.n nhu.ng cho ph´p
a
. a a ´ .
e a a u . e
cˇt hai d a gi´c bˆ t k`; thˆm ch´ c´ thˆ’ c´ lˆ hˆ’ng trong c´c d a gi´c.
´
a ¯ ´
a a y a
. ˙
ı o e o o o ˜ ˙ a ¯ a



3.5.1 Thuˆt to´n Sutherland-Hodgman
a
. a

V` c´ nhiˆu tru.`.ng ho.p xay ra khi d a gi´c d oi tu.o.ng (S) d u.o.c cˇt bo.i d a gi´c lˆi (C)
ı o `
e o . ˙
’ ¯ a ¯ˆ´ . ¯ . a ´ ˙ ¯
’ a ` o
nˆn ch´ng ta cˆn phu.o.ng ph´p tˆ’ ch´.c c´c phˆn d ˜ d i qua trong qu´ tr` xu. l´. Thuˆt
e u `
a ˙
a o u a ` ¯a ¯
a a ınh ˙ y ’ a
.
to´n Sutherland-Hodgman ´p dung phu
a a .o.ng ph´p chia dˆ’ tri: Phˆn t´ b`i to´n kh´ th`nh
a ˙
¯e . a ıch a a o a
.
nh˜ u .ng b`i to´n con d o.n gian ho.n. Dˇc biˆt, tu.o.ng tu. thuˆt to´n Cyrus-Beck, n´ lo.i dung
a a ¯ ˙
’ -a e a a o . .
. . . .
ınh a ˙ ¯ ´ ’ a `
t´ chˆ t cua d a gi´c lˆi: mˆt d u o
o o ¯ .`.ng thˇng d i qua canh bˆ t k` cua d a gi´c s˜ chia mˇt

’ ¯ ´
a y ˙ ¯ ’ a e a
. . .
˙
’ `
phˇng th`nh phˆn trong (ch´ ¯
a a a u.a d a gi´c) v` phˆn ngo`i. Thuˆt to´n s˜ cˇt d a gi´c (S) v´.i
a a ` a a a a e a ¯ ´ a o
.
du o
¯ .`.ng thˇng qua mˆ i canh cua d a gi´c (C) v` gi˜. lai phˆn thuˆc nu.a mˇt phˇng trong.

’ ˜
o . ˙ ¯
’ a a u . `
a o ˙
’ a ˙

a
. .
Tiˆn tr` d u.o.c lˇp lai cho moi canh cua (C). H` 3.14 minh hoa thuˆt to´n cˇt cua d a gi´c
e´ ınh ¯ . a . . . . ˙
’ ınh . a
. ´ ’
a a ˙ ¯ a
(S) v` h` ch˜ a
a ınh u . nhˆt (C). Danh s´ch c´c d ınh cua Subj xuˆ t ph´t l` A, B, C, D, E, F, G, A.
a a ¯˙ ’ ˙
’ ´
a a a
.
- .o.c cˇt v´.i c´c canh bˆn tr´i, bˆn du.´.i, bˆn phai v` bˆn trˆn cua (C); trong
Da gi´c n`y d u . a o a .
a a ¯ ´ e a e o e ˙ a e
’ e ˙ ’
˜
mˆi bu o
o .´.c, mˆt danh s´ch m´.i d u.o.c sinh ra v` g´n lai cho (S). Danh s´ch sinh ra o. bu.´.c
o a o ¯ . a a . a ˙
’ o
.

108
cuˆi c`ng tu.o.ng u.ng mˆt hoˇc nhiˆu d a gi´c liˆn kˆt lai v´.i nhau cho ta thˆng tin giao cua
´
o u ´ o
. a
. ` ¯
e a e e . o´ o ˙

hai d a gi´c.
¯ a

K´ hiˆu Subj v` Clip l` danh s´ch c´c d ınh cua hai d a gi´c (S) v` (C) tu.o.ng u.ng.
y e . a a a a ¯˙ ’ ˙
’ ¯ a a ´
Danh s´ch Subj s˜ d u.o.c cˆp nhˆt sau mˆ i tiˆn tr` cˇt v´.i mˆt canh cua d a gi´c (C). V`
a e ¯ . a . a
. ˜ ´
o e ´
ınh a o o . . ˙ ¯
’ a ı
a ` .`.ng thˇng d i qua canh bˆ t k` cua n´ s˜ chia mˇt phˇng th`nh
(C) l` d a gi´c lˆi, nˆn d u o
a ¯ o e ¯ ˙

a ¯ ´
a y ˙ ’ o e a a˙
’ a
. .
`
a a a ` a e ¯˙
’ e ´
phˆn ngo`i v` phˆn trong. X´t hai d ınh liˆn tiˆp P v` P
e a cua (C) v` d u.`.ng thˇng l d i
˙
’ a ¯ o ˙

a ¯ i i+1 i

qua hai d iˆ’m n`y. K´ hiˆu
¯e ˙ a y e . v`
a tu.o.ng u.ng l` c´c nu.a mˇt phˇng ngo`i v` trong
´ a a ˙ ’ a
.


(li )
a a a −
(li )
tu.o.ng u.ng. Ta biˆt rˇ ng (xem Phˆn 3.3) d a gi´c lˆi l` giao cua c´c nu.a mˇt phˇng trong
´ e `
´ a `
a ¯ a ` ao ˙ a ˙
’ ’ a
. ˙

a
x´c d inh bo.i c´c canh cua n´: (C) = ∩i (li ). X´t canh e liˆn thuˆc hai d ınh liˆn tiˆp F v` S
a ¯. ˙ a .
’ ˙ o
’ −
e . e o
. ¯˙’ e e´ a
cua d a gi´c Subj. C´ bˆn kha nˇng xay ra gi˜.a canh e v` d u.`.ng thˇng li : ca hai d ınh F, S
˙ ¯
’ a o o´ ˙ a
’ ˙
’ u . a¯ o ˙

a ˙’ ¯˙

thuˆc phˆn trong; ca hai thuˆc phˆn ngo`i; hoˇc ch´ng thuˆc hai ph´ cua d u.`.ng thˇng li .
o. `
a ˙
’ o
. `a a a
. u o
. ıa ˙ ¯ o
’ ˙

a
Trong mˆi tru.`.ng ho.p, ta xuˆ t mˆt (hoˇc hai) d iˆ’m ra mˆt danh s´ch m´.i nhu. trong H`
˜
o o . a´ o. a
. ¯e ˙ o
. a o ınh
3.13.
..
..... ..
.....
..
..
.. ..
..
..
.
. .
. ... .
. .
. ...
.
...
..
. .
...
..
.
.
.
. . .
.
. .
− . + − . +
(li ) . ..
.....
.
..
.
.
.
.
. ..
.
(li ) (li ) . ..
.....
.
..
.
.
.
.
. ..
.
(li )
....
...
.. ....
...
..
.
. .
.
.
. .
. ... .
. .
. ...
.
...
..
. .
...
..
.
.
.
. . .
.
. .
.
. ..
..... .
. ..
.....
.
..
.. .
..
..
.
.
. .. .
.
. ..
.
....
... .
....
...
.. ......
..
....... .. .. ......
..
....... ..
.
. ....... ..
.......
.
. ....... ..
.......
. .. ..........
. .
.. .......... .
. . .. ..........
. .
.. .......... .
.
F .......
.......
.......
.......
....... .
......
.
........
..
........
.
.
.
.
.....
. ..
..
.
..
.
..
.
. .......
.......
.......
.......
....... .
......
.
........
..
........
.
.
.
.
.....
. ..
..
.
..
.
..
.
.
..
.
..
.. .
..
.. .
.
.. ..
.
..
.. .
..
.. .
.
..
.. .
. .
.. .. .
. .
..
..
.. . ..
. .
. ..
.. . ..
. .
.
..
.. ....
...
..
.
.
.. ..
.. ....
...
..
.
.
..
.. .
. .
. .. .
. .
.
.. .
. ..
. ... .
.
. .. .
. ..
. ... .
.
.
.. . . .. . .
..
.. ...
..
.. .
..
.
..
.. ...
..
.. .
..
.
.. .
. . ..
. .. .
. . ..
.
..
.. .
. ..
.... .. ..
.. .
. ..
.... ..
. .
. . .
.
.. .. .. ..

..
....
..
...
..
.
.
.
.
. ..
.
.
..
.
.
..
..
.. I • .
.
.
.
. ..
.
..
.
.
.. .
.......................................................
.. .
................. .....................................
.
.
.
.
.
.
. .
.
F ................. .....................................
.......................................................
.. .
.
.
.
.
.
.
. .
.
. .
.
S
S . ...
...
.
..
.
.
.
. .
.
....
. ...
...
.
..
.
.
.
. .
.
....
....
. ....
.
. .

li li
..
(a) ..
(b)
.....
.. .....
..
..
.. ..
..
.
. .
. ... .
. .
. ...
.
...
..
. .
...
..
.
.
.
. . .
.
. .
− . + − . +
(li ) . ..
.....
.
..
.
.
.
.
. ..
(li ) (li ) . ..
.....
.
..
.
.
.
.
. ..
(li )
.....
.
...
.. .....
.
...
..
.
. .
.
.
. .
. ... .
. .
. ...
.
...
..
. .
...
..
.
.
.
. . .
.
. .
.
. ..
..... .
. ..
.....
.
..
.
.
.
.
. ..
.
S .
..
.
.
.
.
. ..
. F
....
...
.......
.. ....
... ......
..
....... ... ....... ..
.
.
..
.............
.
........
........
..
....... ...
.......
. .. ..........
. .
..
..
.
..
.
I • .
.
..
.............
.
........
........
..
....... ..
.......
. .. ..........
. . .
.
..
.
... .
... . .. .... .
..... . ..
....
... .......
....... . .
. .......
....... . .
.
. .. ... .
S• . .
....... . .. ..... .
..
.
......... .....
. ..
.
.
..
. ........
.
.. .
.. . .....
. ..
.
.
..
.
..
.. ..
.
.
. ..
.
. ..
.. ..
.
.
. ..
.
.
.. .
. .. .
. .
. .. .
.
.. . . .. . .
..
.. ....
...
..
.
.
..
..
.. ....
...
..
.
.
..
.. .
. .
. .. .
. .
.
.. .
. ..
. ... .
.
. ..
.. .
. ..
. ... .
.
.
.. . . . .
..
.. ...
..
.. .
..
.
..
.. ...
..
.. .
..
.
.. .
. . ..
. ..
.. .
. . ..
.
..
.. .
. ..
.... .. ..
.. .
. ..
.... ..
. .
. . .
.
..
..
.. ..
.
.
. .
.
..
..
.. ..
.
.
. .
.
..
.. .
. .. . .. .
. .. .
.......................................................
.
.. .
................. .....................................
.
.
.
.. .
......................................................
.. .
......................................................
..
..
.
.. .
.
.
. .
.
. . . .
. ...
...
.
..
.
.
.
. .
.
....
F . ...
...
.
..
.
.
.
. .
.
....
....
. ....
.
. .

li li
(c) (d)
H` 3.13: Bˆn tru.`.ng ho.p v´.i mˆ i canh cua (S).
ınh ´
o o . o o .˜ ˙





109
.
.
.
.
.
.
B................................................................................... A
..
..
.
B .
.
.
.
.
. 1 A
.... .... .... .... ..................
... ... ... ... .................
.
.
.
.
.
.
.
.
.
.
— (S)
.
.
.
.
(C) .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. .
.
.
.
.
.
.
.
.
.
.
.
. | .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. .
. . . .
.
.
.
.
.
.
.
. ...
.
...
...
...
.
.
...
...
I F..................................................E
...
...
. ...
...
.
.
.
.
.
.
.
.
.
.
.
.
. .....
.
. .....
....
.
...
....
..
I F E
...............................
..............................
.
. .
...
...
.
...
...
.
. . .
. .
......
. ... ...
... .
.
.
... ...
. . ...
... .
.
.
.
.
.
.
.
.
. ...
...
...
...
...
...
...
...
...
...
...
...
...
...
.
.
.
.
.
.
.
.
.
.
.
.
.
.
4
. .
... .
... .
..
.
...
....
.
.
.
.
.
...
...
....
...
...
...
.
.
.
.
.
.
.
.
.
. .. .. . . .. .
.
. ....
... .....
... .
. .
. ....
. .
.
... .... ...........................
. ...
... .
.
.
.
. ..
.
.
.......................................
....................................... .
.
.
.
.
. .... ... .
. . ........................
.
.
.
.
.
.
. .
. . .
.
.
.
.
.
.
.
.
.
.
H G
.
.
.
.
.
.
.
.
.
.
.
.
. H
.
.
.
.
.
.
.
.
.
3 G
.
.
.
.
.
.
.
.
. .
. ...................................................................................................
..................................................................................................... .. .... .... .... .... ........................................................................
. . ... ... ... ... . ......................................................................
.. . .
.
.
C D C ............
..... ..........
...
....
.
.
.
.
.
.
.
.
.
2 D
(a) .
.
.
(b)
.
.
.
.
.
.
1 A 1 A
.
.
.
.
.
.
.
...............
. .............
.
. . ...............
. .............
.
. . .
.
.
. .
. .
. .
. .
.
.
. .
. .
. .
. .
.
.
. .
.
. .
. .
.
. .
.
. . . . .
.
.
. .
. .
. .
. .
.
. .
. . .
. .
.
.
. .
. .
.
.
.
. .
.
. .
.
.
...
...
...
.
.
...
....
..
I F
...............................
..............................
E .
...
...
.
.
...
...
....
..
I F 9 .
.
.
.
.
.
.
.................. .... ....
................. ... ...
.
E
.
...
...
. ...
... .
. .
...
...
. .
...
...
. .
.
... ...
...
.
. ... . . .
4 5 ...
. ...
...
...
...
7
.
.
.
.
.
.
.......................................................................................................................
............................................................ ........................................... ..............
.. ..
. .
. 6 4 5 ...
7 .
...
...
...
.
...
....
...
.
8
.
.
.
.
.
.
.
. .. ... ..
.... .... ...
.
.
.
.
6
.
.
. . .
. .
.
. . .
.
.
.
.
. . .... .... .... .
... ... ... ...
... .
.
.
.
.. .
...
.
..
.
.
.
.
.
.
.
.
.
.
3 G
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. ... ... ... ... ... ... ... ... ... ... ... .
. .... .... .... .... .... .... .... .... .... .... .... . .
.
.
2 D
.
.
.
...............
. .
. .............
.
.
.
. ..
..
(c) (d) .
.
.




.
..
..
..
.
. ... ...
.
.
1 A
. .... .... .
.
... . .
.
.
.
.
.
.
.
.
.
.
. 10 .
.
........................................... ......................................................................
...................................................................................................................
. . ..
11 .
...
.
.
.
.
..
..
F 9
...
...
...
...
... I
...
... ...............
...
...
...
...............
... ...
...
4 5 7 ..
...
...
. ...
...
...
...
8

(e)

o ı . ˙
. ’
H` 3.14: Mˆt v´ du cua thuˆt to´n Sutherland-Hodgman.
ınh a
. a

¯˙’ ` ´
1. Hai d ınh F v` S nˇ m trong: xuˆ t S.
a a a


2. Dınh F nˇ m trong v` S nˇ m ngo`i: t` giao d iˆ’m I v` xuˆ t n´.
’ `
a a `
a a ım ¯e ˙ ´
a a o

¯˙’ a `
a a o ´
3. Hai d ınh F v` S nˇ m ngo`i: khˆng xuˆ t.
a


4. Dınh F nˇ m ngo`i v` S nˇ m trong: t` giao d iˆ’m I; xuˆ t I v` sau d o xuˆ t S.
’ `
a a a `
a ım ¯e ˙ ´
a a ¯´ a ´


Bˆy gi`. ta ´p dung c´ch xu. l´ n`y cho H` 3.14.
a o a . a ˙ y a
’ ınh


1. Danh s´ch Subj sau khi cˇt (S) v´.i canh bˆn tr´i cua (C) :
a ´
a o . e a ˙ ’

(1, 2, D, E, F, G, 3, 4, I, A, 1).

2. Danh s´ch Subj sau khi cˇt (S) v´.i canh bˆn du.´.i cua (C) :
a ´
a o . e o ˙ ’

(5, 6, E, F, 7, 5, 4, I, A, 1, 5).


110
3. Danh s´ch Subj sau khi cˇt (S) v´.i canh bˆn phai cua (C) :
a ´
a o . e ˙ ˙
’ ’

(8, 9, F, 7, 5, 4, I, A, 1, 5, 8).

4. Danh s´ch Subj sau khi cˇt (S) v´.i canh bˆn trˆn cua (C) :
a ´
a o . e e ˙ ’

(9, F, 7, 5, 4, I, 10, 11, 5, 8, 9).


Ch´ y rˇ ng c´ thˆm nh˜.ng canh phu nhu. (5, 4) nˆi hai manh d a gi´c d u.o.c tao ra
u ´ a ` o e u . . ´
o ˙
’ ¯ a ¯ . .
trong qu´ tr` thu.c hiˆn thuˆt to´n. Nh˜.ng canh nhu. vˆy c´ thˆ’ gˆy kh´ khˇn trong mˆt
a ınh . e
. a
. a u . a o e a
. ˙ o a o.
´
sˆ u
o´ .ng du.ng, chˇng han tˆ m`u d a gi´c. Ta c´ thˆ’ loai bo nh˜.ng canh nhu. vˆy; tuy nhiˆn
˙

a ˙
o e . ˙ ’ u
. . o a ¯ a . a
. e
d ˆy l` b`i to´n khˆng tˆm thu.`.ng (xem [24]).
¯a a a a o `
a o

Trong mˆ i tiˆn tr` thu.c hiˆn thuˆt to´n Sutherland-Hodgman, mˆt danh s´ch m´.i
˜ ´
o e ınh . e
. a
. a o
. a o
d u.o.c tao ra v` sau d o g´n lai cho danh s´ch Subj. Do d ´ ch´ng ta cˆn mˆt danh s´ch trung
¯ . . a ¯´ a . a ¯o u `
a o
. a
a ˙ ˙’ ’
gian NewSubj. M˜ gia cua thuˆt to´n nhu
a a . sau:
.


V´.i mˆ i d u.`.ng thˇng l d i qua hai d ınh liˆn tiˆp cua d a gi´c (C) thu.c hiˆn
˜
o o ¯ o ˙

a ¯ ¯˙’ e ´ ˙ ¯
e ’ a . e
.

• X´c d inh ph´p vector n v` hˇ ng sˆ D t`. d u.`.ng thˇng l.
a ¯. a a a` ´
o u ¯ o ˙

a
• Kho.i tao danh s´ch NewSubj = NULL.
˙ .
’ a
• V´.i hai d ınh F, S liˆn tiˆp cua d a gi´c (S), kiˆ’m tra c´c tru.`.ng ho.p cua canh
o ¯˙
’ e ´ ˙ ¯
e ’ a e˙ a o . ˙
’ .
F S v´.i d u.`.ng thˇng l; tu` theo mˆ i Tru.`.ng ho.p 1, 2 hoˇc 4, cˆ t mˆt hoˇc hai
o ¯ o ˙

a y ˜
o o . a
. ´ o
a . a
.
d iˆ’m v`o danh s´ch NewSubj.
¯e ˙ a a
• G´n Subj = NewSubj.
a



3.5.2 Thuˆt to´n Weiler-Atherton
a
. a

Trong mˆt sˆ u.ng dung nhu. khu. bo mˇt khuˆ t hay d anh b´ng mˇt, ch´ng ta cˆn x´c d inh
. ´
o o´ . ˙ ˙ a
’ ’ . a´ ¯´ o a
. u ` a ¯.
a
`
a ˙
’ ¯ a .`.ng ho.p n`y, tiˆn tr` rˆ t ph´.c tap. C´ch tiˆp cˆn
phˆn chung cua hai d a gi´c. Trong tru o a ´
e ınh a ´ u . a ´ .
e a
.
cua Weiler-Atherton nhˇ m t` giao cua hai d a gi´c bˆ t k`, thˆm ch´ cho ph´p c´ lˆ hˆ’ng
˙
’ `
a ım ˙
’ ¯ a a y´ a
. ı e o o o ˜ ˙
a ¯ a a u o e . a `
a .p v` hiˆu cua hai d a gi´c.
trong c´c d a gi´c. Ngo`i ra ta c˜ng c´ thˆ’ tao ra c´c phˆn ho a e ˙
˙ ’ ¯ a
. .

X´t v´ du trong H` 3.15: Hai d a gi´c (S) v` (C) d u.o.c biˆ’u diˆn bo.i c´c danh s´ch
e ı . ınh ¯ a a ¯ . e˙ ˜
e ˙ a
’ a
¯˙’
d ınh, k´ hiˆu Subj = (A, B, C, D, E, A) v` Clip = (a, b, c, d, e, a) tu
y e a .o.ng u.ng. Dˆ’ thuˆn tiˆn,
´ -e˙ a e
. . .
ch´ng ta lu
u .u danh s´ch c´c d ınh sao cho phˆn trong cua v`ng nˇ m vˆ ph´ tay tr´i cua mˆ i
a a ¯˙ ’ `a ˙ u
’ `
a `
e ıa a ˙ ’ ˜
o
e ¯ a u ’. d ınh n`y dˆn d ınh kh´c trong danh s´ch. Chˇng
canh khi di chuyˆ’n xung quanh d a gi´c t` ¯˙
˙ ´ ’
a ¯e ¯ ˙ a a ˙

a
.

111
han, phˆn trong cua (S) nˇ m vˆ bˆn tay tr´i cua canh t`. A dˆn B v` bˆn tr´i cua canh t`.
. `
a ˙
’ `
a ` e
e a ˙ .
’ u ´
¯e a e a ˙ .’ u
´ - ` ´
B dˆn C. Diˆu n`y giˆng nhu
¯e e a o . danh s´ch c´c d ınh d u.o.c lu.u theo th´. tu. ngu.o.c chiˆu kim
a a ¯˙ ’ ¯ . u . `e
.
d` ng hˆ.
¯ˆ
o `
o

Tˆ t ca c´c giao d iˆ’m cua hai d a gi´c d u.o.c x´c d .nh v` lu.u trong mˆt danh s´ch.
´ ’
a ˙ a ¯e ˙ ˙
’ ¯ a ¯ . a ¯i a o
. a
Chˇng han, trong v´ du n`y, c´ s´u giao d iˆ’m. Bˆy gi`
˙

a ı . a o a ¯e ˙ a o . ta cˇt (S) v´.i d a gi´c (C) bˇ ng
´
a o ¯ a `
a
.
c´ch lˆn theo “hu.´.ng thuˆn” (t´.c l`, sao cho phˆn trong cua n´ nˇ m bˆn tr´i) cho dˆn khi
a ` a o a
. u a `
a ˙ o `
’ a e a ´
¯e
gˇp giao d iˆ’m “d i v`o”: l` d iˆ’m giao m` d i theo danh s´ch Subj s˜ di chuyˆ’n t`. ph´ ngo`i
a
. ¯e ˙ ¯ a a ¯e ˙ a¯ a e ˙
e u ıa a
v`o ph´ trong cua d a gi´c Clip. Trong tru.`.ng ho.p n`y l` 1, v` xuˆ t ra danh s´ch lu.u tr˜.
a ıa ˙ ¯
’ a o . a a a a ´ a u
o a ¯ a ¯ .o.c cˇt.
thˆng tin (c´c) d a gi´c d u . a ´

A E
..............................................................................................
. .............................................................................................
..
.
.
. .
.
.
.
.
. .
.
.
. .
.
.
. .
.
.
.
. .
.
.
.
.
. .
.
.
. .
.
.
. .
.
.
.
. .
.
.
.
.
.
.
.
.
.
.
.
.
C .
.
.
.
.
.
.
.
.
. .
...... .
.
.
. .. ..... .
.
.
.
. ..
.. ..... ... .
.
.
..
.
.
.
.
.
.
.
.
1 ..
2
..
..
..
...
...
...
...
.. 3 6.
.
.
.
.
.
.
a .
.
.
.
.
. .
.
.
.
..
..
..
.
. ..
...........................................................................................................................
.............................................. .....................................................................................................
. .......................... .. ..
...
...
...
...
.
.
.
.
.
. ...
...
.
..
... e
.
.
.
.
.
. ..
.. ...
... .
.
. ...
...
.
.
.
.
.
. ..
..
...
... .
.
. ...
...
.
. .
. ..
. ...
... .
. ...
..
.
. . .. ... . ..
...
...
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. ...
.
. ...
. .
..
..
..
...
...
...
...
...
...
...
.
.
.
.
.
.
.
.
.
..
..
..
..
..
d
.
.
.
.
. . ...
.
. ..
...
...
...
.
.
.
. ..
..
.
. ..
..
. ...
... .
. ..
.
.
. ..
. ... .
. ..
.
. . ...
... .
. ..
..
.
. ...
... .
. ..
.
.
. ... .
.
. ..
.
.
.
.
.
.
.
.
B ...
...
...
...
...4
...
.....................................................................................................................................................
5.
.
.
.
.
.
.
..
..
..
..

b
.
. ........................................................................................................................
. .. .
.
...
...
...
...
............................
.
.
.
.
.
.
.
.. c
...
... . .
... .
... . .
... ..
... .
...
..

D

ınh ´
H` 3.15: Cˇt x´n Weiler-Atherton.
a e

Tiˆn tr` bˆy gi`. d o.n gian khi ph´t biˆ’u dang h` hoc: Duyˆt doc theo Subj, di
´
e ınh a o ¯ ˙
’ a e˙ . ınh . e .
.
chuyˆ e˙n theo t`.ng d oan, cho dˆn khi gˇp mˆt giao d iˆ’m (2 trong v´ du n`y). Kˆ tiˆp ta di
’ u ¯ . ´
¯e a
. o
. ¯e ˙ ı . a ´ ´
e e
chuyˆ’n v` lˆn theo Clip thay cho Subj. C´ hai c´ch di chuyˆ’n trˆn Clip. Di chuyˆ’n trˆn
˙
e a ` a o a e˙ e e˙ e
Clip theo hu.´.ng thuˆn cua n´. Nhu. vˆy phˆn trong cua d a gi´c Subj v` Clip luˆn luˆn nˇ m
o a ˙ o
. ’ a. `
a ˙ ¯
’ a a o o a `
bˆn tay tr´i trong qu´ tr` di chuyˆ’n. Khi gˇp mˆt giao d iˆ’m, ta chuyˆ’n sang Subj theo
e a a ınh e˙ a
. o
. ¯e ˙ e˙
hu.´.ng thuˆn cua n´ v` vˆn vˆn. Mˆ i d ınh hay giao d iˆ’m bˇt gˇp d u.o.c d at v`o danh s´ch.
o a ˙ o a a a
. ’ ˜ ’
o ¯˙ ¯e ˙ ´ .
a a ¯ . ¯ˇ a . a
Lˇp lai tiˆn tr` “di chuyˆ’n theo hu o
a . e ´ ınh e˙ .´.ng thuˆn v` nhay gi˜.a hai d a gi´c” cho dˆn khi gˇp
a a ˙’ u ¯ a ¯e´ a
. . .
¯˙’ ´ ´ ´
d ınh xuˆ t ph´t. Danh s´ch xuˆ t ra dˆn l´c n`y l` (1, B, 2, 1).
a a a a ¯e u a a

Tiˆp tuc kiˆ’m tra giao d iˆ’m v`o kˆ tiˆp cua Subj chu.a d u.o.c d i qua. Ta c´ giao d iˆ’m
´
e . e˙ ¯e ˙ a e e´ ´ ˙ ’ ¯ . ¯ o ¯e ˙
3 v` lˇp lai tiˆn tr` trˆn, danh s´ch sinh ra l` (3, 4, 5, 6, 3). Kiˆ’m tra thˆm, khˆng c`n giao
a a . e
. ´ ınh e a a e˙ e o o
d iˆ’m v`o cua Subj n`o chu ¯ .
¯e ˙ a ˙ ’ a .a d u.o.c viˆng thˇm, nˆn tiˆn tr` cˇt kˆt th´c. Ta c´ hai d a
´
e a e ´
e ´ ´
ınh a e u o ¯
a ¯ .o.c sinh ra (1, B, 2, 1) v` (3, 4, 5, 6, 3).
gi´c d u . a

Mˆt c´ch sˇp xˆp h˜.u hiˆu dˆ’ thu.c hiˆn tiˆn tr` “lˆn theo hu.´.ng thuˆn v` nhay”
o a
. ´ ´
a e u ˙
e ¯e .
. e
. ´
e ınh `
a o a a
. ˙



112
l` xˆy du.ng hai danh s´ch
a a . a

Subj: (A, 1, B, 2, C, 3, 4, D, 5, 6, E, A)

Clip: (a, b, 4, 5, c, d, e, 6, 3, 2, 1, a).

dˆ’ lˆn theo mˆ i d a gi´c (sao cho phˆn trong cua n´ bˆn tay tr´i) v` danh s´ch c´c d ınh v`
˙ a
¯e ` ˜
o ¯ a `
a ˙ o e
’ a a a a ¯˙’ a
c´c d iˆ’m giao d u .
a ¯e ˙ ¯ .o.c lu.u theo th´. tu. ch´ng bˇt gˇp. (Diˆu g` xay ra nˆu khˆng c´ giao d iˆ’m
u . u ´ .
a a - ` ı ˙
e ’ ´
e o o ¯e ˙
gi˜.a hai canh cua hai d a gi´c?). Nhu. vˆy viˆc lˆn theo d a gi´c tu.o.ng u.ng duyˆt danh s´ch
u . ˙
’ ¯ a a
. e `
. a ¯ a ´ e
. a
a ˙

v` nhay gi˜ u.a hai d a gi´c tu.o.ng u.ng nhay gi˜.a hai danh s´ch.
¯ a ´ ˙
’ u a

Ch´ y rˇ ng ngay khi danh s´ch d u.o.c xˆy du.ng, c´ rˆ t ´ thˆng tin h` hoc trong
u ´ `a a ¯ . a . ´
o a ıt o ınh .
d ´-nhu
¯o . kh´ c´ thˆ’ kiˆ’m tra “d iˆ’m nˇ m ngo`i d a gi´c” dˆ’ x´c d inh ch´ x´c d ınh v`o.
o o e e ˙ ˙ ¯e ˙ `
a a ¯ ˙
a ¯e a ¯. ınh a ¯˙ ’ a
Hu.´.ng thu.c su. dˆ’ di chuyˆ’n d oi v´.i mˆ i d a gi´c d u.o.c nh´ng trong th´. tu. cua danh s´ch.
o . . ¯e ˙ ˙ ´
e ¯ˆ o o ¯ ˜ a ¯ . u u . ˙ ’ a
Trong v´ du tru o
ı . .´.c, tiˆn tr` di chuyˆ’n trong thuˆt to´n d u.o.c cho bo.i H` 3.16.
´
e ınh e˙ a a ¯ . ˙
’ ınh
.

´
Xuˆ t ph´t
a a Xuˆ t´
a ph´t lai a .
| |
Subj: A 1n B 2 C 3n 4 D 5 6 E A
◦ •.....................................•.....................................•...............................◦
.
. ..
.. ..
.. •......................................................•
..
. ..
. ◦ ...............................•................................................•
...
.. ..
..
. ◦ ◦
.....
..... .... .. ..
.....
..... .... . ...
.....
..
...
...
.
..... .......
..... ....... .....
..... ...
.....
... .....
.... ...
..
. .. . .........
.... .......... ....
.... ...
...
....
.... ..... ........
..... ....... ...
...
...
....
. ..
.
.... .............
............ ...
...
....
.... .....
..... .....
..... ...
...
....
.... ... .
..... .....
..... ...
...
....
.... . ...
..... .....
.....
..... .....
......
.... .....
..... ..... ...
..
....
.... ........
... .......
......
....
.... .... .... ......
..
... ..........
.. .
.... .....
..... ... .....
....
..... ...
... .....
....
.... ....
.... ....
.......... .
..... .
............... ..........
.. . ...
◦ ◦ •....
... .
.
.
.•
.........................
....
◦ ◦ ◦ ..
.. .. •
...................
... .............. .
..
.. • • • ◦
......
.......................
... ..................
. .
.
.
.


Clip: a b 4 5 c d e 6 3 2 1 a
| |
D˜ d u.o.c viˆng thˇm
-a ¯ . ´
e a
• = d iˆ’m d u.o.c xuˆ t ra
˙
¯e ¯ . ´
a

H` 3.16: Ap dung phu.o.ng ph´p Weiler-Atherton.
ınh ´ . a



Cuˆi c`ng, dˆ’ ho`n thiˆn thuˆt to´n, ch´ng ta cˆn kiˆ’m tra nh˜.ng tru.`.ng ho.p c´c
´
o u ˙
¯e a e
. a
. a u `a e˙ u o . a
˙
’ ’ ´
˙ a e `
canh cua Clip v` Subj song song hay phu lˆ p lˆn nhau mˆt phˆn.
. a o
. a




3.5.3 C´c ph´p to´n tˆp ho.p trˆn c´c d gi´c
a e a a . . e a ¯a a

Phˆn trˆn ta d ˜ x´t b`i to´n x´c d inh giao cua hai d a gi´c. Phu.o.ng ph´p tr` b`y n`y
`
a e ¯a e a a a ¯. ˙
’ ¯ a a ınh a a
c˜ng c´ thˆ’ ´p dung dˆ’ t` hiˆu v` ho
u o ea ˙ ˙
¯e ım e a . .p cua hai d a gi´c.
˙
’ ¯ a
. .

113
1. Ho.p cua hai d a gi´c (S) v` (C). Di trˆn danh s´ch Subj theo hu.´.ng thuˆn cho dˆn
. ˙
’ ¯ a a - e a o a
. ´
¯e
khi gˇp giao “d iˆ’m ra”: l` d iˆ’m m` d i theo canh cua (S) s˜ di chuyˆ’n t` `
a ¯e˙ a ¯e ˙ a ¯ ˙
’ e ˙
e u a . phˆn trong
. .
ra phˆn ngo`i cua (C). Xuˆ t giao d iˆ’m n`y v` duyˆt theo Subj cho dˆn khi gˇp giao
`
a a ˙’ a´ ¯e ˙ a a e
. ¯e ´ a
.
d iˆ
¯e ˙m kh´c v´.i Clip. Nhay sang danh s´ch Clip v` d i theo hu.´.ng thuˆn cua n´ cho
’ a o ˙
’ a a ¯ o a. ˙
’ o
dˆn khi gˇp giao d iˆ’m kˆ tiˆp; xuˆ t c´c d ınh trong qu´ tr` d i ngang qua v` nhay
¯e´ a
. ¯e˙ ´ ´
e e ´
a a ¯˙ ’ a ınh ¯ a ˙

sang danh s´ch Subj rˆi d i theo hu.´.ng thuˆn. Qu´ tr` kˆt th´c khi gˇp d ınh xuˆ t
a ` ¯
o o a. a ınh e´ u a ¯˙
. ’ a´
ph´t ban d` u; t` giao d iˆ’m ra kˆ tiˆp chu.a d u.o.c viˆng thˇm v` lˇp lai tiˆn tr`
a ¯ˆ
a ım ¯e ˙ ´ ´
e e ¯ . ´
e a a a . e
. ´ ınh
trˆn.
e

2. Hiˆu cua hai d a gi´c (S) v` (C). Di trˆn danh s´ch Subj theo hu.´.ng thuˆn cho dˆn
e
. ˙
’ ¯ a a - e a o a
. ´
¯e
khi gˇp giao d iˆ’m v`o. Nhay sang danh s´ch Clip v` d i theo hu.´.ng ngu.o.c (do d ´
a
. ¯e ˙ a ˙
’ a a ¯ o . ¯o
phˆn trong d a gi´c (C) nˇ m bˆn tay phai trong hu.´.ng di chuyˆ’n) cho dˆn khi gˇp
`a ¯ a `
a e ˙’ o e˙ ´
¯e a
.
¯e ˙’ ˜
o .´.c lˇp, ta luˆn luˆn di chuyˆ’n trˆn Subj
giao d iˆ’m, nhay sang Subj. Trong mˆ i bu o a
˙ o o e˙ e
.
theo hu.´.ng thuˆn v` di chuyˆ’n trˆn Clip theo hu.´.ng ngu.o.c.
o a a
. e˙ e o .


V´.i hai d a gi´c (S) v` (C) trong H` 3.15, ´p dung c´c phu.o.ng ph´p trˆn dˆ d`ng
o ¯ a a ınh a . a a e ˜ a
e

o


(S) ∪ (C) :

(2, C, 3, 2) (lˆ hˆ’ng).
˜ ˙
o o
(4, D, 5, c, d, e, 6, E, A, 1, a, b, 4).

(S) \ (C) :

(1, B, 2, 3, 4, b, a, 1); v`
a
(5, 6, e, d, c, 5).

(C) \ (S) :

(4, 5, D, 4); v`
a
(6, 3, C, 2, 1, A, E, 6).



3.6 ` ˙
’ `
Ray tracing hai chiˆu: phan xa trong buˆng k´
e . o ın

Muc d´ cua phˆn n`y l` ´p dung mˆt sˆ kh´i niˆm h` hoc dˆ’ tao mˆt u.ng dung d` hoa:
. ¯ıch ˙ ’ ` a aa
a . . ´
o o a e . ınh . ¯e .˙ o ´
. . ¯ˆ .
o
mˆ phong qu´ tr` chuyˆ’n d ong cua tia s´ng trong buˆng k´
o ˙’ a ınh ˙
e ¯ˆ . ˙
’ a `o ın.


114
Phu.o.ng ph´p ray tracing l` mˆt cˆng cu quan trong trong d` hoa m´y t´ dˆ’ tˆ’ng
a a o o
. . . ¯ˆ .
o a ınh ¯e o ˙ ˙
.p c´c anh. Trong tˆ’ng ho.p anh, c´c tia s´ng (nhˆn tao) “lˆn theo” trong thˆ gi´.i thu.c
ho a ˙ ’ ˙ ` ´
. o . ˙ ’ a a a . a e o .
`
ba chiˆu ch´
e u.a nhiˆu d ˆi tu.o.ng. Du.`.ng d i cua mˆ i tia s´ng xuyˆn qua c´c d ˆi tu.o.ng trong
` ¯o
e ´ - o ¯ ˙ ’ ˜
o a e ´
a ¯o
. .
suˆo´t hoˇc phan xa lai t`y theo m´.c d ˆ phan xa cua d oi tu.o.ng cho dˆn khi n´ d`.ng o. d ˆi
a
. ˙’ . . u u ¯o . ˙
’ . ´
˙ ¯ˆ
’ . ´
¯e o u ’ ´
˙ ¯o
tu.o.ng n`o d o. M`u cua d ˆi tu.o.ng n`y sau d ´ s˜ d u.o.c d ˇt cho pixel tu.o.ng u.ng trˆn thiˆt
. a ¯´ a ˙ ¯o
’ ´ . a ¯o e ¯ . ¯a . ´ e ´
e
bi hiˆ’n thi. Mˆ phong qu´ tr` ray tracing rˆ t dˆ d`ng trong hai chiˆu.
. e ˙ . o ˙
’ a ınh a ˜ a
´ e `
e

H` dung qu˜ d ao cua tr´i “pinball” nho khi n´ va cham v`o c´c d oi tu.o.ng trong
ınh y ¯. ˙
’ a ˙
’ o . a a ¯ˆ ´ .
“buˆ ` ng k´
o ın”. H` 3.17 minh hoa nh´t cˇ
ınh . a a´t ngang cua mˆt buˆng k´ c´ nˇm b´.c tu.`.ng v`
˙
’ o
. `
o ın o a u o a
ch´u.a ba “tru tr`n”. Tr´i pinball bˇt d` u tai vi tr´ S v` di chuyˆ’n theo hu.´.ng vector c cho
´ a ˙
. o a a ¯ˆ . . ı a e o
dˆn khi gˇp vˆt can s˜ bi dˆi lai v` di chuyˆ’n theo hu.´.ng m´.i. Qu´ tr` d u.o.c lˇp lai. Qu˜
¯e´ a a ˙ e . o . a
. . ’ . e˙ o o a ınh ¯ . a .. y
¯. ˙

d ao cua tr´i pinball l` mˆt d u o
a a o ¯ .`.ng gˆ p kh´c m` ta c´ thˆ’ h` dung ch´ l` d u.`.ng d i cua
´
a u a ˙
o e ınh ınh a ¯ o ¯ ˙

.
tia s´ng khi n´ di chuyˆ’n trong buˆng k´
a o e˙ `
o ın.

..................................................................................................
. .................................................................................................
.
.
.
.
.
.
.
.
.
.
 ...
...
...
...
...
...
.
. ...
...
.
.
. ...
...
.
.
. ...
...
.
.
. ...
...
.
.
.
.
.
.
.
 ...
...
...
...
...
.
.
.
.
.
.
.
 ...
...
...
...
...
.
.
. ...
...
.
. ..
.
. ...
...
.
. ...
...
.
.
.
.
.
.
.
.
 ...
.
.
...
. ...
...
.
.
.
.
.
.
.
.
.
.
t
...............
.............
..
. c ...
...
...
...
...
...
.
.
. ...
...
...
.
.
.
.
.
.
.
S ...
...
...
...
...
.
....
.
.
. ...
...
.
. ......
.
.
. .....
.
. ...
...
.
. ...
...
. ...
...
.
.
.
.
.
.
.
i .
....
...
...
...
.
. ...
...
.
.
... ...
...
... ...
...
...
... ...
...
...
... .....
...
...
... ...
...
...
... ...
...
...
... ...
...
...
... ...
...
...
... .....
...
...
... ...
...
...
... ...
...
...
... ...
...
... ...
...
...
...
... ..
....
...
... .....
... .....
.....
....




ınh ı . `
H` 3.17: V´ du vˆ ray tracing.
e

Ch´ng ta cˆn xˆy du.ng thuˆt to´n x´c d inh d oi tu.o.ng n`o tia s´ng s˜ gˇp d` u tiˆn
u `
a a . a. a a ¯. ´
¯ˆ . a a e a ¯ˆ
. a e
a . ı .i d` u cho d u.`.ng d i kˆ tiˆp v` ch´ng
v` vi tr´ va cham tai d o. Vi tr´ va cham s˜ l` d iˆ’m kho ¯a
˙ ˙ ˆ
’ ´ ´
. . ¯´ . ı . e a ¯e ¯ o ¯ e e a u
ta c´ thˆ’ t` hu.´.ng di chuyˆ’n m´.i cua tia s´ng bˇ ng c´ch ´p dung nh˜.ng k˜ thuˆt trong
˙
o e ım o e˙ o ˙ ’ a `
a a a . u y a
.
` .´.i d ay.
Phˆn 3.6.1 du o ¯ˆ
a



3.6.1 ˙

Vector pha n xa
.

Trong thu.c tˆ ta thu.`.ng nghiˆn c´.u su. phan xa cua c´c d ˆi tu.o.ng khi va cham v`o nhau
. e ´ o e u . ˙
’ . ˙ a ¯o
’ ´ . . a
a e ˙ . u - `
v` hiˆ’n thi ch´ng. Diˆu n`y d ac biˆt quan trong trong mˆ h` phan xa ´nh s´ng cua bˆ
e a ¯ˇ . e
. . o ınh ˙
’ . a a ˙ `
’ e
mˇt hoˇc trong viˆc nghiˆn c´
a a e e u .u qu´ tr` chuyˆ’n d ong cua c´c phˆn tu. gas hay cua c´c qua
a ınh ˙ .
e ¯ˆ ˙ a
’ a ˙ ’ ˙ a
’ ˙’
. . .

115
..
.....
....
.. .
......
... .
... ... .
...
... .
...
... .
.
.
.. ...
... .
.
u ...
...
.
.
.
...
...
. ...
...
.
z .
.
.
.
.
.
.
.
.
.. .
..
. ...
... .
.
.
.....
... .
.
.
. ...
... .
.
.
.. .
... .
...........
.. . .
.. θ
.
....
.....
. .
.
.
.
.
.
........................................................................................... .
.
.................................. ................................................. .
.. ..
. .
.
..
.

w v
H` 3.18: Phˆn giai mˆt vector th`nh hai vector tru.c giao.
ınh a ˙
’ o . a .

b´ng billiard.
o

Quang h` hoc d a chı ra rˇ ng, g´c phan xa bˇ ng g´c t´.i. Ch´ng ta s˜ su. dung c´c
ınh . ¯˜ ˙ ’ `
a o ˙
’ . ` a o o u e ˙ .’ a
vector v` c´c ph´p chiˆu dˆ’ x´c d .nh hu o
a a e ´ ˙
e ¯e a ¯i .´.ng phan xa. C´c kˆt qua n`y, d u.o.c tr` b`y
˙
’ a e ´ ˙ a ¯ .
’ ınh a
.
trong hai chiˆu, c´ thˆ’ dˆ d`ng mo. rˆng lˆn ba chiˆu.
`e ˙ e
o e ˜ a ˙ o
’ . e `
e

Tru.´.c hˆt ch´ng ta phˆn giai mˆt vector (th´. nhˆ t) th`nh hai th`nh phˆn: mˆt th`nh
o e ´ u a ˙ o
’ . u a´ a a `
a o
. a
phˆn theo hu.´.ng cua vector (th´. hai) cho tru.´.c v` mˆt th`nh phˆn vuˆng g´c v´.i vector
`
a o ˙
’ u o a o . a `a o o o
th´u. hai. B`i to´n n`y c´ liˆn quan mˆt thiˆt dˆn phˆn t´ lu.c hˆ p dˆn trong vˆt l´. Trong
a a a o e a ´ ´
e ¯e ´ ˜
a ıch . a a a y
. .
H` 3.18 vector u d u .
ınh ¯ .o.c phˆn giai th`nh mˆt th`nh phˆn w (goi l` ph´p chiˆu tru.c giao
a ˙
’ a o a `
a ´
. . a e e .
˙

cua u lˆn v) doc theo vector v cho tru o a o
e .´.c v` mˆt vector z vuˆng g´c v´.i v. Ta c´ z = u − w.
o o o o
. .
V` vˆy chı cˆn x´c d .nh vector w t`. u v` v. Hiˆ’n nhiˆn vector w c`ng hu.´.ng v´.i vector v
ı a . ˙ `
’ a a ¯i u a e˙ e u o o
nhu .ng kh´c d o d`i. Ho.n n˜.a
a ¯ˆ a u
.
w = u cos(θ)
u,v
= u u v
v
= u, v
.
v
Mˇt kh´c, w = w
a
. a v
. Vˆy
a
.
u, v
w= v.
v 2

Dˆ d`ng kiˆ’m tra rˇ ng vector z vuˆng g´c v´.i vector v, v` z
˜ a
e e˙ `
a o o o a 2
= u 2
− w 2.

Bˆy gi`. ´p dung nh˜.ng kˆt qua trˆn dˆ’ x´c d .nh vector phan xa. X´t tia theo hu.´.ng
a oa . u ´
e ˙
˙ e ¯e a ¯i
’ ˙
’ . e o
vector chı phu.o.ng c gˇp d u.`.ng thˇng l v` phan xa lai theo hu.´.ng r (xem H` 3.19(a)).
˙
’ a ¯ o
. ˙

a a ˙
’ . . o ınh
˙ ¯

K´ hiˆu n l` ph´p vector cua d u o
y e a a .`.ng thˇng l. Khi d o, g´c ho.p bo.i gi˜.a hai vector c v` n
˙

a ¯´ o ˙
’ u a
. .
bˇ ng g´c ho.p bo.i gi˜.a hai vector r v` n (bˇ ng θ).
`
a o . ˙
’ u a `
a

ınh a ˙
’ a a `a . a a `
H` 3.19(b) phˆn giai vector c th`nh th`nh phˆn m doc theo n v` th`nh phˆn e vuˆng
a o
g´c v´
o o .i n. Do t´ d ˆi x´.ng, r c´ c`ng th`nh phˆn e vuˆng g´c v´.i n nhu.ng c´ th`nh phˆn
´
ınh ¯o u o u a `
a o o o o a `
a
.o.c lai doc theo n, do d o r = e − m. Nhu.ng e = c − m nˆn r = c − 2m. V` vector m l`
ngu . . . ¯´ e ı a


116
n
...
... .
. ....
....
.
...
... ..
..
... ..
...
...
... .
. ...
...
...
... .
. ...
...
...
... .
.
. ...
...
...
... .
. .....
...

(a)
...
...
...
c
...
...
...
...
...
.
.
.
.
.
.
.
r ...
...
...
...
...
...
.

...
... .
.
. ...
...
...
... .
. ...
...
...
..
...
θ θ
...
...
...
.
.
.
.
... ........ .....
... ......... .....
. . .
.
..... . ....
... . . ..
...
...
.... . ...
.
.... . ...
l/ ...............................................................................................................................
..............................................................................................................................
/ / / / /
.....
.. .
/ / / / /



n
...
. . .....
....
. ...
. ... ..
..
. . ...
..
......
. ..
. ... ...
.
. ... ..
... .....
.
. ...
... .
. ...
... .
.
.
. ...
... . ...
... .
.
.
. ...
...
...
.
.
. .. ...
... .
.
.

(b) m .
.
.
.
.
.
.
.
.
.
...
...
c
...
...
...
...
...
...
.
.
.
.
.
.
.
.
.
r .
..
...
...
.
.
...
...
. ...
...
−m .
.
.
.
.
.
.
.
.
. ... . .
... .
.
. ...
...
...
.
. ..... .
.
.
.
.
. ...
...
.
.
. .. ...
... .
.
.
.
. ...
... .
.
. .....
... .
.
.
.
.
.. ...
... . .....
.
... . .....
... . . ..
.
.
.
...
...
.
. ........
... . ... .
.
.
l .
........................................................................................................... ..................
...............................................................................................................................
....
. .
........................................... ...........................................
........................................... ...........................................
..
..
. ..
..
.

e e
H` 3.19: Phan xa cua tia t`. mˇt.
ınh ˙
’ . ˙’ u a .

a `
a a ˙ ˙
’ ’
th`nh phˆn trong phˆn giai cua vector c theo vector n nˆn
e
c, n
m= n.
n 2
Suy ra
c, n
r =c−2 n.
n 2
Thu tuc sau x´c d .nh vector phan xa r t`. vector c v` ph´p vector n :
˙ .
’ a ¯i ˙
’ . u a a


void Reflection(Vector2D c, Vector2D n, Vector2D *r)
{
float Coeff = 2*Dot2D(c, n)/Dot2D(n, n);


(*r).dx = c.dx - Coeff*n.dx;
(*r).dy = c.dy - Coeff*n.dy;
}



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

a

Trong u.ng dung cua ch´ng ta, tia s´ng s˜ va cham v`o hai d ˆi tu.o.ng: c´c tru tr`n (d u.o.c
´ . ˙
’ u a e . a ¯o´ . a . o ¯ .
o ınh ˙ ’.i c´c h` tr`n) v` c´c b´.c tu.`.ng (d u.o.c biˆ’u diˆn bo.i c´c d u.`.ng thˇng). Dˆ’
mˆ h` bo a ınh o a a u o ¯ . e˙ ˜
e ˙ a ¯ o
’ ˙

a -e˙


117
d o.n gian ch´ng ta s˜ gia thiˆt buˆng k´ l` d a gi´c lˆi. Khi d o, d a gi´c s˜ l` giao cua c´c
¯ ˙’ u e ˙ ’ e´ `
o ın a ¯ a ` o ¯´ ¯ a e a ˙ a

nu˙
’.a mˇt phˇng ngo`i v` d u.o.c mˆ h` ho´ bo.i ho c´c d u.`.ng thˇng nhu. d ˜ tr` b`y trong
a ˙

a a a¯ . o ınh a ˙ . a ¯ o
’ ˙

a ¯a ınh a
.
`
Phˆn 3.4.
a

V´.i buˆng k´ d ˜ d u.o.c d inh ngh˜ kˆ tiˆp ch´ng ta cˆn x´c d .nh vi tr´ giao cua tia
o `
o ın ¯a ¯ . ¯. ´ ´
ıa, e e u `a a ¯i . ı ˙

s´ng v´.i b´.c tu.`.ng. Phu.o.ng tr` tham sˆ cua tia s´ng xuˆ t ph´t t`. d iˆ’m S chuyˆ’n d ˆng
a o u o ınh ´ ’
o ˙ a ´
a a u ¯e ˙ ˙
e ¯o .
theo vector chı ˙ phu.o.ng c cho bo.i
’ ˙


R(t) := S + ct, t ≥ 0.

B´.c tu.`.ng tu.o.ng u.ng d u.`.ng thˇng
u o ´ ¯ o ˙

a
−→
l := {P ∈ R2 | n, OP = D},

trong d ´ ph´p vector n cua d u.`.ng thˇng l d u.o.c chon hu.´.ng ra ngo`i buˆng k´
¯o a ˙ ¯ o
’ ˙

a ¯ . . o a `
o ın.

Nˆu n, c = 0 th` d u.`.ng thˇng, k´ hiˆu α, d i qua S c´ vector chı phu.o.ng c cˇt d u.`.ng
´
e ı¯ o ˙

a y e
. ¯ o ˙
’ ´
a ¯ o
thˇng l tai d iˆ’m Ph = S + cth , trong d ´
˙

a . ¯e ˙ ¯o
−→
D − n, OS
th = .
n, c

Dˆ d`ng thˆ y rˇ ng, th ≥ 0 nˆu v` chı nˆu tia s´ng R(t) cˇt b´.c tu.`.ng l tai Ph . Ngu.o.c lai,
˜ a
e a `
´ a ´
e a ˙ e ’ ´ a ´
a u o . . .

e´u n, c = 0 th` d u.`.ng thˇng α (v` do d o tia s´ng) s˜ song song v´.i d u.`.ng thˇng l. Trong
ı¯ o ˙

a a ¯´ a e o ¯ o ˙

a
.`.ng ho.p n`y ta g´n t l` mˆt gi´ tri ˆm n`o d ´, chˇng han −1.
tru o a a h a o a .a a ¯o ˙
a’
. . .


V´ du 3.6.1 Cho d u.`.ng thˇng c´ phu.o.ng tr` 6x − 8y + 10 = 0 v` tia s´ng xuˆ t ph´t
ı . ¯ o ˙

a o ınh a a ´
a a
t`
u. S(7, 4) di chuyˆ’n theo vector chı phu.o.ng c = (−2, 1)t . Du.`.ng thˇng c´ ph´p vector
e˙ ˙
’ - o a˙
’ o a
a a` ´
n = (6, −8)t v` hˇ ng sˆ D = −10. Ta c´
o o
−→
D − n, OS
th =
n, c
−10 − (42 − 32)
= = 1.
(−12 − 8)

Suy ra giao d iˆ’m I cua tia v` d u.`.ng thˇng x´c d .nh bo.i
¯e ˙ ˙
’ a ¯ o ˙

a a ¯i ˙


I = S + th c = (7, 4) + (−2, 1) = (5, 5).

˙

Vector phan xa
.
n, c
r = c−2 n
n 2

118
−2 −20 6
= −2
1 100 −8
1 2
= .
5 −11


V´ du 3.6.2 Gia su. d u.`.ng thˇng l c´ ph´p vector n = (−1, 4)t v` hˇ ng sˆ D = 5. X´t tia
ı . ˙ ˙ ¯ o
’ ’ a˙
’ o a a `
a ´
o e
´
s´ng xuˆ t ph´t t`
a a a u . S(1, −2) di chuyˆ’n theo vector chı phu.o.ng c = (−1, 1)t . V` n, c = 5 = 0
e˙ ˙
’ ı
nˆn th`.i d iˆ’m giao x´c d .nh bo.i
e o ¯e ˙ a ¯i ˙’
−→
D − n, OS 5 − (−9) 14
th = = = .
n, c 5 5

Do th > 0 nˆn tia s´ng s˜ giao v´.i d u.`.ng thˇng l tai d iˆ’m Ph x´c d .nh bo.i
e a e o ¯ o ˙

a . ¯e ˙ a ¯i ˙


14 −9 4
Ph = S + th c = (1, −2) + (−1, 1) = , .
5 5 5

T`. d o c´ vector phan xa
u ¯´ o ˙
’ .
7
n, c −1 10 −1 − 17
r =c−2 n= − = .
n 2 1 17 4 − 23
17



C´c kˆt qua d u.o.c tˆ’ng kˆt trong thu tuc x´c d .nh th`.i d iˆ’m giao th nhu. sau:
a e ´ ˙ ¯ . o
’ ˙ ´
e ˙ . a ¯i
’ o ¯e ˙


void Ray_With_Line(Point2D S, Vector2D c, Vector2D normal,
float D, float *t_hit)
{
float Denom = Dot2D(normal, c);
Vector2D s;


PointToVector2D(S, &s);
if (Denom == 0.0) *t_hit = -1.0;
else
*t_hit = (D - Dot2D(normal, s))/Denom;
}


Khi tia s´ng song song v´.i d u.`.ng thˇng, Denom = 0, thu tuc thˆng b´o cho ta biˆt
a o ¯ o ˙

a ˙ .
’ o a e´
bˇ ng c´ch g´n t hit l` mˆt gi´ tri “khˆng thˆ’” xay ra. Bˆ t k` mˆt gi´ tri ˆm l` khˆng thˆ’
`
a a a a o a .
. o ˙ ’
e ˙ ´
a y o a .a a o
. e˙
ı a ´ ˆ
v` tia s´ng bˇt d` u h`nh tr` cua n´ tai th` ¯ e
a ¯a a ınh ˙ o .
’ o.i d iˆ’m xuˆ t ph´t t = 0.
˙ ´
a a


119
.
.
.
.
.
.
.
.
.
. .
....
...
..
. ............
.............
l4 .
.
.
.
.
..
...
....
...
....
.... .....
..... . . .
. ...
....
.... ..... . ...
...
...
....
...
.....
.....
.....
.....
..... t4 • ..
....
...

l5 ....
....
....
....
......
.... .....
.....
..... ..

..... ..
.....
.....
... .
... .
..... . .
.
t3
...
... ....
... ..... .
....
.... ....
...
..
...
......
.... ..
.
..
. ....
.... ....
... .
.
.
.
....
.... ....
... .
.
....
.... ....
.. ..
.
....
... .
...
... ....
..
.
.
.....
.... ..
.
....
.
.... ....
... ..
.
....
.... ....
... .
.
...
... ...
.... .
.
....
.... ...
.... ..
....
.... ... .
....
.
.
.
. ..
....
..
.
..
....
....
.
....
....
.
c .
.
.
.
.
..
..
.
..
. S ....
....
....
....
...
...
.
.
.
.
.
.
.
.
..
..
. •
....
....
..
..
.
.
.
.
.