# ==Transvoxel in practice== <p class="doc-sub">// status: seedling</p> Same-resolution chunks are a data-ownership problem; different-resolution chunks are a topology problem. If one voxel terrain chunk uses cell width <code>h</code> and its neighbour uses <code>2h</code>, their Marching Cubes boundary vertices cannot all line up. The fine side has a vertex wherever an <code>h</code>-sized edge crosses the iso-surface; the coarse side has one opportunity every <code>2h</code>. Independent meshes leave T-junctions, holes, or a visible crack. [[Marching Cubes]] already hints at the answer: add a special triangulation for the boundary instead of pretending the regular cube table can connect two different grids. Eric Lengyel's Transvoxel algorithm is that stitching layer. It is designed for voxel terrain with arbitrary overhangs and caves, where a heightfield-specific skirt or edge stitch is not enough. ## The core idea A Transvoxel mesh has two kinds of cells: - **Regular cells** use the ordinary Marching Cubes table at one resolution. - **Transition cells** occupy the thin band between a full-resolution region and a region sampled at exactly half the resolution. For each transition cell, the high-resolution face is a 3 × 3 grid: nine samples covering the same area as a 2 × 2 group of fine cells. The opposite face has four coarse corners. Those four values duplicate the corner values of the 3 × 3 face; their positions are displaced to the coarse side of the transition cell. Geometrically this gives 13 sample positions, but only nine independent signs. Nine bits produce 512 cases, which Lengyel reduces to 73 equivalence classes with a lookup table. That distinction — 13 positions, 9 independent values, 512 cases — is the detail I most often get wrong on a first implementation. The table is not a normal 13-bit Marching Cubes table. The transition triangles are chosen to meet the fine regular mesh on one side and the coarse regular mesh on the other. The seam is therefore part of the mesh topology, not a strip of geometry hidden behind the terrain. ## Preconditions: make the LOD contract explicit Transvoxel assumes a clean multiresolution layout: 1. A chunk has a resolution level and a cell width. 2. Adjacent levels differ by exactly 2:1 at a boundary. 3. The fine and coarse regions sample one deterministic field. 4. The transition face knows which side is fine and which side is coarse. 5. Each boundary has one owner for transition geometry. The 2:1 rule is usually enforced by balancing an octree or chunk graph: before rendering, refine a chunk if a neighbour would otherwise be more than one level away. Without that rule, one transition cell cannot bridge an arbitrary ratio. A level-0 to level-2 gap needs an intermediate level or several transition bands. The shared field requirement is just as important. If the coarse field applies a different noise filter or evaluates at a slightly different world coordinate, the coarse corner value no longer equals the corresponding fine corner value. The lookup table can only stitch samples that actually agree. See [[Seamless Chunked Voxel Terrain]] and [[Designing Scalar Fields for Procedural Terrain]]. ## Mapping one transition cell Assume a fine chunk borders a coarse chunk on its positive X face. One transition cell spans two fine cells along Y and two along Z. Its high-resolution face samples are: ~~~text fine face (3 × 3) s0 ---- s1 ---- s2 | | | s3 ---- s4 ---- s5 | | | s6 ---- s7 ---- s8 ~~~ The four coarse-side positions correspond to the corners <code>s0</code>, <code>s2</code>, <code>s6</code>, and <code>s8</code>, moved across the seam to the coarse side. Their scalar values are the same corner samples, not four new evaluations. The transition cell is a prism-like volume with a fine, nine-point face and a coarse, four-corner face. The exact axis permutation and winding change for the other five directions. Keep a single face mapping table rather than scattering six versions of the loop through the mesher: ~~~c typedef enum { FACE_NEG_X, FACE_POS_X, FACE_NEG_Y, FACE_POS_Y, FACE_NEG_Z, FACE_POS_Z } Face; typedef struct { Vector3 position[13]; float value[13]; // values 9..12 duplicate four front corners } TransitionSamples; TransitionSamples make_transition_samples(Face face, ChunkCoord fine_chunk, int u, int v, int fine_step, float iso); ~~~ <code>u</code> and <code>v</code> index transition cells over the coarse face, not individual fine cells. For a fine chunk with <code>N</code> cells on a face, there are <code>(N / 2) × (N / 2)</code> transition cells. The helper should construct positions from integer lattice coordinates and a face orientation. Compute the final positions in local coordinates, then apply a camera-relative chunk origin as usual. The displacement between the front and back positions is part of the reference construction. It must agree with how the coarse regular cells are placed; an arbitrary “gap-fixing” offset merely moves the crack. Treat transition width as a layout invariant and test a flat plane before using a noisy field. ## Building the 9-bit case code The case code contains the signs of the nine high-resolution samples. The table's bit order is easy to confuse with the visual sample numbering, so make the mapping explicit: ~~~c static const uint8_t case_bit_for_sample[9] = { 0, 1, 2, 7, 8, 3, 6, 5, 4 }; uint16_t transition_case(const TransitionSamples *s, float iso) { uint16_t code = 0; for (int i = 0; i < 9; ++i) { if (s->value[i] < iso) code |= (uint16_t)1u << case_bit_for_sample[i]; } return code; } ~~~ The array above is for one conventional front-face ordering; a face mapper can rotate or mirror the sample indices so the same table is used for every direction. Confirm it against the ordering used by the official tables you import. The safe invariant is not the names <code>s0</code>…<code>s8</code>; it is that each bit corresponds to the same spatial sample the table generator used. Case <code>0</code> and case <code>511</code> contain no crossing and emit no triangles. Every other code indexes the official transition-class table. Do not regenerate or “simplify” the table by hand unless you are prepared to re-prove its topology. ## What the tables contain Lengyel's reference data is split into a few conceptual pieces: - <code>transitionCellClass[512]</code> maps a nine-bit case to an equivalence class and, for inverse cases, carries enough information to flip winding. - transition-cell data gives the number of vertices and triangles plus the triangle index list for the class. - transition-vertex data says which pair of the 13 sample positions defines each interpolated vertex and includes reuse information for vertices shared with neighbouring transition cells. The official repository is intentionally data-focused. Keep the tables in a generated or clearly isolated source file and keep the algorithm around them small. The data is the specification; a clever rewrite of the lookup is less useful than a test that compares one generated cell against a known case. ## Interpolating and emitting a cell Once the case is known, emission looks familiar: ~~~c static Vertex interpolate_transition_edge(const TransitionSamples *s, EdgeCode edge, float iso) { int a = edge.endpoint_a; int b = edge.endpoint_b; float denominator = s->value[b] - s->value[a]; float t = fabsf(denominator) < 1e-8f ? 0.5f : (iso - s->value[a]) / denominator; t = clamp01(t); return (Vertex){ .position = Vector3Lerp(s->position[a], s->position[b], t), .normal = transition_normal(s, a, b, t) }; } void emit_transition_cell(const TransitionSamples *s, float iso, MeshBuilder *out) { uint16_t code = transition_case(s, iso); if (code == 0 || code == 511) return; uint8_t encoded_class = transitionCellClass[code]; bool flip_winding = (encoded_class & 0x80u) != 0; uint8_t class_index = encoded_class & 0x7Fu; TransitionCellData data = transitionCellData[class_index]; Vertex v[MAX_TRANSITION_VERTICES]; for (int i = 0; i < data.vertex_count; ++i) v[i] = interpolate_transition_edge( s, data.vertices[i], iso); for (int i = 0; i < data.triangle_count; ++i) { TriangleIndex t = data.triangles[i]; if (flip_winding) mesh_add_triangle(out, v[t.a], v[t.c], v[t.b]); else mesh_add_triangle(out, v[t.a], v[t.b], v[t.c]); } } ~~~ The exact struct names and endpoint encoding vary with the table package. Some encodings pack the two endpoint indices and a reuse direction into a 16-bit value. Decode that once in <code>EdgeCode</code>; keep the interpolation and mesh builder independent of the packing. <code>transition_normal</code> should use the same field-gradient policy as regular cells. For a cached grid, interpolate raw gradients and normalise once. For an analytic field, evaluate the gradient at the interpolated position. Matching the triangles but using a different derivative stencil makes a visible normal seam; see [[Normals for Implicit Surfaces]]. ## The face loop When a fine chunk has a coarse neighbour on <code>FACE_POS_X</code>: ~~~c if (neighbour.level == fine.level + 1) { for (int v = 0; v < CELLS / 2; ++v) for (int u = 0; u < CELLS / 2; ++u) { TransitionSamples s = make_transition_samples(FACE_POS_X, chunk, u, v, fine_cell_step, iso_level); emit_transition_cell(&s, iso_level, &chunk_mesh); } } ~~~ Only the fine side needs this transition band. The coarse side emits its regular cells; it must not emit a second copy of the same transition geometry. Give each face a canonical owner — usually the finer chunk when its neighbour is exactly one level coarser — and make the condition part of the chunk graph, not a camera-dependent branch. For negative faces, axis swaps and winding flips are the likely bugs. A useful strategy is to implement one face, test it against a plane and sphere, then derive the other five with a small coordinate transform layer. Do not duplicate the entire extraction algorithm six times. ## Edges, corners, and multiple coarse neighbours A chunk can be fine along one face and coarse along another. At an edge, two transition bands meet; at a corner, three can meet. The 2:1 balance rule limits the combinations, but it does not remove the need to test them. The official vertex-reuse data exists partly so adjacent transition cells can agree on shared crossings. Respect the reuse flags or use a canonical edge key in your own mesh builder. Avoid emitting a transition patch twice because two neighbouring faces both believe they own its edge. A debug material that colours regular cells and transition cells differently makes overlap obvious. Start with one coarse face and one transition band. Add two-face and three-face configurations only after the single-face topology is stable. Otherwise an edge artifact can look like a table error when it is really two correct patches overlapping. ## Normals, materials, and attributes Transition geometry is still part of the same implicit surface. Its vertices should use: - the same iso-level and sign convention; - the same global field and derivative step; - the same material interpolation policy; - the same tangent/normal transform as regular vertices. If a material ID comes from the winning field primitive, use the same sample positions and blend weights on both resolutions. A coarse material lookup that quantises independently can produce a colour seam even when the geometry is closed. For a field with an analytic gradient, compute it in world or canonical field space and transform it once. For a sampled field, make sure the transition cell can read the fine-face halo and the shared coarse corners. A missing sample should fail loudly in debug builds; treating it as zero or air creates plausible but untraceable seams. ## Updating a dynamic terrain A brush edit can affect three layers of work: 1. regular cells in the fine chunk; 2. regular cells in the coarse neighbour; 3. transition cells on their shared face. Queue them as one dependency set. If the edit changes an underlying sample on the shared face, both regular meshes and the transition band may need rebuilding even if the visual brush lies entirely on one side. If the LOD selection changes because the camera moves, rebuild the regular/transition pair together; never display a fine regular mesh next to a new coarse mesh until its transition band is ready. A revision number works here just as it does for same-resolution chunks. Tag a transition job with the revisions of both adjacent chunks and the LOD relationship. Drop the result if either revision or the face relationship changed while it was running. ## Why skirts are still useful A skirt adds a thin strip of geometry below a chunk edge. It is cheap, easy to generate, and often adequate for a heightfield or a prototype. It can hide a gap but does not make the two surfaces agree: the strip may intersect the terrain, cast odd shadows, or become visible from below. It also cannot faithfully stitch caves and arbitrary overhangs. Transvoxel costs more implementation and table plumbing, but the transition triangles describe the actual iso-surface between the two grids. Use a skirt when iteration speed matters and the seam is guaranteed to stay hidden; use Transvoxel when LOD boundaries are part of the visual world. ## A debugging sequence that scales Do not begin with a noisy, edited, six-faced world. Work through fields with known answers: 1. A constant empty field: all cases must emit nothing. 2. A constant solid field: all cases must emit nothing. 3. A plane perpendicular to the transition face: transition geometry should be flat and continuous. 4. A tilted plane: catches axis permutations and winding. 5. A sphere centred on the boundary: catches interpolation and duplicated corner values. 6. A carved cave crossing the boundary: catches arbitrary topology and missing samples. 7. A moving camera that changes the LOD selection: catches stale transition jobs and ownership races. Render the regular mesh wireframe and transition mesh in different colours. Add a line for every transition cell's 13 positions. If the four back positions do not coincide with the coarse grid corners in the expected coordinate system, stop there; no table can fix a coordinate mismatch. ## Things that tripped me up - **Counting 13 signs** — a transition cell has 13 positions but only nine independent scalar values. The lookup table is 9-bit and has 512 cases. - **Using the diagram's sample order as bit order** — the table's case bits are a spatial convention, not necessarily the left-to-right labels in my code. Keep an explicit mapping and verify one asymmetric case. - **Bridging an arbitrary LOD ratio** — Transvoxel's table assumes a 2:1 transition. Balance the chunk graph or insert intermediate levels. - **Re-evaluating duplicated coarse corners** — the four coarse-side values duplicate front-face corners. Sampling a separate coarse field can move the seam. - **Wrong face orientation** — one negative axis often has a reversed winding or swapped U/V axes. Test all six faces with a tilted plane. - **Emitting both sides** — only the fine side owns the transition band. Two transition patches overlap and z-fight at the edge. - **Choosing an arbitrary transition width** — the back positions must agree with the coarse regular-cell layout. An offset that merely hides one view creates a different crack elsewhere. - **Ignoring reuse data** — adjacent transition cells then emit tiny duplicate slivers or disagree at a shared crossing. Decode the official reuse information or use a canonical edge key. - **Sampling missing halos as air** — a single missing fine-face or coarse corner value can turn a valid case into a hole. Make unavailable neighbours an explicit streaming state. - **Treating a normal seam as a topology seam** — if positions agree but highlights do not, inspect gradients and derivative halos before touching the transition table. - **Publishing the tables without their license** — keep the official repository's license with copied/generated data and record the exact source revision used. ## References - [[Marching Cubes]] — the regular-cell algorithm and why independent LOD meshes crack. - [[Seamless Chunked Voxel Terrain]] — shared samples, chunk ownership, and derivative halos at equal resolution. - [[Designing Scalar Fields for Procedural Terrain]] — deterministic fields, feature scale, and LOD-safe sampling. - [[Normals for Implicit Surfaces]] — gradient-derived normals for regular and transition vertices. - [[From Brush Stroke to Mesh - Real-Time Voxel Terrain Editing in C]] — revisioned dirty jobs and render-thread mesh hand-off. - [The Transvoxel Algorithm](https://transvoxel.org/) — Eric Lengyel's official overview, diagrams, dissertation, and citation guidance. - [The Transvoxel Algorithm poster/PDF](https://transvoxel.org/Transvoxel.pdf) — official summary of regular/transition cases and equivalence classes. - [Eric Lengyel's Transvoxel data tables](https://github.com/EricLengyel/Transvoxel) — official table source and license. - [Lengyel — Transition Cells for Dynamic Multiresolution Marching Cubes (2010)](https://doi.org/10.1080/2151237X.2011.563682) — the journal article describing the transition-cell construction. - [Lengyel — Voxel-Based Terrain for Real-Time Virtual Simulations (2010)](https://transvoxel.org/Lengyel-VoxelTerrain.pdf) — the dissertation in which the algorithm was originally described. --- Back to [[Notes/Index|Notes]] · see also [[Marching Cubes]] · [[Seamless Chunked Voxel Terrain]] · [[Designing Scalar Fields for Procedural Terrain]]