1 Superfici nascoste Daniele Marini con contributi di Maurizio Rossi.
-
Upload
petronel-perri -
Category
Documents
-
view
218 -
download
0
Transcript of 1 Superfici nascoste Daniele Marini con contributi di Maurizio Rossi.
1
Superfici nascoste
Daniele Marinicon contributi di Maurizio Rossi
2
Superfici nascoste in scene con poliedri
Si abbiano oggetti composti da n poligoni
Problema per ogni pixel della immaginebull determina lrsquooggetto piugrave vicino allrsquoosservatore (COP)bull calcola il valore del pixel
Se p egrave il numero di pixel il problema egrave O(np)
Questo approccio limita la precisione a livello di immagine
(image precision)
3
Un approccio di tipo ldquoobject precisionrdquo ha complessitagrave dellrsquoordine O(n2) richiede il confronto tra tutti gli oggetti per decidere chi egrave davanti e chi dietro rispetto allrsquoosservatore
4
Ottimizzare i calcoli sfruttando la coerenzabull Tra oggetti oggetti disgiunti non richiedono confronto di vicinanza
bull Tra facce le proprietagrave di superficie variano lentamente e si puograve procedere in modo incrementale
bull Tra spigoli uno spigolo puograve decidere il cambio di visibilitagrave quando delimita facce orientate opposte allrsquoosservatore o quando delimita facce che si intersecano
bull Scan_line tra due linee di scansione adiacenti le variazioni sono piccole (metodi incrementali)bull Drsquoarea pixel vicini sono coperti dalla stessa faccia visibile
bull Di profonditagrave la profonditagrave dei punti di una stessa faccia cambia generalmente meno che tra punti di facce diverse (ancora metodi incrementali)
bull Di frame valida per sequenze di immagini (sfruttata dai metodi di compressione video)
5
Ogni metodo di rimozione di superfici nascoste richiede un
Test di profonditagrave
Va eseguito in coordinate 3D prima della proiezione piana
Si puograve eseguire in coordinate normalizzate se si adotta la matrice canonica Mpersp
Come decidere se un punto p1 (x1y1z1) maschera un punto p2 (x2y2z2)
occorre prima testare se (COP p1 e p2) sono ldquocolinearirdquo in tal caso si puograve confrontare direttamente z1 con z2
6
Per decidere la colinearitagrave
bull Se egrave una proiezione parallela condizione necessaria e sufficiente egrave
x1=x2 e y1=y2
bull Se egrave una proiezione prospettica invece bisogna fare 4 divisioni
x1z1 = x2z2 y1z1 = y2z2
Per evitare la divisione si esegue il test prima di deformare lo spazio in prospettico (proiezione parallela)
7
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 egrave minore rispetto al confronto completo dei poligoni
8
Rimozione facce autonascoste e spigoli autonascosti
nDOP gt 0 dove DOP = (0 0 -1)
Si riduce a un test sul segno dinz (ovvero la componente z dellanormale n alla faccia)
Back face culling
9
Per ottimizzare il metodo si ricorre al partizionamento spazialedi due tipi
bull partizionamento regolare (griglie)bull partizionamento adattivo (BSPtree quadtree octree)
bull gerarchie di oggetti
10
Z-Buffer
11
Il rendering Z-bufferIl rendering Z-bufferbull Lo Z-buffer egrave un dispositivo hardware (o simulato via
software) che consente la rimozione delle linee e facce nascoste in tempo reale
bull Per ogni punto immagine di ogni poligono lo Z-bufferZ-buffer mantiene lrsquoinformazione sulla distanza dal punto di vista
12
Procedure z_buffervar pzintegerbegin for y=0 to YMAX do
for x=0 to XMAX dobegin WritePixel(xybackground_color) WriteZbuffer(xy0)endfor each polygon do for each pixel in polygonrsquos projection do begin
pz=polygonrsquos z_value in (xy)if pz gt= ReadZbuffer(xy) thenbegin WriteZbuffer(xypz) WritePixel(xypolygonrsquos color at (xy))end
endend
13
Esempio calcolo di z1 in un punto (x1y1) di un triangolo lungo una scan-line sullo schermo Lrsquoequazione del piano del triangolo egrave del tipo ax + by + cz + d = 0risolvo rispetto a z e ottengo
z1 = (- d - ax1 - by1)c
noto z1 in (x1y1) si calcola z2 nel pixel successivo della scan-line (x1+x y)
z2 = z1 - xac ma ac =cost x=1 e il calcolo si riduce ad una sottrazione
14
Problemi dello z-buffer
Facce parzialmente sovrapposte molto vicine possono creare deiproblemi a causa dei metodi di calcolo numerico
15
Suddivisione ricorsiva Warnockbull Suddivisione ricorsiva (quad-
tree) dello spazio immagine fino al livello del singolo pixel
bull Criteri di ldquocolorazionerdquondash Un poligono circonda un
quadrante
ndash Un poligono interseca un quadrante
ndash Un poligono egrave contenuto in un quadrante
ndash Poligono e quadrante sono disgiunti
16
Ray casting
bull Adatto a CSG o superfici parametrichebull Dipende dal punto di vistabull Egrave una sorta di ldquocampionamentordquo spaziale della geometria
17
scegli COP e WINDOWfor tutte le linee di scansione do for tutti i pixel nella linea do begin
determina retta COP-pixelfor ogni oggetto nella scena do if retta interseca oggetto e oggetto
egrave il piugrave vicino a COP then attiva pixelend
18
Per il calcolo della intersezione si rappresenta la retta informa parametrica e se lrsquooggetto egrave rappresentato in formaanalitica si calcola lrsquointersezione altrimenti si usano metodinumerici approssimati (es algoritmo di Newton)
Il calcolo delle intersezioni egrave molto costoso si puograve ridurrecon varie tecnichebullbounding box o bounding volumebullorientare la scena con la retta COP-pixel coincidente con zbullorganizzazione gerarchica dei volumibullpartizionamento dello spazio (octree o BSPtree o uniforme)
Ray casting
19
Ray casting CSG
bull Testare le relazioni booleane
20
Se la scena egrave composta di piugrave oggetti con operatoribooleani si determina lrsquooggetto visibile applicandogli operatori booleani ai tratti di retta COP-pixel cheintersecano gli oggetti
Il metodo di ray casting risolve automaticamenteanche il problema delle superfici nascoste
Ray casting CSG
- Superfici nascoste
- Superfici nascoste in scene con poliedri
- PowerPoint Presentation
- Slide 4
- Slide 5
- Slide 6
- Slide 7
- Back face culling
- Slide 9
- Z-Buffer
- Il rendering Z-buffer
- Slide 12
- Slide 13
- Problemi dello z-buffer
- Suddivisione ricorsiva Warnock
- Ray casting
- Slide 17
- Slide 18
- Ray casting CSG
- Slide 20
-
2
Superfici nascoste in scene con poliedri
Si abbiano oggetti composti da n poligoni
Problema per ogni pixel della immaginebull determina lrsquooggetto piugrave vicino allrsquoosservatore (COP)bull calcola il valore del pixel
Se p egrave il numero di pixel il problema egrave O(np)
Questo approccio limita la precisione a livello di immagine
(image precision)
3
Un approccio di tipo ldquoobject precisionrdquo ha complessitagrave dellrsquoordine O(n2) richiede il confronto tra tutti gli oggetti per decidere chi egrave davanti e chi dietro rispetto allrsquoosservatore
4
Ottimizzare i calcoli sfruttando la coerenzabull Tra oggetti oggetti disgiunti non richiedono confronto di vicinanza
bull Tra facce le proprietagrave di superficie variano lentamente e si puograve procedere in modo incrementale
bull Tra spigoli uno spigolo puograve decidere il cambio di visibilitagrave quando delimita facce orientate opposte allrsquoosservatore o quando delimita facce che si intersecano
bull Scan_line tra due linee di scansione adiacenti le variazioni sono piccole (metodi incrementali)bull Drsquoarea pixel vicini sono coperti dalla stessa faccia visibile
bull Di profonditagrave la profonditagrave dei punti di una stessa faccia cambia generalmente meno che tra punti di facce diverse (ancora metodi incrementali)
bull Di frame valida per sequenze di immagini (sfruttata dai metodi di compressione video)
5
Ogni metodo di rimozione di superfici nascoste richiede un
Test di profonditagrave
Va eseguito in coordinate 3D prima della proiezione piana
Si puograve eseguire in coordinate normalizzate se si adotta la matrice canonica Mpersp
Come decidere se un punto p1 (x1y1z1) maschera un punto p2 (x2y2z2)
occorre prima testare se (COP p1 e p2) sono ldquocolinearirdquo in tal caso si puograve confrontare direttamente z1 con z2
6
Per decidere la colinearitagrave
bull Se egrave una proiezione parallela condizione necessaria e sufficiente egrave
x1=x2 e y1=y2
bull Se egrave una proiezione prospettica invece bisogna fare 4 divisioni
x1z1 = x2z2 y1z1 = y2z2
Per evitare la divisione si esegue il test prima di deformare lo spazio in prospettico (proiezione parallela)
7
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 egrave minore rispetto al confronto completo dei poligoni
8
Rimozione facce autonascoste e spigoli autonascosti
nDOP gt 0 dove DOP = (0 0 -1)
Si riduce a un test sul segno dinz (ovvero la componente z dellanormale n alla faccia)
Back face culling
9
Per ottimizzare il metodo si ricorre al partizionamento spazialedi due tipi
bull partizionamento regolare (griglie)bull partizionamento adattivo (BSPtree quadtree octree)
bull gerarchie di oggetti
10
Z-Buffer
11
Il rendering Z-bufferIl rendering Z-bufferbull Lo Z-buffer egrave un dispositivo hardware (o simulato via
software) che consente la rimozione delle linee e facce nascoste in tempo reale
bull Per ogni punto immagine di ogni poligono lo Z-bufferZ-buffer mantiene lrsquoinformazione sulla distanza dal punto di vista
12
Procedure z_buffervar pzintegerbegin for y=0 to YMAX do
for x=0 to XMAX dobegin WritePixel(xybackground_color) WriteZbuffer(xy0)endfor each polygon do for each pixel in polygonrsquos projection do begin
pz=polygonrsquos z_value in (xy)if pz gt= ReadZbuffer(xy) thenbegin WriteZbuffer(xypz) WritePixel(xypolygonrsquos color at (xy))end
endend
13
Esempio calcolo di z1 in un punto (x1y1) di un triangolo lungo una scan-line sullo schermo Lrsquoequazione del piano del triangolo egrave del tipo ax + by + cz + d = 0risolvo rispetto a z e ottengo
z1 = (- d - ax1 - by1)c
noto z1 in (x1y1) si calcola z2 nel pixel successivo della scan-line (x1+x y)
z2 = z1 - xac ma ac =cost x=1 e il calcolo si riduce ad una sottrazione
14
Problemi dello z-buffer
Facce parzialmente sovrapposte molto vicine possono creare deiproblemi a causa dei metodi di calcolo numerico
15
Suddivisione ricorsiva Warnockbull Suddivisione ricorsiva (quad-
tree) dello spazio immagine fino al livello del singolo pixel
bull Criteri di ldquocolorazionerdquondash Un poligono circonda un
quadrante
ndash Un poligono interseca un quadrante
ndash Un poligono egrave contenuto in un quadrante
ndash Poligono e quadrante sono disgiunti
16
Ray casting
bull Adatto a CSG o superfici parametrichebull Dipende dal punto di vistabull Egrave una sorta di ldquocampionamentordquo spaziale della geometria
17
scegli COP e WINDOWfor tutte le linee di scansione do for tutti i pixel nella linea do begin
determina retta COP-pixelfor ogni oggetto nella scena do if retta interseca oggetto e oggetto
egrave il piugrave vicino a COP then attiva pixelend
18
Per il calcolo della intersezione si rappresenta la retta informa parametrica e se lrsquooggetto egrave rappresentato in formaanalitica si calcola lrsquointersezione altrimenti si usano metodinumerici approssimati (es algoritmo di Newton)
Il calcolo delle intersezioni egrave molto costoso si puograve ridurrecon varie tecnichebullbounding box o bounding volumebullorientare la scena con la retta COP-pixel coincidente con zbullorganizzazione gerarchica dei volumibullpartizionamento dello spazio (octree o BSPtree o uniforme)
Ray casting
19
Ray casting CSG
bull Testare le relazioni booleane
20
Se la scena egrave composta di piugrave oggetti con operatoribooleani si determina lrsquooggetto visibile applicandogli operatori booleani ai tratti di retta COP-pixel cheintersecano gli oggetti
Il metodo di ray casting risolve automaticamenteanche il problema delle superfici nascoste
Ray casting CSG
- Superfici nascoste
- Superfici nascoste in scene con poliedri
- PowerPoint Presentation
- Slide 4
- Slide 5
- Slide 6
- Slide 7
- Back face culling
- Slide 9
- Z-Buffer
- Il rendering Z-buffer
- Slide 12
- Slide 13
- Problemi dello z-buffer
- Suddivisione ricorsiva Warnock
- Ray casting
- Slide 17
- Slide 18
- Ray casting CSG
- Slide 20
-
3
Un approccio di tipo ldquoobject precisionrdquo ha complessitagrave dellrsquoordine O(n2) richiede il confronto tra tutti gli oggetti per decidere chi egrave davanti e chi dietro rispetto allrsquoosservatore
4
Ottimizzare i calcoli sfruttando la coerenzabull Tra oggetti oggetti disgiunti non richiedono confronto di vicinanza
bull Tra facce le proprietagrave di superficie variano lentamente e si puograve procedere in modo incrementale
bull Tra spigoli uno spigolo puograve decidere il cambio di visibilitagrave quando delimita facce orientate opposte allrsquoosservatore o quando delimita facce che si intersecano
bull Scan_line tra due linee di scansione adiacenti le variazioni sono piccole (metodi incrementali)bull Drsquoarea pixel vicini sono coperti dalla stessa faccia visibile
bull Di profonditagrave la profonditagrave dei punti di una stessa faccia cambia generalmente meno che tra punti di facce diverse (ancora metodi incrementali)
bull Di frame valida per sequenze di immagini (sfruttata dai metodi di compressione video)
5
Ogni metodo di rimozione di superfici nascoste richiede un
Test di profonditagrave
Va eseguito in coordinate 3D prima della proiezione piana
Si puograve eseguire in coordinate normalizzate se si adotta la matrice canonica Mpersp
Come decidere se un punto p1 (x1y1z1) maschera un punto p2 (x2y2z2)
occorre prima testare se (COP p1 e p2) sono ldquocolinearirdquo in tal caso si puograve confrontare direttamente z1 con z2
6
Per decidere la colinearitagrave
bull Se egrave una proiezione parallela condizione necessaria e sufficiente egrave
x1=x2 e y1=y2
bull Se egrave una proiezione prospettica invece bisogna fare 4 divisioni
x1z1 = x2z2 y1z1 = y2z2
Per evitare la divisione si esegue il test prima di deformare lo spazio in prospettico (proiezione parallela)
7
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 egrave minore rispetto al confronto completo dei poligoni
8
Rimozione facce autonascoste e spigoli autonascosti
nDOP gt 0 dove DOP = (0 0 -1)
Si riduce a un test sul segno dinz (ovvero la componente z dellanormale n alla faccia)
Back face culling
9
Per ottimizzare il metodo si ricorre al partizionamento spazialedi due tipi
bull partizionamento regolare (griglie)bull partizionamento adattivo (BSPtree quadtree octree)
bull gerarchie di oggetti
10
Z-Buffer
11
Il rendering Z-bufferIl rendering Z-bufferbull Lo Z-buffer egrave un dispositivo hardware (o simulato via
software) che consente la rimozione delle linee e facce nascoste in tempo reale
bull Per ogni punto immagine di ogni poligono lo Z-bufferZ-buffer mantiene lrsquoinformazione sulla distanza dal punto di vista
12
Procedure z_buffervar pzintegerbegin for y=0 to YMAX do
for x=0 to XMAX dobegin WritePixel(xybackground_color) WriteZbuffer(xy0)endfor each polygon do for each pixel in polygonrsquos projection do begin
pz=polygonrsquos z_value in (xy)if pz gt= ReadZbuffer(xy) thenbegin WriteZbuffer(xypz) WritePixel(xypolygonrsquos color at (xy))end
endend
13
Esempio calcolo di z1 in un punto (x1y1) di un triangolo lungo una scan-line sullo schermo Lrsquoequazione del piano del triangolo egrave del tipo ax + by + cz + d = 0risolvo rispetto a z e ottengo
z1 = (- d - ax1 - by1)c
noto z1 in (x1y1) si calcola z2 nel pixel successivo della scan-line (x1+x y)
z2 = z1 - xac ma ac =cost x=1 e il calcolo si riduce ad una sottrazione
14
Problemi dello z-buffer
Facce parzialmente sovrapposte molto vicine possono creare deiproblemi a causa dei metodi di calcolo numerico
15
Suddivisione ricorsiva Warnockbull Suddivisione ricorsiva (quad-
tree) dello spazio immagine fino al livello del singolo pixel
bull Criteri di ldquocolorazionerdquondash Un poligono circonda un
quadrante
ndash Un poligono interseca un quadrante
ndash Un poligono egrave contenuto in un quadrante
ndash Poligono e quadrante sono disgiunti
16
Ray casting
bull Adatto a CSG o superfici parametrichebull Dipende dal punto di vistabull Egrave una sorta di ldquocampionamentordquo spaziale della geometria
17
scegli COP e WINDOWfor tutte le linee di scansione do for tutti i pixel nella linea do begin
determina retta COP-pixelfor ogni oggetto nella scena do if retta interseca oggetto e oggetto
egrave il piugrave vicino a COP then attiva pixelend
18
Per il calcolo della intersezione si rappresenta la retta informa parametrica e se lrsquooggetto egrave rappresentato in formaanalitica si calcola lrsquointersezione altrimenti si usano metodinumerici approssimati (es algoritmo di Newton)
Il calcolo delle intersezioni egrave molto costoso si puograve ridurrecon varie tecnichebullbounding box o bounding volumebullorientare la scena con la retta COP-pixel coincidente con zbullorganizzazione gerarchica dei volumibullpartizionamento dello spazio (octree o BSPtree o uniforme)
Ray casting
19
Ray casting CSG
bull Testare le relazioni booleane
20
Se la scena egrave composta di piugrave oggetti con operatoribooleani si determina lrsquooggetto visibile applicandogli operatori booleani ai tratti di retta COP-pixel cheintersecano gli oggetti
Il metodo di ray casting risolve automaticamenteanche il problema delle superfici nascoste
Ray casting CSG
- Superfici nascoste
- Superfici nascoste in scene con poliedri
- PowerPoint Presentation
- Slide 4
- Slide 5
- Slide 6
- Slide 7
- Back face culling
- Slide 9
- Z-Buffer
- Il rendering Z-buffer
- Slide 12
- Slide 13
- Problemi dello z-buffer
- Suddivisione ricorsiva Warnock
- Ray casting
- Slide 17
- Slide 18
- Ray casting CSG
- Slide 20
-
4
Ottimizzare i calcoli sfruttando la coerenzabull Tra oggetti oggetti disgiunti non richiedono confronto di vicinanza
bull Tra facce le proprietagrave di superficie variano lentamente e si puograve procedere in modo incrementale
bull Tra spigoli uno spigolo puograve decidere il cambio di visibilitagrave quando delimita facce orientate opposte allrsquoosservatore o quando delimita facce che si intersecano
bull Scan_line tra due linee di scansione adiacenti le variazioni sono piccole (metodi incrementali)bull Drsquoarea pixel vicini sono coperti dalla stessa faccia visibile
bull Di profonditagrave la profonditagrave dei punti di una stessa faccia cambia generalmente meno che tra punti di facce diverse (ancora metodi incrementali)
bull Di frame valida per sequenze di immagini (sfruttata dai metodi di compressione video)
5
Ogni metodo di rimozione di superfici nascoste richiede un
Test di profonditagrave
Va eseguito in coordinate 3D prima della proiezione piana
Si puograve eseguire in coordinate normalizzate se si adotta la matrice canonica Mpersp
Come decidere se un punto p1 (x1y1z1) maschera un punto p2 (x2y2z2)
occorre prima testare se (COP p1 e p2) sono ldquocolinearirdquo in tal caso si puograve confrontare direttamente z1 con z2
6
Per decidere la colinearitagrave
bull Se egrave una proiezione parallela condizione necessaria e sufficiente egrave
x1=x2 e y1=y2
bull Se egrave una proiezione prospettica invece bisogna fare 4 divisioni
x1z1 = x2z2 y1z1 = y2z2
Per evitare la divisione si esegue il test prima di deformare lo spazio in prospettico (proiezione parallela)
7
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 egrave minore rispetto al confronto completo dei poligoni
8
Rimozione facce autonascoste e spigoli autonascosti
nDOP gt 0 dove DOP = (0 0 -1)
Si riduce a un test sul segno dinz (ovvero la componente z dellanormale n alla faccia)
Back face culling
9
Per ottimizzare il metodo si ricorre al partizionamento spazialedi due tipi
bull partizionamento regolare (griglie)bull partizionamento adattivo (BSPtree quadtree octree)
bull gerarchie di oggetti
10
Z-Buffer
11
Il rendering Z-bufferIl rendering Z-bufferbull Lo Z-buffer egrave un dispositivo hardware (o simulato via
software) che consente la rimozione delle linee e facce nascoste in tempo reale
bull Per ogni punto immagine di ogni poligono lo Z-bufferZ-buffer mantiene lrsquoinformazione sulla distanza dal punto di vista
12
Procedure z_buffervar pzintegerbegin for y=0 to YMAX do
for x=0 to XMAX dobegin WritePixel(xybackground_color) WriteZbuffer(xy0)endfor each polygon do for each pixel in polygonrsquos projection do begin
pz=polygonrsquos z_value in (xy)if pz gt= ReadZbuffer(xy) thenbegin WriteZbuffer(xypz) WritePixel(xypolygonrsquos color at (xy))end
endend
13
Esempio calcolo di z1 in un punto (x1y1) di un triangolo lungo una scan-line sullo schermo Lrsquoequazione del piano del triangolo egrave del tipo ax + by + cz + d = 0risolvo rispetto a z e ottengo
z1 = (- d - ax1 - by1)c
noto z1 in (x1y1) si calcola z2 nel pixel successivo della scan-line (x1+x y)
z2 = z1 - xac ma ac =cost x=1 e il calcolo si riduce ad una sottrazione
14
Problemi dello z-buffer
Facce parzialmente sovrapposte molto vicine possono creare deiproblemi a causa dei metodi di calcolo numerico
15
Suddivisione ricorsiva Warnockbull Suddivisione ricorsiva (quad-
tree) dello spazio immagine fino al livello del singolo pixel
bull Criteri di ldquocolorazionerdquondash Un poligono circonda un
quadrante
ndash Un poligono interseca un quadrante
ndash Un poligono egrave contenuto in un quadrante
ndash Poligono e quadrante sono disgiunti
16
Ray casting
bull Adatto a CSG o superfici parametrichebull Dipende dal punto di vistabull Egrave una sorta di ldquocampionamentordquo spaziale della geometria
17
scegli COP e WINDOWfor tutte le linee di scansione do for tutti i pixel nella linea do begin
determina retta COP-pixelfor ogni oggetto nella scena do if retta interseca oggetto e oggetto
egrave il piugrave vicino a COP then attiva pixelend
18
Per il calcolo della intersezione si rappresenta la retta informa parametrica e se lrsquooggetto egrave rappresentato in formaanalitica si calcola lrsquointersezione altrimenti si usano metodinumerici approssimati (es algoritmo di Newton)
Il calcolo delle intersezioni egrave molto costoso si puograve ridurrecon varie tecnichebullbounding box o bounding volumebullorientare la scena con la retta COP-pixel coincidente con zbullorganizzazione gerarchica dei volumibullpartizionamento dello spazio (octree o BSPtree o uniforme)
Ray casting
19
Ray casting CSG
bull Testare le relazioni booleane
20
Se la scena egrave composta di piugrave oggetti con operatoribooleani si determina lrsquooggetto visibile applicandogli operatori booleani ai tratti di retta COP-pixel cheintersecano gli oggetti
Il metodo di ray casting risolve automaticamenteanche il problema delle superfici nascoste
Ray casting CSG
- Superfici nascoste
- Superfici nascoste in scene con poliedri
- PowerPoint Presentation
- Slide 4
- Slide 5
- Slide 6
- Slide 7
- Back face culling
- Slide 9
- Z-Buffer
- Il rendering Z-buffer
- Slide 12
- Slide 13
- Problemi dello z-buffer
- Suddivisione ricorsiva Warnock
- Ray casting
- Slide 17
- Slide 18
- Ray casting CSG
- Slide 20
-
5
Ogni metodo di rimozione di superfici nascoste richiede un
Test di profonditagrave
Va eseguito in coordinate 3D prima della proiezione piana
Si puograve eseguire in coordinate normalizzate se si adotta la matrice canonica Mpersp
Come decidere se un punto p1 (x1y1z1) maschera un punto p2 (x2y2z2)
occorre prima testare se (COP p1 e p2) sono ldquocolinearirdquo in tal caso si puograve confrontare direttamente z1 con z2
6
Per decidere la colinearitagrave
bull Se egrave una proiezione parallela condizione necessaria e sufficiente egrave
x1=x2 e y1=y2
bull Se egrave una proiezione prospettica invece bisogna fare 4 divisioni
x1z1 = x2z2 y1z1 = y2z2
Per evitare la divisione si esegue il test prima di deformare lo spazio in prospettico (proiezione parallela)
7
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 egrave minore rispetto al confronto completo dei poligoni
8
Rimozione facce autonascoste e spigoli autonascosti
nDOP gt 0 dove DOP = (0 0 -1)
Si riduce a un test sul segno dinz (ovvero la componente z dellanormale n alla faccia)
Back face culling
9
Per ottimizzare il metodo si ricorre al partizionamento spazialedi due tipi
bull partizionamento regolare (griglie)bull partizionamento adattivo (BSPtree quadtree octree)
bull gerarchie di oggetti
10
Z-Buffer
11
Il rendering Z-bufferIl rendering Z-bufferbull Lo Z-buffer egrave un dispositivo hardware (o simulato via
software) che consente la rimozione delle linee e facce nascoste in tempo reale
bull Per ogni punto immagine di ogni poligono lo Z-bufferZ-buffer mantiene lrsquoinformazione sulla distanza dal punto di vista
12
Procedure z_buffervar pzintegerbegin for y=0 to YMAX do
for x=0 to XMAX dobegin WritePixel(xybackground_color) WriteZbuffer(xy0)endfor each polygon do for each pixel in polygonrsquos projection do begin
pz=polygonrsquos z_value in (xy)if pz gt= ReadZbuffer(xy) thenbegin WriteZbuffer(xypz) WritePixel(xypolygonrsquos color at (xy))end
endend
13
Esempio calcolo di z1 in un punto (x1y1) di un triangolo lungo una scan-line sullo schermo Lrsquoequazione del piano del triangolo egrave del tipo ax + by + cz + d = 0risolvo rispetto a z e ottengo
z1 = (- d - ax1 - by1)c
noto z1 in (x1y1) si calcola z2 nel pixel successivo della scan-line (x1+x y)
z2 = z1 - xac ma ac =cost x=1 e il calcolo si riduce ad una sottrazione
14
Problemi dello z-buffer
Facce parzialmente sovrapposte molto vicine possono creare deiproblemi a causa dei metodi di calcolo numerico
15
Suddivisione ricorsiva Warnockbull Suddivisione ricorsiva (quad-
tree) dello spazio immagine fino al livello del singolo pixel
bull Criteri di ldquocolorazionerdquondash Un poligono circonda un
quadrante
ndash Un poligono interseca un quadrante
ndash Un poligono egrave contenuto in un quadrante
ndash Poligono e quadrante sono disgiunti
16
Ray casting
bull Adatto a CSG o superfici parametrichebull Dipende dal punto di vistabull Egrave una sorta di ldquocampionamentordquo spaziale della geometria
17
scegli COP e WINDOWfor tutte le linee di scansione do for tutti i pixel nella linea do begin
determina retta COP-pixelfor ogni oggetto nella scena do if retta interseca oggetto e oggetto
egrave il piugrave vicino a COP then attiva pixelend
18
Per il calcolo della intersezione si rappresenta la retta informa parametrica e se lrsquooggetto egrave rappresentato in formaanalitica si calcola lrsquointersezione altrimenti si usano metodinumerici approssimati (es algoritmo di Newton)
Il calcolo delle intersezioni egrave molto costoso si puograve ridurrecon varie tecnichebullbounding box o bounding volumebullorientare la scena con la retta COP-pixel coincidente con zbullorganizzazione gerarchica dei volumibullpartizionamento dello spazio (octree o BSPtree o uniforme)
Ray casting
19
Ray casting CSG
bull Testare le relazioni booleane
20
Se la scena egrave composta di piugrave oggetti con operatoribooleani si determina lrsquooggetto visibile applicandogli operatori booleani ai tratti di retta COP-pixel cheintersecano gli oggetti
Il metodo di ray casting risolve automaticamenteanche il problema delle superfici nascoste
Ray casting CSG
- Superfici nascoste
- Superfici nascoste in scene con poliedri
- PowerPoint Presentation
- Slide 4
- Slide 5
- Slide 6
- Slide 7
- Back face culling
- Slide 9
- Z-Buffer
- Il rendering Z-buffer
- Slide 12
- Slide 13
- Problemi dello z-buffer
- Suddivisione ricorsiva Warnock
- Ray casting
- Slide 17
- Slide 18
- Ray casting CSG
- Slide 20
-
6
Per decidere la colinearitagrave
bull Se egrave una proiezione parallela condizione necessaria e sufficiente egrave
x1=x2 e y1=y2
bull Se egrave una proiezione prospettica invece bisogna fare 4 divisioni
x1z1 = x2z2 y1z1 = y2z2
Per evitare la divisione si esegue il test prima di deformare lo spazio in prospettico (proiezione parallela)
7
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 egrave minore rispetto al confronto completo dei poligoni
8
Rimozione facce autonascoste e spigoli autonascosti
nDOP gt 0 dove DOP = (0 0 -1)
Si riduce a un test sul segno dinz (ovvero la componente z dellanormale n alla faccia)
Back face culling
9
Per ottimizzare il metodo si ricorre al partizionamento spazialedi due tipi
bull partizionamento regolare (griglie)bull partizionamento adattivo (BSPtree quadtree octree)
bull gerarchie di oggetti
10
Z-Buffer
11
Il rendering Z-bufferIl rendering Z-bufferbull Lo Z-buffer egrave un dispositivo hardware (o simulato via
software) che consente la rimozione delle linee e facce nascoste in tempo reale
bull Per ogni punto immagine di ogni poligono lo Z-bufferZ-buffer mantiene lrsquoinformazione sulla distanza dal punto di vista
12
Procedure z_buffervar pzintegerbegin for y=0 to YMAX do
for x=0 to XMAX dobegin WritePixel(xybackground_color) WriteZbuffer(xy0)endfor each polygon do for each pixel in polygonrsquos projection do begin
pz=polygonrsquos z_value in (xy)if pz gt= ReadZbuffer(xy) thenbegin WriteZbuffer(xypz) WritePixel(xypolygonrsquos color at (xy))end
endend
13
Esempio calcolo di z1 in un punto (x1y1) di un triangolo lungo una scan-line sullo schermo Lrsquoequazione del piano del triangolo egrave del tipo ax + by + cz + d = 0risolvo rispetto a z e ottengo
z1 = (- d - ax1 - by1)c
noto z1 in (x1y1) si calcola z2 nel pixel successivo della scan-line (x1+x y)
z2 = z1 - xac ma ac =cost x=1 e il calcolo si riduce ad una sottrazione
14
Problemi dello z-buffer
Facce parzialmente sovrapposte molto vicine possono creare deiproblemi a causa dei metodi di calcolo numerico
15
Suddivisione ricorsiva Warnockbull Suddivisione ricorsiva (quad-
tree) dello spazio immagine fino al livello del singolo pixel
bull Criteri di ldquocolorazionerdquondash Un poligono circonda un
quadrante
ndash Un poligono interseca un quadrante
ndash Un poligono egrave contenuto in un quadrante
ndash Poligono e quadrante sono disgiunti
16
Ray casting
bull Adatto a CSG o superfici parametrichebull Dipende dal punto di vistabull Egrave una sorta di ldquocampionamentordquo spaziale della geometria
17
scegli COP e WINDOWfor tutte le linee di scansione do for tutti i pixel nella linea do begin
determina retta COP-pixelfor ogni oggetto nella scena do if retta interseca oggetto e oggetto
egrave il piugrave vicino a COP then attiva pixelend
18
Per il calcolo della intersezione si rappresenta la retta informa parametrica e se lrsquooggetto egrave rappresentato in formaanalitica si calcola lrsquointersezione altrimenti si usano metodinumerici approssimati (es algoritmo di Newton)
Il calcolo delle intersezioni egrave molto costoso si puograve ridurrecon varie tecnichebullbounding box o bounding volumebullorientare la scena con la retta COP-pixel coincidente con zbullorganizzazione gerarchica dei volumibullpartizionamento dello spazio (octree o BSPtree o uniforme)
Ray casting
19
Ray casting CSG
bull Testare le relazioni booleane
20
Se la scena egrave composta di piugrave oggetti con operatoribooleani si determina lrsquooggetto visibile applicandogli operatori booleani ai tratti di retta COP-pixel cheintersecano gli oggetti
Il metodo di ray casting risolve automaticamenteanche il problema delle superfici nascoste
Ray casting CSG
- Superfici nascoste
- Superfici nascoste in scene con poliedri
- PowerPoint Presentation
- Slide 4
- Slide 5
- Slide 6
- Slide 7
- Back face culling
- Slide 9
- Z-Buffer
- Il rendering Z-buffer
- Slide 12
- Slide 13
- Problemi dello z-buffer
- Suddivisione ricorsiva Warnock
- Ray casting
- Slide 17
- Slide 18
- Ray casting CSG
- Slide 20
-
7
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 egrave minore rispetto al confronto completo dei poligoni
8
Rimozione facce autonascoste e spigoli autonascosti
nDOP gt 0 dove DOP = (0 0 -1)
Si riduce a un test sul segno dinz (ovvero la componente z dellanormale n alla faccia)
Back face culling
9
Per ottimizzare il metodo si ricorre al partizionamento spazialedi due tipi
bull partizionamento regolare (griglie)bull partizionamento adattivo (BSPtree quadtree octree)
bull gerarchie di oggetti
10
Z-Buffer
11
Il rendering Z-bufferIl rendering Z-bufferbull Lo Z-buffer egrave un dispositivo hardware (o simulato via
software) che consente la rimozione delle linee e facce nascoste in tempo reale
bull Per ogni punto immagine di ogni poligono lo Z-bufferZ-buffer mantiene lrsquoinformazione sulla distanza dal punto di vista
12
Procedure z_buffervar pzintegerbegin for y=0 to YMAX do
for x=0 to XMAX dobegin WritePixel(xybackground_color) WriteZbuffer(xy0)endfor each polygon do for each pixel in polygonrsquos projection do begin
pz=polygonrsquos z_value in (xy)if pz gt= ReadZbuffer(xy) thenbegin WriteZbuffer(xypz) WritePixel(xypolygonrsquos color at (xy))end
endend
13
Esempio calcolo di z1 in un punto (x1y1) di un triangolo lungo una scan-line sullo schermo Lrsquoequazione del piano del triangolo egrave del tipo ax + by + cz + d = 0risolvo rispetto a z e ottengo
z1 = (- d - ax1 - by1)c
noto z1 in (x1y1) si calcola z2 nel pixel successivo della scan-line (x1+x y)
z2 = z1 - xac ma ac =cost x=1 e il calcolo si riduce ad una sottrazione
14
Problemi dello z-buffer
Facce parzialmente sovrapposte molto vicine possono creare deiproblemi a causa dei metodi di calcolo numerico
15
Suddivisione ricorsiva Warnockbull Suddivisione ricorsiva (quad-
tree) dello spazio immagine fino al livello del singolo pixel
bull Criteri di ldquocolorazionerdquondash Un poligono circonda un
quadrante
ndash Un poligono interseca un quadrante
ndash Un poligono egrave contenuto in un quadrante
ndash Poligono e quadrante sono disgiunti
16
Ray casting
bull Adatto a CSG o superfici parametrichebull Dipende dal punto di vistabull Egrave una sorta di ldquocampionamentordquo spaziale della geometria
17
scegli COP e WINDOWfor tutte le linee di scansione do for tutti i pixel nella linea do begin
determina retta COP-pixelfor ogni oggetto nella scena do if retta interseca oggetto e oggetto
egrave il piugrave vicino a COP then attiva pixelend
18
Per il calcolo della intersezione si rappresenta la retta informa parametrica e se lrsquooggetto egrave rappresentato in formaanalitica si calcola lrsquointersezione altrimenti si usano metodinumerici approssimati (es algoritmo di Newton)
Il calcolo delle intersezioni egrave molto costoso si puograve ridurrecon varie tecnichebullbounding box o bounding volumebullorientare la scena con la retta COP-pixel coincidente con zbullorganizzazione gerarchica dei volumibullpartizionamento dello spazio (octree o BSPtree o uniforme)
Ray casting
19
Ray casting CSG
bull Testare le relazioni booleane
20
Se la scena egrave composta di piugrave oggetti con operatoribooleani si determina lrsquooggetto visibile applicandogli operatori booleani ai tratti di retta COP-pixel cheintersecano gli oggetti
Il metodo di ray casting risolve automaticamenteanche il problema delle superfici nascoste
Ray casting CSG
- Superfici nascoste
- Superfici nascoste in scene con poliedri
- PowerPoint Presentation
- Slide 4
- Slide 5
- Slide 6
- Slide 7
- Back face culling
- Slide 9
- Z-Buffer
- Il rendering Z-buffer
- Slide 12
- Slide 13
- Problemi dello z-buffer
- Suddivisione ricorsiva Warnock
- Ray casting
- Slide 17
- Slide 18
- Ray casting CSG
- Slide 20
-
8
Rimozione facce autonascoste e spigoli autonascosti
nDOP gt 0 dove DOP = (0 0 -1)
Si riduce a un test sul segno dinz (ovvero la componente z dellanormale n alla faccia)
Back face culling
9
Per ottimizzare il metodo si ricorre al partizionamento spazialedi due tipi
bull partizionamento regolare (griglie)bull partizionamento adattivo (BSPtree quadtree octree)
bull gerarchie di oggetti
10
Z-Buffer
11
Il rendering Z-bufferIl rendering Z-bufferbull Lo Z-buffer egrave un dispositivo hardware (o simulato via
software) che consente la rimozione delle linee e facce nascoste in tempo reale
bull Per ogni punto immagine di ogni poligono lo Z-bufferZ-buffer mantiene lrsquoinformazione sulla distanza dal punto di vista
12
Procedure z_buffervar pzintegerbegin for y=0 to YMAX do
for x=0 to XMAX dobegin WritePixel(xybackground_color) WriteZbuffer(xy0)endfor each polygon do for each pixel in polygonrsquos projection do begin
pz=polygonrsquos z_value in (xy)if pz gt= ReadZbuffer(xy) thenbegin WriteZbuffer(xypz) WritePixel(xypolygonrsquos color at (xy))end
endend
13
Esempio calcolo di z1 in un punto (x1y1) di un triangolo lungo una scan-line sullo schermo Lrsquoequazione del piano del triangolo egrave del tipo ax + by + cz + d = 0risolvo rispetto a z e ottengo
z1 = (- d - ax1 - by1)c
noto z1 in (x1y1) si calcola z2 nel pixel successivo della scan-line (x1+x y)
z2 = z1 - xac ma ac =cost x=1 e il calcolo si riduce ad una sottrazione
14
Problemi dello z-buffer
Facce parzialmente sovrapposte molto vicine possono creare deiproblemi a causa dei metodi di calcolo numerico
15
Suddivisione ricorsiva Warnockbull Suddivisione ricorsiva (quad-
tree) dello spazio immagine fino al livello del singolo pixel
bull Criteri di ldquocolorazionerdquondash Un poligono circonda un
quadrante
ndash Un poligono interseca un quadrante
ndash Un poligono egrave contenuto in un quadrante
ndash Poligono e quadrante sono disgiunti
16
Ray casting
bull Adatto a CSG o superfici parametrichebull Dipende dal punto di vistabull Egrave una sorta di ldquocampionamentordquo spaziale della geometria
17
scegli COP e WINDOWfor tutte le linee di scansione do for tutti i pixel nella linea do begin
determina retta COP-pixelfor ogni oggetto nella scena do if retta interseca oggetto e oggetto
egrave il piugrave vicino a COP then attiva pixelend
18
Per il calcolo della intersezione si rappresenta la retta informa parametrica e se lrsquooggetto egrave rappresentato in formaanalitica si calcola lrsquointersezione altrimenti si usano metodinumerici approssimati (es algoritmo di Newton)
Il calcolo delle intersezioni egrave molto costoso si puograve ridurrecon varie tecnichebullbounding box o bounding volumebullorientare la scena con la retta COP-pixel coincidente con zbullorganizzazione gerarchica dei volumibullpartizionamento dello spazio (octree o BSPtree o uniforme)
Ray casting
19
Ray casting CSG
bull Testare le relazioni booleane
20
Se la scena egrave composta di piugrave oggetti con operatoribooleani si determina lrsquooggetto visibile applicandogli operatori booleani ai tratti di retta COP-pixel cheintersecano gli oggetti
Il metodo di ray casting risolve automaticamenteanche il problema delle superfici nascoste
Ray casting CSG
- Superfici nascoste
- Superfici nascoste in scene con poliedri
- PowerPoint Presentation
- Slide 4
- Slide 5
- Slide 6
- Slide 7
- Back face culling
- Slide 9
- Z-Buffer
- Il rendering Z-buffer
- Slide 12
- Slide 13
- Problemi dello z-buffer
- Suddivisione ricorsiva Warnock
- Ray casting
- Slide 17
- Slide 18
- Ray casting CSG
- Slide 20
-
9
Per ottimizzare il metodo si ricorre al partizionamento spazialedi due tipi
bull partizionamento regolare (griglie)bull partizionamento adattivo (BSPtree quadtree octree)
bull gerarchie di oggetti
10
Z-Buffer
11
Il rendering Z-bufferIl rendering Z-bufferbull Lo Z-buffer egrave un dispositivo hardware (o simulato via
software) che consente la rimozione delle linee e facce nascoste in tempo reale
bull Per ogni punto immagine di ogni poligono lo Z-bufferZ-buffer mantiene lrsquoinformazione sulla distanza dal punto di vista
12
Procedure z_buffervar pzintegerbegin for y=0 to YMAX do
for x=0 to XMAX dobegin WritePixel(xybackground_color) WriteZbuffer(xy0)endfor each polygon do for each pixel in polygonrsquos projection do begin
pz=polygonrsquos z_value in (xy)if pz gt= ReadZbuffer(xy) thenbegin WriteZbuffer(xypz) WritePixel(xypolygonrsquos color at (xy))end
endend
13
Esempio calcolo di z1 in un punto (x1y1) di un triangolo lungo una scan-line sullo schermo Lrsquoequazione del piano del triangolo egrave del tipo ax + by + cz + d = 0risolvo rispetto a z e ottengo
z1 = (- d - ax1 - by1)c
noto z1 in (x1y1) si calcola z2 nel pixel successivo della scan-line (x1+x y)
z2 = z1 - xac ma ac =cost x=1 e il calcolo si riduce ad una sottrazione
14
Problemi dello z-buffer
Facce parzialmente sovrapposte molto vicine possono creare deiproblemi a causa dei metodi di calcolo numerico
15
Suddivisione ricorsiva Warnockbull Suddivisione ricorsiva (quad-
tree) dello spazio immagine fino al livello del singolo pixel
bull Criteri di ldquocolorazionerdquondash Un poligono circonda un
quadrante
ndash Un poligono interseca un quadrante
ndash Un poligono egrave contenuto in un quadrante
ndash Poligono e quadrante sono disgiunti
16
Ray casting
bull Adatto a CSG o superfici parametrichebull Dipende dal punto di vistabull Egrave una sorta di ldquocampionamentordquo spaziale della geometria
17
scegli COP e WINDOWfor tutte le linee di scansione do for tutti i pixel nella linea do begin
determina retta COP-pixelfor ogni oggetto nella scena do if retta interseca oggetto e oggetto
egrave il piugrave vicino a COP then attiva pixelend
18
Per il calcolo della intersezione si rappresenta la retta informa parametrica e se lrsquooggetto egrave rappresentato in formaanalitica si calcola lrsquointersezione altrimenti si usano metodinumerici approssimati (es algoritmo di Newton)
Il calcolo delle intersezioni egrave molto costoso si puograve ridurrecon varie tecnichebullbounding box o bounding volumebullorientare la scena con la retta COP-pixel coincidente con zbullorganizzazione gerarchica dei volumibullpartizionamento dello spazio (octree o BSPtree o uniforme)
Ray casting
19
Ray casting CSG
bull Testare le relazioni booleane
20
Se la scena egrave composta di piugrave oggetti con operatoribooleani si determina lrsquooggetto visibile applicandogli operatori booleani ai tratti di retta COP-pixel cheintersecano gli oggetti
Il metodo di ray casting risolve automaticamenteanche il problema delle superfici nascoste
Ray casting CSG
- Superfici nascoste
- Superfici nascoste in scene con poliedri
- PowerPoint Presentation
- Slide 4
- Slide 5
- Slide 6
- Slide 7
- Back face culling
- Slide 9
- Z-Buffer
- Il rendering Z-buffer
- Slide 12
- Slide 13
- Problemi dello z-buffer
- Suddivisione ricorsiva Warnock
- Ray casting
- Slide 17
- Slide 18
- Ray casting CSG
- Slide 20
-
10
Z-Buffer
11
Il rendering Z-bufferIl rendering Z-bufferbull Lo Z-buffer egrave un dispositivo hardware (o simulato via
software) che consente la rimozione delle linee e facce nascoste in tempo reale
bull Per ogni punto immagine di ogni poligono lo Z-bufferZ-buffer mantiene lrsquoinformazione sulla distanza dal punto di vista
12
Procedure z_buffervar pzintegerbegin for y=0 to YMAX do
for x=0 to XMAX dobegin WritePixel(xybackground_color) WriteZbuffer(xy0)endfor each polygon do for each pixel in polygonrsquos projection do begin
pz=polygonrsquos z_value in (xy)if pz gt= ReadZbuffer(xy) thenbegin WriteZbuffer(xypz) WritePixel(xypolygonrsquos color at (xy))end
endend
13
Esempio calcolo di z1 in un punto (x1y1) di un triangolo lungo una scan-line sullo schermo Lrsquoequazione del piano del triangolo egrave del tipo ax + by + cz + d = 0risolvo rispetto a z e ottengo
z1 = (- d - ax1 - by1)c
noto z1 in (x1y1) si calcola z2 nel pixel successivo della scan-line (x1+x y)
z2 = z1 - xac ma ac =cost x=1 e il calcolo si riduce ad una sottrazione
14
Problemi dello z-buffer
Facce parzialmente sovrapposte molto vicine possono creare deiproblemi a causa dei metodi di calcolo numerico
15
Suddivisione ricorsiva Warnockbull Suddivisione ricorsiva (quad-
tree) dello spazio immagine fino al livello del singolo pixel
bull Criteri di ldquocolorazionerdquondash Un poligono circonda un
quadrante
ndash Un poligono interseca un quadrante
ndash Un poligono egrave contenuto in un quadrante
ndash Poligono e quadrante sono disgiunti
16
Ray casting
bull Adatto a CSG o superfici parametrichebull Dipende dal punto di vistabull Egrave una sorta di ldquocampionamentordquo spaziale della geometria
17
scegli COP e WINDOWfor tutte le linee di scansione do for tutti i pixel nella linea do begin
determina retta COP-pixelfor ogni oggetto nella scena do if retta interseca oggetto e oggetto
egrave il piugrave vicino a COP then attiva pixelend
18
Per il calcolo della intersezione si rappresenta la retta informa parametrica e se lrsquooggetto egrave rappresentato in formaanalitica si calcola lrsquointersezione altrimenti si usano metodinumerici approssimati (es algoritmo di Newton)
Il calcolo delle intersezioni egrave molto costoso si puograve ridurrecon varie tecnichebullbounding box o bounding volumebullorientare la scena con la retta COP-pixel coincidente con zbullorganizzazione gerarchica dei volumibullpartizionamento dello spazio (octree o BSPtree o uniforme)
Ray casting
19
Ray casting CSG
bull Testare le relazioni booleane
20
Se la scena egrave composta di piugrave oggetti con operatoribooleani si determina lrsquooggetto visibile applicandogli operatori booleani ai tratti di retta COP-pixel cheintersecano gli oggetti
Il metodo di ray casting risolve automaticamenteanche il problema delle superfici nascoste
Ray casting CSG
- Superfici nascoste
- Superfici nascoste in scene con poliedri
- PowerPoint Presentation
- Slide 4
- Slide 5
- Slide 6
- Slide 7
- Back face culling
- Slide 9
- Z-Buffer
- Il rendering Z-buffer
- Slide 12
- Slide 13
- Problemi dello z-buffer
- Suddivisione ricorsiva Warnock
- Ray casting
- Slide 17
- Slide 18
- Ray casting CSG
- Slide 20
-
11
Il rendering Z-bufferIl rendering Z-bufferbull Lo Z-buffer egrave un dispositivo hardware (o simulato via
software) che consente la rimozione delle linee e facce nascoste in tempo reale
bull Per ogni punto immagine di ogni poligono lo Z-bufferZ-buffer mantiene lrsquoinformazione sulla distanza dal punto di vista
12
Procedure z_buffervar pzintegerbegin for y=0 to YMAX do
for x=0 to XMAX dobegin WritePixel(xybackground_color) WriteZbuffer(xy0)endfor each polygon do for each pixel in polygonrsquos projection do begin
pz=polygonrsquos z_value in (xy)if pz gt= ReadZbuffer(xy) thenbegin WriteZbuffer(xypz) WritePixel(xypolygonrsquos color at (xy))end
endend
13
Esempio calcolo di z1 in un punto (x1y1) di un triangolo lungo una scan-line sullo schermo Lrsquoequazione del piano del triangolo egrave del tipo ax + by + cz + d = 0risolvo rispetto a z e ottengo
z1 = (- d - ax1 - by1)c
noto z1 in (x1y1) si calcola z2 nel pixel successivo della scan-line (x1+x y)
z2 = z1 - xac ma ac =cost x=1 e il calcolo si riduce ad una sottrazione
14
Problemi dello z-buffer
Facce parzialmente sovrapposte molto vicine possono creare deiproblemi a causa dei metodi di calcolo numerico
15
Suddivisione ricorsiva Warnockbull Suddivisione ricorsiva (quad-
tree) dello spazio immagine fino al livello del singolo pixel
bull Criteri di ldquocolorazionerdquondash Un poligono circonda un
quadrante
ndash Un poligono interseca un quadrante
ndash Un poligono egrave contenuto in un quadrante
ndash Poligono e quadrante sono disgiunti
16
Ray casting
bull Adatto a CSG o superfici parametrichebull Dipende dal punto di vistabull Egrave una sorta di ldquocampionamentordquo spaziale della geometria
17
scegli COP e WINDOWfor tutte le linee di scansione do for tutti i pixel nella linea do begin
determina retta COP-pixelfor ogni oggetto nella scena do if retta interseca oggetto e oggetto
egrave il piugrave vicino a COP then attiva pixelend
18
Per il calcolo della intersezione si rappresenta la retta informa parametrica e se lrsquooggetto egrave rappresentato in formaanalitica si calcola lrsquointersezione altrimenti si usano metodinumerici approssimati (es algoritmo di Newton)
Il calcolo delle intersezioni egrave molto costoso si puograve ridurrecon varie tecnichebullbounding box o bounding volumebullorientare la scena con la retta COP-pixel coincidente con zbullorganizzazione gerarchica dei volumibullpartizionamento dello spazio (octree o BSPtree o uniforme)
Ray casting
19
Ray casting CSG
bull Testare le relazioni booleane
20
Se la scena egrave composta di piugrave oggetti con operatoribooleani si determina lrsquooggetto visibile applicandogli operatori booleani ai tratti di retta COP-pixel cheintersecano gli oggetti
Il metodo di ray casting risolve automaticamenteanche il problema delle superfici nascoste
Ray casting CSG
- Superfici nascoste
- Superfici nascoste in scene con poliedri
- PowerPoint Presentation
- Slide 4
- Slide 5
- Slide 6
- Slide 7
- Back face culling
- Slide 9
- Z-Buffer
- Il rendering Z-buffer
- Slide 12
- Slide 13
- Problemi dello z-buffer
- Suddivisione ricorsiva Warnock
- Ray casting
- Slide 17
- Slide 18
- Ray casting CSG
- Slide 20
-
12
Procedure z_buffervar pzintegerbegin for y=0 to YMAX do
for x=0 to XMAX dobegin WritePixel(xybackground_color) WriteZbuffer(xy0)endfor each polygon do for each pixel in polygonrsquos projection do begin
pz=polygonrsquos z_value in (xy)if pz gt= ReadZbuffer(xy) thenbegin WriteZbuffer(xypz) WritePixel(xypolygonrsquos color at (xy))end
endend
13
Esempio calcolo di z1 in un punto (x1y1) di un triangolo lungo una scan-line sullo schermo Lrsquoequazione del piano del triangolo egrave del tipo ax + by + cz + d = 0risolvo rispetto a z e ottengo
z1 = (- d - ax1 - by1)c
noto z1 in (x1y1) si calcola z2 nel pixel successivo della scan-line (x1+x y)
z2 = z1 - xac ma ac =cost x=1 e il calcolo si riduce ad una sottrazione
14
Problemi dello z-buffer
Facce parzialmente sovrapposte molto vicine possono creare deiproblemi a causa dei metodi di calcolo numerico
15
Suddivisione ricorsiva Warnockbull Suddivisione ricorsiva (quad-
tree) dello spazio immagine fino al livello del singolo pixel
bull Criteri di ldquocolorazionerdquondash Un poligono circonda un
quadrante
ndash Un poligono interseca un quadrante
ndash Un poligono egrave contenuto in un quadrante
ndash Poligono e quadrante sono disgiunti
16
Ray casting
bull Adatto a CSG o superfici parametrichebull Dipende dal punto di vistabull Egrave una sorta di ldquocampionamentordquo spaziale della geometria
17
scegli COP e WINDOWfor tutte le linee di scansione do for tutti i pixel nella linea do begin
determina retta COP-pixelfor ogni oggetto nella scena do if retta interseca oggetto e oggetto
egrave il piugrave vicino a COP then attiva pixelend
18
Per il calcolo della intersezione si rappresenta la retta informa parametrica e se lrsquooggetto egrave rappresentato in formaanalitica si calcola lrsquointersezione altrimenti si usano metodinumerici approssimati (es algoritmo di Newton)
Il calcolo delle intersezioni egrave molto costoso si puograve ridurrecon varie tecnichebullbounding box o bounding volumebullorientare la scena con la retta COP-pixel coincidente con zbullorganizzazione gerarchica dei volumibullpartizionamento dello spazio (octree o BSPtree o uniforme)
Ray casting
19
Ray casting CSG
bull Testare le relazioni booleane
20
Se la scena egrave composta di piugrave oggetti con operatoribooleani si determina lrsquooggetto visibile applicandogli operatori booleani ai tratti di retta COP-pixel cheintersecano gli oggetti
Il metodo di ray casting risolve automaticamenteanche il problema delle superfici nascoste
Ray casting CSG
- Superfici nascoste
- Superfici nascoste in scene con poliedri
- PowerPoint Presentation
- Slide 4
- Slide 5
- Slide 6
- Slide 7
- Back face culling
- Slide 9
- Z-Buffer
- Il rendering Z-buffer
- Slide 12
- Slide 13
- Problemi dello z-buffer
- Suddivisione ricorsiva Warnock
- Ray casting
- Slide 17
- Slide 18
- Ray casting CSG
- Slide 20
-
13
Esempio calcolo di z1 in un punto (x1y1) di un triangolo lungo una scan-line sullo schermo Lrsquoequazione del piano del triangolo egrave del tipo ax + by + cz + d = 0risolvo rispetto a z e ottengo
z1 = (- d - ax1 - by1)c
noto z1 in (x1y1) si calcola z2 nel pixel successivo della scan-line (x1+x y)
z2 = z1 - xac ma ac =cost x=1 e il calcolo si riduce ad una sottrazione
14
Problemi dello z-buffer
Facce parzialmente sovrapposte molto vicine possono creare deiproblemi a causa dei metodi di calcolo numerico
15
Suddivisione ricorsiva Warnockbull Suddivisione ricorsiva (quad-
tree) dello spazio immagine fino al livello del singolo pixel
bull Criteri di ldquocolorazionerdquondash Un poligono circonda un
quadrante
ndash Un poligono interseca un quadrante
ndash Un poligono egrave contenuto in un quadrante
ndash Poligono e quadrante sono disgiunti
16
Ray casting
bull Adatto a CSG o superfici parametrichebull Dipende dal punto di vistabull Egrave una sorta di ldquocampionamentordquo spaziale della geometria
17
scegli COP e WINDOWfor tutte le linee di scansione do for tutti i pixel nella linea do begin
determina retta COP-pixelfor ogni oggetto nella scena do if retta interseca oggetto e oggetto
egrave il piugrave vicino a COP then attiva pixelend
18
Per il calcolo della intersezione si rappresenta la retta informa parametrica e se lrsquooggetto egrave rappresentato in formaanalitica si calcola lrsquointersezione altrimenti si usano metodinumerici approssimati (es algoritmo di Newton)
Il calcolo delle intersezioni egrave molto costoso si puograve ridurrecon varie tecnichebullbounding box o bounding volumebullorientare la scena con la retta COP-pixel coincidente con zbullorganizzazione gerarchica dei volumibullpartizionamento dello spazio (octree o BSPtree o uniforme)
Ray casting
19
Ray casting CSG
bull Testare le relazioni booleane
20
Se la scena egrave composta di piugrave oggetti con operatoribooleani si determina lrsquooggetto visibile applicandogli operatori booleani ai tratti di retta COP-pixel cheintersecano gli oggetti
Il metodo di ray casting risolve automaticamenteanche il problema delle superfici nascoste
Ray casting CSG
- Superfici nascoste
- Superfici nascoste in scene con poliedri
- PowerPoint Presentation
- Slide 4
- Slide 5
- Slide 6
- Slide 7
- Back face culling
- Slide 9
- Z-Buffer
- Il rendering Z-buffer
- Slide 12
- Slide 13
- Problemi dello z-buffer
- Suddivisione ricorsiva Warnock
- Ray casting
- Slide 17
- Slide 18
- Ray casting CSG
- Slide 20
-
14
Problemi dello z-buffer
Facce parzialmente sovrapposte molto vicine possono creare deiproblemi a causa dei metodi di calcolo numerico
15
Suddivisione ricorsiva Warnockbull Suddivisione ricorsiva (quad-
tree) dello spazio immagine fino al livello del singolo pixel
bull Criteri di ldquocolorazionerdquondash Un poligono circonda un
quadrante
ndash Un poligono interseca un quadrante
ndash Un poligono egrave contenuto in un quadrante
ndash Poligono e quadrante sono disgiunti
16
Ray casting
bull Adatto a CSG o superfici parametrichebull Dipende dal punto di vistabull Egrave una sorta di ldquocampionamentordquo spaziale della geometria
17
scegli COP e WINDOWfor tutte le linee di scansione do for tutti i pixel nella linea do begin
determina retta COP-pixelfor ogni oggetto nella scena do if retta interseca oggetto e oggetto
egrave il piugrave vicino a COP then attiva pixelend
18
Per il calcolo della intersezione si rappresenta la retta informa parametrica e se lrsquooggetto egrave rappresentato in formaanalitica si calcola lrsquointersezione altrimenti si usano metodinumerici approssimati (es algoritmo di Newton)
Il calcolo delle intersezioni egrave molto costoso si puograve ridurrecon varie tecnichebullbounding box o bounding volumebullorientare la scena con la retta COP-pixel coincidente con zbullorganizzazione gerarchica dei volumibullpartizionamento dello spazio (octree o BSPtree o uniforme)
Ray casting
19
Ray casting CSG
bull Testare le relazioni booleane
20
Se la scena egrave composta di piugrave oggetti con operatoribooleani si determina lrsquooggetto visibile applicandogli operatori booleani ai tratti di retta COP-pixel cheintersecano gli oggetti
Il metodo di ray casting risolve automaticamenteanche il problema delle superfici nascoste
Ray casting CSG
- Superfici nascoste
- Superfici nascoste in scene con poliedri
- PowerPoint Presentation
- Slide 4
- Slide 5
- Slide 6
- Slide 7
- Back face culling
- Slide 9
- Z-Buffer
- Il rendering Z-buffer
- Slide 12
- Slide 13
- Problemi dello z-buffer
- Suddivisione ricorsiva Warnock
- Ray casting
- Slide 17
- Slide 18
- Ray casting CSG
- Slide 20
-
15
Suddivisione ricorsiva Warnockbull Suddivisione ricorsiva (quad-
tree) dello spazio immagine fino al livello del singolo pixel
bull Criteri di ldquocolorazionerdquondash Un poligono circonda un
quadrante
ndash Un poligono interseca un quadrante
ndash Un poligono egrave contenuto in un quadrante
ndash Poligono e quadrante sono disgiunti
16
Ray casting
bull Adatto a CSG o superfici parametrichebull Dipende dal punto di vistabull Egrave una sorta di ldquocampionamentordquo spaziale della geometria
17
scegli COP e WINDOWfor tutte le linee di scansione do for tutti i pixel nella linea do begin
determina retta COP-pixelfor ogni oggetto nella scena do if retta interseca oggetto e oggetto
egrave il piugrave vicino a COP then attiva pixelend
18
Per il calcolo della intersezione si rappresenta la retta informa parametrica e se lrsquooggetto egrave rappresentato in formaanalitica si calcola lrsquointersezione altrimenti si usano metodinumerici approssimati (es algoritmo di Newton)
Il calcolo delle intersezioni egrave molto costoso si puograve ridurrecon varie tecnichebullbounding box o bounding volumebullorientare la scena con la retta COP-pixel coincidente con zbullorganizzazione gerarchica dei volumibullpartizionamento dello spazio (octree o BSPtree o uniforme)
Ray casting
19
Ray casting CSG
bull Testare le relazioni booleane
20
Se la scena egrave composta di piugrave oggetti con operatoribooleani si determina lrsquooggetto visibile applicandogli operatori booleani ai tratti di retta COP-pixel cheintersecano gli oggetti
Il metodo di ray casting risolve automaticamenteanche il problema delle superfici nascoste
Ray casting CSG
- Superfici nascoste
- Superfici nascoste in scene con poliedri
- PowerPoint Presentation
- Slide 4
- Slide 5
- Slide 6
- Slide 7
- Back face culling
- Slide 9
- Z-Buffer
- Il rendering Z-buffer
- Slide 12
- Slide 13
- Problemi dello z-buffer
- Suddivisione ricorsiva Warnock
- Ray casting
- Slide 17
- Slide 18
- Ray casting CSG
- Slide 20
-
16
Ray casting
bull Adatto a CSG o superfici parametrichebull Dipende dal punto di vistabull Egrave una sorta di ldquocampionamentordquo spaziale della geometria
17
scegli COP e WINDOWfor tutte le linee di scansione do for tutti i pixel nella linea do begin
determina retta COP-pixelfor ogni oggetto nella scena do if retta interseca oggetto e oggetto
egrave il piugrave vicino a COP then attiva pixelend
18
Per il calcolo della intersezione si rappresenta la retta informa parametrica e se lrsquooggetto egrave rappresentato in formaanalitica si calcola lrsquointersezione altrimenti si usano metodinumerici approssimati (es algoritmo di Newton)
Il calcolo delle intersezioni egrave molto costoso si puograve ridurrecon varie tecnichebullbounding box o bounding volumebullorientare la scena con la retta COP-pixel coincidente con zbullorganizzazione gerarchica dei volumibullpartizionamento dello spazio (octree o BSPtree o uniforme)
Ray casting
19
Ray casting CSG
bull Testare le relazioni booleane
20
Se la scena egrave composta di piugrave oggetti con operatoribooleani si determina lrsquooggetto visibile applicandogli operatori booleani ai tratti di retta COP-pixel cheintersecano gli oggetti
Il metodo di ray casting risolve automaticamenteanche il problema delle superfici nascoste
Ray casting CSG
- Superfici nascoste
- Superfici nascoste in scene con poliedri
- PowerPoint Presentation
- Slide 4
- Slide 5
- Slide 6
- Slide 7
- Back face culling
- Slide 9
- Z-Buffer
- Il rendering Z-buffer
- Slide 12
- Slide 13
- Problemi dello z-buffer
- Suddivisione ricorsiva Warnock
- Ray casting
- Slide 17
- Slide 18
- Ray casting CSG
- Slide 20
-
17
scegli COP e WINDOWfor tutte le linee di scansione do for tutti i pixel nella linea do begin
determina retta COP-pixelfor ogni oggetto nella scena do if retta interseca oggetto e oggetto
egrave il piugrave vicino a COP then attiva pixelend
18
Per il calcolo della intersezione si rappresenta la retta informa parametrica e se lrsquooggetto egrave rappresentato in formaanalitica si calcola lrsquointersezione altrimenti si usano metodinumerici approssimati (es algoritmo di Newton)
Il calcolo delle intersezioni egrave molto costoso si puograve ridurrecon varie tecnichebullbounding box o bounding volumebullorientare la scena con la retta COP-pixel coincidente con zbullorganizzazione gerarchica dei volumibullpartizionamento dello spazio (octree o BSPtree o uniforme)
Ray casting
19
Ray casting CSG
bull Testare le relazioni booleane
20
Se la scena egrave composta di piugrave oggetti con operatoribooleani si determina lrsquooggetto visibile applicandogli operatori booleani ai tratti di retta COP-pixel cheintersecano gli oggetti
Il metodo di ray casting risolve automaticamenteanche il problema delle superfici nascoste
Ray casting CSG
- Superfici nascoste
- Superfici nascoste in scene con poliedri
- PowerPoint Presentation
- Slide 4
- Slide 5
- Slide 6
- Slide 7
- Back face culling
- Slide 9
- Z-Buffer
- Il rendering Z-buffer
- Slide 12
- Slide 13
- Problemi dello z-buffer
- Suddivisione ricorsiva Warnock
- Ray casting
- Slide 17
- Slide 18
- Ray casting CSG
- Slide 20
-
18
Per il calcolo della intersezione si rappresenta la retta informa parametrica e se lrsquooggetto egrave rappresentato in formaanalitica si calcola lrsquointersezione altrimenti si usano metodinumerici approssimati (es algoritmo di Newton)
Il calcolo delle intersezioni egrave molto costoso si puograve ridurrecon varie tecnichebullbounding box o bounding volumebullorientare la scena con la retta COP-pixel coincidente con zbullorganizzazione gerarchica dei volumibullpartizionamento dello spazio (octree o BSPtree o uniforme)
Ray casting
19
Ray casting CSG
bull Testare le relazioni booleane
20
Se la scena egrave composta di piugrave oggetti con operatoribooleani si determina lrsquooggetto visibile applicandogli operatori booleani ai tratti di retta COP-pixel cheintersecano gli oggetti
Il metodo di ray casting risolve automaticamenteanche il problema delle superfici nascoste
Ray casting CSG
- Superfici nascoste
- Superfici nascoste in scene con poliedri
- PowerPoint Presentation
- Slide 4
- Slide 5
- Slide 6
- Slide 7
- Back face culling
- Slide 9
- Z-Buffer
- Il rendering Z-buffer
- Slide 12
- Slide 13
- Problemi dello z-buffer
- Suddivisione ricorsiva Warnock
- Ray casting
- Slide 17
- Slide 18
- Ray casting CSG
- Slide 20
-
19
Ray casting CSG
bull Testare le relazioni booleane
20
Se la scena egrave composta di piugrave oggetti con operatoribooleani si determina lrsquooggetto visibile applicandogli operatori booleani ai tratti di retta COP-pixel cheintersecano gli oggetti
Il metodo di ray casting risolve automaticamenteanche il problema delle superfici nascoste
Ray casting CSG
- Superfici nascoste
- Superfici nascoste in scene con poliedri
- PowerPoint Presentation
- Slide 4
- Slide 5
- Slide 6
- Slide 7
- Back face culling
- Slide 9
- Z-Buffer
- Il rendering Z-buffer
- Slide 12
- Slide 13
- Problemi dello z-buffer
- Suddivisione ricorsiva Warnock
- Ray casting
- Slide 17
- Slide 18
- Ray casting CSG
- Slide 20
-
20
Se la scena egrave composta di piugrave oggetti con operatoribooleani si determina lrsquooggetto visibile applicandogli operatori booleani ai tratti di retta COP-pixel cheintersecano gli oggetti
Il metodo di ray casting risolve automaticamenteanche il problema delle superfici nascoste
Ray casting CSG
- Superfici nascoste
- Superfici nascoste in scene con poliedri
- PowerPoint Presentation
- Slide 4
- Slide 5
- Slide 6
- Slide 7
- Back face culling
- Slide 9
- Z-Buffer
- Il rendering Z-buffer
- Slide 12
- Slide 13
- Problemi dello z-buffer
- Suddivisione ricorsiva Warnock
- Ray casting
- Slide 17
- Slide 18
- Ray casting CSG
- Slide 20
-