How to detect separated parts in a mesh

Question

I have a mesh that consists of two submeshes. I want to select each submesh separately.

The problem with Unity-submeshes is you have to assign separate material-ids in the 3D program (such as Blender or 3dsMax). My submeshes however use the same material and the same texture space. I don't want to say to our artists that they have to assign different material ids every time a mesh is comprised of different separated parts. Instead I want to detect this myself with a script.

So what the script should do is very similar to the "select element" tool in 3dsMax: select a triangle, find all connected triangles, and return the triangle-list back to me.

Now I've tried this by -> 1. selecting the first vertex-id in the triangle-list -> 2. find the next two vertex-ids (so I've selected my triangle) -> 3. searching through the triangle-list of other triangles contain at least one of the vertex-ids in my selected triangle(s) -> 4. add those triangles to my selected triangles-list -> 5. repeat step 3 and 4 until I get no more feedback

This method however returns only parts of a submesh for me, cutting submeshes on (mostly) hard edges. This is logical, as hard edges create two separate vertices with distinct normals. However, there should be a method to detect this. How would 3dsMax or Blender otherwise be able to do this?

Answer 1

@Syndias you have the right approach. My only guess is that there is a bug in your implementation, maybe you aren't recursively checking all of the connected faces found?

I just had to solve this problem for myself as well, here is the solution I just posted on my blog (more detailed explanation there and also editor code for picking faces in the scene view). http://dantefalcone.name/finding-linked-faces-elements-within-a-3d-model-mesh-with-unity3d-and-c/

 /// <summary>
 /// Given two faces, return whether they share any common vertices.
 /// </summary>
 /// <param name="faceA">Face represented as array of vertex indices.</param>
 /// <param name="faceB">Face represented as array of vertex indices.</param>
 /// <returns>bool - whether the faces are connected. </returns>
 bool IsConnected(int[] faceA, int[] faceB)
 {
     for (int i = 0; i < faceA.Length; i++)
         for (int j = 0; j < faceB.Length; j++)
             if (faceA[i] == faceB[j])
                 return true;
     return false;
 }

 /// <summary>
 /// Given a single triangle face of vertex indices, 
 /// returns a list of all the vertices of all linked faces.
 /// </summary>
 /// <param name="pickedTriangle">The known triangle to find linked faces from.</param>
 /// <param name="triangles">The index buffer triangle list of all vertices in the mesh.</param>
 /// <returns>List<int> - List of all the triangle face indices that represent the surface element.</returns>
 public List<int> GetElement(int[] pickedTriangle, List<int> triangles)
 {
     // Create the return result list, starting with the current picked face
     List<int> result = new List<int>(pickedTriangle);
  
     // Iterate through the triangle list index buffer by triangle (iterations of 3)
     for (int i = 0; i < triangles.Count; i += 3)
     {
         // Select the (i)th triangle in the index buffer
         int[] curTriangle = new int[3] { triangles[i], triangles[i + 1], triangles[i + 2] };
  
         // Check if faces are linked
         if (IsConnected(curTriangle, pickedTriangle))
         {
             // Recursively add all the linked faces to the result
             result.AddRange(GetElement(curTriangle, triangles));
         }
     }
  
     return result;
 }

Answer 2

Ok, I can be a bit later, but I've written a method that does it and I wanna share it. So, basically It returns a list with all vertices indices connected to the vertexId (including itselft).

  public List<int> GetConnectedVertices(int vertexId, out Vector3 centerOfMass, int[] triangles, Vector3[] vertices) {
       var result = new List<int>(vertices.Length);
       var selectedVertices = new bool[vertices.Length];
       var ignoreTriangles = new bool[triangles.Length / 3];

       var v = new int[3]; 
 
       selectedVertices[vertexId] = true;
       result.Add(vertexId);
 
       centerOfMass = new Vector3();
 
       bool isSearching = true;
       while (isSearching) {
 
          isSearching = false;
 
          for (int i = 0; i < triangles.Length; i += 3) {
 
             if (ignoreTriangles [i / 3]) {
                continue;
             }
 
             v[0] = triangles[i];
             v[1] = triangles[i + 1];
             v[2] = triangles[i + 2];
 
             if (selectedVertices[v[0]] || selectedVertices[v[1]] || selectedVertices[v[2]]) {
                for (int j = 0; j < 3; j++) {
                   if (!selectedVertices[v[j]]) {
                      result.Add(v[j]);
                      centerOfMass += vertices[v[j]];
 
                      selectedVertices[v[j]] = true;
                      isSearching = true;
                   }
                }
                ignoreTriangles [i / 3] = true;
             }
          }
 
          if (!isSearching) {
             break;
          }
 
          for (int i = 0; i < vertices.Length; i++) {
             for (int j = i + 1; j < vertices.Length; j++) {
                if (selectedVertices[j] != selectedVertices[i]) {
                   if ((vertices[i] - vertices[j]).sqrMagnitude < 0.00001f) {
                      selectedVertices[j] = selectedVertices[i] = true;
                   }
                }
             }
          }
       }
 
       centerOfMass /= result.Count;
 
       return result;
    }

How to detect separated parts in a mesh

2 Replies

Your answer

Follow this Question

Related Questions