|
|
|
cignoni@iei.pi.cnr.it |
|
http://vcg.iei.pi.cnr.it/~cignoni |
|
|
|
|
|
|
Clipping di segmenti |
|
Algoritmo di Cohen-Sutherland |
|
Clipping di poligoni |
|
Algoritmo di Sutherland-Hodgman |
|
Eliminazione linee nascoste |
|
|
|
|
Sino ad adesso abbiamo ignorato che lo schermo
(la finestra dell’applicazione) fosse una superficie discreta ma di
dimensione finita |
|
Questo comporta la necessità di fare clipping
delle primitive che si rasterizzano |
|
Fare clipping significa identificare le porzioni
della primitiva che sono visibili e quelle che non lo sono |
|
|
|
|
Il problema del clipping è genericamente
risolvibile per qualunque superficie chiusa |
|
A noi però interessa risolvere solo il problema
di fare clipping su rettangoli, dato che le porzioni di schermo che
l’applicazione gestisce sono rettangoli |
|
|
|
|
Un punto si trova all’interno del rettangolo di
clipping se sono soddisfatte le 4 disuguaglianze: |
|
|
|
|
|
Qualora una qualsiasi di queste
disuguaglianze non valesse il punto è al di fuori del rettangolo di
clipping |
|
|
|
|
|
Per fare il clipping di un segmento, si
considera la posizione dei suoi punti estremi: |
|
Se i due punti sono entrambi dentro, l’intero
segmento lo è |
|
Se un punto è dentro e uno fuori il segmento
interseca il rettangolo e si deve calcolare l’intersezione |
|
Se entrambi i punti sono fuori dal rettangolo il
segmento può o non può intersecare il rettangolo e si devono fare altri
calcoli per determinare se le intersezioni ci sono, e se ci sono dove sono |
|
|
|
|
Se i due punti sono entrambi dentro, l’intero
segmento (AB) lo è |
|
|
|
|
Se un punto è dentro e uno fuori il segmento
(CD) interseca il rettangolo e si deve calcolare l’intersezione (D’) |
|
|
|
|
Se entrambi i punti sono fuori dal rettangolo
(EF, GH, IJ) il segmento può o non può intersecare il rettangolo e si
devono fare altri calcoli per determinare se le intersezioni ci sono, e se
ci sono dove sono |
|
|
|
|
L’approccio più diretto alla soluzione del
problema sarebbe quello di fare il calcolo delle intersezioni tra la retta
su cui giace il segmento e le 4 rette su cui giacciono i lati del
rettangolo di clipping |
|
|
|
|
Una volta individuati i punti di intersezione
verificare poi se essi appartengono effettivamente al segmento ed al lato
(G¢ e H¢) oppure no (I¢ e J¢). |
|
|
|
|
Questo calcolo si può facilmente compiere
utilizzando l’equazione parametrica della retta: |
|
|
|
|
Le rette si intersecano se, dopo aver risolto
contemporaneamente i due insiemi di equazioni che descrivono il segmento ed
il lato in tlato e tsegm i due valori rientrano
entrambi nell’intervallo [0, 1] |
|
|
|
|
Si dovrebbe inoltre verificare in anticipo se
per caso le linee sono parallele prima di calcolare l’intersezione |
|
Un algoritmo del genere funziona ma è costoso e
quindi inefficiente |
|
|
|
|
L’algoritmo di clipping di Cohen-Sutherland si
basa su un approccio completamente diverso |
|
La considerazione di base che si fa è che le
rette che delimitano il rettangolo che definisce la regione di clipping
suddividono il piano in nove regioni |
|
|
|
|
La considerazione di base che si fa è che le
rette che delimitano il rettangolo che definisce la regione di clipping
suddividono il piano in nove regioni |
|
|
|
|
Ad ogni regione viene associato un codice
numerico di quattro cifre binarie |
|
|
|
|
Il codice è formato da 4 bit, vero o falso: |
|
|
|
bit 1 sopra l’edge in alto y > ymax |
|
bit 2 sotto l’edge in basso y < ymin |
|
bit 3 a dx dell’edge di dx x > xmax |
|
bit 4 a sx dell’edge di sx x < xmin |
|
|
|
|
|
|
Il codice è formato da 4 bit, vero o falso: |
|
|
|
bit 1 sopra l’edge in alto y > ymax |
|
bit 2 sotto l’edge in basso y < ymin |
|
bit 3 a dx dell’edge di dx x > xmax |
|
bit 4 a sx dell’edge di sx x < xmin |
|
|
|
|
|
|
Il codice è formato da 4 bit, vero o falso: |
|
|
|
bit 1 sopra l’edge in alto y > ymax |
|
bit 2 sotto l’edge in basso y < ymin |
|
bit 3 a dx dell’edge di dx x > xmax |
|
bit 4 a sx dell’edge di sx x < xmin |
|
|
|
|
|
|
Il codice è formato da 4 bit, vero o falso: |
|
|
|
bit 1 sopra l’edge in alto y > ymax |
|
bit 2 sotto l’edge in basso y < ymin |
|
bit 3 a dx dell’edge di dx x > xmax |
|
bit 4 a sx dell’edge di sx x < xmin |
|
|
|
|
|
|
Il codice è formato da 4 bit, vero o falso: |
|
|
|
bit 1 sopra l’edge in alto y > ymax |
|
bit 2 sotto l’edge in basso y < ymin |
|
bit 3 a dx dell’edge di dx x > xmax |
|
bit 4 a sx dell’edge di sx x < xmin |
|
|
|
|
|
|
Con queste premesse l’operazione di clipping si
risolve con opportune codifiche e confronti tra codici numerici |
|
|
|
|
Per fare il clipping di un segmento si
codificano i suoi punti estremi sulla base della regione del piano a cui
appartengono e poi si confrontano i due codici |
|
|
|
|
Se il codice di entrambi i punti estremi è 0000,
allora si può banalmente decidere che il segmento è interamente all’interno |
|
|
|
|
Altrettanto banalmente si può decidere che un
segmento è tutto all’esterno quando l’operazione di AND logico tra i codici
dei due punti ha un risultato diverso da 0 |
|
|
|
|
In questo caso, infatti, entrambi i punti stanno
in uno stesso semipiano (quello identificato dal bit a 1 del risultato) e
quindi il segmento non interseca il rettangolo di clipping |
|
|
|
|
Se il risultato dell’AND è invece 0000 |
|
|
|
|
|
Se il risultato dell’AND è invece 0000 |
|
si cerca quale dei due punti estremi giace fuori
dal rettangolo (almeno uno lo è) |
|
|
|
|
|
Se il risultato dell’AND è invece 0000 |
|
si cerca quale dei due punti estremi giace fuori
dal rettangolo (almeno uno lo è) |
|
si suddivide il segmento in due parti calcolando
l’intersezione del segmento con i bordi del rettangolo |
|
|
|
|
|
Se il risultato dell’AND è invece 0000 |
|
si cerca quale dei due punti estremi giace fuori
dal rettangolo (almeno uno lo è) |
|
si suddivide il segmento in due parti calcolando
l’intersezione del segmento con i bordi del rettangolo |
|
una si scarta (poiché giace fuori dal
rettangolo) e si itera il procedimento |
|
|
|
|
|
Se il risultato dell’AND è invece 0000 |
|
si cerca quale dei due punti estremi giace fuori
dal rettangolo (almeno uno lo è) |
|
si suddivide il segmento in due parti calcolando
l’intersezione del segmento con i bordi del rettangolo |
|
una si scarta (poiché giace fuori dal
rettangolo) e si itera il procedimento |
|
|
|
|
|
Se il risultato dell’AND è invece 0000 |
|
si cerca quale dei due punti estremi giace fuori
dal rettangolo (almeno uno lo è) |
|
si suddivide il segmento in due parti calcolando
l’intersezione del segmento con i bordi del rettangolo |
|
una si scarta (poiché giace fuori dal
rettangolo) e si itera il procedimento |
|
|
|
|
|
Fare clipping di un poligono è un’operazione più
complessa che farlo di un segmento dato che i casi da trattare sono vari e
diversi tra loro |
|
Poligono convesso |
|
|
|
|
Fare clipping di un poligono è un’operazione più
complessa che farlo di un segmento dato che i casi da trattare sono vari e
diversi tra loro |
|
Poligono concavo che clippato si divide |
|
|
|
|
Fare clipping di un poligono è un’operazione più
complessa che farlo di un segmento dato che i casi da trattare sono vari e
diversi tra loro |
|
Poligono con molti spigoli esterni |
|
|
|
|
L’approccio iniziale di soluzione potrebbe
essere quello di confrontare ogni lato del poligono con le 4 rette che
delimitano il rettangolo di clipping |
|
|
|
|
Un approccio di questo tipo porta a compiere
molte operazioni (costose quali i calcoli di intersezioni) di cui una gran
parte possono essere inutili |
|
|
|
|
L’idea alla base dell’algoritmo di
Sutherland-Hodgman è applicare una strategia risolutiva del tipo divide et
impera |
|
Il problema viene così ricondotto a quello di
calcolare il clipping di un poligono qualsiasi rispetto ad una retta |
|
|
|
|
L’applicazione, in successione, della procedura
alle 4 rette che definiscono il rettangolo di clipping avrà come risultato
il clipping del poligono sul rettangolo |
|
|
|
|
L’algoritmo riceve in ingresso una serie di
vertici v1, v2,¼,vn che definiscono n spigoli: gli n-1 da vi a vi+1
e quello da vn a v1 |
|
Dopo aver fatto clipping su una retta ritorna in
output un’altra serie di vertici che definiscono il poligono clippato |
|
|
|
|
Il confronto si effettua scandendo il poligono
in senso orario partendo dal vertice vn fino a v1 per
poi tornare a vn |
|
Per ogni passo si confronta la relazione
esistente tra due vertici successivi e la retta di clipping |
|
Per ogni caso i vertici indicati con verranno inseriti nella lista di output |
|
|
|
|
|
Le relazioni possono essere di 4 tipi: |
|
Spigolo tutto interno |
|
|
|
|
|
Le relazioni possono essere di 4 tipi: |
|
Spigolo tutto interno |
|
Spigolo uscente |
|
|
|
|
|
Le relazioni possono essere di 4 tipi: |
|
Spigolo tutto interno |
|
Spigolo uscente |
|
Spigolo tutto esterno |
|
|
|
|
|
Le relazioni possono essere di 4 tipi: |
|
Spigolo tutto interno |
|
Spigolo uscente |
|
Spigolo tutto esterno |
|
Spigolo entrante |
|
|
|
|
Vediamo come opera l’algoritmo nel caso in
figura |
|
I vertici in nero sono gli originali, quelli in
arancio sono originati dall’algoritmo di clipping sulla retta rossa |
|
|
|
|
Vediamo come opera l’algoritmo nel caso in
figura |
|
I vertici in nero sono gli originali, quelli in
arancio sono originati dall’algoritmo di clipping sulla retta rossa |
|
|
|
|
Vediamo come opera l’algoritmo nel caso in
figura |
|
I vertici in nero sono gli originali, quelli in
arancio sono originati dall’algoritmo di clipping sulla retta rossa |
|
|
|
|
Vediamo come opera l’algoritmo nel caso in
figura |
|
I vertici in nero sono gli originali, quelli in
arancio sono originati dall’algoritmo di clipping sulla retta rossa |
|
|
|
|
Vediamo come opera l’algoritmo nel caso in
figura |
|
I vertici in nero sono gli originali, quelli in
arancio sono originati dall’algoritmo di clipping sulla retta rossa |
|
|
|
|
Vediamo come opera l’algoritmo nel caso in
figura |
|
I vertici in nero sono gli originali, quelli in
arancio sono originati dall’algoritmo di clipping sulla retta rossa |
|
|
|
|
Una cosa da tenere di conto sarà l’eventualità
che in output dall’algoritmo si possano ottenere dei lati che si
sovrappongono ai bordi del rettangolo di clipping |
|
Tali lati si possono generare quando un poligono
si divide in due |
|
È necessario allora aggiungere una fase di
post-processing all’algoritmo per eliminarli |
|
|
|
|
|
Il problema della rimozione delle superfici
nascoste consiste nel determinare se un oggetto è visibile all’osservatore,
oppure rimane oscurato da altri oggetti della scena |
|
Non è quindi un problema legato solo alla
disposizione degli oggetti nella scena, ma alla relazione che esiste tra
oggetti e posizione dell’osservatore |
|
|
|
|
|
Gli algoritmi per la rimozione delle superfici
nascoste si possono dividere in due classi: |
|
gli algoritmi object-space determinano, per ogni
oggetto, quali parti dell’oggetto non sono oscurate da altri oggetti nella
scena |
|
gli algoritmi image-space determinano, per ogni
pixel, quale è l’oggetto più vicino all’osservatore |
|
|
|
|
Data una scena tridimensionale composta da n
poligoni piatti ed opachi, si può derivare un generico algoritmo di tipo
object-space considerando gli oggetti a coppie |
|
|
|
|
|
Data una coppia di poligoni, ad esempio A e B,
ci sono quattro casi da considerare: |
|
A oscura B: visualizzeremo solo A |
|
B oscura A: visualizzeremo solo B |
|
A e B sono completamente visibili:
visualizzeremo sia A che B |
|
A e B si oscurano parzialmente l’un l’altro:
dobbiamo calcolare le parti visibili di ciascun poligono |
|
|
|
|
Si prende uno dei n poligoni e lo si confronta
con tutti i restanti n – 1 |
|
In questo modo si determina quale parte del
poligono sarà visibile |
|
Questo processo è ripetuto con gli altri
poligoni |
|
La complessità di questo approccio risulta di
ordine O(n2) |
|
L’approccio object-space è consigliabile solo
quando gli oggetti nella scena sono pochi |
|
|
|
|
|
|
Per ogni pixel, si considera un raggio che parte
dal centro di proiezione e passa per quel pixel |
|
Il raggio è intersecato con ciascuno dei piani
determinati dai k poligoni per determinare per quali piani il raggio
attraversa un poligono |
|
L‘intersezione più vicina al centro di
proiezione è quella visibile |
|
|
|
|
L’operazione fondamentale dell’approccio
image-space è il calcolo delle intersezioni dei raggi con i poligoni |
|
Per un display w´h, questa operazione deve
essere eseguita w·h·n volte, e la complessità risulta di ordine O(n),
considerando quindi la risoluzione dello schermo una costante. |
|
|
|
|
|
Consideriamo una scena composta da poligoni
planari |
|
L’algoritmo depth sort è una variante di un
algoritmo ancora più semplice, chiamato algoritmo del pittore |
|
Supponiamo che i poligoni siano ordinati sulla
base della loro distanza dall’osservatore |
|
|
|
|
|
|
Per rappresentare correttamente la scena,
potremmo individuare la parte visibile del poligono più distante, e
predisporla nel frame buffer |
|
Se i poligoni sono solo due, questa operazione
richiede l’esecuzione del clipping di un poligono rispetto all’altro |
|
|
|
|
Un’altra possibilità è invece quella di seguire
un approccio analogo a quello usato da un pittore: |
|
Dipingere prima il poligono più lontano
interamente, e poi dipingere il poligono più vicino, dipingendo sopra le
parti del poligono più lontano non visibili all’osservatore |
|
|
|
|
|
I problemi da risolvere per implementare questo
approccio riguardano |
|
l’ordinamento in profondità dei poligoni |
|
la situazione di sovrapposizione tra poligoni |
|
|
|
|
Devo ordinare i poligoni in base alla distanza
della loro coordinata z massima dall’osservatore |
|
Più precisamente, si considera l’estensione
nella direzione z di ogni poligono |
|
|
|
|
Se la profondità minima di ogni poligono è
maggiore della profondità massima del poligono situato sul retro, possiamo
visualizzare i poligoni partendo da quello più in profondità |
|
|
|
|
E’ il caso del poligono A, che è situato dietro
a tutti gli altri poligoni e può essere visualizzato per primo |
|
|
|
|
E’ il caso del poligono A, che è situato dietro
a tutti gli altri poligoni e può essere visualizzato per primo |
|
|
|
|
Gli altri poligoni, tuttavia, non possono essere
visualizzati basandosi solo sulla loro estensione lungo z |
|
Se le estensioni z di due poligoni si
sovrappongono, dobbiamo determinare un ordine per visualizzarli
individualmente che permetta di ottenere l’immagine corretta |
|
|
|
|
|
|
Il test più semplice consiste nel controllare le
estensioni lungo x e lungo y |
|
Se non c’è sovrapposizione in almeno una delle
due direzioni, allora sicuramente nessuno dei due poligoni può oscurare
l’altro, ed essi possono essere visualizzati in un ordine qualsiasi |
|
|
|
|
|
|
Se anche questo test fallisce, può essere ancora
possibile trovare un ordine corretto per visualizzare i poligoni, ad
esempio se tutti i vertici di un poligono cadono dalla stessa parte del
piano determinato dall’altro poligono |
|
|
|
|
Rimangono da considerare due situazioni
problematiche, per cui non esiste un ordine corretto di rappresentazione |
|
|
|
|
La prima si verifica quando tre o più poligoni
si sovrappongono ciclicamente |
|
|
|
|
La seconda situazione si verifica invece quando
un poligono penetra nell’altro |
|
|
|
|
In entrambi i casi, è necessario spezzare i
poligoni in corrispondenza dei segmenti di intersezione, e cercare l’ordine
corretto di rappresentazione del nuovo insieme di poligoni |
|
|
|
|
|
L’algoritmo z-buffer è un algoritmo di tipo
image-space, basato su una logica molto semplice, e facile da implementare |
|
Lavora in accoppiamento con l’algoritmo di scan
conversion, e necessita, oltre alla memoria di display (frame buffer),
anche di un’area di memoria in cui memorizzare le informazioni di
profondità relative ad ogni pixel |
|
Quest’area addizionale di memoria è chiamata z-buffer |
|
|
|
|
|
|
La rasterizzazione dei poligoni avviene subito
dopo la proiezione sul piano di vista in NDC |
|
Ad ogni pixel dello schermo possono coincidere
0, 1 o più primitive |
|
Nel corso dell’esecuzione della scan conversion,
possiamo pensare al processo di proiezione come al calcolo del colore da
associare ad ogni punto di intersezione tra una retta che passa dal centro
di proiezione ed un pixel e le primitive |
|
|
|
|
|
|
Nell’effettuare questa operazione, si può
facilmente controllare se il punto di intersezione è visibile o meno
(dall’osservatore), secondo la regola che stabilisce che |
|
il punto è visibile se è il punto di
intersezione più vicino al centro di proiezione |
|
|
|
|
Quando si esegue la scan conversion del poligono
B, il suo colore apparirà sullo schermo poiché la distanza z1 è
minore della distanza z2 relativa al poligono A |
|
Al contrario, quando esegue la scan conversion
del poligono A, il pixel che corrisponde al punto di intersezione non
apparirà sul display |
|
|
|
|
|
|
Poiché si procede poligono per poligono, non è
possibile disporre di tutte le informazioni relative agli altri poligoni |
|
Dobbiamo disporre di una memoria, detta appunto
z-buffer, che abbia la stessa risoluzione del frame buffer e con una
profondità sufficiente per memorizzare la informazioni sulla risoluzione
che si vuole ottenere per le distanze |
|
Ogni elemento dello z-buffer è inizializzato al
valore della distanza massima dal centro di proiezione (il back-clipping
plane) |
|
|
|
|
|
|
Con questo approccio i poligoni possono essere
rasterizzati in qualsiasi ordine (non è necessario alcun ordinamento
preventivo dei poligoni in object-space, ovvero in 3D) |
|
for y:=0 YMAX |
|
for x:=0
XMAX |
|
WritePixel(x,y,colore del background); |
|
WriteZ(x,y,0). |
|
for ogni poligono |
|
for ogni pixel nella proiezione del poligono |
|
pz:= valore della z nel pixel di coordinate
(x,y) |
|
if
pz>= ReadZ(x,y) then |
|
WriteZ(x,y,pz) |
|
WritePixel(x,y,colore
del poligono nel pixel di coordinate (x,y)) |
|
|
|
|
|
Se ripensiamo a come avviene la proiezione da 3
a 2 dimensioni, una volta trasformato il view frustum nel cubo in NDC
possiamo pensare all’algoritmo di z-buffer come a quel metodo che anziché
scartare la z al momento della proiezione la memorizza (nello z-buffer
appunto) assieme all’informazione sul colore (nel frame buffer) |
|
|
|
|
Oltre alla rimozione delle superfici nascoste esistono
metodi opzionali che consentono di eliminare dalla pipeline di rendering
primitive che si può decidere che saranno comunque invisibili |
|
Se un oggetto è rappresentato da un poliedro
solido chiuso, le facce poligonali del poliedro delimitano completamente il
volume del solido |
|
Modelliamo i poligoni in maniera tale che le
normali alle loro superfici siano tutte dirette verso l’esterno del
poligono |
|
|
|
|
|
Se nessuna parte del poliedro viene tagliata dal
front clipping plane: |
|
le facce che hanno una normale che punta verso
l’osservatore possono essere visibili |
|
|
|
|
|
Se nessuna parte del poliedro viene tagliata dal
front clipping plane: |
|
quelle con normale che punta via dall’osservatore
sicuramente non lo sono |
|
|
|
|
Le facce sicuramente invisibili non vengono più
considerate nelle fasi successive del processo di rendering |
|
|
|
|
|
Per determinare se un poligono deve essere
eliminato, dobbiamo verificare se la sua normale è diretta o meno verso
l’osservatore |
|
Se indichiamo con q l’angolo tra la normale e
l’osservatore, il poligono in esame definisce la parte anteriore di un
oggetto se e solo se |
|
-90° £ q £ 90°, |
|
cos q ³ 0 |
|
Invece di calcolare il coseno,
si usa il
prodotto scalare |
|
n·v ³ 0 |
|
|
|
|
|
|
Questo procedimento (detto di solito back-face
culling) consente, in media, di dimezzare il tempo necessario a fare il
rendering degli oggetti solidi dato che, sempre in media, circa metà delle
facce di un poliedro saranno back-facing e quindi il loro rendering sarebbe
comunque inutile |
|