Page MenuHome

Shared code for BLI_kdtree (3D and 4D)
AbandonedPublic

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

Details

Summary

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.

Details:

  • 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

Repository
rB Blender
Branch
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.

source/blender/editors/mesh/editmesh_select_similar.c
150

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.

source/blender/editors/mesh/editmesh_select_similar.c
150

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.
source/blender/editors/mesh/editmesh_select_similar.c
150

Thanks for the info!
Found some more information here:

https://en.wikibooks.org/wiki/Cg_Programming/Applying_Matrix_Transformations

Simon G. (intrigus) added inline comments.
source/blender/blenlib/intern/kdtree_impl.h
42

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.
source/blender/blenlib/intern/kdtree_impl.h
42

Good catch, done.

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