Algoritmo di generazione procedurale di heightmap 2D tramite interpolazione del rumore di Perlin e diagramma di Voronoi

Studente proponente

s213405 Dami Alessio

Titolo della proposta

Descrizione del problema proposto

Il rumore di Perlin è un tipo di gradient noise (rumore creato tramite funzioni gradiente) che è utilizzato nella creazione di texture, mappe, superfici e molto altro. Ha i vantaggi di essere pseudo-casuale, graduale tra i suoi valori (senza sbalzi) e controllabile tramite i suoi attributi. L'algoritmo però è omogeneo, senza zone distinte tra loro. L'integrazione di un diagramma di Voronoi può risolvere questo problema, interpolando i valori normalmente ottenuti dal rumore con quelli dati da una media pesata delle distanze di ogni singola coordinata rispetto ai suoi nodi più vicini

Descrizione della rilevanza gestionale del problema

I classici algoritmi di generazione rumore sono utili al' ingegnere gestionale quando si lavora su mappe che possono rappresentare il territorio. Le varie celle del diagramma di Voronoi possono essere assimilabili ai vari distretti, zone o quartieri di una città, o similmente varie zone di una provincia e così via. Queste zone rappresentano la presenza più o meno elevata di una determinata caratteristica, come ad esempio la copertura di rete, o la presenza di centri di distribuzione e logistica. A queste zone può essere applicato quindi un rumore di sottofondo per simulare una casualità all'interno della zona. L'algoritmo quindi potrebbe essere utile nella simulazione a priori, e rimane comunque utile nel suo scopo originale di generazione texture, mappe, shader e simili utilizzi.

Descrizione dei data-set per la valutazione

L'algoritmo utilizza un singolo database formato dall'insieme dei diagrammi di Voronoi sotto forma di insieme dei seed che li generano.
Il database è stato popolato casualmente, ed il programma permette di recuperare uno specifico diagramma tramite ricerca dei nodi, e anche l'inserimento nel database di un nuovo diagramma tramite l'inserimento manuale di ogni singolo nodo. (è ad esempio possibile inserire un diagramma con nodi a forma circolare che permetta la generazione di una mappa a forma toroidale)

Descrizione preliminare degli algoritmi coinvolti

Il primo passo è la generazione del diagramma di Voronoi dati un insieme di punti (siano essi presi dal database o inseriti manualmente come nuovi). Dopodiché il programma, per ogni coordinata del piano, trova i K nodi/semi più vicini (numero modificabile) e applica una media pesata delle distanze della coordinata da questi K nodi (più vicino è il nodo più peso avrà nella media). Questo passaggio permette, maggiore siano i nodi presi in considerazione, di trascurare via via i bordi tra le varie celle del diagramma che sono tipiche di Voronoi. Salvate queste distanze pesate (e normalizzate nell'intervallo [0,1] per essere compatibili con altri rumori) viene generato, sullo stesso piano di uguali dimensioni, un rumore di Perlin secondo le sue caratteristiche (ampiezza, frequenza, ottave, etc). Infine l'algoritmo attua un interpolazione lineare tra i due piani (il piano delle distanze pesate normalizzate e il piano del rumore di Perlin) e fornisce il piano interpolato finale.

Durante questi passaggi c'è la possibilità di mostrare a schermo i risultati intermedi, come ad esempio l'heightmap data dalle distanze pesate normalizzate del diagramma di Vononoi, oppure il rumore di Perlin preso singolarmente, oppure il risultato interpolato finale, sia come scala di grigi (grayscale) sia come immagine colorata (ad esempio si assegnano dei colori blu, celeste, verde, marrone e bianco per simulare una mappa, con valori che vanno dal blu (0) che rappresenta il mare profondo al bianco (1) che rappresenta vette di montagna)

Descrizione preliminare delle funzionalità previste per l’applicazione software

Sebbene non esaustive, queste sono le funzioni previste dall'applicativo:

Inserimento e reperimento di un diagramma di Voronoi dal database. Possibilità di mostrare a schermo il diagramma corrente. L'inserimento dei nodi avverrebbe tramite coordinate 2D

Modifica dei parametri usati nell'algoritmo da parte dell'utente per ottenere risultati in base alle proprie preferenze. Un elenco non esaustivo è: Numero di nodi da prendere in considerazione quando si fa la media pesata delle distanze, Clamping valori dell'heightmap delle distanze: possibilità di normalizzare valori oltre una certo intervallo (valori troppo scuri o chiari) Possibilità di invertire i valori delle distanze: un valore più vicino a un nodo sarà più scuro piuttosto che essere più chiaro. Attributi del rumore di Perlin: ampiezza, frequenza, ottave e persistenza

Inoltre sarà data la possibilità di mostrare risultati (immagini) intermedi e salvarle.

TdP-prove-finali / Introduzione