Saturday, December 31, 2011

Perlin Noise in JavaScript

Perlin noise in two dimensions, generated using the code below.
I've been working on an HTML5 canvas-based procedural texture demo (which I'll blog about tomorrow), for which I did a JavaScript port of Ken Perlin's noise() routine (which is in Java). Ahead of tomorrow's blog, I thought I'd briefly discuss Perlin Noise.

Perlin Noise
If you've worked with 3D graphics programs, you're already well familiar with Ken Perlin's famous noise function (which gives rise to so-called Perlin noise). The code for it looks a little scary, but intuitively it's an easy function to understand. Let's take the 2D case (although you can generate Perlin noise for any number of dimensions). Imagine that you have a 256-pixel-square image (blank, all white). Now, imagine that I come along and tell you to mark the canvas off into 32 rows and 32 columns of 8x8-pixel squares. Further imagine that I ask you to assign a random grey value to each square. You've now got a kind of checkerboard pattern of random greys.

What differentiates Perlin noise from random checkboard noise is that in Perlin's case, the color values are interpolated smoothly from the center of each tile outward, in such a way that you don't see an obvious gridlike pattern. In other words, when you cross a tile boundary, you want the slope of the pixel intensity to be constant (no discontinuities). You can visualize the end result if you took the 32x32 random checkboard pattern and passed it through a Gaussian blur a few times. Pretty soon, you wouldn't even be able to tell that gridlines ever existed in the first place. That's the idea with Perlin noise. You want to interpolate colors from one block to the next in such a way that there are no discontinuities at the cell boundaries. It turns out this requirement can be met in quite a variety of ways (by using cubic splines, quartics, or even sine- or cosine-based interpolation between squares, for example; or by using Perlin's gain() function). There's no one "correct" way to do it.

I'd love to be able to link to a good Perlin noise tutorial on the Web, but so far I haven't found one that doesn't try to conflate fractal noise, turbulence, and other topics with Perlin noise. The best treatment I've come across, frankly, is (not surprisingly) in Perlin's own Texturing and Modeling book (which is truly a first-rate book, "must reading" for graphics programmers).

Fortunately, Ken Perlin has done all the hard work for us in writing the necessary interpolation (and other) code for noise(), and he has kindly provided a 3D reference implementation of the noise() function in highly optimized Java. I ported his code to JavaScript (see below) and I'm happy to say it works very well in a canvas environment (as we'll see in tomorrow's post, right here). It's reasonably fast, too. In fact, it's so fast that there's no need to fall back to a 2D version for better speed. This is good, because the 3D version gives you added versatility in case you decide you want to animate your noise in the time domain.

Usage of Perlin's function is very straightforward. It takes 3 arguments (in Java, these are double-precision floating point numbers -- which is fine, because in JavaScript all numbers are IEEE-754 double-precision floating point numbers, under the covers). The way the function is usually used, the first two arguments correspond to the x and y coordinate values of a pixel in 2-space. If you're working in 3-space, the third argument is the z-value. In 2-space, you can call the noise() function with the third argument set to whatever you like. If you're doing a 2D animation and want the texture to animate in real time, you can link the third argument (that z-value) to a time-based index, and the texture will animate smoothly, because you are, in effect, sampling closely spaced slices of a 3D noise space.

The return value from noise() is a double-precision floating point number in the range 0..1. Actually, in Perlin's original code, the return value can range from -1 to 1.0, but in my JavaScript port (below), I clamp the return to 0..1. Here's the code:

// This is a port of Ken Perlin's Java code. The
// original Java code is at http://cs.nyu.edu/%7Eperlin/noise/.
// Note that in this version, a number from 0 to 1 is returned.
PerlinNoise = new function() {

this.noise = function(x, y, z) {

   var p = new Array(512)
   var permutation = [ 151,160,137,91,90,15,
   131,13,201,95,96,53,194,233,7,225,140,36,103,30,69,142,8,99,37,240,21,10,23,
   190, 6,148,247,120,234,75,0,26,197,62,94,252,219,203,117,35,11,32,57,177,33,
   88,237,149,56,87,174,20,125,136,171,168, 68,175,74,165,71,134,139,48,27,166,
   77,146,158,231,83,111,229,122,60,211,133,230,220,105,92,41,55,46,245,40,244,
   102,143,54, 65,25,63,161, 1,216,80,73,209,76,132,187,208, 89,18,169,200,196,
   135,130,116,188,159,86,164,100,109,198,173,186, 3,64,52,217,226,250,124,123,
   5,202,38,147,118,126,255,82,85,212,207,206,59,227,47,16,58,17,182,189,28,42,
   223,183,170,213,119,248,152, 2,44,154,163, 70,221,153,101,155,167, 43,172,9,
   129,22,39,253, 19,98,108,110,79,113,224,232,178,185, 112,104,218,246,97,228,
   251,34,242,193,238,210,144,12,191,179,162,241, 81,51,145,235,249,14,239,107,
   49,192,214, 31,181,199,106,157,184, 84,204,176,115,121,50,45,127, 4,150,254,
   138,236,205,93,222,114,67,29,24,72,243,141,128,195,78,66,215,61,156,180
   ];
   for (var i=0; i < 256 ; i++) 
 p[256+i] = p[i] = permutation[i]; 

      var X = Math.floor(x) & 255,                  // FIND UNIT CUBE THAT
          Y = Math.floor(y) & 255,                  // CONTAINS POINT.
          Z = Math.floor(z) & 255;
      x -= Math.floor(x);                                // FIND RELATIVE X,Y,Z
      y -= Math.floor(y);                                // OF POINT IN CUBE.
      z -= Math.floor(z);
      var    u = fade(x),                                // COMPUTE FADE CURVES
             v = fade(y),                                // FOR EACH OF X,Y,Z.
             w = fade(z);
      var A = p[X  ]+Y, AA = p[A]+Z, AB = p[A+1]+Z,      // HASH COORDINATES OF
          B = p[X+1]+Y, BA = p[B]+Z, BB = p[B+1]+Z;      // THE 8 CUBE CORNERS,

      return scale(lerp(w, lerp(v, lerp(u, grad(p[AA  ], x  , y  , z   ),  // AND ADD
                                     grad(p[BA  ], x-1, y  , z   )), // BLENDED
                             lerp(u, grad(p[AB  ], x  , y-1, z   ),  // RESULTS
                                     grad(p[BB  ], x-1, y-1, z   ))),// FROM  8
                     lerp(v, lerp(u, grad(p[AA+1], x  , y  , z-1 ),  // CORNERS
                                     grad(p[BA+1], x-1, y  , z-1 )), // OF CUBE
                             lerp(u, grad(p[AB+1], x  , y-1, z-1 ),
                                     grad(p[BB+1], x-1, y-1, z-1 )))));
   }
   function fade(t) { return t * t * t * (t * (t * 6 - 15) + 10); }
   function lerp( t, a, b) { return a + t * (b - a); }
   function grad(hash, x, y, z) {
      var h = hash & 15;                      // CONVERT LO 4 BITS OF HASH CODE
      var u = h<8 ? x : y,                 // INTO 12 GRADIENT DIRECTIONS.
             v = h<4 ? y : h==12||h==14 ? x : z;
      return ((h&1) == 0 ? u : -u) + ((h&2) == 0 ? v : -v);
   } 
   function scale(n) { return (1 + n)/2; }
}

So let's say you have a function that marches through all the pixel values in an image, and you want to use this code. You need the x and y coordinates of the pixel, the width of the image (as w), and the height (as h). Then you could do something like:

x /= w; y /= h; // normalize
size = 10;  // pick a scaling value
n = PerlinNoise.noise( size*x, size*y, .8 );
r = g = b = Math.round( 255 * n );

Here, the z-argument is arbitrarily set to .8, but it could just as well be set to zero or whatever you like. You can fiddle with size to get a result that's visually pleasing (it will vary considerably, depending on the effect that you're trying to achieve). If you're animating the texture, the next time-step might set the z-arg to 0.9, say, instead of 0.8.

In the example given above, we're setting r = g = b, which of course gives a grey pixel. The overall result looks like the picture at the top of this post. In fact, that image was generated using the code shown above.

Perlin's justly famous noise function is enormously versatile (and a ton of fun to play with). As I say, the most authoritative, in-depth discussion of it occurs in Perlin's Texturing and Modeling book. We'll see more colorful uses of the noise() function in tomorrow's blog. Don't miss it!