Page MenuHome

Python wrapper for BLI_kdtree

Authored by Campbell Barton (campbellbarton) on Dec 23 2013, 10:34 PM.


Dan Eicher (dna)

Python class wrapper around KDTree to provide a generic python kdtree implementation.

Diff Detail

Event Timeline

Think this could be made to use mathutils, since its nicer to get back vectors rather then tuples of numbers and the vector parsing mathutils has is more convenient too. (can replace py_seq_to_vec3)


for generic names like this - prefer kdtree_py_api.c

29 ↗(On Diff #416)

Could just use Pythons allocation functions since the only use is alloc&free immediately.

83 ↗(On Diff #416)

Looks like this isnt needed?

103 ↗(On Diff #416)

*picky* bpy_BLI_kdtree_ is an odd prefix, This isnt really related to the bpy api.

164 ↗(On Diff #416)

The normal is only used for particles, right now and has a strange hack in squared_distance, See: /* can someone explain why this is done?*/ Think this should be resolved before exposing to Python.

180 ↗(On Diff #416)

Py_BuildValue is fairly slow, since "if[fff]" is called multiple times in this function, I think this could be made into a function and done manually with PyTuple_New(), PyTuple_SET_ITEM, etc.

292 ↗(On Diff #416)

*picky* prefer one line per method as is done everywhere else in blender.

Campbell Barton (campbellbarton) requested changes to this revision.Dec 24 2013, 8:14 AM
177 ↗(On Diff #416)

as with the bvh review, best return same number of args on success/fail. (None, None, None) in this case.

Dan Eicher (dna) updated this revision to Unknown Object (????).Dec 24 2013, 9:55 PM

Fixed all issues other than:

  • py_seq_to_vec3 lets you pass in any sequence object including a mathutils.Vector. Would be kind of inconvenient to have to create a Vector just pass it into the functions and then immediately discard.
  • MEM_freeN is needed for BLI_kdtree_range_search.

On the kdtree normals issue -- One would think it would act like shooting a ray from the point in the normal direction but not so much, AFAICT it uses the normal to only return points in +180° of the normal direction. I think the hack is to penalize results in the negative direction or something like that (perhaps an optimization?). Seems to work OK though I'd imagine it would fail on the 'teacup in a stadium' case.

Dan Eicher (dna) updated this revision to Unknown Object (????).Dec 24 2013, 10:26 PM

Fixed leaking PyObjects from PyTuple_Pack() not stealing references.

Note: mathutils_array_parse works for arbitrary sequence types too, its just optimized for vectors as well. (avoids float ->pyfloat->float for each axis). Or worse, calling the read-callback 3 times.


just pass nearest->co


Not sure theres a good reason to allow passing a None arg, the caller can just ommit the arg in this case.


again, seems odd to support.


The python API could ensure this fairly easily, (just store bool flag)... OR the C api could ensure and assert if it fails.


again... wouldnt bother with this.

Please leave the normal thing out of the API, it penalizes points behind the normal with a quite arbitrary amount that's probably not even working so reliable for particles, best not to expose such hacks to Python.

I'll check into mathutils_array_parse and remove the normals bit.


For some odd reason just passing nearest->co was failing.

Tested with:

for v in bm.verts:
    i, d, co = tree.find_nearest( == co
Campbell Barton (campbellbarton) requested changes to this revision.Dec 30 2013, 1:50 AM
Dan Eicher (dna) updated this revision to Unknown Object (????).Dec 30 2013, 6:53 AM

Think that got all the issues, couldn't spare a whole lot of time on this so hopefully didn't miss anything.

Think this is close to bring finished,

Think its worth having correct balance use checked for in the API, PyKDTree can have an unsigned int count_balance, which is set when balance runs, if this doesn't match the count when find_* functions run an error can be raised.


prefer PyTuple_New(), SET_ITEM, means no need to decref after.


"iO&" -> "iO&:insert"

will give better exception messages, goes for other uses of PyArg_ParseTupleAndKeywords

Dan Eicher (dna) updated this revision to Unknown Object (????).Dec 31 2013, 4:46 AM

Fixed the PyTuple_New and args function name thing.

On the balance issue, added a flag that gets reset if any points are added after calling balance() so one can do:

for v in bm.verts:

Committing this patch with the following edits....


  • Moved to mathutils.kdtree
  • Made co argument the first argument for all KDTree.find* functions.
  • Re-ordered the return value so it it matches order passed (co, index, distance - not an arg so added last).
  • renamed KDTree.find_nearest -> find
  • renamed KDTree.find_nearest_n -> find_n
  • renamed KDTree.search_range -> find_range


  • Negative values weren't being checked for, would crash when creating a new KDTree.
  • Fixed freeing NULL pointer when range_search doesn't find any items.
  • Fixed for uninitialized memory use when running find() on an empty KDTree.


  • Integrated with sphinx documentation generation.
  • Added example for API docs.
  • Added unit tests (

Passing negative values crashes.