Glossary and notation

20.1 Notation quick reference

Symbol	Meaning
$$D$$	high-level design and intent
$$B$$	material and process setup
$$M$$	target machine profile
$$P$$	stitch or command program
$\mathcal{E}$	physical execution or forward-fabrication model
$\Omega$	a planar sew region
$\partial\Omega$	boundary of a region
$\Gamma$	a continuous thread path or set of paths
$$p_i$$	the $$i$$ th discrete needle position
$$d(x)$$	local preferred stitch direction
$$h(x)$$	local row spacing
$\varphi(x)$	scalar potential used to generate level-curve paths
$$u(x)$$	material displacement field
$$G=(V,E)$$	a graph with vertices $$V$$ and edges $$E$$
$\chi$	Euler characteristic
$$b_0,b_1$$	numbers of connected components and holes in a planar region
$$L(P)$$	a loss or cost assigned to program $$P$$
$\rho(x)$	local penetration or thread-density estimate

20.2 Terms

Term	Meaning in a stitch compiler
Anisotropy	Direction-dependent behavior. Fabric may stretch differently along warp, weft, and bias; thread reflectance and stitched stiffness are directional too.
Appliqué	A staged process that places and secures another material, often with placement stitches, tack-down, an operator stop, cutting, and a finishing border.
Attachment state	Whether the top thread is considered secured to the work at the current point. It affects jumps, trims, tack stitches, and valid transitions.
Bean stitch	A repeated running-stitch pattern that traverses short segments multiple times to form a heavier line.
Betti numbers	Topological counts. For planar embroidery regions, $$b_0$$ counts connected components and $$b_1$$ counts holes.
Boustrophedon route	An alternating back-and-forth traversal, like mowing a field. Common for neighboring fill rows.
Boundary compensation	A geometric adjustment intended to counter expected pull, push, or registration error at a region boundary.
Color block	A consecutive group of commands sewn without a color or needle change.
Command IR	A machine-neutral representation of stitch, jump, trim, stop, color, needle, and end commands.
Compensation	Deliberate modification of geometry or stitch placement to offset expected physical deformation.
Connected component	A maximal region or graph substructure in which every part is reachable from every other part.
Contour fill	A fill made from paths that follow repeated offsets or distance contours of a boundary.
Coverage	How completely thread visually or structurally occupies a target region. Coverage depends on thread width, loft, substrate, spacing, direction, and layering.
Cross field	A four-way direction field whose orientations are equivalent under $90^\circ$ rotation. Useful in meshing and some lattice constructions; most ordinary stitch direction is a two-way line field.
Density	Informally, how much thread is placed in an area. A compiler should distinguish row spacing, along-row sampling, layer count, and physical thread coverage.
Direction field	A direction assigned continuously or discretely over a region. It guides local stitch orientation.
Directed acyclic graph (DAG)	A graph with directed edges and no directed cycles. Used to represent sew-before and cover-before constraints.
Euler characteristic	A topological invariant. For a planar region, $\chi=b_0-b_1$ .
Euler trail	A graph walk that uses every required edge exactly once. It exists in a connected undirected graph when zero or two vertices have odd degree.
Fill / tatami stitch	A family of closely spaced rows used to cover an area. “Tatami” commonly describes a regular back-and-forth fill.
Hoop / work envelope	The physical fixture and the region the machine can safely reach for a given setup.
Intermediate representation (IR)	A data model between source artwork and target bytes. Different IRs preserve geometry, semantics, paths, stitches, or machine commands.
Jump	A non-sewing movement between positions. Whether the thread remains attached, is trimmed, or leaves a visible float depends on surrounding commands and machine behavior.
Layer	A semantic and temporal unit whose order affects coverage, structure, registration, and appearance.
Line field	An orientation field in which $$d$$ and $$-d$$ are equivalent. Stitch angle is normally a line field because $30^\circ$ and $210^\circ$ describe the same local axis.
Lock stitch / tack stitch	Small securing sequences at an end or beginning. Exact terminology varies; the compiler should model their purpose and provenance explicitly.
Machine profile	Capabilities, limits, coordinate rules, command mappings, and process assumptions for a target machine and format.
Medial axis	The locus of centers of maximal inscribed disks. It captures the branching “skeleton” of a shape and is useful for width estimation and path planning.
Motif fill	A repeated decorative pattern clipped or deformed into a region.
Offset	A curve or region displaced by a specified distance. Offsets are used for inset, expansion, contour fill, overlap, and compensation.
Pareto-optimal	A solution for which no objective can improve without worsening at least one other objective.
Path	An ordered continuous curve or discrete polyline. A path does not by itself specify whether movements are stitches, jumps, or hidden travel.
Penetration	A needle-down location in the fabric. Repeated or tightly clustered penetrations can damage or stiffen the substrate.
Pull compensation	Extension intended to counter the tendency of stitching to draw a region inward, commonly along stitch direction.
Push compensation	Adjustment intended to counter outward displacement or bulging caused by thread placement and material response.
Quantization	Mapping continuous coordinates or parameters to a finite target resolution.
Region	A bounded planar domain with semantic identity, boundaries, components, holes, and intended stitch treatment.
Routing	Choosing traversal order, direction, entry/exit states, travel paths, jumps, trims, and sometimes color-block order.
Running stitch	A sequence of stitches sampled along a path, usually used for outlines, details, underlay, or travel.
Satin column	A narrow region sewn with alternating stitches between two rails, often controlled by rungs or paired cross-sections.
Scalar field	A numeric value at each point, such as distance, spacing, density, confidence, or a potential whose level sets form stitch rows.
Signed distance field	A scalar field giving distance to a boundary with one sign inside and the other outside. Useful for offsets, masks, and geometric queries.
Singularity	A point or small region where a direction field is undefined or cannot remain smooth. It may be required by topology rather than caused by numerical failure.
Stabilizer	Supporting material used to control deformation and provide a substrate for stitching. It is part of the material stack.
Stitch length	Distance between consecutive needle penetrations along a sewn path. It is distinct from row spacing.
Stitch primitive	A semantic generator such as running stitch, satin, fill, motif, underlay, or appliqué step.
Stitch program	The ordered commands executed by the embroidery machine.
Streamline	A curve everywhere tangent to a vector or direction field, obtained by integrating the field.
Thread path	The geometric route taken by top or bobbin thread. It may include sewn segments, floats, tie-ins, and structural underpaths.
Topological event	A split, merge, birth, or death of path components as an offset, contour, or threshold changes.
Travel stitch	A sewn movement used to get from one working location to another, ideally hidden under existing or future stitching.
Trim	A command or machine action that cuts thread, changing attachment and startup requirements.
Underlay	One or more preliminary stitch layers used to stabilize, support, shape, or lift later stitching.
Winding number	A measure of how a closed path wraps around a point, used to determine inside and outside robustly.

Algorithmic reference and implementation checklist

21.1 Representative complexity

Complexity notation is useful for architecture, but constants and output size matter enormously in geometry. A robust library call can beat an elegant custom algorithm by a wide margin.

Let $$n$$ be input curve or segment count, $$k$$ the number of intersections, $$|V|$$ and $$|E|$$ graph size, $$m$$ field degrees of freedom, and $$N$$ generated stitches.

Operation	Representative complexity	Notes
Curve flattening or resampling	$$O(n+N)$$	Output-sensitive; adaptive error tests add work near curvature
Sweep-line segment intersections	$O((n+k)\log n)$	Arrangement construction also pays for output topology
Connected components	$$O(\|V\|+\|E\|)$$	DFS or union–find variants
Topological sort of layer DAG	$$O(\|V\|+\|E\|)$$	A remaining edge after the sort indicates a cycle
Euler trail construction	$$O(\|E\|)$$	After graph preparation, Hierholzer’s algorithm is linear
Dijkstra shortest paths	$O(\|E\|\log\|V\|)$	With a binary heap; alternatives vary by edge weights
Undirected Chinese Postman	Polynomial	Dominated by shortest paths and minimum-weight matching of odd vertices
TSP, GTSP, many sequencing variants	NP-hard	Use heuristics, branch-and-bound, or mixed-integer models at appropriate scales
Sparse field smoothing	Roughly $$O(m)$$ per iterative step	Direct factorizations can be faster for repeated right-hand sides but use more memory
Streamline integration	$$O(N)$$ samples plus field lookup	Seeding, collision, and spacing checks can dominate
Nearest-neighbor checks	Expected $O(\log N)$ per query	Spatial hashing may be simpler and faster for uniform stitch scales
Raster coverage or heatmap	$$O(R+N)$$ with indexing	$$R$$ is raster size; naïve segment–pixel work can be much larger
Mixed-integer global solve	Exponential worst case	Often effective on reduced candidate sets with good bounds and time limits

The most important scaling decision is often not the solver. It is the representation. Routing 100 semantic objects with a few entry/exit candidates is far easier than routing 50,000 individual stitches as unrelated points.

21.2 A minimum viable stitch compiler

A minimum viable compiler should be able to:

normalize units, transforms, orientation, and coordinate handedness;
import paths and construct valid closed regions;
generate running stitches, a basic fill, and a basic satin or narrow-column treatment;
keep stitch length and row spacing separate;
represent stitch, jump, color change, stop, trim, and end semantically;
enforce hoop and target-delta limits;
preserve layer order and detect cycles;
choose deterministic entry, exit, and object order;
export at least one target format and decode it for comparison;
report short stitches, long stitches, jumps, trims, bounds, and unsupported commands;
render a decoded-output preview;
maintain provenance from source object to generated stitches;
have golden-file and round-trip tests.

This already qualifies as a compiler. It need not solve inverse textile mechanics on day one.

21.3 A production-quality compiler

A more mature implementation adds:

Geometry and topology

robust Boolean operations and winding rules;
component, hole, adjacency, and shared-boundary analysis;
topology-aware offsets and contour branching;
signed-distance and medial-axis queries;
protected negative space and overlap semantics;
geometry repair with explicit diagnostics.

Stitch planning

semantic primitive IR with multiple traversal candidates;
spatial direction, spacing, compensation, and confidence fields;
field-guided and contour fills;
first-class underlay and appliqué stages;
tapered and split satin policies;
deterministic texture and stagger generation;
local and global path alternatives.

Scheduling and optimization

precedence-constrained routing;
visibility-aware travel costs;
attachment-state planning;
color and needle scheduling;
route refinement after compensation;
exact or bounded optimization for small difficult cases;
Pareto or lexicographic objective handling.

Mechanics and calibration

versioned machine, material-stack, and process profiles;
spatial pull, push, and overlap compensation;
penetration and stiffness risk maps;
uncertainty estimates and extrapolation warnings;
calibration-card ingestion and profile fitting;
physical regression records.

Backends

a capability matrix for every target;
explicit lowering and emulation policies;
delta splitting and quantization checks;
metadata and color-block handling;
encode–decode semantic comparison;
target-specific conformance fixtures.

Product infrastructure

stable diagnostic codes and documentation links;
provenance-aware visual debugging;
incremental compilation;
deterministic builds with recorded seeds and versions;
IR serialization and migration;
performance tracing by compiler pass;
anonymizable telemetry for real production failures;
a corpus of synthetic and real-world test designs.

21.4 A useful test corpus

Include deliberately hostile cases, not just attractive demo art:

a self-intersecting path with ambiguous fill rule;
nested holes and touching boundaries;
a dumbbell shape whose insets split;
a narrow acute wedge;
a satin whose rails reverse or cross;
a field with incompatible boundary constraints;
disconnected line art with many odd-degree junctions;
a precedence cycle;
a route whose “hidden” travel becomes visible after order changes;
movements just below, at, and above target delta limits;
duplicated points and zero-length commands;
coordinates at all hoop boundaries;
a design with thousands of tiny objects;
a design that changes topology under compensation;
a corrupted or truncated target file;
a valid file whose decoded semantics differ from the source plan.

For each case, store expected diagnostics as well as expected output. A compiler that rejects a bad design with an excellent explanation is behaving correctly.

21.5 A maturity ladder

It is helpful to think in layers rather than in a binary “auto-digitizing works” claim.

Level	Capability
1. Encoding	Writes syntactically valid machine files
2. Geometry	Generates usable stitches from clean vector shapes
3. Semantics	Understands primitives, layers, underlay, and entry/exit intent
4. Optimization	Routes and schedules globally under constraints
5. Material awareness	Predicts risk and compensates using measured profiles
6. Closed loop	Learns from registered stitch-outs and production outcomes
7. Inverse design	Jointly optimizes appearance, mechanics, topology, and machine execution

Each level is useful. The architecture should allow growth without forcing high-level design intent through a low-level point-list interface.

References

References and further reading

The following sources are a practical starting point rather than an exhaustive bibliography. The embroidery-specific literature is relatively small, so adjacent work in computational fabrication, direction-field design, cloth mechanics, and graph routing is essential.

For the central embroidery-path problem, begin with Liu et al. on direction-aware streamlines and Tian et al. on spiral paths. For the mathematical machinery behind fields, continue with direction-field and vector-field processing references. For the material side, the cloth-modeling and computational-embroidery papers show why geometry alone is not enough. For real implementation semantics, inspect the official Ink/Stitch documentation and pyembroidery source.

Margaret Ellen Seehorn, Gene S.-H. Kim, Aashaka Desai, Megan Hofmann, and Jennifer Mankoff, “Enhancing Access to High Quality Tangible Information through Machine Embroidered Tactile Graphics,” Proceedings of the ACM Symposium on Computational Fabrication (SCF ’22), Article 23, 2022. https://doi.org/10.1145/3559400.3565586

Gabriel Cirio, Jorge López-Moreno, David Miraut, and Miguel A. Otaduy, “Yarn-Level Simulation of Woven Cloth,” ACM Transactions on Graphics 33, no. 6, Article 207, 2014. https://doi.org/10.1145/2661229.2661279

Georg Sperl, Rosa M. Sánchez-Banderas, Manwen Li, Chris Wojtan, and Miguel A. Otaduy, “Estimation of Yarn-Level Simulation Models for Production Fabrics,” ACM Transactions on Graphics 41, no. 4, Article 65, 2022. https://doi.org/10.1145/3528223.3530167

⁴

Qiming Tian, Yupin Luo, and Dongcheng Hu, “Spiral-Fashion Embroidery Path Generation in Embroidery CAD Systems,” Computer-Aided Design 38, no. 2, pp. 125–133, 2006. https://doi.org/10.1016/j.cad.2005.08.004

⁵

Zhenyuan Liu, Michal Piovarči, Christian Hafner, Raphaël Charrondière, and Bernd Bickel, “Directionality-Aware Design of Embroidery Patterns,” Computer Graphics Forum 42, no. 2, pp. 397–409, 2023. https://doi.org/10.1111/cgf.14770

⁶

Xiangjia Chen, Guoxin Fang, Wei-Hsin Liao, and Charlie C. L. Wang, “Field-Based Toolpath Generation for 3D Printing Continuous Fibre Reinforced Thermoplastic Composites,” Additive Manufacturing 49, Article 102470, 2022. https://doi.org/10.1016/j.addma.2021.102470

⁷

Kate S. Glazko, Alexandra A. Portnova-Fahreeva, Arun Mankoff-Dey, Afroditi Psarra, and Jennifer Mankoff, “Shaping Lace: Machine Embroidered Metamaterials,” Proceedings of the 9th ACM Symposium on Computational Fabrication (SCF ’24), 2024. https://doi.org/10.1145/3639473.3665792

⁸

Ink/Stitch, “Tatami Stitch (Fill Stitch),” official documentation. https://inkstitch.org/docs/stitches/fill-stitch/

⁹

Fernando de Goes, Mathieu Desbrun, and Yiying Tong, “Vector Field Processing on Triangle Meshes,” ACM SIGGRAPH 2016 Course Notes, 2016; and Felix Knöppel, Keenan Crane, Ulrich Pinkall, and Peter Schröder, “Globally Optimal Direction Fields,” ACM Transactions on Graphics 32, no. 4, Article 59, 2013. Course notes; direction-field paper

¹⁰

Jack Edmonds and Ellis L. Johnson, “Matching, Euler Tours and the Chinese Postman,” Mathematical Programming 5, pp. 88–124, 1973. https://doi.org/10.1007/BF01580113

¹¹

Ink/Stitch, “Tools: Stroke—Redwork,” official documentation. The tool’s routing goal is to traverse every path exactly twice. https://inkstitch.org/docs/stroke-tools/

¹²

Ink/Stitch, “Commands,” official documentation. https://inkstitch.org/docs/commands/

¹³

Huamin Wang, James F. O’Brien, and Ravi Ramamoorthi, “Data-Driven Elastic Models for Cloth: Modeling and Measurement,” ACM Transactions on Graphics 30, no. 4, Article 71, 2011. https://doi.org/10.1145/2010324.1964966

¹⁴

Ink/Stitch, “Satin Column,” official documentation. https://inkstitch.org/docs/stitches/satin-column/

¹⁵

Abhinit Sati, Ioannis Karamouzas, and Victor B. Zordan, “DIGISEW: Anisotropic Stitching for Variable Stretch in Textiles,” Proceedings of the ACM Symposium on Computational Fabrication (SCF ’21), Article 3, 2021. https://doi.org/10.1145/3485114.3485121

¹⁶

Yu Jiang, Narjes Pourjafarian, Alice Haynes, and Jürgen Steimle, “Embrogami: Shape-Changing Textiles with Machine Embroidery,” Proceedings of the 37th Annual ACM Symposium on User Interface Software and Technology (UIST ’24), 2024. https://doi.org/10.1145/3654777.3676431

¹⁷

Ayesha Nabila, Hua Ma, and Junichi Yamaoka, “4D Embroidery: Implementing Parametric Structures in Textiles for Sculptural Embroidery,” UbiComp/ISWC ’22 Adjunct, pp. 88–90, 2022. https://doi.org/10.1145/3544793.3560358

¹⁸

Xinling Chen, Michael McCool, Asanobu Kitamoto, and Stephen Mann, “Embroidery Modeling and Rendering,” Proceedings of Graphics Interface 2012, pp. 131–139, 2012. https://doi.org/10.5555/2305276.2305299

¹⁹

EmbroidePy, “pyembroidery,” an open-source Python library for reading and writing embroidery formats. https://github.com/EmbroidePy/pyembroidery

²⁰

Ink/Stitch, “Tack and Lock Stitches,” official documentation. https://inkstitch.org/docs/stitches/lock-stitches/

Symbol	Meaning
$\(D\)$	high-level design and intent
$\(B\)$	material and process setup
$\(M\)$	target machine profile
$\(P\)$	stitch or command program
$\mathcal{E}$	physical execution or forward-fabrication model
$\Omega$	a planar sew region
$\partial\Omega$	boundary of a region
$\Gamma$	a continuous thread path or set of paths
$\(p_i\)$	the $\(i\)$ th discrete needle position
$\(d(x)\)$	local preferred stitch direction
$\(h(x)\)$	local row spacing
$\varphi(x)$	scalar potential used to generate level-curve paths
$\(u(x)\)$	material displacement field
$\(G=(V,E)\)$	a graph with vertices $\(V\)$ and edges $\(E\)$
$\chi$	Euler characteristic
$\(b_0,b_1\)$	numbers of connected components and holes in a planar region
$\(L(P)\)$	a loss or cost assigned to program $\(P\)$
$\rho(x)$	local penetration or thread-density estimate

Operation	Representative complexity	Notes
Curve flattening or resampling	$\(O(n+N)\)$	Output-sensitive; adaptive error tests add work near curvature
Sweep-line segment intersections	$O((n+k)\log n)$	Arrangement construction also pays for output topology
Connected components	$\(O(\|V\|+\|E\|)\)$	DFS or union–find variants
Topological sort of layer DAG	$\(O(\|V\|+\|E\|)\)$	A remaining edge after the sort indicates a cycle
Euler trail construction	$\(O(\|E\|)\)$	After graph preparation, Hierholzer’s algorithm is linear
Dijkstra shortest paths	$O(\|E\|\log\|V\|)$	With a binary heap; alternatives vary by edge weights
Undirected Chinese Postman	Polynomial	Dominated by shortest paths and minimum-weight matching of odd vertices
TSP, GTSP, many sequencing variants	NP-hard	Use heuristics, branch-and-bound, or mixed-integer models at appropriate scales
Sparse field smoothing	Roughly $\(O(m)\)$ per iterative step	Direct factorizations can be faster for repeated right-hand sides but use more memory
Streamline integration	$\(O(N)\)$ samples plus field lookup	Seeding, collision, and spacing checks can dominate
Nearest-neighbor checks	Expected $O(\log N)$ per query	Spatial hashing may be simpler and faster for uniform stitch scales
Raster coverage or heatmap	$\(O(R+N)\)$ with indexing	$\(R\)$ is raster size; naïve segment–pixel work can be much larger
Mixed-integer global solve	Exponential worst case	Often effective on reduced candidate sets with good bounds and time limits