Creating a Planet : Geometry

I have wanted to expand on my previous post regarding ‘Cube to Sphere Projection’ for a while now, so in this article I am going to cover how I define the spherical geometry of the planets in more detail.

You can read the previous article here.

To be honest, I wasn’t very happy with details of the last post and I’ve wanted to expand on it ever since. The idea was to give people who wanted to work on a planet renderer enough information to make a start on their own project with ideas for the basic planet geometry. As previously mentioned, my planets are based on quad trees which are orientated around the planet center to form a cube (therefore 6 quad trees are required, one for each cube face). My LOD is then based on the distance of the camera to the particular node. This is slightly contrary to ‘traditional’ quadtrees which are usually split based on a number of objects assigned to a particular node.

There are many different implementations for both flat and spherical terrains (more information), but I find this method my favorite because of the ease of working with the different nodes of the quad tree; knowing that the size of a node is n^2+1 means texturing is easily accomplished and finding specific vertices in the grid becomes trivial. In this article I’m going to cover the planet geometry again, albeit in more detail.

Quad trees:
Quad trees can be a huge help in optimizing terrain rendering. The basic idea is that we want to define a series of bounding boxes which contain parts of the terrain at different scales, which get progressively smaller (each node will be 1/4 the size of its parent node). We can use the bounding boxes to check which parts of the terrain are visible, starting at the root (the largest BB) and recursively calling the children all the way down to the tree leafs where all our geometry and sceneobjects lie.

Implementation :
We start by defining the root node of the tree which encompasses the entire area of the terrain (remember we are working with a 2d plane now – so this can be done the XZ axis). Each node has four child nodes (which can be null in the case of the leaf nodes) and a bounding box volume which defines the extents of the node along each of the two axis. It can also be beneficial to store the center point of each node, which I’ll come to later.

The general flow goes like: starting with the root node, subdivide it to produce 4 children of equal size which fit within the current BB and pass in the new bounding information from the root node to each child. This subdividing of nodes happens ‘n’ number of times. n can be either a predefined depth variable for how many levels the quadtree will have, or a minimum amount of objects allowed in a node. Once we subdivide down to this depth level we have reached a leaf node. The leaf node should contain the terrain geometry and possibily a collection of sceneobjects within its bounding volume.

One representation of a quadtree would be:

Rendering this terrain now only requires one call the draw function on the root node, where a bounding box check will be done with the camera view frustum. If the BB is within or even partially within the frustum we call the draw function of each of the children in the tree. This happens right down the tree until a leaf node is reached. Once at the leaf node, we know it is visible by the camera and so we can render the terrain mesh and the sceneobjects attached to the node.

This can save a lot of work; imagine that for a high level node which isn’t within the camera frustum, we can immediately cull this along with all its children saving all those draw calls. You can also further benefit for the fact that if a particular bb is fully within the camera frustum, you can go straight to the leaf nodes and draw them, saving on furter BB.Intersection() calls.

Using quadtrees can also narrow down the amount of work needed between scene object interactions because each scene object is assigned to the node within whos bounds they lie. When it comes to doing things like collision checks then you only need check each object with the other objects in the same node.

Storing the scene objects and the terrain mesh in the leaf node isn’t the only way to do this as you could also store them in each of the nodes at different depths (like chunked LOD). But as there are many ways of doing this, your implementation will depend greatly on what you want to achieve.

Defining the Planet Geometry
The above example of the quadtree works quite well for traditional terrains but for the purpose of creating a planet we need to actually define the spherical geometry based on a cube. This means defining the cube first and then transforming the vertices to form a sphere. In order to do this and make sure the LOD is sufficent to get down to one meter at surface level we need to calculate the size of the cube.

This is done using a binary logarithm of the radius of the planet, taking the gridsize of each node into account. A binary logarithm will tell you by what power or exponential you need to raise a base number to get the desired number. (or simply put, how many times must I subdivide a number to get to two). This is easy to work out:

float _iRadius = 32;
int _iMaxLOD = (int)Math.Log2(iRadius * 2.0f);

This function will tell us that we need to subdivide a cube of size 64 (radius = 32), six times to get to a resolution of two (meters);

The only problem now is that 6 will subdivide the cube down to a resolution of 2 – but what if the patch grids have a size of 32^2? This would mean the resolution of the vertices on the surface would actually be a lot smaller than our desired 1 meter. To correct this we simply take the binary logarithm of the gridsize (n^2) and subtract it from _iMaxLOD. Luckily, these LOD functions only need to be called when initialing the planets, so we don’t really need to worry about performance.

Defining a cube of vertex Grids:
Defining a cube using quadtrees isn’t particually hard once you get used to it, but it can be a pain getting the orientation of the cubes quite right. Each of my terrain patches has a buildMesh() function which, when called, generates a grid of vertices around a center position on a given plane. The individual planes are very important as they will define which quadtree belong to what cube size. The function looks similar to:

private void BuildMesh(Vector3 centerPos, Vector3 axisX, Vector3 axisZ)
{
    // temp array for demonstraion
    VertexPositionTextureNormal[] vertices = new VertexPositionTextureNormal[width*height];

    int index = 0;
    for(int u = 0; u < height; u++)
    {
        for(int v = 0; v < width; v++)
        {
            vertices[index].Position = new Vector3(centerPos + (axisX / width) * (v - width / 2) + (axisZ / height) * (u - height / 2));

            index++;
        }
    }
}

Calling this function 6 times passing in the correct local orientations should produce a cube made up of 6 grids of vertices like this, where the red denotes the local X axis and the blue denotes the local Z axis. The back faces are missing in the diagram:

Based on the size of the cube which we calculated above, you should ensure that when defining a quadtree cube face, at least one component is equal to CubeSize / 2, and that the other two components are CubeSize. This will help created a closed cube.

Making the World Round:
Projecting the vertices from a cube out to a sphere is very easy. Consider the following diagram and the instructions to see how to do this:

1) Center the cube on zero (0,0,0).
2) Normalize each vertex in the grid. This will create a unit sphere.
3) Multiply the vertex position by the radius of the planet + the height of the terrain at this point, which will scale the sphere to the desired dimensions of your planet.

and all this convets to a simple function:

private Vector3 GetWorldSpaceCoordinate(Vector3 cubePos, float height)
{
    cubePos.Normalize();
    return cubePos * _fRadius + height;
}

The height above can come from a variety of sources. I use 3d perlin noise in a number of shaders which render the heightmaps for each patch to several rendertargets of varing sizes. I then use the corresponding texture values are coord U,V to get the height for the terrain grid at X,Y. As long as the size of the rendertarget matches the patch nodes this seems to work fine.

Following the above instructions, you should be able to generate spheres which resemble the following image:

LOD Selection:
As with everything else, there are numerous methods for calculating when to split each quadtree node into smaller pieces. I don’t think this has to be particularly complicated to get good results. One thing I would suggest though is splitting the nodes of the quadtree based on the distance from the camara to the center of the closest edge on the bounding box. Using calculations which depend on the distance of the camera from the center of the node can cause huge differences at higher LOD levels when the camera is stradling the borders of nodes.

Other Little bits:
Of course this article only outlines the way I have defined planet mesh geometry and there are still many things left to do after this. Here are a few of the many things needed to get this geometry resembling a planet:

CPU heightmaps – I wrote this article to describe how to generate heightmap textures using the CPU.

GPU heightmaps – the same again, just adapted to work on the GPU

Real Scales and Imprecision – If you want to create realistically scaled planets, you will inevitably encounter issues with 32-bit imprecission which I discuss a little in this article.

Depth Buffers – This is another important issue when using realistic scales because all that distance between planets wont fit correctly into a 16-bit / 32-bit depth buffer.