Point related operations execution speed

thanks, @stevebaer

At this point, I don’t know if I can match the performance reported by the researchers of the papers I’ve been studying. They are generating stipple images in minutes rather than hours and getting great results (I am only iterating 5 times, which is nowhere near enough).

I am getting pretty good results from just doing the weighted point reduction method found at http://www.eng.uwaterloo.ca/~alopyrev/cs791/stippling_report.html

What I have discovered is that the populate geometry component (which I use to generate random points) in grasshopper already does a really good job of distributing points in an evenly spaced manner. Even spacing is what this capacity-constrained point distribution method is trying to achieve. I essentially start with evenly spaced sample points, so there is no need to complicate things by calculating the sites.

One thing I would like to point out is that populating a geometry with 1,000 samples takes 287 ms, 10,000 seems to take 27 s, but populating with 100,000 samples takes around 50 minutes. Why is it taking so long to populate? Is it because it has to reference previous points in order to populate evenly? Is there a way to populate without consideration for other points? Maybe populate with 1 point, but 100,000 seeds?

@stevebaer,

thank you for this example. I still need to understand the sampling part (random.sample). Your script is useful in my case since i am interested in multiple neighbours per point. Once question though: Is the method:

Rhino.Geometry.PointCloud.ClosestPoint

using the RTree internally ?

I´m asking since i made a small comparison script and scene attached below using RTree for finding a single closest point against Rhino.Geometry.PointCloud.ClosestPoint, which in addition seems to be threadsave, so i´ve also tested using multiple (8) treads. The tests where performed for 1000 test points on a pointcloud with 223905 points. These are the results:

SingleThreaded: 1000 TestPoints, Time: 0.86 sec
MultiThreaded: 1000 TestPoints, Time: 0.13 sec
RTree: 1000 TestPoints, Time: 0.82 sec

Script: PointCloudClosestPtTests.py (2.8 KB)
Scene: TestScene.rar (4.8 MB)

I guess once there are more points in the pointcloud, RTree performs faster, need to find out if it`s treadsave too :wink:

For doing knn search, this would be very helpful. I´m interested in a list of point indices per pointcloud point. Still need to find out how your script needs to be changed to get them instead of the points.

c.

1 Like

That is something @DavidRutten would have to help answer since I’m not all that familiar with the underlying algorithm used by the populate geometry component.

This just gets a fixed number of random items in the point cloud. I use that to fill in the initial list of points. I put 5 random points from the cloud into the list and then continue to update the list when I find points that that are closer than the “furthest” point in the list.

No, the point cloud is performing a linear brute force search. Every time you search for a closest point in the point cloud, every single point in the cloud is evaluated. The RTree is a data structure set up for searching. Typically search structures can find the answer in log(n) queries where unstructured data would always take n queries. This means that as n gets really large you will see enormous benefits to searching with data structures that have the data pre-sorted in some way for very fast lookup. There is a performance hit with the current RTree implementation since it has to continuously jump back and forth between C++ and .NET which is something I can tune up over time. That said, the performance hit for C++/.NET would be minimal when compared to searching massive data sets using a brute force technique.

Your python script timing is including the time it takes to create the create the RTree data structure which will skew your timing results.

Just save the args.Id too when you are saving the point locations.

@stevebaer,

thank you very much for the detailed explanations, this helps a lot. :beers: You are right about the RTree data structure creation time, i wanted to measure everything required to perform the same results.

For comparison i did another test which shows how fast RTree scales, using a pointcloud with 895583 points and 10000 random testpoints, these are the results:

SingleThreaded: 10000 TestPoints, Time: 72.45 sec (using ClosestPoint)
MultiThreaded: 10000 TestPoints, Time: 17.72 sec (using ClosestPoint)
RTree creation, Time: 2.96 sec
RTree: 10000 TestPoints, Time: 4.29 sec

Wow, this gets 16 times faster (compared to single core) and four times the speed of Rhino.Geometry.PointCloud.ClosestPoint with 8 cores and even if the RTree creation time would count it is twice as fast. I guess the larger the data gets, the larger the gap will scale. [quote=“stevebaer, post:23, topic:31002”]
Just save the args.Id too when you are saving the point locations.
[/quote]

Ok, will do it :wink:

c.

The Populate components do indeed slow down rather drastically as more points are requested. They all work in roughly the same way. The basic idea is to find a point on the shape which is furthest away from all points already part of the population. However I have no good way of picking the best point. So I randomly generate N points on the shape (where N grows as the square-root of the population size), measure the distance for each random point to the nearest existing point, then select the best one and move on to the next point.

So if you’re generating a population of 100k points, you’ll be performing about 22.5 million closest point searches on a cloud that contains on average 50k points. There are definitely things I can do to speed that up, but the approach taken just necessitates a lot of looping.

Note that it will be much faster to just generate random points in a rectangle or box, that’s an O(N) algorithm, I hope my implementation is O(N log N) because I do use an octree to speed up nearest neighbour search, but I suspect it’s somewhere in between O(N log N) and O(N²)

Ah, big-O notation… I love it :slight_smile:

Next week’s WIP will contain a small optimization for this that should help decrease the creation time

@stevebaer, thanks for that. I guess the tree is the least problem here. I am still trying to optimize your example script above since it takes more than one hour to find 5 neighbours of every pointcloudpoint with a cloud size of 800K points. The funny thing is that the time it takes is totally random even for a very small pointcloud. I guess this is caused by the different distances caused by random.sample.

c.

Hmm… I must be doing something wrong. Once the data structure is built you should be getting relatively quick results even with clouds that large.

Hi Steve, maybe i am doing it wrong :wink: i´ve tried with the script below, all with 5 neighbours and without saving them in a variable. For 10K pointclouds its fast, around 4-5 sec, for 100K it increases to 265 seconds. The test pointclouds are just spheres with random points, if that matters.

NeighboursTest.py (1.7 KB)

c.

@DavidRutten @stevebaer @clement

Hi all, I also have the experience that by increasing size of the pointcloud, it takes much more time.
I use the Tree method to find nearly overlaping points. I have two sets of points and I want to know the index (from one set) of the overlapping points.

RT = Tree()
RT.TPTS01 = rg.RTree()
RT.TPTS02 = rg.RTree()
sphererad = tol
outputList = []

for i,pt01 in enumerate(points[0]):
    RT.TPTS01.Insert(pt01, RT.TPTS01.Count)
    
for j,pt02 in enumerate(points[1]):
    RT.TPTS02.Insert(pt02, RT.TPTS02.Count)

overlap = RT.rt_overlap(RT.TPTS01,RT.TPTS02,tol)
if RT.RESULTOVERLAP01:
    outputList = RT.RESULTOVERLAP01

return outputList

But with few points its fast, but with million points it takes 10min. Is it possible to speed up the procedure by multithreading.
By: ghpythonlib.parallel.run (removeDuplicatesTreeMulti,list,True)
Unfortunately it doesn’t work. I don’t know how to adress a seperate searchcall back funktion for the parrallel run.
Do you guys have an idea how to speed up the overlapping search with the resulting index list?

Thanks

@ZweiP,

maybe one small optimisation could be to avoid adding the points one by one, so instead of this:

RT.TPTS01 = rg.RTree()
RT.TPTS02 = rg.RTree()

for i,pt01 in enumerate(points[0]):
    RT.TPTS01.Insert(pt01, RT.TPTS01.Count)
    
for j,pt02 in enumerate(points[1]):
    RT.TPTS02.Insert(pt02, RT.TPTS02.Count)

you could build the trees and add the points as pointcloud in one go:

RT.TPTS01 = rg.RTree.CreatePointCloudTree(rg.PointCloud(points[0]))
RT.TPTS02 = rg.RTree.CreatePointCloudTree(rg.PointCloud(points[1]))

@stevebaer mentioned above that there will be some slight optimisations to the tree creation.

My guess is that the example Steve posted above is slow because it uses the random.sample and because of the multiple required calls to

tree.Search(rg.Sphere(search_point, radius), search_callback, tag)

His script example above takes much longer to find a single neighbour but is 5 times faster finding 20 neighbours per test point. I guess that the real work has to be done somehow in the SearchCallback itself. Note that my example script above is only testing for one closest point in the Tree for each point in the pointcloud. So it does not do any re-indexing (sorting by distance) of the neighbours like Steve`s example does.

Overall it would be helpful if Rhino6 gets a simple RhinoCommon method to receive a list of neighbour indices per pointcloud point but for all points in a pointlcoud, preferable in a single line of code :wink:

c.

That is true. @clement, you can move the sample part outside of the loop since it only needs to be done once. We are just trying to get a random set of points for starting the search. That random set can be reused over and over again.

@stevebaer, i’ve tried that. It only changes from 65sec to 63sec with a 100K pointcloud and 10 neighbours for every pointcloud point. Using a pointcloud with 200K points, i still get a time increase to 570sec. So the random.sample is not the most important factor here i guess. It is the multiple calls of the tree.Search and the content in the search_callback.

One question: I see you are increasing the hit count value in the search_callback like so:

args.Tag[3] = call_count + 1

Is it technically possible to change the search_point (the center of the searchsphere) in the search_callback too ? I mean the whole cloud gets passed to the the search_callback, so if every cloud point is searched, it might prevent calling tree.Search so many times.

c.

@clement
After posting I already changed it to create rg.RTree.CreatePointCloudTree. :slight_smile:
But creating is not such a problem to find the overlapping indexes takes much more time. :frowning:
Is there a faster way to find overlapping indexes of two big pointclouds? Or at least a way to run it parallel (ghpythonlib.parallel.run).
rs.CullDuplicatePoints takes too long

Thanks.

@ZweiP, i guess we need to find out first why it runs so slow with single pointcloud before doing tests with 2 pointclouds. Doing any multiprocessed tests failed over here using System.Threading.Tasks, i guess the search_callback function is not threadsave.

@stevebaer, i´ve found some cases where the hitcount goes up the roof. The larger the pointcloud gets, the larger the peaks in hitcount gets eg. with a 10K cloud, i get occassionally this:

...
003 search called 4058 times for mesh with 10000 points
080 search called 8155 times for mesh with 10000 points
238 search called 1505 times for mesh with 10000 points
276 search called 6892 times for mesh with 10000 points
>>> 63 times hitcount above 1000

the first number is the index of a pointcloud point. Overall with a 10K pointcloud, i get 63 cases where the hitcount is above 1000. With a 100K pointcloud, the number of hitcounts above 1000 increases with the size of the pointcloud:

...
98273 search called 70320 times for mesh with 100000 points
98519 search called 5810 times for mesh with 100000 points
98544 search called 30178 times for mesh with 100000 points
>>> 750 times hitcount above 1000

Note that the peak values increased with the pointclount too.

c.

Those kind of numbers suggests there is a subtle bug in either my sample or in the underlying data structure. I’ll look into this some more.