Hilbert Curve Fill

[robin-swift]

Copied from old to do list.

[tatarize]

The math on this is a bit beyond libembroidery I think, unless you're planning on advancing this library to do more than I think it should (read, write, compose embroidery).

---

Basically you draw a hilbert curve larger than the object you're filling. Then you cricut the curve with the other closed shape your filling. And you connect each segment along the edge to the next segment and every other segment gets an extra connection between them.

The math here is important to understand. A Hilbert curve is Eulerian, which is to say you start from one location and you can connect each segment to the next in an even number of nodes.

If you cut this with another shape, each time the edge of the graph is struck there will be 3 additional nodes. 2 nodes going to either the next or previous intersection and 1 nodes going to the other way, combine that with the now cut end of the original graph gives you 4 (even). This means that each point also creates a Eulerian graph. We then proceed to take any walk we want around the graph and we will inevitably end up back where we started since the combined graph is also Eulerian.

Do note, this is true for all Eulerian fills, even a basic scanline fill. Which is actually the algorithm Inkstitch currently uses for it's fills. You can fill any eulerian graph cut with another eulerian graph with at most 50% additional edge connections.

---

Doing this requires some pretty reasonable math with regard to the geometry. But, it serves as a solid basis for a wide variety of fill patterns. Basically you can fill an embroidery graph with anything that doesn't have an odd number of internal nodes. So wavy fills, hilbert fills, scanline fills, spirals, whatever.

Here's an MIT licensed no-dependency version that does this for simple scanlines.

https://github.com/EmbroidePy/vpype-embroidery/blob/main/vpype_embroidery/efill.py

[robin-swift]

Ah! That middle section is helpful in working out the intersection. If you see what I tried today in fills.c it's generated as an L-system so it can be configured into a dragon curve or some others.

unless you're planning on advancing this library to do more

Yes, the plan is to build better geometry support. A lot of development time since I joined the project has gone into shrinking the library to fit in an embedded system without removing features. Eventually I decided to split the embedded system code into an assembly library (the asm/ folder) and a C90 general library that supports all the underlying heavier calculations of Embroidermodder. So now I'm turning attention to what the other stated goals were; finishing any I can work out.