I have been implementing Transvoxel in to my Marching Cubes project in c++. The Transvoxel documentation and available code examples feature cell vertex reuse (caching) via indices. The main benefits are:
- No doubling vertices - simpler mesh
- Avoids recalculating same vertex positions and its other parameters
And I think its mandatory for Transvoxel to work correctly.
The fallowing snippets explain the main part of caching:
ReuseCell& getReuseCell(Int3_64 pos) {
uint32 j = pos.Z & 1;
uint32 i = pos.Y * maxX + pos.X;
return cache[j][i];
}
...
Array<std::vector<ReuseCell>, FixedAllocation<2>> cache;
...
struct ReuseCell {
Array<uint32, FixedAllocation<4>> vertices;
...
};
The pos.Z & 1 part deserves special attention. Generally as Z grows from 0 to n the bit & 1 part turns it to 0,1,0,1,0,1.., making the cache rolling and relatively small, but most importantly relevant so 100% of the time same position vertex is reused. Any new Z row has the cache of previous one.
However this caching relies the volume cells to be processed in sequential order:
for(z)
for(y)
for(x)
otherwise it can't work.
My implementation of Marching cubes uses and Octree instead of a regular grid, to avoid processing of empty areas and other benefits that comes with it. And Octree traversal is not sequential (as example above) as it recursively processes the octants in depth, therefor this caching method can not work with it. In more detail I currently use Z (morton) order to recursively process my Octree.
So I am looking for ideas for non-standard Octree traversal (How to read a sparse Octree sequentially, like a 3D array?) or different caching strategy as I don't want to switch from Octree to regular grid.
