Mesh poligonale

Un esempio di 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]

Definizione

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]

Caratteristiche

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.

Fans e Strips

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

Varietà

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.

Orientazione

Un poligono e i suoi due vettori normali

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.

Strutture dati delle mesh

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.

Rappresentazioni delle mesh poligonali

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.

Indexed face set

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.

Edge-based data structure

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.

Winged edge data structure

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]

Half edge data structure

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

Formati di file per le mesh

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)

Note

1. (IT) Francesco Siddi, Grafica 3D con Blender, Apogeo, 25 giugno 2014, ISBN 9788850333141. URL consultato il 3 marzo 2018.
2. (IT) Giuseppe Ragazzini, Il Ragazzini 2017. Dizionario inglese-italiano, italiano-inglese. Con Contenuto digitale, Zanichelli, 1º giugno 2016, ISBN 9788808737373. URL consultato il 3 marzo 2018.
3. mesh - Dizionario inglese-italiano WordReference, su wordreference.com. URL consultato il 3 marzo 2018.
4. (EN) Mario Botsch, Leif Kobbelt e Mark Pauly, Polygon Mesh Processing, 1ª ed., A K Peters/CRC Press, 9 agosto 2010, ISBN 9781568814261. URL consultato il 3 marzo 2018.
5. (EN) Fabio Ganovelli, Massimiliano Corsini e Sumanta Pattanaik, Introduction to Computer Graphics: A Practical Learning Approach, 1ª ed., Chapman and Hall/CRC, 22 ottobre 2014, ISBN 9781439852798. URL consultato il 3 marzo 2018.
6. (EN) John F. Hughes, Andries Van Dam e Morgan Mcguire, Computer Graphics: Principles and Practice, 3ª ed., Addison-Wesley Professional, 28 febbraio 2009, ISBN 9780321399526. URL consultato il 4 marzo 2018.
7. (EN) Jakob Andreas Baerentzen, Jens Gravesen e Francois Anton, Guide to Computational Geometry Processing: Foundations, Algorithms, and Methods, Springer-Verlag New York Inc, 31 maggio 2012, ISBN 9781447140740. URL consultato il 4 marzo 2018.
8. (IT) Werner Stefano Villa, Autodesk AutoCad 2017. Guida completa per architettura, meccanica e design, Tecniche Nuove, 23 giugno 2016, ISBN 9788848131360. URL consultato il 3 marzo 2018.
9. Francesco Siddi, Grafica 3D con Blender.
10. (EN) Jakob Andreas Baerentzen, Jens Gravesen e Francois Anton, Guide to Computational Geometry Processing: Foundations, Algorithms, and Methods, Springer-Verlag New York Inc, 31 maggio 2012, ISBN 9781447140740. URL consultato il 4 marzo 2018.
    
    «A shape is a manifold if any sufficiently small patch is homeomorphic to a disk.»
11. Walter Maraschini e Mauro Palma, Enciclopedia della Matematica, M-Z, Edizione speciale per il Corriere della Sera, Garzanti, 2014.
    
    «La topologia consiste nello studio delle proprietà della figure e delle forme geometriche che rimangono invariate quando esse vengono sottoposte a deformazioni continue, che si verificano cioè senza "strappi", "sovrapposizioni", "incollamenti" e "duplicazioni". In termini meno intuitivi, è lo studio delle proprietà delle figure geometriche del piano e dello spazio che rimangono invarianti per trasformazioni biunivoche e bicontinue, dette omeomorfismi o trasformazioni topologiche, ossia trasformazioni che mantengono, anche inversamente, proprietà di "convergenza" e di "connessione"»
12. (EN) Mario Botsch, Leif Kobbelt e Mark Pauly, Polygon Mesh Processing, 1ª ed., A K Peters/CRC Press, 9 agosto 2010, ISBN 9781568814261. URL consultato il 4 marzo 2018.
    
    «A vertex in a triangle mesh is called regular if its valence (i.e., its number of neighboring vertices) is 6 for interior vertices or 4 for boundary vertices. In quadrangle meshes, the regular valences are 4 and 3, respectively. [...] The global structure of a mesh can be classified as being irregular, semiregular, highly regular, or regular. [...] In a regular mesh all vertices are regular. A regular mesh can compactly be represented as a 2D array that can be used for efficient rendering (a so-called geometry image).»
13. Edge Loop - CGWiki, su wiki.cgsociety.org, 24 marzo 2011. URL consultato il 4 marzo 2018 (archiviato dall'url originale il 24 marzo 2011).
14. Bruce G. Baumgart, Winged Edge Polyhedron Representation, PN, 1972. URL consultato il 4 marzo 2018.

Voci correlate

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

Controllo di autorità	GND (DE) 4175199-1