CG
GIS [email protected]
Računarstvo i informatika
Računarska grafika
Odsecanje (clipping) objekata
Prof. Dr Slobodanka Đorđević - Kajan
Katedra za računarstvo
Elektronski fakultet Niš
Prof. Dr Slobodanka Đorđević-Kajan
EF Niš, Računarstvo i informatika
RG – Grafički sistemi
1
2008/2009
CG
Ciljevi
Definisanje odsecanja
Definisanje pokrivanja
Algoritmi za odsecanje
Odsecanje tačke
Odsecanje linija
Odsecanje poligona
Prof. Dr Slobodanka Đorđević-Kajan
EF Niš, Računarstvo i informatika
RG – Grafički sistemi
2
2008/2009
GIS [email protected]
CG
Definisanje odsecanja
Prof. Dr Slobodanka Đorđević-Kajan
EF Niš, Računarstvo i informatika
RG – Grafički sistemi
3
2008/2009
GIS [email protected]
CG
Definisanje pokrivanja
Prof. Dr Slobodanka Đorđević-Kajan
EF Niš, Računarstvo i informatika
RG – Grafički sistemi
4
2008/2009
GIS [email protected]
CG
Algoritmi odsecanja
GIS [email protected]
Algoritmi odsecanja se dele prema sledećim
kriterijumima:
– Prema primitivi koja se odseca
• Tačka
• Linija
• Poligon
– Prema prozoru za odsecanje (clipping window)
• Pravougaoni prozor (paralelan koordinatnim osama)
• Konveksan poligon
• Proizvoljan poligon
Prof. Dr Slobodanka Đorđević-Kajan
EF Niš, Računarstvo i informatika
RG – Grafički sistemi
5
2008/2009
CG
Poligon
GIS [email protected]
 Poligon može biti:
– konveksan ili konkavan
– pozitivno ili negativno orijentisan
 Poligon je konveksan ako linija koja spaja bilo koje dve
tačke unutar poligona leži u poligonu
L – levo
D - desno
D
A
B
B
Prof. Dr Slobodanka Đorđević-Kajan
L
Konkavan
poligon
A
Pozitivno
orijentisan
EF Niš, Računarstvo i informatika
RG – Grafički sistemi
D
C
R
B
E
A
Konveksan
poligon
C
L
B
R
E
A
Negativno
orijentisan
6
2008/2009
CG
Odsecanje tačke
y
wtop
wbottom
wleft
Prof. Dr Slobodanka Đorđević-Kajan
EF Niš, Računarstvo i informatika
RG – Grafički sistemi
wright
x
7
2008/2009
GIS [email protected]
CG
Odsecanje tačke
GIS [email protected]
 Tačka P(x,y) je unutar prozora za
odsecanje ako ispunjava sledeća 4 uslova:
1.
2.
3.
4.
x  wright
x  wleft
y  wtop
y  wbottom
y
wtop
P(x,y)
y
wbottom
wleft
Prof. Dr Slobodanka Đorđević-Kajan
x
wright
x
EF Niš, Računarstvo i informatika
RG – Grafički sistemi
8
2008/2009
CG
Odsecanje linije
F
Prozor za odsecaje
G
Ima više algoritama
Obradićemo dva:
– Algoritam “grube sile”
– Cohen-Sutherland algoritam
Prof. Dr Slobodanka Đorđević-Kajan
EF Niš, Računarstvo i informatika
RG – Grafički sistemi
9
2008/2009
GIS [email protected]
CG
Algoritam grube sile
GIS [email protected]
Računaju se preseci linija sa ivicama prozora
za odsecanje i onda se testira šta je unutar,
a šta van prozora
Nedostaci algoritma: neefikasnost i sporost
F
wtop
wbottom
wleft
Prof. Dr Slobodanka Đorđević-Kajan
G
wright
EF Niš, Računarstvo i informatika
RG – Grafički sistemi
10
2008/2009
Cohen-Sutherland algoritam
odsecanja linije
CG
 Cohen-Sutherland-ov algoritam efikasno rešava problem
odsecanja linija izvan pravougaonog prozora
 Osnovna ideja algoritma:
– Prvo pokušati da se linija u celini prihvatiti ili odbaciti
– Ukoliko se ne uspe u prvom koraku, određuje se presek linije i
produžene ivice prozora
– Ponovo se pokuša prihvatanje ili odbacivanje preostalog dela
linije
Prof. Dr Slobodanka Đorđević-Kajan
EF Niš, Računarstvo i informatika
RG – Grafički sistemi
11
2008/2009
GIS [email protected]
Cohen-Sutherland algoritam
odsecanja linije
CG
Posmatraju se krajnje tačke linija
Uslov trivijalnog prihvatanja linije:
– Obe krajnje tačke linije su unutar prozora odsecanja
Uslov trivijalnog odbacivanja linije:
– Obe krajnje tačke linije su levo od wleft ili desno od wright
iznad wtop ili ispod wbottom
U svim ostalim slučajevima neophodno je
F
izračunavanje preseka
wtop
wbottom
wleft
Prof. Dr Slobodanka Đorđević-Kajan
G
EF Niš, Računarstvo i informatika
RG – Grafički sistemi
wright
12
2008/2009
GIS [email protected]
Cohen-Sutherland Algoritam
CG
(C1 = = 0) & & (C2 = = 0)
odnosno
(C1 | C2) = = 0
Prof. Dr Slobodanka Đorđević-Kajan
EF Niš, Računarstvo i informatika
RG – Grafički sistemi
13
2008/2009
GIS [email protected]
Cohen-Sutherland algoritam
Prof. Dr Slobodanka Đorđević-Kajan
EF Niš, Računarstvo i informatika
RG – Grafički sistemi
CG
14
2008/2009
GIS [email protected]
CG
Cohen-Sutherland algoritam
 U slučaju da linija P1 P2 seče levu
ivicu prozora W presečna tačka P se
y
određuje na sledeći način:
P(wleft, P1.y+dy1)
wbottom
dy=P2.y-P1.y
P
dx=P2.x-P1.x
dy1
P1
dx1=wleft-P1.x
dx
dx1
dy1:dx1=dy:dx => dy1 = (dy:dx) dx1
wleft
 Dobijeni izraz za koordinate tačke P
ne zavisi od položaja tačaka P1 i P2
– bitno je samo da linija P1P2 seče
levu ivicu prozora
Prof. Dr Slobodanka Đorđević-Kajan
EF Niš, Računarstvo i informatika
RG – Grafički sistemi
P2
x
dy
15
2008/2009
GIS [email protected]
Primer
CG
GIS [email protected]
Zadatak: Za prozor xmin=3.0, xmax=6.0, ymin=2.0, ymax=5.0 naći prema
Cohen-Sutherland algoritmu:
1.
Položajne kodove tačaka: A(4,3), B(5,4), C(2,1), D(8,1), E(1,3),
F(5,6), G(5,1), H(9,3)
2.
Uslov trivijalnog odbacivanja proizvoljne linije PQ
3.
Uslov trivijalnog prihvatanja proizvoljne linije PQ
4.
Koji se od sledećih linijskih segmenata mogu trivijalno odbaciti CD,
EF, GH, AE?
Rešenje:
1.
Neka je CP položajni kod tačke P:
CA=0000 CB=0000, CC=0101, CD=0110, CE=0001, CF=1000, CG=0100,
CH=0010
2.
Uslov trivijalnog odbacivanja linijskog segmenta PQ je:
(CP & CQ) != 0
3.
Uslov trivijalnog prihvatanja linijskog segmenta PQ je:
(CP == 0) && (CQ == 0), odnosno (CP | CQ) == 0
4.
Trivijalno se može odbaciti samo linijski segment CD
Prof. Dr Slobodanka Đorđević-Kajan
EF Niš, Računarstvo i informatika
RG – Grafički sistemi
16
2008/2009
CG
Primer
b3 iznad
b2 ispod
b1 desno
b0 levo
A(4,3) 0000
y
CD
EF
GH
AE
F
5
B(5,4) 0000
B
2
C(2,1) 0101
H
D(8,1) 0110
A
E
E(1,3) 0001
G
C
3
D
6
F(5,6) 1000
x
G(5,1) 0100
H(9,3) 0010
Uslov trivijalnog odbacivanja linijskog segmenta PQ je: (CP & CQ) != 0
Uslov trivijalnog prihvatanja linijskog segmenta PQ je: (CP | CQ) == 0
Prof. Dr Slobodanka Đorđević-Kajan
EF Niš, Računarstvo i informatika
RG – Grafički sistemi
17
2008/2009
GIS [email protected]
CG
Odsecanje poligona
GIS [email protected]
 Poligon može biti:
– konveksan ili konkavan
– pozitivno ili negativno orijentisan
 Poligon je konveksan ako linija koja spaja bilo koje dve
tačke unutar poligona leži u poligonu
D
A
B
B
Konveksan
poligon
Prof. Dr Slobodanka Đorđević-Kajan
C
L
Konkavan
poligon
R
B
E
A
L – levo
D - desno
D
C
A
Pozitivna
orijentacija
EF Niš, Računarstvo i informatika
RG – Grafički sistemi
L
B
R
E
A
Negativna
orijentacija
18
2008/2009
CG
Odsecanje poligona
Prozor za odsecanje
[Foley96]:
Prof. Dr Slobodanka Đorđević-Kajan
Primeri odsecanja poligona:
(a) Više komponenti Odsecanjem konkavnog
poligona dobijena su dva
poligona
(b)Prost konveksni slučaj
(c) Konkavni slučaj
EF Niš, Računarstvo i informatika
RG – Grafički sistemi
19
2008/2009
GIS [email protected]
Sutherland-Hodgman-ov algoritam za
poligon - 1
CG
GIS [email protected]
 Algoritam rešava problem odsecanja proizvoljnog poligona
izvan prozora, koji je konveksan poligon
 Koristi se strategija "podeli-pa-savladaj": rešavaju se
elementarni problemi čija kombinacija rešava ceo problem
 Elementaran problem: odsecanje poligona u odnosu na
jednu ivicu prozora za odsecanje
 Ivica prozora za odsecanje je prava – produžena ivica
prozora koji je poligon
 Sukcesivno odsecanje na svim ivicama za odsecanje
daje konačni rezultat
 Rezultat predstavljaju delovi poligona koji pripadaju prozoru,
zatvoreni ivicama prozora
– za razliku od rezultata koji bi se dobio primenom Cohen-Sutherlandovog algoritma
Prof. Dr Slobodanka Đorđević-Kajan
EF Niš, Računarstvo i informatika
RG – Grafički sistemi
20
2008/2009
Odsecanje poligona – Primer 1

CG
GIS [email protected]
Odsecanje poligona se
obavlja sukcesivno,
ivica po ivica :
a)
b)
c)
d)
e)
Stanje pre odcesanja
Stanje nakon
odsecanja po desnoj
ivici prozora
Stanje nakon
odsecanja po donjoj
ivici prozora
Stanje nakon
odsecanja po levoj
ivici prozora
Stanje nakon
odsecanja po gornjoj
ivici prozora
Prof. Dr Slobodanka Đorđević-Kajan
[Foley96]
EF Niš, Računarstvo i informatika
RG – Grafički sistemi
21
2008/2009
CG
GIS [email protected]
Odsecanje poligona – Primer 2
(2) Odsecanje po
donjoj ivici prozora
(1) Odsecanje po desnoj
ivici prozora
(3) Odsecanje po
levoj ivici prozora
(4) Odsecanje po
gornjoj ivici prozora
Rezultat: Poligon sa starim i novim temenima
Prof. Dr Slobodanka Đorđević-Kajan
EF Niš, Računarstvo i informatika
RG – Grafički sistemi
22
2008/2009
Sutherland-Hodgman-ov algoritam za
poligon - 2
CG
GIS [email protected]
 Ako je tačka P(x,y) desno od bilo koje ivice pozitivno
orijentisanog konveksnog poligona, ona je van poligona
 Ako je tačka P(x,y) levo od svih ivica pozitivno
orijentisanog konveksnog poligona ona je unutar poligona
 Kako se izračunava da li je tačka levo ili desno? D
C
L
P(x,y)
A(x1,y1)
Prof. Dr Slobodanka Đorđević-Kajan
B
E
B(x2,y2)
R
A
C=(x2-x1)(y-y1)-(y2-y1)(x-x1)
ako je C>0
tada je tačka P(x,y) je levo od ivice AB
ako je C<0
tada je tačka P(x,y) je desno od ivice AB
EF Niš, Računarstvo i informatika
RG – Grafički sistemi
23
2008/2009
Sutherland-Hodgeman algoritam za
poligon - 3
CG







Poligon koji se iseca je zadat listom temena P1,P2,...,Pn
Prozor odsecanja je pozitivno orijenisani konveksan
poligon
E ivica prozora odsecanja zadata krajnjim tačkama A i B
Iseca se svaka ivica (Pi-1,Pi) poligona i formira se izlazna
lista temena koja definišu novi (isečeni) poligon
Polazi se od ivice (Pn,P1),pa se ide do ivice (Pn-1,Pn)
Ispituje se odnos između susednih temena i ivice
odsecanja i u izlaznu listu dodaju 0, 1 ili 2 temena
Postoje 4 slučaja koje treba posebno analizirati
Prof. Dr Slobodanka Đorđević-Kajan
EF Niš, Računarstvo i informatika
RG – Grafički sistemi
24
2008/2009
GIS [email protected]
CG
GIS [email protected]
4 slučaja isecanja poligona po SutherlandHodgeman-ovom algoritamu za poligon
Prozor odsecanja
unutar
unutar
spolja
spolja
izlaz
izlaz
poligon koji
se odseca
poligon koji
se odseca
izlaz
unutar
[Foley,96]
ivica
odsecanja
ivica
odsecanja
spolja
unutar
spolja
poligon koji
se odseca
poligon koji
se odseca
izlazi
ivica
odsecanja
Prof. Dr Slobodanka Đorđević-Kajan
ivica
odsecanja
EF Niš, Računarstvo i informatika
RG – Grafički sistemi
25
2008/2009
4 slučaja isecanja poligona po SutherlandHodgeman-ovom algoritamu za poligon
CG
E
Pi
E
B
E
B
B
Pi
Pi-1
A
levo desno
A
levo desno
A
levo desno
isečenog
poligona
Ivica poligona je Ivica poligona seče
desno od prozora
ivicu prozora
odsecanja
izlazeći iz prozor
Prof. Dr Slobodanka Đorđević-Kajan
Pi-1
Q
Pi
Q u izlaznu
listu temena
Pi u izlaznu
listu temena
isečenog
poligona
Ivica poligona je
levo od prozora
odsecanja
Pi-1
B
Pi
Q
Pi-1
E
EF Niš, Računarstvo i informatika
RG – Grafički sistemi
A
levo desno
Pi i Q u izlaznu
listu temena
isečenog poligona
Ivica poligona seče
ivicu prozora ulazeći
u prozor
26
2008/2009
GIS [email protected]
Sutherland-Hodgeman algoritam za
poligon - 3
CG

GIS [email protected]
Izlazna lista temena se određuje na sledeći način:
1. Ako su temena Pi-1 i Pi levo od ivice E prozora, teme Pi
se smešta u izlaznu listu temena
2. Ako su temena Pi-1 i Pi desno od ivice E prozora, ništa
se ne smešta u izlaznu listu temena
3. Ako je Pi-1 levo, a Pi desno od ivice E prozora,
izračunava se presek Q linijskog segmenta Pi-1Pi sa
produženom ivicom E i Q se smešta u izlaznu listu
temena
4. Ako je Pi-1 desno, a Pi levo od ivice E, izračunava se
presek Q linijskog segmenta Pi-1Pi sa produženom
ivicom E i u izlaznu listu se unose Q i Pi
Prof. Dr Slobodanka Đorđević-Kajan
EF Niš, Računarstvo i informatika
RG – Grafički sistemi
27
2008/2009
CG
Odsecanje trougla
Prof. Dr Slobodanka Đorđević-Kajan
EF Niš, Računarstvo i informatika
RG – Grafički sistemi
28
2008/2009
GIS [email protected]
CG
Odsecanje proizvoljnog poligona
Prof. Dr Slobodanka Đorđević-Kajan
EF Niš, Računarstvo i informatika
RG – Grafički sistemi
29
2008/2009
GIS [email protected]
CG
Weiler-Atherton algoritam
 Algoritam rešava problem odsecanja proizvoljnog poligona izvan
prozora koji je takođe proizvolja poligon
– Algoritam određuje presek dva proizvoljna poligona
– Oba poligona mogu biti konkavna, mogu sadržati rupe
 Algoritam
– Kreće se od proizvoljnog temena poligona koji se odseca u
pravcu kazaljke na satu
– Prati se ivica poligona koji se odseca do preseka sa ivicom
prozora
– Ako ivica ulazi u prozor, nastavlja se praćenje ivice
poligona koji se odseca
– Ako ivica izlazi iz prozora, skreće se desno i nastavlja
ivicom prozora kao da je on poligon koji se odseca, a
originalni poligon prozor
– Pamte se tačke preseka da bi se obezbedilo da se svi putevi
pređu samo jednom
Prof. Dr Slobodanka Đorđević-Kajan
EF Niš, Računarstvo i informatika
RG – Grafički sistemi
30
2008/2009
GIS [email protected]
CG
GIS [email protected]
Weiler-Atherton algoritam - Primer
Polazna tačka
Ako ivica
ulazi u
prozor,
nastavlja se
praćenje
ivice
poligona
Prof. Dr Slobodanka Đorđević-Kajan
EF Niš, Računarstvo i informatika
RG – Grafički sistemi
Ako ivica
izlazi iz
prozora,
skreće se
desno i
nastavlja
ivicom
prozora
kao da je on
poligon
31 koji
2008/2009 se odseca
Odsecanje kruga i elipse
Prof. Dr Slobodanka Đorđević-Kajan
EF Niš, Računarstvo i informatika
RG – Grafički sistemi
CG
32
2008/2009
GIS [email protected]
Odsecanje kruga i elipse
Prof. Dr Slobodanka Đorđević-Kajan
EF Niš, Računarstvo i informatika
RG – Grafički sistemi
CG
33
2008/2009
GIS [email protected]
Kviz I samostalni rad
CG
Kviz
– Šta je to odsecanje, a šta preklapanje?
– Kakvu ulogu igraju segmenti?
Samosalni rad
– Nacrati nekoliko objekata i segementirati ih
– Izvršiti operacije odsecanja i preklapanja
Prof. Dr Slobodanka Đorđević-Kajan
EF Niš, Računarstvo i informatika
RG – Grafički sistemi
34
2008/2009
GIS [email protected]
Download

Odsecanje (clipping) objekata