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

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.

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:
return result

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

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

• Very nice, and much faster than my algorithm. Mar 11 '17 at 13:40

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)
if not e.other_vert(vert).tag]

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()
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

• This solution is far better (and faster) than mine and should be accepted. FYI, I've not seen that at first time as bpy.data.meshes seems to get all meshes including the one that has no more object. Apr 17 '18 at 9:28
• Hi batFINGER, FYI did some other comparative tests. The benchmarks are really dependent on the island count and size. Tried a 6x6x6 arrayed uv sphere for instance (104k vertices). Sep 14 '19 at 6:11
• I think this is actually a very efficient way to separate loose parts instead of using the ops operator, can you point out how to make this extra step? I can't see a sort of a "separate" function in the bmesh documentation. (obviously a bmesh noob :) ) Feb 8 '20 at 17:40
• Thanks. Perhaps ask as a new question. There is a bmesh.ops.split(...) but setting a destination to either another bmesh or a mesh is not yet implemented. Feb 9 '20 at 8:05
• @batFINGER I just posted a question about it, but I see that using bmesh.ops.split () disconnects all faces if I'm not mistaken Feb 18 '20 at 11:37

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

• Nice one. Ran a simple test on all solutions. Very little difference between top 3. Nov 6 '18 at 5:15
• Is it possible to return polygon indices instead of vert indices? Dec 15 '20 at 17:55

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


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 vert in polygon.verts:
if vert.index not in found_set:
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.

• Hi, was the opportunity to retest that old thing a bit! For your information (and that's true for batFinger answer too), have recursion depth limits (maximum recursion depth exceeded while calling a Python object) for a 10x10x10 cube array + merge by distance. Or is there a way to get rid of that? Sep 13 '19 at 10:21
• yes, recursion limit find more reading here: stackoverflow.com/a/3323013 , i have not tested my solution with a large disjoint mesh. tricky stuff. Sep 13 '19 at 10:26
• i suspect there's a nice numpy solution to this too, using a "Set Intersection Matrix", these are brute force problems :) Sep 13 '19 at 10:30
• sys.setrecursionlimit(1500) works on the 10x10x10 merged. But not faster it seems (same for batFinger). And we should guess what to set if not 1500. Interested in it too... Sep 13 '19 at 10:37
• my priority here is readability, ideally no-one is executing this kind of code more than once a frame, on large disjoint objects Sep 13 '19 at 11:23

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()

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

"""There are 2 verts in an edge so we need to add it twice."""

for i in range(2):

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()


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)