Computer Graphics

(1)

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”)

Mesh superficiali

• Di solito: discretizzazione lineare a tratti

di una superfice continua (un “2 manifold”) immersa in R ³

• 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)

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

(2)

Simplicial Meshes: complessità crescente

2.000.000.000 △

2002

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...

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

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...>

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

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)

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...

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

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)

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

Caratteristiche della connettività di una mesh

• Chiusa o aperta

– se chiusa, ogni edge condiviso da 2 faccie – se aperta, alcuni edge sono di bordo

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

(4)

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

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

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...)

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.

Argomento molto vasto

• Un buon manuale:

(5)

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)

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

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)

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 ∈ ∈ ∈ ∈

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

• ...

Mesh: altri task

• Stripification

– suddividere i triangoli in triangle strips

• più lunghe possibile

– (perché?)

(6)

Remeshing

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

Mesh: altri task

automaticamente

mesh semplificata 2K triangles mesh originale

500K triangoli

• Semplificazione automatica

• parametri:

– un errore massimo

– o un numero di facce obiettivo

Semplificazione automatica

p e r f o r m a n c e

q u a l i t y

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

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

– ...

(7)

Detail preservation

(o "texture for geometry")

• Idea:

– semplificare una mesh – sintetizzare una tessitura

– per ripristinare il dettaglio perso durante la semplificazione

500mila triangoli

2mila triangoli

semplificazione

automatica

sempre duemila triangoli, ma con texture mapping

Computer Graphics