Computer Graphics
Marco Tarini
Lezione 3: modellare con triangoli
Università dell’Insubria
Facoltà di Scienze MFN di Varese Corso di Laurea in Informatica Anno Accademico 2012/13
M a r c o T a r i n i ‧ C o m p u t e r G r a p h i c s ‧ 2 0 1 2 / 1 3 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Rasterization-based HW-supported rendering
• tutto sia composto da triangoli (3D) – o al limite da punti, o segmenti
•ma....
...non tutto nasce composto di triangoli quasi nulla
M a r c o T a r i n i ‧ C o m p u t e r G r a p h i c s ‧ 2 0 1 2 / 1 3 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Tutto sia composto da triangoli (3D)
un quadrilatero?
"quad" "diagonal split"
due triangoli!
M a r c o T a r i n i ‧ C o m p u t e r G r a p h i c s ‧ 2 0 1 2 / 1 3 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Tutto sia composto da triangoli (3D)
un poligono a n lati?
triangolarizzazione di poligono:
(in 3D, non un problema del tutto banale...) (n-2) triangoli!
M a r c o T a r i n i ‧ C o m p u t e r G r a p h i c s ‧ 2 0 1 2 / 1 3 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
triangoli!
Tutto sia composto da triangoli (3D)
la superficie di un solido geometrico, per es. una sfera?
M a r c o T a r i n i ‧ C o m p u t e r G r a p h i c s ‧ 2 0 1 2 / 1 3 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
triangoli!
Tutto sia composto da triangoli (3D)
la superficie di
un solido geometrico,
per es. una sfera?
M a r c o T a r i n i ‧ C o m p u t e r G r a p h i c s ‧ 2 0 1 2 / 1 3 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
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 ‧ C o m p u t e r G r a p h i c s ‧ 2 0 1 2 / 1 3 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
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 ‧ C o m p u t e r G r a p h i c s ‧ 2 0 1 2 / 1 3 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
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 ‧ C o m p u t e r G r a p h i c s ‧ 2 0 1 2 / 1 3 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Tutto sia composto da triangoli (3D)
nuvola di punti ?
(point cloud) triangoli!
problema molto studiato, e (nel caso generale) difficile
Algoritmi comuni: “Ball Pivoting”
x
y z
x
y z
M a r c o T a r i n i ‧ C o m p u t e r G r a p h i c s ‧ 2 0 1 2 / 1 3 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
da nuvola di punti a triangoli: esempio
M a r c o T a r i n i ‧ C o m p u t e r G r a p h i c s ‧ 2 0 1 2 / 1 3 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Tutto sia composto da triangoli (3D)
volume? triangoli!
algoritmi di segmentation (e.g. "marching cubes" * )
triangoli che definiscono
iso-superficie una
Passare da volume a superficie
M a r c o T a r i n i ‧ C o m p u t e r G r a p h i c s ‧ 2 0 1 2 / 1 3 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Dataset Volumetrico:
- griglia 3D regolare di valori di densità - campionamento regolare in 3D - es: output di una scansione TAC - es in C:
densità: 0.3 densità: 0.45
…
float volume[RES_X] [RES_Y] [RES_Z]
consumo memoria cubico con la risoluzione
(diventa facilmenteingestibile)
Passare da volume a superficie
M a r c o T a r i n i ‧ C o m p u t e r G r a p h i c s ‧ 2 0 1 2 / 1 3 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Dataset Volumetrico V
algoritmo
“Marching- Cubes”
Iso-superficie Triangolata
(di valore s) S
• s = valore soglia
• superficie (chiusa) dove il valore del campo = s
• racchiude i punti di V che hanno valore > s
M a r c o T a r i n i ‧ C o m p u t e r G r a p h i c s ‧ 2 0 1 2 / 1 3 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Da dataset volumetrico a triangoli: altro esempio
M a r c o T a r i n i ‧ C o m p u t e r G r a p h i c s ‧ 2 0 1 2 / 1 3 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Tutto sia composto da triangoli (3D)
superfici implicite?
Superficie implicita
• E’ il luogo degli zeri di una funzione data:
(tutti i punti p t.c. f (p) = 0 )
• Nota: definiscono un “dentro” e un “fuori”:
– f (p) < 0 <==> p dentro – f (p) > 0 <==> p fuori
– f (p) = 0 <==> p sulla superficie
…sono oggetti solidi! (superfici “watertight”)
M a r c o T a r i n i ‧ C o m p u t e r G r a p h i c s ‧ 2 0 1 2 / 1 3 ‧ U n i v e r s i t à d e l l ’ I n s u b r i aR R f : 3 →
Superficie implicita
• Es…
M a r c o T a r i n i ‧ C o m p u t e r G r a p h i c s ‧ 2 0 1 2 / 1 3 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
2 2 2
2 y z R
x z y x
f = + + −
z
x y
Giocare con le sup implicite: GSM
• Molto convenienti…
• Siano A e B oggetti solidi delimitati da superfici implicite, con funzioni f A e f B
• Posso definire (come sup implicite):
– inversioni: - f A
– intersezioni: max( f A , f B ) – unioni: min( f A , f B ) – scavi: max( f A , - f B )
M a r c o T a r i n i ‧ C o m p u t e r G r a p h i c s ‧ 2 0 1 2 / 1 3 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
A B
Geometric Solid Modelling
M a r c o T a r i n i ‧ C o m p u t e r G r a p h i c s ‧ 2 0 1 2 / 1 3 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
////
Geometric Solid Modelling
M a r c o T a r i n i ‧ C o m p u t e r G r a p h i c s ‧ 2 0 1 2 / 1 3 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
min max min
max
--
f 4 f 4
f 5
f 2 f 1
M a r c o T a r i n i ‧ C o m p u t e r G r a p h i c s ‧ 2 0 1 2 / 1 3 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Tutto sia composto da triangoli (3D)
superfici implicite? triangoli!
nb: non c'e' un modo solo per farlo.
Modo + semplice (non ottimo): campionare volume e estrarre isosuperfice a valore 0
triangoli che definiscono
la superficie esplicitamente
M a r c o T a r i n i ‧ C o m p u t e r G r a p h i c s ‧ 2 0 1 2 / 1 3 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Tornando allo schema generale...
applicazione interattiva mondo reale
/ modello matematico / artista 3D ...
Geometria
Immagine/i
rendering
preprocessing (modelling)
acquisizione 3D / simulazione / modellazione
(e.g. 3Dstudio max, Maya)
M a r c o T a r i n i ‧ C o m p u t e r G r a p h i c s ‧ 2 0 1 2 / 1 3 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Tipica fase di preporsessing
Geometria
Immagine/i rendering
preprocessing (modelling)
diagonal split (da quad a 2 tri) può venire fatto anche qui, al volo
diagonal split (da quad a 2 tri) può venire fatto anche qui, al volo
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 ‧ C o m p u t e r G r a p h i c s ‧ 2 0 1 2 / 1 3 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a