4
\$\begingroup\$

I am reading Eric Lengel’s paper about the Transvoxel algorithm.

In an early part describing the classical Marching Cubes (3.1.1), he talks about ambiguous cases. From what I understand, these can result from grouping the cases into “equivalence classes”.

However, in the Marching Cubes paper I read (is this the one he is referring to ?), there does not seem to be any grouping done, and each of the 256 cases produces its own triangulation. For example, taking the case of Lengyel’s figure 3.2 (on page 12 of the first document), the left cube has index 189 (vertices 0 2 3 4 5 7) and the right cube index 24 (vertices 3 and 4), which gives non “equivalent” triangulations: 4 triangles for the left cube, and 2 for the right cube.

To phrase this as a question: are there different versions of Marching Cubes, and could Lengyel be referring to a different one than Paul Bourke's ?

\$\endgroup\$
4
  • \$\begingroup\$ Isn't this exact purpose for dual contouring? to explain and fix these "edge cases" ... to give an example the paper on DC talks about where the surface comes in to then out of a given space portion something that MC / transvoxel on their own would miss. \$\endgroup\$
    – War
    Sep 16, 2014 at 9:39
  • \$\begingroup\$ I don't know, I haven't looked into DC yet. I'm not complaining about MC ambiguities here, just saying I don't see such ambiguities, and trying to understand. \$\endgroup\$
    – Gnurfos
    Sep 16, 2014 at 12:14
  • \$\begingroup\$ Yeh i was saying if you read up on DC it might explain those ambiguities (unless I misunderstood the problem) since DC was created to address certain shortcomings in MC. \$\endgroup\$
    – War
    Sep 16, 2014 at 14:17
  • \$\begingroup\$ A very simple way to see how ambiguity can arise is to go down a dimension and look at 'Marching Squares'. In that case, a square with two positive vertices (diagonally opposite) and two negative vertices (also diagonally opposite) can clearly be contoured in two ways: we can either connect the edges such that the two negative nodes are part of the same region, or such that the two positive nodes are. A priori (i.e., without analytical or topological information), there's no reason to prefer one over the other. \$\endgroup\$ Sep 17, 2014 at 23:37

1 Answer 1

3
\$\begingroup\$

The original 1987 paper on marching cubes reduced the 256 cases to 15 using symmetries and 'complementary cases'.

The Eric Lengyel paper you link describes what an ambiguous face is and how if two adjacent cubes sharing such a face disagree on its interpretation there will be a hole in the triangle mesh at that face. (Section 3.1.2).

The original paper had exactly such a disagreement wherever a complementary case cube shared an ambiguous face with a non-complementary case cube: Neither the triangle edges nor the inside/outside interpretation would match up at such a face and so there would be a hole in the mesh. The discrepancy was picked up quite quickly (Dürst, 1988) so subsequent treatments of marching cubes are likely to handle these cases correctly or, failing that, at least consistently.

\$\endgroup\$
3
  • \$\begingroup\$ Ah thanks, so I mistook Bourke's paper for the "original" algorithm. \$\endgroup\$
    – Gnurfos
    Sep 18, 2014 at 8:05
  • \$\begingroup\$ What is the point or reducing with equivalences ? I can imagine that in 1987, 256 cases was maybe too big in memory, or too tedious to precompute. But Lengyel in 2010 still mentions use of equivalences, so I think there might be more to it. \$\endgroup\$
    – Gnurfos
    Sep 18, 2014 at 9:17
  • \$\begingroup\$ @Gnurfos the equivalences exist in an abstract sense whether code exploits them or not. The original method had 15 distinct ways to place the triangles, Lengyel expands this to 18 distinct ways, and these would be true facts even if neither paper even mentioned it! But they mention it because human brains haven't grown so much since 1987 that we'd rather read about 256 cases than wonder if some of them are really the same case. (And supposing you did want to precompute all 256 cases, is there a better method for that than identifying the equivalent cases and coding each of them once?) \$\endgroup\$ Sep 18, 2014 at 10:45

You must log in to answer this question.

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