No announcement yet.

[Plugin] kd-tree Blueprint Function Library

  • Filter
  • Time
  • Show
Clear All
new posts

    [Plugin] kd-tree Blueprint Function Library


    I created a first UE4 plugin UE4-Kdtree.
    This plugin provides the user to build kd-tree and radius search from it.

    I developed this plugin because there was no Blueprint interface about kd-tree when I used UE4 at first time.
    I'm a newbie about UE4 plugin development, so the comments and requests are very welcomed on GitHub Issue page or this topic.

    Project Page:
    Installation & Tutorial:

    Screenshots of this plugin:


    Very cool, I can totally see the usefulness of this for e.g. spatial search queries. One thing you might consider is to add an async version of Collect from Kdtree (and maybe Build kdtree too) that would run the lookup on a background thread and callback with only the results on the game thread. I don't know if it's needed for typical use cases though, it would depend on typical query performance cost on game thread.

    Thanks for sharing!
    Plugins: GES - Node.js - TensorFlow - Client - ZipUtility - Leap Motion - Hydra - Myo


      Thanks for feedbacks.
      I think an async version is useful especially Build kdtree because kd-tree is costly in building phase.
      I'm now tackling to make it. But I need times because I'm newbie about developing UE4 plugin.



        I will release v1.1 which includes async version of existing Blueprint Functions.

        This feature enables us to build kd-tree or search from kd-tree asynchronous with game main thread.
        And also, I deleted the Actor specialized Blueprint functions which I thought redundant.

        Click image for larger version

Name:	kdtree_async.png
Views:	204
Size:	122.1 KB
ID:	1659439

        Hope you like it. Thanks.


          Hi ぬっち, I have been attempting to use this plugin (On 4.23) but have had very little success. I then created a very basic scenario to test it and found I did not get the results I had expected.

          For my setup, I used an array of 7 vectors to build the tree:

          Vectors were simple: (-3,0,0) (-2,0,0) (-1,0,0) (0,0,0) (1,0,0) (2,0,0) (3,0,0)

          I then ran a Collect from KDTree using 0,0,0 as a center with a radius of 1. I would have expected to see 0,0,0 in the result.. probably not (-1,0,0) or (1,0,0) because it would be right on the border. But what I got as a result was (-3,0,0):

          I don't understand this result at all. If I expand my radius to 1.1, I get (-3,0,0) (-2,0,0) and (-1,0,0). I am completely lost as to why these results are occurring and I'm assuming I'm doing this wrong - could you point me in the right direction please?

          Last edited by Chumble; 02-01-2020, 10:15 PM.


            Ok, I figured it out. It's weird.


            SO .. You need to use the "Indices" values from the Collect node as indices into the ORIGINAL array. I have no idea what the "Data" node is supposed to be for. The doc seems to indicate it should return all the values of the original array too but it doesn't. Anyway, looks like it's working now.


              Hi, Chumble .

              Thanks and sorry for late response.
              I think this issues relates to the problem described in .
              This issue is already fixed and you can try it from master branch.

              Anyway, thanks for your great feedback!


                Nice Work !