Simplicial Meshes: complessità crescente
70.000
1994 1994 1994 1994
Simplicial Meshes: complessità crescente
1.200.000
1997 1997 1997 1997
Simplicial Meshes: complessità crescente
2.000.000.000
2002 2002 2002 2002
Mesh: task comuni
• Data una mesh:
– magari appena caricata
• trovare il AABB
(axis aligned bounding box)
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 0 / 1 1 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
(axis aligned 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)
Mesh: strutture dati per la navigazione
• Navigazione ("traversal") di mesh
• Apposite strutture dati di adiacenca :
– puntatori (o indici) da ogni elemento ad ogni elemento adiacente o incidente – + efficienza in tempo, - efficienza in spazio
Esempi:
struttura FV: puntatori da ogni faccia
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 0 / 1 1 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
F
V E
struttura FV: puntatori da ogni faccia agli (n) vertici incidenti struttura FF: puntatori da ogni faccia
alle (tre) facce adiacenti struttura EF: da ogni edge alle (due) faccie
adiacenti
Mesh: strutture dati per la navigazione
• Esempio:
struttura VF:
– per ogni vertice, la lista delle facci incidenti – (lunghezza variabile! Poco efficiente! Come si fa?)
Altre strutture di navigazione utili (oltre a F,V,E):
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 0 / 1 1 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
F
V E
W: Wedge: (angolo di faccia)
H: Half-Wedge: ("mezzo" angolo di faccia) (molto potente)
(operazioni...)
Mesh: task comuni
• Data una mesh:
– magari appena caricata
• trovare le normali per faccia
• trovare le normali per vertice – come si fa?
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 0 / 1 1 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
– come si fa?
– che struttura serve?
• (FV? VF?)
BASTA LA FV!
1 azzerare tutte le norm x vertice 2 iterare su ogni faccia:
- trovare normale x faccia (normalizzata)
- aggiungerla a normale dei tre vertici incidenti (FV) 3 iterare su ogni vertice:
normalizzare normale x vertice
Mesh: task più difficili (esempi)
• Bounding sphere
• Calcolo di caratteristiche
– Geometriche (curvatura per vertice, curve geodesiche...) – Topologiche (chiusura, genus, edge di bordo...)
• Detection e chiusura buchi
• Date due mesh, calcolare la "distanza"
– in totale
Tutti esempi di task di MODELLING (fatti in
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 0 / 1 1 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
– in totale – punto per punto
• Rimozione rumore (geometrico, topologico) – o enhancing del segnale ad alta frequenza...
– simile al problema dell’image processing
(infatti si parla di "geometry processing")
• Distinguere edges fra “lisci” e “creases”
– angolo solido sotto o sopra una soglia (“crease angle”)
• …
(fatti in preprocessing) (vedi 1ma lezione)
Mesh: task più difficili (esempi)
• Misure di distanza
– Date due mesh A e B, calcolare la loro "distanza"
• Es. la metrica Hausdorff Hausdorff Hausdorff Hausdorff di distanza fra mesh } ) ) , ( inf ( sup , ) ) , ( inf ( sup
max{ d a b d a b
A a B B b
A b
a ∈ ∈ ∈ ∈
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 0 / 1 1 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
– Calcolare la distanza:
• in totale
• punto per punto
Mesh: task più difficili (altri esempi)
• Stripification
• Parametrizzazione – detta anche "u-v mapping"
• Semplificazione automatica – detta anche "poly-reduction"
– e precalcolo di livelli di dettaglio
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 0 / 1 1 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
– e precalcolo di livelli di dettaglio
• Detail recovery
• Rigging
– per animazioni
• Morphing
– trovare "vie di mezzo" fra due meshes
• ...
Task più difficili
• Stripification
– suddividere i triangoli in triangle strips
• più lunghe possibile – (perché?)
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 0 / 1 1 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Task più difficili
• Parametrizzazione
– assegnare una coppia di coordinate texture ad ogni wedge
– ci sono seams
• replicare i vertici
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 0 / 1 1 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
• replicare i vertici
• memorizzale le text coord per wedge
u v
Task più difficili
• Semplificazione automatica
• parametri:
– un errore massimo
– o un numero di facce obiettivo
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 0 / 1 1 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a automaticamente
mesh semplificata
2K triangles
mesh originale 500K triangoli
Semplificazione automatica
p e r f o r m a n c e
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 0 / 1 1 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
q u a l i t y
Semplificazione automatica
Una piramide di Livelli di Dettaglio
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 0 / 1 1 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
LOD 1 LOD 2 LOD 3 LOD 4
usare quando visto da vicino
usare quando visto da lontano
Semplificazione automatica
• Molte tecniche diverse – Adattive oppure no
• usare piu' triangoli dove c'e' bisogno (es non nelle zone cmq piatte)
• oppure no
– Errore massimo introdotto:
• misurato e/o limitato
• oppure no
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 0 / 1 1 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
