A friend of mine asked me to join him in a small side project that combines both art, programming and hardware. The latter is still in the design phase, so let me tell you about the art and programming part first. The principal idea is to generate art (random, really generative or from existing data) and let it being drawn in real life by a machine. We wanted to start simple and just process existing bitmap images and turn them into nice looking paths that can be drawn by the “machine”.

My initial idea was to generate a path from a random walk with a probability density that matches the surrounding pixel density of the current position. While that works in a way, the result is hardly legible. After some researching we came to the conclusion to do what in general is known as TSP art.

TSP art

TSP as in the Travelling Salesman Problem is a two-step problem. In a first step, for given number of points, we find a set of points that approximates the pixel density of the input image. In a second step, we determine a path that connects all points exactly once.

Sampling points

Because (photographic) image formation is a stochastic process one can do the reverse and use the brightness of each input image pixel as the probability that light hit the sensor. Since we want to have more points for darker areas, we have to use the inverse though. That and simple rejection sampling leads us to a basic point sampling algorithm:

1. If we have enough points stop.
2. Compute a random position (x, y) in [0, width; 0, height].
3. Read the pixel value at (x, y) in the input image, normalize it to [0, 1] and invert it.
4. Compute a random brightness value between [0, 1].
5. If the random brightness value is larger than the pixel value accept it.

This works wonderfully but due to the stochastic nature requires many samples which is detrimental to the path finding step. In the following image you can see the result for 10000 and 100000 points:

Luckily there are various approaches to approximate the density with less points the same way a human would draw an image using a pencil.

Weighted Voronoi stippling

Weighted Voronoi Stippling is such an approach. The basic idea in layman’s terms is as follows:

1. Sample a set of points randomly or use the algorithm from above.
2. Compute the Voronoi diagram for the point set.
3. For each Voronoi cell move its central point to the darkest area.
4. Continue until you are satisfied.

The following image shows you the result for 10000 and 30000 points and 5 as well as 100 iterations:

Note though that there are no major improvements past the 50 iterations mark.

Solving the Travelling Salesman Problem

Now that we have a good set of points we want to connect them and ideally visit each point only once. Sounds familiar? Yes, it’s the infamous Travelling Salesman Problem which is NP-complete, meaning you won’t find the best solution in a reasonable amount of time for a larger number of points. So again a bit of research and the most straightforward algorithm is again two-fold, first we compute an initial path using the Nearest Neighbor algorithm and then iteratively improve that path using the 2-opt algorithm. Here are two results for 10000 and 30000 points respectively:

inkdrop

All of the images have generated by a small Rust tool called inkdrop. It is split into a core library that implements the algorithms as well as some data structures and two binaries to drive them via command line or a GTK 4 user interface. The primary output data format is SVG which is super simple and matches the problem very well. To generate Voronoi diagrams I used the wonderful Voronator library which wraps the Delaunator library I tried to use before but gave me too many headaches.

Long-time readers will know that GTK is nothing new for me but GTK 4 is. And I must admit, I love the on-going work of the Gtk-rs team that provides usable GTK 4 bindings at this early stage as well as the GTK team itself. GTK 4 finally improves quite a few pain points for me and surprised me positively with the addition of layout managers and declarative property bindings. This allows one to write even less code and declare more UI facts in the builder file itself. Neat.

So, here is part one of our generative art adventure.

Update: The Rust bindings to GTK4 are now stable. Yay!