GH: Point3dList.ClosestIndex() Extremely slow - why?

Grasshopper Developer
1

For some reason the Point3dList suddenly seems very slow.

I’m prototyping two versions of a component, one working directly on a mesh and it’s Vertices list, and the other working on a pointlist from the input (same points from the same mesh). I mainly use the function mesh.ClosestPoint(pt) and Point3dList.ClosestIndex(pt) respectively, but the Point3dList method is extremely slow compared to the mesh ditto.

Profiling info shows that the mesh doesn’t even show up on the radar while the Point3dList spends 500+ms doing exactly the same job. (Important: I’m not reloading the pointlist each time, I hold a cached version which reloads only if the lits changes, which it never does after first read)

Fig 1. The upper component works on a pointlist and the lower directly on the mesh.

bild
bild.png770×693 124 KB

The code that differs is minimal:

  private bool SomeMethod(Mesh mesh, Point3d from_pt, ...)
  {
    hit_point = mesh.ClosestPoint(from_pt);    
    // ...
    var pt = mesh.ClosestPoint(some_pt);

End the Point3dList version:

  private bool SomeMethod(ref Point3dList pointcloud, Point3d from_pt... )
  {
    var ix = pointcloud.ClosestIndex(from_pt);
    hit_point = pointcloud[ix];
    // ...
    ix = pointcloud.ClosestIndex(some_pt);
    var pt = pointcloud[ix];

The number of points is about 224.000, but why is Point3dList.ClosestIndex() so much slower than the mesh ditto?

// Rolf

2

I would try with PointCloud Class instead of Point3dList…
Radovan

3

Thank you for the hint. However, I tried PointCloud but still not satisfactory. I think I will have to try RTree instead.

bild
bild.png844×379 60.1 KB

// Rolf

4

The mesh class has build in search trees for fast lookup, whereas the point list is just a dumb list which iterates over all the points and finds the closest one.

500ms is sort of expected for a brute force search on a 200k set. It’s an O(n) algorithm. The search trees used in meshes and other advanced geometry types will probably be closer to O(log(n)).

5

OK. I’ll try RTree in a minute.

// Rolf

6

I tried the RTree approach as described in the RTree example code, but same thing there, way too slow (about 750 ms, which was even worse than the other lists).

I would have uploaded the component with code, but the internalized data choked the .gh file so it became unusable, even if disabling the Solver before opening it (I uploaded a copy for @DavidRutten to check if there’s something wrong with ~200.000+ internalized points or if such big numbers simply exceeds some limitation in GH_Documents. One can’t even rightclick on the canvas without the file freezing for several minutes. It’s zombified).

Anyway, it seems I will have to try some other RTree functions, like Point3dClosestPoints or Point3dKNeighbors. Hopefully they come down to the neighbourhood of the Mesh.ClosestPoint() function.

The reason why I want to test for ClosestPoints directly on point lists coming in through the Inputs is for optimizations where I reduce the number of poins with different inclusion tests before feeding them into the component which are internally utilizing ClosestPoint functionality.

I could go for reducing the size of the mesh instead (which I actually currently do), but reducing and rebuilding a mesh part costs more processing power than to simply reduce the number of mesh vertices with different PointInclusion tests.

// Rolf

7

You need to sort a Point3dList (or List, or array of Point3d). Once the list is sorted, then you can perform as many binary searches as you want and they will be very fast. If you need to know the point’s original index, the you could create a List<Tuple<Point3d,int>> with every int as the index back in the original list. The generic List<> class in C# has functions for sorting and searching.

8

Thank you for this hint!

I also just noticed, after reconnecting the (RTree) component directly to the Mesh (skipping the internalization of the vertices) that the performance improved to ~170 ms. That’s better, although still ~10 times slower than Mesh.ClosestPoint().

But now I will try the sorted tuple list. Thanks again for the hint!

// Rolf

The component, but whithout the 224.000 internalized points…
ClosestPointRTRee.gh (3.3 MB)