Computer Graphics
Lezione 2: hardware ergo triangoli
Università dell’Insubria
Facoltà di Scienze MFN di Varese
Corso di Laurea in Informatica
Anno Accademico 2006/07
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
Marco Tarini ‧ Computer Graphics ‧
2006/07 ‧ Università dell’Insubria - 2
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
Marco Tarini ‧ Computer Graphics ‧
2006/07 ‧ Università dell’Insubria - 3
Riassunto puntata precedente 3/3
• Ci occuperemo principalmente di:
Real Time 3D Rendering
Scena 3D
resto dell'
applicazione
Marco Tarini ‧ Computer Graphics ‧
rendering
Immagine
N volte al sec
screen buffer
( e.g. N=60 )
( array 2D di pixel )
2006/07 ‧ Università dell’Insubria - 4
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
Marco Tarini ‧ Computer Graphics ‧
2006/07 ‧ Università dell’Insubria - 5
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
(come vedremo...)
• sono piu' di 32 bit x pixel
• C'è bisogno di muscoli potenza di calcolo
Marco Tarini ‧ Computer Graphics ‧
2006/07 ‧ Università dell’Insubria - 6
Real Time 3D Rendering
• Problema difficile
– fortunatamente,
processo massicciamente parallelizzabile
• Ingrediente base della soluzione:
hardware specializzato
Marco Tarini ‧ Computer Graphics ‧
2006/07 ‧ Università dell’Insubria - 7
Sistemi Multimediali II
• Ci occuperemo principalmente di:
Real-Time
Hardware-Based
3D Rendering
Marco Tarini ‧ Computer Graphics ‧
2006/07 ‧ Università dell’Insubria - 8
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...
Marco Tarini ‧ Computer Graphics ‧
2006/07 ‧ Università dell’Insubria - 9
Paradigmi di rendering
•
•
•
•
•
•
Raytracing
Rasterization based
Image based (per es. light filed)
Radiosity
Point-splatting
...
Marco Tarini ‧ Computer Graphics ‧
2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 10
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
Marco Tarini ‧ Computer Graphics ‧
2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 11
Hardware dedicato alla grafica : storia
• aumento potenza
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
Marco Tarini ‧ Computer Graphics ‧
Year
94
96
98
00
2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 12
Hardware dedicato alla grafica : storia
• aumento potenza
Virtua Fighter
Dead or Alive 3
Dawn
(SEGA)
(Tecmo Corp., Xbox)
(NVIDIA)
50K triangles/sec
100M triangles/sec
200M triangles/sec
1995
2001
2002
Marco Tarini ‧ Computer Graphics ‧
2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 13
Hardware dedicato alla grafica : storia
• aumento capabilities
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
transform and lighting
HW supported… polygon fill
HW supported… color interpolation (Goroud)
HW supported… texture mapping
HW supported… per-pixel shading (Phong)
HW supported… alpha blending
HW supported… fog computation
HW supported… Z-buffers
HW supported… bump-mapping
HW supported… environment mapping (“Cube-maps”)
HW supported… stencil buffers (per pixel masks)
HW supported… color transform matrices
HW supported… paletted textures
HW supported… multiple texture accesses
HW supported… texture filtering (MIP-maps)
HW supported… Level-of-Detail computation
HW supported… dependent texturing
HW supported…
…
• Programmable HW
Marco Tarini ‧ Computer Graphics ‧
2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 14
Hardware dedicato alla grafica : storia
• Progresso congiunto HW e Algoritmi
tecnologia
ruota
Marco Tarini ‧ Computer Graphics ‧
tecnologia
strada
sviluppi hardware
tecniche algoritmiche
– Un po come ruota e strada
2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 15
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
Marco Tarini ‧ Computer Graphics ‧
2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 16
Paradigmi di rendering
Rendering Paradigm:
(Triangle-) Rasterization Based
•
•
•
•
•
•
Raytracing
detto anche:
Transform and Lighting
Rasterization based
( Tlight
& Lfiled)
)
Image based (per es.
Radiosity
I. Che si usino solo
Point-splatting
le seguenti primitive di rendering :
triangoli, segmenti, punti
...
Marco Tarini ‧ Computer Graphics ‧
2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 17
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
Marco Tarini ‧ Computer Graphics ‧
v1 =( x1, y1, z1 )
z
2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 18
Rasterization-based HW-supported rendering
• tutto sia composto da triangoli (3D)
– o al limite da punti, o segmenti
• non tutto nasce composto di triangoli...
Marco Tarini ‧ Computer Graphics ‧
2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 19
Tutto sia composto da triangoli (3D)
due triangoli!
un quadrilatero?
"quad"
"diagonal split"
Marco Tarini ‧ Computer Graphics ‧
2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 20
Tutto sia composto da triangoli (3D)
un poligono a n lati?
(n-2) triangoli!
triangolarizzazione di poligono:
(in 3D, non un problema del tutto banale...)
Marco Tarini ‧ Computer Graphics ‧
2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 21
Tutto sia composto da triangoli (3D)
la superficie di
un solido geometrico,
per es. una sfera?
Marco Tarini ‧ Computer Graphics ‧
triangoli!
2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 22
Tutto sia composto da triangoli (3D)
la superficie di
un solido geometrico,
per es. una cono?
Marco Tarini ‧ Computer Graphics ‧
triangoli!
2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 23
Tutto sia composto da triangoli (3D)
un campo d'altezza?
(array 2D di altezze,
e.g. per modellare un terreno?)
Marco Tarini ‧ Computer Graphics ‧
triangoli!
2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 24
Esempio di campo di altezza triangolato
• "height field"
• un esempio tipico:
– campo d'altezza per modellare un terreno...
Marco Tarini ‧ Computer Graphics ‧
2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 25
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
M a r c o più
T aavanti
r i n i nel
‧ Ccorso,
o m p use
t ec'è
r Gtempo
r a p h i c s ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 26
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
Marco Tarini ‧ Computer Graphics ‧
2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 27
da nuvola di punti a triangoli: esempio
Marco Tarini ‧ Computer Graphics ‧
2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 28
Tutto sia composto da triangoli (3D)
triangoli
che definiscono
una
iso-superficie
volume?
triangoli!
algoritmi di segmentation
(e.g. "marching cubes" * )
* verdemo
M a r c o più
T aavanti
r i n i nel
‧ Ccorso,
o m p use
t ec'è
r Gtempo
r a p h i c s ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 29
Da dataset volumetrico a triangoli: esempio
Marco Tarini ‧ Computer Graphics ‧
2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 30
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
Marco Tarini ‧ Computer Graphics ‧
2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 31
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
Marco Tarini ‧ Computer Graphics ‧
2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 32
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
Marco Tarini ‧ Computer Graphics ‧
2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 33
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
Marco Tarini ‧ Computer Graphics ‧
2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 34
Modellare direttamente con triangoli
• rappresentare gli oggetti con triangoli
– o al limite da punti, o linee
un coniglio
di porcellana?
una teiera?
triangoli, triangoli, triangoli
Marco Tarini ‧ Computer Graphics ‧
2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 35
Modellare direttamente con triangoli
• rappresentare gli oggetti con triangoli
– o anche quads
– o al limite da punti, o linee
Marco Tarini ‧ Computer Graphics ‧
2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 36
Modellare direttamente con triangoli
Marco Tarini ‧ Computer Graphics ‧
Phillip
1994
2 0 0 6 / 0 7 ‧ U n i v e r s i t àby d
e l l ’ Heckinger
I n s u b r i(3D
a - modeller)
37
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)
Marco Tarini ‧ Computer Graphics ‧
by M. Turitzin and J. Jacobs
Stanford Uni (real time!)
2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 38
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
Marco Tarini ‧ Computer Graphics ‧
2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 39
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
Marco Tarini ‧ Computer Graphics ‧
2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 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
Marco Tarini ‧ Computer Graphics ‧
nVIDIA tech demo at SIGGRAPH 2001
nVIDIA quadro
2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 41
nVIDIA technology demo at SIGGRAPH 2004
=REAL
M aTIME!=
rco Tarini ‧ Comput
er Graphics ‧
2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 42