Giáo trình Đồ họa máy tính - Chương 4, Phần 1: Hiển thị đối tượng hai chiều
CHÖÔNG 4
HIEÅN THÒ ÑOÁI TÖÔÏNG HAI CHIEÀU
Chöông naøy seõ ñeà caäp tôùi caùc kó thuaät ñeå hieån thò caùc ñoái töôïng hai chieàu
treân caùc thieát bò nhö maøn hình, maùy in, …
Caùc heä ñoà hoïa cho pheùp ngöôøi duøng moâ taû caùc hình aûnh baèng heä toïa ñoä
theá giôùi thöïc. Noù coù theå laø baát kì heä toïa ñoä Descartes naøo maø ngöôøi duøng
caûm thaáy thuaän tieän nhaát khi söû duïng. Caùc hình aûnh ñöôïc moâ taû trong heä
toïa ñoä thöïc sau ñoù seõ ñöôïc caùc heä ñoà hoïa aùnh xaï vaøo heä toïa ñoä thieát bò.
Thoâng thöôøng caùc heä ñoà hoïa cho pheùp ngöôøi duøng xaùc ñònh vuøng naøo cuûa
hình aûnh ñöôïc hieån thò vaø noù seõ ñöôïc hieån thò ôû ñaâu treân maøn hình. Ta coù
theå choïn moät vuøng hay moät soá vuøng ñeå hieån thò cuøng moät luùc, caùc vuøng
naøy coù theå ñaët ôû caùc nôi khaùc nhau treân maøn hình hay loàng vaøo nhau. Quaù
trình bieán ñoåi naøy ñoøi hoûi caùc pheùp bieán ñoåi nhö dòch chuyeån, quay, bieán
ñoåi tæ leä; vaø caùc thao taùc loaïi boû caùc vuøng hình aûnh naèm ngoaøi vuøng ñöôïc
ñònh nghóa, ….
1. QUY TRÌNH HIEÅN THÒ ÑOÁI TÖÔÏNG HAI CHIEÀU
1.1. Moät soá khaùi nieäm
Cöûa soå (window) laø moät vuøng ñöôïc choïn ñeå hieån thò trong heä toïa ñoä theá
giôùi thöïc.
Vuøng quan saùt (viewport) laø vuøng ñöôïc choïn treân thieát bò hieån thò ñeå caùc
ñoái töôïng ôû trong cöûa soå aùnh xaï vaøo.
Cöûa soå xaùc ñònh caùi gì ñöôïc thaáy treân thieát bò hieån thò, coøn vuøng quan saùt
xaùc ñònh nôi naøo noù seõ ñöôïc hieån thò.
ÔÛ ñaây chuùng ta neân phaân bieät khaùi nieäm cöûa soå ñöôïc duøng trong phaàn
naøy vôùi khaùi nieäm cöûa soå ñöôïc duøng trong caùc chöông trình öùng duïng treân
caùc heä ñieàu haønh nhö Windows.
Thoâng thöôøng cöûa soå vaø vuøng quan saùt coù daïng hình chöõ nhaät, coù caùc
caïnh song song vôùi caùc truïc toïa ñoä. Tuy nhieân chuùng cuõng coøn coù moät soá
daïng khaùc nhö ña giaùc, hình troøn, …
Quaù trình aùnh xaï moät vuøng ñònh nghóa trong heä toïa ñoä theá giôùi thöïc vaøo
moät vuøng trong heä toïa ñoä thieát bò ñöôïc goïi laø pheùp bieán ñoåi heä quan saùt
(viewing transformation).
Window
Viewport
ywmax
yvmax
yvmin
ywmin
xwmin
xwmax
xvmin
xvmax
Hình 4.1 – Pheùp bieán ñoåi heä quan saùt vôùi cöûa soå vaø vuøng quan saùt coù daïng laø caùc hình chöõ nhaät
Quy trình hieån thò caùc ñoái töôïng trong ñoà hoïa hai chieàu coù theå ñöôïc moâ taû
qua sô ñoà sau :
Tröôùc tieân, caùc ñoái töôïng seõ ñöôïc moâ taû baèng caùc ñoái töôïng ñoà hoïa cô sôû
vaø caùc thuoäc tính cuûa chuùng trong töøng heä toïa ñoä cuïc boä (modeling
coordinates - MC) nhaèm ñôn giaûn hoùa vaø taän duïng caùc ñaëc tröng rieâng cuûa
töøng loaïi. Sau ñoù, chuùng ta seõ duøng caùc pheùp bieán ñoåi heä toïa ñoä ñeå
chuyeån caùc moâ taû töø caùc heä toïa ñoä cuïc boä naøy sang moät heä toïa ñoä theá
giôùi thöïc (world coordinates - WC) duy nhaát chöùa toaøn boä caùc ñoái töôïng thaønh
phaàn. Pheùp chuyeån ñoåi naøy ñöôïc goïi laø pheùp chuyeån ñoåi moâ hình (modeling
coordinates transformation).
Tieáp theo, chuùng ta seõ ñònh moät heä toïa ñoä quan saùt (viewing coordinates - VC),
laø heä toïa ñoä moâ taû vò trí cuûa ngöôøi quan saùt ñoái töôïng. Nhôø vieäc söû duïng
heä toïa ñoä naøy maø cuøng moät moâ taû, caùc ñoái töôïng coù theå ñöôïc quan saùt ôû
nhieàu goùc ñoä vaø vò trí khaùc nhau.
Sau khi chuyeån caùc moâ taû ñoái töôïng töø heä toïa ñoä theá giôùi thöïc sang heä toïa
ñoä quan saùt, chuùng ta seõ ñònh nghóa cöûa soå trong heä toïa ñoä naøy, ñoàng thôøi
ñònh nghóa vuøng quan saùt trong heä toïa ñoä thieát bò chuaån (normalized device
coordinates - NDC) coù toïa ñoä caùc chieàu thay ñoåi trong khoaûng töø 0 ñeán 1.
Sau khi thöïc hieän pheùp aùnh xaï töø cöûa soå sang vuøng quan saùt, taát caû caùc
phaàn cuûa ñoái töôïng naèm ngoaøi vuøng quan saùt seõ bò xeùn (clip) vaø toaøn boä
nhöõng gì naèm trong vuøng quan saùt seõ ñöôïc aùnh xaï sang heä toïa ñoä thieát bò
(device coordinates - DC). Vieäc ñöa ra heä toïa ñoä thieát bò chuaån nhaèm giuùp cho
vieäc töông thích deã daøng vôùi nhieàu loaïi thieát bò hieån thò khaùc nhau.
Chuyeån ñoåi töø heä
toïa ñoä cuïc boä
sang heä toïa ñoä
theá giôùi thöïc
Chuyeån ñoåi töø heä
toïa ñoä theá giôùi thöïc
sang heä toïa ñoä
quan saùt
AÙnh xaï töø heä toïa
ñoä thieát bò
chuaån sang heä
toïa ñoä thieát bò
Chuyeån ñoåi töø heä toïa
ñoä quan saùt sang heä
toïa ñoä thieát bò chuaån
MC
WC
VC
NDC
DC
Hình 4.2 – Quy trình hieån thò ñoái töôïng hai chieàu
Baèng caùch thay ñoåi vò trí cuûa vuøng quan saùt chuùng ta coù theå quan saùt caùc
ñoái töôïng taïi caùc vò trí khaùc nhau treân maøn hình hieån thò, ñoàng thôøi, baèng
caùch thay ñoåi kích thöôùc cuûa vuøng quan saùt, chuùng ta coù theå thay ñoåi kích
thöôùc vaø tính caân xöùng cuûa caùc ñoái töôïng ñöôïc hieån thò. Chuùng ta coù theå
thöïc hieän caùc hieäu öùng thu phoùng baèng caùch aùnh xaï caùc cöûa soå coù kích
thöôùc khaùc nhau vaøo vuøng quan saùt coù kích thöôùc coá ñònh. Khi caùc cöûa soå
ñöôïc thu nhoû, phaàn naèm trong cöûa soå seõ ñöôïc phoùng to giuùp chuùng ta deã
daøng quan saùt caùc chi tieát maø khoâng theå thaáy ñöôïc trong caùc cöûa soå lôùn
hôn.
1.2. Heä toïa ñoä quan saùt vaø heä toïa ñoä thieát bò chuaån
1.2.1. Heä toïa ñoä quan saùt
Ñeå thieát laäp heä toïa ñoä quan saùt, tröôùc tieân ta seõ choïn moät ñieåm P0
x0 , y0
trong heä
toïa ñoä theá giôùi thöïc laøm goác toïa ñoä. Sau ñoù chuùng ta seõ söû duïng moät vector V moâ taû höôùng
quan saùt ñeå ñònh höôùng cho truïc tung yv cuûa heä toïa ñoä. Vector V ñöôïc goïi laø view-up
vector.
Töø V chuùng ta coù theå tính ñöôïc caùc vector ñôn vò v
vx ,vy
vaø u
ux ,uy töông öùng
cho caùc truïc tung yv vaø truïc hoaønh xv cuûa heä toïa ñoä. Caùc vector ñôn vò naøy seõ ñöôïc duøng
ñeå taïo thaønh hai doøng ñaàu tieân cuûa ma traän quay MR ñeå ñöa caùc truïc xv yv truøng vôùi caùc
truïc xw yw cuûa heä truïc toïa ñoä theá giôùi thöïc.
yworld
yworld
yview
y
v
i
e
y0
w
T
xview
x0
xworld
xworld
R
x
v
i
e
w
(a)
(b)
Hình 4.3 – Pheùp bieán ñoåi moät ñieåm töø heä toïa ñoä quan saùt sang heä toïa ñoä thöïc
Ma traän cuûa pheùp chuyeån moät ñieåm trong heä toïa ñoä theá giôùi thöïc sang heä
toïa ñoä quan saùt laø tích cuûa hai ma traän cuûa caùc pheùp bieán ñoåi : pheùp tònh
tieán goác toïa ñoä heä quan saùt veà goác toïa ñoä heä toïa ñoä theá giôùi thöïc, pheùp
quay ñöa caùc truïc cuûa heä toïa ñoä quan saùt truøng vôùi caùc truïc cuûa heä toïa ñoä
theá giôùi thöïc. MWC,VC MT MR
.
1.2.2. Heä toïa ñoä thieát bò chuaån
Do caùch ñònh nghóa cuûa caùc heä toïa ñoä thieát bò khaùc nhau neân moät hình aûnh
hieån thò ñöôïc treân thieát bò naøy chöa chaéc hieån thò chính xaùc treân thieát bò kia.
Chính vì vaäy caàn phaûi xaây döïng heä toïa ñoä thieát bò chuaån ñaïi dieän chung cho
caùc thieát bò ñeå coù theå moâ taû caùc hình aûnh cuûa theá giôùi thöïc maø khoâng
phuï thuoäc vaøo baát cöù thieát bò naøo.
Trong heä toïa ñoä naøy, caùc toïa ñoä x, y seõ ñöôïc gaùn caùc giaù trò trong khoaûng
töø 0 ñeán 1. Nhö vaäy, vuøng khoâng gian cuûa heä toïa ñoä thieát bò chuaån chính laø
hình vuoâng ñôn vò coù goùc traùi döôùi laø (0,0) vaø goùc phaûi treân (1,1).
y
(1,1)
1
1
x
Hình 4.4 – Heä toïa ñoä thieát bò chuaån
1.3. Chuyeån ñoåi töø cöûa soå sang vuøng quan saùt
Pheùp chuyeån ñoåi töø cöûa soå sang vuøng quan saùt bao goàm 3 pheùp bieán ñoåi :
pheùp tònh tieán ñeå dòch chuyeån goùc traùi döôùi veà goác toïa ñoä (hình 4.5a), pheùp
bieán ñoåi tæ leä ñeå chænh kích thöôùc cuûa cöûa soå veà cuøng kích thöôùc cuûa
vuøng quan saùt (hình 4.5b, hình 4.5c), cuoái cuøng laø pheùp tònh tieán dòch chuyeån
y
y
v
v
(xmax,ymax
)
(umax,vmax)
(xmin,ymin
)
(umin,vmin)
x
x
u
u
(a)
(b)
(c)
(d)
veà goùc traùi döôùi cuûa vuøng quan saùt (hình 4.5d).
Hình 4.5 – Pheùp chuyeån ñoåi töø cöûa soå sang vuøng quan saùt
Ta coù ma traän cuûa pheùp bieán ñoåi :
umax umin vmax vmin
xmax xmin ymax ymin
MWV MTW
xmin ,ymin
MS
,
MTV
umin ,vmin
umax umin
xmax xmin
0
0
0
1
vmax vmin
ymax ymin
vmax vmin
0
umax umin
xmax xmin
xmin
umin ymin
vmin
ymax ymin
Nhö vaäy neáu P
x, y
laø ñieåm trong cöûa soå thì noù seõ coù toïa ñoä trong vuøng quan saùt laø :
umax umin
xmax xmin
vmax vmin
ymax ymin
sx
x xmin umin ,sy
y ymin
vmin
vôùi sx
, sy
.
sx,sy laø caùc heä soá tæ leä cuûa caùc kích thöôùc cuûa cöûa soå vaø vuøng quan saùt. Khi
sx sy 1, caùc ñoái töôïng qua pheùp chuyeån ñoåi seõ ñöôïc giöõ nguyeân hình daùng vaø tính caân
xöùng.
1.4. Caùc thuaät toaùn xeùn hình
Thao taùc loaïi boû caùc phaàn hình aûnh naèm ngoaøi moät vuøng cho tröôùc ñöôïc goïi
laø xeùn hình. Vuøng ñöôïc duøng ñeå xeùn hình goïi laø cöûa soå xeùn (clip window).
Tuøy thuoäc vaøo töøng öùng duïng cuï theå maø cöûa soå xeùn coù theå coù daïng laø
ña giaùc hay laø ñöôøng cong kheùp kín. Trong phaàn naøy chuùng ta seõ khaûo saùt
caùc thuaät toaùn xeùn hình vaøo cöûa soå xeùn laø hình chöõ nhaät tröôùc, sau ñoù seõ
khaûo saùt caùc cöûa soå xeùn coù daïng khaùc. Ñeå ñôn giaûn, trong caùc thuaät toaùn
xeùn hình, cöûa soå xeùn ñöôïc goïi laø cöûa soå.
2. CAÙC THUAÄT TOAÙN XEÙN ÑIEÅM, ÑOAÏN THAÚNG
Giaû söû cöûa soå xeùn laø cöûa soå hình chöõ nhaät coù toïa ñoä cuûa caùc ñieåm döôùi beân traùi vaø
ñieåm treân beân phaûi laàn löôït laø
xmin, ymin
vaø
xmax, ymax
.
Moät ñieåm P
x xmax
x, y
ñöôïc coi laø naèm beân trong cöûa soå neáu thoûa heä baát phöông trình :
x
min
ymin y ymax
Baây giôø, ta seõ xeùt baøi toaùn xeùn ñoaïn thaúng ñöôïc cho bôûi hai ñieåm P1x1, y1
vaø
P2
x2 , y2
vaøo cöûa soå hình chöõ nhaät treân.
P7
P4
P2
P2
P6
P8
P1
P1
P'6
Window
Window
P3
P'5
(a)
P5
(b)
Hình 4.6 – Minh hoïa thao taùc xeùn caùc ñoaïn thaúng vaøo moät cöûa soå hình chöõ nhaät. Tröôùc khi xeùn (a). Sau khi
xeùn (b).
Thao taùc xeùn hình laø moät trong nhöõng thao taùc cô baûn cuûa quaù trình hieån thò
ñoái töôïng, do ñoù vaán ñeà toái öu toác ñoä luoân laø ñích cho caùc thuaät toaùn nhaém
ñeán. YÙ töôûng chung cuûa caùc thuaät toaùn xeùn ñoaïn thaúng ñoù laø loaïi boû
pheùp toaùn tìm giao ñieåm giöõa ñoaïn thaúng vôùi bieân cuûa cöûa soå moät caùch
nhanh nhaát ñoái vôùi caùc ñoaïn thaúng ñaëc bieät nhö naèm hoaøn toaøn trong hoaëc
hoaøn toaøn beân ngoaøi cöûa soå (ví duï nhö ñoaïn P1P2 vaø P3P4 trong hình 4.6). Ñoái
vôùi caùc ñoaïn thaúng coù khaû naêng caét cöûa soå, caàn phaûi ñöa ra caùch tìm giao
ñieåm thaät nhanh.
Nhaän xeùt raèng, caùc ñoaïn thaúng maø coù caû hai ñieåm naèm hoaøn toaøn trong
cöûa soå thì caû ñoaïn thaúng naèm trong cöûa soå, ñaây cuõng chính laø keát quaû sau
khi xeùn (ví duï nhö ñoaïn thaúng P1P2), maët khaùc ñoái vôùi caùc ñoaïn thaúng maø
coù hai ñieåm naèm veà cuøng moät phía cuûa cöûa soå thì luoân naèm ngoaøi cöûa soå
vaø seõ bò maát sau khi xeùn (ví duï nhö ñoaïn thaúng P3P4). Vôùi caùc ñoaïn thaúng coù
khaû naêng caét cöûa soå (ví duï nhö ñoaïn thaúng P5P6 vaø P7P8) ñeå vieäc tìm giao
ñieåm nhanh caàn ruùt goïn vieäc tìm giao ñieåm vôùi nhöõng bieân cöûa soå khoâng
caàn thieát ñeå xaùc ñònh phaàn giao neáu coù cuûa ñoaïn thaúng vaø cöûa soå.
Ngöôøi ta thöôøng söû duïng phöông trình tham soá cuûa ñoaïn thaúng trong vieäc tìm
giao ñieåm giöõa ñoaïn thaúng vôùi cöûa soå.
x x1 t
y y1 t
x2 x1
x1 tDx, Dx x2 x1
y1 tDy, Dy y2 y1,
y2 y1
0 t 1
Neáu giao ñieåm öùng vôùi giaù trò t naèm ngoaøi ñoaïn
khoâng thuoäc veà cöûa soå.
0,1 thì giao ñieåm ñoù seõ
2.1. Thuaät toaùn Cohen-Sutherland
Ñaây laø moät trong nhöõng thuaät toaùn ra ñôøi sôùm nhaát vaø thoâng duïng nhaát.
Baèng caùch keùo daøi caùc bieân cuûa cöûa soå, ngöôøi ta chia maët phaúng thaønh
chín vuøng goàm cöûa soå vaø taùm vuøng xung quanh noù.
Khaùi nieäm maõ vuøng (area code)
Moät con soá 4 bit nhò phaân goïi laø maõ vuøng seõ ñöôïc gaùn cho moãi vuøng ñeå
moâ taû vò trí töông ñoái cuûa vuøng ñoù so vôùi cöûa soå. Baèng caùch ñaùnh soá töø 1
ñeán 4 theo thöù töï töø phaûi qua traùi, caùc bit cuûa maõ vuøng ñöôïc duøng theo quy
öôùc sau ñeå chæ moät trong boán vò trí töông ñoái cuûa vuøng so vôùi cöûa soå bao
goàm : traùi, phaûi, treân, döôùi.
Bit 1 : traùi (LEFT)
Bit 2 : phaûi (RIGHT)
Bit 3 : treân (TOP)
Bit 4 : döôùi (BOTTOM)
Giaù trò 1 töông öùng vôùi vò trí bit naøo trong maõ vuøng seõ chæ ra raèng ñieåm ñoù
ôû vò trí töông öùng, ngöôïc laïi bit ñoù seõ ñöôïc ñaët baèng 0. Ví duï moät vuøng coù
maõ laø 1001, thì noù seõ naèm phía döôùi (bit 4 baèng 1), beân traùi (bit 1 baèng 1) so
vôùi cöûa soå, vuøng coù maõ laø 0000 chính laø cöûa soå.
TOP
0101
0001
1001
0100
0110
0010
1010
4
3
2
1
LEFT
LEFT
RIGHT
0000
RIGHT
TOP
Window
BOTTOM
BOTTOM
1000
Hình 4.7 – Maõ vuøng quy ñònh vò trí töông ñoái cuûa vuøng so vôùi cöûa soå
Caùc giaù trò bit trong maõ vuøng ñöôïc tính baèng caùch xaùc ñònh toïa ñoä cuûa ñieåm
thuoäc vuøng ñoù vôùi caùc bieân cuûa cöûa soå. Bit 1 ñöôïc ñaët laø 1 neáu
x, y
x xmin , caùc bit khaùc ñöôïc tính töông töï.
Thuaät toaùn
Gaùn maõ vuøng töông öùng cho caùc ñieåm ñaàu cuoái P , P2 cuûa ñoaïn thaúng caàn xeùn laàn löôït
1
laø c1,c2 . Ta coù nhaän xeùt :
•
Caùc ñoaïn thaúng naèm hoaøn toaøn beân trong cöûa soå seõ coù c1 c2 0000, öùng
vôùi caùc ñoaïn naøy, keát quaû sau khi xeùn laø chính noù.
•
Neáu toàn taïi k
1,..,4 , sao cho vôùi bit thöù k cuûa c1,c2 ñeàu coù giaù trò 1, luùc
naøy ñoaïn thaúng seõ naèm veà cuøng phía öùng vôùi bit k so vôùi cöûa soå, do ñoù
naèm hoaøn toaøn ngoaøi cöûa soå. Ñoaïn naøy seõ bò loaïi boû sau khi xeùn. Ví duï,
neáu c1 1001,c2 0101, roõ raøng bit 1 cuûa chuùng ñeàu baèng 1 (öùng vôùi bieân
traùi), do ñoù ñoaïn thaúng naèm hoaøn toaøn veà bieân traùi cuûa cöûa soå. Ñeå xaùc
ñònh tính chaát naøy, ñôn giaûn chæ caàn thöïc hieän pheùp toaùn logic AND treân
c1,c2 . Neáu keát quaû khaùc 0000, ñoaïn thaúng seõ naèm hoaøn toaøn ngoaøi cöûa soå.
•
Neáu c1,c2 khoâng thuoäc veà hai tröôøng hôïp treân, ñoaïn thaúng coù theå hoaëc
khoâng caét ngang cöûa soå (ví duï ñoaïn P5 P6 , P7 P8 trong hình 4.6) chaéc chaén seõ
toàn taïi moät ñieåm naèm ngoaøi cöûa soå, khoâng maát tính toång quaùt giaû söû ñieåm
ñoù laø
P1 . Baèng caùch xeùt maõ vuøng cuûa P laø c1 ta coù theå xaùc ñònh ñöôïc caùc
1
bieân maø ñoaïn thaúng coù theå caét ñeå töø ñoù choïn moät bieân vaø tieán haønh tìm
giao ñieåm P 'cuûa ñoaïn thaúng vôùi bieân ñoù. Luùc naøy, ñoaïn thaúng ban ñaàu
1
ñöôïc xeùn thaønh P P '. Tôùi ñaây chuùng ta laïi laëp laïi thao taùc ñaõ xeùt cho
1
1
ñoaïn thaúng môùi P P ' cho tôùi khi xaùc ñònh ñöôïc phaàn naèm trong hoaëc loaïi
1
1
boû toaøn boä ñoaïn thaúng.
Chuùng ta minh hoïa thuaät toaùn baèng hình veõ 4.8. Vôùi ñoaïn thaúng P P2 , ta seõ kieåm
1
tra
P laàn löôït vôùi caùc bieân traùi, phaûi, döôùi, treân vaø tìm ra ñieåm naøy naèm döôùi cöûa soå, sau
1
ñoù chuùng ta tìm giao ñieåm P ' cuûa ñoaïn thaúng vôùi bieân döôùi. Luùc naøy ñoaïn thaúng ban ñaàu
1
ñöôïc xeùn ngaén laïi thaønh P 'P2 . Vì P2 naèm ngoaøi cöûa soå neân baèng caùch xeùt töông töï,
1
chuùng ta seõ tieán haønh tìm giao ñieåm P2 ' cuûa P 'P2 vôùi bieân treân vaø luùc naøy ñoaïn P 'P2 ' ,
1
1
chính laø phaàn naèm hoaøn toaøn trong cöûa soå.
Trong tröôøng hôïp ñoaïn P3 P4 P3 naèm beân traùi cöûa soå neân chuùng ta coù theå xaùc ñònh
,
ñieåm giao P3 ', vaø töø ñoù loaïi boû ñoaïn thaúng P3 P3 '. Baèng caùch kieåm tra maõ vuøng, chuùng ta
deã daøng xaùc ñònh ñöôïc ñoaïn thaúng P3 'P4 naèm hoaøn toaøn beân döôùi cöûa soå neân coù theå boû ñi
toaøn boä.
P2
P'2
P3
P'1
P'3
P1
P4
Hình 4.8 – Minh hoïa thuaät toaùn Cohen - Sutherland
Caùc ñieåm giao vôùi caùc bieân cöûa soå cuûa ñoaïn thaúng coù theå ñöôïc tính töø phöông trình
tham soá nhö ñaõ ñeà caäp ôû phaàn treân. Tung ñoä y cuûa ñieåm giao ñoaïn thaúng vôùi bieân ñöùng
cuûa cöûa soå coù theå tính töø coâng thöùc y y1 m
Töông töï, hoaønh ñoä x cuûa ñieåm giao ñoaïn thaúng vôùi bieân ngang cuûa cöûa soå coù theå tính töø
coâng thöùc : x x1 y y1 / m , trong ñoù y coù theå laø ymin hay ymax
x x1
, trong ñoù x coù theå laø xmin hay xmax .
.
Löu ñoà thuaät toaùn Cohen-Sutherland duøng ñeå xeùn moät ñoaïn thaúng qua hai ñieåm
(x1,y1) vaø (x2,y2) vaøo cöûa soå hình chöõ nhaät cho tröôùc
Begin
EnCode(P1,c1);
EnCode(P2,c2)
(c1!=0000) || (c2!=0000)
No
Yes
(c1&c2 == 0000)
Yes
No
Xaùc ñònh giao ñieåm cuûa ñoaïn
thaúng vôùi bieân cuûa cöûa soå
baèng caùch xeùt maõ vuøng cuûa
ñieåm naèm ngoaøi cöûa soå
End
Caøi ñaët minh hoïa thuaät toaùn Cohen - Sutherland
#define TRUE
1
0
1
2
4
#define FALSE
#define LEFT
#define RIGHT
#define TOP
#define BOTTOM
typedef struct {
int x, y;
8
}POINT;
typedef struct {
int Left, Top, Right, Bottom;
}RECT;
typedef int CODE;
#define Accept(a,b)
#define Reject(a,b)
(!(a|b))
(a&b)
// Tra ve ma vung cua p la c
void EnCode(POINT p, CODE &c, RECT rWin)
{
c = 0;
if(p.x < rWin.Left)
c |= LEFT;
if(p.x > rWin.Right)
c |= RIGHT;
if(p.y > rWin.Top)
c |= TOP;
if(p.y < rWin.Bottom)
c |= BOTTOM;
}
// Hoan vi hai diem p1 va p2 sao cho p1 luon nam ngoai cua so
void SwapPoint(POINT& p1, POINT &p2, CODE &c1, CODE &c2)
{
if(!c1) // Neu p1 nam hoan toan trong cua so
{
POINT p;
p = p1;
p1 = p2;
p2 = p;
CODE c;
c = c1;
c1 = c2;
c2 = c;
}
}
// Tra ve TRUE neu co cat cua so. Nguoc lai tra ve FALSE
int CohenSutherlandClipping(POINT P1, POINT P2, POINT &Q1, POINT &Q2, RECT rWin)
{
int fStop = FALSE, fResult = FALSE;
CODE c1, c2;
while(!fStop)
{
EnCode(P1, c1, rWin);
EnCode(P2, c2, rWin);
// Neu duong thang nam hoan toan ben trong cua so
if(Accept(c1, c2))
{
fStop
fResult = TRUE;
} // Accept
= TRUE; // break
else
{
// Neu duong thang nam hoan toan ben ngoai cua so
if(Reject(c1,c2))
{
fStop = TRUE; // break
} // Reject
else // Xet truong hop duong thang co the cat cua so
{
SwapPoint(P1, P2, c1, c2);
float m;
if(P2.x!=P1.x)
m = float(P2.y-P1.y)/(P2.x-P1.x);
if(c1 & LEFT)
{
P1.y += (rWin.Left-P1.x)*m;
P1.x = rWin.Left;
} // Left
else
{
if(c1 & RIGHT)
{
P1.y += (rWin.Right-P1.x)*m;
P1.x = rWin.Right;
} // Right
else
{
if(c1 & TOP)
{
if(P2.x!=P1.x)
P1.x += (rWin.Top - P1.y)/m;
P1.y = rWin.Top;
} // Top
else // Bottom
{
if(P2.x!=P1.x)
P1.x
+= (rWin.Bottom - P1.y)/m;
P1.y = rWin.Bottom;
} // Bottom
}
}
} // Xet truong hop duong thang co the cat cua so
}
} //while
Q1 = P1;
Q2 = P2;
return (fResult);
} //CohenSutherlandClipping
2.2. Thuaät toaùn Liang-Barsky
Thuaät toaùn Liang-Barsky ñöôïc phaùt trieån döïa vaøo vieäc phaân tích daïng tham soá
cuûa phöông trình ñoaïn thaúng.
x x1 t
y y1 t
x2 x1
x1 tDx, Dx x2 x1
y1 tDy, Dy y2 y1,
y2 y1
0 t 1
ÖÙng vôùi moãi giaù trò t, ta seõ coù moät ñieåm P töông öùng thuoäc ñöôøng thaúng.
•
•
•
Caùc ñieåm öùng vôùi t 1seõ thuoäc veà tia P2x.
Caùc ñieåm öùng vôùi t 0 seõ thuoäc veà tia P2x’.
Caùc ñieåm öùng vôùi 0 t 1 seõ thuoäc veà ñoaïn thaúng P P2
.
1
x
P2(x2, y2)
t>1
t=1
P1(x1, y1)
t=0
t<0
x'
Hình 4.9 – Phöông trình tham soá cuûa ñoaïn thaúng
Taäp hôïp caùc ñieåm thuoäc veà phaàn giao cuûa ñoaïn thaúng vaø cöûa soå öùng vôùi
caùc giaù trò t thoûa heä baát phöông trình :
x
y
x1 tDx xmax
y1 tDy ymax
min
min
0 t 1
p1 Dx, q1 x1 xmin
p2 Dx, q2 xmax x1
p3 Dy, q3 y1 ymin
p4 Dy, q4 ymax y1
Ñaët
Luùc naøy ta vieát heä phöông trình treân döôùi daïng :
p t q , k
0 t 1
1,2,3,4
k
k
Nhö vaäy vieäc tìm ñoaïn giao thöïc chaát laø tìm nghieäm cuûa heä baát phöông trình
naøy. Coù hai khaû naêng xaûy ra ñoù laø :
•
Heä baát phöông trình voâ nghieäm, nghóa laø ñöôøng thaúng khoâng coù phaàn giao
vôùi cöûa soå neân seõ bò loaïi boû.
•
Heä baát phöông trình coù nghieäm, luùc naøy taäp nghieäm seõ laø caùc giaù trò t thoûa
t
t1,t2
0,1 .
Ta xeùt caùc tröôøng hôïp :
•
Neáu k
k treân laø voâ nghieäm, do ñoù heä voâ nghieäm.
Neáu k 1,2,3,4 : (pk 0) (qk 0) thì vôùi caùc baát phöông trình maø öùng
1,2,3,4
: (pk 0) (qk 0)thì roõ raøng baát phöông trình öùng vôùi
•
vôùi pk = 0 laø caùc baát phöông trình hieån nhieân, luùc naøy heä baát phöông trình
caàn giaûi töông ñöông vôùi heä baát phöông trình coù pk 0.
•
•
Vôùi caùc baát phöông trình pk t qk maø pk 0, ta coù t qk / pk
Vôùi caùc baát phöông trình pk t qk maø pk 0, ta coù t qk / pk
t1,t2
.
.
Vaäy nghieäm cuûa heä baát phöông trình laø
vôùi :
qk
pk
t max(
, p 0
0 )
1
k
qk
pk
t min(
, p 0
1 )
2
k
t1 t2
Neáu heä treân coù nghieäm thì ñoaïn giao Q1Q2 seõ laø
Q1 (x1 t1 Dx, y1 t1 Dy),Q2 (x1 t2 Dx, y1 t2 Dy)
.
Neáu xeùt thuaät toaùn naøy ôû khía caïnh hình hoïc ta coù :
•
Tröôøng hôïp k
1,2,3,4 : (pk 0) (qk 0) töông öùng vôùi tröôøng hôïp
ñoaïn thaúng caàn xeùt song song vôùi moät trong caùc bieân cuûa cöûa soå ( pk 0)
vaø naèm ngoaøi cöûa soå (qk 0) neân seõ bò loaïi boû sau khi xeùn.
•
Vôùi pk 0, giaù trò t rk qk / pk seõ töông öùng vôùi giao ñieåm cuûa ñoaïn
thaúng vôùi bieân k keùo daøi cuûa cöûa soå. Tröôøng hôïp pk 0, keùo daøi caùc bieân
cöûa soå vaø ñoaïn thaúng veà voâ cöïc, ta coù ñöôøng thaúng ñang xeùt seõ coù höôùng ñi
töø beân ngoaøi vaøo beân trong cöûa soå. Neáu pk 0, ñöôøng thaúng seõ coù höôùng
ñi töø beân trong cöûa soå ñi ra. Do ñoù hai ñaàu muùt cuûa ñoaïn giao seõ öùng vôùi
caùc giaù trò t1,t2 ñöôïc tính nhö sau : Giaù trò t1 chính laø giaù trò lôùn nhaát cuûa
caùc rk qk / pk maø pk 0 (ñöôøng thaúng ñi töø ngoaøi vaøo trong cöûa soå) vaø 0;
giaù trò t2 chính laø giaù trò nhoû nhaát cuûa caùc rk qk / pk maø pk 0 (ñöôøng
thaúng ñi töø trong cöûa soå ñi ra) vaø 1.
Hình 4.10 – Xeùt vôùi bieân traùi ñoaïn thaúng P1P2 coù höôùng ñi töø ngoaøi vaøo trong, nhöng so vôùi bieân phaûi ñoaïn
P2
P'2
P'1
P1
thaúng P’1P’2 laïi coù höôùng ñi töø trong cöûa soå ñi ra
Khi caøi ñaët thuaät toaùn Liang-Barsky, ban ñaàu caùc giaù trò t1, t2 ñöôïc khôûi ñoäng
t1 0,t2 1. Vôùi moãi laàn xeùn ñoaïn thaúng vôùi moät bieân cuûa cöûa soå, caùc giaù trò p,q seõ ñöôïc
truyeàn cho haøm ClipTest ñeå xaùc ñònh ñoaïn thaúng coù bò loaïi boû hay bò xeùn bôùt moät ñoaïn
hay khoâng. Khi p 0, tham soá r q / p seõ ñöôïc xem xeùt ñeå caäp nhaät t1 , khi p 0 , r
duøng ñeå caäp nhaät t2 . Khi caäp nhaät t1 vaø t2 neáu t1 t2 , ñoaïn thaúng seõ bò loaïi boû. Ngoaøi
ra neáu (p=0 vaø q<0), chuùng ta cuõng seõ loaïi boû ñoaïn thaúng vì noù song song vaø naèm ngoaøi
cöûa soå. Neáu ñoaïn thaúng khoâng bò loaïi boû sau boán laàn goïi vôùi caùc tham soá p, q töông öùng
vôùi caùc bieân cuûa cöûa soå, caùc giaù trò t1 vaø t2 seõ ñöôïc duøng ñeå suy ra toïa ñoä hai ñieåm ñaàu
muùt cuûa ñoaïn giao.
Caøi ñaët minh hoïa thuaät toaùn Liang - Barsky
// Tra ve TRUE neu khong xay ra truong hop nam ngoai cua so
int ClipTest(int p, int q, float &t1, float &t2)
{
float r;
if (p<0)
{
r = float(q)/p;
if (r>t2)
return FALSE;
else
if (r>t1)
t1 = r;
}
else
{
if (p>0)
{
r = float(q)/p;
if (r<t1)
return FALSE;
else
if (r<t2)
t2 = r;
}
else // p=0
{
if (q<0)
return FALSE;
}
}
return TRUE;
}
{
int LiangBarskyClipping(POINT P1, POINT P2, RECT R, POINT *Q1, POINT *Q2)
float t1, t2;
int Dx, Dy, x1, y1, x2, y2, xmin, ymin, xmax, ymax
;
t1 = 0;
t2 = 1;
x1 = P1.x; y1 = P1.y;
x2 = P2.x; y2 = P2.y;
Dx = x2 - x1; Dy = y2 - y1;
xmin = R.Left; ymin = R.Top;
xmax = R.Right; ymax = R.Bottom;
if (ClipTest(-Dx, x1 - xmin, t1, t2)) // Giai he bat phuong trinh 1
{
if (ClipTest(Dx, xmax - x1, t1, t2)) // Giai he bat phuong trinh 2
{
if (ClipTest(-Dy, y1 - ymin, t1, t2)) // Giai he bat phuong trinh 3
{
if (ClipTest(Dy, ymax - y1, t1, t2)) // Giai he bat phuong trinh 4
{
Q1.x = x1 + t1. Dx;
Q1.y = y1 + t1. Dy;
Q2.x = x1 + t2. Dx;
Q2.y = y1 + t2. Dy;
return TRUE;
} // Giai he bat phuong trinh 4
} // Giai he bat phuong trinh 3
} // Giai he bat phuong trinh 2
} // Giai he bat phuong trinh 1
return FALSE;
} // LiangBarskyClipping
Nhaän xeùt
Thoâng thöôøng, thuaät toaùn Liang-Barsky cho toác ñoä toát hôn thuaät toaùn Cohen-
Sutherland vì ruùt goïn ñöôïc soá giao ñieåm caàn tính. Moãi laàn caäp nhaät caùc giaù
trò t1,t2 , chæ caàn moät pheùp chia, vaø giao ñieåm cuûa ñoaïn thaúng vôùi cöûa soå
chæ ñöôïc tính duy nhaát moät laàn sau khi ñaõ tìm ra ñöôïc giaù trò t1,t2 . Trong khi ñoù
thuaät toaùn Cohen-Sutherland ñoâi luùc phaûi tính giao ñieåm cho caùc ñieåm khoâng
naèm trong bieân cuûa cöûa soå ñoøi hoûi nhieàu pheùp toaùn hôn.
3. THUAÄT TOAÙN XEÙN ÑA GIAÙC
Chuùng ta coù theå hieäu chænh caùc thuaät toaùn xeùn ñoaïn thaúng ñeå xeùn ña giaùc
baèng caùch xem ña giaùc nhö laø moät taäp caùc ñoaïn thaúng lieân tieáp noái vôùi
nhau. Tuy nhieân, keát quaû sau khi xeùn nhieàu khi laïi laø taäp caùc ñoaïn thaúng rôøi
nhau. Ñieàu chuùng ta mong muoán ôû ñaây ñoù laø keát quaû sau khi xeùn phaûi laø
moät caùc ña giaùc ñeå sau naøy coù theå chuyeån thaønh caùc vuøng toâ.
Hình 4.11 – Keát quaû sau khi xeùn ña giaùc ban ñaàu. Ña giaùc ban ñaàu (a). Keát quaû laø caùc ñoaïn rôøi nhau (b)
(a)
(b)
(c)
vaø keát quaû laø caùc ña giaùc (c)
Trong phaàn naøy chuùng ta seõ khaûo saùt moät trong caùc thuaät toaùn xeùn ña giaùc
ñoù laø thuaät toaùn Sutherland-Hodgeman.
Hình 4.12 – Quaù trình xeùn moät ña giaùc vaøo cöûa soå
Thuaät toaùn naøy seõ tieán haønh xeùn ña giaùc laàn löôït vôùi caùc bieân cöûa soå.
Ñaàu tieân, ña giaùc seõ ñöôïc xeùn doïc theo bieân traùi cuûa cöûa soå, keát quaû sau
böôùc naøy seõ ñöôïc duøng ñeå xeùn tieáp bieân phaûi, roài cöù töông töï nhö vaäy cho
caùc bieân treân, döôùi. Sau khi xeùn heát vôùi boán bieân cuûa cöûa soå, ta ñöôïc keát
quaû cuoái cuøng.
Vôùi moãi laàn xeùn ña giaùc doïc theo moät bieân naøo ñoù cuûa cöûa soå, neáu goïi
Vi ,Vi1 laø hai ñænh keà caïnh ViVi1 , ta coù 4 tröôøng hôïp coù theå xaûy ra khi xeùt
töøng caëp ñænh cuûa ña giaùc ban ñaàu vôùi bieân cuûa cöûa soå nhö sau:
•
(i) Neáu Vi naèm ngoaøi, Vi1 naèm trong, ta löu giao ñieåm I cuûa ViVi1 vôùi
bieân cuûa cöûa soå vaø Vi1
.
•
•
(ii) Neáu caû Vi , Vi1 ñeàu naèm trong, ta seõ löu caû Vi , Vi1
.
(iii) Neáu Vi naèm trong, Vi1 naèm ngoaøi, ta seõ löu Vi vaø I.
•
(iv) Neáu caû Vi , Vi1 ñeàu naèm ngoaøi, ta khoâng löu gì caû.
Vi
I
Vi+1
Vi
Vi+1
Vi
Vi+1
I
Vi+1
Vi
(i)
(ii)
(iii)
(iv)
Hình 4.13 – Caùc tröôøng hôïp khi xeùt Vi ,Vi1 vôùi caùc bieân cuûa cöûa soå
Caøi ñaët minh hoïa thuaät toaùn Sutherland-Hodgeman
#include <graphics.h>
#include <mem.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#define TRUE
#define FALSE
#define LEFT
#define RIGHT
#define TOP
1
0
1
2
4
8
#define BOTTOM
typedef struct {
int x, y;
}POINT;
typedef struct {
int Left, Top, Right, Bottom;
}RECT;
// Xac dinh p co nam ben trong cua so neu xet theo mot canh b
int Inside(POINT p, int Edge, RECT rWin)
{
switch(Edge)
{
case LEFT :
if(p.x < rWin.Left)
return FALSE;
break;
case RIGHT:
if(p.x > rWin.Right)
return FALSE;
break;
case TOP :
if(p.y > rWin.Top)
return FALSE;
break;
case BOTTOM :
if(p.y < rWin.Bottom)
return FALSE;
break;
}
return TRUE;
} //Inside
// Tra ve giao diem cua doan noi p1&p2 voi canh b
POINT Intersect(POINT p1, POINT p2, int Edge, RECT rWin)
{
POINT iPt;
float m;
if(p1.x != p2.x)
m = float(p2.y-p1.y)/(p2.x-p1.x);
switch(Edge)
{
case LEFT :
iPt.x = rWin.Left;
iPt.y = p2.y + (rWin.Left-p2.x)*m;
break;
case RIGHT :
iPt.x = rWin.Right;
iPt.y = p2.y + (rWin.Right-p2.x)*m;
break;
case TOP :
iPt.y = rWin.Top;
if(p1.x != p2.x)
iPt.x = p2.x + (rWin.Top-p2.y)/m;
else
iPt.x = p2.x;
break;
case BOTTOM :
iPt.y = rWin.Bottom;
if(p1.x != p2.x)
iPt.x = p2.x + (rWin.Bottom-p2.y)/m;
else
iPt.x = p2.x;
break;
}
return (iPt);
} // Intersect
// Tien hanh cat da giac voi mot canh nao do cua cua so.
void ClipEdge(POINT *pIn, int N, POINT *pOut, int &Cnt, int Edge,
RECT rWin)
{
int FlagPrevPt = FALSE;
Cnt = 0;
POINT pPrev;
pPrev = pIn[0];
if(Inside(pPrev, Edge, rWin)) // Save point
{
pOut[Cnt] = pPrev;
Cnt++;
FlagPrevPt = TRUE;
}
for(int i=1; i<N; i++)
{
if(FlagPrevPt) // Diem bat dau nam trong
{
if(Inside(pIn[i], Edge, rWin)) // Save point P
{
pOut[Cnt] = pIn[i];
Cnt++;
}
else // Save I
{
}
FlagPrevPt = FALSE;
pOut[Cnt] = Intersect(pPrev, pIn[i], Edge, rWin);
Cnt++;
}
else // Diem bat dau canh nam ngoai
{
if(Inside(pIn[i], Edge, rWin)) // Save point I, P
{
FlagPrevPt = TRUE;
pOut[Cnt] = Intersect(pPrev, pIn[i], Edge, rWin);
Cnt++;
pOut[Cnt] = pIn[i];
Cnt++;
}
}
pPrev = pIn[i];
}
// Neu Diem cuoi va dau giao voi bien cua cua so Save point I
if(!(Inside(pIn[N], Edge, rWin) == Inside(pPrev, Edge, rWin)))
{
pOut[Cnt] = Intersect(pPrev, pIn[N], Edge, rWin);
Cnt++;
}
pOut[Cnt] = pOut[0];
} // Intersect
void ClipPolygon(POINT *pIn, int N, POINT *pOut, int &Cnt,
RECT rWin)
{
POINT pTmp[20];
_fmemcpy(pTmp, pIn, (N+1)*sizeof(POINT));
ClipEdge(pTmp, N, pOut, Cnt, LEFT, rWin);
N = Cnt;
_fmemcpy(pTmp, pOut, (N+1)*sizeof(POINT));
ClipEdge(pTmp, N, pOut, Cnt, RIGHT, rWin);
N = Cnt;
_fmemcpy(pTmp, pOut, (N+1)*sizeof(POINT));
ClipEdge(pTmp, N, pOut, Cnt, TOP, rWin);
N = Cnt;
_fmemcpy(pTmp, pOut, (N+1)*sizeof(POINT));
ClipEdge(pTmp, N, pOut, Cnt, BOTTOM, rWin);
} // ClipPolygon
Nhaän xeùt
Thuaät toaùn Sutherland-Hodgeman cho keát quaû raát chính xaùc khi laøm vieäc vôùi
caùc ña giaùc loài, tuy nhieân vôùi caùc ña giaùc loõm keát quaû hieån thò coù theå seõ
coù ñoaïn thöøa nhö hình 4.11. Ñieàu naøy xaûy ra khi ña giaùc sau khi xeùn bò taùch
thaønh hai hay nhieàu vuøng. Do chuùng ta chæ löu keát quaû xuaát trong moät danh
saùch caùc ñænh neân ñænh cuoái cuûa danh saùch öùng vôùi ña giaùc tröôùc seõ noái
vôùi ñænh ñaàu cuûa danh saùch öùng vôùi ña giaùc sau. Moät trong nhieàu caùch ñeå
khaéc phuïc ñieåm naøy laø phaân ña giaùc loõm thaønh hai hay nhieàu ña giaùc loài vaø
xöû lí moãi ña giaùc loài rieâng.
TOÙM TAÉT
Hieån thò ñoái töôïng laø quaù trình ñöa caùc moâ taû ñoái töôïng töø theá giôùi thöïc sang moät thieát bò xuaát cuï theå
naøo ñoù. Quy trình naøy baét ñaàu baèng caùch ñònh nghóa töøng ñoái töôïng thaønh phaàn trong heä toïa ñoä cuïc boä
vaø keát thuùc baèng vieäc chuyeån toaøn boä ñoái töôïng leân heä toïa ñoä thieát bò. Baèng caùch ñöa ra ñònh nghóa heä
toïa ñoä quan saùt vaø caùc khaùi nieäm cöûa soå, vuøng quan saùt; moãi ñoái töôïng coù theå ñöôïc quan saùt ôû nhieàu vò trí
vaø goùc ñoä khaùc nhau. Thoâng thöôøng moãi hình aûnh maø chuùng ta quan saùt ñöôïc treân maøn hình thieát bò ñöôïc
goïi laø moät theå hieän (view) cuûa ñoái töôïng.
Quaù trình aùnh xaï moät vuøng ñònh nghóa trong heä toïa ñoä theá giôùi thöïc vaøo moät vuøng trong heä toïa ñoä
thieát bò ñöôïc goïi laø pheùp bieán ñoåi heä quan saùt. Ñaây thöïc chaát laø pheùp bieán ñoåi heä toïa ñoä. Quaù trình loaïi
boû caùc phaàn hình aûnh naèm ngoaøi moät vuøng cho tröôùc ñöôïc goïi laø xeùn hình. Vuøng ñöôïc duøng ñeå xeùn hình
goïi laø cöûa soå xeùn.
Caùc thuaät toaùn xeùn ñoaïn thaúng Cohen-Sutherland, Liang-Barsky ñeàu taäp trung giaûi quyeát hai vaán ñeà
chính nhaèm toái öu toác ñoä thuaät toaùn ñoù laø : loaïi boû vieäc tìm giao ñieåm ñoái vôùi caùc ñoaïn thaúng chaéc chaén
khoâng caét cöûa soå (nhö naèm hoaøn toaøn trong, naèm hoaøn toaøn ngoaøi), vaø vôùi caùc ñoaïn coù khaû naêng caét
cöûa soå, caàn phaûi tìm caùch haïn cheá soá laàn caàn tìm giao ñieåm vôùi caùc bieân khoâng caàn thieát. Thuaät toaùn
Cohen-Sutherland giaûi quyeát hai yù naøy thoâng qua kieåu döõ lieäu maõ vuøng maø veà maët baûn chaát ñoù chæ laø söï
moâ taû vò trí töông ñoái cuûa vuøng ñang xeùt so vôùi caùc bieân cuûa cöûa soå. Coøn thuaät toaùn Liang-Barsky thì tuy
döïa vaøo phöông trình tham soá cuûa ñoaïn thaúng ñeå laäp luaän nhöng thöïc chaát laø döïa treân vieäc xeùt caùc giao
ñieåm coù theå coù giöõa ñoaïn thaúng keùo daøi vôùi caùc bieân cuûa cöûa soå (cuõng ñöôïc keùo daøi). Caùc giao ñieåm
naøy töông öùng vôùi caùc giaù trò rk qk / pk . Caû hai thuaät toaùn naøy ñeàu coù theå ñöôïc môû roäng cho vieäc xeùn
hình trong ñoà hoïa ba chieàu.
BAØI TAÄP
1. Phaân tích caùc heä toïa ñoä duøng trong quy trình hieån thò ñoái töôïng hai chieàu.
2. Vieát ñoaïn chöông trình minh hoïa quaù trình chuyeån ñoåi töø cöûa soå sang vuøng quan saùt.
3. YÙ nghóa cuûa maõ vuøng trong thuaät toaùn Cohen-Sutherland.
4. Haõy cho moät ñoaïn thaúng minh hoïa maø trong tröôøng hôïp naøy thuaät toaùn phaûi thöïc
hieän vieäc tìm giao ñieåm 4 laàn theo thöù töï LEFT, TOP, RIGHT, BOTTOM.
5. Caøi ñaët thuaät toaùn Cohen-Sutherland ñeå xeùn moät ña giaùc. Phaân tích caùc tröôøng hôïp
thuaät toaùn naøy cho keát quaû laø caùc ñoaïn thaúng rôøi raïc.
6. So saùnh hai thuaät toaùn Cohen-Sutherland vaø Liang-Barsky veà soá pheùp toaùn thöïc hieän
trong caùc tröôøng hôïp chính.
7. Caøi ñaët thuaät toaùn Liang-Barsky vaø so saùnh vôùi toác ñoä thuaät toaùn Cohen-Sutherland.
8. Hieäu chænh caùc thuaät toaùn xeùn ñoaïn thaúng ñaõ hoïc ñeå coù theå xeùn ñoaïn thaúng vaøo cöûa
soå hình chöõ nhaät nghieâng vôùi truïc hoaønh moät goùc
.
9. Trình baøy vaø caøi ñaët thuaät toaùn phaân moät ña giaùc loõm thaønh caùc ña giaùc loài.
10. Döïa treân keát quaû cuûa baøi taäp treân, hieäu chænh thuaät toaùn Sutherland-Hodgeman ñeå
xeùn caùc ña giaùc loõm ñöôïc chính xaùc.
20 trang
27/04/2022
7820
Bạn đang xem tài liệu "Giáo trình Đồ họa máy tính - Chương 4, Phần 1: Hiển thị đối tượng hai chiều", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- giao_trinh_do_hoa_may_tinh_chuong_4_phan_1_hien_thi_doi_tuon.doc
Chuong4.htm
