Sistemi Multimediali II
Marco Tarini
Università dell’Insubria
Facoltà di Scienze MFN di Varese
Corso di Laurea in Informatica
Anno Accademico 2004/05
Lezione 8: meshes
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
Mesh triangolare (o mesh simpliciale)
• Una mesh è un insieme di triangoli adiacenti
faccevertici
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 - 3/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 two- manifoldNO 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 - 4/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 - 5/40
Caratteristiche topologiche di una mesh
• Orientabile, non orientabile– è possibile assegnare un orientamento ad
ogni faccia coerentemente?– orientabile = normali coerenti!
1
23
1
23
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 - 6/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 - 7/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 - 8/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 - 9/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 - 10/40
cubo.ply
Esempio: formato PLY
• Esempio: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 - 11/40
LetteraL.ply
Esempio: formato OFF
• Esempio:
1 5 10 5 14 3 2 1 04 5 4 3 04 6 7 8 94 6 9 10 114 0 1 7 64 1 2 8 74 2 3 9 84 3 4 10 94 4 5 11 104 5 0 6 11
OFF12 10 400 0 03 0 03 1 01 1 01 5 00 5 00 0 13 0 13 1 11 1 1
# vertici
# facce # edges
x,y,z2ndo vert
prima faccia:4 vertici:con indici3, 2, 1 e 0
indice 0
indice 3
indice 2indice 1
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 il bounding box– utile ad esempio
per translare e scalarel'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 - 13/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 normalenormalizzare normaleaggiungere 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 - 14/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 - 15/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 - 16/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
u
v
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
Task più difficili
automaticamente
mesh semplificata2K triangles
mesh originale500K triangoli
• Semplificazione automatica• parametri:
– un errore massimo– o un numero di facce obiettivo
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
p e r f o r m a n c e
q u a l i t y
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
Semplificazione automatica
LOD 1 LOD 2 LOD 3 LOD 4
Una piramide di Livelli di Dettaglio
usare quando visto da vicino
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 - 20/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 - 21/40
500milatriangoli
2milatriangoli
semplificazioneautomatica
sempre duemila triangoli, ma con texture mapping
rendering
TESSITURAfatta appostadetail
recover
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
simplified2K triangles
originale500K triangles
semplificato ma con tessitura2K triangles