2
$\begingroup$

Consider the following edge selection:

enter image description here

What would be the fastest way to return the indices of the different parts of this selection? I am aiming for an output similar to this: edge_indices = [[24, 46, 29, 47], [32, 52, 37, 53]]. The goal is to detect separate (disconnected) parts within a selection.

One possibility would be to loop over every edge and check for selected connected edges and save the different edge loops, but I feel there should be a faster way to do this.

Thanks!

$\endgroup$
3
$\begingroup$

An iterative version

Each line is commented below but ask in comment if anything is unclear.

import bpy
from collections import defaultdict

# Get edge vertex that is not inside the vert_indices
def other_vert(e, vert_indices):
    return e.vertices[1] if e.vertices[0] in vert_indices else e.vertices[0]

def islands(edges):
    # Will store vertex index to concerned edge list
    d = defaultdict(list)
    # Will store not encountered edges
    not_done = set()
    
    # Prepare the dict and set above
    for e in edges:
        v0 = e.vertices[0]
        v1 = e.vertices[1]
        d[v0].append(e)
        d[v1].append(e)
        not_done.add(e)

    # While some edges are not encountered so far 
    while not_done:
        # Take a starting one
        e = not_done.pop()
        # Start with one of its vertices
        verts = set(e.vertices)
        # This first edge belong to the loop
        loop = [e]
        # While next vertices
        while verts:
            # Gets corresponding new edges
            new_edges = set(e for v in verts for e in d[v] if e in not_done)
            # Remove them: they are encountered
            not_done.difference_update(new_edges)
            #for e in new_edges: not_done.remove(e)
            # Get next vertices
            verts = set(other_vert(e, verts) for e in new_edges)
            # Add the edges to the loop
            loop.extend(new_edges)
        # Yield return each loop
        yield loop

obj = bpy.context.object

edges = [e for e in obj.data.edges if e.select]

print("-")
for island in islands(edges):
    print([e.index for e in island])
$\endgroup$
7
  • $\begingroup$ Both lemon and batFINGER have done the job perfectly. However, lemon's code seems to be quite a lot faster, so I will mark lemon's answer as most helpful. $\endgroup$
    – Niels
    Oct 18 '20 at 11:52
  • $\begingroup$ @lemon in case you missed comment on answer below, this needs a minor fix. It appears the poles on the UV sphere cause a keyerror trying to remove edge from list again. $\endgroup$
    – batFINGER
    Oct 21 '20 at 14:02
  • 1
    $\begingroup$ @batFINGER, thanks. Bug corrected I think. Replaced a loop by difference_update (which should be faster, by the way). $\endgroup$
    – lemon
    Oct 22 '20 at 6:57
  • $\begingroup$ @lemon I ran your script in a .blend with an active object (in both Edit and Object modes, with and without geometry selected). But the output is always just - It never does print([e.index for e in island]) What am I misunderstanding or doing wrong? Thanks. $\endgroup$
    – Mentalist
    Dec 16 '20 at 9:48
  • 1
    $\begingroup$ @Mentalist if you want to consider all edges, change this line edges = [e for e in obj.data.edges if e.select] $\endgroup$
    – lemon
    Dec 16 '20 at 9:56
4
$\begingroup$

Recursively walk the selection.

Similarly to the method employed here How to find the number of loose parts with Blender's Python API?

  1. 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".
  2. 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()?

$\endgroup$
7
  • $\begingroup$ Both lemon and batFINGER have done the job perfectly. However, lemon's code seems to be quite a lot faster, so I will mark lemon's answer as most helpful. $\endgroup$
    – Niels
    Oct 18 '20 at 11:54
  • $\begingroup$ NP. Been meaning to have a look into the loose parts re optimize for speed, as well as fix recursion limit. . Favour the logic of recursion. $\endgroup$
    – batFINGER
    Oct 19 '20 at 17:56
  • $\begingroup$ Hi @batFINGER, as for the previous question, the elapse rely on island count/edge count ratio... so (I've commented about it on blender.stackexchange.com/questions/75332/… $\endgroup$
    – lemon
    Oct 19 '20 at 18:08
  • 1
    $\begingroup$ @batFINGER, as I've corrected my bug. 6x6x6 sphere is around 0.56s, and 0.45s for yours (which is faster here, so). But if I merge by distance the spheres (so 1 island), yours is 1.16s and mine is 0.59s. $\endgroup$
    – lemon
    Oct 22 '20 at 7:12
  • $\begingroup$ @lemon Yes get similar results. (Albeit with a 3x slower PC) and agreed (and noted above) the iterative approach is faster for a large contiguous area. Growing the selection sent back via recursion has reduced the time considerably, compared to prior incarnation... where it was absolutiely awful. (One mega sub'd edge would be the worst, akin to version 1) $\endgroup$
    – batFINGER
    Oct 22 '20 at 7:27

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.