Procedural Generation – Textures on the CPU

In this tutorial I’ll be covering how you can use perlin noise and various fractal functions for generating textures either at compile time or run time. This technique can be useful for generating natural looking textures (grass, wood, marble etc.) or heightmaps for your terrains.

The noise function that I’ll cover is implemented as per Ken perlin’s improved noise article here. The full source code is provided at the end of the article, but I have tried to write it as such that you can follow through each step and steadily build up your own XNA 3.1 app.

Generating complicated textures on the CPU is an expensive operation and can stall the application; especially if you attempt to generate large textures at run time – but learning about perlin noise is probably more straight forward on the CPU (as opposed to the GPU). I’ll be covering noise generation on the GPU in a future article.

Step 1 – Setting up the Project:

So let’s set up a new XNA 3.1 project where we can work from:

File->New->Project

Give it a name and make sure you have selected the project type ‘XNA Game Studio 3.1’ and press OK. After the default workspace has been loaded you’ll will be presented with the default project layout.

Before I get into the beef of the article, I’d just like to create the empty classes within the project so you have a view of the overall setup. We will fill these classes in as we run through the tutorial. Right mouse button on the project in the solution explorer (Ctrl+W then S) and create the following files:

Photobucket

We will put all of the perlin noise and fractal functions in the Noise.cs class file. The CreateTexture.cs is where we will define the code for mixing different fractals and producing the actual textures. To make things easier for this tutorial I’ll be creating these two classes as static classes, which means we don’t need to create an instance of the classes to use them, we simply need to call the namespace.class.function() from anywhere in the project and it’ll work.

Step 2 – Exploring Perlin Noise:

First we’ll look at the perlin noise class and go through the implementation that will enable us to produce the textures. Perlin noise can be used to calculate pseudo-random values in any dimension, but the higher the dimension the more it will cost you in terms of performance. Here we’ll be implementing a 3d improved noise basis function which takes 3 variables as input and uses 7 linear interpolations (lerps) per octave to obtain the end result. Although we’ll be implementing 3d perlin noise, we can still use it to create 2d textures by passing in an x and y value and leaving the third component zero.

Perlin noise works by taking input values and returning one pseudo-random value in the range [-1,1]. It does this by using the input values as coordinates in a grid (usually called lattice) of gradient values. Each gradient isn’t cimputed until we have the exact coordinate, but once we find the gradient at a particular coordinate referenced by the input, we can use linear interpolation with this and all its neighbouring gradients in the grid to obtain the apparently random end result. Because we define this lattice of values the same for each instance of the class, we will always get the same output for a specific input.

In order to make sure that we get even further variety, instead of calculating the gradient vector based on the input coordinates directly, we use the input values as a reference into a hash table. The hash table is called the permutation table, and we create it in the class constructor.

As an explanation; while cell indices 0 and 1 may be next to each other in an array of gradients, they will not necessarily be neighbours in the final grid, because 0 and 1 passed through the hash algorthm will return totally different results. To achieve this we define a permutation array which contains the integer values 0 – 255 in a pseudo random order.

It is also important to note that if the permutation table is not the same between different instance of your application (i.e. not constant), you will get different results from the perlin noise function even if you use the same input coordinates for a particular texture. For this reason we will use an instance of the .net Random class with a seeded constructor.

So let’s jump into the code for the Perlin noise. Open up the Noise.cs class file and change the basic class template code to resemble this:

using System;

namespace TextureGeneration
{
    public static class c3DPerlinNoise
    {
        private static Random rand;

        private static int[] ms_p = new int[512];

        // The static class constructor
        static c3DPerlinNoise()
        {

        }
    }
}

Here we just defined a new static class and two static class members. You can see that the permutation table we dicussed above is defined as being 512 in length. Just something to note, static constructors in static classes are run the first time you try and use a function within the class itself.

Now we’ll look at filling up the constructor and creating our tables. Let’s add the following code in the class constructor:

// Create an instance of the random number generator, making sure to pass in a seed.
rand = new Random(42);

// Use the bitwise left shift operator to make sure the array of permutation values is a multiple of 2
int nbVals = (1 << 8); // result is 256
int[] ms_perm = new int[nbVals];

// set values in temp perm array as "unused", denoted by -1
for (int i = 0; i < nbVals; i++)
{
ms_perm[i] = -1;
}

First up we create an instance of the random class, remembering to pass into it the seed. The seed can be any integer or float value, here I just used 42. For those of you unsure of the << operator, it shifts the bits of the right hand value, effectly incrementing it in multiples of 2. This is used here just to make sure we defined the size as being a multiple of 2 (256). Next we defined a temporary array half the size of the final permutation array. We will use this to define the integer values between 0 and 255 in a random order, before copying them to the final permutation array.

Next we must fill the permutation array:

for (int i = 0; i < nbVals; i++)
{
// for each value, find an empty spot, and place it in it
while (true)
{
// generate rand # with max a nbvals
int p = rand.Next() % nbVals;
if (ms_perm[p] == -1)
{
ms_perm[p] = i;
break;
}
}
}

for (int i = 0; i < nbVals; i++)
{
ms_p[nbVals + i] = ms_p[i] = ms_perm[i];
}

Here we iterative though a loop 256 times, and each time we try and find a free position within the temporary permutation table at a random location. This loop ends when all the integer values between 0 and 255 have been randomly placed in the array. The last part of the above code places the temporary permutation values in the final array, and fills it out so we have a full 512 values.

And that’s all for the constructor – pretty painless. We basically end up with a permutation array with 512 cells of mixed up integer values and a static random number generator.

The next step is actually implementing the perlin noise based on what ever input the user provides. The input I am refering to in 3D noise are three seperate values which are typically some sort of coordinate such as the position of a texel or vertex on a terrain etc.

There are three important things to note about the input to the noise function:

1. Integer values will always return zero. You’ll see why this is true later, but basically we use the fraction part of the input as the amount to linear interpolate for the given gradient. Therefore if the input value is an integer then there is no fraction part, and thus the lerp will return 0.
2. Small variations between input values to the noise function will yield small changes in the output values.
3. Large variations between input values to the noise function will yield apparently random output values.

We are counting on all of the above being true in order to produce nice generated textures.

Next up we’ll create the noise function which calculates the gradients and performs the linear interpolation. Create a new static function within the c3DPerlinNoise class with:

private static double Noise (double x, double y, double z)
{

}

The first step in the noise function is to take the input values and work out a coordinate within the lattice of gradient values. We do this by using the integer part of each of the input coordinates (that is, we take the fraction part away from the input components). Because the input values could very well be larger than the permutation array of hash values in any one dimension, we also need to also wrap the input integers and keep the range within [0,255]. Do this with the following code:

int X = (int)x & 255;
int Y = (int)y & 255;
int Z = (int)z & 255;

Now get the fraction part of each of the input values. We will use later as the distance to linear interpolate into each gradient. If you are unsure about the linear interpolation you can check it out here. If you remember the three points we covered about a page back, this is point 2. Add this code:

    x -= Math.Floor(x);
    y -= Math.Floor(y);
    z -= Math.Floor(z);

Uisng what we have seen so far, try to imagine now calling the noise function 30 times using small increments in the input values, say from within two nested for loops. Using the above code, you can see that we work out the lattice gradient using the integer part of the input, and the fraction is used in the lerp calculation. Imagine that the first vector we linear interpolatie on is a vector which is ‘pointing’ straight up. So we carry on incrementing the input values and calling the noise function. Once the incremented input values cross out of this lattice cell and into another cell (when the integer increments), the linear interpolation will be called on a gradient vector which is probably ‘pointing’ in a completly different direction. If the increments of the input values are exactly the same then you will see a noticable seam where the gradient changes.

To try and avoid this we run the fraction parts of the input through a fade curve (s-curve) which will weight the input towards 0 and 1. This is needed to avoid seams in the output texture due to the transitions between lattice cells where the different gradients produce noticable jumps in the output values. We will define the fade function a little later, but for now add this to the noise function:

double u = fade(x);
double v = fade(y);
double w = fade(z);

Before we go on to calculate the gradient value, we need to pass our new integer values into the permutation table to get the hash values (remember, this should mix up the values even further, and help to add variation). We do this with the following code:

int A = ms_p[X    ] + Y, AA = ms_p[A] + Z, AB = ms_p[A + 1] + Z;
int B = ms_p[X + 1] + Y, BA = ms_p[B] + Z, BB = ms_p[B + 1] + Z;

Okay, so this is getting long winded but rest asured we are nearly there. This is the final step and it is where we employ linear interpolation between the gradients. As I said earlier, each extra dimension of noise introduces a performance overhead; this is because of the need to lerp between more surrounding points in the lattice, for 3d noise we must lerp between 7 gradients. The last thing of note here is that we calculate the gradient values using the hash value and the input coordinates:

return lerp(w, lerp(v, lerp(u, grad(ms_p[AA  ], x  , y  , z   ),
                                      grad(ms_p[BA  ], x-1, y  , z   )),
                             lerp(u, grad(ms_p[AB  ], x  , y-1, z   ),
                                      grad(ms_p[BB  ], x-1, y-1, z   ))),
                   lerp(v, lerp(u, grad(ms_p[AA+1], x  , y  , z-1 ),
                                      grad(ms_p[BA+1], x-1, y  , z-1 )),
                             lerp(u, grad(ms_p[AB+1], x  , y-1, z-1 ),
                                      grad(ms_p[BB+1], x-1, y-1, z-1 ))));

This will return a double value by linear interpolating between all the gradient values at this point in the lattice.

Before this will work, we just have three utility functions to define. The first one is the fade curve, which weights the input fractions towards zero and one, to ease the transitions of interpolations across lattice cells:

private static double fade(double t)
{
return (t * t * t * (t * (t * 6 - 15) + 10));
}

The _lerp function (linear interpolation) is pretty straight forward,and returns a double:

private static double lerp(double t, double a, double b)
{
return (a + t * (b - a));
}

The last, and most important of the utility functions is the grad() function, which computes the gradient based on the hash value:

private static double grad(int hash, double x, double y, double z)
{
int h = hash & 15;
double u = h<8 ? x : y;
double v = h<4 ? y : h==12||h==14 ? x : z;

return ((h&1) == 0 ? u : -u) + ((h&2) == 0 ? v : -v);
}

And that is it, at least for the perlin noise part. The above functions can now be used to return a pseudo-random value in the [-1, 1] range for any 3d input, such as terrain vertex positions etc.

Step 3 – Fractals for Interesting Noise:

Okay, with the noise class defined above you may well be thinking that the battle’s almost over – well, not quite. We could (if we hadn’t defined the noise function as private) just call the noise function above and pass in the input coordinates to define a texture of noise. This would result in a texture based on just one octave of noise. But in order to achieve nice results, or rather varied results for a wide variety of textures, we need to use multiple octaves of noise.

Each successive noise function you use for one point of input is known as an octave, and you can use as many or as little octaves as you like in the texture. When we call multiple octaves of noise, we can specify an amplitude and frequency. The amplitude is used to modify the output of the noise function while the frequency modifies the input values for each call to the noise function. The frequency of an octave is usually double that of the previous octave. For this reason, there becomes a point where the frequency of the octaves is too high to be displayed on the screen, so it makes sense to limit the use of octaves.

There is another property which can be used called persistence or lacunarity, which specifies the rate of change of the frequency (of the input) over octaves.

Now we’ll just run through some fractal functions which can be used to create more interesting noise, and which should explain these new terms a little better:

The first fractal function is fractal browian motion (fBm). This is just the weighted sum of multiple scales of an arbiturary basis function (the basis function in our case is improved perlin noise – but the basis could be anything else such as simplex noise)

public static double fBm(double x, double y, double z, int octaves, float lacunarity, float gain)
{
    double frequency = 1.0f;
    double amplitude = 0.5f;
    double sum = 0.0f;

    for (int i = 0; i < octaves; i++)
    {
        sum += noise(x * frequency, y * frequency, z * frequency) * amplitude;
        frequency *= lacunarity;
        amplitude *= gain;
    }
    return sum;
}

You can see that the frequency used to modify the input values is doubled on each iteration of the octaves (I’m assuming here that the lacunarity is 2.0f), while the amplitude is modified based on the gain. The frequency is multiplied with each input variable to the noise function. This function produces textures similiar to:

Photobucket

The next fractal function is Ridged multifractal. It is generated in much the same way as fBm noise, except the output of each octave is modified by an absolute value function. This function is very popular for creating terrain heightmaps, as it produces ridge like features at all scales. The implementation is as follows:

public static double RidgedMF(double x, double y, double z, int octaves, float lacunarity, float gain, float offset)
{
double sum = 0;
float amplitude = 0.5f;
float frequency = 1.0f;
double prev = 1.0f;

for (int i = 0; i < octaves; i++)
{
double n = ridge(noise(x * frequency, y * frequency, z * frequency), offset);
sum += n * amplitude * prev;
prev = n;
frequency *= lacunarity;
amplitude *= gain;
}

return sum;
}

public static double ridge(double h, float offset)
{
h = Math.Abs(h);
h = offset - h;
h = h * h;
return h;
}

The RdgedMF in the source code I have provided produces the following texture:

Photobucket

4. Getting the Project setup to create and display the textures:

We have covered a lot of ground so far, but there is still one thing left to do, and that is to actually create the textures! If you want to go ahead then and open up the CreateTexture.cs file class in the solution explorer and we’ll define the following function in there. First of all setup the class as another static class like this:

using System;
using Microsoft.Xna.Framework.Graphics;
using TextureGeneration.Noise;

namespace TextureGeneration
{
public static class CreateTexture
{

}
}

All the following functions should be created inside this class. Now we’ll justlook at creating a texture which could be used to generate a heightmap from, like in Riemers tutorials (here). Define the following function:

public static Color[] CreatefBmHeightMap(int width, int height)
{
Color[] data = new Color[width * height];
float tempColor;

float x = 0, y = 0, z = 0;

As you may be able to guess, we’ll be filling the Color[] array within the function and we’ll pass it back out at the end. This will later be used to fill a texture2D class instance. The next step is too create a two for loops, one nested within the other. This will enable us to produce a noise value for each texel of a texture (given the width and height):

for (int v = 0; v < width; v++)
{
x += 0.5f;
y = 0;
for (int u = 0; u < height; u++)
{
tempColor = (float)c3DPerlinNoise.fBm(x, y, z, 8, 0.45f, 1.0f);
data[v * width + u] = new Color(tempColor, tempColor, tempColor, 1);

y += 0.5f;
}
}

return data;
}

There are a few things going on here which we need to take note of. The first is that we do not use the integers created by the nested for loops input directly because if you remember, integer values produce 0 as output, so instead we use the x,y and z floats defined locally in the function, and manually increment them. We then go on to use the result of the fBm function to fill all components of a Color struct, producing a black and white image. This should be perfect for a heightmap. The output of this function can be seen above (the fBm sample).

For the Sake of Completness:

We’ll quickly define some code to get the texture up on the screen in your application. This is all pretty basic stuff, so I’m not going to linger on anything. Go back into the Game1.cs class and define a Texture2d member:

private Texture2D _HeightmapTexture;

This will contain the texture that we are to create. In this tutorial we’ll just set the texel data directly with the SetData function.

Now go into the LoadContent() method and add the following code:

_HeightmapTexture = new Texture2D(GraphicsDevice, 512, 512, 1, TextureUsage.None, SurfaceFormat.Color);
_HeightmapTexture.SetData
(CreateTexture.CreatefBmHeightMap(_HeightmapTexture.Width, _HeightmapTexture.Height));

This will create an instance of the Texture2D with the specified size and with a surface format of Color which has 8-bits for RGB and A. The second line fills the texture data with the Color[] array which is created and returned from the CreateTexture.CreatefBmHeightMap() function.

Lastly, go to the draw method and add this line between the SpriteBatch.Begin() and SpriteBatch.End():

_SpriteBatch.Draw(_HeightMap, new Rectangle(10,10,512,512), Color.White);

And that’s that! Press F5 and you should see a fBm noise texture displayed on the screen.

That pretty much concludes the tutorial, I hope you found it interesting!

Now as this was my first tutorial, I would greatly appreciate any comments or criticism about issues, things I may have forgot or any improvements. I look forward to your feedback and I’ll try and use it for my next tutorial (in a few weeks)

You can donwload the sample project here

Making Noise

Thanks,

-John

References:

Perlin’s Improved noise reference

Advertisements
  1. #1 by Gahme on December 25, 2009 - 3:08 pm

    A really cool tutorial, thank you for that.
    I was always really interested in producing procedural cities, so this site gives me alot of information necessary for that (L-System Roads, Procedural Texture Creation)
    In my opinion, this tutorial is pretty good, the only thing I’d improve is maybe not explaining every little detail, like creating a new class. I dont say you have to make expert tutorials, just leave out the real basics, this way you can save time and focus on the actual topic.
    All in all, Im just hoping for more cool articles,screenshots,videos and of course new tutorials 🙂

    -Gahme

  2. #2 by tt on January 8, 2010 - 10:44 pm

    I noticed an error in this..

    On line 14
    result0 = (float)c3DPerlinNoise.fBm(x, y, z, 6, 0.85f, 0.5f);

    doesn’t match the definition of the c3DPerlinNoise.fBm function

    • #3 by admin on January 8, 2010 - 11:20 pm

      Thanks. I have updated the code. The error was in the fBm function itself.

      -John

  3. #4 by Steven Hansen on January 9, 2010 - 11:41 am

    Nice job! Most tutorials I see on this subject avoid looking at the math behind the noise and it’s obvious the author doesn’t really know what’s going on.

    You show a good understanding of the subject matter, and share the reasoning with the reader in a very clear way. The examples are also enlightening as well as relevant.

    –Phoenix

  4. #5 by Philippe Da Silva on January 10, 2010 - 3:45 am

    Hi and thanks for this tutorial.
    I have been working on Perlin Noise to generate Nebulae textures and your article give a great hand 😉
    Now I just need to find out which maths I should apply to tile the texture… Any ideas? :p

  5. #6 by Marco Sperling on January 23, 2010 - 11:45 pm

    Hi John,

    nice to see you making progress and sharing knowledge along the way.
    What XNA site are you frequently browsing since ziggy’s site has been down now for quite some time?

    • #7 by Lintfordpickle on January 24, 2010 - 10:07 am

      Hi. Unfortunately progress has slowed a bit due to lack of time, but I am still working on a few things for Britonia.

      Since ziggys site has been down I usually browse gamedev.net, XNA UK and XNAMAG.de

  6. #8 by Petrocket on February 14, 2010 - 4:26 am

    Thanks for the code! I’m using it to do a ridged fractal noise implementation in glsl.

    Minor optimization on your permutation table generation:

    uchar perm[256];
    // initialize with unique values 0..255
    for(int i = 0; i < 256; i++) {
    perm[i] = i;
    }

    // seed the random number generator
    srand(mSeed);

    // randomize the permutation table
    for(int i = 0; i < 256; i++) {
    // for each value swap with a random slot in the array
    uchar swapIndex = rand() % 256;

    int oldVal = perm[i];
    perm[i] = perm[swapIndex];
    perm[swapIndex] = oldVal;
    }

    That should make it O(n) (or is it O(1) argh!)

  7. #9 by Matan on March 10, 2010 - 4:37 am

    I have to say this looks like a great tutorial, however i’m a bit confused about the grad() function, hopefully you can explain it to me:

    in your grad function you take the hash argument and use bitwise AND with 15 (1111.b). That mean that any number above 15 won’t be used fully, and doing that bitwise AND 15 can also be done on the table since you don’t seem to use the actual hash value for anything else, but rather the result hash value.

    I have to also say I don’t really understand what you did in that function, or rather why. I didn’t found you explaining that function.

    • #10 by Lintfordpickle on March 11, 2010 - 10:51 am

      The hash input value is used to give the input vector a direction (not to change the magnitude), so we only need to use the first few bits. In this implementation it will give a possible 12 directions. This function was taken straight from the reference implementation (linked at the top).

      I guess you are right in that you could put this value directly in the permutation table, when I’ve a little more time I’ll check it. There are also other functions which can be used to calculate the actual gradient, so I’ll look around the net and ad a few more links. (If you have the book ‘Texturing and Modelling: A procedural approach, it talks about ways to do this).

  8. #11 by Matan on March 11, 2010 - 2:38 pm

    Thanks you for your comment.

    I have to say I searched the net and didn’t found much, but I don’t know much about the subject like you, so I might of found it and didn’t know it was that.

    I don’t have the book you mentioned, but I’ll look into it.

    Also, if you have the time, I would love if you could comment or explain the grad function you currently have, all of it. The other parts of it are not understandable to me either.

    And by the way, great article! It helps understand perlin noise (most of it), and it’s the best one I could find, so thanks!

  9. #12 by Michael Lindholm on April 1, 2010 - 12:58 am

    Hi mr Lintfordpickle 🙂

    We have talked before on Ziggyware, and you see on my link here that I’m the guy behind the Liero3d projekt 🙂

    Anyway, I don’t know if i mentioned it the last time, but the reason i started working in XNA, and started with 3D, was so that i could write a planet-to-surface engine one day, and when i finally decided to start on the project, I found your tutorials on the subject extremely useful 🙂

    So i wanted to give you a big -thank you- for all your great work on these Tutorials, and i of course hope to see more of them on your page in the future 🙂

    Also, i think you made a good choice when moving your project to a space-themed game, as it opens up for more options with a space-to-surface engine 🙂

    take care

  10. #13 by Byron Nelson on June 2, 2010 - 5:17 pm

    Dear John,

    Any chance you can check the filehost for the source code link? It reports that the file is not available, and I’d really like to get my hands on it.

    Best,
    Byron

  11. #14 by Lintfordpickle on June 2, 2010 - 6:45 pm

    Hi Byron,

    I’ve hosted it on my SkyDrive for now:

    http://cid-109c9e6c1fce824a.skydrive.live.com/self.aspx/.Public/TextureGeneration.7z

    I’ll look over the weekend and sort out all the broken-links. If you need any thing else, just give me a shout.

    -John

  12. #15 by Blackley1 on July 17, 2010 - 5:51 am

    Hey just a comment to those than dont want to download the SLN to get the proper looking RidgeMF you need to change the code to move the X and Y by

    x += 0.005f;
    and
    y += 0.005f;

    and a good starter data is

    8 Octaves
    2.85 Lacunarity
    .45 gain
    1.0 offset

    and thats all you need to get the RidgeMF working . . . Hope this helped i needed to downlaod the entire project just to get those points!

  13. #16 by Jay on July 30, 2010 - 11:26 pm

    Great tutorial

    and thanks Blackley1, that is the only thing I would consider is missing from the tut.

    I look forward to reading more!

  14. #17 by Mike on December 2, 2010 - 3:08 am

    Hi John, It looks like your download link is no longer working. I went through the effort of filling in the form and getting the link from my email, and when I finally clicked download the site told me the file was unavailable… 😦

    Can you please update your link?

    Thanks.

  15. #18 by Mike on December 2, 2010 - 3:10 am

    Okay, I just noticed you’ve posted a new link in the comments.
    I’ll use that one 😉

    Might be worth updating your article, though.

    Nice tutorial, by the way.

  1. Creating a Planet : Geometry :

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: