search

PointCloudLibrary / pcl

Point Cloud Library (PCL)
https://pointclouds.org/
Other
10k stars 4.62k forks source link

[FLANN] "Discussion around FLANN maintenance, possibility to use nanoflann" #4699

Open WildRackoon opened 3 years ago

WildRackoon commented 3 years ago

Is your feature request related to a problem? Please describe.

FLANN library is not maintained anymore, it hardly had any commit since April 2019, as mandatory dependency for PCL It just seems a bit odd.

People have brought this issue in the past at least once: https://github.com/PointCloudLibrary/pcl/pull/84

Describe alternatives you've considered

No one around here is not unfamiliar with the direct fork https://github.com/jlblancoc/nanoflann, that offers better performance and flexibility.

I am curious whether people have ever considered this ? would we face any problems ?

A complete port is no small feat, but I would be happy to help.

mvieth commented 3 years ago

Sounds interesting. Some first questions that come to my mind:

  1. What classes in PCL would have to be modified? Definitely flann_search.h[pp] in the search module, anything else?
  2. Should FLANN be simply replaced, or should it be possible to use either FLANN or nanoflann?
  3. Is nanoflann available as a package everywhere where FLANN is available?
  4. A PCL-specific running time comparison would be interesting
  5. License issues?
WildRackoon commented 3 years ago
  1. What classes in PCL would have to be modified? Definitely flann_search.h[pp] in the search module, anything else?

Yes mostly search related ones, but there is quite some stuff to change. Here is a full grep of "FLANN" in the codebase: https://pastebin.com/pxad2ZsB

  1. Should FLANN be simply replaced, or should it be possible to use either FLANN or nanoflann?

It the performance are better and there are no major implementation issues, we should replace it altogether, it's getting old. If built from source for optimisations, you currently need to fix its compilation scripts for the latest version to work.

  1. Is nanoflann available as a package everywhere where FLANN is available?

Only has a 'source package' for now : https://launchpad.net/ubuntu/+source/nanoflann Not very familiar with Deb/Ubuntu package admission process, but it should not be that hard to get it done ? Gentoo already has one: https://packages.gentoo.org/packages/sci-libs/nanoflann

Since PCL uses CMake, I strongly suggest letting developer choose wether to use 'ExternalProject' feature and download/build it on the fly: https://cmake.org/cmake/help/latest/module/ExternalProject.html

  1. A PCL-specific running time comparison would be interesting

Agree, This is mandatory

  1. License issues?

Same BSD as PCL : https://github.com/jlblancoc/nanoflann/blob/master/COPYING

tkircher commented 3 years ago

As noted in the thread you opened over at the flann project, I'm taking over as maintainer. It's definitely possible or even likely that nanoflann has better single-thread CPU performance, but most of us don't want to use a kNN algorithm that isn't GPU-accelerated.

BaltashovIlia commented 3 years ago

Hi,

I have compared the performance of different KNN libraries using modified nanoflann random benchmark tool. The test was to find 7 NN for 100k points in another cloud of the same size.

Performance rating from best to worst:

  1. flann – cuda
  2. libnabo – opencl
  3. libnabo – cpu
  4. nanoflann – cpu
  5. flann – cpu
  6. fastann – cpu
  7. libkdtree - cpu

A few comments:

So I think the best option would be to create libnabo-cpu and flann-cuda implementation of KdTree.

WildRackoon commented 3 years ago

I've been diving in those codebases a bit, indeed @tkircher concern over CPU vs GPU is a real issue depending on the application. We need to find a good way to dissociate those two use cases.

yasamoka commented 2 years ago

5299

jujimeizuo commented 1 year ago

Hi,

I have compared the performance of different KNN libraries using modified nanoflann random benchmark tool. The test was to find 7 NN for 100k points in another cloud of the same size.

Performance rating from best to worst:

  1. flann – cuda
  2. libnabo – opencl
  3. libnabo – cpu
  4. nanoflann – cpu
  5. flann – cpu
  6. fastann – cpu
  7. libkdtree - cpu

A few comments:

  • flann-cuda is a bit harder to get to work. @tkircher, actually I used your fork of flann but with some of changes (most from https://github.com/yuyi1005/flann). Thank you.
  • libnabo-opencl also requires a little work to compile it.
  • flann-cuda is faster than CPU algorithms only if you are finding neighbors for all query points in one call, and not one by one.

So I think the best option would be to create libnabo-cpu and flann-cuda implementation of KdTree.

Hello! Have you saved the code for the benchmark and can you share it with me？ Because I want to compare the performance of libnabo and kdtree of pcl.

Thank you!

arjunskumar commented 10 months ago

@BaltashovIlia where i can access the flann-cuda code?