Entradas en "procedural"

Ruido Perlin

Vamos con una explicación (seguida por la implementación de rigor) del algoritmo de ruido más usado en todo el mundo; el ruido Perlin.

El modelo conceptual del ruido Perlin fue descubierto en 1982 por Ken Perlin como resultado de su trabajo de generación de texturas para la película Tron. Desde entonces, el ruido Perlin, y pequeñas variantes posteriores (como el ruido Simplex) son la base para generar efectos como fuego, humo, nubes… texturas como madera, mármol, granito… mapas de altura, etc, de forma totalmente automática. En esencia, nos permite generar patrones de forma muy similar a como lo suele hacer la naturaleza.

En esta entrada vamos a explicar todo el proceso, la naturaleza del ruido, a implementarlo, y finalmente a usarlo para generar terrenos en 3D como el de la siguiente imagen (y un visor interactivo para probarlos, al final de la entrada):

noise_final

RUIDO BLANCO

Primero, entendamos las características del ruido aleatorio para comprender en qué se diferencia el ruido Perlin de él. Si generamos un mapa 2D de ruido blanco clásico (valores (pseudo)aleatorios), obtenemos algo similar a la siguiente imagen:

noise

Exacto, es muy parecido a lo que veíamos en nuestras viejas televisiones cuando no habíamos seteado ningún canal; sólo que entonces era el resultado del ruido blanco electromagnético del ambiente, completamente caótico, y en este caso sólo son bits al azar.

¿Qué características importantes vemos en esa imagen?

1) Desde el punto de vista de la teoría de la información, la entropía es máxima. Así que esta imagen no puede comprimirse al codificarse sólo con los símbolos usados en su lenguaje (blanco/negro).

2) Desde un punto de vista físico, su densidad media es prácticamente constante (tiende fuertemente a serlo) para todos los fragmentos de dimensiones superiores a 1×1. Es decir, si hacemos un desenfoque gaussiano la imagen se volverá esencialmente plana, incluso con radios de tan sólo 2px.

RUIDO PERLIN (1 dimensión)

En el ruido Perlin las características son las opuestas, que es lo deseable cuando trabajamos en generación procedural o automática. Si entendemos cómo se crea el ruido, es fácil y lógico entender el por qué de esta naturaleza.

Así que empecemos:

Vamos a calcular el ruido perlin como la generación de onda n-dimensional compuesta por k octavas. Si pensamos en la función seno para representar una onda:

sin

Vemos como su amplitud va desde -1 a 1 (2 en total) y su longitud de onda es 6. Esta bien podría ser la primera componente de nuestra onda final, en el siguiente paso, queremos una onda de la misma naturaleza, pero con mayor frecuencia (menor longitud de onda) y menor amplitud. Por ejemplo:

graph2

La tercera y cualta deberían obedecer al mismo principio (suponiendo que sólo usáramos 4):

graph3

graph4

De esta forma, si sumamos las componentes anteriores, y en general cualesquiera en las que cada una aumenta la frecuencia y reduce la amplitud de forma progresiva, obtendremos algo como lo siguiente:

graph0

Esta onda unidimensional, que se asemeja al perfil de un paisaje montañoso cumple el siguiente principio, que tanto observamos en la naturaleza: A mayor escala, menor número de variaciones pero con más influencia, a menor escala, mayor número de variaciones pero con menor influencia. O dicho de otra forma, a altas frecuencias bajas amplitudes y viceversa.

Pero en la naturaleza los procesos no están formados a base de ondas periódicas como el seno que hemos usado hasta ahora. Debemos crear una onda pseudo-aleatoria simplemente eligiendo valores aleatorios en los “nodos”. Los nodos son los puntos en los que una onda periódica alcanzaría un máximo o mínimo, es decir, debemos introducir valores cada λ unidades de espacio (longitud de onda).

Ejemplo:

puntos generados aleatoriamente para formar una onda

puntos generadores aleatoriamente para generar una onda

Una vez generados los puntos, debemos interpolar entre los valores de los nodos para rellenar todo el dominio en el que se define la onda. Podemos usar aquí cualquier tipo de interpolación: linear, trigonométrica, Lagrange, B-splines… pero usualmente con una simple interpolación linear es suficiente. Los resultados finales no mejoran demasiado con interpolaciones más complejas (como los B-Splines, que sería la ideal) y que tienen un coste computacional muy alto. No obstante sois libres de usar la que mejor os parezca.

Nota: Tengo pendiente una entrada sobre interpolación, usando B-Splines (splines cúbicos) y Lagrange, que sí son muy útiles en otros cientos de aplicaciones.

interpolación lineal

interpolación lineal

interpolación por cosenos

interpolación por cosenos

interpolación cúbica

interpolación cúbica

Para utilizar una nomenclatura adecuada, a cada componente vamos a llamarla octava, y usaremos un caso típico en el que en cada octava la frecuencia se multiplica por dos y la amplitud si divide por dos (de hecho, es así cómo se definen las octavas en música).

Con todo esto, ya podemos empezar a generar nuestra primera onda de ruido Perlin real. Empezaremos con una frecuencia de 2 (dos cambios en todo el dominio) y una amplitud de 128 (para representarla en una imagen de 256*256 siendo el centro del eje de ordenadas el centro de la imagen.

frecuencia: 2 amplitud: 128

frecuencia: 2
amplitud: 128

frecuencia: 4 amplitud: 64

frecuencia: 4
amplitud: 64

frecuencia: 8 amplitud: 32

frecuencia: 8
amplitud: 32

frecuencia: 16 amplitud: 16

frecuencia: 16
amplitud: 16

frecuencia: 32 amplitud: 6

frecuencia: 32
amplitud: 6

frecuencia: 64 amplitud: 4

frecuencia: 64
amplitud: 4

frecuencia: 128 amplitud: 2

frecuencia: 128
amplitud: 2

El resultado de sumar estas 7 octavas es el siguiente:

Ruido Perlin con 7 octavas

Ruido Perlin final con 7 octavas

Y el código que he escrito para generarlas es el siguiente:

//=============
//Interpolation
//=============
var interpolate={}
interpolate.linear=function(x1,y1,x2,y2,x)
{
	return ((x-x1)*(y2-y1)/(x2-x1))+y1;
}
//=============
//Perlin Noise
//=============
var perlin={}
perlin.octave(frequency, amplitude, length)
{
	var wave=new Array(length);
	var step_length=Math.floor(length/frequency);
	for(var i=0;i<=length;i+=step_length)
	{
		//Create the nodes of the wave
		wave[i]=(amplitude/2)-(Math.random()*amplitude);
		//Interpolation between nodes
		if(i>=step_length)
		{
			for(var j=i-(step_length-1);j<i;j++)
			{
				var x1=i-(step_length);
				var x2=i;
				wave[j]=interpolate.linear(x1,wave[x1],x2,wave[x2],j);
			}
		}
	}
	return wave;
}

Como veis el código es muy sencillo. El objeto “interpolate” está preparado para expandirse añadiendo nuevos métodos de interpolación si fuese necesario. Para generar todas las octavas y sumarlas, usando una progresión de doble frecuencia/mitad amplitud, podríamos simplemente hacer algo ad hoc como lo siguiente:

var lenght=256;
var perlin_wave=new Array(lenght);
var n_octaves=7;
for(var i=0;i<perlin_wave.length;i++) //wave initialization
	perlin_wave[i]=0;
for(var i=1;i<=n_octaves;i++)
{
	var current_pow=Math.pow(2,i);
	var octave=perlin.octave(current_pow,lenght/current_pow,lenght);
	for(var j=0;j<perlin_wave.length;j++)
		perlin_wave[j]+=octave[j];
}

O bien, podemos crear un método dentro del objeto perlin con el código anterior si lo que queremos es tenerlo encapsulado.

Con esto ya tenemos nuestro generador de ruido Perlín en una dimensión. Aunque lo interesante viene para el caso en 2D.


Prueba a generar nuevas ondas con nuestra implementación haciendo clic en el botón
Generar una nueva onda

RUIDO PERLIN (2 dimensiones)

Para el caso de 2 dimensiones debemos pensar en la onda y sus octavas como mapas o texturas. Una octava 2D con frecuencia 2 creará dos valores aleatorios por dimensión, es decir, un total de 2×2=4 valores que estarán situados en las 4 esquinas del mapa. Si la amplitud es de 256 con valores entre -128 a 128 podemos normalizarla a valores entre 0 y 256 y dibujar en escala de grises (un gris para cada valor) la onda de forma muy gráfica y representativa.

Ejemplo:

image21

En este caso, hemos rellenado el dominio vacío de la onda, con el color del punto definido que manda sobre el cuadrante; dado que como hemos dicho, sólo los vértices del mapa tienen un valor establecido. Sin embargo, lo ideal es de nuevo usar algún método de interpolación para rellenar todo el dominio. De nuevo el más usado para este caso es la interpolación lineal aplicada a dos dimensiones (bilinear), que está perfectamente explicada en la wikipedia. De esta forma, obtenemos algo como lo siguiente:

image22

Usando estos principios, podemos empezar a generar octavas y crear nuestro ruido Perlin en 2D. Por ejemplo:

frecuencia: 2 amplitud: 128

frecuencia: 2
amplitud: 128

frecuencia: 4 amplitud: 64

frecuencia: 4
amplitud: 64

frecuencia: 8 amplitud: 32

frecuencia: 8
amplitud: 32

frecuencia: 16 amplitud: 16

frecuencia: 16
amplitud: 16

frecuencia: 32 amplitud: 8

frecuencia: 32
amplitud: 8

frecuencia: 64 amplitud: 4

frecuencia: 64
amplitud: 4

frecuencia: 128 amplitud: 2

frecuencia: 128
amplitud: 2

La suma de todas estas octavas da como resultado:

Ruido Perlin 2D final con 7 octavas

Ruido Perlin 2D final con 7 octavas

Esta imagen ya tiene semejanza con algo que parecen ser nubes o humo sobre un fondo, de hecho, si dejamos el canal B a 255 y el canal G como el máximo de (185,valor_de_la_onda), habremos creado un sencillo filtro que produce imágenes como la siguiente:

nubes fluorescentes

nubes fluorescentes lanshóricas

El código para el ruido Perlin en 2D que he escrito para generar los ejemplos anteriores es el siguiente:

//=============
//Interpolation
//=============
var interpolate={}
interpolate.linear=function(x1,y1,x2,y2,x)
{
	return ((x-x1)*(y2-y1)/(x2-x1))+y1;
}
interpolate.bilinear=function(x1,y1,x2,y2,v1,v2,v3,v4,tx,ty)
{
	//P1:{x1,y1,v1} - P2:{x2,y1,v2} - P3:{x1,y2,v3} - P4:{x2,y2,v4}
	//Target:{tx,ty}
	//NOTE: Bind each area with the oposite value
	var area_v1=Math.abs((tx-x1)*(ty-y1))*v4;
	var area_v2=Math.abs((tx-x2)*(ty-y1))*v3;
	var area_v3=Math.abs((tx-x1)*(ty-y2))*v2;
	var area_v4=Math.abs((tx-x2)*(ty-y2))*v1;
	var area_total=(x2-x1)*(y2-y1);
	return (area_v1+area_v2+area_v3+area_v4)/area_total;

}
//=============
var perlin={}
perlin.octave_2d=function(frequency, amplitude, length)
{
	var step_length=Math.floor(length/frequency);
	var wave=new Array(length+1);
	for(var i=0;i<=length;i++)
		wave[i]=new Array(length);
	for(var i=0;i<=length;i+=step_length)
	{
		for(var j=0;j<=length;j+=step_length)
		{
			//Create the nodes of the wave
			wave[i][j]=(amplitude/2)-(Math.random()*amplitude);
			//Interpolation between nodes
			if(i>=step_length && j>=step_length)
			{
				for(var a=i-(step_length);a<=i;a++)
				{
					for(var b=j-(step_length);b<=j;b++)
					{
						var x1=i-(step_length);
						var x2=i;
						var y1=j-(step_length);
						var y2=j;
						wave[a][b]=interpolate.bilinear(x1,y1,x2,y2,wave[x1][y1],wave[x2][y1],wave[x1][y2],wave[x2][y2],a,b);
					}
				}
			}
		}
	}
	return wave;
}
//=============
function wave2D(data)
{
	this.map=data;
	this.add=function(data)
	{
		for(var i=0;i<data.length;i++)
		{
			for(var j=0;j<data.length;j++)
				this.map[i][j]+=data[i][j];
		}
	}
	this.render=function(ctx)
	{
		for(var i=0;i<this.map.length;i++)
		{
			for(var j=0;j<this.map.length;j++)
			{
				//Normalize from 0 to 255
				var depth=Math.floor(128+this.map[i][j]);
				//LaNsHoRic clouds: ("+depth+","+Math.max(185,depth)+",255)
				ctx.fillStyle="rgb("+depth+","+depth+","+depth+")";
				ctx.fillRect(i,j,1,1);
			}
		}
	}
	this.toURL=function()
	{
		var canvas=new Canvas();
		canvas.width=canvas.height=this.map.length;
		var ctx=canvas.getContext("2d");
		this.render(ctx);
		return canvas.toDataURL();
	}
}

Con esto, podemos adaptar el código de generación anterior a lo siguiente:

var final_wave=new wave2D(perlin.octave_2d(1,256,256));
for(var i=1;i<8;i++) //7 octaves
{
	var current_pow=Math.pow(2,i);
	var octave=perlin.octave_2d(current_pow,256/current_pow,256);
	final_wave.add(octave);
}

Prueba a generar nuevos mapas con nuestra implementación haciendo clic en el botón
Generar un nuevo mapa

Podemos cambiar la forma en que aumenta la frecuencia y disminuye la amplitud para obtener diferentes resultados. Jugando con la progresión y los valores podemos obtener texturas como granito, nubes dispersas, humo denso, etc. O usar el ruido como perturbación de un mapa base, con esto podemos generar lava, madera, mármol, relámpagos, etc. Sólo es cuestión de ir jugando con valores y experimentar un poco.

El siguiente uso popular de los mapas de ruido Perlin como el que acabamos de generar, es como mapas de altura. De esta forma podemos generar terrenos de forma automática, que en base a nuestros parámetros de generación podrán ser más o menos montañosos, más escarpados, más suaves…

En el siguiente cuadro puedes ver como usando nuestro generador de ruido Perlin creamos terrenos en 3D. Puedes hacer clic con el ratón y arrastrar para rotar la cámara. La implementación del modelado en 3D y del visor del mapa de altura están fuera del contenido de la entrada, pero prometo preparar una hablando de ello si os interesa (notificádmelo).

Como resumen rápido, dividimos un plano en tantas secciones de como frecuencia f tiene la mayor octaba. El plano queda con f*f vértices que asociamos con los píxeles del mapa 2D generado, para elevarlos según el valor del mapa en ese punto. Así el plano queda deformado como en los siguientes ejemplos:


Haz clic y arrastra el ratón para visualizar el terreno.
Generar un nuevo terreno aleatorio

Si os sirve de ayuda no es necesario mención pero sí sería cortés un agradecimiento aunque fuese en un comentario 🙂

Leer más