Radius search in point cloud

[lazysquid]

Hello, I'm here for some helps. Currently I'm implementing radius search(Specifically, I want to find a set of indices of registered point around the query point within the given radius.) for a given point using GVDB. I'm implementing this because I expected that GVDB has this kind of function but I couldn't find any. I've read quite some examples(particle surface, point cloud, point fusion) and guide documents but couldn't find the functionality that I want.

Am I missing somethings or GVDB does not have the kNN search function?

Thank you.

[alvingitlord]

Check this kernel function https://github.com/NVIDIA/gvdb-voxels/blob/6f438f808ba9334acf2ee1122ca224c0988e7d25/source/gFluidSurface/fluid_system_cuda.cu#L247

[lazysquid]

@alvingitlord Thank you for your answer. However, from my understanding, the kernel function doesn't fully utilize GVDB API. The example could insert the cloud into GVDB. Then for input queries we can find neighbor voxels of each quries and can do some NN searches items within the voxels.

Is there any specific reasons for implementation without GVDB features?

[ramakarl]

@lazysquid Its not entirely clear what you want. Is the "query point" a) another one of the registered points, is it b) an arbitrary point in space, or is it c) a voxel in gvdb?

If a), this doesnt require gvdb at all, the link alvin gave in fluids v3 is correct. Since it is a point-to-point query no voxels are involved.

If b), then the code for a) should be used as a starting point. Uniforn subdiv is fastest.

If c), the the code for a) is also starting point. The query func would need to be placed into a gvdb voxel kernel.

The insert func found in Fluids v3 does most of the work, inserting points into a uniform grid of bins. This handles millions of pnts fast. If you had billions or trillions of points then you might want to use gvdb as the point acceleration structure (not implemented now).

The query func from a) answers: "after points have been dropped into a uniform grid (not gdvb), what are all the bins which might need to be checked if i perform a query from a given bin up to a fixed radius. "

You asked for all point in a fixed radius and later mention kNN. These are two diff things. Fixed-radius-NN is all points from a given point inside a fixed distance. kNN is the first k closest points to a given point regardless of their distance.

Hope this helps.

[lazysquid]

@ramakarl Thank you for your comments.

Yes. I'm looking for Fixed-radius-NN not kNN.

b) is the answer that I'm looking for. More clearly, 1) I have millions of registered particles, the radius of each particles are zero. And the number of registered particles will be increased as the time goes by. (You can think point cloud stream from RGBD camera) 2) For arbitrary point x and search radius r, I want to find the indices of registered point around x within radius r.

What I wanted to do is similar to this but in my case, the input is arbitrary position x. http://on-demand.gputechconf.com/gtc/2014/presentations/S4117-fast-fixed-radius-nearest-neighbor-gpu.pdf

Since the document of gvdb point said, gvdb insertion is utilizing the method above, so I was hoping I might use that internal feature without implementing it or implement the feature with relatively small amount of time and effort by using gvdb.

Maybe I should implement uniform grid my self.

Anyway, thanks for your comment!