## XNA Shader Programming – Tutorial 25, Perlin Noise using the GPU This tutorial will intruduce you to procedural textures. If you ever want to generate textures procedurally, you probably stumble upon the Perlin Noise algorithm created by Ken Perlin in 1983.

Why noise?

If you are trying to model natural textures like grass, grain, wood, marble, clouds (+++), you want the textures to contain some irregularity to avoid making the texture look too repeating or perfect. This can be done by using pseudo-random numbers (PRN). You also want to have control over the PRN when using them in your texture generators, so your output won’t be different every time you run your program, or every frame.

Perlin Noise does this. It’s an algorithm that generates a real PRN for every point in space in the range –1 to 1, and it’s controllable (if you know the seed that generates the pattern you want, you can get the same pattern later). The values that the Perlin Noise function returns changes smoothly when moving from a point P1 to another point P2.

Perlin Noise can be used in many other situations as well, like generating landscapes (Minecraft is using this to generate the landscape), fractals, vertex displacements and so on. It’s also used in movies like Tron, LOTR and A Perfect Storm.    Ken Perlin himself has written an article on generating Perlin Noise on the GPU. This article can be found in the book GPU Gems 1, and another one in GPU Gems 2. You can read them for free online here:

This implementation is based on this and another tutorial found here: http://re-creationstudios.com/shared/PerlinNoiseGPU/, but converted to XNA 4.0.

The algorithm

The algorithm can be learned from the presentation “Making Noise” by Ken Perlin at GDCHardCore on Dec 9, 1999.

Noise can be used in any space Rn. You input a coordinate, and it returns a PRN-value for that coordinate. The Noise function is defined on a regular grid, where each grid point is a whole number. When you feed the input coordinate, the algorithm will look at each of the surrounding 2n grid points. The grid points are located on the grid corners (whole numbers), and the point  P is the fraction, somewhere between the grid points. At each surrounding grid point, you select a “random” gradient vector. The same gradient vector must be used for the same grid-point every time, and have the length of 1. Also, we need the vectors from each grid point to point P, let’s call them gP: By performing the dot product on the gradient vectors and gP, we can find out how much each of them is affecting point P.

Then you interpolate between all of the values computed above to get the final value for point P. If you are in 3D space R3, you will have 8 surrounding grid points, and 7 interpolations to get the final value. The first thing that we need is a pre-computed table containing the values 0 – 255 in random order, in two dimensions. This is used to generate one or more PRN at every point P.

We also need a table of gradients. We are implementing noise over R4, and thus needs 16 gradients points.

These will have to be generated on the CPU during loading, as it’s not possible to do it on the GPU with XNA. Also, as these are arrays, and XNA doesn’t support arrays in the shaders, we pass them to our shader as textures.

The shader then use these textures to calculate noise.

Implementaion

First, we create the lookup table for the permutations, and the gradients. Start by creating a new class named PerlinNoise and define it as the following:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Microsoft.Xna.Framework.Graphics;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics.PackedVector;

namespace NoiseGPU
{
public class PerlinNoise
{
GraphicsDevice device;

public PerlinNoise()
{
}
}
}

Then we define our two tables as local variables to the class:

// permutation table
static int[] permutation = new int;

{
{1,1,0},
{-1,1,0},
{1,-1,0},
{-1,-1,0},
{1,0,1},
{-1,0,1},
{1,0,-1},
{-1,0,-1},
{0,1,1},
{0,-1,1},
{0,1,-1},
{0,-1,-1},
{1,1,0},
{0,-1,1},
{-1,1,0},
{0,-1,-1}
};

Notice that the permutation table is empty. We calculate this in a function named InitNoiseFunction(int seed). This function takes in a seed (so we can get the same result next time we run the application), and generates our permutations.

public void InitNoiseFunctions(int seed, GraphicsDevice device)
{
this.device = device;

Random rand = new Random(seed);

// Reset
for (int i = 0; i < permutation.Length; i++)
{
permutation[i] = -1;
}

// Generate random numbers
for (int i = 0; i < permutation.Length; i++)
{
while (true)
{
int iP = rand.Next() % permutation.Length;
if (permutation[iP] == -1)
{
permutation[iP] = i;
break;
}
}
}
}

Now that we got our two tables ready, we can start creating our textures so we can pass the tables in to our shader:

public Texture2D GeneratePermTexture2d()
{
Texture2D permTexture2d = new Texture2D(device, 256, 256, true,
SurfaceFormat.Color);
Color[] data = new Color[256 * 256];
for (int x = 0; x < 256; x++)
{
for (int y = 0; y < 256; y++)
{
int A = perm2d(x) + y;
int AA = perm2d(A);
int AB = perm2d(A + 1);
int B = perm2d(x + 1) + y;
int BA = perm2d(B);
int BB = perm2d(B + 1);
data[x + (y * 256)] = new Color((byte)(AA), (byte)(AB),
(byte)(BA), (byte)(BB));
}
}
permTexture2d.SetData<Color>(data);
return permTexture2d;
}

{
Texture2D permGradTexture = new Texture2D(device, 256, 1, true,
SurfaceFormat.NormalizedByte4);
NormalizedByte4[] data = new NormalizedByte4[256 * 1];
for (int x = 0; x < 256; x++)
{
for (int y = 0; y < 1; y++)
{
data[x + (y * 256)] = new NormalizedByte4(gradients[permutation[x] % 16, 0],
}
}
}

These two functions simply maps the tables into two textures. The first one generates a 2d table of 256×256 PRN values, and returns an output similar to the image below: The other functions takes the gradients from our array, and store the directions as colors into a 16×1 sized texture. Its output is similar to the image below: Now, over to our shader. I added a new Effect file to the project and changed the vertex shader to look like this:

float4x4 World;
float4x4 View;
float4x4 Projection;

{
float4 Position : POSITION0;
float2 texCoord : TEXCOORD0;
};

{
float4 Position : POSITION0;
float2 texCoord : TEXCOORD0;
float4 wPosition: TEXCOORD1;
};

{

float4 worldPosition = mul(input.Position, World);
float4 viewPosition = mul(worldPosition, View);
output.Position = mul(viewPosition, Projection);
output.wPosition = mul(input.Position, World);
output.texCoord = input.texCoord;

return output;
}

It’s out of the box with two exceptions, the texture coordinate and a new variable named wPosition, simply the world position of the vertex. This will be used as the input point P to our noise algorithm (the point P we talked about in the theory section).

Next, we need our two textures and their samplers:

texture permTexture2d;

sampler permSampler2d = sampler_state
{
texture = <permTexture2d>;
MAGFILTER = POINT;
MINFILTER = POINT;
MIPFILTER = NONE;
};

{
MAGFILTER = POINT;
MINFILTER = POINT;
MIPFILTER = NONE;
};

Should be know to you by now. Next, we create a few helper functions:

{
return t * t * t * (t * (t * 6 – 15) + 10);
}

fade(..) is the interpolation function we are using to interpolate through the grid points. This function is f( t ) = 6t5 – 15t4 +10t3

float4 perm2d(float2 p)
{
return tex2D(permSampler2d, p);
}

perm2d simply grabs the permutation value at point P.

{
}

gradperm compute the inner product of the gradient vector, and the vector from the point P to the grid-coordinate.

Then we create the algorithm itself.

float inoise(float3 p)
{
float3 P = fmod(floor(p), 256.0);    // FIND UNIT CUBE THAT CONTAINS POINT
p -= floor(p);                      // FIND RELATIVE X,Y,Z OF POINT IN CUBE.
float3 f = fade(p);                 // COMPUTE FADE CURVES FOR EACH OF X,Y,Z.

P = P / 256.0;
const float one = 1.0 / 256.0;

// HASH COORDINATES OF THE 8 CUBE CORNERS
float4 AA = perm2d(P.xy) + P.z;

// AND ADD BLENDED RESULTS FROM 8 CORNERS OF CUBE
return lerp( lerp( lerp( gradperm(AA.x, p ),
gradperm(AA.z, p + float3(-1, 0, 0) ), f.x),
lerp( gradperm(AA.y, p + float3(0, -1, 0) ),
gradperm(AA.w, p + float3(-1, -1, 0) ), f.x), f.y),

lerp( lerp( gradperm(AA.x+one, p + float3(0, 0, -1) ),
gradperm(AA.z+one, p + float3(-1, 0, -1) ), f.x),
lerp( gradperm(AA.y+one, p + float3(0, -1, -1) ),
gradperm(AA.w+one, p + float3(-1, -1, -1) ), f.x), f.y), f.z);
}

This functions puts it all together. It first makes a unit cube around the point and the coordinates of the cube. It then computes the face curves for each axis of the point. Then we interpolate Last, we create the PixelShader function:

{
float3 p = input.wPosition;
float inz = inoise(p)*0.5+0.5;
return float4(inz,inz,inz,1);
}

technique PerlinNoise
{
pass Pass1
{
}
}

The only thing that needs an explanation here is the inx variable. As the noise is in the –1 to 1 scale, we need to change this in to a 0 to 1 scale. It’s done by multiplying the value with 0.5 and adding 0.5 to it.

Implementing our application

Now, let’s take this into use. Nothing should be new in this code.

using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Audio;
using Microsoft.Xna.Framework.Content;
using Microsoft.Xna.Framework.GamerServices;
using Microsoft.Xna.Framework.Graphics;
using Microsoft.Xna.Framework.Input;
using Microsoft.Xna.Framework.Media;
using Microsoft.Xna.Framework.Graphics.PackedVector;

namespace NoiseGPU
{
/// <summary>
/// This is the main type for your game
/// </summary>
public class Game1 : Microsoft.Xna.Framework.Game
{
GraphicsDeviceManager graphics;
SpriteBatch spriteBatch;
Model meshObject;
Matrix projection, view;
Effect perlinNoiseEffect;

Texture2D permTexture2d;

PerlinNoise noiseEngine = new PerlinNoise();

private void DrawModel(Model m, Matrix projection, Matrix view)
{
Matrix[] transforms = new Matrix[m.Bones.Count];
m.CopyAbsoluteBoneTransformsTo(transforms);

foreach (ModelMesh mesh in m.Meshes)
{
foreach (Effect effect in mesh.Effects)
{
effect.CurrentTechnique = perlinNoiseEffect.Techniques[“PerlinNoise”];
effect.Parameters[“permTexture2d”].SetValue(permTexture2d);
effect.Parameters[“World”].SetValue(transforms[mesh.ParentBone.Index]);
effect.Parameters[“View”].SetValue(view);
effect.Parameters[“Projection”].SetValue(projection);
}
mesh.Draw();
}
}

public Game1()
{
graphics = new GraphicsDeviceManager(this);
Content.RootDirectory = “Content”;
}

/// <summary>
/// Allows the game to perform any initialization it needs to before starting to run.
/// This is where it can query for any required services and load any non-graphic
/// related content.  Calling base.Initialize will enumerate through any components
/// and initialize them as well.
/// </summary>
protected override void Initialize()
{
float aspectRatio = graphics.GraphicsDevice.Viewport.AspectRatio;
projection =
aspectRatio, 1.0f, 10000.0f);

noiseEngine.InitNoiseFunctions(3435, graphics.GraphicsDevice);

base.Initialize();
}

/// <summary>
/// LoadContent will be called once per game and is the place to load
/// </summary>
{
// Create a new SpriteBatch, which can be used to draw textures.
spriteBatch = new SpriteBatch(GraphicsDevice);

foreach (ModelMesh mesh in meshObject.Meshes)
{
foreach (ModelMeshPart part in mesh.MeshParts)
{
part.Effect = perlinNoiseEffect;
}
}

permTexture2d = noiseEngine.GeneratePermTexture2d();

}

/// <summary>
/// UnloadContent will be called once per game and is the place to unload
/// all content.
/// </summary>
{
// TODO: Unload any non ContentManager content here
}

/// <summary>
/// Allows the game to run logic such as updating the world,
/// checking for collisions, gathering input, and playing audio.
/// </summary>
/// <param name=”gameTime”>Provides a snapshot of timing values.</param>
double timer = 0;
protected override void Update(GameTime gameTime)
{
timer += gameTime.ElapsedGameTime.Milliseconds/5000.0;
// Allows the game to exit
this.Exit();

view = Matrix.CreateLookAt(new Vector3(100.0f * (float)Math.Sin(timer), 0.0f, 100.0f * (float)Math.Cos(timer)),
Vector3.Zero, Vector3.Up);

base.Update(gameTime);
}

/// <summary>
/// This is called when the game should draw itself.
/// </summary>
/// <param name=”gameTime”>Provides a snapshot of timing values.</param>
protected override void Draw(GameTime gameTime)
{
GraphicsDevice.Clear(Color.DarkOliveGreen);

DrawModel(meshObject, projection, view);

spriteBatch.Begin(SpriteSortMode.Deferred, new BlendState());
spriteBatch.Draw(permGradTexture, new Rectangle(0, 0, 256, 32), Color.White);
spriteBatch.Draw(permTexture2d, new Rectangle(GraphicsDevice.Viewport.Width-256, 0, 256, 256), Color.White);
spriteBatch.End();

base.Draw(gameTime);
}
}
}

We render a sphere using the noise effect we created, and also render the two textures we are generating.

This entry was posted in Graphics, Tutorial, XNA Shader Tutorial. Bookmark the permalink.

### 4 Responses to XNA Shader Programming – Tutorial 25, Perlin Noise using the GPU

1. bestmotherboardfori74790k.wordpress.com says:

Howdy I am so thrilled I found your weblog, I really found you by error, while I was looking on Yahoo for something else, Nonetheless I am here now and would just like to
say kudos for a marvelous post and a all round thrilling
blog (I also love the theme/design), I don’t have time to look over it all at the minute but I have
2. Amy says: