Circle stacking on a 3D spherical shape in Grasshopper/Kangaroo

Hi everyone,

For a project of mine I just started, I'm wondering about the chance of success I will have with achieving the intended result and I hope you guys can maybe shed some light on this issue.

For my project I want to make a sphere or spherical-like shape and pack it with circles of varying sizes. The circles all have to touch each other and thus on a point where three circles 'sort of' meet, there can only be three circles. This is shown in the second picture I have attached, a 2D circle packing made by Daniel Piker. So basically what I want to achieve is having the second picture projected on a 3d surface, that I can also edit. Also I would like to be able to change the size and amount of the circles that populate the surface. This means that I would be able to say 'there should be 30 circles with a radius of 2, 40 circles with a radius of 3 and 50 circles with a radius of 4, put them on this particular shape'.

As I've just started the project I haven't done so much research yet. What I have found is for example this Kangaroo definition of circle packing in 2D: http://www.grasshopper3d.com/group/kangaroo/forum/topics/circle-pac...

It is very beautiful and does exactly what I want to achieve, except that it is in two dimensions. I also have to say that I feel pretty confident working with both Grasshopper and Rhino, but not really with Kangaroo. I have used it a few times but not extensively.

So what I'm wondering is, how could I best approach this project? I looked into the concept of 'circle packing' and I noticed that it can be approached very mathematically. As I am an architecture student I don't know much about the math behind the geometry (although I do think it is very interesting) and thus I'm wondering if I will be able to achieve what I want to achieve. Also, do you think I could best approach the project in Kangaroo and do you think it is realistic for me to think I could finish the project? I'm just trying to see if I'm not going to try to tackle a problem that is very difficult to solve even for skilled mathematicans or something. Sorry for the long and perhaps vague read, but I would be very happy with any sort of input you might have on my problem!

Thanks in advance!

Attachments:

circle packing sphere.gif, 5 KB
circlepack daniel piker.png, 200 KB

Replies to This Discussion

Permalink Reply by Daniel Piker on May 3, 2014 at 5:16pm

Hi Joris,

Most of what you describe sounds possible, and I have made available a few tools and definitions for circle packing that could be of help here.

This property of three circles being tangent around each gap is called a compact circle packing, and this isn't always possible to achieve exactly on every surface, but luckily for a sphere it is.

You can break the problem into 2 parts:

-The combinatorics, or connectivity, ie how many circles there are, and which is tangent to which. This is often represented as a mesh, where each vertex is the centre of a circle, and the edges link the centres of the circles which are tangent to each other.

-The sizes and centre positions. If you treat the combinatorics as fixed, you can then concentrate on optimizing the radii and locations of the circles to get them as close to tangent as possible.

I have done some work on solving these 2 parts simultaneously (see video here), and shared some scripts for this here.

Alternatively we can deal with them separately. For the combinatorics you could use something regular, based on subdivision (for a sphere you might want to start with an icosahedron). Alternatively you could use the remeshing tool I recently shared here. This can cover any surface with a mesh of almost equal edge lengths.

For the second part there is a force in Kangaroo which can optimize any triangulated mesh so that there is a packing of spheres centred on its vertices (and if the mesh is smooth, this sphere packing also leads to a circle packing). The file cp_mesh1 in the circle packing directory of the new collection of Kangaroo example files I recently posted shows this.

As for limiting to a small number of specified radii, this is still tricky, and impossible without compromising some of the other conditions. If you allow some variable gaps between the circles, you can replace each one with the closest from your set of radii. If you do not choose your radii in advance, but generate a packing with continuously varying radii then cluster them, it can give a better fit.

Alternatively you can give up the requirement that the packing to be compact and have good tangency, but some gaps with more than 3 sides.

Circle packing is a beautiful and surprisingly deep topic. I'd also recommend taking a look at the work of Ken Stephenson, Bobenko Hoffmann and Springborn, and Mathias Höbinger's thesis, which goes into more detail about triangular meshes with tangent incircles.

Permalink Reply by Joris Burger on May 6, 2014 at 3:28am

Hi Daniel, thank you very much for your elaborate reply, I will look into the things you mentioned and see what I'll be able to figure out. Thanks again!

Permalink Reply by Joris Burger on July 9, 2014 at 9:22am

Dear Daniel,

I have spent some time working on the project described in the first post and I have a few questions that you might be able to answer.

I have based my solution on your Remesh_plankton_circles script. As I said I want to achieve an as compact as possible circle packing on an ellipsoid surface with only a few specified radii for the circles. I've gotten to learn that it is impossible to achieve compact circle packing on an ellipsoid, this is not a problem but I would still like to get as close as possible to a nice packing of circles. I've edited your code a little bit so that it doesn't really use the 'SizePoints' variable as it is not important for my outcome. I've added a 'weighted average' instead that uses the average of all of the expected circles.

Furthermore, because I want to limit the number of usable radii of the circles I've added a functionality that changes a circles radius to a radius that's specified beforehand. It now selects an available circle with a radius that is smaller than the actual radius. As circles still overlap sometimes I still need to continue with it. Also I still need to add a funtionality that lets me specify an amount of circles that it can aim for, e.g. it should have a maximum of 50 circles of 2mm, no more.

When going through your code I found a few numbers that are used to determine the WeightedCombo, these are for example (4f / 3f) in line 105 or (4f / 5f) in line 128. I was wondering where do these 4/5f's come from? Are they some sort of a constant value?

Other than that I am curious to know if you might have more ideas on how to go further with my definition? I am still looking for a much more dense and compact circle packing than I'm achieving at the moment and I was wondering on how to achieve this? Should in the mesh-creating part of the code be added a force that makes the (half)edges of the mesh want to approach a value that's the product of the radius of two of the available circle sizes? Or should I think in another direction?

Attached you can find a screenshot of what I'm working on now and the Grasshopper/Kangaroo file. I am kind of stuck on where to go from here so any help would be much appreciated! Thanks in advance! :)

Attachments: