Hello world - Rimozione delle superfici nascoste - Appunti

Rasterization -  HSR descrivere il problema ed elencare le strategie e quindi gli algoritmi

La computazione avviene in aritmetica intera, e le operazioni sono “per pixel” (pixel bound).

Non tutti i poligoni sopravvissuti, però, devono essere disegnati. Alcuni possono non essere visibili dall’osservatore perché nascosti (totalmente o parzialmente) da altri poligoni.

• Problema: dati un insieme di poligoni in 3D ed un punto di vista, si vogliono disegnare solo i poligoni visibili (o porzioni di essi).
Ogni poligono si assume essere piatto ed opaco.

• Vi sono essenzialmente due approcci:
– object-precision: l’algoritmo lavora sui poligoni stabilendo relazioni di occlusione reciproca. Il costo `e quadratico nel numero dei poligoni. Però la precisione `e elevata (precisione macchina).

– image-precision: l’algoritmo stabilisce occlusioni a livello del pixel. `E più veloce ma la precisione `e limitata.
• La rimozione delle superfici nascoste (Hidden Surface Removal, HSR) viene anche indicata come determinazione delle superfici visibili (Visible Surface Determination,VSD).

le strategie sono divise in due categorie:

1 - Object-precision

Back-face culling

• Non `e un algoritmo generale di HSR in senso stretto, ma solo una tecnica (object space) utile per eliminare poligoni ovviamente invisibili.
• L’eliminazione delle facce posteriori (o back-face culling), elimina i poligoni che, a causa della loro orientazione, non possono essere visti.
• Viene effettuato nello spazio vista.
• Se v `e la direzione di vista (punta verso l’osservatore) ed n `e la normale al poligono, è facile rendersi conto che il poligono `e visibile solo se:
n · v > 0
• Nota: se la scena `e composta da un solo solido convesso, il culling risolve anche il problema della eliminazione delle facce posteriori.

List-priority

• Gli algoritmi list-priority determinano un ordinamento per i poligoni che garantisce che l’immagine che si ottiene `e corretta se i poligoni vengono disegnati nell’ordine assegnato.
• Operano in object-precision (ovvero a livello di poligono), nello spazio 3D screen.
• Questa tecnica non scarta i triangoli ma li ordina.
• Infatti, risolve un problema di visibilità, ma implica il rendering back-to-front di tutti i triangoli.
• Pu`o costituire la fase di HSR dentro la rendering pipeline, oppure pu´o essere a carico della applicazione, nel qual caso si assume che l’HSR della pipeline sia “spento” e che i triangoli vengano disegnati nell’ordine in cui vengono spediti.

Depth-sort: algoritmo del pittore

– i poligoni vengono ordinati per profondit`a (o pseudo-profondità) decrescente.
– si effettua il rendering dei poligoni della lista, dal più lontano al più vicino (back-to-front rendering ).
– In questo modo i poligoni più lontani vengono sovrascritti da quelli più vicini.

• Problema 1: se gli z-intervalli dei due poligono non sono disgiunti l’algoritmo non si applica (cos’è la profondità del poligono?); bisogna controllare altre condizioni per stabilire se uno dei due può essere disegnato prima dell’altro.
• Problema 2: nel caso ciclico `e necessario spezzare i poligoni in parti.
• L’algoritmo di Newell risolve correttamente questi problemi.

Depth-sort con Newell

• Ordina i poligoni in base al vertice di massima distanza dall’osservatore.
• I poligoni i cui z-intervalli non si sovrappongono possono essere disegnati (in ordine back-to-front) come nell’algoritmo del pittore.
• Dati due poligoni P e Q i cui z-intervalli si sovrappongono, è corretto disegnare P prima di Q solo se almeno uno di questi test `e vero:
1. gli x-intervalli di P e Q sono disgiunte (veloce);
2. gli y-intervalli di P e Q sono disgiunte (veloce);
3. Si consideri il piano contenente Q. P `e contenuto completamente nel semispazio opposto a quello dove `e l’osservatore (abbastanza veloce)?
4. Si consideri il piano contenente P. Q è contenuto completamente nello stesso semispazio dove `e l’osservatore (abbastanza veloce)?
5. Le proiezioni di P e Q sullo schermo sono disgiunte (pesante)?
• Se tutti i test falliscono, controllo se `e corretto disegnare Q prima di P.
• Se anche questo fallisce Q viene tagliato usando il piano contenente P (con clipping), ed i pezzi vengono collocati nella lista al posto giusto.

BSP tree

• Poiché l’ordine dei poligoni dipende dal punto di vista, bisogna ricalcolarlo ad ogni spostamento.
• Non è praticabile in una applicazione interattiva (es: simulatore di volo).
• Usiamo un albero BSP per ottenere rapidamente l’ordine corretto dei poligoni al cambiare del punto di vista.
• Costruzione (off-line) di un albero BSP auto-partitioning (divido usando i piani che
contengono i poligoni). Le foglie sono poligoni o frazioni.
• Attraversando l’albero si ottiene l’ordinamento desiderato:
– consideriamo la radice dell’albero
– il punto di vista si trova (diciamo) a destra dell’iperpiano associato alla radice.
– allora i poligoni che stanno a sinistra si possono disegnare prima di quelli che stanno a destra dell’iperpiano.
– l’ordine per i poligoni che si trovano nei due semispazi si ottiene ricorsivamente considerando separatamente i due sottoalberi.
• Questa tecnica si basa sull’idea comune ad altre di pre-processare la scena usando strutture dati opportune per ridurre il tempo di rendering.

2 - Image-precision

Depth-Buffer

• `E un algoritmo image-precision, opera nello spazio 3D screen.
• Il depth-buffer o z-buffer `e una matrice (grande come l’immagine) che contiene, per ciascun pixel, il più piccolo valore di profondità (z) incontrato finora.
• Durante la scan-conversion, per ciascun poligono che viene processato:
– si calcola la profondità (z) dei punti interni con interpolazione della z dei vertici (con interpolazione scan-line, come il colore in Gouraud shading).
– se la z del pixel `e inferiore a quella contenuta nello z-buffer, allora la sua intensità viene scritta nell’immagine e la z viene viene aggiornata.
• Vantaggio: semplicità di implementazione
• Svantaggio: occupazione di memoria: servono almeno 20-32 bits per pixel per avere una discretizzazione accettabile delle profondità.

Scan-Line Algorithm

Area Subdivision

Commenti

Post popolari in questo blog

Indovinello: Soluzioni!!!