Computer Graphics
Marco Tarini
Università dell’Insubria
Facoltà di Scienze MFN di Varese Corso di Laurea in Informatica Anno Accademico 2012/13
Lezione 10: meshes
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
Tipi di mesh
• Mesh per superfici
– Mesh di triangoli (o tri-mesh, o simpliciali) – Mesh di quadrilateri (o quad-mesh) – Mesh miste (quad e tri)
• Spesso, mesh prevalemtemente di quads (quad-dominant ) – Mesh di poligoni
• Mesh volumetriche
– Mesh tetraedrali (o simpliciali 3D) – Mesh exaedrali (“di cubi”)
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
Mesh superficiali
• Di solito: discretizzazione lineare a tratti
di una superfice continua (un “2 manifold”) immersa in R 3
• Componenti:
1. geometria
• i vertici, ciascuno con pos (x,y,z)
• un campionamento della superficie!
2. connettività
• come sono connessi i vertici
• (es.: in una tri-mesh, i triangoli) 3. attributi
• opzionale
• (es: colore, materiali, normali, UV, temperatura)
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
Mesh triangolare (o mesh simpliciale)
• Un insieme di triangoli adiacenti
facce
vertici
spigoli (o edges)
Simplicial Meshes: complessità crescente
70.000 △
1994
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
Simplicial Meshes: complessità crescente
1.200.000 △
1997
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
Simplicial Meshes: complessità crescente
2.000.000.000 △
2002
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
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
Formati files per mesh
(una Torre di Babele!)
• 3DS -3D Studio Max file format
• OBJ –Another file format for 3D objects
• MA, MB –Maya file format
• 3DX –Rinoceros file format
• BLEND –Blender file format
• DAE –COLLADA file format
• X –Direct X object
• BYU -Movie BYU file format
• DEM -Digital Elevation Models
• DXF –(exchange format, Autodesk's AutoCAD)
• FIG -Used by REND386/AVRIL
• FLT -MulitGen Inc.'s OpenFlight format
• HDF -Hierarchical Data Format
• IGES -Initial Graphics Exchange Specification
• IV -Open Inventor File Format Info
• LWO, LWB & LWS- Lightwave 3D file formats
• MAZ -Used by Division's dVS/dVISE
• MGF -Materials and Geometry Format
• MSDL -Manchester Scene Description Language
• 3DML –by Flatland inc.
• C4D –Cinema 4D file format
• SLDPTR –SolidWork "part"
• WINGS –Wings3D object
• NFF -Used by Sense8's WorldToolKit
• SKP –Google sketch up
• KMZ –Google Earth model
• OFF -A general 3D mesh Object File Format
• OOGL -Object Oriented Graphics Library
• PLG -Used by REND386/AVRIL
• POV –“persistence of vision” ray-tracer
• QD3D -Apple's QuickDraw 3D Metafile format
• TDDD -for Imagine & Turbo Silver ray-tracers
• NFF & ENFF -(Extended) Neutral File Format
• VIZ -Used by Division's dVS/dVISE
• VRML, VRML97 -Virtual Reality Modeling Language
• X3D –tentato successore di VRML
• PLY –introdotto by Cyberware – tipic. dati range scan
• DICOM–Dalla casa omonima – tipic. dati CAT scan
• Renderman–per l'omonimo visualizzatore
• RWX–RenderWare Object
• Z3D –ZModeler File format
– etc, etc, etc...
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
Come definisco una triangle mesh?
• Una tri-mesh è un insieme di triangoli adiacenti
• Strutture dati?
• Modo diretto:
– un vettore di triangoli – e per ogni triangolo tre vertici – e per ogni vertice tre coordinate
• Ma: replicazione dati – poco efficiente in spazio – oneroso fare updates
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
cubo.ply
Esempio di file format : 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
<dati...>
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
LetteraL.off
Esempio di file format : formato OFF
• Esempio:
1 5 1 0 5 1 4 3 2 1 0 4 5 4 3 0 4 6 7 8 9 4 6 9 10 11 4 0 1 7 6 4 1 2 8 7 4 2 3 9 8 4 3 4 10 9 4 4 5 11 10 4 5 0 6 11 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
# vertici
# facce # edges
x,y,z 2ndo vert
prima faccia:
4 vertici:
con indici 3, 2, 1 e 0 indice 0
indice 3 indice 2 indice 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
Esempio di file format : formato PLY
• E' un formato digitale per mesh superficiali
• Può essere in binario, o in ASCII (testo) – binario: più compatto e veloce da leggere – ascii: direttamente 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 ‧ 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
E gli attributi?
• Tipicamente definiti:
– per vertice
• un attributo nella struttura di ogni vertice – per faccia
• un attributo nella struttura di ogni faccia – per wedge (vertice di faccia)
• tre attributi nella struttura di ogni faccia (caso più generico!) – per edge (raro)
• Attributi più comuni:
– colore
– coordinate texture – normali...
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
Caratteristiche della connettività di una mesh
• Orientabile, non orientabile
– è possibile assegnare un orientamento ad ogni faccia coerentemente?
– orientabile = normali coerenti!
1
3 2 1
3 2
senso opposto, edge coerente A
B C
D
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
Caratteristiche della connettività di una mesh
• Orientabile, non orientabile – esempi di mesh non orientabili:
• mesh non two-manifold
• e...
Nastro di Moebius
(non orientabile, aperta)
Bottiglia di Klein
(non orientabile, chiusa)
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
Mesh: strutture dati
• Sturtture dati indexed (mesh indicizzata) – Inseme di vertici
• per ogni vertice, la posizione – Iniseme di facce
• per ogni faccia, 3 indici di vertici – Se serve: lista ordinata di edges
• per ogni edge, 2 indici ai 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 2 / 1 3 ‧ U n i v e r s i t à d e l l ’ I n s u b r i
Caratteristiche della connettività di una mesh
• Chiusa o aperta
– se chiusa, ogni edge condiviso da 2 faccie – se aperta, alcuni edge sono di bordo
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
Mesh: strutture dati per la navigazione
• Navigazione ("traversal") di mesh
• Apposite strutture dati di adiacenza :
– puntatori (o indici) da ogni elemento ad ogni elemento adiacente o incidente
– + efficienza in tempo, - efficienza in spazio
F
V E
Esempi:
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
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
Mesh: strutture dati per la navigazione
• Esempio:
struttura VF:
– per ogni vertice, la lista delle facci incidenti – (lunghezza variabile! Poco efficiente! Come si fa?)
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 2 / 1 3 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Caratteristiche topologiche di una mesh
• Two Manifold ("varietà due") oppure no – in generale : two-manifold = localmente è una superficie – per le mesh:
two-manifold = ogni edge condiviso da max 2 faccie
• two manifold = bene
• non two manifold = male
• (molti algoritmi su mesh necessitano che sia two-manifold)
NO SI
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
Mesh: strutture dati
• Strutture basate su half-edges
V3 V4
V1
V5
V2
Mesh editing: applicativi generici
• 3D Studio Max (autodesk) , Maya
(alias) , Cinema4D (maxon)
– generici, potenti, completi• Blender
– idem, ma open-source e freeware (simile a: Gimp VS. Adobe Photoshop per 2D images)
• MeshLab
– open-source, grande collezione algoritmi di geometry processing …
• AutoCAD
(autodesk), SolidWorks (SolidThinking)
– per CAD• ZBrush
(pixologic) , Mudbox (autodesk)
– scultura virtuale, specializzato in ritocco manuale dettagli hi-freq, bumpmapping, normalmaps…
• Wings3D
– open-source, piccolo, specializzato in low-poly editing, subdivision surfaces
• Rhinoceros
– parametric surfaces (NURBS)
• FragMotion
– specializzato per mesh animate
• …
• + moltissimi strumenti per contesti specifici
– (editing di umani, di interni architetturali, di paesaggi, o editor specifici per game-engines, etc...)
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
Mesh editing: librerie
• VCG-Lib (CNR, it)
– Vision and Computer Graphic Lib
• OpenMesh (RWTH, de)
• CGAL (~INRIA, fr)
– Computational Geometry Algorithms Library
– tutte e tre: C++, open-suorce.
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
Argomento molto vasto
• Un buon manuale:
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
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
Mesh: task comuni
• Data una mesh:
– magari appena caricata
• trovare il AABB
(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)
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
Mesh: task comuni
• Data una mesh:
– magari appena caricata
• trovare le normali per faccia
• trovare le normali per vertice – 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
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
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 – 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”)
• …
Tutti esempi di task di MODELLING (fatti in preprocessing) (vedi 1ma lezione)
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
Mesh: task più difficili (esempi)
• Misure di distanza
– Date due mesh A e B, calcolare la loro "distanza"
• Es. la metrica Hausdorff di distanza fra mesh
– Calcolare la distanza:
• in totale
• punto per punto
} ) ) , ( inf ( sup , ) ) , ( inf ( sup
max{ d a b d a b
A B a 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 2 / 1 3 ‧ U n i v e r s i t à d e l l ’ I n s u b r i
Mesh: altri task
• Stripification
• Parametrizzazione – detta anche "u-v mapping"
• Semplificazione automatica – detta anche "poly-reduction"
– e precalcolo di livelli di dettaglio
• Detail recovery
• Rigging – per animazioni
• Morphing
– trovare "vie di mezzo" fra due meshes
• ...
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
Mesh: altri task
• Stripification
– suddividere i triangoli in triangle strips
• più lunghe possibile
– (perché?)
Remeshing
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
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
Mesh: altri task
• Parametrizzazione
– assegnare una coppia di coordinate texture ad ogni wedge
– 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 ‧ 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
Mesh: altri task
automaticamente
mesh semplificata 2K triangles mesh originale
500K triangoli
• 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 2 / 1 3 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
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 ‧ 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
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 ‧ 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
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 – Topologia:
• mantenuta
• oppure no – Streaming
• Possibile
• 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 2 / 1 3 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Detail preservation
(o "texture for geometry")
• Idea:
– semplificare una mesh – sintetizzare una tessitura
– per ripristinare il dettaglio perso durante la semplificazione
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
500mila triangoli
2mila triangoli
semplificazione
automaticasempre duemila triangoli, ma con texture mapping
rendering
TESSITURA fatta apposta (es. BumpMap) detail
recover
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
simplificato 2K triangles originale
500K triangles
semplificato ma con tessitura 2K triangles
Mesh: task tipici nella game industry
• Semplificazione automatica – LOD construction
• Light baking
– Precomputazione Luce
– Tipico esempio: ambient Occlusion
• U-V mapping
– parametrizzazione (v. tessiture, dopo)
• Texturing
– creazione tessiture
• Rigging / Animation – linear blend skinning
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