Computer Graphics
Lezione 13:
Università dell’Insubria
Facoltà di Scienze MFN di Varese
Corso di Laurea in Informatica
Anno Accademico 2006/07
Marco Tarini
meshes
Mesh triangolare (o mesh simpliciale)
• Un insieme di triangoli adiacenti
facce
vertici
spigoli
(o edges)
Marco Tarini ‧ Computer Graphics
‧ 2006/07 ‧ Università dell’Insubria
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
– Mesh di poligoni
• Mesh volumetriche
– Mesh tetraedrali (o simpliciali 3D)
Marco Tarini ‧ Computer Graphics
‧ 2006/07 ‧ Università dell’Insubria
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 al max due faccie
• two manifold = bene
• non two manifold = male
• (molti algoritmi su mesh necessitano che sia two-manifold)
NO
Marco Tarini ‧ Computer Graphics
SI
‧ 2006/07 ‧ Università dell’Insubria
Caratteristiche topologiche di una mesh
• Chiusa o aperta
– se chiusa, ogni edge è condiviso proprio due faccie
– se aperta, alcuni edge sono di bordo
Marco Tarini ‧ Computer Graphics
‧ 2006/07 ‧ Università dell’Insubria
Caratteristiche topologiche di una mesh
• Orientabile, non orientabile
– è possibile assegnare un orientamento ad ogni
faccia coerentemente?
– orientabile = normali coerenti!
A
1
D
3
2
3
1
2
C
senso opposto, edge coerente
Marco Tarini ‧ Computer Graphics
B
‧ 2006/07 ‧ Università dell’Insubria
Caratteristiche topologiche di una mesh
• Orientabile, non orientabile
– esempi di mesh non orientabili:
• mesh non two-manifold
• e...
Nastro di Moebius
(non orientabile, aperta)
Marco Tarini ‧ Computer Graphics
Bottiglia di Klein
(non orientabile, chiusa)
‧ 2006/07 ‧ Università dell’Insubria
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
• Poco efficiente
– replicazione dati
– oneroso fare updates
Marco Tarini ‧ Computer Graphics
‧ 2006/07 ‧ Università dell’Insubria
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
– Se serve: lista ordinata di edges
• per ogni edge, 2 indici ai vertici
Marco Tarini ‧ Computer Graphics
‧ 2006/07 ‧ Università dell’Insubria
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...
Marco Tarini ‧ Computer Graphics
‧ 2006/07 ‧ Università dell’Insubria
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
Marco Tarini ‧ Computer Graphics
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
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...
‧ 2006/07 ‧ Università dell’Insubria
Esempio di file format : formato PLY
• E' un formato digitale per mesh superficiali
• 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
Marco Tarini ‧ Computer Graphics
‧ 2006/07 ‧ Università dell’Insubria
Esempio di file format : 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
Marco Tarini ‧ Computer Graphics
‧ 2006/07 ‧ Università dell’Insubria
Esempio di file format : 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
Marco Tarini ‧ Computer Graphics
LetteraL.off
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
‧ 2006/07 ‧ Università dell’Insubria
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)
Marco Tarini ‧ Computer Graphics ‧
2006/07 ‧ Università dell’Insubria
Mesh: strutture per la navigazione
• Navigazione ("traversal") di mesh
• Strutture dati apposite
– puntatori (o indici) da ogni elemento ad ogni elemento adiacente o incidente
– efficienza in tempo contro efficienza in spazio
Esempi:
struttura FV: puntatori da ogni faccia
ai vertici incidenti
F
V
struttura FF: puntatori da ogni faccia
alle facce adiacenti
struttura EF: da ogni edge alle due faccie
adiacenti
E
Marco Tarini ‧ Computer Graphics
‧ 2006/07 ‧ Università dell’Insubria
Mesh: strutture 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):
W: Wedge: (angolo di faccia)
F
V
H: Half-Wedge: ("mezzo" angolo di faccia)
(molto potente)
(operazioni...)
E
Marco Tarini ‧ Computer Graphics
‧ 2006/07 ‧ Università dell’Insubria
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?)
Marco Tarini ‧ Computer Graphics
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
‧ 2006/07 ‧ Università dell’Insubria
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")
• ...
Marco Tarini ‧ Computer Graphics
‧ 2006/07 ‧ Università dell’Insubria
Task più difficili
• Misure di distanza
– Date due mesh A e B, calcolare la loro "distanza"
• Es. la metrica Hausdorff di distanza fra mesh
max{ sup ( inf d (a, b) ) , sup ( inf d (a, b) ) }
aA
bB
bB
aA
– Calcolare la distanza:
• in totale
• punto per punto
Marco Tarini ‧ Computer Graphics
‧ 2006/07 ‧ Università dell’Insubria
Mesh: task più difficili
• Stripification
• Parametrizzazione
• Semplificazione automatica
– e precalcolo di livelli di dettaglio
• Detail recovery
• ...
Marco Tarini ‧ Computer Graphics
‧ 2006/07 ‧ Università dell’Insubria
Task più difficili
• Stripification
– suddividere i triangoli in triangle strips
• più lunghe possibile
– (perché?)
Marco Tarini ‧ Computer Graphics
‧ 2006/07 ‧ Università dell’Insubria
Task più difficili
• Parametrizzazione
– assegnare una coppia di coordinate texutre
ad ogni wedge
– ci sono seams
• replicare i vertici
• memorizzale le text coord per wedge
v
u
Marco Tarini ‧ Computer Graphics
‧ 2006/07 ‧ Università dell’Insubria
Task più difficili
• Semplificazione automatica
• parametri:
– un errore massimo
– o un numero di facce obiettivo
automaticamente
mesh originale
triangoli
M a r c o T a 500K
rini ‧ C
omputer Graphics
mesh semplificata
‧ 2 0 0 6 / 0 7 ‧ U n i v e 2K
r s i ttriangles
à dell’Insubria
Semplificazione automatica
performance
quality
Marco Tarini ‧ Computer Graphics
‧ 2006/07 ‧ Università dell’Insubria
Semplificazione automatica
Una piramide di Livelli di Dettaglio
LOD 1
LOD 2
usare quando
visto da vicino
Marco Tarini ‧ Computer Graphics
LOD 3
LOD 4
usare quando
visto da lontano
‧ 2006/07 ‧ Università dell’Insubria
Semplificazione automatica
• Molte tecniche diverse
– Errore massimo introdotto:
• misurato e/o limitato
• oppure no
– Topologia:
• mantenuta
• oppure no
– Streaming
• Possibile
• Oppure no
– ...
Marco Tarini ‧ Computer Graphics
‧ 2006/07 ‧ Università dell’Insubria
Semplificazione automatica
• Strategie completamente diverse
– Approcci iterativi
• repeat
– compi l'azione di semplificazione
atomica meno costosa
(in termini di errore aggiunto)
– aggiorna costi
• until (obiettivo raggiunto)
remove
vertex
edge
collapse
– es: numero faccie,
errore
remove
face
Marco Tarini ‧ Computer Graphics
‧ 2006/07 ‧ Università dell’Insubria
Semplificazione automatica
• Strategie completamente diverse
– Vertex clustering:
• dividi i vertici originali in una griglia regolare
• collassa in un solo vertice tutti i vertici nella stessa casella
• togli i triangoli che hanno solo 1 o 2 vertici diversi
– Approssimazione dipende da dimensione griglia
Marco Tarini ‧ Computer Graphics
‧ 2006/07 ‧ Università dell’Insubria
Semplificazione automatica
• Strategie completamente diverse
– Fitting di piani
• sostituire molte facce con poligoni planari quando i loro
vertici sono quasi coplanari
Cohen-Steiner,
Alliez,
Desbrun
(SIGGR04)
Marco Tarini ‧ Computer Graphics
‧ 2006/07 ‧ Università dell’Insubria
Detail preservation
(o texture for geometry)
• Idea:
– semplificare una mesh
– sintetizzare una tessitura
– per ripristinare il dettaglio perso durante la
semplificazione
Marco Tarini ‧ Computer Graphics
‧ 2006/07 ‧ Università dell’Insubria
500mila
triangoli
detail
recover
TESSITURA
fatta apposta
(es. BumpMap)
semplificazione
automatica
2mila
triangoli
rendering
sempre duemila triangoli, ma con texture mapping
Marco Tarini ‧ Computer Graphics
‧ 2006/07 ‧ Università dell’Insubria
originale
500K triangles
Marco Tarini ‧ Computer Graphics
semplificato
simplified
ma con tessitura
2K triangles
‧ 2006/07 ‧ Università dell’Insubria