Radius nearest neighbors

Hi, I'm trying to have something similar to ANN or FLANN (approximate nearest neighbors libraries for c++). And I was wondering if there is anything similar already out there for Unity.

What I was looking for is a radius filtering approach, given a Vector3 and a radius, what points (in the kdtree) are within the sphere described by those values?

I was thinking KDTree for efficiency, checking all points is quite slow, I have around 60000 points.

I found this kdtree class but it only gives a single Vector3. I guess it could be extended for this purpose but I don't see how..

Thanks!

 

It might seem counterintuitive, but taking advantage of Unity's physics might be a good choice. I know the physics engine does a fair bit of optimization/compartmentalization/etc along these lines. So, Physics.OverlapSphere might actually be really fast.

 

It's not - I've just recently had to optimize out a bunch of calls to it. They bubble up into Physics.Simulate() in the Profiler. It also uses the collision matrix regardless of whether you give it a mask or not and some parts of it are treated like a physics collision. This leads me to believe that the physic simulation is actually using the OverlapSphere method from the API. I haven't seen similar behavior in Raycast so I don't know why this is different.

That being said - if you're not doing it often and your scene isn't overly complex then it'll work fine. (We started to see performance dips at ~100 masked OverlapSphere calls per frame)

 

But that would mean I need to attach a collider to each point, right? Is there something like a Point collider? Or would I need sphere colliders for each point? As I said I have a lot of points could even have the order 100K.

Thanks for the tips!