Recursively walk the selection.
Similarly to the method employed here How to find the number of loose parts with Blender's Python API?
- Take one edge of the selection, tag it as "visited" then recursively
do same with its connected edges until no more. This will be an
"island".
- Remove the island from the selection, and return to 1.
The tag
property of a bmesh element remains persistent, even without updating the bmesh, and AFAIK will need to be reset each time.
Test script, run in edit mode with edges selected.
import bpy
import bmesh
from collections import defaultdict
import sys
from functools import lru_cache
def recursion_limit(method):
def rec(edges, **kwargs):
sys.setrecursionlimit(max(len(edges) >> 1, 1000))
result = method(edges, **kwargs)
sys.setrecursionlimit(1000)
return result
return rec
@recursion_limit
def edge_islands(edges, as_indices=True):
tags = defaultdict(bool)
tags.update({e : True for e in edges})
@lru_cache(128)
def walk(tree):
for edge in tree:
if tags[edge]:
yield edge.index if as_indices else edge
del tags[edge]
leaves = tuple(
set(
e for edge in tree
for v in edge.verts
for e in v.link_edges
if tags[e]
)
)
if leaves:
yield from walk(leaves)
return list(
list(walk((e,)))
for e in list(tags.keys())
if tags[e]
)
if __name__ == "__main__":
# test call on mesh in edit mode
context = bpy.context
ob = context.object
me = ob.data
bm = bmesh.from_edit_mesh(me)
selected_edges = [e for e in bm.edges if e.select]
print("Input", len(selected_edges))
islands = edge_islands(selected_edges)
print(len(islands), "Islands", islands)
Time It
However, lemon's code seems to be quite a lot faster, so I will mark
lemon's answer as most helpful
On answering lemon commented he may not answer. Had a feeling (s)he would, with an iterative approach, it would be faster and would be accepted.
Did some optimizing for speed (it was pretty much a copy paste job from an older answer)
- As noted and striked-though removed the use of the
tag
property
- . Took out set conversion and arithmetic.
- Cached the recursion using
functools.lru_cache
- Recursed on all connected each time, rather than a single edge. This greatly reduces the recursion depth.
Have included the script used to test the two scripts for speed, with the caveat the script is run in edit mode, and the result desired needs to be converted to a list of lists. (Timing method that returns a generator will not consume the data and give a result of 0.01 or less milliseconds)
@lemon's script is designed to run in object mode. To make sure the selection is updated the mesh is updated. The input edges are calculated for both. Anything outside the method eg imports, prints, creating the bmesh is not included.
Once again: reports the time taken to generate a list of lists using the two methods. Make sure to edit the text block name the scripts are in. In example below this is in "batFINGER", lemon's in "lemon".
import bpy
import bmesh
from random import randint
bat = bpy.data.texts["batFINGER"].as_module()
lem = bpy.data.texts["lemon"].as_module()
def timeit(method):
import time
def timed(*args, **kw):
ts = time.time()
result = method(*args, **kw)
te = time.time()
print(f"{method.__name__ : <23} {(te - ts) * 1000 :6.2f} ms")
return result
return timed
@timeit
def batfinger(edges):
return bat.edge_islands(edges)
@timeit
def lemon(edges):
return [[e.index for e in island] for island in lem.islands(edges)]
context = bpy.context
ob = context.object
me = ob.data
bm = bmesh.from_edit_mesh(me)
selected_edges = [e for e in bm.edges if e.select]
batfinger(selected_edges)
#lemon test,
ob.update_from_editmode()
selected_edges = [e for e in me.edges if e.select]
lemon(selected_edges)
Results
Ran over a test mesh with both loose parts and large contiguous areas. As a rule of thumb the iterative approach is quicker for large connected areas.
After the optimizations results are comparable.
----------------------------------------
79010 Edges
batfinger 741.60 ms
lemon 707.91 ms
Islands: 3625 Largest: 4124
----------------------------------------
79010 Edges
batfinger 759.15 ms
lemon 830.18 ms
Islands: 3625 Largest: 4124
----------------------------------------
79010 Edges
batfinger 759.82 ms
lemon 710.61 ms
Islands: 3625 Largest: 4124
----------------------------------------
79010 Edges
batfinger 750.31 ms
lemon 836.75 ms
Islands: 3625 Largest: 4124
Related
Is there a way to assign vertex groups to all loose elements via python
How to use loopcut_slide operation without any UI?
What is the bmesh equivalent to bpy.ops.mesh.shortest_path_select()?