I need to recreate a similar behaviour than what the Pop3d (Populate 3d) component does in Grasshopper, but in RhinoPython for a project.
I’m basically looking for a way to populate a box with random, three-dimensional points.
Now, I have no need for perfectly distributed, random sampling, but the formation of too many distinct point clusters should be prevented.
I’ve implemented Poisson Disc Sampling/blue noise sampling before, but in two dimensions? Does anybody know if it scales well into 3D?
Another idea was to subdivide the box into a three-dimensional grid of sub-regions, corresponding to the total number of sample points. Each 3D cell would contain a single point that could be jittered for randomness. I guess a neat by-product here would be the tree-like data structure that would make nearest neighbour searches fast and easy.
What do you think? Have you come a cross something more straightforward?
Any suggestion?
are you talking about 1000, or 1000000 million points.
will you run the code once for a single project your do you want to implement a library ?
a simple and fast way for a small amount of points:
generate a new random point.
generate new points and test each of them against all existing points, if distance / distribution is not well, delete it.
Another simple and easy to implement way:
generate more random points then you need, delete points in the most dense area until you have the desired amount of points.
if you work with lists, work from last item to index 0 - this is less struggle when deleting items.
@AndersDeleuran
if the box dimension e.g. is 100x200x300 a random 0…1 for x,y,z will not give a homogenous distribution, because the density in x direction will be factor 3 more then in z.
the simple solution is to distribute in 300x300x300, and only use points inside the desired box.
I’d say from a couple of hundred to a maximum of maybe 15,000 points.
Once at the beginning to establish a certain situation, but it may get re-run a handful of times to reshuffle, if the initial state doesn’t lead to satisfying results down the line.
Yes, but that will get pretty expensive, especially as the point population grows, especially without binary search tree implementation.
Sounds complex, since you first would have to establish existing clusters of nearest neighbours?
Thanks for your reply!
This I already have. Currently random points are spawned in x-, y-, and z-domains of the regional box, not the normalized intervals. Thanks.
generate n random points, where n is some small number
for each of these check their closest neighbour in the existing population
choose the one with the biggest distance and add it to the population
repeat
If you maintain an RTree and insert each point as you add it, I think the closest point check should be reasonably fast.
Alternatively you could generate one point at a time, and only add it if it is further than some distance from its nearest neighbour.
Indeed, I’m aware. I was just pointing out the Box.PointAt method, since it had not been mentioned. Which (depending on the requirements) can produce a fairly nice distribution on long/narrow cuboids, even if they aren’t homogenous:
If you keep a set of all the point coordinates, rounded to the nearest (min_distance_wanted, min_distance_wanted, min_distance_wanted) then you can very quickly check whether there is another one in the neighbourhood… You might end up with some points close together on the bounds of neighbouring zones of acceptability but it should be quick to implement and run…
You could also have a 3D array of n dimensional vectors where you can then assign each index a given floating point value. For example and RGB value will be a 3D vector. Then you could have each vector influence or weigh Kneighbour searches, translations, etc. In short you can create a 3D scalar field to influence the overall random distribution of points. By the way, if you are familiar with C# Accord.NET has a very good KDTree implementation, for neighbour queries. Its extremely fast.
So I’d basically have a three-dimensional grid of points that then get moved by a random field of vectors? How is this more beneficial than simply generating the random points straight-away? It seems this would only pile one more layer of complexity on top of the initial issue, namely getting the right vector values so that excessive clustering is prevented.
If the points are already random, why would I need to influence them? It seems I’d first have to identify clusters, optimize the local vector field, and then move the points.
I’ve already implemented KDTree myself, both in Python and C++. I usually don’t mess with C#. Generally speaking, it seems that the RTree implementation in Rhino, is also favourable for nearest neighbour searches. RTree is faster, when it’s not constantly rebuilt. KDTree should be better in the other case.
Well, it can be a way to better distribute your points. Also if you make your NVectors structs they wont have much of a performance impact because they will be allocated in the stack.
