0
$\begingroup$

In Python is there a way to test if two objects overlap?

I am somewhat randomizing the location of two objects and I need to make sure that they do not overlap.

I have spent several hours (without success) trying to come up with my own algorithm, but I am now wondering if maybe I can use an existing function instead...

Thanks in advance for your suggestions!

$\endgroup$
  • 2
    $\begingroup$ There are various ways of testing for intersection, some more complex than others. How precise do you need to be? Are the objects arbitrary polygonal meshes and you need exact intersection testing, or would just bounding box comparisons suffice? Are you randomizing the rotation and scale as well as location? $\endgroup$ – acro Aug 27 at 2:29
  • $\begingroup$ @acro cubes of uniform size, on the same plane on axis Z; some randomization of Y and X; rotated randomly somewhat on axis Z. $\endgroup$ – vndep Aug 27 at 11:21
  • 4
    $\begingroup$ Consider: "python 2.8" is misleading -> Blender is using python 3.7 already $\endgroup$ – brockmann Aug 27 at 11:29
  • $\begingroup$ @acro, why this edit adding "in the XY plane"? $\endgroup$ – lemon Aug 28 at 11:22
  • 2
    $\begingroup$ @lemon from vndep's add-on comment where he said the test for separation is for objects only varying in that plane. i'm not too experienced with the guidelines yet, thought it clarified the question? $\endgroup$ – acro Aug 28 at 12:27
3
$\begingroup$

There is a Python API to do that. BVHTree.overlap

It is nearly direct, we just need to convert objects vertices in world coordinates:

import bpy
from mathutils.bvhtree import BVHTree

# Get the objects
obj1 = bpy.data.objects["Cube"]
obj2 = bpy.data.objects["Suzanne"]

# Get their world matrix
mat1 = obj1.matrix_world
mat2 = obj2.matrix_world

# Get the geometry in world coordinates
vert1 = [mat1 @ v.co for v in obj1.data.vertices] 
poly1 = [p.vertices for p in obj1.data.polygons]

vert2 = [mat2 @ 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( "Overlap" )
else:
    print( "No overlap" )
$\endgroup$
1
$\begingroup$

With all the objects being same-sized cubes on the same Z, you only need to worry about XY. Three possible levels to consider going about this, in increasing order of complexity:

  1. Just rough it with circle separation. If you treat each object as if it were a circle, no Z-rotation will matter. A cube with half-width ('radius') 1 will fit inside a circle of radius sqrt(2) - with its corners touching that circle. In that case, the cheap and nasty quick way to detect all these sorts of overlaps is just using the distance formula between the object centers to see if that distance is less than two of these radii. Like...

    import bpy
    from math import sqrt
    
    def dist(a, b):
        dx = a.location[0] - b.location[0]
        dy = a.location[1] - b.location[1]
        return sqrt(dx*dx + dy*dy)
    
    minDist = 2 * circRadius
    
    cubes = [ob for ob in bpy.data.objects if ob.name.startswith("Cube")]
    
    for cube in cubes:
        for other in cubes:
            if other != cube:
                if dist(cube, other) < minDist:
                    print("%s and %s overlap." % (cube.name, other.name))
    

Note that this will report false positive overlaps on cubes that are closely aligned and close by each other, not touching, but still within the approximate circles.

  1. If you want to get more 'proper' or accurate, that starts to get more into 'collision detection' topics. You may want to read up on how games check for overlaps, eg SAT (the separating axis theorem).

  2. Blender definitely has utilities for doing this sort of thing internally. I don't know its internals well enough to know what's all in there, having not done this exact thing before, but it sounds like a common need. The boolean tool is bound to detect things exactly. Even just testing this basic stuff, I noticed in the Scripting workspace that there's internal modules like mathutils, mathutils.geometry, and that objects have functions such as closest_point_on_mesh, ray_cast, and so on. Familiarizing yourself with these and searching through/reading the API docs will pay dividends, if you need a more exact solution. For example, at a glance I also see spatial partitioning helpers such as mathutils.bvhtree, mathutils.kdtree, and others.

$\endgroup$

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.