The Transvoxel Algorithm

The Transvoxel Algorithm is a method for seamlessly stitching together neighboring triangle meshes generated from voxel data at differing resolutions so that level of detail (LOD) can be used with large voxel-based datasets such as volumetric terrain in next-generation video games. The algorithm was invented by Eric Lengyel in 2009 and implemented in the C4 Engine. This web page provides a high-level overview of the Transvoxel Algorithm, links to additional information, and data tables that can assist in an implementation.

Patent status

The Transvoxel Algorithm is free of patent claims.

The problem it solves

Voxel-based terrain systems are increasing in popularity because they remove the topographical limitations of conventional elevation-based terrain systems and provide the ability to create more complex structures like caves, overhangs, and arches. Triangle meshes are typically generated from voxel data using the Marching Cubes algorithm, and the larger numbers of triangles that it generates makes a level-of-detail (LOD) system even more important for high-performance rendering of large terrains. A natural way to implement level of detail for voxel-based terrain is to simply triangulate the voxel data at multiple resolutions, but this leads to the well-known problem of cracks forming along the boundary between meshes representing different resolutions, as shown in Figure 1. While it is relatively simple to patch these types of cracks in a robust manner for elevation-based terrain, the topographical freedom allowed by voxel-based terrain makes the patching process vastly more difficult because the structure of edge mismatches on the boundary plane can be much more complex. The Transvoxel Algorithm introduces the concept of a “transition cell” to smoothly and seamlessly connect voxel terrain meshes across multiresolution boundaries. The algorithm is designed so that only local voxel data is required for each transition cell, and this allows fast retriangulation in cases where the voxel data is dynamically changing in a real-time application.

(a)	(b)	(c)	(d)
Figure 1. Triangle meshes for adjacent voxel terrain blocks are rendered at two different resolutions near a cave entrance. (a) Cracks are visible along the boundary between the blocks, allowing the sky in the background to show through, and a large hole appears where the terrain surface is nearly tangent to the boundary plane between the blocks. (b) A wireframe is overlaid to show the triangles generated by Marching Cubes. (c) The surfaces of differing resolutions are seamlessly joined by triangles generated for transition cells using the Transvoxel Algorithm, which follows in the footsteps of Marching Cubes but operates on an alternate arrangement of voxels at the boundary between cells of different resolutions. (d) The wireframe overlay reveals the triangles corresponding to the transition cells.

How it works

Figure 2. These are the 73 equivalence classes into which the 512 possible transition cell cases fall.

The Transvoxel Algorithm works by inserting special transition cells in between regular cells along the boundary between voxel data sampled at one resolution and voxel data sampled at exactly half that resolution. Instead of considering all possible combinations of voxel state for both the full-resolution and half-resolution data at a transition boundary, which would require that approximately 1.2 million cases be handled, we consider only nine samples of the high-resolution data. This gives us a much more manageable 512 cases to handle, and these cases happen to fall into the 73 equivalence classes shown in Figure 2. Every transition cell is filled with one of these triangle patterns in order to perfectly fill the seams, cracks, and holes that appear between meshes of different resolutions, as was done for the cave in Figure 1.

In Figure 2, black dots represent voxels that lie inside solid space, and corners without a dot represent voxels that lie outside in empty space. Green triangles are front-facing polygons, and red triangles are back-facing polygons.

See large PDF version

Get print version (18 × 24 inch wall poster)

Look-up tables

Like the Marching Cubes algorithm, the Transvoxel Algorithm is efficiently implemented using a set of look-up tables that provide information about each of the 512 possible cases that can arise. These tables are not easy to generate, so I am providing the tables that I made in the following repository. There are comments in the .cpp file that describe what the numbers mean.

Transvoxel data tables on GitHub

For more information

• Eric Lengyel’s Dissertation, University of California at Davis, 2010. This dissertation goes into great detail about the Transvoxel Algorithm and multiresolution voxel terrain in general. It also describes how the algorithm can be efficiently implemented.

  Download PDF document (50.7 MB)

• Lengyel, Eric. “Transition Cells for Dynamic Multiresolution Marching Cubes”. Journal of Graphics, GPU, and Game Tools. Vol. 15, No. 2 (2010), A K Peters.
  DOI: 10.1080/2151237X.2011.563682

• A complete implementation of the Transvoxel Algorithm is included with the C4 Engine.

How to cite the Transvoxel Algorithm

Please cite the dissertation in which this algorithm was originally described:

Lengyel, Eric. “Voxel-Based Terrain for Real-Time Virtual Simulations”. PhD diss., University of California at Davis, 2010.