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 article provides a high-level overview of the Transvoxel Algorithm, links to additional information, and data tables that can assist in an implementation.
Patent statusThe 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.
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.
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 C++ data file. There are comments in the file that describe what the numbers mean.
Download look-up tables (Transvoxel.cpp, 60 kB)
For more information
How to cite this article
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.