Map Generator


Generatore casuale di mappe low poly

Descrizione


Il progetto Map Generator consiste in un generatore casuale di un paesaggio naturale, caratterizzato dalla presenza di laghi, colline e montagne. Tale paesaggio viene generato dinamicamente ed, esplorandolo, si continua a generare nuovi frammenti di mappa, consentendo l'esplorazione di una mappa sconfinata. Al momento, il progetto permette di eseguire un'esplorazione della mappa in ogni possibile direzione. All'avvio dell'eseguibile, il personaggio, parte da un punto randomico della mappa e il programma segna quel punto mediante una bandiera rossa visibile nell'ambiente. In qualsiasi momento, quando si ha voglia di tornare al punto di partenza, è possibile visualizzare una bussola che indicherà, mediante una freccia al suo interno, la via per poter tornare alla bandiera.

Ogni frammento di mappa che viene generato è incollato ai pezzi esistenti in modo tale da rendere il paesaggio coerente e completamente connesso, consentendo anche di poter viaggiare a ritroso sulla strada percorsa e di attraversare lo stesso identico paesaggio. Tale progetto nasce come base per poter realizzare progetti più complessi che necessitino della generazione casuale di una mappa, come un videogioco o un simulatore d'esplorazione.

Manuale Utente


Per poter utilizzare il generatore di mappe, è necessario scaricare il progetto, decomprimerlo e avviare l'eseguibile al suo interno. Una volta avviato, è possibile iniziare l'esplorazione utilizzando i seguenti comandi:

  • MOUSE per muovere la visuale

  • WASD per il movimento dell'esploratore

  • M per mostrare e nascondere la bussola

  • SPAZIO per saltare


Il progetto non richiede alcuna connessione ad internet. Basta decidere le impostazioni grafiche (risoluzione e qualità video) e verrà automaticamente avviata l'esecuzione della simulazione di esplorazione.

Teoria


Curve di Bèzier

Le curve di Bézier sono il più importante tipo di curve polinomiali. Vengono definite da un poligono di controllo in un intervallo [0, 1]. Il grado della curva è dato dal (numero di vertici -1) del poligono di controllo.

Dati due punti P0 e P1, una curva di Bézier lineare è il segmento avente come estremi i punti dati. Tale curva è data da:

Generalizzando, una curva di Bèzier può essere generalizzata nel seguente modo.

Per poter valutare una curva di Bèzier, si utilizza l'Algoritmo di de Casteljau, che si tratta di un metodo ricorsivo numericamente stabile (e per questo motivo molto utilizzato).

L'algoritmo di de Casteljau si basa su una poligonale <P0, ... Pk>, dalla quale si forma una nuova poligonale di primo livello, formata da (k-1) punti. A partire da questa, si forma una nuova poligonale di secondo livello con (k-2) punti e così via, fino alla definizione dell'ultimo punto (che è il punto della curva corrispondente al valore t). L'intera curva è ottenuta iterando l'algoritmo per ogni t in [0,1].

La formula di una curva intermedia è:


Incollamento curve di Bezier

Due curve di Bézier, definite per u0 ≤ u ≤ u1 e u1 ≤ u ≤ u2 dai poligoni di controllo P0, ...,Pn e Pn,...,P2n, che supponiamo essere r volte derivabili un u = u1, diciamo che abbiano una condizione di incollamento C(r) se vale:

Data tale definizione di incollamento, noi ci interessiamo agli incollamenti di tipo C(0), C(1), C(2).

Si ha un incollamento di tipo C(0) quando il punto iniziale e il punto finale dei due poligoni di controllo coincide, perché non è richiesto che i poligoni di controllo siano derivabili (o, meglio, siano derivabili 0 volte) nel punto di incollamento.

Si ha un incollamento di tipo C(1) quando si ha un incollamento di tipo C(0) e i poligoni di controllo sono derivabili una volta nel punto di incollamento. Per controllare tale tipo di incollamento, è necessario che il rapporto semplice tra tra i nodi u0, u1 e u2 sia uguale a quello dei punti Pn-1, Pn e Pn+1.

Si ha un incollamento di tipo C(2) quando sono verificate tutte le condizione per un incollamento C(1) ed, entrando in gioco anche le derivate seconde, è necessario aggiungere condizioni sui punti Pn-1 e Pn+1. Deve valere:

dove D è il punto di intersezione tra le rette passanti per Pn-2,Pn-1 e Pn+1,Pn+2.

All'aumentare del grado del tipo di incollamento, si ottengono incollamenti sempre migliori, che consentono continuità nella curva ad un numero sempre maggiore di derivate. Questo fatto, però, comporta un costo computazionale sempre maggiore all'aumentare del grado di incollamento delle curve.

Per questo motivo, in questo progetto, si utilizzano solo incollamenti di curve di Bézier di tipo C(1), che offrono un ottimo risultato visivo senza un'esagerata richiesta di calcolo computazionale.


Rumore di Perlin

Il rumore di Perlin è un tipo di rumore di gradiente, cioè una primitiva utilizzata per la generazione di texture procedurali, usato dagli artisti di effetti visivi per aumentare l'aspetto del realismo nella grafica computerizzata.

Questo metodo consiste in una creazione di un reticolo di gradienti casuali (o tipicamente pseudorandom), i cui prodotti a punti vengono poi interpolati per ottenere valori tra i reticoli. La funzione ha un aspetto pseudo-casuale, ma tutti i dettagli visivi hanno la stessa dimensione, consentendo alla funzione di essere facilmente controllabile.


Molteplici copie scalate del rumore di Perlin possono essere inserite in espressioni matematiche per creare una grande varietà di texture procedurali. Le texture sintetiche che utilizzano questo metodo sono spesso utilizzate in CGI (Computer Graphics Interface) per rendere più naturali gli elementi visivi generati dal computer - come le superfici di oggetti, il fuoco, il fumo o le nuvole - imitando l'aspetto casuale controllato delle texture in natura.

È anche spesso utilizzato per generare texture quando la memoria è estremamente limitata, come ad esempio in demo di videogame o in grosse mappe procedurali o come nel nostro caso più generalmente, per tutte le applicazioni che richiedono grosse elaborazioni nella grafica in tempo reale.

Il rumore è, dal punto di vista fisico, la somma di oscillazioni irregolari, intermittenti o statisticamente casuali. Le oscillazioni possono essere pseudo-controllate in modo tale da utilizzare i valori dell'onda per generare variazioni nell'altezza del terreno.


Nel nostro caso è necessario avere un controllo diretto su tutte le componenti che costituiscono il rumore:

L' ampiezza permette di controllare la componente Y del rumore, mentre la frequenza permette il controllo della X. Questi ci permettono di controllare l'altezza e la quantità di dislivelli presenti nella nostra mappa modificandone i valori associati.


Le ottave sono livelli multipli di rumore sommati assieme per ottenere un rumore complessivo (in rosso nell'immagine sottostante), preservando la forma complessiva del nostro paesaggio. In questo modo, andando a manipolare ogni sotto livello in maniera sempre più dettagliata, siamo in grado di ottenere una risultante che rispecchi quella di un paesaggio, formato da rilievi con pendenza uniforme in pianura e da pendenze scoscese in prossimità delle montagne.


La lacunarity permette di dare un livello di dettaglio maggiore all'aumentare del numero delle ottave. Questa influisce in maniera diretta sulla frequenza del rumore, per cui, per ogni livello di rumore utilizzato, abbiamo che:



La persistenza permette di dare un'influenza minore al livello di dettaglio all'aumentare del numero di ottave. Questa influisce in maniera diretta sull'ampiezza del rumore, per cui, per ogni livello di rumore utilizzato, abbiamo che:



Modellando le ottave mediante la lacunarity e la persistenza siamo in grado di ottenere un profilo più realistico della nostra mappa. Per definirne l'altezza, utilizziamo un valore fisso come moltiplicatore per ogni valore definito all'interno della matrice risultante dall'algoritmo del rumore di Perlin. Vengono applicate delle texture, inoltre, per simulare il colore del terreno, ogni colore viene associato ad un range di valori della matrice, permettendo di avere colori realistici all'interno del nostro paesaggio.


Mesh e normalizzazione

Per mostrare tridimensionalmente la mappa su schermo e per sfruttare la matrice derivante dal rumore di Perlin, ci siamo avvalsi delle mesh poligonali.

Mesh poligonali

Una mesh poligonale è un insieme di vertici, spigoli e facce che definiscono la forma di un oggetto tridimensionale e lo definiscono nello spazio. È una della basi costituenti della computer grafica 3D.

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. I vertici 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, 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. 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 ad esse. Per esempio, è facile creare un quadrilatero i cui vertici non giacciono tutti sullo stesso piano, ma ci sarà sempre un piano contenente tre vertici del quadrilatero.


Nella realtà, i materiali sono considerati un 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. Nel nostro caso, la mappa deve possedere un qualche tipo di texture che, applicata ad ogni triangolo, permetta di colorare una certa sezione di una mesh, rispecchiando le caratteristiche cromatiche che il nostro occhio associa ad un paesaggio. Nella computer grafica, il processo di definizione di una forma o di un oggetto è completamente separato dall'attribuzione di un materiale allo stesso a cui viene applicato.

Per questo, molti formati di mesh, supportano anche alcune forme di UV mapping, che consistono in una separata rappresentazione bidimensionale della mesh utilizzata per mostrare la porzione di texture map da applicare ai differenti poligoni che la compongono. Con questa tecnica, la mesh viene "appiattita" su un piano, sul quale giace un'immagine (la nostra texture 2D). A questo punto ogni vertice dell'oggetto tridimensionale disporrà di un set di coordinate bidimensionali condiviso con l'immagine, che potrà essere quindi associata alle sue facce, risultando visibile nello spazio 3D. Le coordinate UV fanno quindi da ponte tra lo spazio bidimensionale delle texture e quello tridimensionale della mesh.


Un grande vantaggio dell'UV mapping è la precisione: è possibile posizionare con estrema esattezza degli elementi su una mesh, anche se poi si deformerà. Un altro vantaggio è la velocità di calcolo: con una texture 2D è possibile aumentare notevolmente il livello di dettaglio di un oggetto, mantenendo il rendering entro tempi accettabili.

La luce che illumina il paesaggio viene simulata mediante componenti grafiche: dovendo generare l'ambiente dinamicamente, queste non andranno a riflettere perfettamente la luce, generando una ombreggiatura uniforme. Essendo che ogni triangolo gestirà la riflessione in maniera autonoma, si è quindi ricorsi alla normalizzazione della mesh per ovviare al problema.

Normalizzazione delle mesh

I triangoli sono sufficienti per definire la forma di base dell'oggetto, come già detto, ma sono necessarie ulteriori informazioni per mostrare la mesh nella maggior parte dei casi. Per consentire all'oggetto di essere ombreggiato correttamente mediante un'illuminazione, è necessario fornire un vettore normale per ciascun vertice. Un normale è un vettore che punta verso l'esterno, perpendicolare e alla superficie della mesh alla posizione del vertice con cui è associata.


Durante il calcolo dell'ombreggiatura, ogni vertice normale viene confrontato con la direzione della luce in entrata, che è anche un vettore. Se i due vettori sono perfettamente allineati, allora la superficie riceve la luce in testa a quel punto e la luminosità totale di questa verrà utilizzata per l'ombreggiatura. Una luce che esce esattamente lateralmente al vettore normale non darà alcuna illuminazione alla superficie in quella posizione. Tipicamente, la luce arriverà ad un angolo rispetto alla normale e quindi l'ombreggiatura sarà da qualche parte tra la piena luminosità e l'oscurità totale, a seconda dell'angolo.


Poiché la maglia è costituita da triangoli, può sembrare che le normali negli angoli risultano semplicemente perpendicolari al piano del loro triangolo. Tuttavia, le normali vengono solitamente interpolate al triangolo per dare la direzione della superficie delle posizioni intermedie tra gli angoli. Se tutte e tre le normali puntano nella stessa direzione, il triangolo sarà uniformemente illuminato ovunque. L'effetto di avere triangoli separati uniformemente ombreggiati, è che i bordi saranno molto nitidi e distinti. Questo è esattamente quello che serve per un modello di un cubo o di altri solidi taglienti, ma l'interpolazione delle normali può essere usata per creare una ombreggiatura piatta per approssimare una superficie curva come nel nostro caso.

Per ottenere bordi nitidi, è necessario raddoppiare i vertici ad ogni bordo, poiché entrambi i due triangoli adiacenti avranno bisogno di proprie normali in maniera separata. Per le superfici curve, i vertici sono condivisi solitamente lungo i bordi, ma spesso è necessaria una qualche forma di intuizione per determinare la direzione migliore per le normali condivise. Una normale potrebbe essere semplicemente la media delle normali delle superfici dei triangoli circostanti. Tuttavia, per un oggetto come una sfera, le normali dovrebbero puntare direttamente verso l'esterno dal centro della sfera.

In questo modo ad ogni vertice è stato associato un valore della matrice del rumore e grazie alla triangolazione di questi punti, si è potuta creare la mappa poligonale. Applicando, inoltre, ad ogni triangolo una texture e sfruttando l'UV mapping, la mappa è stata colorata rispecchiando un paesaggio. Infine, mediante la normalizzazione delle facce, le ombreggiature sulla superficie dovute ai componenti che simulano la luce sulla mappa sono state rese uniformi e realistiche.


Incollamento delle superfici limitrofe mediante nodi

Il problema principale riscontrato durante lo sviluppo del progetto è stato quello di far coincidere le altezze tra diversi incollamenti limitrofi. Per ovviare al problema, che generava dei vuoti tra le differenti altezze, è stato applicato per ogni bordo di ogni porzione di mappa una risoluzione della mesh doppia rispetto a quella utilizzata nel resto degli incollamenti.


In questo modo è bastato dare ai vertici dei bordi adiacenti un valore medio in altezza per risolvere il problema. Per assegnare questo valore però ogni vertice è stato trattato come un nodo di un grafo.


Il grafo è formato da dei vertici principali (in viola nell'immagine sopra), utilizzati come vertici per la costruzione dei triangoli che compongono la mesh, i vertici ignorati (in grigio), che non sono considerati nella computazione attuale della mesh ma potrebbero esserlo all'aumentare della risoluzione e dei vertici fuori dalla mesh (in rosso), non mostrati nella mappa ma utili per il calcolo delle normali sui bordi. Inoltre, tra i vertici fuori dalla mesh e i vertici principali, sono stati aggiunti dei vertici bordo (in arancione), che si connettono a tutti i vertici limitrofi ai vertici principali (in verde) per creare dei triangoli con una risoluzione molto più alta di questi ultimi.

In questo modo, solo i vertici bordo adiacenti tra i due incollamenti devono essere valutati nella media delle altezze, mentre i vertici di connessione vengono adattati in modo tale che tra i vertici principali e i vertici bordo non vi sia una pendenza troppo netta che risulterebbe visibile e fuori contesto. L'utilizzo, inoltre, di una mesh non visibile fuori di questa permette un calcolo della normale adeguato che crea un'ombreggiatura uniforme tra i bordi degli incollamenti adiacenti.