Jump to content
AntoineSfx

Packing circles of different radius

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.

 

Share this post


Link to post
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

Share this post


Link to post
Share on other sites

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

 

Share this post


Link to post
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

Share this post


Link to post
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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×