›
›

Giáo trình Đồ họa máy tính - Bài: Các thuật toán xén điểm đoạn thẳng - Dương Anh Đức, Lê Đình Huy

Download
ÑOÀ HOÏA MAÙY TÍNH  
Caùc thuaät toaùn xeùn  
ù ä ù ù  
ñieåm, ñoaïn thaúng  
å ï ú  
Daãn nhaäp  
ã
ä
· 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).  
· Cho 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  
)
(
xmax , ymax
)  
vaø .  
P
(
x, y
)  
ñöôïc coi laø naèm beân trong cöûa soå  
· Moät ñieåm  
neáu thoûa heä baát phöông trình :  
x
£ x £ xmax  
ì
í
î
min  
.
ymin £ y £ ymax  
· Baây giôø, ta seõ xeùt baøi toaùn xeùn ñoaïn thaúng ñöôïc cho  
P
(
x1, y1  
)
P2  
(
x2 , y2
)  
vaøo cöûa soå hình  
bôûi hai ñieåm  
vaø  
1
chöõ nhaät treân.  
P7  
P4  
P2  
P2  
P6  
P8  
P1  
P1  
P'6  
Window  
Window  
P3  
P'5  
(a)  
P5  
(b)  
Döông Anh Ñöùc, Leâ Ñình Duy  
Caùc thuaät toaùn xeùn hình 1/11  
ÑOÀ HOÏA MAÙY TÍNH  
Vaán ñeà toái öu hoùa toác ñoä  
à á ù á  
á
ä
· YÙ töôûng chung :  
¨ Ñ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 treân) : khoâng caàn phaûi tìm giao  
ñieåm.  
¨ Ñ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 nhanh.  
· Nhaän xeùt  
¨ 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  
y2 - y1  
)
)
= x1 + tDx, Dx = x2 - x1  
= y1 + tDy, Dy = y2 - y1, 0 £ t £ 1  
· Neáu giao ñieåm öùng vôùi giaù trò t naèm ngoaøi ñoaïn  
[
0,1
]  
thì giao ñieåm ñoù seõ khoâng thuoäc veà cöûa soå.  
Döông Anh Ñöùc, Leâ Ñình Duy  
Caùc thuaät toaùn xeùn hình 2/11  
ÑOÀ HOÏA MAÙY TÍNH  
Thuaät toaùn Cohen - Sutherland  
ä
ù
· Keùo daøi caùc bieân cuûa cöûa soå, 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ù.  
TOP  
0101  
0001  
1001  
0100  
0110  
0010  
1010  
4
3
2
1
LEFT  
LEFT  
RIGHT  
0000  
RIGHT  
TOP  
Window  
BOTTOM  
BOTTOM  
1000  
· 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. Ví duï :  
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í öông öùng, ngöôïc laïi bit ñoù seõ  
ñöôïc ñaët baèng 0.  
¨ Caùc giaù trò bit trong maõ vuøng ñöôïc tính baèng caùch xaùc  
(
x, y  
)
thuoäc vuøng ñoù vôùi caùc bieân  
ñònh toïa ñoä cuûa ñieåm  
x < x  
cuûa cöûa soå. Bit 1 ñöôïc ñaët laø 1 neáu  
ñöôïc tính töông töï.  
min , caùc bit khaùc  
Döông Anh Ñöùc, Leâ Ñình Duy  
Caùc thuaät toaùn xeùn hình 3/11  
ÑOÀ HOÏA MAÙY TÍNH  
Thuaät toaùn  
ä
ù
· Gaùn maõ vuøng töông öùng cho caùc ñieåm ñaàu cuoái  
P , P  
c1,c  
2 cuûa ñoaïn thaúng caàn xeùn laàn löôït laø  
coù nhaän xeùt :  
2 . Ta  
1
¨ Caùc ñoaïn thaúng naèm hoaøn toaøn beân trong cöûa soå seõ coù  
c = c = 0000  
, öùng vôùi caùc ñoaïn naøy, keát quaû sau khi  
xeùn laø chính noù.  
1
2
c1 ,c2  
ñeàu  
kÎ 1,..4  
¨ Neáu toàn taïi  
, sao cho vôùi bit thöù k cuûa  
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. Ñ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  
c1,c  
AND treân  
2 . Neáu keát quaû khaùc 0000, ñoaïn thaúng seõ  
naèm hoaøn toaøn ngoaøi cöûa soå.  
c1,c2  
¨ Neáu  
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å, 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  
P
quaùt giaû söû ñieåm ñoù laø 1 . Baèng caùch xeùt maõ vuøng cuûa  
c1  
P
laø  
ta coù theå xaùc ñònh ñöôïc caùc bieân maø ñoaïn  
1
thaúng coù theå caét ñeå töø ñoù choïn moät bieân vaø tieán haønh  
P '  
tìm giao ñieåm  
ñoaïn thaúng ban ñaàu ñöôïc xeùn thaønh  
ta laïi laëp laïi thao taùc ñaõ xeùt cho ñoaïn thaúng môùi  
cuûa ñoaïn thaúng vôùi bieân ñoù. Luùc naøy,  
1
P P '  
. Sau ñoù chuùng  
1
1
P P '  
1
1
cho tôùi khi xaùc ñònh ñöôïc phaàn naèm trong hoaëc loaïi boû  
toaøn boä ñoaïn thaúng.  
¨ 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á. Ví duï : tung ñoä y cuûa  
ñieåm giao ñoaïn thaúng vôùi bieân ñöùng cuûa cöûa soå coù theå  
y = y1 + m
(
x - x1
)  
, trong ñoù x coù theå laø  
tính töø coâng thöùc  
xmax  
xmin  
hay  
.
Döông Anh Ñöùc, Leâ Ñình Duy  
Caùc thuaät toaùn xeùn hình 4/11  
ÑOÀ HOÏA MAÙY TÍNH  
Löu ñoà thuaät toaùn Cohen - Sutherland  
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  
// Ñoaïn CT tính maõ vuøng  
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;  
}
Döông Anh Ñöùc, Leâ Ñình Duy  
Caùc thuaät toaùn xeùn hình 5/11  
ÑOÀ HOÏA MAÙY TÍNH  
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  
y2 - y1  
)
)
= x1 + tDx, Dx = x2 - x1  
= y1 + tDy, Dy = 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.  
t ³ 1  
t £ 0  
¨ Caùc ñieåm öùng vôùi  
¨ Caùc ñieåm öùng vôùi  
¨ Caùc ñieåm öùng vôùi  
seõ thuoäc veà tia P2x.  
seõ thuoäc veà tia P2x’.  
0 £ t £ 1  
P P2  
seõ thuoäc veà ñoaïn thaúng  
.
1
x
P2(x2, y2)  
t>1  
t=1  
P1(x1, y1)  
t=0  
t<0  
x'  
· 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  
x
y
£ x1 + tDx £ xmax  
£ y1 + tDy £ ymax  
ì
ï
í
min  
min  
trình :  
ï
0 £ t £ 1  
î
Döông Anh Ñöùc, Leâ Ñình Duy  
Caùc thuaät toaùn xeùn hình 6/11  
ÑOÀ HOÏA MAÙY TÍNH  
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 = 1,2,3,4  
0 £ t £ 1  
ì
í
î
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õ  
tÎ  
[
t1,t2  
]
Í
[
0,1
]  
.
laø caùc giaù trò t thoûa  
· Ta xeùt caùc tröôøng hôïp :  
$ kÎ
{
1,2,3,4
}
: (pk = 0) Ù (qk < 0)  
¨ Neáu  
thì roõ raøng baát  
phöông trình öùng vôùi k treân laø voâ nghieäm, do ñoù heä voâ  
nghieäm.  
" kÎ
{
1,2,3,4
}
: (p ¹ 0) Ú (q ³ 0)  
thì vôùi caùc baát  
¨ Neáu  
k
k
phöông trình maø öùng 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.  
pkt £ qk  
p < 0  
¨ Vôùi caùc baát phöông trình  
t ³ qk / pk  
maø  
, ta coù  
k
.
pkt £ q  
p > 0  
¨ Vôùi caùc baát phöông trình  
t £ qk / pk  
k maø  
, ta coù  
k
.
Döông Anh Ñöùc, Leâ Ñình Duy  
Caùc thuaät toaùn xeùn hình 7/11  
ÑOÀ HOÏA MAÙY TÍNH  
[
t1,t2  
]
vôùi :  
· Vaäy nghieäm cuûa heä baát phöông trình laø  
ì
ï
ï
ì
í
î
ü
qk  
pk  
t = max(  
, p < 0 U  
{
0
}
)
ý
1
k
þ
ü
ï
ï
í
ì
qk  
pk  
t = min(  
, p > 0 U  
{1  
}
)
í
ý
2
k
î
þ
ï
ï
ï
t1 £ t2  
ï
î
Q1Q2  
· Neáu heä treân coù nghieäm thì ñoaïn giao  
seõ laø  
Q (x + t Dx, y + t Dy),Q (x + t Dx, y + t Dy)  
.
1
1
1
1
1
2
1
2
1
2
· Neáu xeùt thuaät toaùn naøy ôû khía caïnh hình hoïc ta coù :  
$ k Î  
{
1,2,3,4  
}
: (pk = 0) Ù (qk < 0)  
töông öùng  
¨ Tröôøng hôïp  
vôùi tröôøng hôïp ñoaïn thaúng caàn xeùt song song vôùi moät  
p = 0  
trong caùc bieân cuûa cöûa soå (  
) vaø naèm ngoaøi cöûa soå  
k
q < 0  
(
) neân seõ bò loaïi boû sau khi xeùn.  
k
t = rk = qk / pk  
seõ töông öùng vôùi  
p ¹ 0  
¨ Vôùi  
, giaù trò  
k
giao ñieåm cuûa ñoaïn thaúng vôùi bieân k keùo daøi cuûa cöûa soå.  
p < 0  
Tröôøng hôïp  
thaúng veà voâ cöïc, ta coù ñöôøng thaúng ñang xeùt seõ coù höôùng  
p > 0  
, keùo daøi caùc bieân cöûa soå vaø ñoaïn  
k
ñi töø beân ngoaøi vaøo beân trong cöûa soå. Neáu  
thaúng seõ coù höôùng ñi töø beân trong cöûa soå ñi ra. Do ñoù hai  
t1 ,t2  
, ñöôøng  
k
ñaàu muùt cuûa ñoaïn giao seõ öùng vôùi caùc giaù trò  
ñöôïc  
t1  
tính nhö sau : Giaù trò  
rk = qk / p pk < 0  
chính laø giaù trò lôùn nhaát cuûa caùc  
(ñöôøng thaúng ñi töø ngoaøi vaøo  
k maø  
trong cöûa soå) vaø 0; giaù trò  
t2  
chính laø giaù trò nhoû nhaát  
(ñöôøng thaúng ñi töø trong  
pk > 0  
k maø  
rk = qk / p  
cuûa caùc  
cöûa soå ñi ra) vaø 1.  
Döông Anh Ñöùc, Leâ Ñình Duy  
Caùc thuaät toaùn xeùn hình 8/11  
ÑOÀ HOÏA MAÙY TÍNH  
Thuaät toaùn xeùn ña giaùc  
ä ù ù ù  
Sutherland - Hodgemand  
Daãn nhaäp  
ã
ä
· 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â.  
(a)  
(b)  
(c)  
Döông Anh Ñöùc, Leâ Ñình Duy  
Caùc thuaät toaùn xeùn hình 9/11  
ÑOÀ HOÏA MAÙY TÍNH  
Thuaät toaùn Sutherland - Hodgeman  
ä
ù
· 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ù  
Vi ,Vi+1  
cuûa cöûa soå, neáu goïi  
laø hai ñænh keà caïnh  
ViV  
i+1 , 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:  
Vi+1  
naèm trong, ta löu giao ñieåm I  
Vi  
¨ Neáu  
naèm ngoaøi,  
ViVi+1  
Vi+1  
cuûa  
vôùi bieân cuûa cöûa soå vaø  
.
Vi  
Vi  
Vi+1  
,
Vi+1  
¨ Neáu caû  
,
ñeàu naèm trong, ta seõ löu caû  
.
Vi  
vaø I.  
Vi  
Vi+1  
¨ Neáu  
naèm trong,  
naèm ngoaøi, ta seõ löu  
Vi+1  
Vi  
¨ Neáu caû  
,
ñ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)  
Döông Anh Ñöùc, Leâ Ñình Duy  
Caùc thuaät toaùn xeùn hình 10/11  
ÑOÀ HOÏA MAÙY TÍNH  
Caøi ñaët haøm xeùn ña giaùc theo moät caïnh cuûa cöûa 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];  
}// ClipEdge  
Döông Anh Ñöùc, Leâ Ñình Duy  
Caùc thuaät toaùn xeùn hình 11/11  
pdf 11 trang baolam 09/05/2022 2140
Download
Bạn đang xem tài liệu "Giáo trình Đồ họa máy tính - Bài: Các thuật toán xén điểm đoạn thẳng - Dương Anh Đức, Lê Đình Huy", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • pdfgiao_trinh_do_hoa_may_tinh_bai_cac_thuat_toan_xen_diem_doan.pdf