# My vertex cache for reusing vertices in marching cubes algorithm in unity fails for one case, but I cant figure out what case

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.

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) {
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) {
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) {
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) {
}
}
}
}
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.

• 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. Jan 3, 2020 at 21:12