Algorithm Efficiency / Using Multiprocessor Calls

I’m new to this forum, but have been using Blender and Python now for a few years. I am not a trained programmer (but simply an engineer with a lot of programming background). I recently wrote a script up for work using Blender & Python that is used for edge and feature detection based on a number of methods. I’m returning a number of important edges by selecting them in the bmesh object. (I’ll try and post code if I am permitted (because someone is paying me to do this it is considered their property…))

I am having issues with the next step: I need to sort these edges into small lists of edges that are joined. Currently I’m doing this by asking for a length comparison of the set operation done on the verts ids belonging to the list of all edges except current and the current list of edges. I gain lists by simply making each individual edge a list and slowly joining all the other lists together, until there are no more shared verts (i.e. everything has been grouped).


#PSEUDO CODE
while (all edges not grouped):
   current_edges = edge_groups[0]
   for i in range(0, len(egde_groups)):
        current_verts = get_verts(current_edges)
        other_verts = get_verts(edges_to_compare)
        if len(set(current_verts).intersection(other_verts)):
           group the lists (making sure not to duplicate groups)
           reset the current_edges if current_edges has been changed...etc  
           #BECAUSE WE NOW MAY HAVE A NEW CONNECTION POINT
   if current_edges  is last in final list:
      break

The problem is that when the mesh gets large or slightly “soft featured” this takes forever!

I’ve tried implementing a multicore solution using multiprocessing Python modules to split the initially selected edges into a number of smaller groups, but sadly I have Windows at work. Windows, as I have found, has an issue forking the process. (I would post a link to another forum thread for reference…but there are restrictive noob rules).

So now my question(s):
Is there a way around the Windows multicore issue with Blender-Python? (Keep in mind I’m not an admin at my workplace). If not, is there an easier/ less computationally intensive way to find groupings of edges in a set of predefined edges that which connected?

Generally, when your program is running very slow like this, it is because you need a better algorithm. It sounds like you have managed to get yourself into an O(n^2) situation or maybe even worse.

My gut reaction is that you seem to be doing a lot of work to iterate edges multiple times to combine them into sets. I probably don’t understand your problem fully, but it seems like you should be able to make a single pass of the edges and drop them into buckets with some checking to see if 2 groups have merged or not.


# Start with no edge groups
edgeGroups = []

# Walk the edges
for edge in edges:
  
  # See if the edge is part of a group
  groups = [group for group in edgeGroup if isMember(edge, group)]

  # If there are no groups, then add this edge to a new one.
  if len(groups) == 0:
    # Store a dictionary with a set of the included vertices and the included edges
    edgeGroups.append({verts: set(edge.vert1, edge.vert2), edges: set(edge)})    

  else:
    # Add the edge to the first matching group
    group = groups[0]
    group.verts.add(edge.vert1)
    group.verts.add(edge.vert2)
    group.edges.add(edge)

  # If there were multiple group matches, merge all the groups into the first group.
  mainGroup = groups[0]
  for i in range(1, len(groups)):
    merge(mainGroup, groups[i])
    edgeGroups.remove(groups[i]) 

def isMember(edge, group):
  '''Tests if the given edge is connected to this group by see if it has a shared vert with a group member.'''
  return (edge.vert1 in group.verts) or (edge.vert2 in group.verts)

def merge(mainGroup, mergeGroup):
  '''Adds all edges and vertices of 'mergeGroup' to 'mainGroup'. '''
 mainGroup.verts = mainGroups.verts.union(mergeGroup.verts)
 mainGroup.edges = mainGroup.edges.union(mergeGroup.edges)

I agree totally, it is of an order n^2.

I toyed with the idea above, but thought that I’d still have to run a large number of loops, though not nested, and I would be essentially writing the same structures Blender has (verts to edges) into yet another dictionary array (I suppose memory is very available nowadays).

I’ll definitely try it your way instead.

I’m not doing anything special with the grouping afterward, simply using them to then gather physical data on the object features (mainly centers and sizes). This might entail using a combination of sorting algorithms similar to the one above on the edge group centers points after their calculations.

I really appreciate the help.

Is this all in vain anyway? Does anyone know if a feature detection code/library exists (that someone much more mathematically talented than myself whipped up)?

P.S. Can anyone kick up the login timeout time on the website? I had to re-login like 3 times while writing this…

There are a few elements to your code that are slightly confusing to me:

“groups = [group for group in edgeGroup if isMember(edge, group)]”
I’m not quite sure if I understand this correctly (it is very compact), but is it gathering group elements that share nodes? I guess the part I can’t visualize is what type of list argument is returned here…

“group = groups[0]”
I’m not sure what is happening here? Again this might stem from the above issue of not seeing your structure…are you nesting lists?

Thanks.

First off, you should consider that code to be mostly Python pseudo code. I didn’t run or test that code so there are almost certainly syntax and minor logic errors.

Reading the comments is probably more helpful than reading the code itself since the comments document the algorithm in plain English.

The main advantage that my algorithm has is that:
(1) It only loops over the edges once.
(2) It uses the Python “set” objects for building collections of objects. Testing if an object is part of a “set” is significantly more efficient than testing if an object is part of an unsorted “list”.

The idea behind the algorithm is something like this: I have a list of edges and I want to divide them up into “groups” of edges that are connected to each other. So if I have only one edge, I get one group. If I have 2 edges then I might have one group or two groups depending on if they are touching. The test to see if there is one group is to say, “Do these edges have any vertices in common?”

So the algorithm picks up each edge and says, “does this edge belong to any of my existing groups/piles?” You get one of three answers to this question:
(1) This edge is not connected to any existing group. So you start a new group with just that edge in it.
(2) The edge is part of just one existing group. So you add the edge to that group.
(3) The edge is connected to more than one group. That means that both groups are really connected. In this case, it adds the edge to the first group and also adds all the edges from the other matching groups. It then deletes the extra groups.

At the end, you should have the edges partitioned into groups that are connected in some fashion.

Yes, Python “list comprehensions” (that is what this is called) can get very dense. You can think of them as a very compact form of a for-loop. The same code could be rewritten as:


groups = []
for group in edgeGroup:
  if isMember(edge, group):
    groups.append(group)

This is the code that logically asks the question, “is this edge part of any existing groups?” The result of that line is:
(1) An empty list. The edge is not part of any groups.
(2) A single group. The edge is part of just one group.
(3) Multiple groups. The edge joins multiple, existing groups into a single, connected group.

“group = groups[0]”
I’m not sure what is happening here? Again this might stem from the above issue of not seeing your structure…are you nesting lists?

“groups” is just a Python “list” that contains the information about a group of edges. From the above comments on the list comprehension, “groups[0]” is just selecting the first group that does contain the edge.

If an edge is a member of two groups then you want to merge those groups into a single group. You could do that by:

  • Creating a new group that contains all the elements from group1 and group2 then deleting group1 and group2.
    or
  • Add all the elements from group2 into group1 then delete group2.

If an edge is part of at least one group, then you always add the edge to that group. Since I’m always adding the edges to the first group in the list, it makes sense to simply merge all the other groups into the first and then remove them.

Thanks, that clarifies things a bit. I think I understood the overall sorting idea. You are looping over edges once to presort, then looping over the groups to do a final sort (which should result in more order x*n speeds rather than n^2). I was using sets before as they are extremely nifty, but was not using the union operator to unite groups (simply mergedList =
[list1_elements]+
[list2_elements]). My python still needs a bit of polishing. Thanks for the small tutorial.

One more question: Won’t this error due to changing list length?:


# If there were multiple group matches, merge all the groups into the first group.
  mainGroup = groups[0]
  for i in range(1, len(groups)):
    merge(mainGroup, groups[i])
    edgeGroups.remove(groups[i]) 


The loop is over the length of ‘groups’ and I’m removing elements from ‘edgeGroups’, it should be safe.

slightly off thw threading topic, when you are iterating over the edges or verts, are you using the builtin connectivity information in bmesh? as opposed to infering it from sets which you build manually.

vert.link_edges
edge.link_faces
edge.other_vert (test_vert)

I’ve done some feature detection but nothing fast at all. If you want to talk privately for tips I might be able to help a little.

My algorithm did not use the built-in connectivity data in bmesh simply because I’ve never worked directly with the bmesh data structures so I was not really sure what was available.

I’d like to, but I’m not sure it would work out quite the same way. Thanks Kastoria, I’ve used your method successfully. That list comprehension string sure is something…gotta love python.

Anyway new issue: Visualization of the Data

Is there an easy way to run a loop through edge groups and display them one at a time? I’ve tried simply:


for edgeGroup in edgeGroups:
    #DESELECT ALL MESH FOR BETTER VIEWING
    bpy.ops.mesh.select_all(action='DESELECT')
    for edge in edgeGroup:
        edge.select = True
    bpy.context.scene.objects.active = bpy.context.scene.objects.active
    time.sleep(2)

but I don’t seem to be refreshing in real time. The loop simply executes entirely…without updating as it is running. If I recall correctly I’ve seen this before in python printing (it seems to be a scope issue?). Do you have any suggestions? The objective is just to blink the selected edge groups up on screen so I can verify my thresholds and groups are alright.

You gotta put this in a modal operator…and you need to use BGL to visualize

Check out the Modal Draw template that comes with blender. And here a utility to draw a BMEdge.


def draw_polyline_from_3dpoints(context, points_3d, color, thickness, LINE_TYPE):
    '''
    a simple way to draw a line
    slow...becuase it must convert to screen every time
    but allows you to pan and zoom around
    
    args:
        points_3d: a list of tuples representing x,y SCREEN coordinate eg [(10,30),(11,31),...]
        color: tuple (r,g,b,a)
        thickness: integer? maybe a float
        LINE_TYPE:  eg...bgl.GL_LINE_STIPPLE or 
    '''
    
    points = [location_3d_to_region_2d(context.region, context.space_data.region_3d, loc) for loc in points_3d]
    
    if LINE_TYPE == "GL_LINE_STIPPLE":  
        bgl.glLineStipple(4, 0x5555)  #play with this later
        bgl.glEnable(bgl.GL_LINE_STIPPLE)  
    bgl.glEnable(bgl.GL_BLEND)
    
    bgl.glColor4f(*color)
    bgl.glLineWidth(thickness)
    bgl.glBegin(bgl.GL_LINE_STRIP)
    for coord in points:
        if coord:
            bgl.glVertex2f(*coord)
    
    bgl.glEnd()  
      
    if LINE_TYPE == "GL_LINE_STIPPLE":  
        bgl.glDisable(bgl.GL_LINE_STIPPLE)  
        bgl.glEnable(bgl.GL_BLEND)  # back to uninterupted lines  
        bgl.glLineWidth(1)
    return
def draw_bmedge(context, bmedge, mx, thickness, color):
    '''
    simple wrapper to drawp a bmedge
    '''
    points = [mx * bmedge.verts[0].co, mx*bmedge.verts[1].co]
    draw_polyline_from_3dpoints(context, points, color, thickness, 'GL_LINE_SMOOTH')

Can’t you just remove the 2 second sleep from your loop? That would leave your edge groups highlighted in the mesh and since they should not be connected you should be able to visually sort out each one. Obviously you won’t get the nice effect of blinking each group on/off but it would be very easy to do.

If you don’t want to get into OpenGL, another option might be to add your edge data as a custom CollectionProperty to your Mesh and give it a custom Integer property that when you click a button it makes that edgeGroup the active group. Once again, not nearly as seamless as the automatic cycling though the groups but it might be easier than the OpenGL code.

I have not done much work integrating scripts into the UI, so I’m not sure how hard that would be. But it seems that adding a slider and a ‘show’ button should be a fairly straight forward thing to do.

Edit

Also, I’m curious if you benchmarked the two implementations? How much of a speed up did you get?