Superfici nascoste
Daniele Marini
con contributi di Maurizio Rossi
1
Superfici nascoste in scene con
poliedri
Si abbiano oggetti composti da n poligoni
Problema: per ogni pixel della immagine,
• determina l’oggetto più vicino all’osservatore (COP)
• calcola il valore del pixel
Se p è il numero di pixel il problema è O(n·p)
Questo approccio limita la precisione a livello di immagine
(image
precision)
2
Un approccio di tipo “object precision” ha
complessità dell’ordine O(n2), richiede il confronto
tra tutti gli oggetti per decidere chi è davanti e chi
dietro rispetto all’osservatore.
3
Ottimizzare i calcoli sfruttando la coerenza:
• Tra oggetti: oggetti disgiunti non richiedono confronto di
vicinanza
• Tra facce: le proprietà di superficie variano lentamente e si
può procedere in modo incrementale
• Tra spigoli: uno spigolo può decidere il cambio di visibilità
quando delimita facce orientate opposte all’osservatore o quando
delimita facce che si intersecano
• Scan_line: tra due linee di scansione adiacenti le variazioni
sono piccole (metodi incrementali)
• D’area: pixel vicini sono coperti dalla stessa faccia visibile
• Di profondità: la profondità dei punti di una stessa faccia
cambia generalmente meno che tra punti di facce diverse (ancora
metodi incrementali)
• Di frame: valida per sequenze di immagini (sfruttata dai
metodi di compressione video)
4
Ogni metodo di rimozione di superfici nascoste richiede un
Test di profondità
Va eseguito in coordinate 3D prima della proiezione piana.
Si può eseguire in coordinate normalizzate se si adotta la
matrice canonica Mpersp
Come decidere se un punto p1 : (x1,y1,z1) maschera un punto
p2 : (x2,y2,z2) ???
occorre prima testare se (COP, p1 e p2) sono “colineari”,
in tal caso si può confrontare direttamente z1 con z2.
5
Per decidere la colinearità:
• Se è una proiezione parallela condizione necessaria e
sufficiente è:
x1=x2 e y1=y2
• Se è una proiezione prospettica invece bisogna fare 4
divisioni:
x1/z1 = x2/z2 y1/z1 = y2/z2
Per evitare la divisione si esegue il test prima
di deformare lo spazio in prospettico (proiezione parallela)
6
Per escludere a priori poligoni che non si possono
eventualmente mascherare si esegue un test su bounding
box, o test minimax, il cui costo computazionale è minore
rispetto al confronto completo dei poligoni:
7
Back face culling
Rimozione facce autonascoste e spigoli
autonascosti
nDOP > 0 dove DOP = (0, 0, -1)
Si riduce a un test sul segno di
nz (ovvero la componente z della
normale n alla faccia)
8
Per ottimizzare il metodo si ricorre al partizionamento spaziale
di due tipi:
• partizionamento regolare (griglie)
• partizionamento adattivo (BSPtree, quadtree, octree)
• gerarchie di oggetti
9
Z-Buffer
10
Il rendering: Z-buffer
•
•
Lo Z-buffer è un dispositivo hardware (o simulato via
software) che consente la rimozione delle linee e facce
nascoste in tempo reale
Per ogni punto immagine di ogni poligono lo Z-buffer
mantiene l’informazione sulla distanza dal punto di vista
11
Procedure z_buffer;
var pz:integer;
begin for y:=0 to YMAX do
for x:=0 to XMAX do
begin
WritePixel(x,y,background_color);
WriteZbuffer(x,y,0)
end
for each polygon do
for each pixel in polygon’s projection do
begin
pz:=polygon’s z_value in (x,y)
if pz >= ReadZbuffer(x,y) then
begin
WriteZbuffer(x,y,pz);
WritePixel(x,y,polygon’s color at (x,y))
end
end
end.
12
Esempio: calcolo di z1 in un punto (x1,y1) di un triangolo
lungo una scan-line sullo schermo. L’equazione del piano del
triangolo è del tipo: ax + by + cz + d = 0
risolvo rispetto a z e ottengo:
z1 = (- d - ax1 - by1)/c
noto z1 in (x1,y1) si calcola z2 nel pixel successivo della scanline (x1+Dx, y):
z2 = z1 - Dxa/c ma a/c =cost, Dx=1 e il calcolo si riduce ad
una sottrazione
13
Problemi dello z-buffer
Facce parzialmente sovrapposte molto vicine possono creare dei
problemi a causa dei metodi di calcolo numerico
14
Suddivisione ricorsiva: Warnock
• Suddivisione ricorsiva (quadtree) dello spazio immagine,
fino al livello del singolo pixel
• Criteri di “colorazione”:
– Un poligono circonda un
quadrante
– Un poligono interseca un
quadrante
– Un poligono è contenuto in un
quadrante
– Poligono e quadrante sono
disgiunti
15
Ray casting
• Adatto a CSG o superfici parametriche
• Dipende dal punto di vista
• È una sorta di “campionamento” spaziale della geometria
16
scegli COP e WINDOW
for tutte le linee di scansione do
for tutti i pixel nella linea do
begin
determina retta COP-pixel
for ogni oggetto nella scena do
if retta interseca oggetto e oggetto
è il più vicino a COP
then attiva pixel
end
17
Ray casting
Per il calcolo della intersezione si rappresenta la retta in
forma parametrica e se l’oggetto è rappresentato in forma
analitica si calcola l’intersezione, altrimenti si usano metodi
numerici approssimati (es. algoritmo di Newton)
Il calcolo delle intersezioni è molto costoso, si può ridurre
con varie tecniche:
•bounding box o bounding volume,
•orientare la scena con la retta COP-pixel coincidente con z,
•organizzazione gerarchica dei volumi,
•partizionamento dello spazio (octree o BSPtree o uniforme)
18
Ray casting CSG
• Testare le relazioni booleane:
19
Ray casting CSG
Se la scena è composta di più oggetti con operatori
booleani, si determina l’oggetto visibile applicando
gli operatori booleani ai tratti di retta COP-pixel che
intersecano gli oggetti
Il metodo di ray casting risolve automaticamente
anche il problema delle superfici nascoste.
20