mitchell-best-candidate-circles

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 http://bl.ocks.org/mbostock/1893974 )
mitchell-best-candidate-circles

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

colour_blind_test

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:

brute_force_37

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)
mitchell-best-candidate-loop

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:

mbc_238

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

mbc_144

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

natalie_p_0_l_1_2_mr_2

natalie_p_0_l_2_1_mr_4

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

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

My girlfriend’s bunny:
linus

My girlfriend’s bunny using a density map:
linus_with_density_map

Lascia una risposta

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

Immagine CAPTCHA

*

È 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="">