clipping e facce nascoste

clipping (taglio ai bordi)
e
facce nascoste
clipping e facce nascoste
visualizzazione da 3D a 2D e poi su schermo:
eliminazione delle parti che escono dalla scena
o dal volume di visualizzazione: clipping
eliminazione delle parti che non sono visibili:
rimozione delle superfici nascoste
proiezione sul piano di vista
trasformazione dell'immagine da finestra utente
a finestra dispositivo
clipping e facce nascoste
eliminazione delle parti che escono dalla scena o dal
volume di visualizzazione: clipping
nella figura sotto a sinistra le parti fuori scena sono
eliminate, resta quanto a destra:
clipping e facce nascoste
casi possibili:
a) entrambi vertici dentro nella finestra
b) un vertice dentro, un vertice fuori
c) entrambi i vertici fuori: necessario un controllo piu'
accurato: caso c1 (parte dentro), c2 e c3 (tutto fuori)
c3
a
b
c1
a
c2
b
c1
clipping e facce nascoste
nel caso c) con entrambi i vertici fuori e' necessario un
controllo piu' accurato:
caso c1 (parte dentro), c2 e c3 (tutto fuori)
per distinguere i sottocasi devo trovare le intersezioni
del segmento (ad es. c2) con le rette che formano la
finestra di clipping, e poi stabilire dove si trovano
... metodo inefficiente, non si usa.
c3
a
b
c1
a
c2
b
c1
clipping e facce nascoste
schema per clipping piu' veloce: si assegna un bit per le
regioni definite dalle 4 rette limite della finestra:
bit 1 per y>ymax (sopra),
1001
1000
1010
bit 2 per y<ymin (sotto)
X
bit 3 per x>xmax (destra)
0001
0000
0010
bit 4 per x<xmin (sinistra)
b
(sono i bit del segno di
ymax-y, y-ymin, xmax-x, ..)
0101
0100
0110
si nota inoltre che se l'AND
dei codici degli estremi != 0 , allora gli estremi stanno nello
stesso settore->il segmento sta tutto fuori;
se l'AND dei due codici ==0 allora calcolo l'intersezione (ad
es. per il segm.b trovo il punto X) ed elimino uno delle due
parti del segm (con il test dei 4 bit) [Algor.Cohen-Sutherland]
clipping poligoni
caso poligoni : il clipping viene fatto
mantenendo unito il contorno; si
noti la differenza tra clipping di
singoli segmenti che formano il
poligono (sotto,sinistra) e clipping
del poligono come spezzata continua
connessa (sotto,destra)
non riportiamo gli algoritmi per questo problema
(algor. di Sutherland - Hodgman, Weiler Atherton, ...)
clipping
menzioniamo solamente altri problemi di clipping:
clipping di figure generiche delimitate da curve
generiche (es. ellisse)
clipping di testo (clipping a livello
di stringa,
di singolo carattere,
di parti di singolo carattere)
Line clipping: Sproull-Sutherland '68,
Liang-Barsky '84, Nicholl-Lee-Nicholl '87,
Poligon clipping: Sutherland Hodgman '74,
Liang-Barsky 83, Weiler Atherton '74
operazioni logiche su due
figure geometriche: A op B
un algoritmo di calcolo del
contorno di un operazione
logica tra due figure
geometriche piane e' stato
sviluppato per un progetto
di "macchina visuale" nel
'77, programma "matrix",
(Zajec-Hmeljak) qui a
destra; nella fig. in alto a
sinistra e' visibile l'xor tra
due figure irregolari, in
basso a destra l'and, a
sinistra il clipping
xor
diff
and
clip
clipping 3D poliedri
lo stesso problema del mantenere la
connessione dei lati di un poligono si
presenta nel caso 3D per oggetti solidi
con faccie piane (cubo, poliedro, cono,
ecc);
problemi posti e risolti negli anni 60-70
in OpenGL e' possibile specificare
altri piani di clipping (oltre il frustum),
con apposita procedura:
glClipPlane( id, planeParameters);
glEnable(id);
id e' GL_CLIP_PLANEk (k=0,1,2.., nCP
il numero mass. di piani di clipping si ha
con glGetIntegerv(GL_MAX_CLIP_PLANES, numPlanes);
facce nascoste
dopo la fase di clipping che elimina tutti gli oggetti
che stanno fuori della finestra (o spazio) di
visualizzazione, e elimina le parti di oggetti che
sono in parte dentro in parte fuori scena, rimane il problema rimozione delle superfici nascoste
risale agli anni 60;
esistono molti algoritmi per risolverlo,
I.Sutherland, R.Sproull, R.Shumacker: A Characterization of Ten HiddenSurface Algorithms, Computing Surveys, ACM, vol.6,nr.1, 1974, p.1-55
vediamo alcuni ...
facce nascoste
un primo aspetto e' l' eliminazione delle
facce di un oggetto che stanno DIETRO, e
che sicuramente NON sono visibili:
questa prima selezione di eliminazione si
dice culling,
che significa ...
culling
cull |kəl| |kəl| |kʌl|verb [ trans. ] (usu. be culled)
select from a large quantity; obtain from a
variety of sources : anecdotes culled from
Greek and Roman history.
reduce the population of (a wild animal) by
selective slaughter : he sees culling deer as a
necessity | [as n. ] (culling) kangaroo culling.
send (an inferior or surplus animal on a farm)
to be slaughtered.
poetic/literary pick (flowers or fruit) : [as adj. ]
(culled) fresh culled daffodils.
[ selezionare, scegliere, cernire, scremare ]
facce nascoste
aspetto del culling per
oggetto singolo: eliminare le
facce nascoste, non visibili; CP
oggetto
si basa sull' angolo tra il
V
vettore V Centro Proiezione
a
- faccia e la normale N
N
(orientam.bordo anti-orario)
alla faccia volta verso
" culling "
l'esterno; sono eliminate
tutte le facce con angolo >
900 (sono le facce posteriori,
"dietro", che sono
ovviamente coperte dalle
facce davanti)
OpenGL culling
OpenGL culling:
glEnable( GL_CULL_FACE);
glCullFace(mode); // mode =
GL_BACK,GL_FRONT ...
glDisable( GL_CULL_FACE);
rimozione facce posteriori
il sistema OpenGL prevede una procedura per
specificare le normali alle primitive,
glEnable(GL_NORMALIZE);
// per avere le normali unitarie (piu'veloce)
glNormal3fv(normalVector);
glBegin(GL_TRIANGLES);
glVertex3fv(vert1); ... ; glVertex3fv(vert3);
glEnd();
...
la possibilita' di specificare il verso "esterno" /
"interno" con scelta CCW o CW (clockwise) ...
normale a poligono
se P1, P2, P3 sono tre vertici di un poligono
(orientato antiorario), e se V1=(P2-P1) =(x1,y1,z1),
e V2=(P3-P2) = (x2,y2,z2) allora la normale e ' data
dal prodotto vettoriale N = V1 ^ V2
che e' dato dalla matrice a destra, che da':
ux uy uz
Nx = y1*z2-z1*y2,
x1 y1 z1
Ny = x1*z2-z1*x2, e
Nz = x1*y2-y1*x2
x2 y2 z2
Caso in cui non so come sono orientati i poligoni
devo fare un test aggiuntivo per saper la direzione
della normale
(ad es. calcolo il prodotto scalare N*B tra la N Normale al
poligono e B vettore Baricentro Oggetto - Punto del
Poligono)
piu' complesso e piu' rilevante e' il
problema delle superfici di un oggetto
nascoste da altri oggetti,
cioe' l'
eliminazione delle faccie nascoste
facce nascoste
caso di piu' oggetti: due
gruppi di algoritmi di
rimozione delle facce
nascoste perche' coperte
da altri oggetti: un
primo gruppo lavora
nello spazio degli oggetti
(object-space methods)
ogni faccia (ogni primitiva) di un oggetto viene
confrontata con tutte le facce (le primitive) dell'altro
oggetto (se ho 2 oggetti); la complessita' di tale
approccio e' k2, se k e' il numero complessivo delle
faccie
facce nascoste
object-space methods:
lavoro nello spazio degli
oggetti, dove ogni faccia
(ogni primitiva) di un
oggetto viene confrontata
con tutte le facce (le
primitive) dell'altro oggetto
(se ho 2 oggetti); i casi
possibili sono quelli in
figura:
posizioni reciproche di
due primitive geometriche
poligono A
copre B
A e B disgiunti
A copre B
parzialmente
B copre A
parzialmente
poligono B
copre A
facce nascoste: image-space methods
un'altra famiglia di algoritmi
per la rimozione delle facce
nascoste si basa su dei
test - pixel per pixel - di quale
faccia e' visibile per quel pixel;
le facce devono esser ordinate,
i test per ogni pixel implicano un
test su ogni faccia/ogni oggetto
intersecato dal raggio,
se ho nx * ny pixel e k oggetti, in totale nx * ny * k test
"most visible-surface algorithms use image-space
methods" (Hearn-Baker) ... vedremo in seguito ...
facce nascoste
a tutti gli algoritmi usati per la rimozione delle faccie
nascoste si aggiungono procedimenti per ottimizzare
la velocita':
primo l' ordinamento degli oggetti della scena
rispetto la distanza dal piano di proiezione (asse z),
suddivisione della scena in regioni omogenee, per
ridurre il numero dei confronti oggetto-oggetto o
faccia-faccia necessari, e non ripetere test gia' fatti;
infine, spesso sono usati algoritmi ibridi,
una prima fase con metodi image-space (ottimizzati),
poi per i dettagli vengono usati metodi object-space,
algoritmo del pittore
l'algoritmo del pittore usa la
stessa tecnica dei pittori su
tela: prima vengono
disegnati gli oggetti piu'
lontani (lo sfondo) e poi via
via gli oggetti piu' vicini;
dalla scena iniziale (sopra)
elimino le facce posteriori (4
su 7 !),ho la scena in mezzo;
ordino secondo le z (1 faccia
piu' lontana, 6 piu'vicina);
ora disegno ...
algoritmo del pittore:
a) situazione dopo ordinamento, b) dopo tracciate le facce 1,2,3;
c) dopo le prime 4,
d) alla fine
algoritmo del pittore
funziona in alcuni casi, ma ...
nota:
nel caso di oggetti tracciati per
linee "a fil di ferro" (wire-frame)
l'algor.del pittore deve essere
modificato: non e' sufficente
tracciare i poligoni in ordine
inverso (partendo dallo sfondo),
perche' sono solo contorni:
devo calcolare le intersezioni, e
ricostruire le parti rimanenti del
poligono in modo che rimanga
una linea chiusa (problema come
nel caso del clipping)
A
B
A1
B
A2
algoritmo del pittore
funziona in alcuni casi,
ma non sempre ...
un' osservazione:
circolare
caso di figure ambigue talvolta non si riesce a ordinare
gli oggetti secondo profondita': in
figura due situazioni non
ordinabili secondo le z:
per i tre poligoni sopra c'e' un
ricoprimento circolare,
i due solidi sotto sono
compenetrati ...
vediamo una soluzione ...
compenetrati
algoritmo del pittore
l'ordinamento delle facce dei
poligoni puo' esser fatto ad es.
considerando i baricentri delle
facce - metodo che talvolta
presenta problemi (errori)
residui,
vedi gli esempi a fianco: i tre
rettangoli hanno il baricentro
alla stessa distanza z, ma il
rettangolo A e' inclinato, e sta
dietro B e davanti C; in tal caso
devo esaminare la situazione
lato per lato (vedremo)
B
C
A
vista di fronte
B
A
vista da fianco
C
algoritmo del pittore
un po' piu' in dettaglio:
1) disegna oggetto ovvero tutte le faccie dell'oggetto
-> clipping 3D (elimina faccie fuori scena)
-> faccia nascosta (posteriore) ->si, elimina
-> visibile -> proiezione di x e y: (x,y,z)->(xp,yp,z)
-> memorizza faccia in ListaCompletaFacce
2) alla fine dell'oggetto ordina le faccie secondo le z
(complessita' n*log(n) ) [*] pagina seguente
3) trasforma da coordinate mondo a coordinate
schermo
4) disegna ovvero salva in display file
sequenza gia' presente in GKS, Core e Phigs ...
algoritmo del pittore / 3D viewing pipeline
questo procedimento:
// disegna oggetto / clipping 3D / culling / proiezione /
sort secondo le z / coordinate schermo //
e'parte della catena di visualizzazione della grafica:
coordinate modello -> Modelling Transform ->
coordin.scena ("world") -> Viewing Transf(LookAt)->
coord.vista (PtoVista, PianoProiez) -> ProjectionTrans->
coord.nel piano proiez.(piu'z) -> Normaliz.Trans->
coord.normalizzate nel piano -> Clipping ->
coord.normalizzate -> Viewport -> coord.schermo
algoritmo del pittore / triangolarizzazione ...
un esempio di procedimento
per l'ordinamento su z dei
poligoni basato sui triangoli:
trasforma i poligoni in triangoli
(crea lista completa triangoli)
poi confronta i triangoli a due a
due (vedi pag.seguente) e crea
sottoliste "triangoli dietro a.."
disegna poi i triangoli che non
precedono nessuno (dietro a
tutti) e cancella da lista, procedi
finche' la lista triangoli diventa
vuota...
algoritmo del pittore / triangolarizzazione ...
trasformare i poligoni in triangoli (crea lista completa
triangoli) non e' sempre immediato: nel procedimento di
triangolarizzazione (da A a B) possono verificarsi triangoli
degeneri (C) e poligoni non convessi
D - ok , E - non ok :
(C)
(A)
(B)
(D)
(E)
algoritmo del pittore / confronto di due triangoli
ordinamento di triangoli: considero
solo i triang. che si intersecano;
per decidere se due triangoli si
intersecano (test di copertura
parziale): test preliminare dei
min/max dei due triangoli (A), se i
rettangoli circoscritti si intersecano,
test successivo (ogni lato di un
triang con ogni lato dell'altro) (casi B
e C)
B)
A)
C)
algoritmo del pittore / confronto di due triangoli
rimane il caso di due triangoli con lati che non si intersecano ,
come nelle due figure a sinistra A) e a destra C): in tal caso
eseguo ancora il test T1 dentro T2 e T2 dentro T1 (basta
test se un punto di T1 sta dentro T2)
A)
C)
algoritmo del pittore / confronto di due segmenti
A
B
C
anche per il test di intersezione di due segmenti (lati di
un poligono) si procede con test preliminari min/max dei
rettangoli circoscritti: se non c'e' intersezione (caso A) il
test e' finito, se invece c'e' possibilita' di intersezione
(casi B e C) allora si procede ad un test piu' accurato
(calcola intersezione)
algoritmo del pittore / confronto di due segmenti
test di intersezione di due segmenti per stabilire la precedenza
(davanti/dietro):
test preliminari min/max dei rettangoli circoscritti:
se c'e' possibilita' di intersezione (casi B e C) allora si procede ad
un test piu' accurato:
dopo il calcolo dell'intersezione si confrontano le
coordinate z nel punto di intersezione (siamo nel piano
di proiezione xp,yp per le coordinate x,y, ma abbiamo
conservato le z) e quindi si stabilisce l'ordine di
precedenza in base alle z; se le z sono uguali, si
procedera' ad un altro punto di intersezione...
il procedimento non risolve il caso di triangoli
conpenetranti, ed e' comunque abbastanza pesante...
algoritmo del pittore - superfici/linee nascoste
l'algoritmo del pittore (un po'modificato) risolve anche
il problema del disegno di oggetti con solo controrno
(wire-frame),
non andiamo nel dettaglio dell'algoritmo di disegno di
oggetti visualizzati solo con le linee di contorno, con
rimozione delle linee nascoste; prima di dare le linee
generali dell'algoritmo,
in omaggio ai colleghi che hanno lavorato su questo
tema negli anni 70, presentiamo la slide seguente;
e' un risultato di un programma "PerPic" su una
superficie particolare; il programma era scritto in
Fortran4, su un Control Data 6400 a dischi, nastri e
schede perforate, multiprogrammato, uso batch.
Perpic
(Carminelli e
Policastro)
(un programma
per il disegno
prospettico con
eliminaz. delle
linee nascoste)
riprendiamo l' algoritmo del pittore
dati n triangoli per eseguire il disegno in ordine dal piu'
lontano al piu' vicino devo :
per tutti i triangoli k da 1 a n
per il triangolo k confronto k con
tutti i triangoli j da 1 a n (escluso k)
per vedere se c'e' intersezione -possibl ricoprimento
per ogni triangolo k creo due liste di triangoli,
una sono i Tj che intersecano e precedono il Tk
(stanno davanti il Tk)
l'altra sono i Tj che intersecano e seguono il Tk
(stanno dietro Tk)
poi vado a disegnare tutti i triangoli, inizio da quelli con
lista Tj seguenti (dietro) vuota: cioe' disegno prima il Tk
che sta dietro a tutti, e lo elimino dalle liste ...
algoritmo del pittore - ordinamento e disegno
uso delle liste precedente / seguente:
0) lista triangoli
con sottoliste:
a sinistra davanti,
a destra dietro
|
|1|
|
|2|
| 5 1 |3|
|
2 |4|
|
6 |5|
| 1 2 |6|
|6 4 2 |7|
3 6
|
7 6 4 |
|
7
|
3
|
7 5
|
|
1) i triangoli 3 e 7
non hanno altri
triangoli dietro, li
disegno, e li tolgo
dalle liste;
|
|
|
|
|
|1| 6
|2| 6 4
2 |4|
6 |5|
1 2 |6| 5
1
1
5
|1| 3 6
|2| 6
1 2 |6|
7
3
1
5
6
6
4
|
|
|
3
3
2
|
|
|
|
|
2) dopo 3 e 7, ho 4 e
5 senza tri. dopo, li
posso disegnare, e li
tolgo dalle liste
4
2
5
6
7
4
2
7
|
|
|
algoritmo del pittore - ordinamento e disegno
uso delle liste precedente / seguente:
0) lista triangoli
con sottoliste:
a sinistra davanti,
a destra dietro
|
|1|
|
|2|
| 5 1 |3|
|
2 |4|
|
6 |5|
| 1 2 |6|
|6 4 2 |7|
3 6
|
7 6 4 |
|
7
|
3
|
7 5
|
|
2) dopo 3 e 7, ho 4 e
5 senza triangoli
dopo, li posso disegnare, e li tolgo
dalle liste
|
|
|
|1 | 6
|2 | 6
1 2 |6|
1
1
5
|1 |
|2 |
7
2
4
5
1
2
5
6
7
|
|
3
6
6
2
|
|
3
3
4
|
|
|
3) ora ho il triang.
6 senza tri. dietro,
lo disegno e lo
elimino:
2
4
2
7
algoritmo del pittore - ordinamento e disegno
uso delle liste precedente / seguente:
0) lista triangoli
con sottoliste:
a sinistra davanti,
a destra dietro
|
|1|
|
|2|
| 5 1 |3|
|
2 |4|
|
6 |5|
| 1 2 |6|
|6 4 2 |7|
3 6
|
7 6 4 |
|
7
|
3
|
7 5
|
|
3) ora ho il triang.
6 senza tri. dietro,
lo disegno e lo
elimino:
|
|
|1 |
|2 |
|
|
4) rimangono infine
solo i due triangoli
1 e 2 (senza tri.
dietro) che sono
disegnati e tolti
dalle liste - ora le
liste sono vuote,
abbiamo finito.
3
3
1
1
5
3
1
5
6
5
6
6
4
7
2
2
4
2
7
7
4
2
depth-buffer o z buffer
il procedimento piu' usato e' quello del depth buffer o z-buffer,
che riportiamo brevemente:
gli oggetti cambiano sistema di riferimento da mondo del singolo
oggetto M (xm,ym,zm) (modelling) a mondo scena (xv,yv,zv)
(view) poi sono proiettati sul piano di proiezione (xp,yp,zv)
(projection) ma sono conservate le z (zv view) senza
modifica; le coordinate (xp,yp,zv) sono infine normalizzate e
trasformate in coordinate display (xd,yd,zv) (x,y in pixel);
ora, per rimuovere le parti nascoste:
si usano due memorie di display, una (display buffer) contiene
per ogni pixel il colore C dell'oggetto M visibile in quel pixel,
l'altra (depth buffer o z-buffer) contiene la z (profondita') del
punto di M corrispondente a quel pixel;
depth-buffer o z buffer
si usano due memorie di display, il display buffer contiene per
ogni pixel il colore C dell'oggetto M visibile in quel pixel,
il depth buffer o z-buffer contiene la z (profondita') del punto
dell' oggetto M corrispondente a quel pixel;
inizialmente il display buffer contiene il colore dello sfondo
e il z-buffer contiene la z massima (negativa) possibile;
in figura inserisco una primitiva a profondita' costante nel z-buffer vuoto
- le nuove z coprono le zmax inizialmente presenti nel z-buffer:
xxxxxxx
xxxxxxx
xxxxxxx
xxxxxxx
xxxxxxx
z-buffer
+
555555
55555
5555
555
55
primitiva
=
555555
55555x
5555xx
555xxx
55xxxx
z-buffer
se ora inserisco altre figure per ogni pixel si confrontano le z -
depth-buffer o z buffer
display buff. contiene il colore C dell'oggetto M visibile nel pixel,
z-buff. contiene la z del punto dell'oggetto M corrisp. a quel pixel
xxxxxxx
xxxxxxx
xxxxxxx
xxxxxxx
xxxxxxx
+
555555
55555
5555
555
55
=
555555x
55555xx
5555xxx
555xxxx
55xxxxx
z-buffer iniz
qui primitiva a profondita' costante
555555x
55555xx
5555xxx
555xxxx
55xxxxx
+
6789
56789
456789
3456789
2345678
=
555555x
55555xx
455589x
3456789
2345678
qui caso di primitiva a profondita' (nero)
costante che si interseca con primitiva a
profondita' non costante (rosso)
per ogni nuovo oggetto che viene disegnato, [[ pipeline da
(xm,ym,zm) a (xp,yp,zv) ]] si confronta pixel per pixel la zvb gia'
presente nel z-buff. con la zvo del nuovo oggetto: se la zvo < zvb
allora il nuovo pixel copre quello gia' disegnato nel display buffer
(colore nuovo), e la nuova zvo entra nel z-buffer al posto della
precedente; i pixel sono scelti con il procedimento scan-line che
procede su una orizzontale dal primo pixel coinvolto dall' oggetto
all'ultimo (in una riga) (sfrutto la coerenza di pti vicini).
eliminazione linee e facce nascoste
e con questa figura termina il
capitolo sulla eliminazione
delle linee e delle
faccie nascoste