Color Based Optimization

[tatyanade]

Was doing this small test to see what order the colors would go - strokes are all the same color and fill is a different color but all the fills are the same. The second column is STROKE_OVER_FILL and the 3rd is FILL_OVER_STROKE. This is how it ran: It did the stroke for 1, then had me switch colors, did the fill for 2, had me switch color, did the stroke for 2 and 3, had me switch, did the fills for 3 and 4, had me switch, did the stroke for 5, had me switch, did the fill for 6, had me switch and did the stroke for 6 and 7, then i switched thread for the last time to cover the fill for 7 and 8. meaning i load the thread 8 individual times

Would be a lot less hassle if it does something more like strokes for 1,5,3,4, then having me switch to the color for the fill and doing the fill for 2, 3, 4, 6, 7, 8, then switching back to do the remaining stroke_over_fill strokes for 2 and 6

this would conflict with #35 stitch-wise TSP (since its currently acting object based) but is definitely a lot more user friendly to be able to optimize the embroidery so that you change out the thread the least amount of possible times

[golanlevin]

@tatyanade, this is fantastic user-testing, thank you — EXACTLY the kind of work I had in mind. I would much rather hear this from you than from hordes of complaining users.

So, @LingDong- : minimizing thread (color) switching seems to me like an even more important optimization than the object-based optimization we discussed earlier. It is truly a major hassle to switch colors (threads), especially since it requires threading the needle each time. Could you please add more options/settings that we can pass to the optimizer, so that (for example), we embroider all of the red objects at once, then all of the blue objects, to minimize thread switching?

[LingDong-]

ok. But one issue:

• say we have a red shape. part of the red shape is occluded by a blue shape drawn on top. Now we draw another red shape somewhere else, but it is on top of another blue shape.

• my code puts the red shapes together, and the blue shapes together. now the red shapes either both occludes blue shapes, or be occluded by the blue shapes, which is incorrect.

I can provide an option so user can decide for themselves if this optimization will break their design.

[tatyanade]

I think it makes sense to have to switch out thread specifically due to order of shapes in your specific example, and would be more interested in an option for least amount of color switching while also retaining the order of shapes

• so for your example I'd say loading the color 4 times is valid,
• in my original example loading color 8 times does make sense in order to retain the specified order, loading 3 times would make more sense as it would look identical, but loading twice due to the fact that there's 2 colors would not make sense cause it ruins the order that I told it to embroider, and would break the design

[LingDong-]

Hi @tatyanade, in that case the optimizer needs to "smartly" figure out what to re-order by computing the occlusion situation of the design and somehow iterate over a large number of permutations. To do that, the optimizer need to first render each group of stitches of same color onto a different layer. For example:

--- TOP ---

1. red
2. green
3. red
4. blue
5. green
6. yellow
7. red
8. blue

--- BOTTOM ---

Now since 1,3 and 7 are all red we want them to go together.

We try to put layer 3 after 6 so it's next to 7. We need to check it against layers 4,5,6 and make sure that there's no occlusion between them and layer 3, otherwise it messes up the design.

Say luckily it turns out there's no occlusion, and we manage to swap 3 and 6. Now we try to put 1 next to 6 and 7, because they're all red. We now need to check 1 against 2,3,4,5 to make sure there's no occlusion.

Say unfortunately, there's occlusion, so we cannot swap it. We stop here.

However, perhaps it turns out, instead of trying to put 1 and 3 next to 7, if we try to put 3 and 7 next to 1, there wouldn't be such an issue. 1,3,7 can be 1,2,3. So maybe we need to try all the 3!=3x2x1 orderings to see which works.

Now there're 4 different colors. We need to do that test for all of them. Which color do we try to optimize first? it will surely produce different results. Complexity seems to go up exponentially with the number of layers / colors.

Perhaps with some math, we can prove that some situations are impossible, and there're many less cases to test.

However, I'm just saying that this is not at all trivial problem, and potentially quite expensive if we couldn't come up with an algorithm that's less naive than what I just described. Perhaps there's a more sophisticated efficient algorithm. Perhaps we can reduce it to a known problem. If the problem reminds you of some well-known solved (or unsolvable) problem please let me know :)

Of course, I understand that it is quite useful (and an interesting problem too!). I'm happy to dig into it. @golanlevin what do you think?

[LingDong-]

Here's a terrible monte carlo idea: Try 100,000 random permutations, compute a score for each of them. If a permutation breaks the design, it gets score of Infinity. If it is valid, score it by the number of color change required. We pick the one with the lowest score.

[golanlevin]

It's not a terrible idea.

[LingDong-]

Hi @golanlevin @tatyanade I made some progress on the Monte Carlo color optimizer: 4150b8568390528571343bda0bacabae77cd8c4a

It is currently a standalone processing sketch, living in wip_features/optcolch, to be integrated in to the library when more complete.

I'm randomly generating each layer as a differently-colored triangle, and rendering is stored as a boolean array. For each different permutation, the one-hot arrays are re-composited, and tested against the original.

In the visualization below, the small pictures are rendering of each permutation (they should look identical). On the right there's a stack of colors, which indicates the ordering and color of each layer. The top layer is at the bottom of the stack.

In the text beneath each picture, the hex string is the ID of each layer concatenated. The top layer is at the right of the string. Number of color changes is also indicated.

The leftmost picture is the original ordering.

The performance is dependent on number of colors and number of layers (of course), but also seems dependent on the "hardness" of each instance of the problem. Sometimes the layers aren't interleaving with each other that much, so in just a second it comes up with some 5 good solutions, but sometimes it takes forever.

[golanlevin]

Perhaps the argument to the colorOptimize function should be how many seconds you're willing to wait for a solution :)

[LingDong-]

Hi @golanlevin, this is now integrated into the main library: a6605230910ef8cfedd6fb4ca0ce408f4585f6dc

E.g. output from running it on @tatyanade 's original case:

[PEmbroider]  Original color change: 7, optimizing...
[PEmbroider]  Color opt trial # 95, improved color changes to: 4
[PEmbroider]  Color opt trial # 313, improved color changes to: 3
[PEmbroider]  Color opt trial # 413, improved color changes to: 2
[PEmbroider]  Color opt timed out, best solution: 2 color changes

It came up with the optimal solution in less then 1 second.

Usage:

beginOptimize(1 /*number of seconds you're willing to wait */, 3,999 /* old arguments */);

PEmbroider_text_1 is also updated with the new functionality.

[golanlevin]

I like this "*number of seconds you're willing to wait" as an argument. Really funny but practical.

[tatyanade]

@LingDong- when using begin/endOptimize, do you still need to call the regular E.optimize() function before endDraw, or would that be redundant?

[LingDong-]

E.begin/endOptimize will be enough, the optimization happens the moment endOptimize is called.

[tatyanade]

Im running this with the flower example right now; It takes a long time due to i think just my laptop being old, but it would be nice if there where a way for me to specify how long i am willing to wait for the color optimization versus however long it takes to actually optimize the stitches - maybe something like E.optimizeColors(seconds) that runs before/after E.optimize? Ran the flower example for E.beginOptimize(10800,1,100) specified for about 3 hours but ran over- and I'm not sure it even got to the color optimization since its still 118 color changes (unless your design has constraints of all the colors overlapping)

[golanlevin]

Hi @tatyanade , I think it might be better to start with a simpler design to test the color-based optimization....

[LingDong-]

Hi @tatyanade sorry I don't think the color optimization would work on the flower example. Firstly the colors overlap each other two much, then also 118! is waaaay to many permutations. I've already tried to run it over night for some 10 hours without reducing a single color...

[golanlevin]

Yeah, 118 factorial is 4.6 x 10¹⁹⁴. Nope nope nope.