Dual Contouring: Seams & LOD for Chunked Terrain

There was a mistake in the original version of this post, the second last selectionFunc was a duplicate of the previous entry in the table. The table has now been corrected. Apologies to anyone who was tearing their hair out trying to debug that one!

Introduction

A couple of years ago I read these blog posts (1, 2) on 0 FPS, and like a lot of programmers decided I should write one of these voxel renderers. I implemented Marching Cubes first, but I was unhappy with the way terrain looked using MC -- it was far too blocky. I then implemented Naive Surface Nets and was pleased that I now had smooth terrain, but I soon discovered that Surface Nets couldn't support sharp features, like a 90 degree angle. That meant it would never be possible to have both a smooth terrain and a realistic looking building produced by the Surface Nets algorithm. I was aware of Dual Contouring from the 0 FPS posts, and my main source of information Miguel Cepero's Procedural World blog. Dual Contouring sounded like a significant step up in difficulty from Surface Nets, and I was quite skeptical about how feasible it would be to use Dual Contouring in a game. I never tried to upgrade my renderer to use DC and my interest in the project faded.

Then about a year ago, EverQuest Next was announced. Far from using blocky Minecraft style graphics EQN looked like a typical AAA game. I wanted to know how this was possible, and quickly discovered that I already knew -- it was based on the Procedural World project. I realised Miguel was really on to something here, and the next day started on a new voxel renderer. I set myself a goal: learn how this technology worked by creating a Dual Contouring renderer that would be capable of handling large terrains.

It's taken quite a while but I achieved my goal, and my renderer can produce large destructible terrains, like this one:

Early on I ran into one of the major problems with using Dual Contouring to generate terrain. Rather than looking like the finished version in the picture above, my terrain was full of cracks.

Initially I used a nasty hack to work around this problem, and went on with other features. The hack annoyed me and caused a lot of complications. I knew to achieve the final goal I would need to solve the problem properly. The remainder of this post explains the problem in detail and the solution I eventually implemented.

The Problem

It’s not practical to store the entire world as a single entity, attempting to do so with such a large terrain will very quickly lead to poor performance as the size of the data and the time required to process it grows and grows. To work around these performance problems the standard technique is to organise the world space into a grid of equally sized cube chunks. Each chunk is responsible for representing a small part of the world, and can be processed in isolation. Using chunks allows modifications to the terrain to be processed quickly, and provides a starting point for building a Level of Detail (LOD) system.

In order to create the mesh for the terrain, each chunk is responsible for generating a mesh which represents the terrain inside the chunk’s bounding box. To generate the mesh an octree is constructed. The first stage in the octree generation is to evaluate each 1x1x1 cube, or voxel, which exists inside the chunk’s bounds. If any of the voxels is determined to contain the surface of the terrain then a leaf node of the octree is generated, with each leaf node containing a single vertex of the terrain mesh. Once all the leaf nodes are created the octree is constructed upwards until the root node (which has the same bounding box as the chunk) is created. The octree can then be traversed (or contoured) to produce the mesh for each chunk.

I then ran into the problem: there were cracks in between the individual meshes I had generated. I was a bit confused by this: I had organised the terrain into chunks, with each chunk generating a mesh. There are no gaps between the chunks, so why were there cracks in the mesh?

I often find the easiest way to think through a problem is to consider the simplest case possible. Here the problem is cracks appearing in the terrain, so I’ll use the simplest terrain possible to think through the problem. The simplest terrain is a flat plane, e.g. height(x, z) = 100, which will generate a flat plane along the x and z axes through the points where y = 100. It looks like this:

Using this flat plane terrain makes thinking about the problem easier. We can essentially think about the problem in 2D, with quadtrees instead of octrees. Each chunk can then be imagined something like this:

The thick black line represents the chunks' bounding box. The thin grey lines represent the leaf node, with the red circles representing the vertices belonging to the nodes.

When the mesh is generated each chunk , and so each octree, is considered in isolation. The generated meshes will then look like this:

Triangles are generated by connecting the leaf nodes' vertices

The Solution

The cracks in between the meshes are caused by the contouring each chunk's octree without considering the neighbouring octrees. In order to fill in the cracks these nodes would need to be contoured as part of the same octree.

Nodes which contribute to the seams are highlighted blue

Again using the flat plane terrain as a model, we can imagine the chunks in the world laid out like a grid. Each square in the grid also contains another smaller square, representing the mesh. In order to render the terrain properly, all the cracks between the chunks need to be filled in, creating a seam. Ideally each chunk would be responsible for a small part of the seam which would allow the global problem of the cracks to be localised, with each chunk handling a piece of the seam. This would mean that the advantages of the chunked approach (reducing the size of data sets, enabling parallelisation, etc) would not be lost while solving the cracks problem the chunks introduce.

A grid of chunks. The black line represents the chunk bounding box, and the green squares represent the mesh

After a few false starts, I realised there was a way to organise the seam for the flat plane which would allow all the cracks to be removed while also keeping the generation of the seam a responsibility of each chunk.

If you imagine a sort of L shape being attached to each chunk then the gaps between the mesh will all be removed, without any overlapping being introduced:

A seam is added for the bottom left chunk.

By having each chunk generate and be responsible for a small piece of the seam, a full mesh for the terrain can be created and managed without adversely affecting performance.

To generate the seam for each mesh we need to first collect all the nodes which could possibly contribute to the seam. I think the easiest way to manage this is to construct the seam on the maximum faces & edges of the chunk’s bounding box. We need to consider the chunk itself and the seven neighbouring chunks which share a face or an edge. In order to avoid creating overlapping meshes we need to ensure that only nodes which contribute to the seam are selected. Going back to the flat plane terrain again, we can work this out.

First we need to select any nodes in the chunk which have either the maximum x, y, or z value which matches the chunk’s own maximum x, y, or z value.

Leaf nodes are selected from the chunk

Next from each neighbour we need to select the nodes which are adjacent to the original chunk. For the chunk which is adjacent on the x axis this would be any node which has a minimum x value equal to the maximum x value of the original chunk:

Leaf nodes from the X-axis neighbour are selected

Then for the Z axis:

Leaf nodes from the Z-axis neighbour are selected

And finally the X and Z axes:

A single leaf node is selected from the X & Z axes neighbour

This process can be extended to three dimensions and 7 neighbours, each with a relevant selection criteria. I often find code easier to understand than descriptions. This is C++11.

vector<OctreeNode*> FindSeamNodes(Chunk* chunk)
{
  const ivec3 baseChunkMin = chunk->getMin();
  const ivec3 seamValues = baseChunkMin + vec3(CHUNK_SIZE);

  const ivec3 OFFSETS[8] = 
  { 
      ivec3(0,0,0), ivec3(1,0,0), ivec3(0,0,1), ivec3(1,0,1), 
      ivec3(0,1,0), ivec3(1,1,0), ivec3(0,1,1), ivec3(1,1,1) 
  };

  auto selectionFuncs[8] =
  {
    [&](const ivec3& min, const ivec3& max) 
    { 
      return max.x == seamValues.x || max.y == seamValues.y || max.z == seamValues.z;
    }
    
    [&](const ivec3& min, const ivec3& max) 
    { 
      return min.x == seamValues.x; 
    }
    
    [&](const ivec3& min, const ivec3& max) 
    { 
      return min.z == seamValues.z; 
    }
    
    [&](const ivec3& min, const ivec3& max) 
    { 
      return min.x == seamValues.x && min.z == seamValues.z; 
    }

    [&](const ivec3& min, const ivec3& max) 
    { 
      return min.y == seamValues.y; 
    }
    
    [&](const ivec3& min, const ivec3& max) 
    { 
      return min.x == seamValues.x && min.y == seamValues.y; 
    }

    [&](const ivec3& min, const ivec3& max) 
    { 
      return min.y == seamValues.y && min.z == seamValues.z; 
    }
    
    [&](const ivec3& min, const ivec3& max) 
    { 
      return min.x == seamValues.x && min.y == seamValues.y && min.z == seamValues.z; 
    }
  };

  vector<OctreeNode*> seamNodes;
  for (int i = 0; i < 8; i++)
  {
    const ivec3 offsetMin = OFFSETS[i] * CHUNK_SIZE;
    const ivec3 chunkMin = baseChunkMin + offsetMin;
    if (Chunk* c = GetChunk(chunkMin))
    {
      auto chunkNodes = c->findNodes(selectionFuncs[i])
      seamNodes.insert(end(seamNodes), begin(chunkNodes), end(chunkNodes));
    }
  }

  return seamNodes;
}

The selectionFuncs array holds a lambda function that is used to select only the relevant nodes from each chunk’s octree. The findNodes function is quite simple. Due to the octree structure all parent nodes of the seam nodes that are to be selected will also meet the selection criteria from selectionFuncs[i].

void Octree_FindNodes(OctreeNode* node, FindNodesFunc& func, vector<OctreeNode*>& nodes)
{
    if (!node)
    {
        return;
    }

    const ivec3 max = node->min + ivec3(node->size);
    if (!func(node->min, max))
    {
        return;
    }
    
    if (node->type == Leaf)
    {
        nodes.push_back(node);
    }
    else
    {
        for (int i = 0; i < 8; i++)
            Octree_FindNodes(node->children[i], func, nodes);
    }
}

typedef std::function<bool(const ivec3&, const ivec3&)> FilterNodesFunc; 

vector<OctreeNode*> Chunk::findNodes(FilterNodesFunc filterFunc)
{
    vector<OctreeNode*> nodes;
    Octree_FindNodes(octreeRoot, filterFunc, nodes);
    return nodes;
}

Once all the seam nodes have been gathered, a new octree can be created which contains all the seam nodes. The octree is then used to generate a new mesh just as the chunk’s octree was originally. Repeating this process for each chunk ensures that there are no cracks between the chunk meshes.

Four chunk seams have been generated, filling in the cracks

Unfortunately this scheme does introduce a dependency between the chunks. If a chunk modified then its possible that a seam owned by a neighbouring chunk may need to be updated too. Modifications to the terrain are constrained by a bounding box which allows most of these potential updates to be skipped -- they are only necessary when the operation bounding box is near a particular neighbour.

One of the features of the Dual Contouring method is its support for simplifying (i.e. removing triangles) from the extracted mesh. The simplification process is an operation performed on the octree whereby leaf nodes with a common parent are removed and the parent node replaced, creating a new leaf node twice the size of the removed leafs. There are a few different ways I can think of to use the simplification to create different levels of detail, for now I’m using the simplest one I could think of. Each LOD (starting from 0) all existing leaf nodes are removed, and their parents are replaced by new leaf nodes. Each round of simplifcation reduces the polycount farily significantly, which allows for a really basic LOD system. The current detail level for each chunk is calculated based on the distance to the camera, so that as the distance increases the chunks use a more or less simplified mesh.

As a consequence there will be neighbouring chunks with differently sized leaf nodes:

Neighbouring chunks with differently sized leaf nodes

Typically when dealing with voxel-based mesh generation this a tricky problem to solve. If you’re using Marching Cubes you’ll need to use something like the TransVoxel algorithm to be able to stitch the chunk meshes together, for instance. In this case however, we don’t need to do anything different at all -- the Dual Contouring algorithm works with the differently sized leaf nodes in each octree. The process is exactly as before, all the seam nodes of the neighbouring chunks are gathered, a new octree is constructed and the mesh generated. Just as before the seam mesh completely covers the crack without generating any overlapping polygons.

Chunks with different levels of detail are stitched together by the seams