Archive for January, 2009

Cube to Sphere Terrain Projection

Because a few people who read the blog/website have asked about how to convert a cube into a sphere when creating planets, I have decided to write this entry.

Let me just outline the goal of this post:

We want to create a planet mesh, which we can render with LOD, Culling and it should be straight forward to place objects on the ground (trees, buildings etc. etc.)

Usually when rendering terrains, I find people tend towards using Quadtree Spatial Partitioning.  This is a very good method, but it is limited in that the terrain (or plane) it partitioned along 2 axis’ only, e.g the X and Z axis (Quadtrees are explained in the post here).  The difference for us is that we will then need to define 6 quadtrees, one for each side of a cube, which means orientating each plane differently (depending on which side of the cube they are, their local X and Z axis’ will be pointing in different directions in world space). By using several Quadtrees, we will have gained the ability to use LOD when rendering, and we can also then cull all the nodes which are not visible by the camera.  We can also insert objects easily into quadtrees, and by providing the proper quadtree index (in the [0,5] range), we can specify on which side of the planet the objects are.

But just using quadtrees doesn’t actually solve the problem completly, as we still need to convert the cube to a sphere – but this part is quite easy, as you are about to see.

Part I – Defining the six quadtree sides, and creating the cube.

// Creates the planet faces.
public void BuildPlanet()
{
// Calculate the max LOD based on the radius of the planet.  For a planet the size of earth,
// the liLODMax is calculated to 46.
int liLODMax = (int)Math.Log((float)((2.0f * Math.PI * m_fRadius) / 4.0f), 2);// Now calucate the size of each cube (planet face).  We will use this variable when defining the world space

// coordinates of the vertices.
int liCubeSize = m_iLODMax * 2;
int liHalfCube = m_ liCubeSize / 2;

// Create and build quadtree face #0
//                                 cWorldNode(int index, int maxLOD, cWorld parent)
m_Faces[0] = new cWorldNode(0, liLODMax, this);// Now call the function which will create the actual mesh data for this quadtree/planet face.

//        Game game - the current instance of the game class
//        Vector3 orientation - This vector defines which side of the planet cube this quadtree should represent.
//            Two of the components should be 0, and the other component should be liHalfCube;
//              Vector3 localX - The 'direction' of the local X axis in world space.
//              Vector3 localZ - The 'direction' of the local Z axis in world space.
m_Faces[0].BuildParentNode(Game, new Vector3(0, 0, liHalfCube), new Vector3(m_ liCubeSize, 0, 0), new Vector3(0, m_ liCubeSize, 0));

// Create the other 5 planet faces /* code removed for space */

}

So, you should be able to see from the above code, that we have just created the first Quadtree plane for the positive Z-Axis of the cube.  This will of course need to be done another 5 times for the other sides, but this should be no problem.

The next part (part II) takes place within the BuildParentNode() function, and it is here that we actually create the mesh, assign texture coordinates, weights etc. (and where we will transform the cube to a sphere).

Part II – Terrain Node Creatation

/// <summary
/// Builds the parent node information for this quadtree face.  The actual terrain mesh is generated in this function.
/// Note that for child nodes, there is a separate function, BuildChildNode().
/// </summary>
/// game is the current instance of the XNA game class.
/// centre is the centre of the planet face (on one of the cube edges).
/// dx is the direction of the X-Axis in local 'terrain space'.
/// dy is the direction of the Y-Axis in local 'terrain space'.
Public void BuildParentNode(Game game, Vector3 centre, Vector3 dx, Vector3 dy)
{

/*  code removed for vertex buffer generation*/

// Define the grid size.  i.e. the number of vertices in a grid (16x16)
int liGridSize = 16;
int liGridSizePlus = 17; // liGridSize + 1

// loop through and create a grid of vertices.
for (int u = 0; u <= liGridSize; u++)
{
for (int v = 0; v <= liGridSize; v++)
{
// Create the vertex grid around the centre of thecube face (which is passed into the function as Vector3 centre).
Vector3 tempPosition = centre + (dx / liGridSize) * (v - liGridSize / 2) + (dy / liGridSize) * (u - liGridSize / 2);

// This is where we would define the height of the vertex.
lfHeight = 0;

// Project the vertex onto the sphere, taking into consideration the height of the
// vertex and the radius of the planet.  By specifying 0 as the height, we will
// get a 'perfectly' round planet/sphere.
m_vVertexPositions[liGridSizePlus * u + v] = SurfaceVectorToCoordinates(tempPosition, m_Parent.Radius, lfHeight);

/* code removed for space */
/* Assign texture coordinates and weights etc*/
}
}

/* code removed for space */
/* build the vertex buffer and create a bounding box for this terrain node */
}

/// <summary>
/// Transforms a vector from the surface of a cube, onto the surface of a sphere.
/// </summary>
/// surfacePos is the vertex position on the cube.
/// radius is the radius of the planet.
/// height is the height of the terrain at this position.
public static Vector3 SurfaceVectorToCoordinates(Vector3 surfacePos, float radius, float height)
{

// Create a return veriable.
Vector3 loReturnData = surfacePos;

// Get a unit vector ( this will 'point' in the correct direction, from (0,0,0) to
// the position of the vertex on the sphere ).
loReturnData.Normalize();

// Add the planet radius and the height of the vertex, and return the vector.
return loReturnData *(radius + height);
}
A lot of code has been removed from the above function, but it should now at least be clear how I have created the planets in Britonia.

Have fun!

// Creates the planet faces.
public void BuildPlanet()
{
// Calculate the max LOD based on the radius of the planet.  For a planet the size of earth,
// the liLODMax is calculated to 46.
int liLODMax = (int)Math.Log((float)((2.0f * Math.PI * m_fRadius) / 4.0f), 2);// Now calucate the size of each cube (planet face).  We will use this variable when defining the world space

// coordinates of the vertices.
int liCubeSize = m_iLODMax * 2;
int liHalfCube = m_ liCubeSize / 2;
// Create and build quadtree face #0
//                            cWorldNode(int index, int maxLOD, cWorld parent)
m_Faces[0] = new cWorldNode(0, liLODMax, this);// Now call the function which will create the actual mesh data for this quadtree/planet face.

//        Game game – the current instance of the game class
//        Vector3 orientation – This vector defines which side of the planet cube this quadtree should represent.
//            Two of the components should be 0, and the other component should be liHalfCube;
//        Vector3 localX – The ‘direction’ of the local X axis in world space.
//        Vector3 localZ – The ‘direction’ of the local Z axis in world space.
m_Faces[0].BuildParentNode(Game, new Vector3(0, 0, liHalfCube), new Vector3(m_ liCubeSize, 0, 0), new Vector3(0, m_ liCubeSize, 0));
// Create the other 5 planet faces /* code removed for space */
}

8 Comments

Noise Part II (CPU)

Well, here is the second part of the noise articles. In this article, I’ll first post the 3d noise code which I have started to use to produce my 3D perlin height map textures, and then I’ll post some functions for using the perlin noise The results can be used for a handful of things, including height maps, procedural textures and 3d textures (for skyboxes etc.).

In order to actually use a Perlin noise function, we need a pseudo-random number generator. In the following code, an array is create in the function Init() which produces a set of random numbers which we’ll use for this purpose. Using these random numbers, and depending on the input to the function (which can be 1d, 2d, 3d …) we can control the data returned from the function.

Here is the complete C# 3d Perlin noise code (converted from Ken Perlin’s Advanced Noise Code here):

You can now read my tutorial for 3D Perlin Noise here

public static class c3DPerlinNoise
{
    private static Random rand;  // Tables for Perlin noise permutations
    private static int[] ms_perm = new int[256];
    private static int[] ms_p = new int[512];

    /// Static constructor.  This is needed to create the static instance of
    /// the random class with our seed.  static c3DPerlinNoise()  {  Init();  }
    /// (Re)-Initialises the noise functions.  Can be used to recreate the
    /// noise function with a different seed.

    public static void Init()
    {
        rand = new Random(GalaxisBase.AnswerToUniverse);

        int nbVals = (1 << 8);  // set values as "unused"

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

        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];
    }

    /// x - The first component
    /// y - The second component
    /// z - The third component
    private static double iNoise(double x, double y, double z)
    {
        int  X = (int)Math.Floor(x) & 255,
        Y = (int)Math.Floor(y) & 255,
        Z = (int)Math.Floor(z) & 255;

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

        // compute fade curves for each x,y,z
        double u = _fade(x);
        double v = _fade(y);
        double w = _fade(z);

        // get the hash coordinates of the 8 cube corners.
        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;

        // Add blended results from 8 corners of cube.
        double returnValue = _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))));

        return returnValue;

    }

    /// Smooth interpolation parameter
    private static double _fade(double t)
    {
        return (t * t * t * (t * (t * 6 - 15) + 10));
    }

    /// Linear interpolation
    private static double _lerp(double t, double a, double b)
    {
        return (a + t * (b - a));
    }

    /// Gradiant
    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));
    }
} // end class

Ok, there’s a fair bit of code there, and quite a few functions. The main function you’ll use is iNoise(), which as you can see, accepts the 3d input (coordinates for instance), and should produce a result in the [-1,1] range.

The other functions (_grad(), _fade() and _lerp()) are all ‘utility’ functions, which are used to blend the results, to ensure we get nice transitions between similar input values.

We could just call this function and get the 3d noise value for a given x,y,z coordinates, but it would be better if we call the inoise function several times (each called an octave), and we can ‘control’ the output a little. For example:
public static double Noise3D(double x, double y, double z, float octaves, float persistence, float gain) { double sum = 0; float amp = 0.5f; float freq = 1.0f; // Add finer and finer ‘hues’ of smoothed noise together for (int o = 0; o < octaves; o++) { sum += SmoothNoise(x * freq , y * freq , z * freq ) * amp; freq *= persistence;
amp *= gain; } //Return the result return sum; }
This will produce noise with x amount of octaves. The persistance changes how the coordinates are sampled in the noise, and the amplitude effects the output of the iNoise function. The gain is used to amplify the output (so we can create really sharp heightmaps etc.)
We can also create ridgeMF and fBm noise as follows:

// Ridged multifractal
// See "Texturing & Modeling, A Procedural Approach", Chapter 12
private static double ridge(float h, float offset)
{
h = abs(h);
h = offset - h;
h = h * h;
return h;
}
// Ridged multifractal
public static double ridgedmf(double x, double y, double z, int octaves, float persistence, float gain, float offset)
{
double sum = 0;     // The return result
double freq = 1.0; // Sample the first octave at normal frequency.
double amp = 0.5; // Reduce the amplitude per octave of noise
double prev = 1.0;
for(int i=0; i<octaves; i++)
{
double n = ridge(inoise(x*freq, y * freq, z * freq), offset);
sum += n*amp*prev;
prev = n;
freq *= persistence;
amp *= gain;
}
// Return the result
return sum;
}

/// Fractal Sum
public static double fBm(double x, double y, double z, int octaves, float persistence, float gain)
{
double freq = 1.0f;  // Sample the first octave at normal frequency.
double amp = 0.5f; // Reduce the amplitude per octave of noise
double sum = 0;      // The return result
for(int i=0; i<octaves; i++)
{
sum += inoise(x.X*freq, y.Y * freq, z.Z * freq)*amp;
freq *= persistence;
amp *= gain;
}
// Return the result.
return sum;
}

n.b. this code came from GPU Gems II Implementing improved Perlin noise on the GPU.
And that’s it! As an idea of something you could try, I am currently trying to improve the star field textures of the skybox. Using this function, it should be possible to define 6 voxel grids in a cube shape, then using the each coordinate as 3d noise input, I should be able to make nice transitions of nebulae which ‘wrap’ around the skybox textures, leaving no visible seems. Well, that’s the dream!

Leave a comment