Vertices, faces -> adjacency list

Scripting
1

Hi

I need help with a graph problem. What is the fastest way to convert a obj style mesh information (list of vertices, list of faces) into an adjacency list (for every mesh node a list of integers indicating all the nodes that node shares edges with)? My first approach is:

  • to first get all the single edges (startIndexNode, endIndexNode)
  • delete the duplicates using a nested for loop
  • loop over nodes and compare all edges (startIndexNode, endIndexNode) with the node index

This is expensive and takes way to long. What is a good strategy for this graph problem? Any help is very much appreciated.

M

2

This is what I have so far. Way too slow!
Sorry, I am new to python and just translated this from vbs.

def GetTriEN(Vertices):
    allEdges = []
    TriEInd = []
    for i in range(len(Vertices)):
        allEdges.append([Vertices[i][0],Vertices[i][1]])
        allEdges.append([Vertices[i][1],Vertices[i][2]])
        allEdges.append([Vertices[i][2],Vertices[i][0]])
    for i in range(len(allEdges)):
        blnDup = False
        for j in range(i+1,len(allEdges)):
            if ((allEdges[i][0] == allEdges[j][1]) and (allEdges[i][1] == allEdges[j][0])) or ((allEdges[i][0] == allEdges[j][0]) and (allEdges[i][1] == allEdges[j][1])):
                blnDup = True
                break
        if not blnDup:
            TriEInd.append(allEdges[i])
    return TriEInd
3

Hi Manuel,

have you tried to exchange range with xrange in your function?

Alternatively, you might be able to get the adjacent (connected) vertices and faces from a single vertex by using these methods:

GetConnectedVertices(vertexIndex) 
GetVertexFaces(vertexIndex)

Both belong to the MeshVertexList class.

c.

4

Thanks Clement! that’s great, I’ll take a look into this. Not experienced with RhinoCommon SDK in python. GetConnectedVertices(vertexIndex) is probably exactly what I need.

M

5

Hi Manuel,

take care of what it reports as connect and try it out using meshes which have unwelded or naked edges. I´ve been surprised by the outcome. You might be interested in

MeshTopologyEdges
MeshTopologyVertices

as well. Good Luck !

c.

6

Do the faces in this mesh have a limit of 3 or 4 vertices per face? -or- can there be an unlimited number of vertices per face? I’m asking because the 3 or 4 vertex case is easier to deal with since it maps to what our Mesh class currently supports in RhinoCommon

7

For now 3 vertices per face. But for future work it would be beneficial if the mesh class would support >4 vertices per face.
Thanks
M