Sistemi Multimediali II
Lezione 8:
Università dell’Insubria
Facoltà di Scienze MFN di Varese
Corso di Laurea in Informatica
Anno Accademico 2004/05
Marco Tarini
meshes
Mesh triangolare (o mesh simpliciale)
• Una mesh è un insieme di triangoli adiacenti
facce
vertici
spigoli
(o edges)
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
Caratteristiche topologiche di una mesh
• Two Manifold ("varietà due") o no
– se si ogni edge è condiviso da al max due faccie
• two manifold = bene
• non two manifold = male
• molti algoritmi su mesh richiedono che la mesh sia twomanifold
NO
SI
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
Caratteristiche topologiche di una mesh
• Chiusa o aperta
– se chiusa, ogni edge è condiviso proprio due faccie
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
Caratteristiche topologiche di una mesh
• Orientabile, non orientabile
– è possibile assegnare un orientamento ad ogni
faccia coerentemente?
– orientabile = normali coerenti!
1
3
2
3
1
2
senso opposto, edge coerente
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
Come definisco una mesh?
• Una mesh è un insieme di triangoli adiacenti
• Come la definisco?
• Modo diretto:
– un vettore di triangoli
– e per ogni triangolo tre vertici
– e per ogni vertice tre coordinate
• Piuttosto poco efficiente
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
Come definisco una mesh?
• Modo indexed
– Lista ordinata di vertici
• per ogni vertice la posizione
– Lista ordinata di facce
• per ogni faccia, 3 indici di vertici
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
E gli attributi?
• Posso definirli:
– per vertice
• scrivo un attributo dopo ogni vertice
– per faccia
• scrivo un attributo dopo ogni faccia
– per wedge (vertice di faccia)
• scrivo tre attributi dopo ogni faccia
• Attributi più comuni:
– colore
– coordinate texture
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
Esempio: formato PLY
• E' un formato digitale per mesh
• Puo' essere in binario, o in ASCII (testo)
– binario: più compatto e veloce da leggere
– ascii: umanamente leggibile con un editore di testo
• In ogni caso, comincia con un header in ASCII
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
Esempio: formato PLY
• Esempio:
cubo.ply
ply
format ascii 1.0
comment proprio un cubetto
element vertex 8
property float x
property float y
property float z
element face 12
property list uchar int vertex_indices
end_header
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
Esempio: formato OFF
• Esempio:
# facce # edges
# vertici
x,y,z
2ndo
vert
OFF
12 10 40
0 0 0
3 0 0
3 1 0
1 1 0
1 5 0
0 5 0
0 0 1
3 0 1
3 1 1
1 1 1
indice 0
indice 1
indice 2
indice 3
LetteraL.ply
1
0
4
4
4
4
4
4
4
4
4
4
5
5
3
5
6
6
0
1
2
3
4
5
1
1
2
4
7
9
1
2
3
4
5
0
1 0
3 0
8 9
10 11
7 6
8 7
9 8
10 9
11 10
6 11
prima faccia:
4 vertici:
con indici
3, 2, 1 e 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 - 11/40
Mesh: task comuni
• Data una mesh:
– magari appena caricata
• trovare il bounding box
– utile ad esempio
per translare e scalare
l'oggetto opportunamente
– come si fa?
• (si itera sui vertici:
trovare il max e il min
di tutte le x, le y e le 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 - 12/40
Mesh: task comuni
• Data una mesh:
– magari appena caricata
• trovare le normali per vertice
– come si fa?
1 azzerare tutte le norm x vertice
2 iterare ogni faccia:
trovare normale
normalizzare normale
aggiungere normale al vertice
3 iterare ogni vertice:
normalizzarlo
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
Task più difficili
•
•
•
•
•
•
Bounding sphere
Stripification
Parametrizzazione
Simplificazione automatica
Detail recovery
...
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
Task più difficili
• Stripification
– suddividere i triangoli in triangle strips
• più lunghe possibile
– perche?
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
Task più difficili
• Parametrizzazione
– assegnare una coppia di coordinate texutre
ad ogni vertice
– ci sono seams
• replicare i vertici
• memorizzale le text coord per wedge
v
u
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
Task più difficili
• Semplificazione automatica
• parametri:
– un errore massimo
– o un numero di facce obiettivo
automaticamente
mesh originale
mesh semplificata
M a r c o T a r i n i ‧500K
S i s t etriangoli
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 s2K
i t àtriangles
d e l l ’ I n s u b r i a - 17/40
Semplificazione automatica
performance
quality
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
Semplificazione automatica
Una piramide di Livelli di Dettaglio
LOD 1
usare quando
visto da vicino
LOD 2
LOD 3
LOD 4
usare quando
visto da lontano
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
Detail preservation
(o texture for geometry)
• Idea:
– sintetizzare una tessitura
– per ripristinare il dettaglio perso durante la
semplificazione
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
500mila
triangoli
detail
recover
TESSITURA
fatta apposta
semplificazione
automatica
2mila
triangoli
rendering
sempre duemila triangoli, ma con texture mapping
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
originale
semplificato
simplified
ma con tessitura
500K triangles
2K triangles
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