Packing circles of different radius

[AntoineSfx]

Is there a way to generate (instead of physically simulate by growing their radius..) a set of circles of different radius, densely packed ?

I didn't find a relationship between the centers of the circles in an ideally packed set of circles and Delaunay / Voronoi.  It's certainly a good start to use the Voronoi cells but it still requires some tweaking afterwards.  A quick approximation would work too, because I want to use this to copy objects onto another object, but I don't want too much interpenetration between the copies.

Maybe something like generating a bit more than expected, then removing the offending circles until no intersection is found.

 

[StepbyStepVFX]

6 hours ago, AntoineSfx said:

Is there a way to generate (instead of physically simulate by growing their radius..) a set of circles of different radius, densely packed ?

I didn't find a relationship between the centers of the circles in an ideally packed set of circles and Delaunay / Voronoi.  It's certainly a good start to use the Voronoi cells but it still requires some tweaking afterwards.  A quick approximation would work too, because I want to use this to copy objects onto another object, but I don't want too much interpenetration between the copies.

Maybe something like generating a bit more than expected, then removing the offending circles until no intersection is found.

 

Interesting challenge again :-)

Maybe use a point wrangle, and use nearpoints to return, for each point, the closest point surrounding it. Then store an attribute with half of the distance between the 2 points. Call it firstRadius for this example.

Then in a second pass (another point wrangle) we can see if there is room to increase the firstRadius of each point, depending on the firstRadius of surrounding points. Store a list/array of, say, the 10 closest points of each points. And for each points of this list compare the distance between your current point (ptnum) and the point of the list you are iterating in, and the sum of their firstRadius attributes. Take the point for which this difference is minimal, and increase the firstRadius accordingly.

Then instance a sphere or a circle with the radius stored in FirstRadius.

Not sure if my explanations are clear... I haven’t tested, but I am curious to see if this works. Maybe tonight :-)

Edited June 15, 2018 by StepbyStepVFX

[Noobini]

I did this with crappy old Max (MCG)....suuuuuuuurely can be done in Houdini......Houdini should eat this for breakfast...

 

[StepbyStepVFX]

I tried an algorithm that plays with the radius of circles given some fixed points, but it is not optimally packed. Moving the points on top of that would bring better results.... I share the file although that's not quite a good solution. To get a better solution I think it would require an algo that would be using an iterative process with both the radius and positions.

packedCircles.hip

Edited June 15, 2018 by StepbyStepVFX

[jonah@jonahtobias.com]

Here's another approach.  imperfect, but quick, works on any surface, and is only a few nodes.

circle packing.hip

[neblina]

Assuming you would want the circles not to intersect, we can solve this in a VOP network with only a few nodes. 

First we make sure the geometry we want the circles copied to has normals (if we want this to work with any input). We scatter points, and append them to a point VOP.

Inside the VOP (which loops over the points), we want to evaluate the closest point and the point itself, subtract their positions to measure that distance and divide it in half, since we are looking for the largest radius each circle copied to those points could have. 

pcopen (original P to P, OpInput1 to file) > 2x pcimportbyidx (handle to handle, first has index 1, second has index 0) > subtract > length > multconst (0.5) > bind export (pscale)

Also, make sure to adjust the search radius on the pcopen accordingly. A large enough number will suffice.

After that we only have to copy circles to those points. I can provide a file later. All of this could also be solved with wrangles, obviously. I might give that a try too.

Hope it helps, cheers!

 

edit: well, the same principle in vex is actually simpler than I thought. Put this in a wrangle after scatter and copy the circles to points.

int pcloud = pcopen(0, "P", @P, 10, 2);
vector found = pcimportbyidxv(pcloud, "P", 1);
@pscale = length(found - @P)*.5;

 

Edited June 25, 2018 by neblina

[lobao]

Very Cool.

[Drughi]

you can pack everything: 

 

[AntoineSfx]

Excellent finding. I kinda knew the new uvlayout from H17 acquired super powers, because they mentioned it in the Launch presentation video... but there are only so many hours in a day.