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

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:

• bakedegg.JPG, 115 KB
• circlepackingegg.gh, 29 KB