Compact circle packing on complex surface

Greetings all, I have been working on a structure that requires circle packing on a shaped dome with some sharp corners. I have been getting some very helpful reference from this community but after some time without noticeable progress I have decided to come ask for help.

These are our criteria:

  1. control over the range of size of circles (8” to 30” diameter)

  2. maintaining the border of the existing shape

  3. a compact packing of circles (with 3-sided spaces between circle and between circles and the perimeter)

Feel free to let me know is any of these criterias are unreasonable within the framework of this problem and grasshopper.

The following are methods I have tried:

  1. collision based compact packing using kangaroo

PRO: control over size of circles

CON: not compact packing

  1. compact packing by remeshing the domed surface into a delaunay mesh, then create tangent incircle using kangaroo

PRO: compact packing

CON: the size of circles are not controlled, and the relaxed tangent incircle mesh have a tendency to “shrink” away from the thin “finger” region of the domed surface.

The

  1. compact packing by taking the connectivity of physics packing result, turn it into a Delaunay mesh, then remesh for tangent incircle compact packing.

PRO: it is less likely to “shrink” away from the “finger ” park of the surface,

CON: circles like to go over or not fill the surface after the relaxation of the compact packing has begun.

Some general questions:

  1. What controls the size of circles in the tangent incircle compact packing? Is it possible to control it?
  2. Mr. Daniel Piker’s work was extremely helpful in the process of this project, he mentioned compact packing isn’t achievable on every kind of surface, what are some features that go against compact circle packing on a surface?
  3. what does the “iteration” seen in many remeshing component represent? is it a process similar to Lloyd relaxation?

I was using Ngon‘s remeshing feature because the “simple remesh” in kangaroo downright refuses to function on this particular shape. Attached is a screenshot and a current version of the script. I believe Ngon is the only plugin in use. The left portion is the construction of the geometry and the physics packing but they are not used anymore for the most part. The right portion of the script is the tangent incircle compact packing.

Any suggestion and assistance will be much appreciated


this is a video of the “shrinking” problem

this is a example of the circle disrespecting the border

this is a example very close to the end goal, using method 3 with some manual drawn circle to fill the gap(blue), it still suffer from circle not adhere to border
bubble pavilion clean version.3dm (19.6 MB)
bubble pavilion MK4.gh (117.7 KB)
rhino 6 file and grasshopper, Ngon is only used for the remeshing.

My sincere thank to this community for the resources and examples it has provided.

1 Like


Have a go with this:
circpack_dome.gh (111.4 KB)

You’ll need Rhino 7 though - can you download the trial version?

5 Likes

Thank you very much for your assistance, this works a lot better compared to my script in rhino 6, I will still need some time to digest the work you did with C# but this is a great improvement.
An interesting result is the circle have higher chance to go over border when the circle size is too big and the border turn sharply(top of archway), I believe I can adjust the border offset and variable K until a desirable result is achieved.

1 Like

To give a bit more explanation - in a compact circle packing, the size of the circles is completely determined by the connectivity of the mesh and I believe 2 parameters for where they touch the boundary (essentially you can slide them along the boundary and choose how ‘bunched up’ they are - easiest to see on a circle as shown here).
So apart from these 2 degrees of freedom, once you’ve got your mesh with which vertex connects to which defined, you really can’t control the relative sizes without breaking the circle packing. There’s no way to just pick one circle and make it a bit bigger or smaller, because that would introduce gaps in all the surrounding ones.

Given a mesh, Kangaroo adjusts the edge lengths to meet a specific condition which allows it to be converted to a circle packing. To make the circles also tangent to some boundary there is a slightly different condition required on the lengths, and that is what the script part in the definition above does.

Because the final circles are centred on the vertices of the optimised mesh, to get them tangent to the boundary curve, the mesh needs to stop a particular distance away from this curve. The offsetting of the curve on the surface before remeshing in the above definition helps it start closer to this condition to avoid them popping onto the wrong side. I’ll have another look at that boundary tangency code though - I think it should be possible to adjust it to consider the target surface direction and always pull to the interior side to prevent this more robustly.

If the input mesh to this relaxation is nice enough, the relaxation for the circle packing property generally wont change it very much, so you don’t get big changes in the circle sizes after optimization. The TriRemesh component in Rhino 7 gives meshes with good connectivity, usually with only valence 5/6/7. This helps, as the occasional valence 4 or 8 vertices you often get with other remeshing tools will lead to larger variation in the circle sizes, as seen in the square in your second image.

The iterations of the remeshing are a sequence of topology updates (changing the number of vertices and which vertex connects to which), and vertex relocation - typically some form of smoothing and reprojection to keep them on the target surface, respecting sharp features and so on. Repeated application of these steps leads to a ‘nice’ mesh.
Here’s a post I wrote on it when I was first working on remeshing tools.

Now for the compact circle packing, what can sometimes be an even better way to go about it is instead of treating the 2 steps separately like above - remeshing then relaxing the resulting mesh for circle packing - to actually do both together in the same loop. So the optimisation for circle packing is part of the relocation step in the remeshing. That way, if the circle packing relaxation causes them to slide around and change size a lot, the mesh can update itself, which gets around the restriction I mentioned earlier about the connectivity determining the sizes.
I have actually coded versions of this combined remeshing and circle packing optimisation several years ago, but with older versions of both kangaroo and the remesher.
see here

At some point I will make an updated version of this combined version, possibly as part of TriRemesh.

4 Likes

Dear Dan,

Your input is helpful. Thank you.

The challenge we face with our design for a dome sculpture that will hold various size balls (basketballs, beachballs, soccerballs, exercise balls etc) is that we’d like to have greater variance of circle sizes within the circle-packed design.

  1. We’d like the range of circle diameters to be more varied in order to accommodate different size balls. Is there a way to control circle size variance within our desired circle diameter range of 8” to 30” diameters? For example, can we influence or control how many of the circles can accomodate certain size balls.

  2. Is it possible to compact-pack circles at the edges of our shape where there are sharp corners? In our current design the circles packed into most corners of our shape leave voids that have more than three sides.

  3. If this problem is unavoidable, would it work for us to manually circle pack these corner areas before letting the automatic compact packing and relaxation fill the remaining surface shape?

We’re excited to know you’ve worked to combine remeshing and circle packing optimisation and we would be happy to apply that when that is operable.

Thanks in advance for your help Dan.

Best, Peter

corner
Screen Shot 2021-05-12 at 10.52.08 AM
Screen Shot 2021-05-12 at 10.52.28 AM

I see that you have good taste in music :coffee:

Dear Peter,

I´m interested in your solutions for the problems and aims you mentioned in your last post.
Did you make any progress for the questions 1-3?

Best, Samuel