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