Perlin Noise

PERLIN NOISE
por Olmo del Corral (olmobrutall@hotmail.com)

Perlin Noise

Este mapa es probablemente el más útil y famoso de todos los que hay, tanto es así que creo que su creador, Ken Perlin, tiene un oscar por ello.
Hay muy buena documentación sobre este mapa en Internet, la pagina de Hugo Elias es el mejor ejemplo de ello. Voy a intentar no repetir lo que dice Hugo en su pagina, imprescindible visitarla.

El mapa perlin es interesante porque tiene dos propiedades: Completa aleatoriedad y coherencia (es decir, que no hay mucha variación entre dos puntos contiguos, como pasa en White Noise).

Es muy útil pues hay multitud de efectos naturales que son su fiel reflejo (nubes o montañas son lo más típico), y otra multitud que son pequeñas modificaciones (la madera, o como verás, hasta las sombras del fondo de una piscina hacen uso de ella).

Noise

La creación del efecto es relativamente sencilla, consiste en hacer una cuadrícula con cuadros de N pixels de lado y, a cada vértice de los cuadrados, asociarle un número aleatorio. Los píxeles que no estén exactamente encima de uno de estos vértices (la mayoría), sino en el interior de algún cuadrado, tomarán el valor de la interpolacion de los numeros aleatorios de los vértives de éste. Con este algoritmo se consiguen imágenes como las de la izquierda (Noise).

Hay varias fórmulas matemáticas para la interpolación de puntos. En la página de Hugo se ven varias:

Interpolación Linear: Es rápida pero produce visibles picos en los vértices, quedando una imagen de no muy buena calidad. Hace uso de 2 Puntos en 1D, 4 en 2D, 8 en 3D
Interpolación Cosenoidal: No produce picos en los vértices, pero todos ellos tienen derivada 0. luego se ve claramente donde se encuentran. Usa 2 Puntos en 1D, 4 en 2D, 8 en 3D
Interpolación Cúbica: De muy buena calidad, pero tarda bastante en calcular, pues el algoritmo es complejo y hace uso de muchos puntos: 4 en 1D, 16 en 2D, 64 en 3D!!!. Además, puede hacer interpolaciones de puntos en un recorrido ([0...255] por ejemplo) que se salgan un poco de ese recorrido.

En mi ejemplo voy a usar una interpolación similar a la cosenoidal pero más rápida. Basada en el polinomio 3x^2-2x^3.
Este polinomio tiene f '(0)=f '(1)=0, f(0)=0 y f(1)=0. Además es el polinomio más pequeño que cumple estas características.
Utilizo este polinomio porque es mucho mas rápido de valuar que el equivalente cosenoidal: 0.5-0.5*cos(x*pi) y tiene una forma muy similar. Este es el código: a y b son dos valores cualesquiera, y x es la proporción de cercanía entre uno y otro: 0 si esta en a, 1 si b.

float InterPol(float a, float b, float x){     //a altura 1a
    return a+(b-a)*x*x*(3-2*x);                //b altura 2a
                   }                            //c si = 0 entonces a, si = 1 entonces b

Finalmente, algo que creo que Hugo no clarifica es la manera bidimensional y tridimensional de usar la Interpolación Lineal, Cosenoidal o Polinómica (con la cúbica seria mas complicado). Esto es lo que hay que hacer para interpolar el punto en un cuadrado (2D):

int a=InterPol(Punto(0,0),Punto(0,1),frac_x);
int b=InterPol(Punto(1,0),Punto(1,1),frac_x);
final=InterPol(a,b,frac_y);

Punto(n,m) indica los valores aleatorios de los vértices del cuadrado en el que se encuentra, frac_x es 0 cuando esta pegado al lado izquierdo del cuadrado, y 1 en el derecho. Y frac_y es 0 cuando está arriba del cuadrado, y 1 cuando está abajo. Hay una interpretación geométrica de como se hace la interpolación para imágenes en dos dimensiones, y porqué hace falta hacer tres procesos de interpolación, en esta interpolación el plano base es la imagen, y la altura es el valor que da la función Noise. Amenudo son interesantes las interpretaciones en 3D de los mapas.

Esta es la interpretación geométrica:
La rejilla gruesa indica los cuadrados en los que ha sido partida la imagen.(el periodo).
La rejilla fina son los píxeles. En este caso se puede ver que el periodo es de 16, y que por tanto cada celda o cuadrado tiene 16^2 pixels.
Las 4 barras verticales amarillas son los valores de IntNoise para cada vértice.
Las 2 barras verdes apoyadas en el plano indican los valores de frac_x y frac_y, se puede ver como en este caso frac_x= 4/16 y frac_y=4/16 mas o menos. El punto de intersección es el pixel del cual estamos calculado Noise(x,y)
Las Curvas rojas son las curvas del polinomio de interpolación, y los puntos verdes que hay en cada una de ellas están a la altura indicada por las variables a y b.
Finalmente la curva azul es el polinomio de la última instrucción, el punto verde está a la altura del valor final.

Después de este reto de visión espacial, solo queda decir que variando el tamaño de los cuadrado (periodo) y la amplitud de los valores se consiguen distintas imágenes Noise, superponiendo todas se consigue una imagen pseudo-fractal con distintos niveles de detalle como la que aparece al principio de esta pagina, este efecto se ve claramente en la pagina de Hugo Elias :

Este es el código final de mi mapa Perlin Noise:

 float PerlinNoise(float x,float y,int width,int octaves,int seed){
           if (octaves>12) {octaves=12;}             // octaves: Numero de pasadas a distinta amplitud y periodo
           double a,b,valor,freq,tam_pas,cachox,cachoy;
           int casilla,num_pasos,pasox,pasoy;
           int amplitud=256;                        //La amplitud es 128,64,32,16... para cada pasada
           int periodo=256;                         //El periodo es similar a la amplitud
           for (int s=0;s<octaves;s++){
                amplitud>>=1;                      //Manera rápida de dividir entre 2
                periodo>>=1;
                freq=1/float(periodo);             //Optimizacion para dividir 1 vez y multiplicar luego
                num_pasos=int(width*freq);         //Para el const que vimos en IntNoise
                pasox=int(x*freq);                 //Indices del vértice superior izquerda del cuadrado
                pasoy=int(y*freq);                 //en el que nos encontramos
                cachox=x*freq-pasox;               //frac_x y frac_y en el ejemplo
                cachoy=y*freq-pasoy;
                casilla=pasox+pasoy*num_pasos;     // índice final del IntNoise
                a=InterPol(IntNoise(casilla+seed),IntNoise(casilla+1+seed),cachox);
                b=InterPol(IntNoise(casilla+num_pasos+seed),IntNoise(casilla+1+num_pasos+seed),cachox);
                valor+=InterPol(a,b,cachoy)*amplitud;   //superposicion del valor final con anteriores
              }
          return valor;                           //seed es un numero que permite generar imagenes distintas
              }                                   //pues IntNoise dará valores distintos

ANTERIOR

INDICE

SIGUIENTE