Shared Edge of Adjacent Mesh Faces

rhinocommon
mesh

#1

Hi all,

Is there any method in Rhinocommon to access the shared edge between two adjacent mesh faces?
I can only seem to find methods for getting the ids of adjacent faces, but nothing further:

DataTree<int> f_id = new DataTree<int>();
    for(int i = 0; i < f_cnt; ++i){
      f_id.AddRange(m.Faces.AdjacentFaces(i), new GH_Path(i));
    }
}

Something like an iterator for adjacent faces would be great.

Thanks!


(qythium) #2

There is the GetConnectedFaces method of the MeshTopologyEdgeList collection, which you access through Mesh.TopologyEdges, is this what you are looking for?

Specificially, something like this

Mesh m;
for(int edge_id = 0; edge_id < m.TopologyEdges.Count; edge_id++){
  int[] faces = m.TopologyEdges.GetConnectedFaces(edge_id); 
  if (faces.Count() != 2) //Naked or non-manifold edge
    continue;


  Line edge = mesh.TopologyEdges.EdgeLine(edge_id);
  MeshFace face0 = m.Faces[faces[0]];
  MeshFace face1 = m.Faces[faces[1]];
}

#3

hi @qythium, thanks a lot!
i’d say what you suggested does find the adjacent faces of each edge,
but what i was looking for was kind of the opposite - the edges that are shared by adjacent faces.

below is what i come up with.
seems a bit cumbersome, so any advice to improve it is welcomed:

Mesh m;
int f_cnt = m.Faces.Count;
//adjacent face id of each mesh face
DataTree<int> f_fId = new DataTree<int>();
for(int i = 0; i < f_cnt; ++i){
  f_fId.AddRange(m.Faces.AdjacentFaces(i), new GH_Path(i));
}

//vertex ids of each face
DataTree<int> f_vId = new DataTree<int>();
for(int i = 0; i < f_cnt; ++i){
  f_vId.Add(m.Faces[i].A, new GH_Path(i));
  f_vId.Add(m.Faces[i].B, new GH_Path(i));
  f_vId.Add(m.Faces[i].C, new GH_Path(i));
  if(!m.Faces[i].IsTriangle) f_vId.Add(m.Faces[i].D, new GH_Path(i));
}

//a pair of vertex ids defining shared edge of each adjacent face
DataTree<IndexPair> f_eId_v = new DataTree<IndexPair>();
for(int i = 0; i < f_cnt; ++i){
  var f_adj = f_fId.Branch(i);
  for(int j = 0; j < f_adj.Count; ++j){
    var f_adj_v = f_vId.Branch(f_adj[j]);
    IndexPair ip_temp = new IndexPair();
    int ip_cnt = 0;
    for(int k = 0; k < f_adj_v.Count; ++k){
      if(f_vId.Branch(i).Contains(f_adj_v[k])){ //find common vertex ids
        ip_temp[ip_cnt] = f_adj_v[k];
        ip_cnt++;
      }
    }
    f_eId_v.Add(ip_temp, new GH_Path(f_adj[j]));
  }
}

//get ids of shared edges of adjacent faces, indexing correspond to adjacent face datatree
DataTree<int> f_eId = new DataTree<int>();
for(int i = 0; i < f_eId_v.BranchCount; ++i){
  for(int j = 0; j < f_eId_v.Branch(i).Count; ++j){
    int tv0 = m.TopologyVertices.TopologyVertexIndex(f_eId_v.Branch(i)[j][0]);
    int tv1 = m.TopologyVertices.TopologyVertexIndex(f_eId_v.Branch(i)[j][1]);
    int e = m.TopologyEdges.GetEdgeIndex(tv0, tv1);
    f_eId.Add(e, new GH_Path(i));
  }
} 

thanks!


(qythium) #4

Aren’t the two approaches functionally equivalent? You end up with a list of edges and the two faces bordering them.
Your version looks like it’s traversing the mesh in 3 nested inner loops, that will probably scale really badly (~O(n³)) for more complex meshes.


#5

you’re right - it’s definitely pretty inefficient.
so how would i transform the list of edges with the list of two faces bordering them to a list of faces with the list of shared edges with the same indexing?


(qythium) #6

I’m still not quite sure what you mean - do you need the faces to be in a particular order?
In my example code above you have 3 variables line, face0 and face1 for every iteration, you could add each of them to a respective List<T> within the loop and have the indices line up naturally.


#7

I guess the question could be simplified as the following, if to use the Edge loop method:

If the Edge List, list1, consists of Connected Faces indices such that

List<List<int>> list1 = new List<List<int>>();
list1[239] = [0, 1];
list1[238] = [0, 5];
list1[237] = [4, 1];
list1[236] = [5, 2];
list1[235] = [2, 3];
list1[234] = [5, 3];
list1[233] = [4];
//...etc.

then how could I make it into a Face List, list2, such that

list2 = [[239, 238], [239, 237], [236, 235], [235, 234], [237, 233], [238, 236, 234]];

where the integer values in the first list become the indices of the lists of integers in the second list, and the indices of the lists of integers in the first are the item values of the second.


(qythium) #8

Okay, I think I understand now - what you could do is initialize an array of Lists beforehand the size of the MeshFaceList, then write to it in arbitrary order.


List<int>[] faceEdges = new List<int>[m.Faces.Count]; 

for(int edgeId = 0; edgeId < m.TopologyEdges.Count; edgeId++){
    int[] faces = m.TopologyEdges.GetConnectedFaces(edgeId); 
    if (faces.Count() != 2) //Naked or non-manifold edge
        continue;

    foreach(int faceId in faces){
        if (faceEdges[faceId] == null){
            faceEdges[faceId] = new List<int>(){edgeId};
        }else{
            faceEdges[faceId].Add(edgeId);
        }
    }
}

Edit:
Thinking about it a little more, isn’t this equivalent to simply finding the non-naked edges of the mesh faces?
You could write that in a single LINQ query:

faceEdges = m.Faces.Select(
    (face, faceId) =>  m.TopologyEdges.GetEdgesForFace(faceId).Where(
        edgeId => (m.TopologyEdges.GetConnectedFaces(edgeId).Count() == 2)
    ).ToList()
).ToList();

Both the GetEdgesForFace and GetConnectedFaces function calls seem to be constant-time operations, so this should scale linearly with the number of faces.


#9

Amazing - thank you so much!

I’m not too familiar with all the syntaxes beyond the very basic, so just want to confirm with you if I understand correctly the foreach loop:
so the if conditional tests whether a list (within the array) exists/has already been created for the current face, and if not, create the list with this specific faceId as the index, and add the edgeId to the list, else (if the list exists in the array), simply add the edgeId?
I guess something I don’t understand is why the list is being tested whether it’s null or not? Haven’t you already created all the lists (although empty) in the beginning?

Regarding the LINQ method, what are the advantages besides the obvious, shorter code?
Also, is it always the equivalent of getting the non-naked edges?
I understand that the number of non-naked edges of a face is the equivalent of the number of adjacent faces, but how do we know if the orderings of the two lists returned by GetEdgesForFace (at where the count of GetConnectedFaces is 2) and AdjacentFaces are guaranteed to be the same?


(qythium) #10

Yup, you got it :slight_smile:
Declaring the array type at the start doesn’t instantiate the actual lists, since Lists are reference types in C#. Note the new keyword applies to the List[] array, not the List itself. So they will point to null by default unless instantiated.

I find LINQ expressions more readable (and fun to write ) personally, but they sometimes come at a bit of performance cost compared to a plain for loop - about 2x slower in this case, although both are O(n)
image

(no idea about the relative ordering of GetConnectedFaces and AdjacentFaces, that would involve the inner workings of RhinoCommon)


#11

thanks a lot again for the explanation - helped a lot!