Mesh poligonale

Una mesh poligonale, in computer grafica, è un reticolo che definisce un oggetto nello spazio, composto da vertici, spigoli e facce.^[1] Il termine mesh in inglese significa letteralmente "maglia", "rete".^[2][3]

Circa dagli anni duemila, le mesh poligonali sono usate sempre più intensivamente in molte differenti aree della computer grafica e della geometry processing (o elaborazione della geometria, che è un campo relativamente nuovo dell'informatica che concerne algoritmi e modelli matematici per l'analisi e la manipolazione di dati geometrici).^[4]

Intuitivamente, una mesh poligonale è la partizione di una superficie continua in celle poligonali, come triangoli, quadrilateri, ecc. Più formalmente, una mesh ${\displaystyle {\mathcal {M}}}$ può essere definita come una tupla ${\displaystyle ({\mathcal {V}},{\mathcal {K}})}$, dove ${\displaystyle {\mathcal {V}}=\{v_{i}\in \mathbb {R} ^{3}|i=1...{\mathit {N}}_{v}\}}$ è l'insieme dei vertici del modello (punti in ${\displaystyle \mathbb {R} ^{3}}$) e ${\displaystyle {\mathcal {K}}}$ contiene l'adjacency information o, in altre parole, come i vertici sono connessi per formare gli spigoli e le facce della mesh.^[5] Per esempio una mesh composta da un singolo triangolo sarebbe ${\displaystyle (\{v_{0},v_{1},v_{2}\},\{\{v_{0},v_{1}\}\{v_{1},v_{2}\}\{v_{2},v_{0}\}\{v_{0},v_{1},v_{2}\}\})}$, ossia i tre vertici, i tre spigoli e il triangolo.

Le mesh più usate in computer grafica sono le triangle meshes e le quadrilateral meshes (abbreviate in quad meshes).^[5] In questo articolo, per "mesh" si intende una triangle mesh. Altre mesh, nelle quali gli elementi di base sono quadrilateri o altri poligoni, sono a volte utilizzate, ma possono verificarsi inconvenienti. Per esempio, è facile creare un quadrilatero i cui vertici non giacciono tutti sullo stesso piano, mentre c'è sempre un piano passante per tre vertici.^[6] Inoltre, lavorare esclusivamente con triangle meshes semplifica la memorizzazione, e riduce il numero degli algoritmi.^[7]

Una mesh, 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.^[8]

I componenti visibili di una mesh sono:

• Vertice – Punto dello spazio, dotato quindi di coordinate ${\displaystyle x}$, ${\displaystyle y}$, ${\displaystyle z}$ che ne determinano la posizione. In inglese: vertex.
• Spigolo – Segmento che congiunge due vertici nello spazio. In inglese: edge.
• Faccia – Definita attraverso la connessione e chiusura di almeno tre spigoli.^[9] In inglese: face.

L'insieme di tutti i vicini (neighbors) di un vertice ${\displaystyle v_{i}}$è detto il 1-ring del vertice ed è definito come ${\displaystyle v_{1}(i)=\{j|\{i,j\}\in {\mathcal {K}}\}}$.^[5] La cardinalità di ${\displaystyle v_{1}(i)}$è detta grado (degree) o valenza (valence) del vertice ${\displaystyle v_{i}}$.^[5]

Una sequenza di triangoli adiacenti che condividono lo stesso vertice è detta fan di triangoli. Una strip è una sequenza di triangoli che può essere specificata elencando i propri vertici senza ambiguità. Per essere più specifici, dato un elenco ordinato di vertici ${\displaystyle \{v_{0},v_{1},...,v_{n}\}}$, il triangolo ${\displaystyle i}$è rappresentato dai vertici ${\displaystyle \{v_{0},v_{i+1},v_{i+2}\}}$. Strips e fans sono usati per compattare le rappresentazioni delle mesh. Una strip di triangoli con ${\displaystyle n}$ vertici rappresenta ${\displaystyle n-2}$ triangoli. Così, una strip di 100 triangoli richiede 102 vertici per essere memorizzata, piuttosto che 300. La quantità di vertici salvata incrementa con il numero di triangoli; il numeri medio di vertici ${\displaystyle {\bar {v_{t}}}}$necessari per rappresentare un triangolo in una strip con ${\displaystyle m}$ triangoli è ${\displaystyle {\bar {v_{t}}}=1+2/m}$.^[5] Nel caso di un fan, il triangolo ${\displaystyle i}$ è rappresentato dai vertici ${\displaystyle \{v_{0},v_{i+1},v_{i+2}\}}$ assumendo che ${\displaystyle v_{0}}$sia il vertice condiviso.^[5]

• 
  Una strip di triangoli
• 
  Un fan di triangoli

Lo stesso argomento in dettaglio: Varietà (geometria).

Una mesh 2D finita è una manifold mesh se gli spigoli e i triangoli che incontrano un vertice ${\displaystyle v}$ possono essere ordinati in un ordine ciclico ${\displaystyle t_{1},e_{1},t_{2},e_{2},...,t_{n},e_{n}}$senza ripetizioni, tali che lo spigolo ${\displaystyle e_{i}}$ sia uno spigolo dei triangoli ${\displaystyle t_{i}}$ e ${\displaystyle t_{i+1}}$.^[6] Questo implica che per ogni spigolo, ci sono esattamente due facce che lo contengono.^[6]

Una superficie è detta 2-manifold (two-dimensional-manifold) se l'intorno (neighborhood) di ogni punto ${\displaystyle \mathrm {p} }$sulla superficie è omeomorfico a un disco.^[5][10] Più semplicemente, significa che se abbiamo un disco possiamo centrarlo in ${\displaystyle \mathrm {p} }$ e farlo aderire alla superficie attorno a esso. La definizione di 2-manifold è estendibile alla superficie con frontiere, considerando di tagliare via metà del disco e farlo aderire alla frontiera.

Se la superficie è una mesh poligonale, possiamo determinare se è manifold controllando se le seguenti condizioni sono vere:^[5]

• Edge Manifold – Ogni spigolo è condiviso da una faccia (significa che è sulla frontiera della mesh) o due facce.
• Vertex Manifold – Se due facce ${\displaystyle f_{a}}$ e ${\displaystyle f_{b}}$ condividono un vertice, allora possiamo muoverci da ${\displaystyle f_{a}}$ a ${\displaystyle f_{b}}$ "traversando" solo gli spigoli nel 1-ring del vertice. In altre parole, possiamo camminare su tutto l'intorno del vertice senza passare per il vertice stesso.

Lo stesso argomento in dettaglio: Orientazione.

Ogni faccia è un poligono e perciò ha due lati (sides). Se guardiamo una faccia e seguiamo i suoi vertici nell'ordine in cui sono specificati in ${\displaystyle {\mathcal {K}}}$, essi possono descrivere un movimento orario (clockwise) o antiorario (anti-clockwise).^[5] Ovviamente, se guardiamo alle stesse facce dall'interno, queste orientazioni saranno scambiate.^[5]

La definizione dell'orientazione torna utile per la determinazione del vettore normale: se i vertici di un triangolo non-degenere (ossia uno con un'area non nulla) sono nei punti ${\displaystyle P_{i}}$, ${\displaystyle P_{j}}$, ${\displaystyle P_{k}}$, allora possiamo calcolare ${\displaystyle (P_{j}-P_{i})\times (P_{k}-P_{i})}$, che è il vettore perpendicolare al piano del triangolo.^[6] Da notare che se scambiamo i vertici ${\displaystyle P_{j}}$ e ${\displaystyle P_{k}}$, il vettore risultante è negativo.^[6] Poiché spesso si usano le normali di un triangolo in una mesh per determinare cosa è "dentro" o "fuori" la mesh, l'ordine dei vertici è critico.

Per scegliere una mesh data structure (struttura dati della mesh), occorre considerare fattori topologici^[11] e algoritmici:^[4]

• Requisiti topologici – Quali tipi di mesh è necessario rappresentare per mezzo della struttura dati? Possiamo fare affidamento su mesh 2-manifold, o abbiamo necessità di rappresentare spigoli complessi e vertici singolari? Possiamo limitarci a triangle meshes pure, o abbiamo necessità di rappresentare mesh poligonali arbitrarie? Le mesh sono regolari, semiregolari, irregolari?^[12] Vogliamo costruire una gerarchia di mesh via via più rifinite?
• Requisiti algoritmici – Quali tipi di algoritmi opereranno sulla struttura dati? Vogliamo semplicemente renderizzare la mesh, o necessitiamo di un accesso efficiente a intorni locali di vertici, spigoli e facce? La mesh sarà statica o la sua geometria e/o connettività cambierà nel tempo? Abbiamo necessità di associare dati con vertici, spigoli e facce della mesh? Abbiamo requisiti specifici in termini di consumo della memoria (ovvero, gli insiemi di dati sono massivi)?

La scelta di una struttura dati richiede la misurazione di vari criteri come...^[4]

1. Il tempo per costruirla durante la pre-elaborazione.
2. Il tempo di risposta a una specifica query.
3. Il tempo per eseguire una specifica operazione.
4. Il consumo e la ridondanza della memoria.

Finora, abbiamo dato per scontato che c'è una qualche rappresentazione delle mesh senza considerare nel dettaglio come effettivamente memorizzare i poligoni. Infatti, ci sono molte rappresentazioni, e la scelta di una o dell'altra influenza notevolmente le nostre possibilità di lavorazione della mesh.^[7]

La soluzione più semplice consiste nel memorizzare ogni poligono con la posizione geometrica di ognuno dei suoi vertici.^[7] Tuttavia, fare questo significherebbe non avere alcuna informazione sulla connettività – effettivamente, si otterrebbe solo una zuppa di poligoni che può essere renderizzata, ma con poche possibilità di manipolazione, poiché tutte le operazioni primitive assumono una qualche conoscenza di come i poligoni si relazionano gli uni agli altri.

Una più utile e semplice rappresentazione è l'indexed face set.^[7] Un indexed face set memorizza la mesh in due array. Il primo contiene tutti i vertici indicizzati da un numero (tipicamente solo in un array lineare). Per ogni vertice si memorizzano i suoi attributi, ovvero almeno la propria posizione nello spazio ma frequentemente anche altre informazioni come una normale al vertice (vertex normal), e possibilmente alcuni attributi di cui si necessita per scopi particolari come il rendering. Il secondo array è un elenco di facce che contiene almeno un elenco di indici, dove ogni indice fa riferimento all'array dei vertici.

Il principio della struttura dati edge-based, è quella di rappresentare la connettività memorizzando esplicitamente come gli spigoli si relazionano gli uni agli altri.^[7] Per ogni faccia della mesh, si memorizza semplicemente un puntatore a uno solo dei suoi spigoli. Analogamente, si memorizza per ogni vertice un solo puntatore a un singolo spigolo. Se vorremo il prossimo spigolo nell'edge loop^[13] che definisce una faccia, semplicemente seguiremo un puntatore dallo spigolo corrente. Di conseguenza, possiamo circolare per una faccia, visitando tutti i suoi spigoli anche se la faccia ha solo un puntatore a uno di questi. Poiché le rappresentazioni edge-based sono basate su spigoli che conoscono le loro facce incidenti, solo le manifolds sono di solito rappresentabili usando queste strutture dati.

Un winged edge è uno spigolo orientato che connette due vertici. Per ognuno dei suoi due face loops, esso presenta due puntatori verso i successivi spigoli, sia in senso orario che in quello antiorario. Sfortunatamente, la rappresentazione winged edge è un po' complicata, e presenta un altro difetto: lo spigolo in sé è bidirezionale, ma il winged edge è orientato. Se vogliamo muoverci da uno spigolo all'altro, il puntatore che dobbiamo usare dipende dall'orientamento dello spigolo. Vedi l'opera di Bruce G. Baumgart per maggiori dettagli.^[14]

La rappresentazione half edge presenta due rappresentazioni di uno spigolo dato.^[7] Gli half edges sono in coppie, e ogni elemento della coppia rappresenta lo spigolo dal punto di vista di uno dei due poligoni che condividono lo spigolo.^[7] Perciò, non vi è alcuna ambiguità. Ogni half edge presenta un puntatore successivo, che punta al prossimo spigolo nel loop che corrisponde alla sua faccia. Semplicemente seguendo i puntatori successivi, possiamo visitare tutti gli spigoli nell'edge loop di una faccia.

• 
  Winged edge data structure
• 
  Half edge data structure

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

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

• Autodesk
• Computer grafica 3D
• Poligono (computer grafica)
• Primitiva (geometria)

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