int main(void)
{

My Blog

Posted 01/04/12 @ 8:18pm - By Ross

Bring the noise

Well it started with my RoadBuilder class and my research into procedural generation. There was one thing I kept on seeing during my research and that was noise generation techniques. In particular, Perlin noise.

So what, you may ask, is Perlin noise? To answer this, we must first look at what noise is. Conceptually, noise can be thought of as random looking numbers that can be consistently generated based off input. Rereading that it sounds a little cryptic so think of it this way. If I give you a number, you can give me a random number that corresponds to that number. Here is a theoretical chart that would represent a input corresponding to an output:

1 : 22
2 : 8
3 : 34
4 : 3
5 : 16

An input of 1 would correspond to an output of 22, an input of 2 corresponds to an output of 8, etc. The output of this magic function appears to be random, but whenever you give me 1, you get 22 back. That magic function is a noise generating function. So the question of what that magic function might look like probably comes to mind, and that’s where we get into Perlin noise.

Disclaimer: This section contains
Math

Perlin noise was created by Ken Perlin for the movie TRON way back in the day. He wanted a way to add inconsistencies into the visual elements yet have it be controllable. What he came up with set the foundation for a lot of graphics work today.

There’s nothing particularly special about Perlin noise. It is simply one way, among many, for creating noise. It just has the legacy and adoption among most graphical developers. It relies on a few fairly complex principals I’ll try to break down here (for 2D).

  1. Suppose you have a grid over the viewable area of a screen. You can pick a point (or pixel on a screen) and it will reside in a quadrant in that grid.
  2. That quadrant has 4 corners and this is where the randomness comes into play.
  3. Suppose you have 4 vectors pointing off in seemingly random directions at each of those 4 corners. The trick is that you need to be able to reproduce these vectors if they are accessed again. These vectors are called the gradient.
  4. You then have a set of 4 vectors that point from each corner to the original point that resides in the quadrant.
  5. Now we need to know how the gradients effect the vectors pointing at the original point. This is done by taking the dot product of each of the two vectors at each of the 4 corners
  6. We are left with 4 values that we must average, and this is where the ease function comes into play.
  7. The ease function is used to skew the result to give a smoother looking noise. Without the ease function, we’d get noise that looks like a bunch of little squares everywhere.
  8. There are two ease functions, the Hermite curve  3p^2 - 2p^3 which was traditionally used but has a nonzero 2nd derivative. The newer, and better choice, is the Quintic function 6t^5 – 15t^4 + 10t^3 which does have a zero 2nd derivative.
  9. Using this function with the 4 values we calculated on step 6 results in our final value.
  10. Since 2 of the 4 values sit on the same y value, we first calculate the x average. Taking the bottom two corner results we can take the greater and subtract the lesser and pass it to our ease function. We then do the same with the top two corner results.
  11. After we have the x average calculated we are left with 2 values that represent the difference in the y direction. Doing what we did in step 10, we plug in the difference into our ease function to finally end up with our total weighted average. This is our final result.

Obviously visuals help a lot with this, but there is a fair amount of information and documentation you can find online so I’m not going to go too in depth. Suffice to say, this just sums up the process.

This also only covers a 2D example. This algorithm is exponential, O(2^n), so as you add dimensions the complexity in terms of code and running time both start to increase pretty dramatically. As a result, doing anything more than 4D calculations with the traditional Perlin noise algorithm isn’t recommended. But fear not! simplex has come to save the day!

I’m not gonna bother summing up the simplex algorithm (Perlin’s was complicated enough). But it has the benefit of running in linear time (polynomial in some cases). Regardless, it’s considerably faster than exponential and a much better choice for 4D+. Here are a couple examples (programmed in GLSL) of what Perlins and simplex look like. In each case they use the same code, the only difference is the noise generation.

Perlin Noise
Perlin Noise

Simplex NoiseSimplex Noise

Post a Comment

Your email is never published nor shared. Required fields are marked *

*
*

return 0;

}