Entradas en "procedural"

Ruido Perlin

Publicado por LaNsHoR el 16/11/2014 en Computación Gráfica | 344 comentarios

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):

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:

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:

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:

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

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:

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:

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.

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.

El resultado de sumar estas 7 octavas es el siguiente:

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.

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:

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:

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

La suma de todas estas octavas da como resultado:

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:

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);
}

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:

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