1

Superfici nascoste

Daniele Marini

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