How to find the number of loose parts with Blender's Python API?

Question

I want to find out how many loose parts a mesh has using Python, i.e. write a function that takes a mesh object as an argument and returns an int. So far I haven't found a way to access this information from within Blender.

I know I could do this by separating by loose parts and then count the number of objects created, but that seems quite inefficient. I want to know how many loose parts there are without separating.

Answer 1

I propose another approach based on dictionaries and sets, for performance purpose. It allows here to calculate a 1080 times arrayed sphere with about 500k vertices in 3 seconds.

The principle is to:

Initialization

• Create a dictionary keyed by all vertices indexes
• Iterate over the edges to make 'links' in the dictionary from a key to the connected vertices indexes through the edge

Calculation

• Take one key (one vertex index) remaining in the dictionary
• As long as this key exists, loop for this key to:
• Retrieve the corresponding 'links' as a flatten set
• Remove the input key in the dictionary
• Get the corresponding 'links' as new inputs as long as possible (corresponding links still exist)

Here is the commented code:

import bpy
import time
from collections import defaultdict

def MakeVertPaths( verts, edges ):
    #Initialize the path with all vertices indexes
    result = {v.index: set() for v in verts}
    #Add the possible paths via edges
    for e in edges:
        result[e.vertices[0]].add(e.vertices[1])
        result[e.vertices[1]].add(e.vertices[0])
    return result

def FollowEdges( startingIndex, paths ):
    current = [startingIndex]

    follow = True
    while follow:
        #Get indexes that are still in the paths
        eligible = set( [ind for ind in current if ind 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: paths.pop( key )
            #Get the new links as new inputs
            current = set( [ind for sub in next for ind in sub] )

def CountIslands( obj ):
    #Prepare the paths/links from each vertex to others
    paths = MakeVertPaths( obj.data.vertices, obj.data.edges )
    found = True
    n = 0
    while found:
        try:
            #Get one input as long there is one
            startingIndex = next( iter( paths.keys() ) )
            n = n + 1
            #Deplete the paths dictionary following this starting index
            FollowEdges( startingIndex, paths )               
        except:
            found = False
    return n

print( '-------------' )

#The wanted object    
obj = bpy.context.object

start_time = time.time()

for i in range( 1 ): #For testing purpose in order to evaluate runtime elapse
    print( 'islands', CountIslands( obj ) )

elapsed_time = time.time() - start_time
print( elapsed_time )

The blend file

Answer 2

Recursive Bmesh version

Similarly to the way other bmesh operators, BMesh.Ops are used,

get_islands(bm, verts=[])

bm the bmesh.
verts iterarable of any or all of the verts in the bmesh.
returns -> dict(islands=[])

A dictionary is returned with each island as a list of BMVerts, within the "islands" key list.

• It's Quick
• Uses BMVert.tag so doesn't naff up prior selections.
• Works in both edit and object mode
• Requires no operators.

. Test code: Run in object mode, checks for all islands in all meshes in file.

import bpy
import bmesh

def walk_island(vert):
    ''' walk all un-tagged linked verts '''    
    vert.tag = True
    yield(vert)
    linked_verts = [e.other_vert(vert) for e in vert.link_edges
            if not e.other_vert(vert).tag]

    for v in linked_verts:
        if v.tag:
            continue
        yield from walk_island(v)

def get_islands(bm, verts=[]):
    def tag(verts, switch):
        for v in verts:
            v.tag = switch
    tag(bm.verts, True)
    tag(verts, False)
    ret = {"islands" : []}
    verts = set(verts)
    while verts:
        v = verts.pop()
        verts.add(v)
        island = set(walk_island(v))
        ret["islands"].append(list(island))
        tag(island, False) # remove tag = True
        verts -= island
    return ret

#test code
context = bpy.context
ob = context.object
me = ob.data
bm = bmesh.new()
from time import time
t = time()
for me in bpy.data.meshes:
    bm.from_mesh(me)
    islands = [island for island in get_islands(bm, verts=bm.verts)["islands"]]
    print(me.name, "Islands:", len(islands))
    print([len(i) for i in islands])
    bm.clear()

bm.free()
print(len(bpy.data.meshes), "meshes processed in", time() - t, "seconds")

Given the new answers, thought I'd time them. Simple 10 x 10 x 10 applied array on default cube.

This

Cube Islands: 1000
0.0809781551361084 seconds

@Денис Колесников

1000
0.11966490745544434

@lemon

islands 1000
0.18735790252685547

@zebus_3d (note leaves the object in edit mode)

# by faces
total islands:  1000
total time (seconds):  6.521913093005423
# by verts
total islands:  1000
total time (seconds):  10.745814517998951

JakeD

1000
18.090813398361206  seconds

Answer 3

That code makes a different thing - it finds the vertices that belong to the loose parts. But, the code is much clearer. If you need the count, just take len().

obj = context.object
mesh = obj.data
paths={v.index:set() for v in mesh.vertices}
for e in mesh.edges:
    paths[e.vertices[0]].add(e.vertices[1])
    paths[e.vertices[1]].add(e.vertices[0])
lparts=[]
while True:
    try:
        i=next(iter(paths.keys()))
    except StopIteration:
        break
    lpart={i}
    cur={i}
    while True:
        eligible={sc for sc in cur if sc in paths}
        if not eligible:
            break
        cur={ve for sc in eligible for ve in paths[sc]}
        lpart.update(cur)
        for key in eligible: paths.pop(key)
    lparts.append(lpart)

print(lparts)

Answer 4

This is my 2 solutions:

import bpy, bmesh
from timeit import default_timer as timer

bpy.app.debug = True

ob = bpy.data.objects['Cube']
visited = []
# raw contains the information in one dimension
raw = []
island = []

bpy.ops.object.mode_set(mode='EDIT')
mesh=bmesh.from_edit_mesh(bpy.context.object.data)

def detectByFaces():
    bpy.ops.mesh.select_mode(type="FACE")
    bpy.ops.mesh.select_all(action='DESELECT')
    for f in mesh.faces:
        #print(raw)
        if f.index not in raw:
            #print(visited)
            f.select = True
            bpy.ops.mesh.select_linked()
            #print(island)
            for fs in mesh.faces:
                if fs.select:
                    island.append(fs.index)
                    raw.append(fs.index)
            bpy.ops.mesh.select_all(action='DESELECT')
            # if island not in visited i add it:
            if island not in visited:
                visited.append(island[:])
                island.clear()
    print("islands (faces): ", visited)
    print("total islands: ", len(visited))

def detectByVertex():
    bpy.ops.mesh.select_mode(type="VERT")
    bpy.ops.mesh.select_all(action='DESELECT')
    for f in mesh.faces:
        for v in f.verts:
            #print(raw)
            if v.index not in raw:
                #print(visited)
                v.select = True
                bpy.ops.mesh.select_linked()
                #print(island)
                for vs in mesh.verts:
                    if vs.select:
                        island.append(vs.index)
                        raw.append(vs.index)
                bpy.ops.mesh.select_all(action='DESELECT')
                # if island not in visited i add it:
                if island not in visited:
                    visited.append(island[:])
                    island.clear()
    print("islands (vertex): ", visited)
    print("total islands: ", len(visited))

start = timer()
#print(visited)
# by faces is a little more optimal because it makes fewer passes:
detectByFaces()
# by vertices we obtain the array with the vertices of each island:
#detectByVertex()
finish = timer()
print("total time (seconds): ", finish-start)

Answer 5

Example

This GIF is of an object created with three array modifiers on a sphere. There are 6 x 6 x 6 = 216 spheres (disconnected pieces) in all, and you can see the example script spit that out in the bottom-right corner at the end. This object has 104,112 vertices and 207,360 triangles.

Algorithm

This is actually a bit of a challenge if I am not overthinking this. Here is some pseudocode for my algorithm. Disclaimer: I haven't yet studied graph theory, so I may be over-complicating this.

1. Store all edges in a set
2. Pop an edge from that set and store its two vertices in another set
3. Loop over every other edge in the set to see if any of them have any vertices that are already in the set of vertices. (If they do, pop them from the edges set and add their vertices to the verts set.)
4. Repeat #3 until it adds no more vertices to the set of vertices.
5. We now have an island. Clear the set of vertices, and pop another edge from the set of edges. The two vertices on this edge will begin the next island. Increment the number of islands, and (starting at step #3) repeat the process until the set of all edges is empty.

We now have the number of distinct islands from the graph of edges and vertices.

Sample Code:

import bpy
import bmesh

# get the object
obj = bpy.context.object

# get a bmesh using that object's mesh
bm = bmesh.new()
bm.from_mesh(obj.data)

# make sure we can iterate over edges
bm.edges.ensure_lookup_table()


class GraphTracer:
    """Traces the graph of edges and verts to find the number of islands."""

    verts = set()  # stores connected vertices
    edges = set()  # stores edges for next iteration
    islands = 0

    def __init__(self, bmesh_edges):
        self.edges = set(bmesh_edges)

        self.trace_next_island()

    def trace_next_island(self):
        # when this set is empty, quit
        while self.edges:
            # reset the verts set and fill with verts from the next island
            self.verts = set()
            self.add_edge_verts(self.edges.pop().verts)

            # as long as we loop over all remaining verts, if there is no
            # connection, then we have reached the end of an island
            found_connection = True
            while found_connection:

                # immediately set this to false to see if it will be true after loop
                found_connection = False

                # store the edges to be removed in this
                remove_edges = set()

                # loop over each edge to find one that can be connected to a vert
                for edge in self.edges:
                    evs = edge.verts

                    # if the edge has an attachment (vertex) in common with
                    # one already in the island, it is also part of the island
                    if evs[0].index in self.verts or evs[1].index in self.verts:
                        self.add_edge_verts(evs)
                        remove_edges.add(edge)
                        found_connection = True

                # remove the edges (can't change set's size while looping over it)
                for e in remove_edges:
                    self.edges.remove(e)

            self.islands += 1

    def add_edge_verts(self, edge_verts):
        """There are 2 verts in an edge so we need to add it twice."""

        for i in range(2):
            self.verts.add(edge_verts[i].index)

    def get_islands(self):
        return self.islands


gt = GraphTracer(bm.edges)
print(gt.get_islands())

# make sure to free the bmesh when done
bm.free()

Answer 6

Unfortunately there's no parameter as part of Object / bmesh that can be accessed to get at the island count, it would be a nice Object.method to have, or even a bmesh.ops. If you are interested in an algorithm, here's my current approach.

This should return all vertex indices associated with each island, in the form of a dict. Getting the number of islands is a matter of doing len(island_dict)

def recursive_search(found_set, current_vertex):

    for polygon in current_vertex.link_faces:
        for vert in polygon.verts:
            if vert.index not in found_set:
                found_set.add(vert.index)
                found_items = recursive_search(found_set, vert)
                if found_items:
                    found_set.update(found_items)

    return found_set

def vertex_emitter(bm):
    for v in bm.verts:
        yield v

def find_islands_treemap(bm):

    island_index = 0
    islands = {}

    vertex_iterator = vertex_emitter(bm)
    vertex_0 = next(vertex_iterator)
    islands[island_index] = recursive_search({0}, vertex_0)

    for vertex in vertex_iterator:
        if vertex.index not in islands[island_index]:
            island_index += 1
            islands[island_index] = recursive_search({vertex.index}, vertex)

    return islands


island_dict = find_islands_treemap(bm)
print(island_dict)

*ps has not been rigorously stress tested. yet.

Answer 7

My answer here is in addition to the one provided by @batFINGER

What the following adds to his code is the ability to separate by faces. Essentially I go over each of the islands his code gives us. Then I get the verts for the island. Then I iterate on those. I select them all. Then I flush the selection mode to be able to get the faces. Then I iterate to create new verts and new faces, and then I deselect the verts and move onto the next island.

I don't expect it to be fast. It needs optimizing. But it got me the result I wanted - which was to have a bmesh alternative to separate-by-loose-parts.

def _separate_islands(self, object):
    me = object.data
    bm = bmesh.new()
    bm.from_mesh(me)
    bm.select_mode = {'VERT', 'EDGE', 'FACE'}
    verts = bm.verts[:]
    edges = bm.edges[:]
    faces = bm.faces[:]
    islands = [island for island in self._get_islands(bm, verts=bm.verts)["islands"]]
    for island in islands:
        island_me = bpy.data.meshes.new('new_mesh')
        island_bm = bmesh.new()
        for vert in island:
            vert.select = True
        bm.select_flush_mode()
        faces = [[face.verts] for face in bm.faces if face.select]
        for vert_groups in faces:
            for grp in vert_groups:
                new_face_verts = []
                for vert in grp:
                    new_vert = island_bm.verts.new(vert.co)
                    new_face_verts.append(new_vert)
                island_bm.faces.new([vert for vert in new_face_verts])
        for vert in island:
            vert.select = False



        island_bm.to_mesh(island_me)
        island_me.update()
        island_bm.free()
        new_object = bpy.data.objects.new('new_lug', island_me)
        self.drum_collection.objects.link(new_object)
    
    self.drum_collection.objects.unlink(object)
    return

Answer 8

here's another solution, part of bpy_helper, I kept only relevant parts for the answer

How fast is it: result on a 1000 cube islands 0.01136610000003202 seconds

avg. 1000 runs with timeit = 0.011410456999999952 seconds

Measuring single run:

bm = bmesh.new()
bm.from_mesh(bpy.context.object.data)

from time import perf_counter

t0 = perf_counter()
bm_loose_parts(bm)
t1 = perf_counter()
print(t1 - t0)

The code:

import bmesh
from typing import List


class BMRegion:
    """Warning: this does not validate the BMesh, nor that the passed geometry belongs to same BMesh"""

    def __init__(
        self,
        verts: List[bmesh.types.BMVert],
        edges: List[bmesh.types.BMEdge],
        faces: List[bmesh.types.BMFace],
    ):
        self.verts = verts
        self.edges = edges
        self.faces = faces


def _bm_grow_tagged(vert: bmesh.types.BMVert):
    """Flood fill untagged linked geometry starting from a vertex, tags and returns them"""
    verts = [vert]
    edges: List[bmesh.types.BMEdge] = []
    faces: List[bmesh.types.BMFace] = []

    for vert in verts:
        link_face: bmesh.types.BMFace
        for link_face in vert.link_faces:
            if link_face.tag:
                continue
            faces.append(link_face)
            link_face.tag = True
        link_edge: bmesh.types.BMEdge
        for link_edge in vert.link_edges:
            if link_edge.tag:
                continue
            link_edge.tag = True
            edges.append(link_edge)
            other_vert: bmesh.types.BMVert = link_edge.other_vert(vert)
            if other_vert.tag:
                continue
            verts.append(other_vert)
            other_vert.tag = True

        vert.tag = True

    # For debugging
    # assert len(set(verts)) == len(verts)
    # assert len(set(edges)) == len(edges)
    # assert len(set(faces)) == len(faces)

    return BMRegion(verts, edges, faces)


def bm_loose_parts(bm: bmesh.types.BMesh):
    # Clear tags
    for v in bm.verts:
        v.tag = False
    for e in bm.edges:
        e.tag = False
    for f in bm.faces:
        f.tag = False

    loose_parts: List[BMRegion] = []

    for seed_vert in bm.verts:
        if seed_vert.tag:
            continue
        # We could yield instead
        # but tag could be modifed after yield
        # so better to store results in a list
        loose_parts.append(_bm_grow_tagged(seed_vert))

    return loose_parts