Page MenuHome

Shared code for BLI_kdtree (3D and 4D)

Authored by Campbell Barton (campbellbarton) on Mar 18 2019, 1:32 AM.



This avoids copy-pasting the BLI_kdtree API for a 4D version (needed to fix T62595).

The way macros are used here isn't great, alternatives could be to duplicate the code, make the dimensions a property of the tree (at the cost of efficiency) or move it to C++ and use a C-API wrapper.

  • This includes a fix for T62595 (to show how it works).
  • BLI_kdtree is currently being used for 2D trees for select similar and edge-net-filling, so the ability to have use different dimensions isn't limited to this case.


  • If this is included BLI_kdtree_* should be renamed to BLI_kdtree_3d_* since it's strange to have both BLI_kdtree_new & BLI_kdtree_4d_new.
  • Could rename 3d/4d -> v3/v4 (named this way because BLI API's have 3d and 2d versions of functions).

Diff Detail

rB Blender
TEMP-FIX-T62595-v2 (branched from master)
Build Status
Buildable 3161
Build 3161: arc lint + arc unit

Event Timeline

Harbormaster completed remote builds in B3151: Diff 14231.
Harbormaster completed remote builds in B3152: Diff 14232.
Campbell Barton (campbellbarton) edited the summary of this revision. (Show Details)
  • Correct dimension use in header
Harbormaster completed remote builds in B3153: Diff 14233.
  • Relocate math functions
Campbell Barton (campbellbarton) edited the summary of this revision. (Show Details)

Since we don't need to inline the functions, it is probably easier write the kdtree in C++. That would also make it easier to use from other C++ code.

But since the C API will probably stay the same, this can be decided later.


Why mul_transposed_mat3_m4_v3(ob->imat, ...). Looks like a double inversion to me (transpose + using imat). I think the result should be the same when you use the non transposed version with ob->obmat.


This is needed to get the normal in worldspace. mul_mat3_m4_v3(obmat) fails when the matrix has a non-uniform scale.

see: calc_point_from_barycentric_extrusion, snapMesh which does this too.

Harbormaster completed remote builds in B3158: Diff 14243.

Thanks for the info!
Found some more information here:

Simon G. (intrigus) added inline comments.

Shouldn't this be 0-KD_DIMS-1 ?
I.e.: /* range is only (0-KD_DIMS-1) */

Campbell Barton (campbellbarton) marked an inline comment as done.
  • Correct comment
Harbormaster completed remote builds in B3160: Diff 14245.

Good catch, done.

  • Use a prefix that matches the final API names more closely
Harbormaster completed remote builds in B3161: Diff 14246.