Sistemi Multimediali II
Lezione 2: hardware ergo triangoli
Università dell’Insubria
Facoltà di Scienze MFN di Varese
Corso di Laurea in Informatica
Anno Accademico 2004/05
Marco Tarini
Riassunto puntata precedente 1/3
• Computer Graphics ( CG ):
– molteplici applicazioni
–
–
–
–
–
–
–
–
–
–
medicali
industriali
beni culturali
militari 
telecomunicazioni
commerciali
ricerca scientifica (scivis)
intrattenimento: games
intrattenimento: movies
e altro (realta' virtuale....)
– campo in forte progresso
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 2/40
Riassunto puntata precedente 2/3
acquisizione 3D
/ simulazione
/ modellazione
mondo reale
/ modello matematico
/ artista 3D ...
(e.g. 3Dstudio max, Maya)
Geometria
preprocessing
(modelling)
rendering
Immagine/i
applicazione interattiva
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 3/40
Riassunto puntata precedente 3/3
• Ci occuperemo principalmente di:
Real Time 3D Rendering
Scena 3D
resto dell'
applicazione
rendering
Immagine
N volte al sec
screen buffer
( e.g. N=60 )
( array 2D di pixel )
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 4/40
Real Time 3D Rendering
Problema challanging!
per esempio:
• pixel = 32 bit = 4 bytes ("pixel depth")
• screen buffer = 1024 x 768 pixels ("screen resolution")
• frame rate = 60 Hrz ("fps")
• total = 4 x 1024 x 768 x 60 byte al sec ("fill-rate", in bytes)
188 MegaBytes / sec
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 5/40
Real Time 3D Rendering
• Fill-rates molto elevati
– Anticipazione:
...e il fill-rate non è sempre il collo di bottiglia
– Anticipazione 2:
...e quella e' una sottostima del fill-rate.
• manca il fattore depth-complexity ~
~ x2.5
• sono piu' di 32 bit x pixel
• C'è bisogno di muscoli potenza di calcolo
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 6/40
Real Time 3D Rendering
• Problema difficile
– fortunatamente,
processo massicciamente parallelizzabile
• Ingrediente base della soluzione:
hardware specializzato
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 7/40
Sistemi Multimediali II
• Ci occuperemo principalmente di:
Real-Time
Hardware-Based
3D Rendering
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 8/40
Hardware specializzato per il rendering
• Vantaggio: efficienza
• computazioni più ripetute hard-wired nel chipset
• parallelismo rendering/resto-dell-applicazione:
– rendering nella scheda grafica
– resto dell'applicazione libera di utilizzare la CPU e RAM base
MA SOPRATTUTTO:
• sfruttamento del parallelismo implicito nel problema di
rendering
– sotto forma di parallelismo di pipeline
– sotto forma di parallelismo in ogni fase del pipeline
• Svantaggio: rigidità
• vincola l'approccio usato per fare rendering...
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 9/40
Paradigmi di rendering
•
•
•
•
•
•
Raytracing
Rasterization based
Image based (per es. light filed)
Radiosity
Point-splatting
...
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 10/40
Hardware dedicato alla grafica
• storia
– ~20 anni:
• dalla metà degli '80 (e.g.: SGI Iris - 1986)
– dalla metà dei '90, il fiaccola passa dai mainframes ai PC
– progressi enormi
• nella efficienza
– piu' che "Moore’s Law": ~2.4x / year invece di ~1.6 / year
• nella funzionalità
– i dettagli storici saltiamoli per ora
» a mano a mano che vedremo le tecniche diremo quando
sono state introdotte
– filosofia di fondo rimasta la stessa
• paradigma di rendering:
basato principalmente su rasterizzazione di triangoli
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 11/40
Hardware dedicato alla grafica
• storia
109
One-pixel polygons (~10M polygons @ 30Hz)
GeForce 3
& Radeon
108
UNC/HP PixelFlow
Peak
Perf.
SGI
R-Monster
SGI
IR
107
Division
Pxpl6
UNC Pxpl5
('s/sec)
SGI SkyWriter
106
SGI VGX
Flat
shading
105
UNC Pxpl4
HP VRX
SGI GT
SGI Iris
86
88
Gouraud
shading
90
Megatek
E&S Freedom
SGI
RE2
E&S
F300
Stellar GS1000
HP CRX
104
HP TVRX
SGI
RE1
Nvidia TNT
E&S
3DLabs
SGI
Harmony
Cobalt
Glint
Accel/VSIS
Voodoo
PC Graphics
Division VPX
Textures
Antialiasing
92
Year
94
96
98
00
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 12/40
Progresso congiunto HW e Algoritmi
tecnologia
ruota
tecnologia
strada
sviluppi hardware
tecniche algoritmiche
• Un po come ruota e strada
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 13/40
Rasterization-based HW-supported rendering
• anche riferito come
Transform and Lighting (T&L) paradigm
Scena 3D
rendering
screen
buffer
composta da primitive di
pochissimi tipi:
• punti
primitive
• linee
MA SOPRATUTTO
• triangoli
di
rendering
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 14/40
Rasterization-based HW-supported rendering
• punto primo: tutto sia composto da triangoli (3D)
– o al limite da punti, o segmenti
x
v0 =( x0, y0, z0 )
v2 =( x2, y2, z2 )
y
v1 =( x1, y1, z1 )
z
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 15/40
Rasterization-based HW-supported rendering
• tutto sia composto da triangoli (3D)
– o al limite da punti, o segmenti
• non tutto nasce composto di triangoli...
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 16/40
Tutto sia composto da triangoli (3D)
due triangoli!
un quadrilatero?
"quad"
"diagonal split"
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 17/40
Tutto sia composto da triangoli (3D)
un poligono a n lati?
(n-2) triangoli!
triangolarizzazione di poligono:
(non un problema banale...)
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 18/40
Tutto sia composto da triangoli (3D)
la superficie di
un solido geometrico,
per es. una sfera?
triangoli!
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 19/40
Tutto sia composto da triangoli (3D)
la superficie di
un solido geometrico,
per es. una cono?
triangoli!
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 20/40
Tutto sia composto da triangoli (3D)
un campo d'altezza?
(array 2D di altezze,
e.g. per modellare un terreno?)
triangoli!
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 21/40
Esempio di campo di altezza triangolato
• "height field"
• un esempio tipico:
– campo d'altezza per modellare un terreno...
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 22/40
Tutto sia composto da triangoli (3D)
una superficie curva
parametrica?
triangoli!
per es. NURBS *, b-splines *...
questo è facile. Il contrario, che qualche
volta è utile, MOLTO meno
* verdemo
avanti
M
a r c o T apiù
rin
i ‧ S inel
s t ecorso,
m i Mse
u lc'è
t i mtempo
e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 23/40
Tutto sia composto da triangoli (3D)
x
x
y
z
z
y
nuvola di punti ?
(point clouds)
triangoli!
problema molto studiato,
e (nel caso generale) difficile
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 24/40
da nuvola di punti a triangoli: esempio
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 25/40
Tutto sia composto da triangoli (3D)
triangoli
che definiscono
una
iso-superficie
volume?
triangoli!
algoritmi di segmentation
(e.g. "marching cubes" * )
* verdemo
avanti
M
a r c o T apiù
rin
i ‧ S inel
s t ecorso,
m i Mse
u lc'è
t i mtempo
e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 26/40
Da dataset volumetrico a triangoli: esempio
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 27/40
Tutto sia composto da triangoli (3D)
triangoli
che definiscono
la superficie
esplicitamente
superfici implicite?
triangoli!
nb: non c'e' un modo solo per farlo.
Modo + semplice (non ottimo): campionare volume e
estrarre isosuperfice a valore 0
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 28/40
Tornando allo schema generale...
acquisizione 3D
/ simulazione
/ modellazione
mondo reale
/ modello matematico
/ artista 3D ...
(e.g. 3Dstudio max, Maya)
Geometria
preprocessing
(modelling)
rendering
Immagine/i
applicazione interattiva
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 29/40
Tipica fase di preporsessing
Geometria
preprocessing
(modelling)
diagonal split
(da quad a 2 tri)
può venire fatto
anche qui, al volo
rendering
Immagine/i
Tutto il resto che abbiamo visto
nei lucidi precedenti
(trasformazione
in triangoli) tipicamente qui
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 30/40
Riassuntino
Forme geo.
di base
Superfici
parametriche
n-agoni
Dati Volumetrici
Superfici implicite
"al volo"
Triangoli
Quads
Campi d'altezza
r
e
n
d
e
r
i
n
g
Nuvole di punti
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 31/40
Modellare direttamente con triangoli
• rappresentare gli oggetti con triangoli
– o al limite da punti, o linee
una teiera?
un coniglio
di porcellana?
triangoli, triangoli, triangoli
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 32/40
Modellare direttamente con triangoli
• rappresentare gli oggetti con triangoli
– o anche quads
– o al limite da punti, o linee
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 33/40
Modellare direttamente con triangoli
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t by
à Phillip
d e l l ’Heckinger
I n s u b r (3D
i a -modeller)
34/40 1994
Un limite di questo approccio
• Non sempre e' semplice modellare le entità da
rappresentare con triangoli...
– esempi:
• nuvole
• fuoco
• pelliccia
by Niniane Wang
(non real time)
by N. Adabala uni florida
(non real time)
by M. Turitzin and J. Jacobs
Stanford Uni (real time!)
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 35/40
Per dirla tutta sulle primitive di rendering
• Triangoli
– ok, abbiamo capito
Tutto l'hardware è progettato
e ottimizzato
principalmente per
questo caso
• Quads
– in un certo senso, perchè
diventano triangoli al volo
• Segmenti
• Punti
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 36/40
Per dirla tutta sulle primitive di rendering
• Triangoli
– ok, abbiamo capito
• Quads
utili ad esempio
per particle systems
– in un certo senso, perchè
diventano triangoli al volo
• Segmenti
• Punti
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 37/40
Per dirla tutta sulle primitive di rendering
• Triangoli
– ok, abbiamo capito
• Quads
– in un certo senso, perchè
diventano triangoli al volo
utile ad esempio per fare
rendering
di capelli peli etc
(ma non è l'unico sistema
e non è detto che sia il migliore)
• Segmenti
• Punti
nVIDIA tech demo at SIGGRAPH 2001
nVIDIA quadro
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 38/40
nVIDIA technology demo at SIGGRAPH 2004
=REAL
M
a r c TIME!=
o Tarini ‧ Sistemi M
u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 39/40