search

jlblancoc / nanoflann

nanoflann: a C++11 header-only library for Nearest Neighbor (NN) search with KD-trees
Other
2.26k stars 491 forks source link

Add support for ray search #19

Open herpec-j opened 9 years ago

herpec-j commented 9 years ago

Hi,

Would it be possible to add a method to get all indices of points that are traversed by a ray?

Something like:

size_t raySearch(const ElementType *ray_origin, const ElementType *ray_direction, const DistanceType ray_length, std::vector<IndexType> &indices) const;

Or do you have some tips about how to implement this kind of query? I think it would be very useful (e.g for raytracing, etc...).

Thanks!

patrikhuber commented 7 years ago

+1, this would be awesome. I'm a happy nanoflann user but for another task I'm currently looking for a library that can also do ray searches. @herpec-j did you make any progress on this by any chance?

Does anybody else have some implementation hints? Would it be hard with nanoflann?

Thanks!

patrikhuber commented 7 years ago

Hi! I'm picking this topic up again and would really be interested in a solution or at least some comments. @jlblancoc do you think you could help or comment?

Thanks, Patrik

yetigit commented 6 years ago

you can use radius search with the magnitude of your ray , and get the point that are on the ray after

jay3d commented 6 years ago

It would be great to have this functionality as it will aid in mouse view-port picking, any guidelines of how to implement it? Like intersection of the ray with the slices?

patrikhuber commented 5 years ago

Actually, @jay3d, wouldn't you need ray-triangle intersection to do view-port picking? I just revisited this issue and was thinking if I can make it work with @yetigit's suggestion of using radiusSearch(), but then I realised that that would only give me back the closest points, and not whether a ray intersected any triangles. Nanoflann actually doesn't have any support for triangles or meshes, so it is probably not the right tool for the job? Unless I am missing something now.

I could recommend that you try libigl's AABB tree. It is quite lightweight as well and it works for triangular meshes and is excellent for picking. I was hoping that nanoflann could do it, which would be an even more lightweight dependency, but I don't think it can do it after all and it probably wouldn't be too easy to add or not actually nanoflann's purpose to do ray-triangle intersection. I'd be happy to hear some comments in case I'm missing something.