Why Populate Geometry so slow?

I’m by no means an expert on all of this, but what is always a “problem” with dynamic object creation, is the reallocation of memory (copying of memory), if your dynamic data structure changes in size, since this is probably the slowest memory operation that can be done.
Potentially, using a quadree spacial division could even be faster, especially since points are only inserted and not moving iteratively (which would mean that the quadtree would need to be rebuilt at each iteration).
Other than that your stuff looks amazing and your times are mind-blowing!! :slight_smile:
Maybe, I’ve missed this, but you use multi-threading right?

ummm, maybe I’m too thinking in Python way, you have lists and dictionary. It’s a world people casually create and dispose objects dynamically.

Only a big bottleneck I see in this algorithm is, when points move out from a cell and enter to another cell, it is removed from the original list and added to a new list (let’s stop talking about dictionary inquiry cost! For me it’s fast enough). This happens everywhere actually. For instance, by ensuring a point array of 20 items for every cell, you can avoid dynamic allocation of memory. (or maybe this is what David initially suggested…)

Yes, its using parallel-foreach

No, forget about this post. I don’t know how to remove a point from an array.

I wrote a wrapper class for a C++ library written by David Coeurjolly which refactors a low disc blue noise point sampling algorithm. The algorithm is based of this paper. The gist is that the blue noise component that I wrote can create an even distribution of 5,000,000 points in 2.1 seconds. The source code for this can be found here.


For those that want to skip the source code, you can test this component out by copying these two files (see zip file) into your components library.
Blue Noise Point Generator.zip (131.8 KB)

10 Likes

Seems like I happened to open a Pandora’s box… :crazy_face:

Some questions generate more answers than other. Populating is a useful tool for many things.
I played with some of the generator that are on this page
here some test, populating a square with 1000 points


Using Proximity 2D with Group 1, 2, 3 and 4


difference between sampling.gh (11.6 KB)

8 Likes

Interesting paper never saw that earlier - spectrum is distorted but its indeed super fast.

All this talk about algorithms, is super inspiring for a python noob, thanks.
Regards.

1 Like

Yeah, for (in?) the first place, I didn’t even know this is a common topic in Graphics. :heart_eyes: Thank you!

My final code (25% faster than the last one) attached, if anybody is interested. Copyright waived.
sampling_C#.gh (9.2 KB)

1 Like

Yup, adaptive uniform sampling is one of the base ingredients for Monte Carlo approaches used widely by rendering engines.

No matter what would be considered about performance I must admit that your approach is one of most uniform I saw so far :wink:

1 Like