NEW!! Python BVH Tree for ray cast and collisions and snapping

Do you ray cast? Do you snap? Do you check for self intersections all with Python. Hot off the press since the commit linked below, your life got faster and easier.

https://developer.blender.org/rB18af73e461f9a943ae606fcc1401297f4afad20f

Here is what you need to know (from my limited perspective)

  1. Import and Initiate
from mathutils.bvhtree import BVHTree
 initiate from bmesh data, from object data, or from your own geometry

my_tree0 = BVHTree.FromObject(context.object, context.scene)  #other keyword arguments like "use_deform," "use render"
my_tree1 = BVHTree.FromBmesh(bme)  #super easy...give it a bmesh, no other questions
my_tree2 = BVHTree.FromPolygons(verts, polygons, all_triangles = False, epsilne = 0.0)

  1. raycasting and snapping are the similar…but different:
    Blender Object

hit, normal, index = object.ray_cast(start, end)
loc, normal, index = object.closest_point_on_mesh(target_loc)

 BVHTree functions return a tupple with 4 items.  raycast takes start and DIRECTION not start and end

hit, normal, index, distance = my_tree.ray_cast(start, direction, distance = max_distance)
loc, normal, index, distance = my_tree.find(target_loc)

  1. Do your own collision testing!?
overlap_pairs = my_tree.overlap(other_tree)
  1. Raycast appears to behave differently in perspective and ortho mode. Use test codeand test blend from next post to try it out.bb working fine after I used ray_cast code appropriately

  2. Who to Thank. Lukas Toenne and Campbell Barton.

A brief note on why this is important.

Before this…

  1. User’s couldn’t use the object method to ray cast a mesh that is currently in edit mode (editmode_toggle in a modal…YUCK!)
  2. There was overhead associated with the object methods, so it’s faster now
  3. To ray cast your own data involved making a temporary object and linking it to the scene
  4. Collision testing was difficult. Not sure there was any way to do this outside of a large manual ray casts of every edge with another object.

Addon’s that will benefit from this. Here are a few that come to mind.
Snap Tools (Mano Wii)
Retopoflow (CGCookie)
Asset Sketcher (Andreas Esau)
Mira Tools (Mifth)


import bpy
import bmesh
from bpy_extras import view3d_utils
from mathutils.bvhtree import BVHTree
from mathutils import Vector, Matrix


def get_ray_plane_intersection(ray_origin, ray_direction, plane_point, plane_normal):
    d = ray_direction.dot(plane_normal)
    if abs(ray_direction.dot(plane_normal)) <= 0.00000001: return float('inf')
    return (plane_point-ray_origin).dot(plane_normal) / d


def get_ray_origin(ray_origin, ray_direction, ob):
    mx = ob.matrix_world
    q  = ob.rotation_quaternion
    bbox = [Vector(v) for v in ob.bound_box]
    bm = Vector((min(v.x for v in bbox),min(v.y for v in bbox),min(v.z for v in bbox)))
    bM = Vector((max(v.x for v in bbox),max(v.y for v in bbox),max(v.z for v in bbox)))
    x,y,z = Vector((1,0,0)),Vector((0,1,0)),Vector((0,0,1))
    planes = []
    if abs(ray_direction.x)>0.0001: planes += [(bm,x), (bM,-x)]
    if abs(ray_direction.y)>0.0001: planes += [(bm,y), (bM,-y)]
    if abs(ray_direction.z)>0.0001: planes += [(bm,z), (bM,-z)]
    dists = [get_ray_plane_intersection(ray_origin,ray_direction,mx*p0,q*no) for p0,no in planes]
    return ray_origin + ray_direction * min(dists)








def main(self, context, event, ray_max=1000.0):
    """Run this function on left mouse, execute the ray cast"""
    # get the context arguments
    scene = context.scene
    region = context.region
    rv3d = context.region_data
    coord = event.mouse_region_x, event.mouse_region_y


    # get the ray from the viewport and mouse
    ray_vector = view3d_utils.region_2d_to_vector_3d(region, rv3d, coord).normalized()
    ray_origin = view3d_utils.region_2d_to_origin_3d(region, rv3d, coord)


    if rv3d.is_perspective:
        #ray_target = ray_origin + ray_vector * 100
        r1 = get_ray_origin(ray_origin, -ray_vector, context.object)
        ray_target = r1
    else:
        # need to back up the ray's origin, because ortho projection has front and back
        # projection planes at inf
        r0 = get_ray_origin(ray_origin,  ray_vector, context.object)
        r1 = get_ray_origin(ray_origin, -ray_vector, context.object)
        ray_origin = r0
        ray_target = r1


    def ray_cast_obj_bvh(obj, bvh, matrix):
        """Wrapper for ray casting that moves the ray into object space"""


        # get the ray relative to the object
        matrix_inv = matrix.inverted()
        ray_origin_obj = matrix_inv * ray_origin
        ray_target_obj = matrix_inv * ray_target
        ray_dir_obj = ray_target_obj - ray_origin_obj
        d = ray_dir_obj.length
        ray_dir_obj.normalize()
        # cast the ray
        hit, normal, face_index = obj.ray_cast(ray_origin_obj, ray_target_obj)


        #cast it again with BVH
        hit_b, normal_b, face_index_b, distance = bvh.ray_cast(ray_origin_obj, ray_dir_obj)
        
        if face_index != -1:
            return [(hit, normal, face_index),(hit_b, normal_b, face_index_b)]
        else:
            return [(None, None, None)]




    matrix = context.object.matrix_world
    results = ray_cast_obj_bvh(context.object, self.BVH, matrix)
    
    loc, no, f_ind = results[0]
    if loc:
        loc_b, no_b, f_indb = results[1]
        
        print((loc, loc_b))
        print((no, no_b))
        print((f_ind, f_indb))
           
        context.scene.cursor_location = matrix * loc
        if loc_b:
            bpy.data.objects['Lamp'].location = matrix * loc_b
        
class ViewOperatorRayCast(bpy.types.Operator):
    """Modal object selection with a ray cast"""
    bl_idname = "view3d.modal_operator_raycast"
    bl_label = "RayCast View Operator"


    def modal(self, context, event):
        if event.type in {'MIDDLEMOUSE', 'WHEELUPMOUSE', 'WHEELDOWNMOUSE'}:
            # allow navigation
            return {'PASS_THROUGH'}
        elif event.type == 'LEFTMOUSE':
            main(self, context, event)
            return {'RUNNING_MODAL'}
        elif event.type in {'RIGHTMOUSE', 'ESC'}:
            return {'CANCELLED'}


        return {'RUNNING_MODAL'}


    def invoke(self, context, event):
        if context.space_data.type == 'VIEW_3D':
            context.window_manager.modal_handler_add(self)
            
            ob = context.object
            
            
            if ob.hide or ob.type != 'MESH':
                self.report({'WARNING'}, "Active object must be visible and a mesh")    
                return {'CANCELLED'}
            
            self.BVH = BVHTree.FromObject(ob, context.scene)  
            return {'RUNNING_MODAL'}
        else:
            self.report({'WARNING'}, "Active space must be a View3d")
            return {'CANCELLED'}




def register():
    bpy.utils.register_class(ViewOperatorRayCast)




def unregister():
    bpy.utils.unregister_class(ViewOperatorRayCast)




if __name__ == "__main__":
    register()

http://www.pasteall.org/blend/37368

Unfortunately it looks like the ray cast crashes blender if you try to set a distance. It works if you leave the distance argument out but that doesn’t help much if you need to check for edge intersections. Maybe one of the other new functions in the bvh tree can do edge intersection?

import bpy
import numpy as np
from mathutils.bvhtree import BVHTree as tree


print('-----------start------------')
scene = bpy.data.scenes['Scene']
sphere = bpy.data.objects['Sphere']
c1 = bpy.data.objects['c1']
c2 = bpy.data.objects['c2']
b1 = bpy.data.objects['b1']




# code here:
def do_it_all():
    print('test')
    bvh = tree.FromObject(sphere, scene)
    #ray = bvh.ray_cast(c1.location,c2.location, 1.0) # this crashes    
    ray = bvh.ray_cast(c1.location,c2.location)    

    if ray[0] != None:    
        b1.location = ray[0]

Attachments

New_Collision_model.blend (595 KB)

I’m having the same trouble. I will report it as a bug tomorrow, I’m sure it’s a small problem that got left out.

On an uplifting note. MAJOR MAJOR speedups in my tests.
190x on my laptop - 2012 lenovo with core-i7 3610qm @ 2.3GHZ
250x on my girlfriend’s 2014 macbook pro




I believe the mathutils.bvhtree module can be further explored. Currently it only works with Tris, and could work for edges and vertices as well.
For this, I want to change the basic way it works. Here’s my proposal: https://developer.blender.org/D1803
What do you think?