Pointcloud nearest Point


#1

Hi,
I need to find the nearest point in a pointcloud. I’m using GetClosestPoint of pointcloud, but I do this many times, and I need to do it faster. I have tried to use GetClosestPoint with maximum distance parameter, with the idea that less points will be tested, but the function takes the same time to obtain the nearest point, no matters the maximum distance I use.

I noticed too, as I told in another post, that if I create a mesh from my pointcloud, and I use the closest point function of the Mesh, it is faster than the pointcloud one. But I need to do it faster in a pointcloud. I think obtaining a closest point in a pointcloud should be easier than in a mesh, so why is it slower?

Thanks in advance.


#2

you might want to look into R Tree data structure.

@RhinoCommon
Rhino.Geometry.RTree


(Dale Fugier) #3

Hi Jona,

There certainly isn’t anything special about ON_PointCloud::GetClosestPoint, and I am sure there are many ways we can tune up its performance.

Knowing more about what you are trying to might help us better understand what problem you are trying to solve. Any details you can provide might be helpful.

Thanks,

– Dale


#4

Thanks, for your answers. My problem is that I’m trying to obtain the nearest point of a pointcloud from a external point. I have to do this, too many times, and the process is too slow. If I create a mesh from my pointcloud, the process is notably faster. I can’t create meshes in my program because I have to work with pointclouds. So my question is, if a pointcloud is a simplier structure than a mesh, why takes more time finding nearest point in a pointcloud?


#5

Do you have a surface or do you draw a point and then want to find the closest point in the pointcloud? xD

  • If so. you loop through your points in the pointcloud and do closest point with them all.

  • check the distance between the 2 points

  • keep the closest point?

  • you add them to arrays and then sort them?


(Menno Deij - van Rijswijk) #6

You can take a look at this paper how to use RTree data structures to do spatial queries.
http://delab.csd.auth.gr/papers/SIGMOD00cmtv.pdf

I have used this method successfully in speeding up the MeshMeshClosestPoint of Rhino by about 3 orders of magnitude.

Unfortunately, the RTRee object in RhinoCommon will not let you navigate the tree (using tree branches, nodes, leafs), which is required by the algorithms in the paper. So you will have to either code in C++ (OpenNURBS), use another RTRee implementation or code your own implementation.


(Dale Fugier) #7

ON_PointCloud::GetClosestPoint just walk through the entire array of points looking for the closest one - nothing fancy.

I’ve added this to our list of things to tune up for a future Rhino release.

http://mcneel.myjetbrains.com/youtrack/issue/RH-29116


(Willem Derks) #8

Hi Menno,

For my understanding, can an RTree be considered to be a Octree with non uniform nodes?

Thanks
-Willem


(Menno Deij - van Rijswijk) #9

Yes, Octrees have exactly eight nodes, whereas Rtrees have different amount of nodes based on the information they represent.


(Will Pearson) #10

All experiments have run on a workstation of 64 Mbytes RAM and several Gbytes of secondary storage. The page size was set to 1 Kbyte thus resulting to R*-tree node capacity M = 21 (minimum occupancy was set to m = M/3 = 7, a reasonable choice according to [1]).

How things have changed in the last 14 years :).

If you’re willing to get your hands dirty, you might try looking at the Node3List, Node3Tree and Node3Proximity classes in the Grasshopper SDK (@DavidRutten, do these use an Octree behind the scenes?). As always, you have to weigh up the overhead of building the data structure with the time saved by using it for closest point queries.


(David Rutten) #11

Yes they do. I’ve also just now rewritten those classes in C# for GH2, and I switched to a more adaptive subdivision scheme (octree when the node is nearly cubical, X, Y, or Z aligned QuadTree when the node is near square but very flat, or X, Y, Z linear if the node has one long dimension and two short ones). The idea is to get nodes as cubical as possible, while at the same time keeping them as small as possible. The node regions are minimum bounding boxes for their (recursive) content, which should make it more likely that they are rejected earlier in a search process, thus reducing the number of recursions needed to get the final answer. Code isn’t quite done yet (haven’t implemented Box and Sphere search yet) and there’s a number of optimizations I still need to make after I profile it some more, but I’m happy to share the code.


(Menno Deij - van Rijswijk) #12

You’re right, there is some overhead in the closest point query, but I found that I could perform spatial queries that were completely intractable with standard rhino sdk functionality. For example querying the closest two points on two 60k vertex meshes takes about 15s, whereas that is undoable with mesh mesh closest point.


(David Rutten) #13

Just tested two 60k pointclouds for closest point pair with my code, about 2.5 seconds.


(Menno Deij - van Rijswijk) #14

The performance, I found, is very dependent on the spatial structure. I reasoned (and may be wrong here) that spherical meshes/pointclouds would be most difficult to query. The 15s on two 60k vertex meshes was on two meshes obtained by MeshSphere using 200, 300 points in each direction, positioned on the diagonal of a cube (as in attached file).

Indeed, similar meshes of other structures are much faster to query.

Two MeshSpheres.3dm (2.5 MB)


(David Rutten) #15

little under 3 seconds. This includes building the spatial tree of course.

Also did a test on two 1M pointclouds, takes nearly half a minute. Of course only a single pointcloud is converted to a tree, and every point in the other one is is matched to the first one. If I were to put both clouds into spatial trees I could probably speed up closest pair searches significantly, but that would require a lot of new code.


(Steve Baer) #16

Is there a reason this shouldn’t just be in RhinoCommon? Seems generally useful for everyone.


(David Rutten) #17

Sure, once it’s done, profiled and vetted we can move a lot of GH geometry core code into RhinoCommon.


(Steve Baer) #18

I would say as long as the public facing SDK portion is stable we can move code over. This will let more people scrutinize the code and improve it. We can also start setting up tests against these classes.functions since @Alain has gotten a nunit testing framework in place that should work well with our build system.


(Menno Deij - van Rijswijk) #19

FWIW, I sent my implementation of the closest point query algorithm to @dalelear for incorporation into OpenNURBS


(Alain Cormier) #20

I’m happy to write test code for this once it’s in RhinoCommon. It would be a good way for me to learn something interesting.