Chunked level of detail.

In my first efforts,  planets were round,  oceans were blue and the land was green which had me pretty excited but failed to bring about any interest from anyone else.  (I'm sure any programmer can relate to this!)

What it needed was more detail.  I wanted to be able to fly in at orbital speeds,  re-enter and land just like in Orbiter.  The first complication was that representing a full sized planet all at once is impossible on current hardware and likely to be impossible for the foreseeable future, planets are just too big.

Taking inspiration from Steven Wittens fantastic blog i decided to have a go at "Chunked LOD"
The paper which describes it can be found here, However I will run through it and describe how I implemented it.

• The concept:

The basic idea is that from a distance you can't see the fine details of the terrain anyway, so a simpler version is displayed instead. When the camera moves closer to the terrain and higher detail is needed, the terrain patch is split into 4 sub patches where each one is one quater the size of the original and those are displayed instead.

This fits nicely into a data structure called a "Quad tree."

Just like any other tree structure, the "Quad tree" is a hierarchy;  A root node at the top which has child nodes who in turn have child nodes themselves.
What makes it a quad tree is that (as the name sugests) each node has 4 children.

 

This fits in perfectly with the previous cube approach to rendering the planet where the six sides of the cube are formed by six terrain parches representing six root nodes, for six independant quad trees.

At each draw call the algorithm starts from the top of the tree and ask the question;

Is the level of detail for this node sufficient?
If Yes: Render this chunk.
If No: Subdivide this node and recurse the test down to the children who may also need to be split.

All working properly it should look like this:

Another great advantage of this approach is that it becomes trivial to implement highly effective culling of nodes which lie outside of the camera's frustum - if a parent node's bounding sphere lies outside of the camera's frustum, then all of it's children do as well. We don't even need to visit them to know they will not need to be rendered.

• The implementation:

I'm just going to show stubs here because the implementation is dependent on the engine/platform so I'll get you to fill out the methods depending on what you need.

As you move further away from the surface, details get harder and harder to distinguish.
Eventually as you move further out into space, entire mountains can take up less than 1 pixel on your monitor and effectively become invisible.
Therefore if you had a low detail version of a terrain and a high detail version - at a certain distance the two meshes become impossible to tell apart.

So the plan is to determine when a terrain patch is far enough away for the difference between it, and a terrain patch of a different level of detail to be invisible, and to then swap it for the other chunk.

By taking into account how far away we are from the mesh, the estimated difference between the two meshes (more on this later) , the field of view of your camera and the size of your monitor it is possible to calculate how big the differences between 2 levels of detail appear on your monitor in screen space.

In the paper I referenced above, this is called the "Sceen space error metric"
In order to provide the position of the camera from the terrain chunk to calculate this metric it made sense for me to pass the camera object in itself since we also need it's bounding frustum for frustum culling.

The other thing necessary for the metric which isn't shown here is the width of the game window itself, how you want to go about providing that is up to you, XNA made this easy in my case by just querying the global GraphicsAdaptor.

The last step is to choose a tolerated error above which the higher quality mesh is rendered instead. This tolerated error needs to be chosen so the detail swap happens before the difference between levels becomes obvious but not so early as to make the whole operation pointless.

class Camera
{
    BoundingFrustum frustum;
    Vector3 Position;

    public BoundingFrustum GetFrustum()
    { return frustum; }

    public Vector3 GetPosition()
    { return Position; }

}

class TerrainMesh
{
    BoundingSphere sphere;

    TerrainMesh()
    {
        GetHeightmap();
        BuildMesh();
    }

    ~TerrainMesh()
    { /*do stuff */}

    private void BuildMesh()
    { /*do stuff */}
    private void GetHeightmap()
    { /*do stuff */}
    public void Render()
    { /*do stuff */}
    public BoundingSphere GetBoundingSphere()
    { return sphere; }
}

As for the quad tree node class, I have filled out the basic recursive structure of the drawing here. Once again I have stubbed out the engine specific details, so fill out the methods as you need.

class QuadTreeNode
{
    QuadTreeNode[] Children;
    TerrainMesh Mesh;

    // If Lod is sufficient draw this chunk otherwise test child nodes.
    void Draw(Camera camera)
    {
        // if the chunk's bounding sphere is either intersecting or contained within the frustum:
        if (camera.GetFrustum().Contains(Mesh.GetBoundingSphere()) != ContainmentType.Disjoint)
        {
            // if this chunk's detail is sufficient then draw it, also now 
            // is a good time to free up some memory by destroying child nodes 
            // since they won't be needed - unless you want to cache them.
            if (LodIsSufficient(camera.GetPosition()))
            {
                Mesh.Render();
                if (ChildrenAreValid()) DestroyChildNodes();
            }
            else
            {
                // if the children have already been created then pass the draw call down.
                if (ChildrenAreValid())
                    foreach (QuadTreeNode chunk in Children) chunk.Draw(camera);
                else
                {   // otherwise we need to construct them.
                    // it's a good idea to do this on another thread to prevent halting the rendering. 
                    // draw this chunk this frame - children should be ready next time, otherwise we will end up back here.
                    ConstructChildNodes();
                    Mesh.Render();
                }
            }
        }
    }

    // Return true if chunk is detailed enough
    bool LodIsSufficient(Vector3 CameraPosition)
    { /*do stuff */ return true; }

    // return true if all children are constructed and ready to be rendered.
    bool ChildrenAreValid()
    { /*do stuff */ return true; }

    // Construct children if they do not already exist.
    void ConstructChildNodes()
    { /*do stuff */}

    // Release all the child's resources and pass the destroy call down to child's children. 
    void DestroyChildNodes()
    { /*do stuff */}
}

The complications to keep in mind:

Remember to define a maximum tree depth to prevent the draw call from creating new children if you are at the maximum detail you want to support.

When it comes to the estimated difference between the best quality mesh and the mesh currently being tested, it is sufficient to guess by starting with some big number ( I chose 2 ^{number of quad tree levels} ) and then just divide it by 2 each time you subdivide the mesh.
The reason this parameter exists, however, is to give you more control if you already have your height-maps in advance.
Imagine a terrain patch representing wide open plains, the high quality mesh is going to be very hard to distinguish from the low quality mesh very quickly because there is very little change in elevation happening.
By calculating a per-chunk difference estimation you can cause the LOD swap to happen much later when it is actually needed rather than at some global setting.
However if your height-maps are procedural like mine then this is not an option.

 The final piece to my solution was to observe that the closer to the planet you get, the more of the terrain is hidden by the planet's curvature and can be culled from rendering.
This was harder in practice due to the fact that while a chunk may lie over the horizon on a perfectly flat sphere, should it contain hills or mountains which poke up above the horizon then it's possible that visible sections of terrain could be erroneously removed.

Solving this involved being more conservative in my culling where I would only prevent a chunk from being drawn if it was over the horizon by an amount more than the maximum possible height assigned by the terrain generator for that chunk.
This led to some chunks making it through when they should have been culled, but that was a better option than having chunks being culled when they should not have. This still feel hackish and it is an area that I will revisit.

Another problem which needed attention was filling cracks that appear in between two levels of detail.
I decided that this was a problem to be solved later, and was not in the scope of my tech demo.  However a good looking solution at this point appears to be storing two levels of detail in each chunk and morphing between the current detail level and the next as the camera moves in.
This solves the ugly popping that happens when a chunk suddenly changed detail level as well as solving the cracking problem as neighboring chunks will also be morphing to fit this chunk.

• Moving forward.

 I added some vertex normals and this is the result.

The planet is still not textured - but regardless it is a massive leap in quality.
So at this point I turn my mind to the other half of my game - modifying my environment.
I wanted free form building, similar to Minecraft, where the player places blocks to create a structure instead of just plonking down prefabricated models on the surface like in spore for example.
In order to support this gameplay, I required a way to to subtract the shape of a block from the terrain robustly without holes in order to support the digging of a foundation as well as tunneling into the ground.
 Suddenly I am feeling very much out of my depth.  This approach doesn't feel like it is going to work anymore.
 Nothing for it but to dive in and find another way.