Welcome to the first post in a series of articles about our terrain engine. The dynamic and destructible terrain is a huge feature of our Upvoid Engine and deserves some explanation.

The current plan for this series is as follows:

• Part 1 - Dual Contouring (this article)
• Part 2 - Volume Generation and the CSG Tree
• Part 3 - Chunk-based Octree and Level-of-Detail
• Part 4 - Chunk Transition Stitching
• Part 5 - Physics Integration
• Part 6 - Mesh Post-Processing
• Part 7 - Multi-Material and Volume Metadata

Volumes and Voxels

Our vision of the terrain of a dynamic sandbox game includes a lot of destruction, construction, modification and creative freedom. Such terrain is not novel, there have been a lot of approaches in the past achieving differing degrees of expressive power. Wikipedia has a short article about destructible environment. While multiple first person shooters have predefined parts of the terrain that can be destroyed (e.g. Battlefield), games like Worms feature mostly unrestrained terrain modification. Some games even have this as a core gameplay feature such as Terraria or Minecraft.

Predefined destruction is not that challenging to implement as the designer or artist can manually flag all regions that can be modified. When the number of possible modifications is too high to be feasible for manual flagging, other techniques are required. One of the easier techniques is heightmap terrain, where the terrain is represented by a height value for each xy-coordinate. Normally, these values are stored in a grid-like manner. Within the heightmap approach, a lot of problems can be resolved neatly: Mesh generation is just one quad for each grid cell with four $$(x, y, height)$$-coordinates; Level-of-Detail can be implemented by coarsening the grid when further away, transitions just generate triangle(-fans) instead of quads. Terrain modification is simply achieved by altering the height values. Advanced toolkits such as Terragen produce high quality heightmaps and a lot of games use heightmap levels (albeit often static, e.g. in Skyrim). Below is an image of a simple (flat-shaded) heightmap in Blender:

So, why don't we use heightmaps when nearly all problems have easy solutions? - Because their expressive power is limited to 2D. Heightmaps are great for large outdoor areas but it is impossible to express caves, stacks or natural archs. Generating and modifying a full 3D environment is quite vital for games that include mining, so we need a more potent approach. This is where voxels come in. Voxels represent full 3D volume data and are therefore able to represent arbitrary terrain. Minecraft for example takes the simplest approach to voxels: A simple space partitioning into cubes where each cube has exactly one material (including air). This results in the well known "blockiness" of Minecraft:

Marching Cubes

Voxels do not have to be cubes. One of the most famous algorithms in computer graphics is the so called Marching Cubes algorithm published in 1987. The underlying data structure is a 3D grid, but the material is not stored in each grid cell (as in Minecraft) but in each grid vertex. Therefore, each grid cell has exactly 8 neighboring grid vertices with materials. We now want to extract a surface mesh that we can render efficiently. For that purpose we categorize our materials into air and non-air. Having eight neighbors, we get $$2^8 = 256$$ topologically different cases. Accounting for symmetry we can categorize them into the following 15 configurations (Image taken from wikimedia):

Every cube results in zero to four triangles. If some kind of density values are available, we can also interpolate between grid edges and move the triangle vertices according to the interpolation to achieve a better (as-in less jagged) terrain appearance. However, there are some caveats when implementing Marching Cubes. As we ultimately end up using Dual Contouring and not Marching Cubes, we won't go into further detail here.

The original Marching Cubes assumes smooth density values and results in smooth, organic surfaces like these:

There are some problems with the original approach. First, Level-of-Detail is not that easy to implement because it will introduce a lot of "cracks" between LOD-transitions. One extension to Marching Cubes that addresses this is the Transvoxel algorithm. Another problem is that sharp features like hard edges or corners cannot be reconstructed and will lead to jagged appearances. A possible solution is given by the Extended Marching Cubes algorithm. A third problem arises in the multi-material case together with densities: If a density below zero means "inside" and above zero "air", then how are transitions between materials defined? We could just use material indices but that will always result in jagged material transitions as the density field was the only means to "smoothen out" the terrain. Solving all these problems makes the terrain generation unnecessary complex while the density field inevitably restricts our expressive power that we want to preserve.

Hermite Data and Dual Contouring

The technique we ended up using is called Dual Contouring (PDF). This algorithm works on so called hermite data. In a strictly mathematical sense, the presence of hermite data means that you not only know the function values at given points but also all partial derivatives of the function. For our practical case, we only need the first partial derivatives in x, y, and z direction - which is called the gradient. A little more mathematical background: the surface that we want to extract from our volume data can be seen as the isosurface of a given scalar-valued function (often called the density function). From differential calculus we know that the gradient is always perpendicular to the isosurface and therefore the gradient can be seen as the normal vector of the surface.

Back to our data structure: When we say that we store hermite data then this means the following data:

• Material indices at grid vertices (e.g. stone, grass, or air)
• Surface intersection and normal on every edge that has a material change.

The per-edge data can be expressed as a simple vec4 $$(n_x, n_y, n_z, t)$$ with $$n = (n_x, n_y, n_z)$$ being the normal and $$mix(p_0, p_1, t)$$ being the intersection point ($$p_0$$ and $$p_1$$ are the absolute positions of the grid vertices of the edge). A 2D example of this is the following hermite data of a terrain corner: (from left to right: hermite data, marching cubes result, dual contouring result)

Now this is how Dual Contouring works: Instead of choosing the mesh vertices on grid edges and generate triangles inside of grid cells (Marching Cubes approach), we generate exactly one so called feature point per grid cell. (Small optimization: if the grid cell is completely "inside" or "outside", we don't need to generate the feature point) Those feature points can be seen on the rightmost image in the above gallery. After generating those points, we iterate over all grid edges that contain a material change from opaque to non-opaque (e.g. from "grass" to "air"). Each such edge generates one quad whose vertices are the neighboring feature points (In the 2D case, we generate one edge from the neighboring feature points).

That's it. One quad per material-changing edge results in a watertight surface mesh. (For surface experts: the mesh is not necessarily 2-manifold)

How does Dual Contouring solves all those problems mentioned for Marching Cubes?

• Feature sensitivity:
  The choice of the feature point greatly affects the quality of the surface. As the hermite data represents tangent planes on each material-changing edge, we can choose the feature point as the point with the least quadratic distance to all neighboring tangent planes. This results in sharp edges where sharp features lie (e.g. the corner in the above gallery). Always using the cell mid as a feature point results in Minecraft-like surfaces.
• Level-of-Detail:
  When using multiple grids with differing resolutions (we assume they are aligned and their resolution differ by a power of two) transition handling is quite easy. We can simply iterate over the edges of the finer grid and take the feature points from the coarser one where the finer grid ends. This way, the quads may degenerate into triangles but no cracks are visible.
• Multi-Material:
  In our hermite data structure, the multi-material case is already included as we store material indices per grid vertex.

Finally, take a look at some additional screenshots:

The gallery below shows the choice of feature points. In the first row, the feature points are calculated by averaging the intersection points which results in smooth-only surfaces. In the second row, all feature points are set to the mid of their cell, resulting in Minecraft-like terrain.

Level-of-Detail transition can look like this:

Feature sensitivity is most distinct and visible when cutting hard edges into the terrain:

This concludes the first part of my "Terrain Engine" series. The next article will focus on how we actually generate the Hermite Data in an intuitive manner suitable for real-time evaluation while maintaining as much expressive power as possible.

The second article ("Volume Generation and the CSG Tree") can be found here.