- About this document

- What is Perlin noise?

- How do you generate Perlin noise?

- Computational complexity

- Speeding it up

- Looping noise

- Seamlessly tiling noise

I wrote a demo program in C++ that includes a Perlin noise texture class, which I hope provides a decent example of C++ code for Perlin noise. You can find the demo at http://www.robo-murito.net/code.html.

If I've made any grave errors or you just want to comment, feel free to email me.

When I talk about a noise function, I mean a function that takes a coordinate in some space and maps it to a real number between -1 and 1. Note that you can make noise functions for any arbitrary dimension. The noise functions above are 2-dimensional, but you can graph a 1-dimensional noise function just like you would graph any old function of one variable, or consider noise functions returning a real number for every point in a 3D space.

These images were all created using nothing but Perlin noise:

Let's look at the 2D case, where we have the function

withnoise2d(x,y) =z,

Now we need a function

which takes each grid point and assigns it a pseudorandom gradient of length 1 ing(x_{grid},y_{grid}) = (g_{x},g_{y})

Also, for each grid point, we generate a vector going from the grid point
to (*x*, *y*), which is easily calculated by subtracting the
grid point from (*x*, *y*).

Now we have enough to start calculating the value of the noise function
at (*x*, *y*). What we'll do is calculate the influence
of each pseudorandom gradient on the final output, and generate
our output as a weighted average of those influences.

First of all, the influence of each gradient can be calculated by performing
a dot product of the gradient and the vector going from its associated grid
point to (*x*, *y*).
A refresher on the dot product -- remember, it's just the sum of the products
of all the components of two vectors, as in

(Since I'm really tired of writing subscripts, we'll just refer to these 4 values asa,b) · (c,d) =ac+bd.

So here's a 3D-ish picture of some influencess=g(x_{0},y_{0}) · ((x,y) - (x_{0},y_{0})) ,

t=g(x_{1},y_{0}) · ((x,y) - (x_{1},y_{0})) ,

u=g(x_{0},y_{1}) · ((x,y) - (x_{0},y_{1})) ,

v=g(x_{1},y_{1}) · ((x,y) - (x_{1},y_{1})) .

Geometrically, the dot product is proportional to the cosine of the angle
between two vectors, though its unclear to me if that geometrical interpretation
helps one visualize what's going on. The important thing to know at this
point is that we have four numbers, *s*, *t*, *u*, and *v*
which are uniquely determined by (*x*, *y*) and the
pseudorandom gradient function *g*.
Now we need a way to combine them to get *noise2d*(*x*, *y*),
and as I suggested before, some sort of average will do the trick.

I'm going to state the obvious here and say that if we want to take an average of four numbers, what we can actually do is this:

- find the average of the first pair of numbers
- find the average of the second pair of numbers
- average those two new numbers together

We're not taking a plain vanilla-flavored average here, but instead, a
weighted average. That is, the value of the noise function should be influenced
more by *s* than *t* when *x* is closer to *x*_{0}
than *x*_{1} (as is the case in the pictures above). In fact, it ends
up being nice to arrange things so that *x* and *y* values behave as if
they are slightly closer to one grid point or the other than they actually are
because that has a smoothing effect on the final output. I know that sounds
really silly, but noise without this property looks really stupid. In fact,
it sounds so silly that I'm going to write it again: *we're going to want
the input point to behave as if its closer to one grid point or another than
it actually is*.

This is where we introduce the concept of the ease curve. The function
3*p*² - 2*p*³ generates a nice S-shaped curve
that has a few characteristics that are good for our purposes.

What the ease curve does is to exaggerate the proximity its input
to zero or one. For inputs that are sort of close to zero, it outputs a number
*really* close to zero. For inputs close to one, it outputs
a number *really* close to one. And when the input is exactly one half,
it outputs exactly one half. Also, it's symmetrical in the sense that it
exaggerates to the same degree on both sides of *p* = ½.
So if we can treat one grid point as the zero value, and the other as the
one value, the ease curve has the exact smoothing effect that just we
said we wanted.

Ok, I've droned on long enough, it's calculation time:
first, we take the value of the ease curve
at *x* - *x*_{0} to get a weight *S*_{x}.
Then we can find the weighted average of *s* and *t* by constructing
a linear function that maps 0 to *s* and 1 to *t*, and evaluating
it at our x dimension weight *S*_{x}. We'll call this average *a*.
We'll do the same for *u* and *v*, and call the result *b*.

The above figures should satisfy you that no matter where *x* happens
to fall in the grid, the final averages will always be between *s* and
*t*, and *u* and *v*, respectively.
Mathematically, this is all simple to calculate:

Now we find our y dimension weight,S_{x}= 3(x-x_{0})² - 2(x-x_{0})³

a=s+S_{x}(t-s)

b=u+S_{x}(v-u)

And there you have it. So all you have to do is call the noise function for every pixel you want to color, and you're done. Probably.

An interesting consequence of all of this is that the noise function becomes
zero when *x* and *y* are both whole numbers.
This is because the vector (*x*, *y*) -
(*x*_{0}, *y*_{0}) will be the zero vector.
Then the dot product of that vector and
*g*(*x*_{0}, *y*_{0})will evaluate
to zero, and the weights for the averages will also always be zero, so
that the zero dot product will influence the final answer 100%. The funny
thing is that looking at the noise function, you would never guess that it ends up
being zero at regular intervals.

The neat thing about noise is that it's locally variable, but globally flat -- so if we zoom out to a large degree, it will just look like a uniform value (zero in fact). So, we don't care if the noise function starts to repeat after large intervals, because once you're zoomed out far enough to see the repeat, it all looks totally flat anyways.

So now we should feel justified in doing a little trick with modulus.
Say we're doing noise in 3D, and we
want to find the gradient for some grid point
(*i*, *j*, *k*).
Let's precompute a permutation table *P*, that maps every integer
from 0 to 255 to another integer in the same range (possibly even the same number).
Also, let's precompute a table of 256 pseudorandom gradients and put it in
*G*, so that *G*[*n*] is some 3-element gradient.

Now,

But on a computer, modulus with 256 is the same thing as a bitwise and with 255, which is a very fast operation to perform. Now we've reduced the problem of a possibly involved function call into nothing but some table lookups and bitwise operations. Granted, the gradients repeat every 256 units in each dimenstion, but as demonstrated, it doesn't matter.g(i,j,k) =G[ (i+P[ (j+P[k]) mod 256 ] ) mod 256 ]

This speedup is also mentioned on Perlin's web page, and is actually used in his original implementation.

Now each function call takes twice as long to calculate, but since you're probably not going to use this cycling technique in real time, it probably doesn't matter.F_{loop}(x,y,z) = ( (t-z) *F(x,y,z) + (z) *F(x,y,z-t) ) / (t)

**The explanation**

Consider
the graph of a noise function *F*(*x*, *y*, *z*) for
some fixed *x* and *y*. The problem is, you want *F*(0) = *F*(*t*)
and there is no guarantee that will be the case with any old *x*, *y*, and *t*.
Actually, since any given *x* and *y* should have no influence on the repeating
aspect of the animation, we can for all practical purposes throw them out while
we're developing our repeating function, and consider the simplified case of
a one-dimensional noise function *F*(*z*).

We need to take this function and change it into one where it is guaranteed
that *F*(0) = *F*(*t*). Here's an expanded view of our
noise function showing its behavior from -*t* to *t*:

Now we define a new function *F*'(*z*) that behaves like *F*(*z*)
when *z* is near zero, but behaves like *F*(*z* - *t*) when
*z* is near *t*. If you think about it, you see that
*F*'(0) = *F*(0), and that
*F*'(*t*) = *F*(*t* - *t*) = *F*(0).
We can do this with a simple linear interpolation by considering a linear function
which is equal to *F*(*z*) at 0, and equal to *F*(*z* - *t*)
at *t*.

High school algebra tells us that this linear function has a slope of

(and an intercept ofrise) / (run) = (F(z-t) -F(z)) / (t- 0) = (F(z-t) -F(z)) /t

Which is basically the same as the function given above. If you look atF'(z) =slope(z) +intercept

= ( (F(z-t) -F(z)) /t)(z) +F(z)

= ( ( (z) *F(z-t) - (z) *F(z) ) /t) +F(z)

= ( ( (z) *F(z-t) - (z) *F(z) ) /t) + (t/t) *F(z)

= ( (z) *F(z-t) - (z) *F(z) + (t) *F(z)) / (t)

= ( (z) *F(z-t) + (t-z) *F(z) ) / (t)

= ( (t-z) *F(z) + (z) *F(z-t) ) / (t)

If you had a little calculus and too much free time, you could prove that
this looping (and the tiling in the next section) is truly seamless:
not only does *F*(0) = *F*'(*t*), but all their derivatives
should match up as well. Which means that no one should be able to tell
where the repeat actually happens.

A pattern should be emerging here, so it shouldn't surprise you that you'll need evaluate a weighted sum of 8 calls to the noise function if you want to have a repeating animation that tiles in the x and y dimenstions. I'm not going to write it out here out of space considerations, and also because it should be evident what the sum will be.F_{tileable}(x,y) = (

F(x,y) * (w-x) * (h-y) +

F(x-w,y) * (x) * (h-y) +

F(x-w,y-h) * (x) * (y) +

F(x,y-h) * (w-x) * (y)

) / (wh)