Why Populate Geometry so slow?

Though I agree dynamic generation of cells is not the best idea, this animation explains well the algorithm.

2 Likes

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)

12 Likes

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

1 Like

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)

16 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)

2 Likes

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

Hi Andy,

Many thanks to you (And all on this thread) for the insight. I’m struggling to get the blue noise generator/wrapper to work; it throws up a .dll not found (but it’s right there, unlocked, next to the component in the components folder).

Any ideas? new version of Rhino maybe?

thanks

R

@mikity_kogekoge @gankeyu following your very valuable examples I managed to do populate a shape depending on the distance to the border. I use a sort of bitmap in order to calculate the radiuses. It is just dart throwing at the moment but it seems enough for me.
Here the shape and the bitmap (alpha = 0 outside the shape so it is transparent)


So I can do that

It is a copy of Nervous work,

The code allows also to do Image stippling in reasonable time (5 s )
Ratio between radius is 20 (for example radius for white is 20, radius for black is 1)


3 Likes

Nice to see this 2-years old thread is still active!

Great Stuff!! Could you share the code for Image stippling?

It will be in Nautilus plugin. Stay tunned!


5 Likes

really nice @laurent_delrieu, and related to the topic what is the logic behind populate with a pre-existing population list, please, could you upload a c# example I’d really appreciate it.
Eager for the release of your plugin, if you are looking for testers :raised_hand:t3:
Thank you!
T.

The logic is that all new points will not be near the pre existing points. it works as a sort of Islands

thank you @laurent_delrieu but I refer to the logic of the code to consider this analysis of proximity to create the new points.