Marching Cube Ambiguities Versus Marching Tetrahedron

2018-05-31 05:11:51

I have successfully implemented the marching cubes algorithm. I used the standard materials as a reference, but I rewrote it entirely from scratch. It works, but I am observing the ambiguities that lead to holes in the mesh.

I was considering the marching tetrahedrons algorithm, which supposedly does not suffer from ambiguities. I fail to see how this is possible.

The marching tetrahedrons algorithm uses six tetrahedrons in place of a cube, with triangulations for each tetrahedron. But, suppose I were to implement the marching cubes algorithm, but for each of the 256 triangulations, simply choose the one that is the "sum" (union) of the cube's tetrahedron's triangulations? As far as I know, this is what marching tetrahedrons does--so why does that magically fix the ambiguities?

There are 16 unique cases, I think, and the 240 others are just reflections/rotations of those 16. I remember reading in some paper somewhere that to resolve ambiguities, you need 33 cases. Could this be related to why marching tetrahedons somehow doesn't suffer from problems?

So, questions:

Why does marching tetrahedrons not suffer from ambiguities?

If it doesn't, why don't people just use the marching cubes algorithm, but with the tetrahedrons' triangulations instead?

I feel like I'm missing something here. Thanks.

Okay, well I've just finished implementing my version of marching tetrahedrons, and while I easily saw ambiguities lead to problems in the marching cubes's mesh, the marching tetrahedrons's mesh seems to be consistently topologically correct. There are some annoying features along very thin points where some vertices can't quite decide which side of the divide they want to be on, but the mesh is always watertight.

In answer to my questions:

To resolve ambiguities in the marching cubes algorithm, as far as I can tell, one evaluates the function more carefully in the cell. In the tetrahedrons algorithm, one explicitly samples the center of the cell and polygonizes to that. I suspect that because the tetrahedral mesh includes this vertex in particular, ambiguities are implicitly handled. The other extra vertices on the side probably also have something to do with it. As a key point, the function is actually being sampled in more places when you go to refine it.

I'm pretty sure they do. My marching tetrahedrons algorithm does just that, and I think that, internally, it's doing the same thing as the classic marching tetrahedrons algorithm. In my implementation, the tetrahedrons' triangles are all listed for each possible cube, which I suspect makes it faster than figuring out the one or two triangles for each individual tetrahedron individually.

If I had the time and attention span (neither of which I do), it might be beneficial to remesh the insides of each cube to use fewer triangles maximum, which I think wouldn't hurt it.

To answer the question "Why does Marching Tetrahedrons algo has ambiguities?" it is required to understand why do the ambiguities arise in the first place in Marching Cubes.

Ambiguities may occur when there are two diagonally opposite "positive" vertices and two diagonally opposite "negative" vertices in a cube. It took me some time to wrap my mind around it, but the problem with ambiguities is that they theoretically allow to create isosurface patches for adjacent cubes that are incompatible with one another. That's the obvious part. The interesting part is that two adjacent isosurface patches from two ambiguous configurations are incompatible if ( and only if ) one of them separates "negative" vertices, and the other one separates "positive" verticies.

Here is a relevant quote from Rephael Wenger's great book "Isosurfaces Geometry, Topology & Algorithms" (can't post more then 2 links, so I've merged all relevant images from the book into a single one):

The border of a cube's three-dimensional isosurface patch defines an isocontour on each of the cube's square facets. If some conﬁguration's isosurface patch separates the negative vertices on the facet while an adjacent conﬁguration's isosurface patch separates the positive ones, then the isosurface edges on the common facet will not align. The isosurface patches in Figure 2.16 do not separate the positive vertices on any facet. Moreover, the derived isosurface surface patches in any rotation or reﬂection of the conﬁgurations also do not separate positive vertices on any facet. Thus the isosurface patches in any two adjacent cubes are properly aligned on their boundaries. An equally valid, but combinatorially distinct, isosurface table could be generated by using isosurface patches that do not separate the negative vertices on any square facet.

What this means is that if all used ambiguous configurations follow the same pattern (ie always separate "negative" vertices), then it is impossible to produce a topologically incorrect surface. And problems will arise if you use configurations "from both worlds" for a single isosurface.

The surface that was constructed using the same ambiguity resolution pattern still may contain unwanted errors like this (taken from "Efficient implementation of Marching Cubes' cases with topological guarantees" article by Thomas Lewiner Helio Lopes, Antonio Wilson Vieira and Geovan Tavares), but it will be, as you said, watertight.

To achieve this, you will need to use the look-up table based on the 22 unique configurations (not the standard 14 or 15) shown in the Figure 2.16.

Now, back to the original question at last - why does Marching Tetrahedrons does not suffer from ambiguities? For the same reason there will be no ambiguities in the Marching Cubes, if done as described above - because you arbitrarily chose to use one of the two available variants of ambiguous configuration resolution. In Marching Cubes it is not obvious at all (at least for me, had to do a lot of digging) that this is even an option, but in Marching Tetrahedrons it is done for you by the algorithm itself . Here is another quote from Rephael Wenger's book:

The regular grid cubes have ambiguous conﬁgurations while the tetrahedral decomposition does not. What happened to the ambiguous conﬁgurations? These conﬁgurations are resolved by the choice of triangulation. For instance, in Figure 2.31, the ﬁrst triangulation gives an isosurface patch with two components corresponding to 2B-II in Figure 2.22 while the second gives an isosurface patch with one component corresponding to 2B-I.

Note how cubes are sliced into tetrahedrons in two different ways in Figure 2.31. The choice of this slicing or the other is the secret sauce that resolves the ambiguities.

One may ask himself - if the ambiguity problem can be resolved just by using the same pattern for all cubes then why are there so much books and papers about more complicated solutions? Why do I need Asymptotic Decider and all that stuff? As far as I can tell, it all comes down to what you need to achieve. If topological correctness (as in, no holes) is enough for you, then you do not need all the advanced stuff. If you want to resolve problems like those shown in "Efficient implementation of Marching Cubes" article shown above, then you need to dive deeper.

I highly recommend reading the relevant chapters of Rephael Wenger's book "Isosurfaces Geometry, Topology & Algorithms" to better understand the nature of these algorithms, what are the problems, where do the problems come from and how can they be solved.

As was pointed out by Li Xiaosheng, the basics can be better understood by carefully examining the Marching Squares algo first. Actually, the whole answer was layed down by Li Xiaosheng, I've just expanded the explanations a bit.

Take the following 2d example (which introduces ambiguities):

If we divide this square into two triangles, we will get different results in the diagonal we chose to divide the square. Along 0-0 diagonal, we get triangles (010,010) while for the 1-1 diagonal, we get triangles (101,101). Obviously, different decomposition of square lead to different results. Either is correct and this is same for 3D Cubes.

MT doesnot resolve the ambiguities actually but it can produce topologically consist result by choosing the same decomposition strategy for all cubes. That the way it get rid of suffering from ambiguities.

链接地址: http://www.djcxy.com/p/6344.html

上一篇: 将数字除以3而不使用*，/，+，

下一篇: 行进立方体歧义与行进四面体