How does transvoxel algorithm work and how can I implement It?

Question

After wasting over three days of researching on DuckDuckGo/Google, trying to understand transvoxel paper and existing implementation, I come here to clarify the subject for me and made it easier for the next person who wants to implement it.

Here is the transvoxel's homepage which explains well what the algorithm solves. So now I'm happy to find something that solves my current problem, so I would like to implement it to my code, but the website doesn't explain how to implement it or sharing code (except tables). So I was looking for existing implementation of the transvoxel algorithm:

• Transvoxel (XNA): Looks great but this solution all-in-one (octree, caching, voxel, etc.) I really tried to understand the transvoxel class into this one, but no.

• Transvoxel (OGRE3D): Looks great too but again, all in one. I tried too to understand, I translated the code from C++ to C#, but no again.

Finding for marching cube was so easy, one class copy&paste, one public function.

So I gave up the idea to use existing implementation. Why not implementing it myself? (Sadly I don't have the skill to fully understand what the paper said, for example the ambiguous case).

The first thing I didn't understand was if transvoxel is a modified marching cube or a seconds layer that modify the work of the marching cube. In the C++ code (second link of the list) the code uses a implementation of marching cube and transvoxelize each border, on the paper they talk about 19x19x19 voxel data on 16x16x16 chunk and about a modified version of marching cube.

So do you guys can explain me how the transvoxel algorithm works and how can I implement it on my existing project?

My existing project is an Unity3D project which uses marching cubes for an infinite world, LOD chunk are ready, the only one thing missing is fixing crack between different LOD level chunk.

Answer 1

The transvoxel paper is a fairly in-depth work, discussing a variety of topics on how to create an entire voxel terrain system, including an overview of marching cubes, how to fix the ambiguity problem, vertex sharing, triplanar texturing, and texture splatting. The area you are interested in is covered in chapter 4, Level of Detail.

It introduces 512 new types of marching cubes, which are adapters between a voxel of one level of detail and another with half the level of detail. For example, a 16 unit voxel with a 32 unit voxel.

The new marching cubes can be constructed using the lookup tables provided on the transvoxel's homepage. The lookup tables are structured differently than the one used by the original marching cubes. I will walk through the first shape as an example, and it should be pretty easy to figure out the rest.

The values in transitionCellClass define which of the 56 equivalence classes the shape belongs to. (With the high bit set to indicate that the triangles should be winded in reverse) The value at index 1 is 0x01, telling us that its equivalence class is 1.

The transitionCellData array is information about the equivalence classes, containing the vertex count, triangle count, and the order of the vertexes. If we look up the value at index 1 (which we got from transitionCellClass) we see the following:

{0x42, {0, 1, 3, 1, 2, 3}}

0x42 in binary is 0100 0010, which means there are 4 vertices, and 2 triangles. And the rest that the ordering of the vertices for triangle 1 is 0, 1, 3; and the ordering for triangle 2 is 1, 2, 3.

What remains to be calculated is the actual edges these vertices and triangles are on. This is contained in the transitionVertexData array. Looking up index 1 (this is the shape number not the equivalence class) we see the following:

{0x2301, 0x1503, 0x199B, 0x289A}

These numbers define the vertex reuse in the high nibble and the vertex edges in the low. In binary (which makes the structure more apparent) it looks like this:

0010 0011 0000 0001, 0001 0101 0000 0011, 0001 1001 1001 1011, 0010 1000 1001 1010

Throwing away the information we aren't interested in at the moment, we are left with:

0000 0001, 0000 0011, 1001 1011, 1001 1010

or:

0, 1, 0, 3, 9, B, 9, A

In other words vertex 0 is between corner 0 and 1; vertex 1 between 0 and 3; vertex 2 between 9 and B, and vertex 3 between 9 and A.

In marching cubes there were 12 edges between 8 corners, and in transvoxels there are 16 edges between 13 corners. 9 facing the higher detail and 4 the lower.

You could if you wanted, assign each edge a number like in the original, as follows:

0 -> 1 = 0

0 -> 3 = 2

9 -> A = 12

9 -> B = 13

It would then be pretty trivial using these edge numbers to combine the data and put them into a single table like the original marching cubes. The first shape would look like the following:

{0, 2, 12, 2, 13, 12, 0}

Using this new table, you can build it the exact same way as you did in the original.

Now that you have these 512 shapes, what do you do with them? Wherever the level of detail changes, you have to insert transition cubes between (previous answer has an excellent picture of this) For each side of the cube that faces a higher level of detail, you place a transition cell.

Each transition cell is constructed by taking the sign values of the 9 corners of the side facing the high detail voxels, and creating a lookup value the same way you did with the original marching cubes, and creating the shape using the lookup tables, as I explained. The transition cells should be a percentage of the cube, like .25 or .125. And of course it has to be reoriented to face to appropriate side. Both of these transformations can be done when converting the edges to world coordinates.

After you add each of the transition cells, you can then place a regular marching cube scrunched up right in the center of the transition cells, using the standard eight corner lookup.

And that's pretty much all there is to it :)

Answer 2

The first thing I didn't understood was if transvoxel is a modified marching cubes or a second layer that modifies the work of the marching cubes.

My reading of the paper is that Transvoxel's novel addition is a kind of "adapter" to bridge regions of voxels at different resolutions.

Let's say you have an area of very dense voxel samples near your player's camera, and some distance away you want to drop down to half the resolution, and further out to a quarter res:

(Visualized here in 2D for simplicity)

Within the body of each of these regions you have a regular grid of potential samples you can turn into a mesh with the conventional marching cubes algorithm - no problem. (Cells in blue above)

But where these grids of different resolutions butt up against one another, you have these weird voxel cells that have more samples along one face than the others. (Cells in green above)

If we ignore these mid-edge/mid-face samples and just build our mesh for the cell using the samples at the corners as usual, then we risk mis-matching the adjacent mesh formed from the higher resolution sample grid, which does include this information.

So instead, we use the lookup table provided by Transvoxel to select and fit the correct adapter mesh into these border cells, taking into account dense samples on one side, and sparse samples at the other corners.

Its operation is very similar to marching cubes, it just considers a different arrangement of sample points and so has a different collection of mesh templates it uses to bridge them.

on the paper they talk about 19x19x19 voxel data on 16x16x16 chunk

I think that means this:

Does that help you get oriented with how this algorithm fits into a voxel meshing system?