I feel Populate Geometry is too slow comparing to its simple functionality.
For example, 50000 points takes 14mins on my machine. Populate 2D was even slower.
Why is this? Is it computing Voronoi diagram or something?
Is there a way to speed this up?
2 Likes
Populate geometry is not so simple because it looks at distance between points. There are some discussion on that on old Grasshopper forum
https://www.grasshopper3d.com/m/discussion?id=2985220%3ATopic%3A929095
You could go a lot faster with mesh and populating without looking at distance.
Here a script for mesh.
100 000 points in 1 s
I think I publiate it on a dendro topics.
fast mesh populate LEGACY.gh (32.6 KB)
/// <summary>
/// Fast populate on mesh using triangle populate, but gives more density on edges
///Laurent Delrieu 18/8/2019
/// </summary>
/// <param name="mesh"></param>
/// <param name="nPoints">number of point wanted</param>
/// <param name="seed">seed parameter for the random generator</param>
/// <returns>List of points</returns>
List<Point3d> MeshPopulate(Mesh mesh, int nPoints, int seed)
{
Mesh m = mesh.DuplicateMesh();
m.Faces.ConvertQuadsToTriangles();
Random rnd = new Random(seed);
// List<double> surfaceFaces = new List<double>();
List<double> sumSurfaceFaces = new List<double>();
List<Point3d> points = new List<Point3d>();
double totalArea = 0.0;
for (int i = 0; i < m.Faces.Count; i++)
{
double area = MeshFaceArea(i, m);
totalArea += area;
sumSurfaceFaces.Add(totalArea);
}
for (int i = 0; i < m.Faces.Count; i++)
{
double pointsOnAllFacesBefore = 0.0;
if (i > 0)
{
pointsOnAllFacesBefore = (double) nPoints * sumSurfaceFaces[i - 1] / totalArea;
}
double pointsOnAllFaces = (double) nPoints * sumSurfaceFaces[i] / totalArea;
int nPointOnFace = (int) Math.Max((int) pointsOnAllFaces - (int) pointsOnAllFacesBefore, 0);
points.AddRange(PointsOnMeshFace(i, m, nPointOnFace, rnd));
}
return points;
}
/// <summary>
/// Populate a TRIANGULAR FACE
/// </summary>
/// <param name="meshfaceindex"></param>
/// <param name="m"></param>
/// <param name="n"></param>
/// <param name="rnd"></param>
/// <returns></returns>
List<Point3d> PointsOnMeshFace(int meshfaceindex, Mesh m, int n, Random rnd)
{
List<Point3d> points = new List<Point3d>();
//get points into a nice, concise format
Point3d[] pts = new Point3d[4];
pts[0] = m.Vertices[m.Faces[meshfaceindex].A];
pts[1] = m.Vertices[m.Faces[meshfaceindex].B];
pts[2] = m.Vertices[m.Faces[meshfaceindex].C];
Vector3d v1 = m.Vertices[m.Faces[meshfaceindex].C] - m.Vertices[m.Faces[meshfaceindex].A];
Vector3d v2 = m.Vertices[m.Faces[meshfaceindex].B] - m.Vertices[m.Faces[meshfaceindex].A];
for (int i = 0; i < n; i++)
{
double b1 = rnd.NextDouble();
double b2 = rnd.NextDouble();
if ((b2 + b1) > 1.0)
{
b2 = 1.0 - b2;
b1 = 1.0 - b1;
}
points.Add((Point3d) m.Vertices[m.Faces[meshfaceindex].A] + v1 * b1 + v2 * b2);
}
return points;
}
//Algorithm
//http://james-ramsden.com/area-of-a-mesh-face-in-c-in-grasshopper/
double MeshFaceArea(int meshfaceindex, Mesh m)
{
//get points into a nice, concise format
Point3d[] pts = new Point3d[4];
pts[0] = m.Vertices[m.Faces[meshfaceindex].A];
pts[1] = m.Vertices[m.Faces[meshfaceindex].B];
pts[2] = m.Vertices[m.Faces[meshfaceindex].C];
if(m.Faces[meshfaceindex].IsQuad) pts[3] = m.Vertices[m.Faces[meshfaceindex].D];
//calculate areas of triangles
double a = pts[0].DistanceTo(pts[1]);
double b = pts[1].DistanceTo(pts[2]);
double c = pts[2].DistanceTo(pts[0]);
double p = 0.5 * (a + b + c);
//Added 18/08/2019 Math.Max to suppress less than 0 value and NaN on 0 area mesh
double area1 = Math.Sqrt(Math.Max(p * (p - a) * (p - b) * (p - c), 0.0));
//if quad, calc area of second triangle
double area2 = 0;
if(m.Faces[meshfaceindex].IsQuad)
{
a = pts[0].DistanceTo(pts[2]);
b = pts[2].DistanceTo(pts[3]);
c = pts[3].DistanceTo(pts[0]);
p = 0.5 * (a + b + c);
//Added 18/08/2019 Math.Max to suppress less than 0 value and NaN on 0 area mesh
area2 = Math.Sqrt(Math.Max(p * (p - a) * (p - b) * (p - c), 0.0));
}
return area1 + area2;
}
4 Likes
Thanks Laurent! This is helpful! Maybe I’ll use a simple orthogonal grid instead 
Populate Geometry is an O(n2) algorithm where it looks for a good position which isn’t too close to any existing point. And many points are tried for at most 1000 times. 50000*50000/2*1000/2= is a huge number.
1 Like
@mikity_kogekoge you can always aim high and implement this one if you need uniform feature - http://graphics.cs.umass.edu/pubs/sa_2010.pdf
If you do so make sure to share it with us 
Hello, I’m trying to write a nearly O(n) algorithm for this.
The idea is a sort of Astronomical simulation…(so, it’s not exactly the same to the Poisson sampling)
Obviously there are nxn pairs to evaluate, but only pairs that are close to each other need to be evaluated, which can suppress the computations lower than n2.
The prototype attached has two issues so far. (some points pop out, points march along a curve slightly inset from the boundary curve.)
But the performance is already good.
pts |Astronomical Simulation |Polulate Geometry
5000pt |21s |11s
50000pt |4.1m | 14.4m
As can be seen from the attached image below, the distribution of the points is more uniform.
But I assume, the random-ness in the Poisson sampling is something intended.
It would be great if someone give me some feedback before further proceeding.
Thanks!
(the rhino file attached below is very big, as it contains 50000points in the document)
sampling.3dm (18.6 MB)
sampling.gh (10.0 KB)
(left, astronomical simulation, right, Populate Geoemtry)
Okay, worked it out. Removed some issues and brought in parallel computing.
The result is, 2.3mins for 50000 points. (Core i7, 1.8Ghz)
sampling.gh (14.6 KB)
2 Likes
There is still place for improvement
Resulting in this
Unfortunately, I can’t disclose internals for it 
But it does pretty much the same 
3 Likes
18seconds! nice!
Umm 
It’s actually 0,18 s => ~180 ms and it does more than just generaing those. I would have to dive with profiler in it to get pregeneration time value only
180ms!
I’m curious what’s the order of your algorithm? since there is a chance you are using 100x faster machine/language…(my script is written in Python, yours may be in C++)
This measured time suggests that my script is nearly O(n). (it should fall somewhere between O(n) and O(n2))
I rewrote your code in C# and it was like 20x faster. I’d recommend to try avoiding dict as they are quite slow.
Tried many of those… I’m using here a bit of Poisson with own multithreaded twist 
Nope my is C# - I’m not aware of Py overhead but it may also lay in structures @gankeyu points exactly that some of those are causing unnecessary and big overheads Rule of thumb wherever you can use a finite array of elements you’ll be surprised how it can speed up things - dynamic allocation of memory just have it’s time cost 
Not true at least in Python, especially if you do a lot of searching, dictionaries are far faster and superior in comparison to lists or tuples, especially if you add new values on the fly. Lookups in lists are O(n) and in dictionaries O(1) on average. Sets can even be faster, but you can’t easily associate data to other data. Dictionaries and sets are hash tables which are fast but memory hungry
True, and I’d even add one-dimensional, but…
… as I understand it, it’s not the dynamic allocation that’s the problem in this case. Dynamic allocation refers to storing data in heap memory (dynamic memory), as opposed to on the stack. Btw, in C# nearly everything is heap allocated.
The copying is the issue here. Finite arrays stay at a fixed memory address and a fixed amount of space has been pre-allocated for the data type to be stored. Other data structure, like lists, vectors, and so fourth that you can on the fly add to, allocate only so much memory when they are instantiated. While adding elements, once the memory has been filled, the entire data structure needs to get copied to another memory location, where more space is available, and this copying takes a lot of time and happens over and over the more items you add.
2 Likes
Perfectly explained. My explanation just wasn’t precise enough 
1 Like
What is the GUI from that you’re showing above in your preview?
This is my scattering plugin Rhino Nature
Oh, now I see where the highly optimised algorithms come into play! Looks promising!!
1 Like
dict is faster if you are doing an arbitrary-key lookup. But the OP was utilizing dict as a way to store sequential data. He used 0, 1, 2… as keys, under which situation list is almost a better alternative.
Btw, in C# nearly everything is heap allocated.
Yes. The issue here is in OP’s code, tons of list are created dynamically, which are big performance overheads.
OP’s code is a mess! I took a quick peek, but quickly gave up. I mean no offense @mikity_kogekoge, but you should take a look at PEP8.