Noise.glsl
rumore pseudo casuale per la generazione procedurale
"Chiunque consideri metodi aritmetici per produrre cifre casuali è, ovviamente, in uno stato di peccato."
"Various Techniques Used in Connection With Random Digits" ↗
In computer graphics vengono largamente utilizzate tecniche per la sintesi di rumore pseudo casuale. Queste tecniche sono fondamentali per la generazione procedurale, che si contrappone all'utilizzo di contenuti precedentemente predisposti ad hoc e archiviati. Sono particolarmente adatte per una gran quantità di contenuti, quali nuvole, rilievi montuosi, materiali vari e strutture organiche. In generale qualsiasi contenuto che voglia simulare la casualità e la complessità presente in molti fenomeni naturali.
Un progetto in cui ho utilizzato ampiamente questa tecnica è il mio simulatore spaziale Amazing Skies, dove utilizzo rumore pseudo causale per la generazione di nebulose e corpi celesti, in particolare le atmosfere e gli anelli dei giganti gassosi e le coste e le montagne dei pianeti rocciosi.
Perlin e simplex noise
Nel 1983 Kenneth H. Perlin introdusse una tecnica per la sintesi di rumore pseudo casuale. Questa tecnica, chiamata Perlin noise e considerata ora la tecnica classica ("classic" noise), viene descritta per la prima volta nel 1985, in un articolo di Perlin intitolato "An image synthesizer" ↗.
Nel 2001 lo stesso Perlin introdusse un algoritmo migliore chiamato simplex noise. Questa nuova versione mostra meno artefatti, è perfettamente isotropa e inoltre è più efficiente aumentando il numero di dimensioni.
Il simplex noise, come suggerisce il nome, suddivide lo spazio in simplessi. I simplessi sono i politopi regolari la cui sequenza inizia con: punto, segmento, triangolo, tetraedro, eccetera. In n dimensioni un simplesso ha n + 1 vertici e questo permette all'algoritmo simplex noise di essere più efficiente aumentando il numero di dimensioni rispetto al Perlin noise.
Avere un algoritmo che si comporta bene, in termini di efficienza, aumentando il numero di dimensioni è utile in molti casi. Aggiungere una dimensione potrebbe ad esempio essere utile per avere un rumore che evolve nel tempo o secondo qualche altro parametro.
Value noise
L'originale Perlin noise e il successivo simplex noise sono due esempi di gradient noise. Senza entrare troppo nei dettagli implementativi, l'idea alla base di questi algoritmi e di assegnare un vettore a ciascun punto di una griglia di punti, i quali rappresentano il gradiente della funzione nel punto. Il value noise che vedremo in dettaglio in questa pagina non appartiene a questa categoria, è di qualità inferiore, ma molto più semplice e meno costoso in termini di quantità di calcoli. In pratica, come vedremo, invece di definire per ogni punto della griglia il gradiente si assegna direttamente il valore della funzione.
L'idea di utilizzare un algoritmo che produca rumore di minor qualità nasce dal fatto che il rumore di base creato da questi algoritmi raramente viene utilizzato così com'è. Come vedremo nel prossimo paragrafo vengono quasi sempre effettuati più passaggi, ognuno dei quali richiede l'esecuzione dell'algoritmo in questione. Questo porta da una parte a rendere molto importante la velocità dell'algoritmo e dall'altra a rendere meno importante la qualità del rumore generato con un singolo passaggio.
Resta il fatto che nei casi in cui sia sufficiente e opportuno utilizzare uno o pochi passaggi, come ad esempio per realizzare delle bolle o delle gocce, questo algoritmo non è adatto e convine utilizzare una qualche versione di gradient noise.
L'algoritmo in GLSL (attenzione: questo codice potrebbe essere notevolmente ottimizzato, è stato scritto in questa forma con lo scopo di essere il più leggibile possibile):
float valueNoise(vec2 point)
{
vec2 floorPoint = floor(point);
vec2 fractPoint = fract(point);
vec2 smoothPoint = smoothstep(0.0, 1.0, fractPoint);
float value00 = pseudoRandom(floorPoint + vec2(0, 0));
float value01 = pseudoRandom(floorPoint + vec2(0, 1));
float value10 = pseudoRandom(floorPoint + vec2(1, 0));
float value11 = pseudoRandom(floorPoint + vec2(1, 1));
float value0 = mix(value00, value01, smoothPoint.y);
float value1 = mix(value10, value11, smoothPoint.y);
float value = mix(value0, value1, smoothPoint.x);
return 2.0 * value - 1.0;
}
Le funzioni floor, fract,
smoothstep e mix sono funzioni built-in in GLSL.
La prima, come fa intuire il nome, restituisce il valore intero minore o uguale più vicino al valore passato come argomento.
La seconda restituisce la parte frazionaria dell'argomento, quindi
fract(x) = x - floor(x).
La terza incapsula una funzione sigmoidea, per la precisione
smoothstep(x) = (3.0 - 2.0 * x) * x * x.
Infine mix fornisce l'interpolazione lineare del terzo parametro tra i primi due parametri, quindi
mix(a, b, x) = a + (b - a) * x.
Un metodo molto semplice e veloce per ottenere numeri pseudo casuali in un singolo passaggio è utilizzare la parte frazionaria di una sinusoide avente ampiezza di qualche ordine di grandezza superiore all'unità (ad esempio è più che sufficiente 100). La funzione
float pseudoRandom(float value)
{
return fract(100.0 * sin(value));
}
fornisce un numero pseudo casuale compreso tra 0 e 1. La funzione
float pseudoRandom(vec2 point)
{
return pseudoRandom(point.x + pseudoRandom(point.y));
}
utilizza due volte questo metodo, fornendo quindi un valore pseudo casuale compreso tra 0 e 1 a partire dal vettore passato come argomento.
Come si vede dal codice l'algoritmo consiste quindi semplicemente in un'interpolazione non lineare (in cui la non linearità è ottenuta con la funzione sigmoidea) dei valori pseudo casuali assegnati ai 4 vertici adiacenti al punto dato. Alla fine il valore ottenuto viene riscalato nell'intervallo tra -1 e 1.
Questo algoritmo è facilmente estendibile in 3 o più dimensioni. In n dimensioni i vertici della griglia intorno ad un punto saranno 2n e una volta ottenuti i 2n valori pseudo casuali si procederà alla sequenza di interpolazioni per le n coordinate.
Fractal noise
Come anticipato, indipendentemente dalla tecnica specifica utilizzata per produrre il rumore pseudo casuale, il risultato ottenuto viene quasi sempre utilizzato in un algoritmo iterativo che somma differenti contributi ad ampiezza e frequenza differente.
La funzione, sempre in GLSL, ha un ulteriore parametro oltre al punto di cui si vuole calcolare il risultato, la frequenza, che non è altro che un fattore moltiplicativo per il punto dato, quindi a tutti gli effetti uno zoom.
float fractalNoise(vec2 point, float frequency)
{
float result = 0.0;
float amplitude = 0.5;
for (int i = 0; i < OCTAVES; ++i)
{
result += valueNoise(point * frequency) * amplitude;
frequency *= 2.0;
amplitude /= 2.0;
}
return result;
}
L'algoritmo è incredibilmente semplice, soprattuto se consideriamo l'efficacia del risultato. Ad ogni iterazione si somma al risultato un nuovo valore ottenuto dal sintetizzatore di rumore, raddoppiando ad ogni iterazione la frequenza. Ad ogni iterazione inoltre l'ampiezza viene dimezzata, in modo che i contributi a frequenza maggiore siano via via meno intensi.
L'algoritmo non subisce alcuna modifica al passaggio ad un numero maggiore di dimensioni,
basterà cambiare il tipo dell'argomento point e utilizzare un'opportuna funzione per la generazione del rumore pseudo casuale.
L'ampiezza inizia con il valore 1/2 in modo da mantenere i risultati nell'intervallo da -1 a 1 (la serie geometrica 1/2 + 1/4 + 1/8 + ... converge infatti a 1). Non è necessario introdurre un fattore per l'ampiezza da passare come parametro, visto che moltiplicare il risultato finale ha lo stesso risultato di partire da un valore differente da 1/2.
Il numero di passaggi, o di ottave, utilizzando un termine musicale molto appropriato in questo contesto,
è inserito nel codice di esempio come costante in quanto in molte versioni è impossibile eseguire cicli parametrizzati da una variabile.
Se questa limitazione non ci fosse si potrebbe tranquillamente introdurre nella funzione un terzo parametro octaves
e riutilizzare lo stesso codice in contesti in cui sia richiesto un differente numero di iterazioni.