get faces in coincident order from shell

when traversing a shell, in many cases the underlying faces are not returned in coincident order.
which surprises me, since such an order should exist when the faces are sewed together.
am I expecting too much, or is there a call to traverse the shell with coincident / neighboring faces?



Roman Lygin's picture

Hi Jelle,

The ordering sequence of faces in a shell is not enforced. I don't remember internals of the sewing algorithm but may presume that it may even keep the original order of the faces (in a compound, for instance). A shell coming from a STEP file will likely retain its order which is arbitrary.

Nonetheless, you can still reorder them yourself using edge connectivity information and using map containers.
Here is some pseudo-code:
put all faces into a source_map;
create empty target_list;
create empty map of used edges (edges of faces in target_list);

take first face, explode into edges, put edges into edge_map and face into target_list, remove from source_map;

until source_map is empty do:
- take next face,
- start exploding into edges, if at least one edge belongs to edge_map pick up this face, put its edges into edge_map, append face to target_list, remove from source_map;
- if no edges belong to edge_map, skip to next face

Hope this helps.

jelle's picture

hi Roman!

Many thanks for taking the time to explain.
I implemented an ordering algorithm much like your description ( with the TopoExplorer its not very hard ), that works perfectly ;)
I also take into account the parametric orientation of the faces ( since u,v direction do not nessecarily match ).
However, my paranoia was that something like TopOpeBRepTool might already implement something alike.



Anand R P's picture

Hi jelle

I am a novice in opencascade, i too confronted with your problem of ordering the faces, can us share your ordering algorithm with me.

- anand

Fabian Hachenberg's picture

Hi jelle,

I'm also very much interested in your implementation of the ordering algorithm. Thanks!

jelle's picture


def sort_coincident_faces(self):
# make sure the shell can be oriented
# otherwise we're at a loss before starting...
from OCC.BRepCheck import BRepCheck_Shell
orient = BRepCheck_Shell(self.topo).Orientation()
if not orient==0:
raise AssertionError( 'orientation of the shell is messed up...')

tp_shell = Topo(self.topo)
faces = [fc for fc in self.Faces()]
# hash face to its edges
edges_from_faces = dict([[fc, [edg for edg in fc.Edges()]] for fc in self.Faces()])
source_faces = list(edges_from_faces.keys())
sorted_faces = [edges_from_faces.keys()[0]]
# add the edges of the face contained in sorted_faces
identified_edges = list(edges_from_faces[sorted_faces[0]])

while source_faces:
connections = defaultdict(int)
for k,v in edges_from_faces.iteritems():
print 'k',k
for edg in v:
for i in identified_edges:
if edg.topo.IsPartner(i.topo):
print 'connect///'
# there can be several faces that are connected to the faces in `sorted_faces`
# the face of interest is the one with the most coincident edges
k = sorted(connections.iteritems(), key=operator.itemgetter(1), reverse=True)[0][0] # get the face with most connections

if not k in sorted_faces:

for i in sorted_faces:
if i in edges_from_faces:
del edges_from_faces[i]
if i in source_faces:
del source_faces[source_faces.index(i)]

return sorted_faces

So, I follow Roman's suggestion, with 1 slight chance.
I sort the faces that share an edge to their degree; the number of coincident edges a faces has.
For instance, if you already have 2 faces of a cube, the 3rd face should be connected to _either_ of the other faces, right?
connections[k]+=1 # +1 coincidence for this face K

That's all there is to it...

The screendump explains it somewhat more intuitively...


jelle's picture

Messed up indentation, please see: