Remove Vertices that are not in triangle[Solved]

I am using a Boolean mesh script to create a new mesh of the intersection at run-time. This works well, however, when viewing the mesh there is a lot of blank space around it. I believe that the script is deleting the extra triangles, but not the vertices. I have tried exporting the model as an object, and re-importing it later. This results in a much smaller vertex count, although the model is the same.

This would not be an issue, but I need to use the mesh to create a convex mesh collision. The vertices become part of the collision which is very inaccurate.

Is there a way to remove these at run-time?

This was the function I tried, but it didn't make a difference:

Code (csharp):

1. Mesh ClearBlanks(Mesh mesh)
2.     {
3.         int[] triangles = mesh.triangles;
4.         Vector3[] vertices = mesh.vertices;
5.         Vector2[] uv = mesh.uv;
6.         Vector3[] normals = mesh.normals;
7.         List<Vector3> vertList = new List<Vector3>();
8.         List<Vector2> uvList = new List<Vector2>();
9.         List<Vector3> normalsList = new List<Vector3>();
10.         List<int> trianglesList = new List<int>();
11.  
12.         for (int triCount = 0; triCount < triangles.Length; triCount += 3)
13.         {
14.             for(int w = 0; w < 3; w++)
15.             {
16.                 trianglesList.Add(triangles[triCount + w]);
17.                 vertList.Add(vertices[triCount + w]);
18.                 uvList.Add(uv[triCount + w]);
19.                 normalsList.Add(normals[triCount + w]);
20.             }
21.         }
22.  
23.  
24.         triangles = trianglesList.ToArray();
25.         vertices = vertList.ToArray();
26.         uv = uvList.ToArray();
27.         normals = normalsList.ToArray();
28.         //mesh.Clear();
29.         mesh.triangles = triangles;
30.         mesh.vertices = vertices;
31.         mesh.uv = uv;
32.         mesh.normals = normals;
33.         return mesh;
34.     }
35.  

Thank you!

 

I think you have some code missing there (like where the variable 'i' comes from), but I do have a suggestion.

The 'triangles' array is an index into the 'vertices' array. The 'vertices', 'uv', and 'normals' arrays all should be the same size.

Here's the high-level idea: We look at every vertex. If we find it's not in the list of triangles, we remove it from the list of vertices (and UVs and normals), but then we've got a lot of bad indices in the triangle array. To fix that, we have to iterate over all of the triangles and subtract one from every number greater than the index we are testing.

1. Store 'triangles', 'vertices', 'uv', and 'normals' as List<int>, List<Vector3>, or List<Vector2> as appropriate.
   
2. Set testVertex to 0.
3. While testVertex < triangles.Count()
   • If testVertex is not in 'triangles'
     • triangles.removeAt( testVertex ); ... same with 'uv' and 'normals'
     • for( int i = 0; i < triangles.Count(); ++i )
       • If triangles > testVertex then triangles--;
   • Else if testVertex was in 'triangles'
     
     • testVertex++
4. Convert the Lists to Arrays and assign them back to the mesh.

Let me know if you have any questions.

 

Yeah, I forgot to change those. They are updated now. I'll try your idea and get back to you.

 

Code (csharp):

1.  
2.     Mesh ClearBlanks(Mesh mesh)
3.     {
4.         int[] triangles = mesh.triangles;
5.         Vector3[] vertices = mesh.vertices;
6.         Vector2[] uv = mesh.uv;
7.         Vector3[] normals = mesh.normals;
8.         List<Vector3> vertList = vertices.ToList();
9.         List<Vector2> uvList = uv.ToList();
10.         List<Vector3> normalsList = normals.ToList();
11.         List<int> trianglesList = triangles.ToList();
12.  
13.         int testVertex = 0;
14.  
15.         while (testVertex < trianglesList.Count)
16.         {
17.             if (trianglesList.Contains(testVertex))
18.             {
19.                 Debug.Log(testVertex);
20.                 testVertex++;
21.             }
22.             else
23.             {
24.                 vertList.RemoveAt(testVertex);
25.                 uvList.RemoveAt(testVertex);
26.                 normalsList.RemoveAt(testVertex);
27.                 for (int i = 0; i < trianglesList.Count; i++)
28.                 {
29.                     if (trianglesList[i] > testVertex)
30.                         trianglesList[i]--;
31.                 }
32.             }
33.         }
34.  
35.         triangles = trianglesList.ToArray();
36.         vertices = vertList.ToArray();
37.         uv = uvList.ToArray();
38.         normals = normalsList.ToArray();
39.      
40.         mesh.triangles = triangles;
41.         mesh.vertices = vertices;
42.         mesh.uv = uv;
43.         mesh.normals = normals;
44.         return mesh;
45.     }
46.  

right now, this returns an empty mesh. See any errors? I'll try to fix it.

(update) Okay. Made a lot of stupid mistakes. Must be tired. Here is an updated code, some of the vertices from the shape are being deleted though none outside seem to be deleted.

(another update) Now I get the error argument is out of range.

Code (csharp):

1.  
2.         while (testVertex < trianglesList.Count)
3.         {
4.             if (trianglesList.Contains(testVertex))
5.             {
6.                 Debug.Log(testVertex);
7.                 testVertex++;
8.             }
9.             else
10.             {
11.                 vertList.RemoveAt(testVertex);
12.                 uvList.RemoveAt(testVertex);
13.                 normalsList.RemoveAt(testVertex);
14.                 trianglesList.RemoveAt(testVertex);
15.                 for (int i = 0; i < trianglesList.Count; i++)
16.                 {
17.                     if (trianglesList[i] > testVertex)
18.                         trianglesList[i]--;
19.                 }
20.             }
21.         }
22.  

This code runs but the wrong vertices are removed.

 

Code (csharp):

1.  
2.     Mesh ClearBlanks(Mesh mesh)
3.     {
4.         int[] triangles = mesh.triangles;
5.         Vector3[] vertices = mesh.vertices;
6.         Vector2[] uv = mesh.uv;
7.         Vector3[] normals = mesh.normals;
8.         List<Vector3> vertList = vertices.ToList();
9.         List<Vector2> uvList = uv.ToList();
10.         List<Vector3> normalsList = normals.ToList();
11.         List<int> trianglesList = triangles.ToList();
12.  
13.         int testVertex = 0;
14.  
15.         while (testVertex < vertList.Count)
16.         {
17.             if (trianglesList.Contains(testVertex))
18.             {
19.                 Debug.Log(testVertex);
20.                 testVertex++;
21.             }
22.             else
23.             {
24.                 vertList.RemoveAt(testVertex);
25.                 uvList.RemoveAt(testVertex);
26.                 normalsList.RemoveAt(testVertex);
27.  
28.                 for (int i = 0; i < trianglesList.Count; i++)
29.                 {
30.                     if (trianglesList[i] > testVertex)
31.                         trianglesList[i]--;
32.                 }
33.             }
34.         }
35.  
36.         triangles = trianglesList.ToArray();
37.         vertices = vertList.ToArray();
38.         uv = uvList.ToArray();
39.         normals = normalsList.ToArray();
40.        
41.         mesh.triangles = triangles;
42.         mesh.vertices = vertices;
43.         mesh.uv = uv;
44.         mesh.normals = normals;
45.         return mesh;
46.     }
47.  

 

That last attempt looks right. Is it working?

(Edit: Just noticed you changed the title to solved. Glad you got it working!)

 

Yeah! Works great.

 

For the following code is optimized huge meshes

Code (CSharp):

1.     void ClearUnusedVerticesOfMesh(Mesh mesh)
2.     {
3.         try
4.         {
5.             int[] triangles = mesh.triangles;
6.             Vector3[] vertices = mesh.vertices;
7.             Vector2[] uv = mesh.uv;
8.             Vector3[] normals = mesh.normals;
9.  
10.             List<Vector3> vertList = vertices.ToList();
11.             List<Vector2> uvList = uv.ToList();
12.             List<Vector3> normalsList = normals.ToList();
13.  
14.             var v3unused = new Vector3(float.MinValue, float.MinValue, float.MinValue);
15.             var v2unused = new Vector2(float.MinValue, float.MinValue);
16.  
17.             // fill pointer array with used indecise
18.             var verIndecise = Enumerable.Repeat(-1, vertices.Length).ToArray();
19.             for (int i = 0; i < triangles.Length; i++)
20.             {
21.                 verIndecise[triangles] = triangles;
22.             }
23.  
24.             // remove unused pointers and adjust
25.             var idx = 0;
26.             for (int i = 0; i < verIndecise.Length; i++)
27.             {
28.                 if (verIndecise == -1)
29.                 {
30.                     // mark for removal
31.                     vertList = v3unused;
32.                     uvList = v2unused;
33.                     normalsList = v3unused;
34.  
35.                     continue;
36.                 }
37.                 // used index
38.                 verIndecise = idx;
39.                 // assign next index
40.                 idx++;
41.             }
42.  
43.             // adjust triangle
44.             for (int i = 0; i < triangles.Length; i++)
45.             {
46.                 triangles = verIndecise[triangles];
47.             }
48.  
49.             // remove unused
50.             vertList.RemoveAll(it => it == v3unused);
51.             normalsList.RemoveAll(it => it == v3unused);
52.             uvList.RemoveAll(it => it == v2unused);
53.  
54.             if (vertList.Count != idx)
55.             {
56.                 Debug.LogError($"vertices count {vertList.Count} not equal to pointer list count {idx}");
57.             }
58.  
59.  
60.             // must be set again
61.             mesh.triangles = triangles.ToArray();
62.             mesh.vertices = vertList.ToArray();
63.             mesh.uv = uvList.ToArray();
64.             mesh.normals = normalsList.ToArray();
65.         }
66.         catch (System.Exception ex)
67.         {
68.             Debug.LogException(ex);
69.         }
70.     }

 

Besides that fact that your code does not compile because it seems the code is missing some

[i]

(did you post it without code tags first?), this approach isn't that optimised as well. Yes, it avoids the O(n²) nature of the original approach, but instead you're using some shady techniques like magic values. Since the position of the vertices would not stay as we remove vertices, there's not really any benefit keeping the exact vertex order (without the ones we want to remove). It would be way simpler to just rebuild the vertices from the triangles and just keep track of the new mapping.

This should be better both, performance wise and memory wise.

Code (CSharp):

1.     public static void RemoveUnusedVertices(Mesh aMesh)
2.     {
3.         Vector3[] vertices = aMesh.vertices;
4.         Vector3[] normals = aMesh.normals;
5.         Vector4[] tangents = aMesh.tangents;
6.         Vector2[] uv = aMesh.uv;
7.         Vector2[] uv2 = aMesh.uv2;
8.         int[] triangles = aMesh.triangles;
9.  
10.         Dictionary<int, int> vertMap = new Dictionary<int, int>(vertices.Length);
11.  
12.         List<Vector3> newVerts = new List<Vector3>(vertices.Length);
13.         List<Vector3> newNormals = new List<Vector3>(vertices.Length);
14.         List<Vector4> newTangents = new List<Vector4>(vertices.Length);
15.         List<Vector2> newUV = new List<Vector2>(vertices.Length);
16.         List<Vector2> newUV2 = new List<Vector2>(vertices.Length);
17.  
18.         System.Func<int, int> remap = (int aIndex) => {
19.             int res = -1;
20.             if (!vertMap.TryGetValue(aIndex, out res))
21.             {
22.                 res = newVerts.Count;
23.                 vertMap.Add(aIndex, res);
24.                 newVerts.Add(vertices[aIndex]);
25.                 if (normals != null && normals.Length > 0)
26.                     newNormals.Add(normals[aIndex]);
27.                 if (tangents != null && tangents.Length > 0)
28.                     newTangents.Add(tangents[aIndex]);
29.                 if (uv != null && uv.Length > 0)
30.                     newUV.Add(uv[aIndex]);
31.                 if (uv2 != null && uv2.Length > 0)
32.                     newUV2.Add(uv2[aIndex]);
33.             }
34.             return res;
35.         };
36.  
37.         for (int i = 0; i < triangles.Length; i++)
38.         {
39.             triangles[i] = remap(triangles[i]);
40.         }
41.         aMesh.Clear();
42.         aMesh.SetVertices(newVerts);
43.         if (newNormals.Count > 0)
44.             aMesh.SetNormals(newNormals);
45.         if (newTangents.Count > 0)
46.             aMesh.SetTangents(newTangents);
47.         if (newUV.Count > 0)
48.             aMesh.SetUVs(0, newUV);
49.         if (newUV2.Count > 0)
50.             aMesh.SetUVs(1, newUV2);
51.         aMesh.triangles = triangles;
52.     }

Note this still does not work with "all" kinds of meshes as it only looks at the uv channel 1 and 2. Also it does not care about boneWeights and bindposes at the moment. So if this is an animated mesh you would need to take them into account as well. Same goes with meshes with submeshes or other topologies. This would make the method exponentially more complex.

All this does is iterating through the triangles array and for each vertex it encounters it simply adds the vertex to a new list (/ lists) and remembers this mapping so if another shared vertex is hit, it will properly reuse the new index. At the end of this the new vertices lists now only contain the used vertices and since the internal "Remap" method does inplace adjust the index, the triangle array is also fixed already.

It excludes vertex attributes which are not present (normals, tangents and uv coordinates). Keep in mind that Unity now support up to 8 UV channels. Also technically UV coordinates could be Vector3 or Vector4 values as well. Unity does have the proper GetUVs / SetUVs methods, however it would be difficult to create propert code path for all possible combinations. GetVertexAttributeDimension can now be used to figure out the dimensionality of uv coordinates. Though that would require the code to use different Lists. If a general purpose method should be created, it probably makes more sense to access the raw vertex buffer.

 

Your Code does not work.
It works if line 34 is

Code (CSharp):

1. return res;

not

Code (CSharp):

1. return aIndex;

 

I 've built another solution which is mainly "remapping" the existing vertices/triangles and put them into new arrays. An execution takes about 1sec for ~300 meshes with ~55k vertices each and ~500 triangles on average:

Code (CSharp):

1.  
2.         /// <summary>
3.         /// This method is quite complex. What we do is:
4.         /// We use all the vertices from every mesh and check which ones are used in our submesh (aka are triangles using a vertex?)
5.         /// We create a new Vertices list and Triangles list based on our changes.
6.         /// Check the code for technical details.
7.         ///
8.         /// Example:
9.         ///     vertices  => 0=[...], 1=[...], 2=[...]
10.         ///     triangles => 0=4, 1=5, 2=8, 3=1, 4=1
11.         ///  
12.         ///     distinctOrderedTriangles => 0=1, 1=4, 2=5, 3=8
13.         ///  
14.         ///     newVertexTriangleMapping => 1=0, 4=1, 5=2, 8=3
15.         ///  
16.         ///     newVertices  => 0=[...], 1=[...], 2=[...]
17.         ///     newTriangles => 0=1, 1=0, 2=3, 3=0, 4=0 <-- values are replaced with new mapping
18.         /// </summary>
19.         private void _PrepareMeshFilter(MeshFilter meshFilter, PCBridge_World world, int materialIndex)
20.         {
21.             var vertices = world.vertices;
22.             var triangles = world.triangles[materialIndex];
23.  
24.             var mesh = new Mesh();
25.             meshFilter.mesh = mesh;
26.  
27.             // Distinct -> We only want to check vertex-indices once for adding to the new mapping
28.             // Ordered -> We need to check from lowest used vertex-index to highest for the new mapping
29.             List<int> distinctOrderedTriangles = triangles.Distinct().OrderBy(val => val).ToList();
30.             Dictionary<int, int> newVertexTriangleMapping = new();
31.             List<Vector3> newVertices = new();
32.  
33.             // Loop through all the distinctOrderedTriangles
34.             for (int i=0; i<distinctOrderedTriangles.Count; i++)
35.             {
36.                 // curVertexIndex == currently lowest vertex index in this loop
37.                 int curVertexIndex = distinctOrderedTriangles[i];
38.                 Vector3 vertexAtIndex = vertices[curVertexIndex];
39.  
40.                 // Previously index of vertex is now the new index of loop's >i<.
41.                 // This Dictionary will be used to >replace< the original triangle values later.
42.                 // e.g. previous Vertex-index=5 (key) is now the Vertex-index=0 (value)
43.                 newVertexTriangleMapping.Add(curVertexIndex, i);
44.  
45.                 // Add the vertex which was found as new lowest entry
46.                 // e.g. Vertex-index=5 is now Vertex-index=0
47.                 newVertices.Add(vertexAtIndex);
48.             }
49.  
50.             // Now we replace the triangle values. aka the vertex-indices (value old) with new >mapping< from Dictionary.
51.             var newTriangles = triangles.Select(originalVertexIndex => newVertexTriangleMapping[originalVertexIndex]);
52.  
53.             mesh.vertices = newVertices.ToArray();
54.             mesh.triangles = newTriangles.ToArray();
55.         }
56.  

 

In case anyone find this helpful, I needed the removal of unused vertices to work with submeshes. I have a lot of multi material meshes in my project, so this is the ideal solution for me. I adapted turndapage's method for this purpose.

I don't need to keep track of uv's or normals so this solution is simply for vertex removal.

I have briefly tested it, but it might have some issues I am not aware of at this stage.

Code (CSharp):

1. public static class UnusedVertexDeleter
2. {
3.     /// <summary>
4.     /// Removes all unused vertices in the mesh, while keeping track of submeshes.
5.     /// </summary>
6.     /// <returns>Modified mesh with the unused vertices removed.</returns>
7.     public static Mesh RemoveUnusedVerticesSubMeshAware(Mesh mesh)
8.     {
9.         // Store the triangles for each submesh in a 2D array.
10.         int[][] submeshTriangles = new int[mesh.subMeshCount][];
11.         for (int i = 0; i < mesh.subMeshCount; i++)
12.         {
13.             submeshTriangles[i] = mesh.GetTriangles(i);
14.         }
15.  
16.         // Store the vertices in a list for easy removal of unused vertices.
17.         Vector3[] vertices = mesh.vertices;
18.         List<Vector3> vertList = new List<Vector3>(vertices);
19.         int vertexCount = vertices.Length;
20.  
21.         // Loop through all vertices in the mesh.
22.         int testVertex = 0;
23.         while (testVertex < vertexCount)
24.         {
25.             // Check if the vertex is used in any submesh.
26.             bool usedBySubmesh = false;
27.             for (int submeshIndex = 0; submeshIndex < mesh.subMeshCount; submeshIndex++)
28.             {
29.                 int[] triangles = submeshTriangles[submeshIndex];
30.                 for (int i = 0; i < triangles.Length; i++)
31.                 {
32.                     if (triangles[i] == testVertex)
33.                     {
34.                         usedBySubmesh = true;
35.                         break;
36.                     }
37.                 }
38.  
39.                 if (usedBySubmesh)
40.                 {
41.                     break;
42.                 }
43.             }
44.  
45.             // Remove the vertex if it is not used by any submesh.
46.             // Update the indices of any triangles affected by the removal.
47.             if (usedBySubmesh)
48.             {
49.                 testVertex++;
50.             }
51.             else
52.             {
53.                 vertList.RemoveAt(testVertex);
54.                 vertexCount--;
55.  
56.                 for (int submeshIndex = 0; submeshIndex < mesh.subMeshCount; submeshIndex++)
57.                 {
58.                     int[] triangles = submeshTriangles[submeshIndex];
59.                     for (int i = 0; i < triangles.Length; i++)
60.                     {
61.                         if (triangles[i] > testVertex)
62.                         {
63.                             triangles[i]--;
64.                         }
65.                     }
66.  
67.                     mesh.SetTriangles(triangles, submeshIndex);
68.                 }
69.             }
70.         }
71.  
72.         // Update the mesh with the new vertices and bounds.
73.         mesh.vertices = vertList.ToArray();
74.         mesh.RecalculateBounds();
75.  
76.         return mesh;
77.     }
78. }

 

Well, it's horribly inefficient. If you have say 100000 vertices and several submeshes with say around 30000 triangles, your inner loop logic would run 9000000000 times.

The method I posted above would be way faster as we only iterate through the triangles once and just collect and redistribute the used vertices. Of course when you have submeshes you would simply iterate through the submeshes indices instead of the triangles array, that's all. Since we use a dictionary to map the vertices, it means shared vertices will stay shared vertices.

Here's a version that should work with arbitrary submeshes with any kind of topology, not just triangle meshes.

Code (CSharp):

1.     public static void RemoveUnusedVertices(Mesh aMesh)
2.     {
3.         Vector3[] vertices = aMesh.vertices;
4.         Vector3[] normals = aMesh.normals;
5.         Vector4[] tangents = aMesh.tangents;
6.         Vector2[] uv = aMesh.uv;
7.         Vector2[] uv2 = aMesh.uv2;
8.         List<int> indices = new List<int>();
9.  
10.         Dictionary<int, int> vertMap = new Dictionary<int, int>(vertices.Length);
11.  
12.         List<Vector3> newVerts = new List<Vector3>(vertices.Length);
13.         List<Vector3> newNormals = new List<Vector3>(vertices.Length);
14.         List<Vector4> newTangents = new List<Vector4>(vertices.Length);
15.         List<Vector2> newUV = new List<Vector2>(vertices.Length);
16.         List<Vector2> newUV2 = new List<Vector2>(vertices.Length);
17.  
18.         System.Func<int, int> remap = (int aIndex) => {
19.             int res = -1;
20.             if (!vertMap.TryGetValue(aIndex, out res))
21.             {
22.                 res = newVerts.Count;
23.                 vertMap.Add(aIndex, res);
24.                 newVerts.Add(vertices[aIndex]);
25.                 if (normals != null && normals.Length > 0)
26.                     newNormals.Add(normals[aIndex]);
27.                 if (tangents != null && tangents.Length > 0)
28.                     newTangents.Add(tangents[aIndex]);
29.                 if (uv != null && uv.Length > 0)
30.                     newUV.Add(uv[aIndex]);
31.                 if (uv2 != null && uv2.Length > 0)
32.                     newUV2.Add(uv2[aIndex]);
33.             }
34.             return res;
35.         };
36.         for (int subMeshIndex = 0; subMeshIndex < aMesh.subMeshCount; subMeshIndex++)
37.         {
38.             var topology = aMesh.GetTopology(subMeshIndex);
39.             indices.Clear();
40.             aMesh.GetIndices(indices, subMeshIndex);
41.             for (int i = 0; i < indices.Count; i++)
42.             {
43.                 indices[i] = remap(indices[i]);
44.             }
45.             aMesh.SetIndices(indices, topology, subMeshIndex);
46.         }
47.         aMesh.SetVertices(newVerts);
48.         if (newNormals.Count > 0)
49.             aMesh.SetNormals(newNormals);
50.         if (newTangents.Count > 0)
51.             aMesh.SetTangents(newTangents);
52.         if (newUV.Count > 0)
53.             aMesh.SetUVs(0, newUV);
54.         if (newUV2.Count > 0)
55.             aMesh.SetUVs(1, newUV2);
56.     }

Though this is currently limited to UV channel 0 and 1, we now have up to 7 (8 in total) and another issue is that UVs don't have to be a Vector2. They can be Vector3 or Vector4 as well. Covering all those cases would make the code much more complex. For that it probably makes more sense to use one of the low level mesh data methods and treat a vertex like it is defined on the GPU. Unity now has a few options to manipulate the mesh data.

 

Yeah that makes sense! I'm mostly working with meshes with <50 vertices so performance was not my concern. That's fantastic, your approach looks great. Will give it a try to replace my previous approach.