Friday, November 14, 2014

Perlin Noise [Implementation in Java]

I had previously talked in detail about Perlin Noise and its properties, here. Now in this blog post I will write about the implementation. My implementation is based on an excellent writeup which I found in this link (http://webstaff.itn.liu.se/~stegu/TNM022-2005/perlinnoiselinks/perlin-noise-math-faq.html).

Short Description



Fig: Perlin Noise(left), Noise(right)

Perlin noise is a function for generating coherent(smooth) noise over a space. I've have come across multiple implementations of Perlin Noise function and most of them are based on smoothing of multiple noise functions to generate a coherent noise. The one I am discussing in this blog post is alittle different and more or less conforms with the original implementation that Ken Perlin came up with.


Requirement

Perlin Noise (2D) function is a function that takes two points (x and y) and returns a noise value (say z). x, y and z are all floating point numbers.

The Grid

The concept of accepting floating point numbers can be explained from the concept of Grid. The space, which the noise function operates on, is assumed to be composed of grids. Grid, in terms of x and y, are the whole numbers. So, any decimal (fractions) are points lying inside a grid cell.



In the figure, (x0,y0), (x1,y1), (x0,y1), (x1,y0) represents grid points and (x,y) lies inside a grid.

Pseudorandom Gradient

Pseudorandom Gradient function takes the grid coordinates and generates pseudorandom gradient of length 1 as:

g(xgrid, ygrid) = (gx, gy)

These gradients can be visualized as:



Calculating grid influences

Next, We need to calculate a vector directing from grip points to the point (x,y).

vec00 = (x-x0,y-y0);
vec01 = (x-x0,y-y1);
vec10 = (x-x1,y-y0);
vec11 = (x-x1,y-y1);

The influence can be calculated by performing dot operation on the gradient and the vector as:

s = g(x0, y0) · vec00;
t = g(x1, y0) · vec10;
u = g(x0, y1) · vec01;
v = g(x1, y1) · vec11;


Interpolation

A smoothing function, characterized by the curver 3p2 - 2p3, is used to get a weight Sx at (x-x0) in the curve as:

Sx = smoothParam(x-x0);

and also at (y-y0) as:

Sy = smoothParam(y-y0);

where smoothParam(p) = 3p2 - 2p3 , then parameter representing weighted average of s and t is obtained by constructing a linear function mapping 0 to s and 1 to t, and evaluating it at our x dimension weight Sx. We call this ax.

        ax = s + Sx*(t - s);

We also calculate bx using u and v as:

        bx = u + Sx*(v - u);

Then the final result z can be obtained as:

z = ax + Sy*(bx - ax);

Implementation

I have implemented this algorithm in Java, and I have uploaded the project in github. You can view it from the link here.