[Plugin] kd-tree Blueprint Function Library

Hi,

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: GitHub - nutti/UE4-Kdtree: UE4 Plugin: k-d tree
Installation & Tutorial: UE4-Kdtree/README.md at master · nutti/UE4-Kdtree · GitHub
Download: Releases · nutti/UE4-Kdtree · GitHub

Screenshots of this plugin:

Thanks.

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!

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.

Hi,

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.

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: https://i.imgur.com/MW6mHJP.png

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): https://i.imgur.com/8ugnNVj.png

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?

Thanks

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 CollectFromKdtree Returns Incorrect Position Data · Issue #5 · nutti/UE4-Kdtree · GitHub .
This issue is already fixed and you can try it from master branch.

Anyway, thanks for your great feedback!

Nice Work !

I am recently converting a lot of my blueprint work to c++ and I would love to use your plugin there as well. Would you have any tips on how this could be implemented from a c++ perspective? I know it wasn’t designed for that but it seems to me you should still be able to access the same functionality.

@Chumble

Sorry for late response.

Kd-tree plugin exposes C++ API as well as Blueprint API.
You can see the API definition from below files.

Sync - https://github.com/nutti/UE4-Kdtree/…reeBPLibrary.h
Async - https://github.com/nutti/UE4-Kdtree/…reeBPLibrary.h

If you want to use these function from C++, you can call them directly.

Nice plugin ! How would I go about doing a nearest neighbor search with this ? Could the plugin do it, return the closest point to the input center ? Or should I use the k-d tree to narrow down the search and then do a regular nearest neighbor search ?

Why Have I problem with the async version? It doesn’t work! I also tried to create the tree first with SaveGame but it doesn’t work anyway

Currently, there is only Radius search.

Yes, this is a current use case.
But I think returning the closest point to the input center is a good feature.
I will add this feature in future.

I need more information about this.
Could you tell me your workflow?


Here’s my workflow!
If I turn off the playmode, turn it back on and just press 6, it should give me the closest points, right? It doesn’t currently work that way.

Unreal doesn’t keep the data if you exit play mode, you can just build the kdtree on begin play, it’s really fast, then reuse it each time you want to collect or rebuild it if you change the vertices array.

you can also get an editor tick every x seconds if you want to do some in editor updating (useful for debugging) variables e.t.c don’t just exist at play time. so based on use case and dev cycle you can setup editor only senarios. but this is a c++ required setup so depends on scope.