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\$
  • \$\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 '14 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 '14 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 '14 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\$ – Steven Stadnicki Sep 17 '14 at 23:37
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\$
  • \$\begingroup\$ Ah thanks, so I mistook Bourke's paper for the "original" algorithm. \$\endgroup\$ – Gnurfos Sep 18 '14 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 '14 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\$ – Simon Jenkins Sep 18 '14 at 10:45

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.