Marching Cubes Implementation - Missing Triangles in Mesh

Question

I am currently working on understanding and implementing the Marching Cubes algorithm using C++ by rendering a sample data set in OpenGL.

I have been encountering an issue where the mesh that I render is missing triangles. I am seeing almost half of the triangles missing which can be seen below.

Would filling in the triangles and creating quads be the right approach to take to solve the issue, or am I missing something obvious?

The edge intersection table I have used is from the following link: http://paulbourke.net/geometry/polygonise/

Instead of using an edge flag array of 12 bit entries I have 12 if statements (2 of which are shown). I use the index into the 3D array to determine the values of x, y, z based on the edge values (0-11)

    if ((edge.point1 == 0 && edge.point2 == 1) ||
        (edge.point1 == 1 && edge.point2 == 0))
    {
        p1.x = x;   p1.y = y; p1.z = z;
        p2.x = x+1; p2.y = y; p2.z = z;
    }
    else if ((edge.point1 == 1 && edge.point2 == 2) ||
             (edge.point1 == 2 && edge.point2 == 1))
    {
        p1.x = x+1; p1.y = y;   p1.z = z;
        p2.x = x+1; p2.y = y+1; p2.z = z;
    }

Also, the interpolation function is below.

point interpolate(point p1, point p2, unsigned char isovalue)
{
    point p;

    unsigned char d1 = getDataValue(p1.x, p1.y, p1.z);
    unsigned char d2 = getDataValue(p2.x, p2.y, p2.z);

    if (abs(double(isovalue)-double(d1)) == 0)
        return(p1);
    if (abs(double(isovalue)-double(d2))  == 0)
        return(p2);
    if (abs(double(d1)-double(d2))  == 0)
        return(p1);

    double val = double(isovalue - d1) / double(d2 - d1);

    p.x = p1.x + val * (p2.x - p1.x);
    p.y = p1.y + val * (p2.y - p1.y);
    p.z = p1.z + val * (p2.z - p1.z);

    return p;
}

UPDATE:

After finding an example I modified my code and was able to render all triangles. Now, I see an issue where when I rotate my object the object begins to invert the z axis and shows the object inside out.

Why would the object begin to invert the z values during rotation?

Burgess

Are they missing, or backwards? Have you tried disabling culling? Alternatively, what's the datatype for your Element/ElementArray buffer? If you're using, say, GLushort, and putting in more than 64k indices, strange things start happening. – Uprush

It's difficult to suggest anything without seeing some code. I imagine the code is quite lengthy though, so perhaps posting your question on Code Review would be better? – Noblenobleman

David, Thank you for the reply. I will see if perhaps it might be culling or maybe a calculation error. The data type I use is an unsigned char (0-255) - 1 Byte. Each cell of the 3D array goes up to 255 and the data is 255 wide by 255 high by 240 deep. And, Peter, I have not tried Code Review before but will give it a shot. Thanks for the help. – Burgess

@PeterR.Bloomfield: This question is off-topic on Code Review. If the question is about solving a problem, it's best here. CR is only for working code. – Stutter

Answer 1

For this type of space partitioning algorithms you may want to use a very simple model instead (sphere or cube) and then debug your implementation step by step and checkout the input/outputs per each stage. Sometimes overlooking a small detail can mess up with the result. As an idea find the answer to the following:

• Are your cell configurations computed correctly?
• Did you perform a correct one on one mapping between a cell config and the output triangles?
• Are all your triangles ordered clock-wise/counter clock-wise?

Software

I investigated the reason for missing triangles a bit further and learned that the cases with ambiguities would cause missing triangles. I stumbled upon a technique called Asymptotic Decision resolution but all examples are provided in 2D. How would I implement the resolver in 3D for the cubes with ambiguities? Thank you. – Burgess

For cubes with ambiguities you take another sample from the the center. See my publication here: webhome.cs.uvic.ca/~blob/publications/egpgv12.pdf – Software

Thank you for the assistance and paper. I would like to mention another observation. I tried running my code with out any ambiguity resolution (from a standard look up table) and observed missing triangles. I also integrated code from afni.nimh.nih.gov/pub/dist/src/SUMA/MarchingCubes into my code using both the LookupTable.h with subcases and the MarchingCubes.c but still observed missing triangles. I don't know if it would be possible to view my updated code. If so, I would appreciate it. I have uploaded the code to gist.github.com/anonymous/9056336 – Burgess

One other modification I tried was to "fill" the missing triangles by creating quads from right triangles. Of course, I was assuming that the triangles were right triangles. I did not succeed with this method either. – Burgess