Computer Graphics - CNRvcg.isti.cnr.it/~tarini/teaching/cg09/Lez13.Meshes.pdf · • Tipicamente...
Transcript of Computer Graphics - CNRvcg.isti.cnr.it/~tarini/teaching/cg09/Lez13.Meshes.pdf · • Tipicamente...
1
Computer Graphics
Marco Tarini
Università dell’Insubria
Facoltà di Scienze MFN di Varese
Corso di Laurea in Informatica
Anno Accademico 2009/10
Lezione 13: Lezione 13: Lezione 13: Lezione 13: 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 0 9 / 1 0 ‧ 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
faccevertici
spigoli(o edges)
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 0 9 / 1 0 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Altre mesh
• Mesh bidimensionali– 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)– ...
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 0 9 / 1 0 ‧ 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)
NONONONO SISISISI
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 0 9 / 1 0 ‧ 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
• 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 0 9 / 1 0 ‧ 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
• Orientabile, non orientabile– è possibile assegnare un orientamento ad ogni
faccia coerentemente?– orientabile = normali coerenti!
1
23
1
23
senso opposto, edge coerente
A
BC
D
2
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 0 9 / 1 0 ‧ 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
• 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 0 9 / 1 0 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Come definisco una mesh?
• Una 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 0 9 / 1 0 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Come definisco una mesh?• Modo indexedindexedindexedindexed
– Lista ordinata di vertici• per ogni vertice, la posizione
– Lista ordinata 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 0 9 / 1 0 ‧ 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 0 9 / 1 0 ‧ 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
– MA, MB – Maya file format
– 3DX – Rinoceros file format
– BLEND – Blender file format
– DAE – Collada file format
– OBJ –Another file format for 3D objects
– X – Direct X object
– BYU - Movie BYU file format
– DEM - Digital Elevation Models
– DXF – (exchange format used by 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
– OBJ - Wavefront Object Files
– 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 - Virtual Reality Modeling Language
– VRML97 - ISO Specification di VRML
– X3D – successore di VRML
– PLY – Used by Cyberware
– DICOM – Dalla casa omonima
– 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 0 9 / 1 0 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
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
3
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 0 9 / 1 0 ‧ 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 0 9 / 1 0 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
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,z2ndo vert
prima faccia:4 vertici:con indici3, 2, 1 e 0
indice 0
indice 3indice 2indice 1
Mesh editing: applicativi
• 3D Studio Max (autodesk) , Maya (alias) , Cinema4D (maxon)– generici, potenti, completi
• Blender– idem, ma open-source (stile: Gimp VS. Adobe Photoshop per 2D images)
• AutoCAD (autodesk), SolidWorks (SolidThinking) – per CAD
• ZBrush (pixologic) , Mudbox (autodesk)– scultura virtuale, specializzato in ritocco manuale dettagli hi-freq, bumpmapping, normalmaps…
• Wings3D– open-source, specializzato in low-poly editing, subdivision surfaces
• Rhinoceros– parametric surfaces (NURBS)
• MeshLab– open-source, grande collezione algoritmi di ritocco, trasformazione, cleaning, seplificaz, …
• …• + 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 0 9 / 1 0 ‧ 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 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 0 9 / 1 0 ‧ 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 0 9 / 1 0 ‧ 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 scalarel'oggetto opportunamente
– come si fa?• (si itera sui vertici:
trovare il max e il mindi 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 0 9 / 1 0 ‧ 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
• 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
F
V E
Esempi:
struttura FV: puntatori da ogni facciaagli (n) vertici incidenti
struttura FF: puntatori da ogni facciaalle (tre) facce adiacenti
struttura EF: da ogni edge alle (due) faccieadiacenti
4
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 0 9 / 1 0 ‧ 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
Altre strutture di navigazione utili(oltre a F,V,E):
W: Wedge: (angolo di faccia)
H: Half-Wedge: ("mezzo" angolo di faccia)(molto potente)(operazioni...)
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 0 9 / 1 0 ‧ 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 vertice2 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 0 9 / 1 0 ‧ 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• 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... – un pò come come image processing
(infatti si parla di "geometry processing")
• Distinguere edges fra “lisci” e “creases”– angolo solido sotto o sopra una soglia
• …
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 0 9 / 1 0 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Task più difficili
• Misure di distanza– Date due mesh A e B, calcolare la loro "distanza"
• Es. la metrica HausdorffHausdorffHausdorffHausdorff di distanza fra mesh
– Calcolare la distanza:• in totale• punto per punto
})),(inf(sup,)),(inf(supmax{ badbadAaBb
BbAa ∈∈
∈∈
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 0 9 / 1 0 ‧ 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
• 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 0 9 / 1 0 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Task più difficili
• Stripification– suddividere i triangoli in triangle strips
• più lunghe possibile– (perché?)
5
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 0 9 / 1 0 ‧ 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• 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 0 9 / 1 0 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
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 ‧ C o m p u t e r G r a p h i c s ‧ 2 0 0 9 / 1 0 ‧ 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 0 9 / 1 0 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
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 0 9 / 1 0 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
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 0 9 / 1 0 ‧ 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
6
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 0 9 / 1 0 ‧ 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
semplificazioneautomatica
sempre 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 0 9 / 1 0 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
simplified2K triangles
originale500K triangles
semplificato ma con tessitura2K triangles