It very clear how it works with a regular grid. 3 inner loops - x, y, z over some size. The smaller the cells, so will be the mesh more detailed.

But how about octree. I know i can stich different levels with transvoxel (not sure with what max difference), but no idea how to construct the tree from SDF. It kind of needs to know if a cell is occupied and then split and so on? But how?

Or maybe octrees are bad idea for marching cubes and isn't practiced (then what about ray cast)?


1 Answer 1


You use the octree to skip swaths of work.

Anytime you find an octree node that's fully outside or fully inside the volume, you can skip iterating any cells inside it because you know the surface won't cross any of them, so marching cubes will no need to create any vertices or triangles in that entire cubic region.

Your algorithm can be a depth-first traversal of the octree. Starting from the node that covers your entire space, then descending into one of its 8 children each half the width of your space, then into one of its 8 children (grandchildren of your original) that each span a quarter of the width of your space, etc.

Each time you evaluate a node, sample your SDF at its center. If the absolute value of this sample is greater than nodeWidth * sqrt(3)/2 then the level set of your SDF is further away than any corner of the node, and so doesn't cross this node at all.

In that case, you can skip descending into any of that node's children (and grandchildren, etc), because none of them will generate any geometry. You skip ahead in your traversal to the node's next sibling instead. Or, if you've run out of siblings, the parent's next sibling, etc.

If the absolute SDF value is not that high, then it's possible the surface crosses this node, and you recurse into its smaller children as normal.

When you get down to a threshold node size, you can iterate over all the individual voxels contained inside it in the normal triple-for-loop way you're used to.

The advantage is that you only have to do this for leaf nodes that are very close to your surface, and can skip iterating the majority of lattice points in your space.

  • \$\begingroup\$ Not sure if I benefit from octree for MC (over regular grid). \$\endgroup\$ Apr 12, 2021 at 17:07
  • 1
    \$\begingroup\$ It depends. If you have an area of 1024 x 1024 x 1024, running MC on every cell means about a billion invocations of the MC inner loop. But if your SDF is something like a terrain, the octree optimization could cut that down to something more like a few million invocations. Bringing you down from n^3 complexity closer to (but not exactly) n^2 by skipping empty space above the terrain / solid space below the terrain. \$\endgroup\$
    – DMGregory
    Apr 12, 2021 at 17:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .