14
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Related: blender.stackexchange.com/q/8613/599 $\endgroup$ – gandalf3 May 2 '14 at 7:41
  • $\begingroup$ Maybe you could use a boolean modifier, although I am not sure how to do that in a script. Say you have two objects O1 and O2. Make a copy of O1 (i'll call it C1) and give it a boolean modifier. Set the 'Operation' to Interesect and the 'Object' to O2. Then apply the modifier and check how many vertices C1 now has. If if is more than zero, the objects intersect. This should also work if one object lies completely inside the other. $\endgroup$ – maddin45 May 2 '14 at 14:37
  • $\begingroup$ There is this solution too (for bounding boxes) Simple 3D Collision Detection with Python Scripting in Blender $\endgroup$ – gordie Apr 11 '18 at 7:48
19
$\begingroup$

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:

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)
    scene.update()
    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

        co, no, index = ray_cast(co_1, co_2)
        if index != -1:
            intersect = True
            break

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

    scene.update()

    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.

$\endgroup$
  • $\begingroup$ Thanks, your answer is very helpful (I will remember to upvote when I have enough rep). There is unexpected special case though: if one object intersects with triangle(s) in another object but not with any of its edges, script may not find intersection (depends on which object will be chosen as "simple"). But it was very easy to fix, if casting rays from the simpler to the more complex object finds no intersection, try the other way around. $\endgroup$ – Lissanro Rayen May 3 '14 at 2:59
  • $\begingroup$ Good find! I did not expect such issues since both meshes are triangulated. Maybe there's another way to handle this corner case without casting a lot of rays again? I admit, I don't fully understand what is done in the calculation for the ray start and end points, maybe something can be improved here? $\endgroup$ – CoDEmanX May 3 '14 at 11:37
  • $\begingroup$ This corner case is common in scenes with object(s) intersecting with large plane or low-poly leaves intersecting with each other, etc. It is possible to cast less rays by using "continue" if current edge is not touching volume of intersection of bounding boxes. However, most of the time is spent in bmesh_copy_from_object(), even if we call it no more than once per each object, it still takes many times more than anything else. Removing bmesh.ops.triangulate() line gives very noticeable improvement. What was the purpose of triangulation? $\endgroup$ – Lissanro Rayen May 4 '14 at 10:35
  • 1
    $\begingroup$ Hi, anything new/up-to-date with this ? This script gives me an error at the line co, no, index = ray_cast(co_1, co_2) $\endgroup$ – gordie Apr 11 '18 at 7:46
  • 3
    $\begingroup$ The signature changed: bpy.types.Object.ray_cast (origin, direction, distance), was (start, end) $\endgroup$ – CoDEmanX Apr 11 '18 at 9:49

Not the answer you're looking for? Browse other questions tagged or ask your own question.