Compact circle packing on complex surface

[texasvodkas (TexasVodka)]

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

2. 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

3. 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.

[DanielPiker]

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

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

[texasvodkas (TexasVodka)]

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.

[DanielPiker]

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.

[assistant.petercoffi (Assistant Petercoffinstudio)]

@DanielPiker

combined remeshing and circle packing

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

[Antonio_Cersosimo]

I see that you have good taste in music

[mnj90369]

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

[tinwarrior8]

Hello, has there been any progress on being able to pre-place circles in a certain brep, and having the circle packing script being able to recognize them such that when the script runs, it doesn’t have any overlap with these circles? I’ve noticed that the mesh doesn’t get offset evenly when experiencing sharp corners and edges. This sometimes causes the circle-packing to not be able to function properly in these areas.

As a solution I tried splitting off a portion of the brep with sharp corners. This portion I split off with the sharp corners, I just placed a triple tangent circle in it. Then with the remaning larger brep, I used the script on, which worked out quite nicely. I then extracted the curve data. However, when I attempted to stitch back the surfaces together, it still left a 4 sided gap between the circle in area 1 and the edge circles in area 2.

[assistant.petercoffi (Assistant Petercoffinstudio)]

Hi

@DanielPiker

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

Hi Samuel,
Unfortunately we have not been able to find a solution to these three questions. Daniel Piker mentioned he is working on an updated version of his combined version (which he mentioned May 5 in this thread), possibly as part of TriRemesh" but we haven’t heard of any developments yet re: these 3 problems. How about you? Have you found any solutions to these problems? Dan, if you’re reading this we’d be grateful for your advice or input if you have any. We’ve been stuck for a long time with this circle-packing problem. Thanks, Peter

[benedict (Ben)]

@assistant.petercoffi

@assistant.petercoffi

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.

the size of the circles is usually determined the surrounding edge length. however, the ratio between the smallest and the biggest circle is strongly influenced by the mesh’s point valence. if you have valence 4, you’ll have just 4 other circles around it, and therefor the one in the middle will be tiny compared to the surrounding ones. if a mesh vertex has valence 7 or 8, one big circle will be surounded by 8 relatively small circles. knowing this, you can influence the range of circle radii. a mesh with all verteces having valence 6 (let’s just imagine that exists) will result in a very regular pattern.

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.

you can select the corner mesh points from the trimmed mesh and add them to anchor, before putting it to the solver. maybe even a grab node, if you want to chose the corner position manually.

circpack_dome_corner.gh (15.9 KB)

[Elise_Morris]

Dear @benedict

I am currently very new to Grasshopper and am now working on continuing this design as mentioned previously in this thread (a design looking to compact-pack a range of circles with different diameters ranging from ~8”- ~27” on a surface of a shaped dome with sharp corners), and I see that you have provided the circpack_dome_corner.gh file as a help to this- Thank You. Could you explain a little bit of how that works or maybe look at our rhino file with our dome with sharp corners. I have attached the rhino file
03-04-2022_hasthestraightenedarches.3dm (1.9 MB)

Please let us know if you have any input on going about this problem. Any suggestions or assistance with this would be greatly appreciated.

Thank you

[benedict (Ben)]

Hi Elise

I admit this being pretty difficult to describe the whole process in a quick overall explanation. Where are you stuck?

[Elise_Morris]

Dear @benedict,

Thank you for your response, I am not exactly sure what questions to ask just yet. In the meantime I will try to implement your solution, circpack_dome_corner.gh, into our shaped dome design and I hope I can figure out how to make it work.

Our next challenge is to figure out how to limit the range of circle diameters that get packed on the shaped surface. I am aiming for a range of ~8” to ~27” if that’s even possible. Do you have any insight into how to set a range of circle diameters to pack and if I find myself stuck at that stage may I ask your advice again?

Thanks, Elise

[benedict (Ben)]

Hi @Elise_Morris

ok, I can try and tell very quickly the process as good as I know it (the real probs should go to Daniel Piker anyway):

you basically start with having a single surface. it’s pretty important that it’s a single surface and not a polysurface (at least for this definition). from this surface you create a mesh with very special properties.
luckily Daniel Piker already took care of the creation of those meshes automatically by creating TriReMesh, which you can find in the gh definition. angles and distances must be equal etc. however, this will give us a good base, as we want to be able to modify the mesh to our needs later on. I’ll come back to that later.

these properties mentionned before determine mainly how your circles will look like later on:

-the distance between the points will set a raw range for the size of the circles later on.
-the distance of the actual mesh edge from the surface mesh determines where your circles will end. imagine every mesh vertex (where “mesh-lines” intersect) will roughly be the center of the future circle.

so in the definition (which originally came from daniel piker as I mentionned before) the first steps are to set these things.

then you basically start flipping some edges to have a more random looking distribution like explained in my last post to assistant.petercoffi. you need think in ratio instead of fixed numbers to approach something usable. however, it becomes difficult when the range is small, which is not the case for your 8/27.

afterwards you have kangaroo solvers doing the rest of the magic. I strongly recommend watching some tutorials on kangaroo, without that base all my explanations won’t help much.

Hopefully this will give you some sort of introduction, however, I’d also recommend to have a look at the definition from daniel piker, as there’s less extras and therefor easier to follow.

best

Ben

[Elise_Morris]

Thanks for the brief introduction. I have been studying grasshopper tutorials, and am still struggling to grapple with this concept. May we hire your help to solve this problem we are stuck on, we could use your knowledge in this process.

Please email me if interested (elisecarolm@gmail.com)

Thank you for all of your help,
Elise

[Dhinesh]

Pls help us to add circles in some area… Is it possible?

[laurent_delrieu]

Hello
yes it is possible, I added 2 circles

Joking aside, if you want better answer give more elements than just a screenshot.
with circles packing in Kangaroo most of the time the number of circles is defined, so adding more circle is just adding more points/circles. Lets say you have 100 in a panel or a slider, just try 101, 102 …

[Dhinesh]

If increase the qty means also will get some area as opened… Is it possible to add point basis?

[benedict (Ben)]

As Laurent already mentionned, you should reeeeaaaally add your file to get some help with this.

[emilien]

Hi, the C# component do a great job but it become crazy when there’s holes in the surface :

Do you think it’s possible to make it work with more than one closed boundary ?

Thanks