# Circle Packing with Kangaroo and Galapagos?

This is an exciting topic, some people get the circle fever and it’s got me. I’m VERY interested in exploring circles as structure. My favorite kind of circle packing uses Kangaroo collisions but it isn’t as accurate as it should be because you are usually starting with random Populate point locations and random size assignments. It’s especially difficult if you need to use specific circle diameters on a doubly curved surface.

Using Zombie Solver and Galapagos I was hoping to find an optimized pre/post packing solution. I needed a metric for measuring what good packing is, and for better or worse I choose tangent connections, creating bridges between neighboring circles at the closest points, keeping the maximum proximity to less than the smallest diameter so no circles were crossed.

I used the combined length of all “bridges” as a minimization fitness for Galapagos, with the Populate seed for the slider. It getting a little closer I think, and doesn’t strain my laptop too badly but I feel like I haven’t taken this far enough, I should be adding more sliders or finding a better metric by which to measure good circle packing, especially in relation to ground contact. Maybe a multi-objective solver instead of Galapagos?

I was wondering if anyone else has been down this particularly rabbit hole?

I had some help turning @DanielPiker 's C# script for keeping circles within edge boundaries into Python, it’s included here. I understand Python a little better and am working on an angle there as well.

collider with galap.gh (43.6 KB)

This is part of my thesis research but also a real world construction, I convinced my employer to take a leap of faith, our first stack of stainless steel rings just arrived. I might get fired if this doesn’t work but I’ll post my results and findings nonetheless.

4 Likes

Hi again @closedcurve
It’s an interesting challenge.

As discussed before, a compact packing where all the gaps between the circles are 3 sided is only possible when you can adjust all the radii individually, so you’d require almost all unique circle sizes, which I guess rules it out in terms of manufacturing.

For a given set of radii I think the most we can hope for is to get all circles tangent to at least 3 others and most of the gaps with 4 sides or less, and reduce the size of these 4 sided gaps as much as we can.
It looks like what you have here is already doing a pretty good job of this.
One thing you could try that I think could be more effective than changing the random seed with Galapagos (which doesn’t really give any advantage over just brute force testing many values, because there’s no continuous variable being optimized) is to use the regular solver and jiggle the size multiplier by small amounts above/below 1.0. Think of it a bit like vibrating concrete after pouring to reduce gaps and bubbles. This will probably naturally result in a bit of a gradient, with the smaller circles collecting near the base and the big ones rising to the top. You’d need to combine this with adjusting the circle counts to get the right number to fill the surface well.

The other approach I’ve considered, that would require quite a bit more scripting but might make it possible to reduce the gap sizes more significantly would be a new version of the remeshing with radii that iteratively adjust based on the neighbours similarly to in the compact circle packings, but jumping between a given set of possible radii instead of varying them continuously.

3 Likes

Thanks @DanielPiker for the input, still computing it mentally. I started focusing on the gaps as another metric to optimize. I have Minimizing the sum bridge length, Minimizing the negative space between circles (average perimeter of remaining pieces) and Maximizing tangent connections per circle.

Aside from the issue you pointed out with brute forcing a random seed for a Genome, I have some good Fitness measurements for optimizing circle packing. From what I can tell though, it’s splitting hairs considering the fixed radius/quantity constraints.

What I really need is better packing around the perimeter, if my Karamba shell approximation of the structure showed me anything it’s that the edges are everything. I’m trying to avoid manually packing the edge via Grab because I feel like that is defeats the purpose a little bit. Also I can’t manually pack and Galapagos repack with the Zombie Solver, it’s either-or.

I get your recommendation about shaking, I loved your Brazilian Nut Effect video but is there a way to pull toward the edge boundary on a surface and not just downward? If the populated points started in the middle and pull toward all edges simultaneously, I feet like better edge packing would take place.

Are the sizes of 18/24/36 fixed? Or could you choose a different set of radii?
To really reduce the gaps I think an approach close to or starting from a compact circle packing will be the best way.

When you have a fairly isotropic mesh and optimize it for tangent circles, you get all different radii, but they do tend to be loosely clustered around 3 values, linked to the number of neighbours they have. In a good mesh most will have 6 neighbours and there will be a few smaller ones with 5 and big ones with 7.

The peak for the valence 6 ones is fairly spread out, so it might be good to use 2 medium sizes along with one small and one big. Replacing each circle with its closest match from this set of 3 or 4 would break all the tangencies, but I think if you then repacked them as hard spheres you could maybe get back to something fairly close to compact but with mostly thin 4 sided gaps.
Ideally the remeshing/radius adjustment/collisions would all happen at once, allowing the connectivity to change and circles to jump between radii as it changed. I will have a go at scripting this at some point, but perhaps in the meantime there would be a way with the existing components and a staged approach.

1 Like

I see what you mean, the circle sizes are unfortunately fixed. Those sizes represented the most efficient breakup of 240" pipes for rolling and cutting into rings.

(30) qty 240" pipes to create (60) qty 36" OD Rings… 2 rings per pipe
(20) qty 240" pipes to create (60) qty 24" OD Rings… 3 rings per pipe
(10) qty 240" pipes to create (40) qty 18" OD Rings… 4 rings per pipe

We’ve gotten our rings in and have started welding them.

That being said, I’ve considered adding more fixed (the missing 30 inch?) or dynamic radii ‘imaginary’ circles (as CNC cut plywood spacers to be removed after welding the structure, placed/removed where they wouldn’t effect surrounding integrity) or if I could get the budget increase, permanent 3/16 thick stainless steel disks to be welded to the rings. The only problem there is I would need to somewhat control the distribution so all the special circles wouldn’t randomly congregate.

The distribution of random sizes/positions is a problem on many fronts.

When you have a fairly isotropic mesh and optimize it for tangent circles, you get all different radii, but they do tend to be loosely clustered around 3 values

That is very interesting, even if it meant sacrificing material, I maybe should have tried for that instead. In the method I’m employing for construction, close-enough is maybe close enough. In addition to a plywood support structure, I’m locking each circle tangential with it’s neighbors using two 900lb steel ties. I’m theorizing that if I build the entire structure like this (before cutting the ties and welding) that a certain amount of natural relaxation will occur. A visually acceptable amount of displacement that forgives loose connections, a little.

1 Like

I made a little test to demonstrate the concept just in a flat plane

Here it looks like the best fit 3 radii are in a ratio of approx 0.73 : 1 : 1.23
You’re not so far off this with 18/24/36 (0.75 : 1 : 1.5)

(though the quantities of each are very different - you’d ideally want something like 1:7:1, so a big majority of them in the medium size)
Still, it might be worth trying

2 Likes

Well I just heard from the company we sent our pipes to for rolling, I thought they had already rolled everything but it turns out we still have 30 pipes left that were intended to become 36" OD. I’ll loose some space filling potential by reducing those to 24" but can make it up with imaginary circles (gonna call them circle spaces) or discs.

I’ll see what I can crunch but I can’t get a ratio of medium that great, however I’m assuming the closer I get to that ratio the better my collision based packing will become.

Thanks.

EDIT: Ugh, that’s quite the bald spot.

This is awesome! I love how you have just launched into buying massive stainless steel rings without actually finishing the design!

Looking forward to seeing the results!

2 Likes

Sometime an harsh and forced situation motive you to find incredible solutions.

Me too, but I hope for the best.

Have you thought about having the rings planes being not being tangent to the dome shape? eg some ring a bit “up” and some a bit “down” or maybe even tilted position to adapt on the situations?
Probably way more complex to compute but… well i’m just guessing…

2 Likes

Wait till you see what else I blindly ordered and haven’t finished designing for, this isn’t the only circle packing structure I proposed. The fab company I work for is building a park but it’s a tight deadline and materials are scarce/backordered across the board, it was an “order what we can and build with whatever we get” dilemma, which is actually okay for parametric design if you have creative freedom.

Some of the logs for a cordwood wall

Some of the sliced up steel drums for a shade structure

Plus more steel and concrete “circles” on the way or in production. Hope I still like circles/spheres/cylinders/rings/cones after all this.

4 Likes

An ideas for the rings, might be to grind or mill a flat at the point of contact/tangency point. Don’t know your wall thickness (of the tubes the rings are made of), but the flat will make it easier to weld and position.
Also, you have already probably thought of this, but I suggest establishing several control points. or control rings, and start building outward from those. The purpose of this is to allow you to distribute the error evenly amongst the various circle members; I use this technique when dividing a circle. Accurately determine the position of the control points, and then measure subsequent rings off of those. This technique is also used in surveying to establish a control grid, and from what I understand, aircraft frames.
Sounds like a great project, good luck!

1 Like

I wondered about that too… If the rings can move inward and outward in a normal direction then you essentially change the radius by the diameter of the ring’s tube. However if the effect is not randomly but evenly distributed across the structure it would look awful.

This is a nice idea too but those flats need to be not only positioned where the tangent points are but also angled to match the surface curvature so it without a 5 axis CNC it would be hard to do. Plus I am assuming those rings are made from hollow tubing? If they are solid bar then that’s a heavy duty structure!

Material shortage is a nightmare everywhere at the moment! It certainly looks like a great company to work for though!

Flat would be easier, the other structural circle packing examples I’ve seen were all using more cylindrical elements, tubes or cones that rest on each other. For better or worse I’m committed to round tangential(ish) connections. We may have to do something like this, with plasma cut stainless bowties.

That is a great idea I hadn’t considered, it would be most ideal if we were assembling flat and raising the sculpture, like a laser model I did by hand, but we don’t have a crane in our fab shop. I think we’ll have to assemble these in position, leaning against a support structure, stacked on themselves. I expect (but welcome) some distortion/displacement, as long as we can make the arch join, I think we can fenagle some equilibrium before removing the ties and welding. There is a reason I didn’t try for a more complex form, next time I will.

I accidentally did something like that when I was using a more ambitious form, it looks really great. It was more fitting and creative looking for a public art piece. Definitely more of an advance maneuver to compute and label/assemble though, I gotta walk before I can run.

Some updates, I started using Wallacei as a multi solver (wanted to try Octopus but it crashes on opening) and the first results are promising. This is me adjusting the Populate (points) seed and an adjustment of the openings as a gene, and the number of bridges (tangential points) within 2 inches + plus the avg length of the bridges as a fitness.

The red circles are also something new, I’m using an initial packing to distribute points throughout the form (thanks @Will_Wang) to combine with Populate in my primary circle packing to give me some adjustable dynamic circles (among my fixed radii rings) to plug into Wallacei. Those variable circles can either be empty spaces if structurally sound, or plasma cut stainless steel discs. The beauty is each variable circle could be larger or smaller, to help add or reduce tension in the surrounding packing. A crutch to help make up for the limitations of building a structure out fixed radii.

Haven’t tested it yet, these are all just fixed size disks, will test variable soon.

I’m off on too many tangents as it is (pun) but I think the “migration” of randomly populated point positions to packed point positions is very interesting. It’s something I only ever thought to consider when using the Zombie Solver, as the regular solver is so chaotic. IF you were aiming to pre-populate circle positions in a more intentional and controlled manner than Populate, before packing, this would be a good metric to measure and solve for. That potentially opens the door to utilizing both remeshing to extract some (if not all) point positions, AND then collision based packing after you drop in your fixed radius circles based on how closely they round/snap to the remesh circle radii. That would be a more educated, measurable start.

Do you think that is worth investigating @DanielPiker ?

ALSO: Bonus Karamba displacement animation, because it’s fun. Hopefully the real thing won’t do that…

2 Likes

@DanielPiker For comparison I am calculating displacement in Karamba for circle packing with a granular convection/Brazilian nut effect. I liked the definition to posted for a 2D demonstration of that but I was wondering if is possible to get that kind of result through a Zombie Solver, or if that is too complex?

I know you can get close enough by just adjusting scale but I’m not sure how I could get the zombie to calculate with a controllable amount, I could input to my solver (Galapagos/Octopus/ect) like ‘3 shakes’ vs 6 or something.

The shaker Daniel made, for reference: Circle packing with fixed radius and fixed number of circle for each radius - #12 by DanielPiker

Hi Daniel !
tying to open the script but it tells me that I need the version 2.5.3 of kangaroo,
I have rhino 7

thanks

Forgot about this thread, I’ll do an in-depth follow-up soon but I found a sweet spot between Kangaroo, Octopus and Karamba. Going to begin real assembly soon, just a few more thousand iterations first.

6 Likes

Hi -

Please run the Rhino `SystemInfo` command and copy-paste the result here.
-wim

Rhino 7 SR1 2020-12-8 (Rhino 7, 7.1.20343.09491, Git hash:master @ 350b20978b4fcd75493212fbd3c4248983612f86)

Windows 10.0.19041 SR0.0 or greater (Physical RAM: 31Gb)

Computer platform: LAPTOP - Plugged in

Hybrid graphics configuration.
Primary display: Intel(R) HD Graphics 4600 (Intel) Memory: 1GB, Driver date: 1-21-2020 (M-D-Y).
> Integrated graphics device with 3 adapter port(s)
- Windows Main Display is laptop’s integrated screen or built-in port
Primary OpenGL: NVIDIA Quadro K1100M (NVidia) Memory: 2GB, Driver date: 9-25-2017 (M-D-Y). OpenGL Ver: 4.5.0 NVIDIA 385.73
> Integrated acclerated graphics device with 4 adapter port(s)
- Secondary monitor is laptop’s integrated screen or built-in port

OpenGL Settings
Safe mode: Off
Use accelerated hardware modes: On
Redraw scene when viewports are exposed: On

Anti-alias mode: 4x
Mip Map Filtering: Linear
Anisotropic Filtering Mode: High

Vendor Name: NVIDIA Corporation
Render version: 4.5
Driver Date: 9-25-2017
Driver Version: 22.21.13.8573
Maximum Texture size: 16384 x 16384
Z-Buffer depth: 24 bits
Maximum Viewport size: 16384 x 16384
Total Video Memory: 2 GB

Rhino plugins that do not ship with Rhino

Rhino plugins that ship with Rhino
C:\Program Files\Rhino 7\Plug-ins\Commands.rhp “Commands” 7.1.20343.9491
C:\Program Files\Rhino 7\Plug-ins\rdk.rhp “Renderer Development Kit”
C:\Program Files\Rhino 7\Plug-ins\RhinoRenderCycles.rhp “Rhino Render” 7.1.20343.9491
C:\Program Files\Rhino 7\Plug-ins\rdk_etoui.rhp “RDK_EtoUI” 7.1.20343.9491
C:\Program Files\Rhino 7\Plug-ins\rdk_ui.rhp “Renderer Development Kit UI”
C:\Program Files\Rhino 7\Plug-ins\NamedSnapshots.rhp “Snapshots”
C:\Program Files\Rhino 7\Plug-ins\RhinoCycles.rhp “RhinoCycles” 7.1.20343.9491
C:\Program Files\Rhino 7\Plug-ins\Toolbars\Toolbars.rhp “Toolbars” 7.1.20343.9491
C:\Program Files\Rhino 7\Plug-ins\3dxrhino.rhp “3Dconnexion 3D Mouse”
C:\Program Files\Rhino 7\Plug-ins\Displacement.rhp “Displacement”

I am trying to pack circles, with 3 given fixed radius inside a rectangle (the proportion of the quantities of each radius could be a variable).
I would like to apply something like galapagos that optimizes the mínimum area difference betwen the circles and the rectangle.

circulos en un rectangulo Gravity.3dm (3.4 MB)
alexpacking-gravity.gh (64.7 KB)

1 Like