1
$\begingroup$

i am working on a tool and need to get selection islands in the mesh. I want to keep only the biggest connected vertex selection in the mesh.

The smaller selection island should be discarded

I wrote a function that recursively searches a bmesh for connected and selected vertices:

bm = bmesh.new()
bm.from_mesh(obj.data)

_verts = [v for v in bm.verts if v.select]
_edges = [e for e in bm.edges if e.select]

islands = [] # all selection islands

#iterate all selected verts in mesh
for v in _verts.copy():
    #check if that vert is already registered
    if not any([v in i for i in islands]):
        #new selection island
        _island = []

        def get_selected_connected_verts(v):
            '''
            recursive search vertices for connected and selected vertices
            @v : bmesh vertex
            '''
            #iterate all edges linked to the vertex
            for e in v.link_edges:
                #is edge selected
                if e in _edges:
                    #get adjacent vert
                    v_other = e.other_vert(v)
                    #register vert to island
                    if v_other not in _island:
                        _island.append(v_other)
                        #search again
                        get_selected_connected_verts(v_other)
        get_selected_connted_verts(v)
        #register island
        islands.append(_island)


This works great for most meshes. Sadly with higher vertex counts python returns the following error:

RecursionError: maximum recursion depth exceeded while calling a Python object

When i try to increase the recursion limit, the following error appears:

Error   : EXCEPTION_STACK_OVERFLOW
The terminal process terminated with exit code: 3221225725

Theoretically i know that i should be able to make the recursive function iterative... I am just not able to.. Also, if there is a totally different way to do this, please tell me!
I kindly ask for support of more talented programmers.

Thanks a lot!

$\endgroup$
2
  • 1
    $\begingroup$ Related: an iterative approach for counting loose parts blender.stackexchange.com/questions/75332/… $\endgroup$
    – lemon
    Feb 24 '20 at 14:38
  • $\begingroup$ thanks for the quick reply. This definetly set me on the right track ;) $\endgroup$
    – f.bra
    Feb 24 '20 at 15:17
2
$\begingroup$

Some code from this answer. But adapted for bmesh and the selection aspects of this question.

The principle is to start from selected vertices, and:

  • Make a dictionary of possible links to other vertices
  • Iterate available vertices and for each follow all possible remaining paths

The code with comments:

import bpy
import bmesh

def make_vert_paths( verts ):
    #Init a set for each vertex
    result = {v : set() for v in verts}
    #Loop over vertices to store connected other vertices
    for v in verts:
        for e in v.link_edges:
            other = e.other_vert( v )
            if other.select:
                result[v].add(other)
    return result

def make_island( starting_vert, paths ):
    #Initialize the island
    island = [starting_vert]
    #Initialize the current vertices to explore
    current = [starting_vert]

    follow = True
    while follow:
        #Get connected vertices that are still in the paths
        eligible = set( [v for v in current if v in paths] )
        if len( eligible ) == 0:
            follow = False #Stops if no more
        else:
            #Get the corresponding links
            next = [paths[i] for i in eligible]
            #Remove the previous from the paths
            for key in eligible:
                island.append( key ) 
                paths.pop( key )
            #Get the new links as new inputs
            current = set( [vert for sub in next for vert in sub] )

    return island

def make_islands( bm_verts ):
    paths = make_vert_paths( bm_verts )
    result = []
    found = True
    while found:
        try:
            #Get one input as long there is one
            vert = next( iter( paths.keys() ) )
            #Deplete the paths dictionary following this starting vertex
            result.append( make_island( vert, paths ) )               
        except:
            found = False
    return result


obj = bpy.context.object

bm = bmesh.new()
bm.from_mesh(obj.data)
bm.verts.ensure_lookup_table()

bm_verts = [v for v in bm.verts if v.select]

islands = make_islands( bm_verts )

print( len(islands) )
#print( islands )

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.