Python: Locate specific islands of geometry within a mesh object

Question

If I have a mesh object, and the mesh data is made up of several disconnected islands of faces, and using Python I want to evaluate each island to check if it matches certain criteria, and if it does, store that island's median coordinate in a variable... how can that be achieved?

The example object in this screenshot has two circles I want to match. Each circle has 13 verts, 12 faces (which are all tris), and a total area of approximately 3. So if an island matches those criteria, we can consider it to qualify as the kind of circle we are after. Their medians would be [0,0,0] (the world center), and [0,3,0] (the 3D cursor location).

Now let's say we don't know how many such circles there will be in an object, or even how many objects to expect, and we have to identify each circle center programmatically and add those coords to a list. The fun begins!

I have solved some pieces of this puzzle already. I have written a simple script for finding the area of selected faces (as long as they're all tris, which they will be). Here is that script:

import bpy
import bmesh

obj = bpy.context.active_object

# make sure it's a mesh object
if obj.type != 'MESH':
    print('Error: Object is not a mesh object!')
else:
    bpy.ops.object.mode_set(mode='EDIT')

    me = obj.data # mesh data
    bm = bmesh.from_edit_mesh(me)

    ta = 0.0 # total area

    print('\n==== Area of selected faces ====')
    for f in bm.faces:
        if f.select: # selected faces only
            print('Face ' + str(f.index) + ' area is ' + str(f.calc_area()))
            ta = ta + f.calc_area() # add to total

    print('Total area is ' + str(ta))

I have also put together a script for finding the median of a set of vertices. I'll include it too for reference, although in its present form it targets the verts of an object's Vertex Group, not selected verts. Needs minor modifications:

import bpy
import statistics

context = bpy.context
scene = context.scene

act_obj = context.active_object # get active object

v_x = []
v_y = []
v_z = []

def cursor_to_vgroup(mesh_obj, vgroup_name):

  # This is an Object with a Mesh, see if it has the supported group name
  groupIndex = -1
  for i in range(0, len(mesh_obj.vertex_groups)):
    group = mesh_obj.vertex_groups[i]
    if group.name == vgroup_name:
      groupIndex = i

  # Now access the vertices that are assigned to this group
  mesh = mesh_obj.data
  for v in mesh.vertices:
    
    for vertGroup in v.groups:
      if vertGroup.group == groupIndex:
        
        v_global = mesh_obj.matrix_world @ v.co # global vertex coordinates
        
        v_x.append(v_global.x)
        v_y.append(v_global.y)
        v_z.append(v_global.z)

        cur_x = statistics.mean(v_x)
        cur_y = statistics.mean(v_y)
        cur_z = statistics.mean(v_z)

        scene.cursor.location = [cur_x, cur_y, cur_z]

cursor_to_vgroup(act_obj, 'Group')

And finally, I've found an interesting script someone wrote to get linked faces, but I'm not sure how / if I can customize it to sort the vertices into islands. And that's where I'm stuck - trying to figure out how to sort the geometry data into islands, so the island geometry can be checked for matches.

Would any Python wizards care to lend a hand?

^{.blend file contains the mesh object in the screenshot, and the area-getting script.}

Answer 1

Search for the 12 tri-fan poles.

Finding all the loose parts is going to be a rate determining step

How to detect disconnected parts within a selection?

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

but for quoted case

The example object in this screenshot has two circles I want to match. Each circle has 13 verts, 12 faces (which are all tris), and a total area of approximately 3. So if an island matches those criteria, we can consider it to qualify as the kind of circle we are after.

would not bother grinding away to find loose parts,instead search for potential pole verts, ie those that have exactly 12 linked edges and 12 triangles linked.

From there make sure that all the opposite edges of the tris, ie the edge not containing the pole is a boundary. Each vert of the boundary should be connected to exactly 3 edges.

Test script, prints the index of the poles the match the above criterea.

import bpy
import bmesh

context = bpy.context
ob = context.edit_object
me = ob.data

bm = bmesh.from_edit_mesh(me)

poles = [
        v for v in bm.verts 
        if len(v.link_faces) == len(v.link_edges) == 12
        and all(len(f.edges) == 3 for f in v.link_faces)
        ]
print("Potential Poles", [p.index for p in poles])
for p in poles:
    def check(f):
        return (
            bool(
                e for e in f.edges 
                if p not in e.verts 
                and e.is_boundary
                )
            and
                all(
                len(e.other_vert(p).link_edges) == 3
                for e in p.link_edges
                )
            )
    if all(check(f) for f in p.link_faces):
        print(p.index, "is a 12 tri fan pole")

once we have p and know it is a disconnected tri fan all the 13 verts would be for example

[p] + [e.other_vert(p) for e in p.link_edges]

the area

sum(f.calc_area() for f in p.link_faces) 

Putting it all together

^{(Added by @Mentalist based on @batFINGER's code)}

Here the script will check for triangle fan islands of geometry that match the specified face count and total area, find their centers, and take some action after finding those centers (in this example it places an Empty at each).

import bpy
import bmesh
import statistics

context = bpy.context
obj = context.view_layer.objects.active

def place_empty(coordinates): # create an Empty at the specified location
    bpy.ops.object.empty_add(type='PLAIN_AXES', radius=0.1, align='WORLD', location=coordinates, scale=(1, 1, 1))

def check_geom(ob, facecount, match_area, decplaces=3):
    if ob.type == 'MESH': # make sure it's a mesh
        bpy.ops.object.mode_set(mode='EDIT')
        me = ob.data
        bm = bmesh.from_edit_mesh(me).copy() # bmesh as a COPY
        bm.transform(ob.matrix_world) # that copy gets converted to world coords

        poles = [
            v for v in bm.verts 
            if len(v.link_faces) == len(v.link_edges) == facecount
            and all(len(f.edges) == 3 for f in v.link_faces)
            ]
        print("Potential Poles", [p.index for p in poles])
        for p in poles:
            def check(f):
                return (
                    bool(
                        e for e in f.edges 
                        if p not in e.verts 
                        and e.is_boundary
                        )
                    and
                        all(
                        len(e.other_vert(p).link_edges) == 3
                        for e in p.link_edges
                        )
                    )
            area = sum(f.calc_area() for f in p.link_faces)
            if all(check(f) for f in p.link_faces):
                print('\n' + str(p.index) + " is a " + str(facecount) + " tri fan pole, with an area of " + str(area) )
            if round(area, decplaces) == round(match_area, decplaces): # things to do if the area matches
                bpy.ops.object.mode_set(mode='OBJECT')
                v_x = []
                v_y = []
                v_z = []
                
                linked_verts = [p] + [e.other_vert(p) for e in p.link_edges] # verts of this island
                
                for v in linked_verts:
                    # populate lists with coordinates for each axis
                    v_x.append(v.co.x)
                    v_y.append(v.co.y)
                    v_z.append(v.co.z)
                    
                # average each list's values to find the center
                c_x = statistics.mean(v_x)
                c_y = statistics.mean(v_y)
                c_z = statistics.mean(v_z)
                center = [c_x, c_y, c_z] # mean of island vertices
                print('Center location: ' + str(center) )
                
                place_empty(center) # the action to take upon finding the circle centers
    else:
        print('Cannot proceed. Active object is not a mesh.')
                
check_geom(obj, 48, 0.045) # params: the object, the face count, the total face area (object must be a triangle fan mesh)

(684KB)