circular weaving algorithm

The Challenge of Color Circular Weaving

What is circular weaving? Well to demonstrate here is a sweet weaving machine built by Barton Dring:

Some time ago I was asked by Marcus J if I knew how to get a computer to find the best way to place the threads. Having done a lot of algorithmic art for the Makelangelo Software, I was ready and willing to take on the challenge. My first version included weaving on circles and squares with black thread on a white background. It has since been forked by others.

Since then I have been struggling with the challenge of multi-color weaving. One example is seen in the fork link above. Another is instagram artist art.nitka:

I’m pretty sure that if I can get two colors to work then it should extend easily to many colors. Like… the jump is from one to all the things. Bit of a curve.

In the original method I start at nail 0. then i look at all the possible threads that could go out from there and find the one that most closely matches my thread color (black). Longer thread s can get a higher score, so they can easily get more points, but shorter thread s can have less error so it quickly averages out. Once I find the best thread to some other nail N, I place it and move to nail N. Placing it means that I draw the thread on a blank canvas AND I substract that color from the original image. This way I am unlikely to go back over the same pair of nails and eventually the image should be mostly erased, leading to a natural stop.

My first attempt at multicolor was to have a black thread and a white thread alternating back and forth over the image. It wasn’t great.

My second attempt I made two copies of the source image, one for each thread color. I built a list of threads for each image separately. On their own each one was sort of OK. I could put white threads on a black background or black threads on a white background and it was as good as the original method. But put them together and there were obvious problems – The threads didn’t mix in the right order.

Suppose the picture was a white circle in the middle of a black circle. The white threads should go on first to make the center, and then the black threads should cover the white ones around the edge. The problem gets more complicated with a human face, where a dark thread for the eyes might have light thread in the middle for the nose and around the edges for the sides of the face… and then dark again on the edges for the hair!

When the lines are to be combined in the finished image, I start with an empty stack B. I want to add line A to stack B so that when I look down through the stack the image is most-correct. Some white might be on top of some black and vice versa. Remember: it might not be strictly white-black-white-black-etc.
Lines are not woven together – a new white thread cannot be under previous white threads.

It is a convenient property that two lines only cross at a single point. I can find the intersection of two line segments to tell if the threads overlap at all and where, then look at the image at that point and ask “which of these two threads would be best on top?” It is very quick to calculate… but wrong.

Sometimes the answer is indeterminate: lines might be parallel, non-intersecting, or equally good.

Sometimes it would be better to put A under some B lines, because the total error is lower than A being above all B. eg, some error might make a better final image. How much? Where? I don’t know. Aye, that’s the rub.

What it means is that a simple binary sort won’t work. I tried BubbleSort and I tried a TreeSort. Neither of them works quite right. The end result has sorting that is obviously wrong.

The Color Circular Weaving Solution

I don’t know! I have to get back to work, so it will just have to simmer in the crock pot that is my skull. Until a solution is found… wish me luck and share this with your friends. Maybe you or someone you know has a hint.