How could one find all adjacent groups of 4 faces inside a subdivided facet?

[stevmills]

Hi!

I am using trimesh to model network connectivity.

Currently, I can easily find the corner groups of 4 in a given facet:

However, what I'd like to be able to do is automatically find all groupings of 4 faces in a facet regardless of how subdivided it is. Is there a way to accomplish such without a ton of looping?

Thanks!

[Kiord]

What is a corner group ? Is it related to the face colors in your example ? Can you explain in other words ?

[stevmills]

What is a corner group ? Is it related to the face colors in your example ? Can you explain in other words ?

Hi @Kiord, sorry for not explaining better! Yes.. in my question the "corner groups" are the three white groups of 4 faces each at the corners of the facet. I'm not interested in those specifically though, I want to be able to programmatically identify all 16 groups of 4 adjacent faces in the entire 64-face facet.

[Kiord]

Ok I see. I think you can use the graph of the triangles of the given facet :

Here each node corresponds to a triangle, and each edge correspond to a mesh edge between two faces. We can notice that the center of the 4 faces group are 3 nodes away from each other. Also there exist two and only two paths to go from one to another. If you take the adjacency matrix of this graph to power 3, you will get the number of paths of length 3 that connect each node with the others. Now if we take only the coefficients which are equal to 2, we get another adjacency matrix. This adjacency matrix represents the graph of possible groupings of 4 faces, but the different solutions will appear as (four) distinct connected components. Each node of this graph corresponds to the center of a 4 faces group. If you can identify the center of one "true" 4 faces group (you already do), you can use Breadth-first search to get the connected component it belongs to. At this point the problem is solved since you have all the centers of the 4 faces groups.

The problem with this solution is that BFS algorithm is a loop even if it should be well optimized in available libs. Maybe there are more clever ways to use the triangle graph or other graphs.

Are you doing the subdivision yourself ? if so you just need to keep in memory the last iteration.

Also if you can ensure that the subdivision is regular, maybe you can work with the euclidean distances between a the vertices and the corner.

Anyway it is an interesting problem

[stevmills]

@Kiord thanks for the response!

It appears that the facets are constructed in such a way that if you just sort their faces and slice the list into groups of 4, you get the answer I was looking for! 😄

[Kiord]

Glad you noticed that in your data !