How to make a FindOverlap script more efficient?

Hello!
I am a student currently trying to develop an add-on in Blender which is designed for use with STEP files. This means that it will have to handle thousand of objects, often more than 5.000 objects.

I have a FindOverlap function which works so far. However, it is very slow and sometimes, Blender even freezes. Since this is my first code project ever and I have no prior experience, I sadly do not know how to make the code more efficient so that it runs a bit faster. I understood that it’s useful to break the code up into smaller snippets but I’m not sure how to go about it with this function.

Do you perhaps have recommendations or ideas for how to make this more efficient?
Thank you in advance!

class FindOverlap(bpy.types.Operator):
    """This script will select any overlapping objects in the scene"""
    bl_idname = "object.find_overlap"
    bl_label = "Find Overlapping Objects"
   
    def execute(self, context):
        
#        bpy.ops.object.select_all(action='SELECT')
        
        for obj1 in bpy.data.objects:
            for obj2 in bpy.data.objects:
                if obj1.type == 'MESH' and obj2.type == 'MESH':
                    if obj1.matrix_world == obj2.matrix_world:                  
                        continue
                    
                
                if obj1.type == 'MESH' and obj2.type == 'MESH':
                    #get their world matrix
                    matr1 = obj1.matrix_world
                    matr2 = obj2.matrix_world
                    
#                    if obj1.data != obj2.data:
#                        continue
            
                    #get the geometry in world coordinates
                    vert1 = [matr1 @ v.co for v in obj1.data.vertices]
                    poly1 = [p.vertices for p in obj1.data.polygons]
        
                    vert2 = [matr2 @ v.co for v in obj2.data.vertices]
                    poly2 = [p.vertices for p in obj2.data.polygons]
        
                    #create the BVH trees
                    bvh1 = BVHTree.FromPolygons(vert1, poly1)
                    bvh2 = BVHTree.FromPolygons(vert2, poly2)
                    
                    
            
                    #test if overlap 
                    if bvh1.overlap(bvh2):                    
                        print ("Overlapping objects found: ",obj1.name,",",obj2.name)
                        obj1.select_set(True)
                        obj2.select_set(True) 
                    
            else:
                pass
       
       #TO-DO: dialog pop-up with amount of overlapping objects!
       
        return {'FINISHED'}
    

def menu_func(self, context):
    self.layout.operator(FindOverlap.bl_idname, text=FindOverlap.bl_label)
1 Like

One thing I see right off the bat is that you’re evaluating this exact if expression twice:

                if obj1.type == 'MESH' and obj2.type == 'MESH':
                    if obj1.matrix_world == obj2.matrix_world:                  
                        continue
                    
                
                if obj1.type == 'MESH' and obj2.type == 'MESH':
                    #get their world matrix
                    matr1 = obj1.matrix_world
                    matr2 = obj2.matrix_world

And one of these if statements isn’t really doing anything, other than wasting time- by continuing if they’re the same, you’re evaluating the check and then moving on.
You could combine these into one if statement:

if obj1.type == 'MESH' and obj2.type == 'MESH':
    if obj1.matrix_world != obj2.matrix_world:
        matr1, matr2 = obj1.matrix_world, obj2.matrix_world

Removing that double if statement will speed things up for sure, probably not a lot but you should see an improvement. That’s a start, at least

Technically even after making the improvement mentioned by @josephhansen you are still testing more than you should.

ex.

test_grp = ['a', 'b', 'c', 'd']

for me1 in test_grp:
    for me2 in test_grp:
        if not me1 == me2:
            print(f"({me1}, {me2})")

(a, b)
(a, c)
(a, d)
(b, a)
(b, c)
(b, d)
(c, a)
(c, b)
(c, d)
(d, a)
(d, b)
(d, c)

Since you are only concerned about any intersection not the order of operation once (a, b) is tested you do not need to test (b, a).

As such one way to reduce the qty of tests would be to create a new list in the outer loop that reduces the list of items to be tested in the inner loop each iteration.

test_grp = ['a', 'b', 'c', 'd']

tg2 = test_grp

for me1 in test_grp:
    for me2 in tg2:
        if not me1 == me2:
            print(f"({me1}, {me2})")
    tg2.remove(me1)

(a, b)
(a, c)
(a, d)
(c, b)
(c, d)

To further simplify you can remove the selected item in the outer loop prior to your inner loop and not need to test me1 == me2

test_grp = ['a', 'b', 'c', 'd']

tg2 = test_grp

for me1 in test_grp:
    tg2.remove(me1)
    for me2 in tg2:
        print(f"({me1}, {me2})")

To show the kind of improvement this provides on a larger scale:

num_tests = 0
test_objs = 10000

test_grp = list(range(test_objs))
tg2 = test_grp

for me1 in test_grp:
    for me2 in test_grp:
        if not me1 == me2:
            num_tests += 1

print(f"performed {num_tests} tests in method 1")



num_tests = 0

for me1 in test_grp:
    tg2.remove(me1)
    for me2 in tg2:
        num_tests += 1

print(f"performed {num_tests} tests in method 2")

performed 99990000 tests in method 1
performed 37497500 tests in method 2

1 Like

Also you can filter out the non mesh objects prior to your loops.

mesh_objs = [obj for obj in bpy.data.objects if obj.type == 'MESH']

Then instead of:

for obj1 in bpy.data.objects:

use:

for obj1 in mesh_objs:

Depending on how many non mesh objects you have in the file this may or may not help much but potentially cuts back on some loops.

2 Likes

You can do efficient comparison loops by using a list, a while loop, popping an item, then loop over the remaining items.
A simple heuristic like comparing bounding boxes helps ruling out non-intersecting objects.
Using a dictionary you can cache bvh trees for later comparisons to avoid rebuilds.

Example:

import bpy
from mathutils.bvhtree import BVHTree
from mathutils import Vector


# Fixed bounding box triangle indices
bb_tris = [
    [0, 1, 3], [0, 3, 2], [2, 3, 7],
    [2, 7, 6], [6, 7, 5], [6, 5, 4],
    [4, 5, 1], [4, 1, 0], [2, 6, 4],
    [2, 4, 0], [7, 3, 1], [7, 1, 5]
]


# bvh tree of an object (world space)
def bvh_world(ob):
    m = ob.matrix_world
    v_world = [m @ v.co for v in ob.data.vertices]
    polys = [p.vertices[:] for p in ob.data.polygons]
    return BVHTree.FromPolygons(v_world, polys)


# bvh tree of an object's bounding box (world space)
def bvh_bb(ob):
    m = ob.matrix_world
    v_world = [m @ Vector(co) for co in ob.bound_box]
    return BVHTree.FromPolygons(v_world, bb_tris, all_triangles=True)


class FindOverlap(bpy.types.Operator):
    """This script will select any overlapping objects in the scene"""
    bl_idname = "object.find_overlap"
    bl_label = "Find Overlapping Objects"

    def execute(self, context):
        meshes = [ob for ob in bpy.data.objects if ob.type == 'MESH']
        cache = dict()  # Store BVH trees

        def from_cache(ob):
            if ob in cache:
                return cache[ob]
            cache[ob] =  bvh_world(ob)
            return cache[ob]

        while meshes:
            ob1 = meshes.pop()
            bb1 = bvh_bb(ob1)

            for ob2 in meshes:
                if bb1.overlap(bvh_bb(ob2)):

                    bvh1 = from_cache(ob1)
                    bvh2 = from_cache(ob2)

                    if bvh1.overlap(bvh2):                    
                        ob1.select_set(True)
                        ob2.select_set(True) 

            cache.pop(ob1, None)  # Finished with object, release BVH

        return {'FINISHED'}
    

def menu_func(self, context):
    self.layout.operator(FindOverlap.bl_idname, text=FindOverlap.bl_label)

if __name__ == "__main__":
    bpy.utils.register_class(FindOverlap)
    bpy.ops.object.find_overlap()
2 Likes

Thank you for all your replies, I just read them now! I will try them out and let you know how well it worked. Thanks so much! :slight_smile:

1 Like

Thank you for the reply! Could you explain what the fixed bounding box triangle indices are for and from where the values are retrieved? :slight_smile:

Hi, thank you for your reply! I think it’s a good idea to shorten the list of obejcts that need to be tested. However, I struggle a little to understand the following part:

for me1 in test_grp:
    tg2.remove(me1)

Why exactly is it being removed?

It is removed prior to the second loop because there is no need to test objectA to objectA. Your if statement would already skip this. It is also removed so that you do not test objectA intersects objectB and also test objectB intersects objectA.

If objectA and objectB intersect it doesn’t matter which reference point you started from.

1 Like

I understand now, thank you! :slight_smile:

The fixed indices are used to create the polygons needed for a bvh tree of a bounding box. Because a bounding box verts’ length never change (only their coordinates do), we can use a fixed list of indices for the polygons.
These are simply taken from the default cube’s loop triangles.

# Assuming 'cube' is the default cube

cube.calc_loop_triangles()
indices = [list(lt.vertices) for lt in cube.data.loop_triangles]

1 Like