Theodore Gray's walking-stitch hiding optimizer

[golanlevin]

It would be terrific to have an implementation of the optimizer which Theodore Gray describes in this article: http://home.theodoregray.com/stitchblog/2015/7/10/embroidered-animation-finally

[LingDong-]

WIP of this feature is now version controlled at wip_features/satin folder of this repo.

Currently it is a standalone Processing sketch, which will be integrated into PEmbroider when it is more complete.

[golanlevin]

@LingDong- ‚  Not sure if this actually matters at all IRL, but is there a way to have all of the diagonals go in the same direction (e.g. all going from southwest to northeast)? Or do even/odd rules make that impossible? There might be some artifacts that arise when different diagonals are mixed together.

[LingDong-]

Hi @golanlevin, the diagonals are in different directions because:

All scan-lines go left to right. But some of them have to go from top to bottom (producing SW diagonals), while some of them have to go from bottom to top (producing NW diagonals).

While it is possible to make scanlines go from right to left for those that goes from bottom to top, I'll need to branch into 2 cases and write checks for each, and I think it can be error prone. There's a lot of nice assertions I'm getting from the preconditions that all scanlines go from left to right.

I'm thinking maybe we can test it first IRL, and if the diagonals are a problem, I can rewrite it to make reversed scanlines.

[golanlevin]

Hi @LingDong- , what's happening on the left edge here — are those off-by-one errors?

[golanlevin]

There's one row here which is missing dots — not sure if that's a sign of a bug or not:

[golanlevin]

I tried your second shape. Aliasing caused this shape to break up into two islands, only the first of which (the tiny single pixel in the upper left) got embroidered:

[golanlevin]

There appears to be a jumping error on that shape too:

This happens when rot = -0.84. A similar problem happens when rot = -3.94:

[LingDong-]

Hi @golanlevin , thanks a lot for all the testing!

The Off-by-one Issue

The first off-by-one issue is because when the algorithm finds two branches on lower left and lower right, and decided that it needs to stitch the lower right branch first, and after it's done with that it returns to the next row at the same column where the left branch is found. There are actually two problems:

• My scanline increments X at start of the loop instead of at the end, so that makes it actually skip the first one when the aforementioned jump happens.
• The next row might start to the left of the current row instead of at the same column, like this: ▟. Which didn't happen in your screenshot but nevertheless is a possibility!

So the fix is, to scan leftward and find the first black pixel. Now fixed:

The Issue of Missing Dots

That seems to be gone ever since I switched to the queue based flood fill. Must've been some subtle error with the previous implementation

The Issue of the Island

Yup I'll write something to preprocess the image first, getting rid of holes, tiny islands, and run the algo on each disjoint shape.

The Issue of the First Jumping

This is actually an unsolvable case. If you look at the row highlighted by green in the first screenshot below, it is the only corridor to go to the regions above it AND the one below it. So if the thread takes the corridor and go to the region above, there's no "road" to go back to the region below! If it uses the corridor to go to the region below, there is no way it can go to the region above! So actually there is a precondition for the raster method to work perfectly: every corridor needs to be at least 2 pixel in height. It doesn't need to be 2 pixel high all the time, just needs to be at unlucky situations like this.

If you look at the higher res version of the same frame, the problem is gone:

The Issue of the Second Jumping

Though this looks like a jumping issue, this is in fact the island issue. Even though the tiny pixel on lower left corner looks "connected" (by Moore neighborhood), the algorithm uses von Neumann neighborhood so it is actually classifies as an island.

Here's a screenshot right before it tries to jump to the island at the last second:

So yeah currently the algorithm assumes no holes, no islands. If there's one, anything could happen: it might just stitch the first island, it might make a jump to stitch all of them, etc. That's why I've been saying all this time I'll write a preprocessing step to handle these situations ;)

[golanlevin]

Fun report :)

[LingDong-]

Initial support for islands and holes now added: debe33def2ae5bf04f9973f7d05d92ecc5846178

• 1x1 islands and holes are thrown away since they're most likely aliasing artifacts.
• larger islands are handled this way: it first try to stitch the image with the original algorithm, then check the result against the input image to see if there're unfilled regions. If so, recursively redo these parts. This has the additional benefit of being a fallback solution for any potential degenerate cases that are causing missing parts.
• I came up with a rather interesting algorithm to deal with holes:) It's based on flood fill, but uses a cache for efficiency. It makes a bridge (in fact anti-bridge, or maybe canal) between the hole and the nearest side of the shape to its left. It identifies holes and fix them all in one pass.
• You can now use the mouse to make island or hole in the interactive demo:

Hole:

Island:

Holes instead of island can be created using island mode:

My algorithm is smart in the sense that it knows that it only needs to make a cannel to the closest hole that already has a canal, instead of all the way to the left edge. Currently it is dumb in the sense that it could've just walked upwards for 3 pixels and be done (which I intend to fix soon :P

I thinking about a way to get rid of the canal. So instead there will be two rows of "special" pixels. For the first row, if viewed from above (when scanline goes from top to bottom), it is on, but when viewed from below (when scanline goes from bottom to top), it is off. For the second row, if viewed from below, it is on, but when viewed from above, it is off. Both lines will thus be filled by scanlines going in opposite directions.

This requires to check which direction we're viewing it from for every pixel look up, which can be quite annoying. Wonder if there's an even smarter way.

[LingDong-]

Hi @golanlevin

hatchMode(SATIN) now integrated into the library! Works just like other hatch modes: 0dd20b340bf22703fc79a585b7597b502e945576

Example: b07857e3ecdbbe2af34de197cb323a581ec79d01

[golanlevin]

Spectacular work Lingdong. @tatyanade , could you please test the new SATIN hatch mode?