11
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Very nice, and much faster than my algorithm. $\endgroup$ – JakeD Mar 11 '17 at 13:40
5
$\begingroup$

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)
$\endgroup$
  • $\begingroup$ Nice one. Ran a simple test on all solutions. Very little difference between top 3. $\endgroup$ – batFINGER Nov 6 '18 at 5:15
5
$\begingroup$

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
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – lemon Apr 17 '18 at 9:28
  • $\begingroup$ Thanks @lemon Put all meshes in blend in loop in to emphasize speed, has blossomed into one more UV so far lol. $\endgroup$ – batFINGER Nov 6 '18 at 5:18
  • $\begingroup$ 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). $\endgroup$ – lemon Sep 14 at 6:11
2
$\begingroup$

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)
$\endgroup$
1
$\begingroup$

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.

enter image description here

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()
$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – lemon Sep 13 at 10:21
  • $\begingroup$ yes, recursion limit find more reading here: stackoverflow.com/a/3323013 , i have not tested my solution with a large disjoint mesh. tricky stuff. $\endgroup$ – zeffii Sep 13 at 10:26
  • $\begingroup$ i suspect there's a nice numpy solution to this too, using a "Set Intersection Matrix", these are brute force problems :) $\endgroup$ – zeffii Sep 13 at 10:30
  • $\begingroup$ 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... $\endgroup$ – lemon Sep 13 at 10:37
  • $\begingroup$ my priority here is readability, ideally no-one is executing this kind of code more than once a frame, on large disjoint objects $\endgroup$ – zeffii Sep 13 at 11:23

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.