TopologyVertices.ConnectedFaces in order?

Hi @dale,

i am trying to get all faces connected to a topological vertex, but in proper radial order, similar like i can query edges and vertices and control their radial order by pre-sorting using:

TopologyVertices.SortEdges()

So far i’ve tried to get ordered topology edges from the topology vertex first, then from the edges get face pairs using:

TopologyVertices.GetConnectedEdges(EdgeIndex, faceOrientationMatchesEdgeDirection)

Next i’ve tried to get a flat list from the faces, flipping pairs dependant on the face orientation, excluding duplicates while keeping order. Then i’ve found that my order is sometimes clockwise and sometimes not. There must be an easier way or ?

_
c.

You may want to SortEdges starting from each “center vertex” of a star which you are interested in. Otherwise you will have “intermingled” sequences of edges & connected vertices simply because a “global” sort cannot have all “stars” centered around all vertices.

image

Starting the sort from each vertex OTOH (SortEdges(int)) will sort every edge & connected vertex in a perfect star. This way of sorting will be slower though. On a big mesh it may be significantly slower.

https://developer.rhino3d.com/api/RhinoCommon/html/M_Rhino_Geometry_Collections_MeshTopologyVertexList_SortEdges_1.htm

Or, vertices:
https://developer.rhino3d.com/api/RhinoCommon/html/M_Rhino_Geometry_Collections_MeshTopologyVertexList_ConnectedTopologyVertices_1.htm

// Rolf

Hi Rolf, thanks for your reply. So far i’ve been using this, very slow, approach: I sort like this, which is fast:

mesh.TopologyVertices.SortEdges()

Then i iterate over all topology vertices. To get the edges connected to the topology vertex in proper order, i just use:

connected_edges = list(mesh.TopologyVertices.ConnectedEdges(t))

Then i get the connected pairs of faces for each sorted edge. Then get the edges per connected face like this:

edges_per_face = [ (f, list(mesh.TopologyEdges.GetEdgesForFace(f))) for f in connected_faces]

Which gives me a list of tuples, first item in the tuple is the face index and second the edge indices for the face. Then i iterate over the connected edges, and sort the connected faces (two) per edge. If connected edges per face contains eg. edge[i] and edge[i+1], i know this is the face to append between 2 consecutive sorted edges. If not, i re-append the edges_per_face tuple and continue my search until i have the proper face for each consecutive sorted edge pair. The whole process gives me the faces in proper counter clockwise order (like i also get my topology edges), but there should be a simpler way. Filtering the right faces out from the pairs of faces per sorted topology edges is computationally intensive. If we can get connected topology vertices and connected edges in a sorted order, why not faces connected to a topology vertex ?

_
c.

Agreed. It is a bit involved to say the least.

Good question. I guess they just have never thought about it.

// Rolf

I don’t know if this (C# version) approach is of any use for you. This was the simplest I could come up with. It seems to work even if the “star” contains naked edges (two faces were deleted in the mesh shown here to ensure that naked edges are handled):

OrderedFaceStar.gh (8.9 KB)

    // CONNECTED EDGE INDICES
    M.TopologyVertices.SortEdges(I);
    int[] conn_ei = M.TopologyVertices.ConnectedEdges(I); // CEI

    // CONNECTED FACE INDICES
    var conn_fi = new List<int>();
    for (int i = 0; i < conn_ei.Length; i++)
    {
      var face_ix = M.TopologyEdges.GetConnectedFaces(conn_ei[i])[0];
      if (conn_fi.Contains(face_ix)) // face already collected, pick the other side
      {
        var faces = M.TopologyEdges.GetConnectedFaces(conn_ei[i]);
        if (faces.Length > 1) // if not a naked edge, pick the other side [1]
          face_ix = faces[1];
      }
      conn_fi.Add(face_ix); // CFI
    }

// Rolf

@Rolf thank you for the sample but it does not seem to work on a welded box i get this output:

TVertex 0 = List[int]([0, 2, 3])
TVertex 1 = List[int]([2, 1, 3])
TVertex 2 = List[int]([3, 0, 3])
TVertex 3 = List[int]([4, 0, 4])
TVertex 4 = List[int]([1, 4, 3])
TVertex 5 = List[int]([4, 1, 5])
TVertex 6 = List[int]([0, 5, 2])
TVertex 7 = List[int]([2, 1, 2])

This is the box used with dots for all items: WeldedBox.3dm (64.2 KB)

_
c.

Hm. Trickier than I thought… :slight_smile: This seems to work, at least for the test cases I tried.

    // Tries to add both sides (faces) of the edge while avoiding dupes.
    // The j - loop implicitly handles naked edges by not trying to add
    // more faces than an edge actually has (j = faces.Length).

    var conn_fi = new List<int>();
    for (int i = 0; i < conn_ei.Length; i++)
    {
      var faces = M.TopologyEdges.GetConnectedFaces(conn_ei[i]);
      for (int j = faces.Length; j --> 0; ) // counter clockwise
      {
        if (!conn_fi.Contains(faces[j])) // avoid dupes
          conn_fi.Add(faces[j]);
      }
    }

OrderedFaceStar_R2.gh (30.8 KB)

// Rolf

Hi Rolf, did you try it on my example welded Box ? It gives me this:

TVertex 0 = List[int]([3, 0, 2]) # CCW
TVertex 1 = List[int]([3, 2, 1]) # CCW
TVertex 2 = List[int]([4, 3, 0]) # CW (Error)
TVertex 3 = List[int]([5, 4, 0]) # CW (Error)
TVertex 4 = List[int]([3, 1, 4]) # CCW
TVertex 5 = List[int]([5, 4, 1]) # CCW
TVertex 6 = List[int]([2, 0, 5]) # CCW
TVertex 7 = List[int]([5, 2, 1]) # CW (Error)

So it now avoids duplicates, but the face order is not counter clockwise (CCW) for all topology vertices. I think the only way is to iterate over edges in consecutive pairs, conn_ei[i] and conn_ei[i+1] and then get the connected faces for both as set, then do a set intersection to get the face between those edges. I have this already, but when naked edges come into play, it is hard to figure out what to keep. Therefore i asked for a simple way to get the connected faces in sorted order.

_
c.

Yes, but I (looking blushed) apparently had not tested rotate from all corners!

Seems like your approach should be the safest way to find the “in-between-face”.

Naked edges can be detected by checking the number of connected faces returned, like so:

var face_indices = M.TopologyEdges.GetConnectedFaces(conn_ei[i]);
var IsNaked = face_indices.Length == 1;
/// aso

I’ll take another look to see if I can handle naked edges with your approach.

// Rolf

Hi Rolf, naked edges are handled in my case, before i iterate over the edges. So far this is what i have, it is slow with large meshes:

conn_edges = List[int](mesh.TopologyVertices.ConnectedEdges(t))
conn_edges.Add(conn_edges[0])
conn_faces = [mesh.TopologyEdges.GetConnectedFaces(i) for i in conn_edges]
        
ordered_faces = List[int]()

for i in xrange(len(conn_edges)-1):
   pair0 = set(conn_faces[i])
   pair1 = set(conn_faces[i+1])
            
   intersection = pair0.intersection(pair1)
   if not intersection: continue
            
   ordered_faces.Add(list(intersection)[0])

It results in this for the welded box:

0 = [0, 2, 3]
1 = [2, 1, 3]
2 = [4, 0, 3]
3 = [5, 0, 4]
4 = [1, 4, 3]
5 = [4, 1, 5]
6 = [0, 5, 2]
7 = [5, 1, 2]

_
c.

How large meshes do you have? Could you share a mesh so we can test timing for different approaches?

// Rolf

I cannot post the meshes here, they are over 1 million faces. I’ve tested above code (which does other things before getting the ordered faces per topology vertex) on meshes with 80k faces and 100k vertices. It runs through in 6sec. If i add the code to get the ordered faces per vertex, it runs in 14sec.

_
c.

OK, try this on your computer. I have internalized a car with 290881 vertices and 234672 faces, which takes ~720ms on my machine. You can un-comment the for-loop to manually verify the CCW winding (on the car the mesh is flipped inwards in many places, so verify winding against your own meshes).

image

OrderedFaceStar_R3.gh (11.9 MB)

// Rolf

Hi Rolf, i guess i need a faster cpu. I work with python (not gh) which may be slower than C#. Maybe i am interpreting things wrong but your last example does not seem to give the proper faces for an icosahedron mesh, which i have internalized.

OrderedFaceStar_IcoSphere.gh (22.9 KB)

_
c.

If you uncomment the two lines with arrows (you’ll see the comments in the code), then that activates the TVI input. It should work. I tested moving the TVI 0…9 and it should work.

Uncommenting at the arrows will disable the for-loop and the I = tv; assignment , which was used to automate the stress-test of the bigger Audi-mesh.

    /// UNCOMMENT "FOR..." TO USE ONLY INPUT PARAM "I"
    // <-- HERE for (int tv = 0; tv < tv_count; tv++)
    {
      //I = tv; // <-- UNCOMMENT THIS ROW TO USE ONLY INPUT PARAM "I"

BTW: My CPU is an old i7 3930K @3.2GHz. A decade old carcass…

// Rolf

ah, you mean comment not uncomment. Your line was uncommented, if i comment this out, i see it updates the display properly.

Still i think, it should not require 3 nested loops per topology vertex to get the faces in CCW order. Did you try my single loop example too and is it faster using a set intersection thank yours ?

_
c.

Yes! :slight_smile:

But I upload a new version which goes into “manual mode” when the TVI sliders is > -1 (it runs though all TopologyVertices if set to == -1, useful for performance-test on bigger meshes)

No, I didn’t look very carefully since I’m not really fluent in Python.

The reason I used the nested for-loops was to “short-circuit” the face-matching test as early as possible to break the loops (sometimes loops are more “predictable” for the CPU than multiple if-branches). Anyway, yes, generally speaking multiple nested loops is bad, but with the loops I test the faces on the “most likely sides” in respective j,k loop to speed it up a bit.
OrderedFaceStar_IcoSphere_RE.gh (15.6 KB)

Edit: How many ms does it take for you to process the audi mesh with TVI-slider set to -1?

// Rolf

If i run your Audi definition as uploaded the C# component takes 1.6s.

_
c.