1
\$\begingroup\$

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.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ I suspect there are efficient ways to implement transvoxels natively within an octree structure, that do not require an adapter layer or cache to pretend the data is laid out sequentially, so I think this question can attract answers that are different in kind than the question Engineer links, and useful in their own right. There is often more than one way to skin a cat, after all..😉 \$\endgroup\$
    – DMGregory
    Commented Sep 16, 2021 at 14:59
  • 1
    \$\begingroup\$ You have expressed your opinion that the question is a duplicate via your vote. If enough users vote to agree with your assessment, it will be closed. That is, as you say, how this site operates and has always operated. \$\endgroup\$
    – DMGregory
    Commented Sep 16, 2021 at 15:08
  • 1
    \$\begingroup\$ Myself, I think your original answer to how to iterate a sparse octree sequentially is a very good and useful one in its own right. I think keeping a question about sequential iteration of octrees with that answer is a good way to make that information easy to find for future users. I think that the transvoxel case specifically may benefit from different strategies, so a separate question makes sense to me. I defer to the voting community if they find otherwise. I have not used any moderator privileges to enforce my opinion, only stated it as a suggestion, subject to the community's approval. \$\endgroup\$
    – DMGregory
    Commented Sep 16, 2021 at 15:12
  • 1
    \$\begingroup\$ "I suspect there are efficient ways to implement transvoxels natively within an octree structure, that do not require an adapter layer or cache to pretend the data is laid out sequentially", I hope so. As I am stuck. Anyways you should stop the fight here and leave the focus on the question. \$\endgroup\$
    – trshmanx
    Commented Sep 16, 2021 at 17:11

0

You must log in to answer this question.

Browse other questions tagged .