vtkPointPicker very slow

Hello !
I have a vtkPoints and I am trying to peak points from my pointcloud with cursor… so for now I am using vtkPointPicker… but with a large number of points, it is clearly too slow… The idea will be to use a vtkOctreePointLocator (or vtkKdTreePointLocator). Unfortunately we can’t give a locator to a vtkPointPicker (whereas we can with a vtkCellPicker :cry:).
Is there a class to do picking with a vtkOctreePointLocator or do I create this class myself?

Thanks for your help

Some comments:

  • Check out the code in vtkPointCloudRepresentation which uses software picking (vtkPointPicker) or hardware picking (vtkHardwareSelector). This representation class can be paired with vtkPointCloudWidget.

  • Yes, point picker needs a refresh, it should probably use a locator to accelerate picking (beyond a certain #points threshold).

  • The point locators (vtkPointLocator and vtkStaticPointLocator) have IntersectWithLine() methods that you could probably use.

  • I rarely use vtkOctreePointLocator or vtkKdTreePointLocator unless there is a lot of dynamic range in point density. They are slow to build, slow to delete, and not threaded. For most applications the vtkStaticPointLocator can be an order of magnitude faster (if built threaded with TBB etc.)

1 Like

vtkPointLocator does not have an IntersectWithLine() method, octree and kdtree neither… unfortunately.

In my case there is a lot of dynamic range in point density, that is why octree or kdtree seems better but if I understood correctly I have to implement my own IntersectWithLine() method with those classes ?

if you want to use these classes (octree, kdtree) then yes you’ll have to write your own method. Why wouldn’t you use hardware selection? It’s going to be faster than anything you do in software…

I forgot this part, I don’t want a structure just to pick points but also to calculate the nearest neighbors of a point from coordinates and I can’t do that with hardware selection (but yes hardware selection seems to be an amazing tool)

Have you ever experienced the speed difference between vtkStaticPointLocator and vtkOctreePointLocator and/or vtkKdTreePointLocator ?

I suggest you experiment with this test: ./bin/vtkCommonDataModelCxxTests TimePointLocators
Admittedly, this is a lousy test of points with high density variation. If you feel up to contributing a new test, it would be nice to have a test that creates a point cloud with high density variation. I can imagine doing this with some sort of analytic function.

Running unchanged the output is (in my 20-core system, built release):
Timing for 100000 points, 10000 queries
Build and delete tree
Uniform: 0.0233409
Static: 0.00440001
Octree: 0.015322
KD Tree: 0.010422
Closest point queries
Uniform: 0.0119779
Static: 0.0113399
Octree: 0.0296822
KD Tree: 0.0164299
Closest N points queries
Uniform: 0.051096
Static: 0.0308821
Octree: 0.116065
KD Tree: 0.0845001
Closest points within radius queries
Uniform: 0.00304818
Static: 0.00191879
Octree: 0.010278
KD Tree: 0.0102541
Total time
Uniform: 0.089463
Static: 0.0485408
Octree: 0.171347
KD Tree: 0.121606

If you edit the test and change the number of points to something larger:
Timing for 10000000 points, 1000000 queries
Build and delete tree
Uniform: 3.8035
Static: 0.177384
Octree: 2.35506
KD Tree: 4.64083
Closest point queries
Uniform: 3.62174
Static: 2.36916
Octree: 4.82664
KD Tree: 3.62797
Closest N points queries
Uniform: 12.0197
Static: 7.05107
Octree: 12.9393
KD Tree: 11.8128
Closest points within radius queries
Uniform: 5.51731
Static: 3.51151
Octree: 3.96433
KD Tree: 4.40001
Total time
Uniform: 24.9623
Static: 13.1091
Octree: 24.0853
KD Tree: 24.4816

2 Likes

That’s very interesting, vtkStaticPointLocator seems to be very efficient. MaybeI I should start by testing this class eventually. Depending on the results I get I would do other tests, Thanks a lot for your help

Hello Julien! I am in the process of developing the following Picker

https://gitlab.kitware.com/vtk/vtk/-/merge_requests/8740

Let me know if that helps you, in any way.