Creating an algorithm for string art

Introduction

I always was impressed by string art.
Not sure why, but was drawn to it from the first time I saw one (in physical form).

String art is a physical art form where you place nails or pins onto a background, mostly wood with a bright color.
Typically in a circular pattern close to the edge. Onto or better around the nails you span a thin thread (or thicker string) under tension.
If you do it right, it will form an image. The target image will be created by the threads or strings as they progressively darken the image.

Of course you can do bright colored thread onto dark background or any color you want. It's an art form, do whatever you like.

I recently stumbled upon a picture and was interested again. This time I wanted to learn more.

Surprisingly there were not much papers or documentation. Mostly just: we did it, but not how.

Also not much code I could find and the sparse papers told something like half an hour to generate.

So I came up with my own stuff, I'm not the first one to come up with it, but here I will show all the details
as well as the c++ code.

Preview

This is a torture test...
Image to recreate (Image from Randy Rodriguez from Pixabay)

Creating a resolution of 3278x3278 using the multicircle nail position with 776 nails resulted in 32772 paths and was generated in 307.8 sec on a Ryzen 5900X. Update with multithreading, now only 27.2 sec.
See full image (in svg vector format for the full details), warning: might crash your browser...

Here is an example with a traditional outer circle:

3360x3360 pixels, 720 nails results in 20446 paths.

How it works

The algorithm is a so called greedy algorithm. It uses an iterative approach and goes on. No back-tracking or similar.

First, create the target image converted to grayscale from 0 (black) - 255 (white).
Create a "current" image with the progress painted in with the same size.

Then repeat those steps:

1. calculate the difference between the current image and the target
2. from start position, draw a line to each other nail, calculate the new difference
3. pick the line that reduces this difference by the largest amount
4. use the new image as basis for 1 and repeat until the cutoff criteria is met.

The tricky part is how to calculate the differences and doing this extremely fast.
In case you don't know me, optimizing the heck out of stuff is my daily work.

So lets do this step by step.

Difference calculation

During test I tried different ways, but in the end the best results were a simple square of the difference.
Here is an example: The target of pixel is 127 (a middle gray), current pixel is a 255 (white). The difference is then (255 - 127)² or 16.384. The square has the advantage that if the values come closer, the change becomes smaller. So for 127 vs 150, the result is (150 - 127)² or 529.

How to make it fast

The naive approach would be to compute the whole difference on iteration start. Then paint one line and calculate again. Repeat for every line.
This means we need to do the expensive multiplication once per iteration and once for (number of pins - 1), so number of pins time. This is SLOOOOW. On an example image of 2000x2000 pixels and 1000 nails, one iteration would need 2000x2000x1000 difference calculations (4 billion multiplication and overhead). A multiplication roughly takes 6 CPU clock cycles (according to a page I found), so that means more or less 6-7 seconds per iteration just for the multiplication on a 4GHz clock.

So what can we do? Simple, reduce the number of difference calculations. Instead of actually drawing the line on the buffer, I use a line algorithm and only update the pixels on the line. I calculate the previous difference, update the value and calculate the difference again. But instead of 4 million pixels, just a few hundreds on average. If the image is 2000 pixels wide, the most pixels a line can have is 2000. plus maybe a few more for anti-aliased line. even if it in worst case 4000 pixels, compared to 4 million, quite the change. In case of a short line, even bigger difference.

Also, no need to compute the pixels again and again. The program creates all possible combination on startup, stores this in a list (vector) and stores the list in a hash map (unordered list). Also not every combination is needed, starting from nail 0, you have n-1 other nails to draw to. Then from nail 1, you already have the connection to nail 0, so you only need to calculate n-2 new connections and so on.

The result in above torture test  (3278x3278 pixels and 776 nails) about 6.4s to pre-calculate all possible combinations. The remaining 301s is spent to calculate 32.772 paths (with 775 lines each) or 25 million tries. That is an acceptable 84k test/s, on a single CPU core.

Variations

Also, why limit yourself to pure round nail positions around the outer circle, you can place your nails everywhere, on the article image I places in total 776 nails in multiple nested circles.

Here is an example with a 576 nail grid:

Usage

compile the source code with:

g++ -march=native `Magick++-config --cxxflags --cppflags` -Wall -Werror -o main main.cpp -O3 `Magick++-config --ldflags --libs`

and run with

./main <image name> <resolution x> <resolution y> <number of nails> <max number of iterations> <penalty for duplicate path usage> <lineColor>

Resolution is the output resolution, the higher, you get more precision, but higher memory usage and longer processing time.
The penalty should be set to 1 unless you get results where a single path is repeated too many times to make it darker. Increasing this value gives a penalty to the calculation to avoid it. The penality is the difference divided by valueⁿ where value is command line parameter and n is the number of times the path has been used.
lineColor is the darkening color, think of it more as the opacity of a black line. 0 means no darkening, 255 means full black on the first line. Useful values are around 30-100. Depends on the target image. Lower values mean more lines and more visual resolution.

Potential optimizations

In theory all lines from a given starting position could be calculated at the same time using multiple CPU cores or a GPU.
But it would mean, that each thread needs it's own scratch memory for the best result, they would need to be collected in the end and the best from multiple threads be copied a.s.o. That would be a lot of work and frankly, unless I'm torture testing the algorithm, a generation took less than 30s. Not sure if that is worth the time to create the improvements.

Also it is possible to have the nail position generated by image content and some density function or other fancy math.
This would increase the felt resolution by a lot, also stronger brightness gradients might be possible.

Feel free to implement those and send me a pull request ;)

The full (messy) source code is at https://git.contentnation.net/grumpydevelop/stringart.

Feel free to use it and drop a comment below where you used it.

Update from 2024-02-26

A multithreaded version has been pushed.
This improves the calculation speed a lot. The first step of creating the paths is still unchanged and not optimized, but the actual line drawing and matching is multithreaded now. Depending on the image, this result in speed improvements of factor ~10 on my 12/24 core CPU.

The compile step need a small change to:

g++ --std=c++20 -march=native `Magick++-config --cxxflags --cppflags` -Wall -Werror -o main main.cpp -O3 `Magick++-config --ldflags --libs`