How to check if two meshes intersect in python?

Question

I need to check if two meshes intersect or not. At the moment I have some python code to find intersections of world axes aligned bounding boxes, next step would be to implement check for mesh intersection for objects with intersecting bounding boxes.

In Blender Python API I found only very low level functions (like check if ray intersects a triangle), unless I'm missing something using them for my purpose would be slow and inefficient. Is there some kind of python library I could use?

By the way, I think all I need is already implemented in rigid body physics: it has a noticeable reaction when objects are intersecting, and seems to be well optimized. But I think I cannot access its internal data like if there is mesh intersection, so I have to continue with my own implementation. Please correct me if I'm wrong.

What I'm actually trying to achieve is to be able to do something with intersecting objects, for example search for intersecting objects in selection, and then delete or select them, but it all boils down to checking if two meshes intersect or not.

Answer 1

There's unfortunately no way to use the Bullet physics engine to test for collisions. So you really have to ray_cast() to find intersections.

The 3D Printing Toolbox addon comes with a self-intersection checker. I quickly adapted the code to test for intersections between two objects (updated for Blender 2.80+):

import bpy
import bmesh

def bmesh_copy_from_object(obj, transform=True, triangulate=True, apply_modifiers=False):
    """
    Returns a transformed, triangulated copy of the mesh
    """

    assert(obj.type == 'MESH')

    if apply_modifiers and obj.modifiers:
        me = obj.to_mesh(bpy.context.scene, True, 'PREVIEW', calc_tessface=False)
        bm = bmesh.new()
        bm.from_mesh(me)
        bpy.data.meshes.remove(me)
    else:
        me = obj.data
        if obj.mode == 'EDIT':
            bm_orig = bmesh.from_edit_mesh(me)
            bm = bm_orig.copy()
        else:
            bm = bmesh.new()
            bm.from_mesh(me)

    # Remove custom data layers to save memory
    for elem in (bm.faces, bm.edges, bm.verts, bm.loops):
        for layers_name in dir(elem.layers):
            if not layers_name.startswith("_"):
                layers = getattr(elem.layers, layers_name)
                for layer_name, layer in layers.items():
                    layers.remove(layer)

    if transform:
        bm.transform(obj.matrix_world)

    if triangulate:
        bmesh.ops.triangulate(bm, faces=bm.faces)

    return bm

def bmesh_check_intersect_objects(obj, obj2):
    """
    Check if any faces intersect with the other object

    returns a boolean
    """
    assert(obj != obj2)

    # Triangulate
    bm = bmesh_copy_from_object(obj, transform=True, triangulate=True)
    bm2 = bmesh_copy_from_object(obj2, transform=True, triangulate=True)

    # If bm has more edges, use bm2 instead for looping over its edges
    # (so we cast less rays from the simpler object to the more complex object)
    if len(bm.edges) > len(bm2.edges):
        bm2, bm = bm, bm2

    # Create a real mesh (lame!)
    scene = bpy.context.scene
    me_tmp = bpy.data.meshes.new(name="~temp~")
    bm2.to_mesh(me_tmp)
    bm2.free()
    obj_tmp = bpy.data.objects.new(name=me_tmp.name, object_data=me_tmp)
    # scene.objects.link(obj_tmp)
    bpy.context.collection.objects.link(obj_tmp)
    ray_cast = obj_tmp.ray_cast

    intersect = False

    EPS_NORMAL = 0.000001
    EPS_CENTER = 0.01  # should always be bigger

    #for ed in me_tmp.edges:
    for ed in bm.edges:
        v1, v2 = ed.verts

        # setup the edge with an offset
        co_1 = v1.co.copy()
        co_2 = v2.co.copy()
        co_mid = (co_1 + co_2) * 0.5
        no_mid = (v1.normal + v2.normal).normalized() * EPS_NORMAL
        co_1 = co_1.lerp(co_mid, EPS_CENTER) + no_mid
        co_2 = co_2.lerp(co_mid, EPS_CENTER) + no_mid

        success, co, no, index = ray_cast(co_1, (co_2 - co_1).normalized(), distance = ed.calc_length())
        if index != -1:
            intersect = True
            break

    # scene.objects.unlink(obj_tmp)
    bpy.context.collection.objects.unlink(obj_tmp)
    bpy.data.objects.remove(obj_tmp)
    bpy.data.meshes.remove(me_tmp)


    return intersect
# obj = bpy.context.object
# obj2 = (ob for ob in bpy.context.selected_objects if ob != obj).__next__()
# intersect = bmesh_check_intersect_objects(obj, obj2)

# print("There are%s intersections." % ("" if intersect else " NO"))

Select two mesh objects and run the script. It will print the result to the system console.

Note that there's a special case: If, for instance, a cube is fully inside another cube, it will report "NO intersections" - since there are none. But if you think of the objects as solid bodies, they do collide.

Answer 2

Here's an extremely fast method using BVHTree.

from mathutils.bvhtree import BVHTree
import bpy
import bmesh

def create_bvh_tree_from_object(obj):
    bm = bmesh.new()
    bm.from_mesh(obj.data)
    bm.transform(obj.matrix_world)
    bvh = BVHTree.FromBMesh(bm)
    bm.free()
    return bvh


def check_bvh_intersection(obj_1, obj_2):
    bvh1 = create_bvh_tree_from_object(obj_1)
    bvh2 = create_bvh_tree_from_object(obj_2)
    return bvh1.overlap(bvh2)


# Test on file objects
for obj_1 in bpy.data.objects:
    if obj_1.type != "MESH":
        continue
    for obj_2 in bpy.data.objects:
        if obj_2.type != "MESH" or obj_2 == obj_1:
            continue
        intersection = check_bvh_intersection(obj_1, obj_2)
        print(f"{obj_1.name}{'' if intersection else ' DOES NOT'} intersect {obj_2.name}")