Mesh poligonale

Da Wikipedia, l'enciclopedia libera.
Un esempio di mesh poligonale

Una mesh poligonale (letteralmente: maglia, rete), è una collezione di vertici, spigoli e facce che definiscono la forma di un oggetto poliedrico nella computer grafica 3D e nella modellazione solida. Lo studio delle mesh poligonali è un grande sotto-campo della computer grafica. Le rappresentazioni con mesh poligonali sono utilizzate per diverse applicazioni e con diverse finalità.

Elementi di una mesh[modifica | modifica wikitesto]

Elementi che compongono una mesh poligonale

Una mesh è un reticolo che definisce un oggetto nello spazio. Questo reticolo è composto fondamentalmente da tre elementi: vertici, spigoli, e facce. Differentemente da un oggetto solido reale, non presenta una massa; è quindi una sorta di volume vuoto, privo di spessore, le cui facce sono appunto dei "veli" superficiali.[1]

I vertici ("vertice" in inglese è "vertex") sono dei punti dello spazio (dotati quindi di coordinate x, y, z che ne determinano la posizione) e costituiscono la base per definire gli spigoli (edges), ovvero i segmenti che congiungono due vertici nello spazio. A loro volta, gli spigoli definiscono, attraverso la propria connessione e chiusura, le facce. Per definire una faccia sono sufficienti tre spigoli tra loro connessi.[2] Una mesh triangolare consiste in molti triangoli uniti lungo i propri spigoli, per formare una superficie. Altre mesh, nelle quali gli elementi di base sono quadrilateri, o altri poligoni, sono a volte utilizzate, ma possono verificarsi problemi legati a esse. Per esempio, è facile creare un quadrilatero i cui vertici non giacciono tutti sullo stesso piano, mentre c'è sempre un piano contenente tre vertici.[3]

Altri elementi che compongono una mesh, ma che sono opzionali, sono:

  • Un poligono è un insieme complanare di facce. In sistemi che supportano facce con un maggiore numero di spigoli, i poligoni e le facce sono equivalenti. Comunque, molti componenti hardware da rendering supportano solo facce triangolari o quadrangolari, quindi i poligoni sono rappresentati come più facce. Matematicamente una mesh poligonale può essere considerata una griglia non strutturata, o grafo non orientato, con proprietà addizionali su geometria, forma e topologia.
  • Le superfici, più spesso chiamate smoothing groups, sono utili, ma non richieste per raggruppare regioni smussate. Consideriamo un cilindro; per smussarne l'ombreggiatura, tutte le normali delle superfici devono puntare orizzontalmente via dal centro, mentre le normali dei cerchi devono puntare dritte per sopra e sotto. Renderizzata come una sola superficie con il Phong shading, i vertici delle pieghe avrebbero normali scorrette. Perciò, è necessario un qualche modo per determinare dove far cessare la smussatura, per raggruppare parti smussate di una mesh, semplicemente come gruppi di poligoni raggruppano facce triangolari. Come alternativa al fornire superfici/smoothing groups, una mesh può contenere altri dati, come un angolo diviso (poligoni con normali al di sopra di questa soglia sono ciascuno trattati automaticamente come smoothing groups separati o qualche tecnica come lo splitting o la bisellatura è automaticamente applicata allo spigolo presente fra di essi). In più, mesh a risoluzioni molto alte sono meno soggette a inconvenienti che richiederebbero smoothing groups, in quanto i loro poligoni sono così piccoli che rendono il bisogno irrilevante. Ulteriormente, esiste un'altra alternativa che consiste nel semplice distacco delle superfici stesse dal resto della mesh. I motori di rendering non tentano di smussare spigoli lungo poligoni non contigui.

Nella realtà, i materiali sono considerati diretto attributo di un oggetto; pertanto, molti oggetti sono associati a un preciso materiale. Se pensiamo a un bicchiere, lo immaginiamo di vetro, se pensiamo a un cucchiaio, sarà di acciaio, plastica o legno. Se pensiamo alla carrozzeria di un'automobile ci verrà in mente un metallo ricoperto da un'elegante vernice, lucida come uno specchio. Nella computer grafica, il processo di definizione di una forma o di un oggetto è completamente separato dall'attribuzione di un materiale allo stesso.[2] In Blender, ad esempio, un materiale è uno strumento che determina le proprietà fondamentalmente ottiche della mesh a cui viene applicato. In altre parole, se voglio rendere una mesh trasparente, devo prima selezionare la mesh e in seguito andare nella finestra dedicata ai materiali e da lì impostare la trasparenza. Un materiale, come detto, è qualcosa che viene applicato, "assegnato", anche a specifiche facce; in questo modo, è possibile gestire più materiali in un'unica mesh.

Molti formati di mesh supportano anche alcune forme di coordinate UV (vedi mappatura UV), che consistono in una separata rappresentazione bidimensionale della mesh "dispiegata" (in inglese unfolded) per mostrare la porzione di texture map (vedi texture mapping) da applicare a differenti poligoni della mesh.

È anche possibile che le mesh contengano altre informazioni come attributi ai vertici come colore, vettori tangenti, weight maps per controllare l'animazione, ecc.. (alcune volte chiamati anche channels).

Struttura dati di una mesh[modifica | modifica wikitesto]

Una struttura dati di una mesh è una rappresentazione che organizza i dati dei vertici, degli spigoli e delle facce. Ci sono diverse strutture dati ed esse possono essere complicate da implementare.[4]

Alcuni esempi sono:

  • Face-vertex mesh: una semplice lista di vertici e un insieme di facce che puntano ai vertici che formano il poligono.
  • Winged-edge mesh, in cui ogni spigolo punta a due vertici, due facce, e ai quattro (in senso orario e antiorario) spigoli che toccano le facce. Questo tipo di maglie permettono un tempo costante di attraversamento della mesh, ma richiedono una quantità maggiore di dati da memorizzare.
  • Half-edge mesh: Simile al precedente, ma possiede solo informazioni riguardo agli half edge.
  • Quad-edge mesh: vengono memorizzati solo gli spigoli, gli half edge e i vertici senza considerare i poligoni. I poligoni sono impliciti nella rappresentazione, e si possono ottenere attraversando la struttura. I requisiti di memoria sono simili alle half edge mesh.
  • Corner-tables: memorizzano i vertici in una tabella predefinita, in modo che attraversando la tavola si possano ottenere i poligoni rappresentati implicitamente. La rappresentazione è più compatta e più efficiente per recuperare poligoni, ma le operazioni di modifica sono lente. Inoltre, questo tipo di mesh non rappresenta la mesh completamente.
  • Vertex-vertex mesh: una mesh "VV" rappresenta solo i vertici, che puntano ad altri vertici. Sia lo spigolo e le informazioni sulla faccia sono implicite nella rappresentazione. Tuttavia, la semplicità della rappresentazione consente di svolgere con maggiore efficienza diverse elaborazioni.

La scelta della struttura dati viene fatta in base all'applicazione che utilizza tali dati, le prestazioni richieste, la dimensione dei dati, e le operazioni da eseguire. Ad esempio è più facile utilizzare triangoli piuttosto che altri poligoni, soprattutto in geometria computazionale. Per certe operazioni è necessario avere un accesso rapido alle informazioni e questo richiede strutture più complesse come le winged-edge mesh. Per il rendering hardware sono necessarie strutture semplici e di conseguenza le corner-tables sono comunemente incorporate in API di basso livello per il rendering come DirectX e OpenGL.

Vertex-vertex mesh[modifica | modifica wikitesto]

Descrizione del metodo di memorizzazione VV per le mesh poligonali.

Una vertex-vertex mesh rappresenta un oggetto come un insieme di vertici connessi ad altri vertici. Questa è la rappresentazione più semplice, ma non ampiamente usata, dato che le informazione delle facce e degli spigoli sono implicite. Perciò, è necessario navigare nei dati in modo da generare un elenco di facce per il rendering. Inoltre, le operazioni su spigoli e facce non sono facilmente realizzabili.

Tuttavia, le mesh VV beneficiano di piccoli spazi di memoria e di un efficiente morphing della forma. La figura mostra una scatola di quattro lati rappresentata da una mesh VV. Ogni vertice è collegato ai vertici vicini. Si noti che gli ultimi due vertici, v8 e v9 (al centro superiore e inferiore della scatola), possiedono quattro vertici collegati piuttosto che cinque. Un sistema generale deve essere in grado di gestire un numero arbitrario di vertici collegati a un dato vertice.

Per una descrizione completa delle mesh VV vedere l'opera di Smith.[5]

Face-vertex mesh[modifica | modifica wikitesto]

Mesh fv.jpg

Una face-vertex mesh rappresenta un oggetto come un insieme di facce e un insieme di vertici. Questa è la rappresentazione di mesh più ampiamente utilizzata, trattandosi dell'input tipicamente accettato dal moderno hardware grafico.

Le face-vertex mesh migliorano le mesh VV in quanto consentono una ricerca esplicita dei vertici di una faccia e delle facce che circondano un vertice. La figura mostra l'esempio della scatola come una mesh FV. Il vertice v5 è evidenziato per mostrano le facce che lo circondano. Si noti che in questo esempio, ogni faccia deve necessariamente avere esattamente tre vertici. Tuttavia, questo non significa che ogni vertice ha lo stesso numero di facce circostanti.

Per il rendering, l'elenco delle facce viene di solito trasmesso alla GPU come un insieme di indici ai vertici, e i vertici sono inviati come strutture di posizione/colore/normale (nella figura è indicata solo la posizione). Ciò da il vantaggio che le modiche fatte alla forma, ma non geometria, possono essere dinamicamente aggiornate semplicemente rispedendo i dati del vertice senza aggiornare la connessione della faccia.

La modellazione richiede una facile traversata di tutte le strutture. Con le mesh FV è facile trovare i vertici di una faccia. Inoltre, l'elenco dei vertici contiene un elenco delle facce connesse a ogni vertice. A differenza delle mesh VV, sia le facce che i vertici sono espliciti, quindi la localizzazione di facce e vertici è a tempo costante. Tuttavia, gli spigoli sono impliciti, quindi è necessaria una ricerca per trovare tutte le facce che circondano una data faccia. Altre operazioni dinamiche, come la divisione (splitting) o la fusione (merging) di una faccia, sono anch'esse difficili con una face-vertex mesh.

Winged-edge mesh[modifica | modifica wikitesto]

Mesh we2.jpg

Una winged-edge mesh, introdotta da Bruce Baumgart nel 1975, rappresenta esplicitamente i vertici, le facce e gli spigoli di una mesh. Questo tipo di rappresentazione è ampiamente utilizzato in programmi di modellazione per fornire la maggiore flessibilità nella lavorazione della geometria della mesh, perché le operazioni di splitting e merging possono essere eseguite rapidamente. I loro principali punti a sfavore sono i requisiti di archiviazione (di grandi dimensioni) e una maggiore complessità dovuta al mantenimento di molti indici. Una buona discussione sulle problematiche di implementazione delle winged-edge mesh, può essere trovata nel libro Graphics Gems II.

Le winged-edge mesh affrontano la questione dell'attraversamento di spigolo in spigolo, e forniscono un insieme ordinato di facce intorno a uno spigolo. Per ogni dato spigolo, il numero di spigoli in uscita può essere arbitrario. Per semplificare ciò, le winged-edge mesh ne forniscono solo quattro: gli spigoli più vicini in senso orario, e quelli in senso antiorario, ad ogni estremità. Gli altri spigoli possono essere attraversati in modo incrementale. Le informazioni per ogni spigolo, perciò, assomigliano a una farfalla, da qui il nome "winged-edge mesh" (mesh di spigoli ad ala). La figura mostra la "scatola" come una winged-edge mesh. I dati complessivi di uno spigolo consistono in 2 vertici, 2 facce e 4 spigoli.

Renderizzare graficamente una winged-edge mesh richiede la generazione di un elenco di indici delle facce. Questo è di solito fatto solo quando cambia la geometria. Le winged-edge mesh sono ideali per la geometria dinamica, come le superfici di suddivisione e la modellazione interattiva, poiché le modifiche alla mesh possono verificarsi localmente. La traversata lungo la mesh, forse necessaria per la rilevazione di collisioni, può essere realizzata in modo efficiente.

Vedi l'opera di Baumgart per maggiori dettagli.[6]

Render dynamic mesh[modifica | modifica wikitesto]

La winged-edge mesh non è l'unica rappresentazione che permette modifiche dinamiche alla geometria. Un nuova rappresentazione che unisce le proprietà della winged-edge mesh e della face-vertex mesh si chiama render dynamic mesh, che memorizza esplicitamente entrambe: i vertici di una faccia e le facce prossime a un vertice (come le mesh FV), e le facce e i vertici prossimi a uno spigolo (come una winged-edge).

Una render dynamic mesh richiede minore spazio di memorizzazione rispetto a una mesh winged-edge standard e può essere renderizzata direttamente dall'hardware grafico, in quanto l'elenco delle facce contiene un elenco dei vertici. Inoltre, la traversata da vertice a faccia è esplicita (a tempo costante), come lo è da faccia a vertice. Le mesh RD non richiedono i quattro spigoli in uscita, poiché questi possono essere trovati facendo la traversata da spigolo a faccia, quindi da faccia a spigolo prossimo.

Le mesh RD beneficiano delle caratteristiche delle winged-edge mesh, permettendo alla geometria di essere dinamicamente aggiornata di volta in volta.

Vedi l'opera di Tobler & Maierhofer per maggiori dettagli.[7]

Half-edge mesh[modifica | modifica wikitesto]

Dcel-halfedge-connectivity.svg

Una half-edge mesh (o conosciuta anche come doubly connected edge list; DCEL), è una struttura dati che rappresenta un incorporamento di un grafo planare in un piano, e politopi nello spazio 3D. Questa struttura dati fornisce una efficiente manipolazione delle informazioni sulla topologia associate agli oggetti in questione (vertici, spigoli, facce). È utilizzata in molti algoritmi di geometria computazionale per gestire le suddivisioni poligonali del piano, comunemente chiamati planar straight-line graphs. Per esempio, un diagramma di Voronoi è comunemente rappresentato da una DCEL dentro una bounding box.

Questa struttura dati fu originariamente proposta da Muller e Preparata[8] per rappresentazioni di politopi convessi.

Una DCEL è molto più di un elenco di spigoli doppiamente connessi. Nel caso generale, una DCEL contiene una voce per ogni spigolo, vertice e faccia della suddivisione. Ogni voce può contenere informazioni addizionali, per esempio, una faccia può contenere il nome dell'area. Ogni spigolo di solito racchiude due facce ed è perciò conveniente considerare ogni spigolo come due mezzi-spigoli. Ogni mezzo-spigolo (half-edge) racchiude una singola faccia e così possiede una indicazione verso quella faccia. Un mezzo-spigolo possiede una indicazione verso il prossimo mezzo-spigolo e il precedente della stessa faccia. Per raggiungere l'altra faccia, possiamo muoverci verso il gemello del mezzo-spigolo e quindi traversare verso l'altra faccia. Ogni mezzo-spigolo ha anche una indicazione al proprio vertice di origine (il vertice di destinazione può essere ottenuto interrogando quello di origine o il suo gemello, o il successivo mezzo-spigolo).

Ogni vertice contiene le proprie coordinate e in più memorizza una indicazione verso uno spigolo arbitrario che ha il vertice come propria origine. Ogni faccia memorizza una indicazione verso alcuni mezzi-spigoli, o i propri più esterni (se la faccia non è racchiusa allora l'indicazione è nulla). Possiede anche un elenco di mezzi-spigoli, uno per ogni spigolo che può essere incidente entro la faccia. Se i vertici o le facce non contengono alcuna informazione interessante, non c'è necessita di memorizzarli, così da salvare spazio e ridurre la complessità della struttura dati.

Formati di file per le mesh[modifica | modifica wikitesto]

Alcuni formati di file che memorizzano informazioni sulle mesh sono i seguenti:

  • .blend (Blender file)
  • .FBX
  • .3DS (Autodesk 3ds Max file)
  • .DAE (COLLADA - COLLAborative Design Activity)
  • .DXF (AutoCAD DXF - Drawing Interchange Format, or Drawing Exchange Format)
  • .OBJ (Wavefront .obj file)
  • .PLY
  • .STL
  • .VMRL
  • .X3D
  • .C4D
  • .OFF

Note[modifica | modifica wikitesto]

  1. ^ Werner Stefano Villa, Autodesk AutoCAD 2017 - Guida completa per architettura, meccanica e design.
  2. ^ a b Francesco Siddi, Grafica 3D con Blender.
  3. ^ John F. Hughes , Andries van Dam, Morgan McGuire, David F. Sklar, James D. Foley, Steven K. Feiner, Kurt Akeley, Computer Graphics: Principles and Practice.
  4. ^ Steven J. Gortler, Foundations of 3D Computer Graphics.
  5. ^ Colin Smith, On Vertex-Vertex Meshes and Their Use in Geometric and Biological Modeling (PDF), algorithmicbotany.org.
  6. ^ Bruce Baumgart, Winged-Edge Polyhedron Representation for Computer Vision.
  7. ^ Tobler & Maierhofer, A Mesh Data Structure for Rendering and Subdivision (PDF), wscg.zcu.cz.
  8. ^ Muller, D. E.; Preparata, Finding the Intersection of Two Convex Polyhedra.

Voci correlate[modifica | modifica wikitesto]

Informatica Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica