Pages

Monday, February 15, 2010

Bring the (Perlin) Noise

If you just want the source code: The JavaScript Perlin noise generator code is here.

I mentioned in a previous post that I was working on a Perlin noise generator for Art Evolver.

Perlin noise is a function of (x, y) that produces a random-ish pattern. It's not completely random because it has smooth hills and valleys, but the distribution of those hills and valleys is random.

A side note about this algorithm: Usually if you're a computer scientist and you come up with a clever algorithm to solve a particular problem, you get an award from a university, or a CS-centric professional organization like the ACM or IEEE. Perlin got an Academy Award for this noise function. As in, the Oscar kind of Academy Award.  For an algorithm, something not usually consider artsy.  I found that interesting.

Anyways, rather than dive into Perlin's impenetrable description of how the algorithm works, I set out to find an existing JavaScript implementation. That let me to this message board, and specifically this example.

Unfortunately that implementation has some pretty serious directional artifacts:

Note the horizontal and vertical stripes.  There's almost an upside down cross in the lower right. SAAAATAAAAN!

Rather than try to fix that source code (which the author apparently closureized (making it very difficult to understand)) I kept searching.

From the main Wikipedia entry on Perlin noise, I ran across a variant called Simplex noise.  This is an improvement on the original algorithm, also written by Ken Perlin, in 2001.  That Wikipedia page linked to a paper by Stefan Gustavson(pdf) that explains both classical and Simplex Perlin noise in a much easier to grok way than anything I've read by Perlin himself.  I highly recommend Gustavson's paper if you found Perlin difficult.

I took the Java source code in Gustavson's paper and ported it to JavaScript, and the results are here on github.

I ran some performance comparisons between the classical and Simplex algorithms, and for 2-D I only saw a ~10% improvement with Simplex.  Granted, the latter is supposed to be faster in higher dimensions (classical is O(N^2) vs. simplex O(N) where N is the number of dimensions) so it doesn't matter much for my purposes.

Classical Perlin noise

Simplex Perlin noise

Subjectively I think I prefer the Simplex noise to classical, so I'll probably go with that for Art Evolver.

Again, the source code is here.

4 comments:

  1. Thank you for sharing with good, useful, helpful review. If you are looking for cheap insurance quotes, it necessary to know that when you get cheap house insurance, you save much more on rates from home insurers.

    ReplyDelete
  2. Hi, Sean -

    I'm using your code for 2D simplex noise in JavaScript and trying to get it to reproduce something like the image you have posted above. I can get noise, but it is very pixelated, with none of the larger scale features you have above.

    All I am doing is creating a blank image data, setting each pixel to rgba(255,0,0,1.0), and running each pixel through the noise function. I set noise = (noise+1)/2 to bring it back to a [0,1] range and multiply it by the r channel and the alpha channel.

    Clearly, I'm doing something wrong. Would you be willing to share the code you used to generate the simplex photo? I'm happy to share my own, but won't poison your blog with it unasked.

    /ejt

    ReplyDelete
  3. Classic perlin noise is O(2^n) complexity and simplex perlin noise is O(n^2) complexity. Definitely not O(n) :)

    ReplyDelete
  4. Thank you for sharing some good, useful, useful comments. If you're looking for cheap insurance quotes, it is necessary to know, when you get cheap home insurance, you save more about rate from insurance companies.
    jerseys cheap

    ReplyDelete