Jump to content

Packing circles of different radius


AntoineSfx

Recommended Posts

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.

 

Link to comment
Share on other sites

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 by StepbyStepVFX
Link to comment
Share on other sites

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 by StepbyStepVFX
Link to comment
Share on other sites

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 by neblina
  • Like 3
Link to comment
Share on other sites

  • 9 months later...
  • 1 month later...

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...