Comment détecter les pièces déconnectées dans une sélection?

Oct 17 2020

Considérez la sélection d'arêtes suivante:

Quel serait le moyen le plus rapide de renvoyer les indices des différentes parties de cette sélection? Je vise une sortie similaire à celle-ci: edge_indices = [[24, 46, 29, 47], [32, 52, 37, 53]]. L'objectif est de détecter des pièces séparées (déconnectées) dans une sélection.

Une possibilité serait de boucler sur chaque arête et de vérifier les arêtes connectées sélectionnées et d'enregistrer les différentes boucles d'arête, mais je pense qu'il devrait y avoir un moyen plus rapide de le faire.

Merci!

Réponses

3 lemon Oct 18 2020 at 10:10

Une version itérative

Chaque ligne est commentée ci-dessous, mais demandez en commentaire si quelque chose n'est pas clair.

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

3 batFINGER Oct 18 2020 at 09:57

Parcourez la sélection de manière récursive.

De la même manière que la méthode utilisée ici Comment trouver le nombre de pièces détachées avec l'API Python de Blender?

Prenez un bord de la sélection, marquez-le comme "visité" puis faites de même récursivement avec ses bords connectés jusqu'à ce qu'il n'y en ait plus. Ce sera une "île".
Retirez l'îlot de la sélection et revenez à 1.

~~La tagpropriété d'un élément bmesh reste persistante, même sans mettre à jour le bmesh, et AFAIK devra être réinitialisé à chaque fois.~~

Script de test, exécuté en mode édition avec les arêtes sélectionnées.

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)

Le chronométrer

Cependant, le code du citron semble être beaucoup plus rapide, je vais donc marquer la réponse de citron comme la plus utile.

En répondant, le citron a commenté il ne peut pas répondre. Avait un sentiment (s) qu'il ferait, avec une approche itérative, ce serait plus rapide et serait accepté.

A fait quelques optimisations pour la vitesse ( c'était à peu près un travail de copier-coller d'une réponse plus ancienne )

Comme indiqué et barré, mais supprimé l'utilisation de la tagpropriété
. A pris la conversion d'ensemble et l'arithmétique.
Mettre en cache la récursivité en utilisant functools.lru_cache
Récursé sur tous les connectés à chaque fois, plutôt que sur un seul bord. Cela réduit considérablement la profondeur de récursivité.

Ont inclus le script utilisé pour tester les deux scripts pour la vitesse, avec la mise en garde le script est exécuté en mode édition, et le résultat souhaité doit être converti en une liste de listes. (La méthode de minutage qui renvoie un générateur ne consommera pas les données et donnera un résultat de 0,01 milliseconde ou moins)

Le script de @ lemon est conçu pour fonctionner en mode objet. Pour s'assurer que la sélection est mise à jour, le maillage est mis à jour. Les fronts d'entrée sont calculés pour les deux. Tout ce qui ne fait pas partie de la méthode, par exemple les importations, les impressions, la création du bmesh n'est pas inclus.

Encore une fois: rapporte le temps nécessaire pour générer une liste de listes en utilisant les deux méthodes. Assurez-vous de modifier le nom du bloc de texte dans lequel se trouvent les scripts. Dans l'exemple ci-dessous, il s'agit de "batFINGER", le citron est de "citron".

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)

Résultats

Ran sur un maillage de test avec à la fois des pièces détachées et de grandes zones contiguës. En règle générale, l'approche itérative est plus rapide pour les grandes zones connectées.