Convert a mesh to a graph

Questions & Answers
1

Dear Unity users,

I’ll need to represent my mesh as a graph G=(V, E), with V the vertices and E edges. Right now I’m iterating over the mesh’s triangles, using the triangle index to access the vertices by their indices (id, id+1, id+2) and then I store the connectivity in an adjacency list. Is there any other (Potentially faster) way how I could convert my mesh into a graph representation?

I aim for large meshes, e.g. with > 1,000,000 edges. The access to mesh.vertices (I have to iterate at least once over this array seems slow) seems slow.

Here comes the code (Abridged version):

   Vector3[] localVerts = mesh.vertices;
   int[] localTris = mesh.triangles;
   List<Edge> edges = new List<Edge>();

    for (int i = 0; i < mesh.triangles.Length; i += 3)
    {
         int v1 = localVerts[localTris[i+0]];
         int v2 = localVerts[localTris[i+1]];
         int v3 = localVerts[localTris[i+2]];

         edges.Add(new Edge(v1, v2));
         edges.Add(new Edge(v2, v3));
         edges.Add(new Edge(v3, v1));

         edges.Add(new Edge(v2, v1));
         edges.Add(new Edge(v3, v2));
         edges.Add(new Edge(v1, v3));
     }
        
     return edges;

Edge is a small class and I read from the CLR that instantiation takes a few nanoseconds. However the loop is slow starting from Meshes with > 1 M edges. I know see the problem, I should move the mesh.triangles.Length out of the loop’s for-init statement, correct?

Like this:

 int size = mesh.triangles.Length;
 for (int i = 0; i < size; i += 3)
  {
     ///  copy old code here from above
  }

Edit: To address your main question why I want to create the graph: I need the user to pick an arbitrary point on the mesh (This we implemented by touching the mesh with the Avatar’s index finger). Then I need to find the nearest neighbouring vertices connected to the user-selected vertex. The mesh is provided also by the user and is stored in .obj format, then imported into Unity, and then a vertex will be selected by the user to start the process. Therefore a graph algorithm seems best, because I need to make sure, the vertices are reachable via an edge and below a distance threshold.

2

No, there’s no other way than reading the triangles. A mesh is only made up of vertices and triangles and does already represent a graph, just that it contains always “triple edge loops”. What’s exactly the issue when working with 1M+ edges? If you have already some issues with some code you’ve written you should have included that code. Maybe you did something extremely inefficient (like accessing the mesh.triangles or mesh.vertices properties in a loop). Those properties will allocate a temporary array each time you access them. So you have to store those arrays in variables.

If the data you’re working on does not resemble an actual Mesh, why do you actually use a mesh in the first place? Note that Unity also supports line meshes as well as some other topographies