# Make nanoflann a third party used for point locators

**URL:** <https://discourse.vtk.org/t/make-nanoflann-a-third-party-used-for-point-locators/4300>\
**Category:** Development\
**Tags:** proposal\
**Created:** [September 25, 2020, 4:23pm UTC](https://discourse.vtk.org/t/make-nanoflann-a-third-party-used-for-point-locators/4300 "2020-09-25T16:23:15Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![Yohann\_Bearzi](https://discourse.vtk.org/user_avatar/discourse.vtk.org/yohann_bearzi/32/671_2.png) [@Yohann\_Bearzi](https://discourse.vtk.org/u/Yohann_Bearzi)\
**Post date:** [September 25, 2020, 4:23pm UTC](https://discourse.vtk.org/t/make-nanoflann-a-third-party-used-for-point-locators/4300/1 "2020-09-25T16:23:15Z")

</div>

[`nanoflann`](https://github.com/jlblancoc/nanoflann), forked from [`flann`](https://github.com/mariusmuja/flann) (Fast Library for Approximate Nearest Neighbors), is a very powerful and fast point search library that I’ve been using for years on point clouds. There are a lot of different indexing schemes (see page 9 of the [manual](https://www.cs.ubc.ca/research/flann/uploads/FLANN/flann_manual-1.8.4.pdf)).

The main difference between `flann` and `nanoflann` is that `flann` has run-time overheads that are squeezed out by `nanoflann`, which is header only.

I think it would be worth depending on this library for point locators, replacing `vtkKdTreePointLocator` guts by `nanoflann`, and potentially implement new locators with other indexing strategies directly available through `nanoflann`. The metric used to build the index is also customizable through a functor, which could be a cool feature to add to VTK’s locators.

Any filter that does a lot of point searches would benefit from this change. For instance, the new filter `vtkOverlappingCellsDetector` would benefit from it.

`nanoflann` works with CUDA. is thread safe, and I’ve seen an `mpi` directory in the `flann` git repository, without looking too much into it.

Any opinions?

---

<div class="post-metadata">

**Author:** ![utkarshayachit](https://discourse.vtk.org/user_avatar/discourse.vtk.org/utkarshayachit/32/379_2.png) [@utkarshayachit](https://discourse.vtk.org/u/utkarshayachit)\
**Post date:** [September 25, 2020, 4:47pm UTC](https://discourse.vtk.org/t/make-nanoflann-a-third-party-used-for-point-locators/4300/2 "2020-09-25T16:47:03Z")

</div>

How hard is to put together a quick performance comparison for build/lookup using `vtkKdTreePointLocator` and nanoflann? If there’s a dramatic performance improvement, it’d be a very easy case to make.

---

<div class="post-metadata">

**Author:** ![ben.boeckel](https://discourse.vtk.org/letter_avatar_proxy/v4/letter/b/ea5d25/32.png) [@ben.boeckel](https://discourse.vtk.org/u/ben.boeckel)\
**Post date:** [September 25, 2020, 5:10pm UTC](https://discourse.vtk.org/t/make-nanoflann-a-third-party-used-for-point-locators/4300/3 "2020-09-25T17:10:16Z")

</div>

How are we going to manage training? Models?

---

<div class="post-metadata">

**Author:** ![Yohann\_Bearzi](https://discourse.vtk.org/user_avatar/discourse.vtk.org/yohann_bearzi/32/671_2.png) [@Yohann\_Bearzi](https://discourse.vtk.org/u/Yohann_Bearzi)\
**Post date:** [September 25, 2020, 5:14pm UTC](https://discourse.vtk.org/t/make-nanoflann-a-third-party-used-for-point-locators/4300/4 "2020-09-25T17:14:46Z")

</div>

I’m not sure to follow what you mean by that. Ideally the user wouldn’t be aware of the internal mechanics of it. All you want to do is to feed points, and query neighborhoods.

---

<div class="post-metadata">

**Author:** ![ben.boeckel](https://discourse.vtk.org/letter_avatar_proxy/v4/letter/b/ea5d25/32.png) [@ben.boeckel](https://discourse.vtk.org/u/ben.boeckel)\
**Post date:** [September 25, 2020, 5:40pm UTC](https://discourse.vtk.org/t/make-nanoflann-a-third-party-used-for-point-locators/4300/5 "2020-09-25T17:40:28Z")

</div>

Yes, but there’s some pre-trained network behind the scenes right? How will we manage it? The training materials should also be in the source repo too.

---

<div class="post-metadata">

**Author:** ![Yohann\_Bearzi](https://discourse.vtk.org/user_avatar/discourse.vtk.org/yohann_bearzi/32/671_2.png) [@Yohann\_Bearzi](https://discourse.vtk.org/u/Yohann_Bearzi)\
**Post date:** [September 25, 2020, 5:41pm UTC](https://discourse.vtk.org/t/make-nanoflann-a-third-party-used-for-point-locators/4300/6 "2020-09-25T17:41:30Z")

</div>

I guess it wouldn’t be too hard to do. Just have to build a big point cloud and compare performances.

Some people have already looked into this kind of [benchmarks](http://e6.ijs.si/medusa/wiki/images/7/7d/Report.pdf) (not with VTK’s version, which does not seem to be commonly used).

As far as I have looked, regarding kdtrees, when used on 2D / 3D points and when the tree is built staticly, you won’t find better than `nanoflann`. There seems to be a debate on what is better between `flann` / `nanoflann`, or other libraries for more exotic search spaces.

---

<div class="post-metadata">

**Author:** ![Yohann\_Bearzi](https://discourse.vtk.org/user_avatar/discourse.vtk.org/yohann_bearzi/32/671_2.png) [@Yohann\_Bearzi](https://discourse.vtk.org/u/Yohann_Bearzi)\
**Post date:** [September 25, 2020, 5:44pm UTC](https://discourse.vtk.org/t/make-nanoflann-a-third-party-used-for-point-locators/4300/7 "2020-09-25T17:44:38Z")

</div>

I don’t think there are pre-trained networks behind the scenes. A kd-tree does not need training to learn how to build itself. The only limitation of this kind of structure is that if you have a lot of points that are aligned in the same plane in 3D / line in 2D, you lose a lot of efficiency because the space gets weirdly split. The user should know what kind of structure it wants depending on its input data.

---

<div class="post-metadata">

**Author:** ![Yohann\_Bearzi](https://discourse.vtk.org/user_avatar/discourse.vtk.org/yohann_bearzi/32/671_2.png) [@Yohann\_Bearzi](https://discourse.vtk.org/u/Yohann_Bearzi)\
**Post date:** [September 25, 2020, 5:47pm UTC](https://discourse.vtk.org/t/make-nanoflann-a-third-party-used-for-point-locators/4300/8 "2020-09-25T17:47:30Z")

</div>

Oh did you mix flann (Fast Library for Approximate Nearest Neighbors) with flann ( Functional Link Artificial Neural Network)?

---

<div class="post-metadata">

**Author:** ![ben.boeckel](https://discourse.vtk.org/letter_avatar_proxy/v4/letter/b/ea5d25/32.png) [@ben.boeckel](https://discourse.vtk.org/u/ben.boeckel)\
**Post date:** [September 25, 2020, 6:10pm UTC](https://discourse.vtk.org/t/make-nanoflann-a-third-party-used-for-point-locators/4300/9 "2020-09-25T18:10:44Z")

</div>

Ah, yes I did. Normal third party import details apply. Mangling, import, etc. 🙂

---

<div class="post-metadata">

**Author:** ![Yohann\_Bearzi](https://discourse.vtk.org/user_avatar/discourse.vtk.org/yohann_bearzi/32/671_2.png) [@Yohann\_Bearzi](https://discourse.vtk.org/u/Yohann_Bearzi)\
**Post date:** [October 1, 2020, 8:19pm UTC](https://discourse.vtk.org/t/make-nanoflann-a-third-party-used-for-point-locators/4300/10 "2020-10-01T20:19:04Z")

</div>

I did a rapid test. To do so, I tweaked a little this [example](https://github.com/jlblancoc/nanoflann/blob/master/examples/pointcloud_adaptor_example.cpp) from `nanoflann`.

I tried on both `nanoflann` and `VTK` (Release build) to build a kdtree with one million random points, and then did one million random queries on the 10 nearest neighbors. I used `rand()` for the random number generator, with same 3D extent.

Results are:

- `VTK` - kdtree build time is 134ms, search is 7,319ms
- `nanoflann` - kdtree build time is 278ms, search is 554ms

---

<div class="post-metadata">

**Author:** ![Yohann\_Bearzi](https://discourse.vtk.org/user_avatar/discourse.vtk.org/yohann_bearzi/32/671_2.png) [@Yohann\_Bearzi](https://discourse.vtk.org/u/Yohann_Bearzi)\
**Post date:** [October 1, 2020, 8:22pm UTC](https://discourse.vtk.org/t/make-nanoflann-a-third-party-used-for-point-locators/4300/11 "2020-10-01T20:22:59Z")

</div>

On a debug build, the search with VTK takes 54 seconds. I don’t know if we can keep the same performance of `nanoflann` with a VTK debug build if it becomes a third party. Can we @ben.boeckel?

---

<div class="post-metadata">

**Author:** ![ben.boeckel](https://discourse.vtk.org/letter_avatar_proxy/v4/letter/b/ea5d25/32.png) [@ben.boeckel](https://discourse.vtk.org/u/ben.boeckel)\
**Post date:** [October 26, 2020, 10:26am UTC](https://discourse.vtk.org/t/make-nanoflann-a-third-party-used-for-point-locators/4300/12 "2020-10-26T10:26:08Z")

</div>

I don’t like the idea of compiling some bits in release and others in debug if one selects a `Debug` build mode. One is (generally) already not in the mood to figure out hidden CMake flags to get missing debug info when one is looking for it.

---

<div class="post-metadata">

**Author:** ![Joachim\_P](https://discourse.vtk.org/user_avatar/discourse.vtk.org/joachim_p/32/3272_2.png) [@Joachim\_P](https://discourse.vtk.org/u/Joachim_P)\
**Post date:** [November 21, 2020, 11:35am UTC](https://discourse.vtk.org/t/make-nanoflann-a-third-party-used-for-point-locators/4300/13 "2020-11-21T11:35:10Z")

</div>

It would be great to have such a VTK class that would rely on `nanoflann` for efficient point locator requests but before having it integrated in VTK I would publish it as a remote module so interested people could experiment with it first (and it could easily replace the `vtkKdTreePointLocator` through the factory mechanism).

---

<div class="post-metadata">

**Author:** ![Yohann\_Bearzi](https://discourse.vtk.org/user_avatar/discourse.vtk.org/yohann_bearzi/32/671_2.png) [@Yohann\_Bearzi](https://discourse.vtk.org/u/Yohann_Bearzi)\
**Post date:** [March 1, 2022, 6:57pm UTC](https://discourse.vtk.org/t/make-nanoflann-a-third-party-used-for-point-locators/4300/14 "2022-03-01T18:57:47Z")

</div>

I just ran some more tests.

I have a VTK branch named `nano-flann-test` with a test called `TestKdTreePointLocator` performing some benchmark on the point locator of VTK (my fork is [https://kitware.gitlab.com/yohann.bearzi/vtk.git](https://kitware.gitlab.com/yohann.bearzi/vtk.git)). I have another branch on my fork of nanoflann benchmarking the same test called `test-kdtree-vtk`. My fork is in [https://github.com/yohannbearzi/nanoflann](https://github.com/yohannbearzi/nanoflann). Running `examples/pointcloud_adaptor_example` benchmarks the same test as in my VTK branch.

Results look as follows on my machine:

```auto
nanoflann:
Build time 0.299125 seconds for 1000000 points
Search time 0.638600 seconds for 1000000 queries and 10 neighbors

VTK:

vtkKdTreePointLocator
Build time 0.142078 seconds for 1000000 points
Search time 7.368636 seconds for 1000000 queries and 10 neighbors

vtkStaticPointLocator:
Build time 0.093148 seconds for 1000000 points
Search time 4.563173 seconds for 1000000 queries and 10 neighbors

```

When multithreading on 16 threads on my machine, comparing nanoflann and `vtkStaticPointLocator`:

```auto
nanoflann:
Build time 0.294138 seconds for 1000000 points
Search time 0.087202 seconds for 1000000 queries and 10 neighbors

VTK:
Build time 0.034972 seconds for 1000000 points
Search time 0.967511 seconds for 1000000 queries and 10 neighbors

```

So… It turns out that VTK locators are outperformed by nanoflann by a lot (over 10 times) on querying points, but not on actually building the locator (twice slower than `vtkKdTreePointLocator`). So it seems that on instances where there are not a lot of points to fetch, `vtkStaticPointLocator` is to be preferred. “Not a lot” in the test I did is about a as many queries as 10% of the number of points in the locator. For more queries, nanoflann is much much better. I would like to emphasize that this is true on evenly distributed points in a data set. `vtkStaticPointLocator` store points in bins that are formed by a grid discretization of the space. If there is a large concentration of points in one bin, the point locator becomes very slow at fetching points in this bin.

So, I propose we should definitely change `vtkKdTreePointLocator` backend to use nanoflann (it also uses a kdtree in one of their implementation). This locator should be preferred in most instances. Light work can stick with `vtkStaticPointLocator`.

I’m reaching out to the community here. Do you know of a better implementation than nanoflann for point locators? Is there any known issues that could occur with nanoflann that I’m not foreseeing? Or is using nanoflann as a backend a good idea?

---

<div class="post-metadata">

**Author:** ![will.schroeder](https://discourse.vtk.org/user_avatar/discourse.vtk.org/will.schroeder/32/233_2.png) [@will.schroeder](https://discourse.vtk.org/u/will.schroeder)\
**Post date:** [March 1, 2022, 7:22pm UTC](https://discourse.vtk.org/t/make-nanoflann-a-third-party-used-for-point-locators/4300/15 "2022-03-01T19:22:32Z")

</div>

This is a great analysis, I’d definitely replace the implementation of vtkKdTreePointLocator with nanoflann unless there’s some weird build dependencies or licensing issues. I’m curious, did you do any memory usage comparisons? I’ve found myself lately processing 0.5 billion points, and memory can be a concern.

---

<div class="post-metadata">

**Author:** ![Yohann\_Bearzi](https://discourse.vtk.org/user_avatar/discourse.vtk.org/yohann_bearzi/32/671_2.png) [@Yohann\_Bearzi](https://discourse.vtk.org/u/Yohann_Bearzi)\
**Post date:** [March 1, 2022, 8:07pm UTC](https://discourse.vtk.org/t/make-nanoflann-a-third-party-used-for-point-locators/4300/16 "2022-03-01T20:07:11Z")

</div>

I don’t think there’s an easy way to know the memory consumption in the VTK’s locators. They don’t have `GetActualyMemorySize()`. In nanoflann, a locator of 1 million points (the one of my example) produces an excess of 4.3 MB. So roughly 4 bytes per points.

---

<div class="post-metadata">

**Author:** ![Yohann\_Bearzi](https://discourse.vtk.org/user_avatar/discourse.vtk.org/yohann_bearzi/32/671_2.png) [@Yohann\_Bearzi](https://discourse.vtk.org/u/Yohann_Bearzi)\
**Post date:** [March 1, 2022, 8:09pm UTC](https://discourse.vtk.org/t/make-nanoflann-a-third-party-used-for-point-locators/4300/17 "2022-03-01T20:09:55Z")

</div>

Using 10 million points, nanoflann generates an excess of 38 MB, so we’re in the same scale. 4 bytes per point.

---

<div class="post-metadata">

**Author:** ![will.schroeder](https://discourse.vtk.org/user_avatar/discourse.vtk.org/will.schroeder/32/233_2.png) [@will.schroeder](https://discourse.vtk.org/u/will.schroeder)\
**Post date:** [March 1, 2022, 8:11pm UTC](https://discourse.vtk.org/t/make-nanoflann-a-third-party-used-for-point-locators/4300/18 "2022-03-01T20:11:08Z")

</div>

That’s very impressive! although I don’t think you mean 4 MB per point 😉

---

<div class="post-metadata">

**Author:** ![StongeEtienne](https://discourse.vtk.org/user_avatar/discourse.vtk.org/stongeetienne/32/4857_2.png) [@StongeEtienne](https://discourse.vtk.org/u/StongeEtienne)\
**Post date:** [March 20, 2022, 6:07pm UTC](https://discourse.vtk.org/t/make-nanoflann-a-third-party-used-for-point-locators/4300/19 "2022-03-20T18:07:27Z")

</div>

Hi, Sorry to join in late in the discussion (new in this discourse),  
I’ve been using VTK for quite a long time and recently i’ve been using Nanoflann “heavily”.

Nanoflann should be quite easy to integrate since it’s a single “.hpp” file using common STD includes.

Also, for specific application (e.g. 2D / 3D points) the speed can be further improved,  
using some templated L2\_distance function (to remove the “for loop”).  
And could be further improved with continuous array, enabling SSE-AVX instructions.

This is what I did in my branch (however this project is more to generalize kdtree Lpq distances) :

> **[GitHub - StongeEtienne/lpqtree: Modified version of Nanoflann for Lpq...](https://github.com/StongeEtienne/lpqtree)**
>
> Modified version of Nanoflann for Lpq entry-wise matrix distance, Focussing on L21 (with 3D points) - GitHub - StongeEtienne/lpqtree: Modified version of Nanoflann for Lpq entry-wise matrix distanc...

I would be happy to help / discuss !

---

<div class="post-metadata">

**Author:** ![will.schroeder](https://discourse.vtk.org/user_avatar/discourse.vtk.org/will.schroeder/32/233_2.png) [@will.schroeder](https://discourse.vtk.org/u/will.schroeder)\
**Post date:** [May 9, 2023, 7:37pm UTC](https://discourse.vtk.org/t/make-nanoflann-a-third-party-used-for-point-locators/4300/20 "2023-05-09T19:37:12Z")

</div>

Yohann and others-

What is the status with nanoflan? There are some potential applications where the speed could be most beneficial. It sounds like it would be relatively straightforward to integrate.

[Next page](https://discourse.vtk.org/t/make-nanoflann-a-third-party-used-for-point-locators/4300.md?page=2)