A quest for 2d unequal circles packing

I always love studying things that are more or less far from what is my usually area of interest (art <--> tech).. seriously, who doesn’t love R&D? :)
So I’ve just started my new “quest for 2d unequal circles packing” algorithms!
While it may sound a little nerdy, it’s a quite fascinating topic.. but most importantly, some of the algorithms used for packing have beautiful visual outputs.
And that’s the main driver for me (the classical intelligence at work together with the romantic one!). One other driver is showing the elegant beauty of math!
Just to clear things out, here what I want to reproduce:

(“Mitchell’s Best Candidate” algorithm, image taken from )

Did you recognise it?
This kind of pattern of circles with different radii is quite used in color blind tests.


But I think that it looks rather cool also for other purposes.
Who said generative art?
So, let’s get started.
There’s a lot more than what the eye sees.
I first followed a great video by the great Daniel Shiffman, which uses a Brute Force approach (you can find it here).

Here’s a gist of the code used (which was packed into an fbo):

As you can see from the code, we create new circle at random position, check if it’s overlapping, if it’s not, we add it.
At the end we want to have 1024 circles. But we say to the computer:

“Hey, if you try more than 2 000 000 times to add a circle and you don’t find a right spot, please stop. Don’t ruin your life on this. Get over it”.

The visual result of this code is something like this:


The color comes as a second layer, now we’re just interested in the distribution of the circles.
The output is not bad.. but as you can see, not as elegant as the first image. It’s just random circles that don’t overlap. Their distribution is not totally random, but not rather clean.
Something was missing: there’s no magical math at work.
How do we get some magic math?

Obviously, from a mathemagician!
So, the second part of the quest will focus on studying the algorithm of the first image: “Mitchell’s Best Candidate”.
It’s an algorithm that approximates Poisson Disc Sampling (Shiffman has made a video also on this topic), and gives a nicer sampling than a simple uniform random distribution.

First things first: I’m going to use Mitchell’s Best Candidate to generate new samples (dots on a screen, really).
MBC algorithms generates a new random sample by creating k candidates and picking up the best of them. Best = the sample that is farthest away from previous samples.
So let’s begin.
Here’s the code that I used:

The following gif shows how new samples are generated:

(Mitchell’s Best Candidate: click on the image to view the animation)

The distribution of samples is really a lot nicer. Much more clean and elegant.
Now that we have the samples, we just create random circles at the location of the samples.
Yep, we were drawing circles before, too.. but now we want each one with a different radius! So let’s tweak a bit the process:

The visual outcome of the latest algorithm is this:


How cool is that?
Has even some fractal feeling to it.
Now let’s add some colour and little more padding between the circles..


Et voilà!
I know for sure that there are some major optimisations that could be done to the code (now it needs about 5 seconds for generating an image like that).
But at the end.. who cares? My scope is making tools for creating *beautiful?* things, not writing super-optimised code. Code is just another tool for creating tools. :)

// UPDATE 07/10/2016

I’m back again with some early results.

Exploring variations in padding and circles radius.



Here I tweaked the original algorithm in order to use a b&w image to drive the density/radius of the circles:

Here’s the density map I used for the above pic:

My girlfriend’s bunny:

My girlfriend’s bunny using a density map:

Lascia una risposta

L'indirizzo email non verrà pubblicato. I campi obbligatori sono contrassegnati *


È possibile utilizzare questi tag ed attributi XHTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">