3
\$\begingroup\$

In Dual Marching Cubes the dual of an octree is tessellated via the standard marching cubes method. But the classical marching cubes algorithm operates only on cubes with eight vertices (it uses signs at eight corners of the cube to construct a bitmask and select the proper configuration of triangles), while cells of octree duals can actually have more than eight edges.

For example, in the following picture a quadtree dual is shown, where the lower left cell has 8 links to neighboring dual vertices:

quadtree dual

although the marching squares algorithm needs only 4 corner vertices (4-bit masks - 16 cases) for contouring the grid.

And how to build the surface in this case? Which edges to select to form a bitmask used in the marching cubes/squares algorithm as the algorithm needs only 8/4 points as input?

\$\endgroup\$
5
\$\begingroup\$

The thick black lines in the picture aren't an illustration of the connectivity of the dual grid: Those lines are the dual grid itself. The light blue lines show the squares of the quadtree but its not the quadtree that's marching.

The lower left cell of the dual grid is a square. All the other cells in it are either square, some other quad or a "degenerate quad" where some vertices are shared i.e. they're triangles. These are the cells that the original algorithm gets run on to generate the surface.

Back in 3 dimensions every cell would be a possibly degenerate cuboid.

It should be noted though that in the full algorithm the vertices of the dual grid aren't always placed in the centres of the original cells. Instead they are placed wherever in their cell provides the best approximation to the desired implicit function. This is the "Feature Isolation" stage described in the paper.

\$\endgroup\$
  • 1
    \$\begingroup\$ boom ... Mind blown !! \$\endgroup\$ – War Aug 15 '14 at 22:24
  • \$\begingroup\$ yeah, i see now - it's thick black polys that get contoured. i didn't know the definition of a dual grid. \$\endgroup\$ – GameDevEnthusiast Aug 15 '14 at 22:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.