Computer Graphics

Marco Tarini

Università dell’Insubria

Facoltà di Scienze MFN di Varese

Corso di Laurea in Informatica

Anno Accademico 2006/07

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 6 / 0 7 ‧ 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 6 / 0 7 ‧ 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

– 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 6 / 0 7 ‧ 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 al max due 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 0 6 / 0 7 ‧ 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 proprio due

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 6 / 0 7 ‧ 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

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 6 / 0 7 ‧ 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 6 / 0 7 ‧ 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

• Poco efficiente– replicazione dati– 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 6 / 0 7 ‧ 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 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

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 6 / 0 7 ‧ 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 6 / 0 7 ‧ 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 6 / 0 7 ‧ 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

• 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

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 6 / 0 7 ‧ 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

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 6 / 0 7 ‧ 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 10 5 14 3 2 1 04 5 4 3 04 6 7 8 94 6 9 10 114 0 1 7 64 1 2 8 74 2 3 9 84 3 4 10 94 4 5 11 104 5 0 6 11

OFF12 10 400 0 03 0 03 1 01 1 01 5 00 5 00 0 13 0 13 1 11 1 1

# vertici

# facce # edges

x,y,z2ndo vert

prima faccia:4 vertici:con indici3, 2, 1 e 0

indice 0

indice 3

indice 2indice 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 0 6 / 0 7 ‧ 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 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 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a

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

F

V E

Esempi:

struttura FV: puntatori da ogni faccia ai vertici incidenti

struttura FF: puntatori da ogni facciaalle 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 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a

Mesh: strutture 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 6 / 0 7 ‧ 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 6 / 0 7 ‧ 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")

• ...

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 6 / 0 7 ‧ 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 Hausdorff di distanza fra mesh

– Calcolare la distanza:• in totale• punto per punto

})),(inf(sup,)),(inf(supmax{ badbadAaBbBbAa

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 6 / 0 7 ‧ 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• Semplificazione automatica

– e precalcolo di livelli di dettaglio

• Detail recovery• ...

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 6 / 0 7 ‧ 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é?)

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 6 / 0 7 ‧ 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 texutre

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 6 / 0 7 ‧ 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 6 / 0 7 ‧ 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 6 / 0 7 ‧ 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 6 / 0 7 ‧ 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– 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 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a

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)– es: numero faccie,

errore

remove vertex

remove face

edge collaps

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 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a

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

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 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a

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)

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 6 / 0 7 ‧ 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 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a

500milatriangoli

2milatriangoli

semplificazioneautomatica

sempre duemila triangoli, ma con texture mapping

rendering

TESSITURAfatta apposta

(es. BumpMap)detailrecover

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 6 / 0 7 ‧ 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