Talk:Marching cubes

Missing triangle

The picture in the last column, second row is missing 1 triangle. 60.227.138.153 10:55, 26 January 2007 (UTC)

Fixed. --CyHawk (talk) 12:26, 31 January 2008 (UTC)

Ambiguities

The description given here, as well as the cited paper, give wrong results. There is huge list of follow-up papers that all present an improved version that resolves the ambiguous cases to prevent holes from appearing in the surface. This should definitely be corrected.

It is true that the original algorithm has ambiguous cases, and that newer algorithms are available to resolve them. But they aren't "marching cubes" (at least that is my undestanding). For instance the Marching tetrahedrons, for which there is already an article, does not have the same ambiguities. However, the original algorithm is also of encyclopedic interest, and dare I say highly usefull too, as many programs use it, regardless of the ambiguous cases (for some applications it makes little to no difference). Thus, my opinion is to retain this article describing the original algorithm, and also make sure it links to alternative non-ambiguous algorithms as well. Jtsiomb 05:36, 12 August 2007 (UTC)

The 'holes' problem is easily fixed with only minor modifications. I've done it in an implementation, and given details below on this talk page. The original paper with its errors is indeed of historic interest, but to allow the algorithm (as opposed to its original published form) to sit uncorrected is to imply that it is broken and unfixable, which is utterly not the case. Note, the diagram shows 15 cases but two of them are equivalent (with rotate/reflect); there are only 14. I believe that error was in the original paper.

However, I don't have a citable source for these corrections... just my own unpublished work. Surely something has been published. Greg.smith.tor.ca (talk) 01:42, 19 March 2014 (UTC)

I would have to second the argument that there are not any ambiguities. The 'improved' cases certainly are marching cubes, and the very same 'ambiguities' can likely be specified to exist in marching tetrahedrons. The definition of the ambiguity is actually axiomatic, and thus I am not sure how this would be resolved here. If the paper called them 'ambiguous' and this is about the paper then they it is relevant, but if its about the method then its not ambiguous, its an axiom that states that they are, which is not how everyone sees it. Basically, dump the axiom and get a closed hull. — Preceding unsigned comment added by 91.103.38.8 (talk) 13:45, 22 August 2015 (UTC)

External Links

Removed dead link,"Yet another tutorial". —Preceding unsigned comment added by 93.97.31.14 (talk) 19:02, 26 January 2009 (UTC)

"good" starting point?

Cleanup ?

Since that cleanup tag is there for years now, and nobody came here to say what should be cleaned up, I believe it should be removed. If there is no objection to that, I will remove it in a week. Jtsiomb 05:38, 12 August 2007 (UTC)

It appears you’re thirteen years in arrears. Regardlless, rhe most tenable solution to restoring the unadulterated isomer is to utilize sTring theory to loop back around behind the event horizon and delete the legislation which mandated the adulteration. Danielmiot (talk) 03:50, 3 October 2020 (UTC)

This is referred to a double-headed legislative//super-judicial slam-dunk bypass and occurs only once at the trough of a kondrotiev wave. Danielmiot (talk) 03:56, 3 October 2020 (UTC)

15 unique cases (...but it's 14!)

The precalculated array of 256 cube configurations can be obtained by reflections and symmetrical rotations of 15 unique cases.

What do we gain with this? I don't see the advantage.. The lookup-table can't be accessed faster, the number of triangles or interpolations is not reduced.. What is the advantage of this reduction to 15 cases? --84.56.176.217 12:14, 5 October 2007 (UTC)

Data storage perhaps? 15 cases, need less space then 256. But other than this I also see little advantage. But I'm not that experienced with this. --195.169.225.6 (talk) 22:24, 27 November 2007 (UTC)

I have no experience either, but as I understand you have to write a different piece of code for each of the 15 cases. If there were significantly more cases, implementation would be much less feasible. Which piece of code is then executed for a configuration of voxels is then looked up in the lookup-table, so indeed execution speed is not affected. --CyHawk (talk) 11:37, 31 January 2008 (UTC)

For those of you who have never implemented marching cubes, the issue of 256 cases relative to 15 cases is irrelevant. Neither generates more code than the other, because you dont implement it as a gigantic case statement. You implement it as a lookup table that specifies exactly which cube edges you will generate the triangles from. The result is more like 15 lines of code, and detecting symmetries to 15 would actually make it more complex.

Also, the picture of the skull cannot be generated with a correct implementation of marching cubes. You shouldnt see those axis-aligned ridges and bumps on the top of the head. There is a bug in that code, and it is not an ideal representation for this wikipedia entry. A proper marching cubes implementation at the same cube resolution would make it appear fairly smooth. The problem with the skull may be that the input data has a maximum resolution lower than that of the marching cubes algorithm, too. In any case, the illustration is misleading. —Preceding unsigned comment added by 156.145.28.102 (talk) 00:10, 13 May 2008 (UTC)

Indeed, I've recently implemented this, and the reasonable approach is to have a table as stated above. However, there is a question of how the table is generated - in my case I wrote a python script, and, in effect, manually coded each of the 22 cases in there; the purpose of the python script was to generate the full set of cases from the 22 cases and expand the symmetries to make the full table. Far less work and less error-prone than doing them all manually; and yet still less trouble than writing something to generate the table by actually analyzing the edge configurations. So the symmetry reduction is of interest as a means to create the table for the full set.

The reason I say 22 instead of 14 is that I did not do reduction by polarity; this solves the 'ambiguity' problem mentioned throughout. I'm puzzled that this seems to be viewed as a flaw in the MC algorithm, but it's easily fixed. Any face that has 2 diagonally opposite corners inside the volume, and the other two corners out, can be subdivided two ways - I chose to have the inside corners connected with the middle region, and the outside corners thus separated. If you follow that consistently, then all such faces will properly meet all others. But if you decide to 'reduce by polarity' when possible (to 14 cases, not actually 15) then you are arbitrarily flipping the two cases and can have an improperly joined mesh as a result. This occurs whenever a cube which is polarity-reduced meets a cube which is not, on such a face. This is alluded to briefly in the article text.

Even then, some of the 22 cases can still be flipped to others by polarity changes - just stay away from the ones that have such faces.

You could argue that there's still an 'ambiguity' - the mesh may be proper but the topology of it may be incorrect. But this is a hazard with any sampling approach - the surface could have arbitrary pockets or tunnels through cells that aren't detected at the corners. I really don't see how switching to other algos is needed to 'solve the ambiguity problem' (as mentioned here, and in the marching tets, and in the asymptotic decider article).

It seems to me this article should present a correct algorithm - without the naive polarity reduction to 14 cases - and discuss the original '15' (14) cases as a historical note. To do otherwise is to present MC as a broken, unfixable dead end, which it is not.

Also, why all the confusion about 15 vs 33 (not 14 and 22)? The bottom two cases in the last column of the diagram are the same, so it's 14, not 15, if you allow polarity reduction (I seem to recall this article used to point that error out...) And it works out to 22 if you don't allow polarity reduction.

Here's how I reduced the cases :

 Every configuration is identified by the 8 signs (+ or -) on the 8 vertices; the
 following metrics are then counted, which are invariant under rotation and reflection
 (and happen to be sufficient to identify all the distinct cases):

  (1) the total # of vertices with negative sign (0..8)
  (2) the number of edges (0..12) which have sign changes across them.
  (3) number of faces (0..6) which have exactly 2 'negative' vertices on them.

 These form a triplet which identifies each category; any cube with a given triplet
 can be transformed by rotation/reflection to any other with the same triplet.

 Note, if the pattern is complemented (all corners sign changed), the first metric
 changes from n to 8-n, and the other two are unchanged.

 The categories are then as follows (with the number of reflect/rotate subcases in each one):

    (0,0,0) *1 case
    (1,3,0) *8
    (2,4,2) *12,  (2,6,1)*12, (2,6,0)*4
    (3,5,2) *24,  (3,7,3)*24, (3,9,3)*8
    (4,8,6) *6    (4,12,6)*2  (4,6,0)*8  (4,6,2)*24 (4,4,4)*6  (4,8,4)*24
    (5,5,2) *24,  (5,7,3)*24, (5,9,3)*8
    (6,4,2) *12,  (6,6,1)*12, (6,6,0)*4
    (7,3,0) *8
    (8,0,0) *1

So that's the 22 categories. If you do polarity reduction, the last 4 rows map mirrorwise to the first four, and the fifth row remains, leaving the 14 cases (all categories in the middle row map to themselves on a polarity change). There are three cases in the middle row which have at least one kitty-corner side (they are the 2nd and 3rd in the middle row of the article diagram - metrics (4,8,4) and (4,12,6) - and 2nd last in the bottom row: (4,8,6)).

The other ones that have kitty-corner faces : (2,6,1) (3,7,3) (3,9,3) (5,9,3) (5,7,3) (6,6,1). In fact, if you want, you can safely polarity-reduce all cases in the last 4 rows except (5,9,3),(5,7,3),(6,6,1) ... leaving 17 cases. This is the number that I needed to manually code in my table builder.

Greg.smith.tor.ca (talk) 01:21, 19 March 2014 (UTC)

Only 14 cases?

To me it seems there are only 14 different cases? In the "15 unique cube configurations" image, case 15 can be produced using case 10 and a reflection at the YZ plane. —Preceding unsigned comment added by 134.2.62.10 (talk) 09:06, 16 June 2008 (UTC)

Mistake in the graph?

it seems that the 10th cube could be wrong (no zero on front wright edge)

Crystallography

I see a superficial similarity to Miller index. Is it worth putting that in the "see also" section, or is that a silly idea?  Card Zero  (talk) 12:43, 5 September 2011 (UTC)

Head Wound?

That picture of the head looks like the subject has suffered severe trauma to the right temple, and resembles a gunshot wound. The picture has been there for 10 years, I know, but it sure looks inappropriate, to me. Reminds me a little too much of those sick "Faces of Death" videos... Can someone come up with a more appropriate picture? — Preceding unsigned comment added by 96.241.142.171 (talk) 18:05, 11 July 2015 (UTC)

See the image summary at https://commons.wikimedia.org/wiki/File:Marchingcubes-head.png: "The hole is caused by a non-ferromagnetic piercing." --31.46.89.7 (talk) 10:54, 8 January 2021 (UTC)