Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Marching Cubes Implementation - Missing Triangles in Mesh

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;
}

Triangle mesh showing missing triangles

Entire rendered data set with the missing triangles issue

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?

Missing triangles issue fixed but there is an inversion problem on z-axis

like image 814
Vahe J Avatar asked Nov 02 '22 05:11

Vahe J


1 Answers

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?
like image 163
Pourya Avatar answered Nov 15 '22 05:11

Pourya