Informatica Grafica a.a. 2012-2013 DICGIM – University of Palermo Dipartimento di Ingegneria...

Informatica Grafica a.a. 2012-2013

DICGIM – University of Palermo

Dipartimento di Ingegneria Chimica, Gestionale, Informatica e Meccanica

Modelli a poligoni

Roberto Pirrone

11 ottobre 2012



Sommario

Struttura di una mesh di poligoniStruttura dati

Formati di file che specificano mesh di poligoni

Generazione di mesh poligonali da modelli e datiLaser

Modelli analitici

Modelli sweep

Generazione procedurale di mesh

Superfici parametriche

Volumi di dati

Level Of Detail (LOD)

11 ottobre 2012



Mesh di poligoni

Le mesh di poligoni costituiscono una rappresentazione delle superfici di un modello per mezzo di una tassellazione di poligoni piani che approssimano la superficie stessa “pezzo a pezzo”.

Poligoni quadrangolari o meglio triangolari (è assicurata la planarità)

I vertici dei poligoni sono punti effettivi della superficie del modello

Ottima rappresentazione per la macchina, ma poco orientata all’utente.

Tutti gli algoritmi ed i dispositivi hw di rendering assumono di trattare con insiemi di poligoni proiettati ortograficamente sullo schermo.

11 ottobre 2012



Struttura di una mesh di poligoni

Da un punto di vista concettuale un oggetto viene decomposto nelle sue superfici che, campionate, sono approssimate a poligoni.

I poligoni si intendono costituiti da lati che raccordano coppie di vertici.

11 ottobre 2012



Struttura di una mesh di poligoni11 ottobre 2012



Struttura dati una mesh

In genere si usano liste circolari gerarchiche per consentire l’accesso diretto ai singoli vertici o lati.

11 ottobre 2012



Struttura dati una mesh

Ad ogni vertice/poligono sono associate informazioni utili al processo di modellazione e rendering

Coordinate geometriche

Componenti del vettore normale (ovvero della normale al piano del poligono insieme con i coefficienti dell’equazione del piano)

Coordinate del vertice nello spazio delle texture (texture coordinates)

Componenti cromatiche rispetto ai vari tipi di riflessione della luce (autoemissiva, ambiente, diffusa o speculare) descrizione del materiale

11 ottobre 2012



Formati di file per mesh di poligoni

Esistono diversi formati di file che consentono di gestire oggetti grafici in forma di mesh di poligoni secondo le informazioni già viste.

Formati proprietari• 3DS – 3D Studio Max• DXF – AutoCAD• IV – Open Inventor

Formati aperti• OBJ – Wavefront Technologies • PLY – Stanford University

11 ottobre 2012



File Wavefront OBJ11 ottobre 2012



File Wavefront OBJ11 ottobre 2012

Definizione facce:f v1 v2 v3 v4 ...f v1/vt1 v2/vt2 v3/vt3 ...f v1/vt1/vn1 v2/vt2/vn2 v3/vt3/vn3 ...f v1//vn1 v2//vn2 v3//vn3 ...

Riferimento a materialimtllib [external .mtl file name] ...

Shadings 1 (ovvero s off per disabilitare)



File Wavefront OBJ

Riferimento a oggetti e/o gruppi di poligoni

Tipologie di illuminamento

11 ottobre 2012



File Wavefront OBJ

Descrizione di materiali (eventualmente con texture maps)

11 ottobre 2012



File Stanford PLY

Il formato PLY è stato definito da Greg Turk

La struttura base prevedeHeader

Vertex list

Face list

Altri elementi (ad es. materiali)

Il formato usa i tipi del C per definire i dati

Il file può essere ascii o binario little endian o big endian

11 ottobre 2012



File Stanford PLY

Headerplyformat ascii 1.0comment ply is the magic numbercomment format can be also binary_little_endian comment or binary_big_endian in place of asciielementpropertyproperty…elementproperty…end_header

11 ottobre 2012



File Stanford PLY11 ottobre 2012



File Stanford PLY11 ottobre 2012

Definizione di un materiale

Per aggiungere il materiale ad ogni vertice aggiungere la seguente linea alla fine della definizione dell’elemento vertex:

property material_index int



Generazione di mesh poligonali da dati laser

L’approccio più comune è l’algoritmo di skinning

I dati acquisiti giacciono su piani paralleli di scansione

Si crea una striscia di triangoli connettendo a zig-zag i punti contigui che giacciono su due piani adiacenti

11 ottobre 2012



Triangolazione di Delaunay

E’ l’insieme di triangoli che si ottiene circuitando un insieme di punti che definiscono una tassellazione di Voronoi che chiameremo punti seme

In una regione di Voronoi è costituita da tutti i punti del piano che sono i “più vicini” al punto di seme della regione stessa rispetto a qualunque altro punto di seme

11 ottobre 2012




I confini della regione sono gli assi dei segmenti che congiungono i semi

Tali segmenti sono i lati dei triangoli cercatiLa triangolazione di Delaunay rappresenta il grafo duale della tassellazione di Voronoi

11 ottobre 2012




Una triangolazione di Delaunay DT(P) di un insieme di punti P∈Rn si è tale per cui non ci sono punti in P che siano interni all’ipersfera circoscritta a qualunque simplesso in DT(P)

In due dimensioni circonferenze e triangoli

In tre dimensioni sfere e tetraedri

11 ottobre 2012



Flip algorithm

Criterio per la verifica che una triangolazione sia una DTLa somma degli angoli opposti ad un lato comune di due triangoli adiacenti deve essere <180°

Nel caso non sia così si esegue il flip del lato comune

Si elimina il lato comune e si sostituisce con quello che unisce gli altri due vertici; si può provare che si ottiene una DT

11 ottobre 2012



Algoritmi per la Triangolazione di Delaunay di nuvole di punti mediante chiusure convesse

Algoritmo IncrementaleRipeti per ogni punto della nuvola

Aggiungi il punto alla chiusura convessa esistente

Se il punto è interno all’attuale chiusura convessa • non far nulla

Altrimenti• Cancella tutti i triangoli che il punto “può vedere” • Crea la piramide ottenuta connettendo il nuovo punto ai punti

rimasti dei triangoli cancellati nella vecchia chiusura convessa

Per stabilire se un punto è interno o esterno a un triangolo ovvero se è visibile da questo si usa il calcolo della normale positiva al triangolo circuitandone i vertici in senso antiorario.

11 ottobre 2012



Algoritmi per la Triangolazione di Delaunay di nuvole di punti mediante chiusure convesse

Algoritmo divide-and-conquerCalcola ricorsivamente la chiusura convessa delle due metà della nuvola

Esegui la circuitazione delle due chiusure convesse per trovare la tangente comune inferiore o superiore (segmento che connette due vertici nelle chiusure convesse e totalmente esterno ad esse)

Trova il terzo vertice adiacente ad uno dei due estremi della tangente e chiudi un triangolo

Ripeti secondo uno schema di skinning per chiudere tutto il cilindro esterno che raccorda le due chiusure convesse ottenendo la chiusura convessa finale

11 ottobre 2012



Generazione di mesh poligonali da funzioni analitiche

Scansione latitudine-longitudineSi generano quadrangoli che poi vengono trasformati in triangoli suddividendoli attraverso le diagonali

Problemi• non corrispondenza di archi di curva uguali a passi

angolari uguali in lat-long• In caso di forme soggette a deformazioni globali

(flessione, assottigliamento, torsione) la tassellazione lat-long diventa onerosa e può dar luogo a una cattiva poligonizzazione nei punti ad elevata curvatura

11 ottobre 2012




11 ottobre 2012




11 ottobre 2012

Parametrizzazione uniforme: l’insieme dei punti campionati si ottiene proiettando i punti di campionamento di una sfera, i quali sono uniformemente distribuiti sia in termini angolari sia in termini di spaziatura lungo la superficie, attraverso un opportuno fattore di scala variabile punto a punto e che deve essere stimato in ogni punto.



Generazione di mesh poligonali da modelli sweep

E’ possibile ricondurre lo sweep ad una operazione di estrusione di una sezione che viene deformata ad ogni passo secondo la legge imposta dal profilo desiderato

Ad ogni passo di estrusione viene generata un’approssimazione lineare del profilo da cui si ricavano i poligoni

11 ottobre 2012



Generazione di mesh poligonali da modelli sweep

Una generalizzazione del metodo precedente è quella di far scorrere una sezione trasversale appoggiandola ad una coppia di “curve binario” che, con la loro distanza variabile, ne definiscono ad ogni passo la dimensione di scala.

Affine transformation surfaceAd ogni passo lungo z (direzione di estrusione) la sezione trasversale definita sul piano (x,y) subisce una trasformazione affine che la deforma.

Non c’è una curva direttrice, ma i parametri di trasformazione possono essere controllati da curve parametriche.

La natura affine della trasformazione consente sempre l’approssimazione del profilo superficiale mediante poligoni piani.

11 ottobre 2012



Generazione di mesh poligonali da modelli sweep11 ottobre 2012

Problemi di approssimazione planare se si generalizzaad una qualunque curva direttrice

Problemi di orientamento localedella sezione trasversale

Problemi di auto-intersezione della sezione trasversale



Generazione procedurale di mesh poligonali11 ottobre 2012

Fractal terrain: generazione di modelli di rilievi del suolo usando la geometria frattale cioè l’autosimilarità di una forma con sé stessa a diverse scale di osservazione.

Il modello a poligoni originale viene decomposto iterativamente per bisezione dei lati.

Ad ogni nuovo punto generato si aggiunge una perturbazione statistica della quota originale lungo la normale al lato.



Generazione di mesh poligonali da superfici parametriche

11 ottobre 2012

Suddivisione ricorsiva delle patch in porzioni più piccole fino a soddisfare un criterio di “planarità” per il quale l’approssimazionepoligonale della patch risulta accettabile.




11 ottobre 2012

Suddivisione uniforme o non uniforme per inseguire curvature locali




11 ottobre 2012

La suddivisione non uniforme può creare artefatti dovuti allo “spezzarsi”della mesh in corrispondenza di poligoni con risoluzione diversa.Gli eventuali “buchi” andranno circuitati per generare nuovi poligoni.




11 ottobre 2012

La suddivisione delle patch si riconduce ad una approssimazione delle curve a u e v costante mediante poligonali aperte.




11 ottobre 2012

R3=Q(0.5): la struttura dei nuovi punti di controllo si ottiene applicandoL’algoritmo di De Casteljau




11 ottobre 2012

Criterio di planarità: minimizzare d1 e d2



Estrazione di iso-superfici (marching cubes)

Lorenson e Cline (1987)

Questo tipo di approccio è utilizzato soprattutto per visualizzazione o per costruire delle realtà virtuali di campi operatori e non per diagnostica.

Si tratta di determinare come una iso-superficie f(i,j,k)=c, rappresentata mediante poligoni, attraversa il singolo voxel.

11 ottobre 2012



Marching cubes (2)

Ogni cubo è costruito connettendo otto pixel di due slice contigue.

Per cui si conosce il valore di f(i,j,k) ad ogni vertice del cubo.



Marching cubes (3)Ci sono 256 (28) possibilità di attraversamento

8 vertici che possono essere dentro (1) o fuori (0) dalla superficie

Mediante considerazioni di simmetria, le possibilità di attraversamento si riducono a 14 più il caso nullo con tutti i vertici esterni.

Ad ogni vertice di ogni voxel è assegnato un valore in termini dell’informazione rappresentata dal volume: la iso-superficie rappresenta tutti i punti caratterizzati da un unico valore.

L’algoritmo “marcia” da un voxel (cubo) all’altro e:Individua la modalità di attraversamento (vertici del voxel interni ed esterni alla superficie)Calcola l’effettiva posizione dei poligoni nel voxel per mezzo di una interpolazione lineare sugli edge intersecati.

11 ottobre 2012



Marching cubes (4)

Indice ad 8 bit che identificala tipologia di attraversamento e punta alla tabella degli edge numerati come in figura

11 ottobre 2012



Marching cubes (5)

Calcolo delle normali ai vertici dei triangoliLe normali alla superficie sono esprimibili in termini del gradiente Gf perché per f(i,j,k)=c si ha che Gf=0

Allora si calcolano i gradienti con le differenze finite ad ogni vertice del cubo e poi si interpolano lineaemente lungo gli edge per trovarne il valore all’intersezione con f(i,j,k)=c.

11 ottobre 2012



Marching cubes (6)

Traccia dell’algoritmo

1. Carica 4 slice in memoria2. Calcola un cubo da due slice adiacenti3. Compara i valori di f(i,j,k) ad ogni vertice con f (i,j,k)=c

(luogo geometrico della iso-superficie) e calcola un indice ad 8 bit che individua la modalità di attraversamento

4. Usa l’indice per entrare in una tabella degli edge al fine di determinare gli edge effettivamente intersecati

5. Interpola linearmente il valore di f lungo gli edge intersecati per trovare le effettive intersezioni cioè i vertici dei triangoli di output

6. Determina le normali ai vertici a partire dai valori di quelle nei vertici del cubo che vengono interpolate linearmente lungo gli edge

7. Dai come output i triangoli generati dall’attraversamento del cubo con le loro normali ai vertici.

11 ottobre 2012



Esempi di elaborazioni di iso-superfici11 ottobre 2012



LOD – progressive mesh refinement11 ottobre 2012




Criteri di collassamentoSoglia

Minimizzazione di funzionale energia

Informatica Grafica a.a. 2012-2013 DICGIM – University of Palermo Dipartimento di Ingegneria...

Documents

Transcript of Informatica Grafica a.a. 2012-2013 DICGIM – University of Palermo Dipartimento di Ingegneria...