Wed, 07/20/2011 - 01:36

Forums:

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?

thanks,

-jelle

Wed, 07/20/2011 - 13:59

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

repeat.

Hope this helps.

Roman

Wed, 07/20/2011 - 14:29

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.

Thanks!

-jelle

Tue, 09/20/2011 - 14:45

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.

Thanks

- anand

Tue, 09/20/2011 - 20:38

Hi jelle,

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

Wed, 09/28/2011 - 18:46

sure...

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///'

connections[k]+=1

# 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:

sorted_faces.append(k)

identified_edges.extend(edges_from_faces[k])

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

Wed, 09/28/2011 - 18:48

Messed up indentation, please see:

https://gist.github.com/1248127