Page MenuHome

New mathutils submodule for BVH tree support in python.
AbandonedPublic

Authored by Campbell Barton (campbellbarton) on Jan 3 2015, 11:43 AM.

Details

Summary

The current functions for ray_cast and closest_point_on_mesh on bpy.types.Scene and bpy.types.Object are good for quick casting of a few rays, but they become very slow when called many times. This is because the internal BVHTreeFromMesh methods, though caching the actual BVHTree instance, still allocate extra data on construction every time (for poly index mapping) and also rely on the DerivedMesh not being updated. The RNA system further does not allow creation of temporary non-DNA PyObjects.

The solution is the introduction of a new mathutils.bvhtree submodule (similar to mathutils.kdtree). A BVHTree instance can then be created in advance, used for many ray casts or closest-element lookups, and then discarded:

N = large_number

# previously
for i in range(N):
    ob.ray_cast(start, end) # very slow due to constant overhead

# new
from mathutils import bvhtree
tree = bvhtree.DerivedMeshBVHTree(ob) # BMesh variant is also available

for i in range(N):
    tree.ray_cast(start, end) # much faster

del tree # not strictly necessary, just explicit cleanup

Two variants of the BVHTree class are available at this point, one for object-based meshes (using DerivedMesh internally) and one for BMesh data.

Diff Detail

Repository
rB Blender
Branch
mathutils_bvhtree

Event Timeline

Lukas Toenne (lukastoenne) retitled this revision from to New mathutils submodule for BVH tree support in python..
Lukas Toenne (lukastoenne) updated this object.
Lukas Toenne (lukastoenne) updated this revision to Diff 3097.EditedJan 5 2015, 10:49 AM

mathutils.bvhtree submodule functions for ray cast and find-nearest now
support non-Vector tuples like the rest of mathutils.

Also the keywords have been removed for slight performance improvement.

Generally good start, Think it would be good to add the ability to create a BVHTree from scratch (from only Python data),
so we have some more generalized cases, since the current code assumes BMesh or DerivedMesh.

Would also be interesting to add the ability to overlap 2 kdtree's, but not essential inclusion.

source/blender/python/mathutils/mathutils_bvhtree.c
56

Note, both BVHTreeFromMesh and BMBVHTree have a BVHTree pointer.

Currently there isnt much code-reuse going on, but there could be a function.

BVHTree *bvhtree_from_py(PyBVHTree *py_bvhtree); .. that would return the struct from either tree types.

112

using the squared distance is an optimization for C, but for Python API consistancy it may be less trouble to sqrt the value.

125

this can be omitted (Python will fill it in), assume you had it incase it eas useful to free values at some point.

213

think it would be good to be able to get access to different DM types, or at least to consider it for inclusion in the API.

See bpy_bmesh_from_object
https://developer.blender.org/diffusion/B/browse/master/source/blender/python/bmesh/bmesh_py_types.c$967

Where you can choose deform/cage/render options.

220

there is the convention in the api to use the term TESSFACE its a bit ugly but makes it very clear they are tessellation data.

255

This matches rna's Object.ray_cast. But I think this was a poor choise for the API because it assumes you want to cast short rays (edges), which isnt always true.

Think this should use the more common (point, direction, dist) args.

325

these can be NULL (committed in the branch)

Campbell Barton (campbellbarton) requested changes to this revision.Feb 4 2015, 6:44 PM
Campbell Barton (campbellbarton) edited edge metadata.

Before going into master, would be good to have a way to create a tree from scratch (passing in verts/triangles)

This revision now requires changes to proceed.Feb 4 2015, 6:44 PM
Lukas Toenne (lukastoenne) edited edge metadata.

Another alternative BVH Tree representation for totally custom user
geometry.

The new constructor method allows creating a BVHTree from a list of
vertices and triangles directly, without a separate mesh representation.

Campbell Barton (campbellbarton) commandeered this revision.EditedJul 29 2015, 2:20 PM

Committed rB18af73e461f9a943ae606fcc1401297f4afad20f

With following changes

  • Only have a single BVHTree type, and use different Initializer functions. BVHTree.FromObject, BVHTree.FromBMesh, BVHTree.FromPolygons (python data).
    • Arguments to creation functions are keyword-only. (no positional arguments).
  • Never store references to data passed in, only initialize from it, so manipulating the object or BMesh wont cause strange behavior with the BVHTree.
  • Making a BVHTree from Python data data can create faces with any number of sides. (uses NGon tessellation code internally, but indices & normals reference original ngon).
  • Use a generic way to map ngons to tessellation triangles.
  • Cache normals for re-use too. (initialize from ngons, derived mesh or bmesh faces).
  • Add BVHTree.overlap(other_tree) method, which does tri-tri intersection tests (added isect_tri_tri_epsilon_v3 to math library).

One thing missing from this patch is the ability to have BVH-tree created from Verts/Edges, however this could be added still if we want.