1
\$\begingroup\$

I implemented the marching cubes algorithm in unity and wanted to reuse vertices instead of creating new ones for every triangle. I am looping through a 3D array of points as I generate the mesh in the order x y z. To cache the points for reuse I save the relevant vertices for each yz layer of cubes to reference for the next cubes, then after the y loop exits, I save the currentLayer as behindLayer so I can get the last vertex, along edge 8 in my case, from cache.

I'm using the diagram on the first page of this paper as my reference to numbering edges and vertices as well as the edgeTable and triTable: http://paulbourke.net/geometry/polygonise/

In the 3rd dimension of the cache arrays (currentLayer and behindLayer): edge 0 is stored in 0; 1 in 1; 4 in 2; 5 in 3; 6 in 4; 7 in 5; 8 in 6; 9 in 7; 10 in 8.

The exact issue I'm having is that there are double vertices in some intersections. In this example there are double vertices in the center intersection and the middle left intersection. These correspond to edges 8, 9, 10, or 11 as defined in the paper linked above. 2x2x1 set of cubes to be marched through

public class MeshGenerator : MonoBehaviour {

private Vector3[] vertices;
private Vector3[] normals;
private int[] triangles;

public Mesh GenerateMesh(float[,,] pointCloud, float surfaceLevel, int borderedSize, int height) {
    Polygonize(pointCloud, surfaceLevel, borderedSize, height);
    Mesh mesh = new Mesh();
    mesh.vertices = vertices;
    mesh.triangles = triangles;
    mesh.normals = normals;
    return mesh;
}

public void Polygonize(float[,,] pointCloud, float surfaceLevel, int borderedSize, int height) {
    List<Vector3> vertList = new List<Vector3>();
    List<int> triList = new List<int>();

    int[,,] behindCache = new int[height, borderedSize, 9];
    int[,,] currentCache;
    for (int x = 0; x < borderedSize - 1; x++) {
        currentCache = new int[height, borderedSize, 9];
        for (int y = 0; y < height - 1; y++) {
            for (int z = 0; z < borderedSize - 1; z++) {
                int cubeIndex = 0;
                //0
                if (pointCloud[x, y, z + 1] < surfaceLevel) cubeIndex |= 1;
                //1
                if (pointCloud[x + 1, y, z + 1] < surfaceLevel) cubeIndex |= 2;
                //2
                if (pointCloud[x + 1, y, z] < surfaceLevel) cubeIndex |= 4;
                //3
                if (pointCloud[x, y, z] < surfaceLevel) cubeIndex |= 8;
                //4
                if (pointCloud[x, y + 1, z + 1] < surfaceLevel) cubeIndex |= 16;
                //5
                if (pointCloud[x + 1, y + 1, z + 1] < surfaceLevel) cubeIndex |= 32;
                //6
                if (pointCloud[x + 1, y + 1, z] < surfaceLevel) cubeIndex |= 64;
                //7
                if (pointCloud[x, y + 1, z] < surfaceLevel) cubeIndex |= 128;

                if (edgeTable[cubeIndex] != 0) {
                    int[] vertIndices = new int[12];
                    if ((edgeTable[cubeIndex] & 1) == 1) {
                        //Vertex 0
                        if (y > 0 && currentCache[y - 1, z, 2] != 0) {
                            vertIndices[0] = currentCache[y - 1, z, 2];
                        } else {
                            vertIndices[0] = vertList.Count;
                            vertList.Add(LerpVert(new Vector3(x, y, z + 1), pointCloud[x, y, z + 1], new Vector3(x + 1, y, z + 1), pointCloud[x + 1, y, z + 1], surfaceLevel));
                            currentCache[y, z, 0] = vertIndices[0];
                        }
                    }
                    if ((edgeTable[cubeIndex] & 2) == 2) {
                        //Vertex 1
                        if (y > 0 && currentCache[y - 1, z, 3] != 0) {
                            vertIndices[1] = currentCache[y - 1, z, 3];
                        } else {
                            vertIndices[1] = vertList.Count;
                            vertList.Add(LerpVert(new Vector3(x + 1, y, z + 1), pointCloud[x + 1, y, z + 1], new Vector3(x + 1, y, z), pointCloud[x + 1, y, z], surfaceLevel));
                            currentCache[y, z, 1] = vertIndices[1];
                        }
                    }
                    if ((edgeTable[cubeIndex] & 4) == 4) {
                        //Vertex 2 - Dont Cache
                        if (y > 0 && currentCache[y - 1, z, 4] != 0) {
                            vertIndices[2] = currentCache[y - 1, z, 4];
                        } else {
                            vertIndices[2] = vertList.Count;
                            vertList.Add(LerpVert(new Vector3(x + 1, y, z), pointCloud[x + 1, y, z], new Vector3(x, y, z), pointCloud[x, y, z], surfaceLevel));
                        }
                    }
                    if ((edgeTable[cubeIndex] & 8) == 8) {
                        //Vertex 3 - Dont Cache
                        if (y > 0 && currentCache[y - 1, z, 5] != 0) {
                            vertIndices[3] = currentCache[y - 1, z, 5];
                        } else {
                            vertIndices[3] = vertList.Count;
                            vertList.Add(LerpVert(new Vector3(x, y, z), pointCloud[x, y, z], new Vector3(x, y, z + 1), pointCloud[x, y, z + 1], surfaceLevel));
                        }
                    }
                    if ((edgeTable[cubeIndex] & 16) == 16) {
                        //Vertex 4 - Leading Edge
                        vertIndices[4] = vertList.Count;
                        vertList.Add(LerpVert(new Vector3(x, y + 1, z + 1), pointCloud[x, y + 1, z + 1], new Vector3(x + 1, y + 1, z + 1), pointCloud[x + 1, y + 1, z + 1], surfaceLevel));
                        currentCache[y, z, 2] = vertIndices[4];
                    }
                    if ((edgeTable[cubeIndex] & 32) == 32) {
                        //Vertex 5 - Leading Edge
                        vertIndices[5] = vertList.Count;
                        vertList.Add(LerpVert(new Vector3(x + 1, y + 1, z + 1), pointCloud[x + 1, y + 1, z + 1], new Vector3(x + 1, y + 1, z), pointCloud[x + 1, y + 1, z], surfaceLevel));
                        currentCache[y, z, 3] = vertIndices[5];
                    }
                    if ((edgeTable[cubeIndex] & 64) == 64) {
                        //Vertex 6
                        if (z > 0 && currentCache[y, z - 1, 2] != 0) {
                            vertIndices[6] = currentCache[y, z - 1, 2];
                        } else {
                            vertIndices[6] = vertList.Count;
                            vertList.Add(LerpVert(new Vector3(x + 1, y + 1, z), pointCloud[x + 1, y + 1, z], new Vector3(x, y + 1, z), pointCloud[x, y + 1, z], surfaceLevel));
                            currentCache[y, z, 4] = vertIndices[6];
                        }
                    }
                    if ((edgeTable[cubeIndex] & 128) == 128) {
                        //Vertex 7
                        if (x > 0 && behindCache[y, z, 3] != 0) {
                            vertIndices[7] = behindCache[y, z, 3];
                        } else {
                            vertIndices[7] = vertList.Count;
                            vertList.Add(LerpVert(new Vector3(x, y + 1, z), pointCloud[x, y + 1, z], new Vector3(x, y + 1, z + 1), pointCloud[x, y + 1, z + 1], surfaceLevel));
                            currentCache[y, z, 5] = vertIndices[7];
                        }
                    }
                    if ((edgeTable[cubeIndex] & 256) == 256) {
                        //Vertex 8
                        if (x > 0 && behindCache[y, z, 7] != 0) {
                            vertIndices[8] = behindCache[y, z, 7];
                        } else {
                            vertIndices[8] = vertList.Count;
                            vertList.Add(LerpVert(new Vector3(x, y, z + 1), pointCloud[x, y, z + 1], new Vector3(x, y + 1, z + 1), pointCloud[x, y + 1, z + 1], surfaceLevel));
                            currentCache[y, z, 6] = vertIndices[8];
                        }
                    }
                    if ((edgeTable[cubeIndex] & 512) == 512) {
                        //Vertex 9 - Leading Edge
                        vertIndices[9] = vertList.Count;
                        vertList.Add(LerpVert(new Vector3(x + 1, y, z + 1), pointCloud[x + 1, y, z + 1], new Vector3(x + 1, y + 1, z + 1), pointCloud[x + 1, y + 1, z + 1], surfaceLevel));
                        currentCache[y, z, 7] = vertIndices[9];
                    }
                    if ((edgeTable[cubeIndex] & 1024) == 1024) {
                        //Vertex 10
                        if (z > 0 && currentCache[y, z - 1, 7] != 0) {
                            vertIndices[10] = currentCache[y, z - 1, 7];
                        } else {
                            vertIndices[10] = vertList.Count;
                            vertList.Add(LerpVert(new Vector3(x + 1, y, z), pointCloud[x + 1, y, z], new Vector3(x + 1, y + 1, z), pointCloud[x + 1, y + 1, z], surfaceLevel));
                            currentCache[y, z, 8] = vertIndices[10];
                        }
                    }
                    if ((edgeTable[cubeIndex] & 2048) == 2048) {
                        //Vertex 11 - Dont Cache
                        if (z > 0 && currentCache[y, z - 1, 6] != 0) {
                            vertIndices[11] = currentCache[y, z - 1, 6];
                        } else if (x > 0 && behindCache[y, z, 8] != 0) {
                            vertIndices[11] = behindCache[y, z, 8];
                        } else {
                            vertIndices[11] = vertList.Count;
                            vertList.Add(LerpVert(new Vector3(x, y, z), pointCloud[x, y, z], new Vector3(x, y + 1, z), pointCloud[x, y + 1, z], surfaceLevel));
                        }
                    }
                    for (int i = 0; triTable[cubeIndex, i] != -1; i += 3) {
                        triList.Add(vertIndices[triTable[cubeIndex, i]]);
                        triList.Add(vertIndices[triTable[cubeIndex, i + 1]]);
                        triList.Add(vertIndices[triTable[cubeIndex, i + 2]]);
                    }
                }
            }
        }
        behindCache = currentCache;
    }
    triangles = triList.ToArray();
    vertices = vertList.ToArray();
    normals = CalculateNormals(triangles, vertices);
}

Vector3 LerpVert(Vector3 p1, float v1, Vector3 p2, float v2, float surfaceLevel) {
    float percent = (surfaceLevel - v1) / (v2 - v1);
    return Vector3.Lerp(p1, p2, percent);
}

Vector3[] CalculateNormals(int[] tris, Vector3[] verts) {
    Vector3[] normals = new Vector3[verts.Length];
    for (int i = 0; i < tris.Length; i += 3) {
        Vector3 pointA = verts[tris[i]];
        Vector3 pointB = verts[tris[i + 1]];
        Vector3 pointC = verts[tris[i + 2]];


        Vector3 normal = Vector3.Cross(pointA - pointB, pointA - pointC);

        normals[tris[i]] += normal;
        normals[tris[i + 1]] += normal;
        normals[tris[i + 2]] += normal;
    }

    for (int i = 0; i < normals.Length; i++) {
        normals[i].Normalize();
    }
    return normals;
}

Any Help is greatly appreciated I have been staring at this for way too long now unable to figure out whats wrong.

\$\endgroup\$
1
  • \$\begingroup\$ I fixed the left middle double vert by initializing all values i in currentLayer[y, z, i] to -1, so that the comparison if currentLayer[y, z - 1, 6] != 0 returns correctly the first go around. I cant seem to figure out why the middle vert isn't fixed though. But I've definitely narrowed it down to Vertex 11 as the issue. \$\endgroup\$ – Carter Schmidt Jan 3 '20 at 21:12
1
\$\begingroup\$

I figured it out! The problem was when there was a cache hit for vertex 8 in the behindLayer array, it didn't update currentLayer so then when vertex 11 checked if there was a cached index for vertex 8 in currentLayer, it didnt find out and created its own vertex.

\$\endgroup\$

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.