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:
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.
Store ātrianglesā, āverticesā, āuvā, and ānormalsā as List, List, or List as appropriate.
Set testVertex to 0.
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++
Convert the Lists to Arrays and assign them back to the mesh.
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.
while (testVertex < trianglesList.Count)
{
if (trianglesList.Contains(testVertex))
{
Debug.Log(testVertex);
testVertex++;
}
else
{
vertList.RemoveAt(testVertex);
uvList.RemoveAt(testVertex);
normalsList.RemoveAt(testVertex);
trianglesList.RemoveAt(testVertex);
for (int i = 0; i < trianglesList.Count; i++)
{
if (trianglesList[i] > testVertex)
trianglesList[i]--;
}
}
}
This code runs but the wrong vertices are removed.
Besides that fact that your code does not compile because it seems the code is missing some * (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. ```csharp
Dictionary<int, int> vertMap = new Dictionary<int, int>(vertices.Length);
List newVerts = new List(vertices.Length);
List newNormals = new List(vertices.Length);
List newTangents = new List(vertices.Length);
List newUV = new List(vertices.Length);
List newUV2 = new List(vertices.Length);
System.Func<int, int> remap = (int aIndex) => {
int res = -1;
if (!vertMap.TryGetValue(aIndex, out res))
{
res = newVerts.Count;
vertMap.Add(aIndex, res);
newVerts.Add(vertices[aIndex]);
if (normals != null && normals.Length > 0)
newNormals.Add(normals[aIndex]);
if (tangents != null && tangents.Length > 0)
newTangents.Add(tangents[aIndex]);
if (uv != null && uv.Length > 0)
newUV.Add(uv[aIndex]);
if (uv2 != null && uv2.Length > 0)
newUV2.Add(uv2[aIndex]);
}
return res;
};
for (int i = 0; i < triangles.Length; i++)
{
triangles[i] = remap(triangles[i]);
}
aMesh.Clear();
aMesh.SetVertices(newVerts);
if (newNormals.Count > 0)
aMesh.SetNormals(newNormals);
if (newTangents.Count > 0)
aMesh.SetTangents(newTangents);
if (newUV.Count > 0)
aMesh.SetUVs(0, newUV);
if (newUV2.Count > 0)
aMesh.SetUVs(1, newUV2);
aMesh.triangles = triangles;
}* ``` 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.
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:
/// <summary>
/// This method is quite complex. What we do is:
/// We use all the vertices from every mesh and check which ones are used in our submesh (aka are triangles using a vertex?)
/// We create a new Vertices list and Triangles list based on our changes.
/// Check the code for technical details.
///
/// Example:
/// vertices => 0=[...], 1=[...], 2=[...]
/// triangles => 0=4, 1=5, 2=8, 3=1, 4=1
///
/// distinctOrderedTriangles => 0=1, 1=4, 2=5, 3=8
///
/// newVertexTriangleMapping => 1=0, 4=1, 5=2, 8=3
///
/// newVertices => 0=[...], 1=[...], 2=[...]
/// newTriangles => 0=1, 1=0, 2=3, 3=0, 4=0 <-- values are replaced with new mapping
/// </summary>
private void _PrepareMeshFilter(MeshFilter meshFilter, PCBridge_World world, int materialIndex)
{
var vertices = world.vertices;
var triangles = world.triangles[materialIndex];
var mesh = new Mesh();
meshFilter.mesh = mesh;
// Distinct -> We only want to check vertex-indices once for adding to the new mapping
// Ordered -> We need to check from lowest used vertex-index to highest for the new mapping
List<int> distinctOrderedTriangles = triangles.Distinct().OrderBy(val => val).ToList();
Dictionary<int, int> newVertexTriangleMapping = new();
List<Vector3> newVertices = new();
// Loop through all the distinctOrderedTriangles
for (int i=0; i<distinctOrderedTriangles.Count; i++)
{
// curVertexIndex == currently lowest vertex index in this loop
int curVertexIndex = distinctOrderedTriangles[i];
Vector3 vertexAtIndex = vertices[curVertexIndex];
// Previously index of vertex is now the new index of loop's >i<.
// This Dictionary will be used to >replace< the original triangle values later.
// e.g. previous Vertex-index=5 (key) is now the Vertex-index=0 (value)
newVertexTriangleMapping.Add(curVertexIndex, i);
// Add the vertex which was found as new lowest entry
// e.g. Vertex-index=5 is now Vertex-index=0
newVertices.Add(vertexAtIndex);
}
// Now we replace the triangle values. aka the vertex-indices (value old) with new >mapping< from Dictionary.
var newTriangles = triangles.Select(originalVertexIndex => newVertexTriangleMapping[originalVertexIndex]);
mesh.vertices = newVertices.ToArray();
mesh.triangles = newTriangles.ToArray();
}
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.
public static class UnusedVertexDeleter
{
/// <summary>
/// Removes all unused vertices in the mesh, while keeping track of submeshes.
/// </summary>
/// <returns>Modified mesh with the unused vertices removed.</returns>
public static Mesh RemoveUnusedVerticesSubMeshAware(Mesh mesh)
{
// Store the triangles for each submesh in a 2D array.
int[][] submeshTriangles = new int[mesh.subMeshCount][];
for (int i = 0; i < mesh.subMeshCount; i++)
{
submeshTriangles[i] = mesh.GetTriangles(i);
}
// Store the vertices in a list for easy removal of unused vertices.
Vector3[] vertices = mesh.vertices;
List<Vector3> vertList = new List<Vector3>(vertices);
int vertexCount = vertices.Length;
// Loop through all vertices in the mesh.
int testVertex = 0;
while (testVertex < vertexCount)
{
// Check if the vertex is used in any submesh.
bool usedBySubmesh = false;
for (int submeshIndex = 0; submeshIndex < mesh.subMeshCount; submeshIndex++)
{
int[] triangles = submeshTriangles[submeshIndex];
for (int i = 0; i < triangles.Length; i++)
{
if (triangles[i] == testVertex)
{
usedBySubmesh = true;
break;
}
}
if (usedBySubmesh)
{
break;
}
}
// Remove the vertex if it is not used by any submesh.
// Update the indices of any triangles affected by the removal.
if (usedBySubmesh)
{
testVertex++;
}
else
{
vertList.RemoveAt(testVertex);
vertexCount--;
for (int submeshIndex = 0; submeshIndex < mesh.subMeshCount; submeshIndex++)
{
int[] triangles = submeshTriangles[submeshIndex];
for (int i = 0; i < triangles.Length; i++)
{
if (triangles[i] > testVertex)
{
triangles[i]--;
}
}
mesh.SetTriangles(triangles, submeshIndex);
}
}
}
// Update the mesh with the new vertices and bounds.
mesh.vertices = vertList.ToArray();
mesh.RecalculateBounds();
return mesh;
}
}
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.
public static void RemoveUnusedVertices(Mesh aMesh)
{
Vector3[] vertices = aMesh.vertices;
Vector3[] normals = aMesh.normals;
Vector4[] tangents = aMesh.tangents;
Vector2[] uv = aMesh.uv;
Vector2[] uv2 = aMesh.uv2;
List<int> indices = new List<int>();
Dictionary<int, int> vertMap = new Dictionary<int, int>(vertices.Length);
List<Vector3> newVerts = new List<Vector3>(vertices.Length);
List<Vector3> newNormals = new List<Vector3>(vertices.Length);
List<Vector4> newTangents = new List<Vector4>(vertices.Length);
List<Vector2> newUV = new List<Vector2>(vertices.Length);
List<Vector2> newUV2 = new List<Vector2>(vertices.Length);
System.Func<int, int> remap = (int aIndex) => {
int res = -1;
if (!vertMap.TryGetValue(aIndex, out res))
{
res = newVerts.Count;
vertMap.Add(aIndex, res);
newVerts.Add(vertices[aIndex]);
if (normals != null && normals.Length > 0)
newNormals.Add(normals[aIndex]);
if (tangents != null && tangents.Length > 0)
newTangents.Add(tangents[aIndex]);
if (uv != null && uv.Length > 0)
newUV.Add(uv[aIndex]);
if (uv2 != null && uv2.Length > 0)
newUV2.Add(uv2[aIndex]);
}
return res;
};
for (int subMeshIndex = 0; subMeshIndex < aMesh.subMeshCount; subMeshIndex++)
{
var topology = aMesh.GetTopology(subMeshIndex);
indices.Clear();
aMesh.GetIndices(indices, subMeshIndex);
for (int i = 0; i < indices.Count; i++)
{
indices[i] = remap(indices[i]);
}
aMesh.SetIndices(indices, topology, subMeshIndex);
}
aMesh.SetVertices(newVerts);
if (newNormals.Count > 0)
aMesh.SetNormals(newNormals);
if (newTangents.Count > 0)
aMesh.SetTangents(newTangents);
if (newUV.Count > 0)
aMesh.SetUVs(0, newUV);
if (newUV2.Count > 0)
aMesh.SetUVs(1, newUV2);
}
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.