XNA Shader Programming – Tutorial 25, Perlin Noise using the GPU

image

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:

http://developer.nvidia.com/content/gpu-gems-part-i-natural-effects
http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter26.html

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.

image

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.

image

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.
image

Also, we need the vectors from each grid point to point P, let’s call them gP:

image

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.

image

 

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[256];

// gradients for 3d noise
static float[,] gradients = 
{
    {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;
}

public Texture2D GeneratePermGradTexture()
{
    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],
                                                                                         gradients[permutation[x] % 16, 1],
                                                                                         gradients[permutation[x] % 16, 2], 1);
        }
    }
    permGradTexture.SetData<NormalizedByte4>(data);
    return permGradTexture;
}

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:
image

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:
image

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;

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

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

VertexShaderOutput VertexShaderFunction(VertexShaderInput input)
{
    VertexShaderOutput output;

    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;
texture permGradTexture;

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

sampler permGradSampler = sampler_state
{
    texture = <permGradTexture>;
    AddressU  = Wrap;       
    AddressV  = Clamp;
    MAGFILTER = POINT;
    MINFILTER = POINT;
    MIPFILTER = NONE;
};

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

float3 fade(float3 t)
{
    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.

float gradperm(float x, float3 p)
{
    return dot(tex1D(permGradSampler, x), 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 Smilefjes

Last, we create the PixelShader function:

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

technique PerlinNoise
{
    pass Pass1
    {
        VertexShader = compile vs_3_0 VertexShaderFunction();
        PixelShader = compile ps_3_0 PixelShaderFunction();
    }
}

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;
        Texture2D permGradTexture;

        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[“permGradTexture”].SetValue(permGradTexture);
                    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 =
                Matrix.CreatePerspectiveFieldOfView(MathHelper.ToRadians(45.0f),
                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
        /// all of your content.
        /// </summary>
        protected override void LoadContent()
        {
            // Create a new SpriteBatch, which can be used to draw textures.
            spriteBatch = new SpriteBatch(GraphicsDevice);
            meshObject = Content.Load<Model>(“sphere”);
            perlinNoiseEffect = Content.Load<Effect>(“perlinNoiseEffect”);

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

            permTexture2d = noiseEngine.GeneratePermTexture2d();
            permGradTexture = noiseEngine.GeneratePermGradTexture();

            // TODO: use this.Content to load your game content here
        }

        /// <summary>
        /// UnloadContent will be called once per game and is the place to unload
        /// all content.
        /// </summary>
        protected override void UnloadContent()
        {
            // 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
            if (GamePad.GetState(PlayerIndex.One).Buttons.Back == ButtonState.Pressed)
                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);

            // TODO: Add your update logic here

            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.

Download: Source (XNA 4.0)

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

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

  1. Pingback: XNA Shader Programming – Tutorial 26, Bump Mapping Perlin Noise | digitalerr0r

  2. Pingback: Windows Client Developer Roundup 070 for 5/23/2011 - Pete Brown's 10rem.net

  3. 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
    saved it and also added in your RSS feeds, so when I have time
    I will be back to read much more, Please do keep up the fantastic job.

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