Notation and coordinate discipline

Embroidery bugs often masquerade as sophisticated geometry bugs when the actual culprit is millimeters, coordinate handedness, or quantization. Establish a strict coordinate policy before writing clever algorithms.

2.1 Recommended internal conventions

A practical compiler should:

1. use millimeters for all physical geometry;
2. use floating-point coordinates in the high- and middle-level IRs;
3. keep the design-to-machine transform explicit;
4. delay target quantization until the machine-lowering pass;
5. record whether the source coordinate system has a downward- or upward-pointing \(y\) axis;
6. record the transform provenance for every imported object.

A general affine mapping is

where \(q_D\) is a design-space point, \(q_M\) is a machine-space point, \(A\) includes scale, rotation, reflection, or skew, and \(t\) is translation.

For a restricted similarity transform,

Do not silently mix transforms into path coordinates. Keeping them explicit makes hoop rotation, design mirroring, and format export easier to test.

2.2 Quantization

Suppose a target stores coordinates on a lattice with spacing \(h\). A simple quantizer is

The per-axis quantization error is at most \(h/2\), but cumulative path behavior can be worse because neighboring points may collapse to the same lattice point. After quantization, the lowering pass should:

• remove accidental zero-length movements where they have no semantic purpose;
• retain deliberate short lock stitches;
• re-check maximum delta limits;
• split movements that exceed the target format’s representable range;
• re-evaluate the final bounds.

Quantize once. Repeatedly snapping geometry at several compiler stages creates drift, destroys symmetry, and makes round-trip behavior unpredictable.

2.3 Machine coordinates are not artwork coordinates

An artwork point describes where a feature should be. A stitch point describes where the needle should penetrate. Those are related but not interchangeable.

A boundary may need to be expanded for pull compensation. A satin rail may be offset beyond the visible shape. An underlay may be inset. A travel path may deliberately pass through an area that will later be covered. Preserve the original artwork geometry alongside generated stitch geometry so the compiler can measure the difference rather than forgetting it.

Geometry: from artwork to manufacturable regions

3.1 Curves and arc length

Artwork commonly contains line segments, circular arcs, and Bézier curves. A cubic Bézier curve is

The parameter \(t\) is not physical distance. Uniform steps in \(t\) generally produce nonuniform stitch lengths. The arc length from \(0\) to \(t\) is

To place stitches at physical intervals, sample by arc length or use adaptive subdivision with an error tolerance.

For a regular planar curve \(r(t)=(x(t),y(t))\), curvature is

For a short arc of length \(s\) and approximately constant curvature, the deviation between the arc and its chord is roughly

That gives a useful curvature-aware step estimate:

where \(\varepsilon\) is the allowed geometric error. Combine this with stitch-length limits rather than using it alone.

3.2 Polygons, orientation, and winding

Closed artwork should be normalized into valid planar regions. For a polygon with vertices \(p_i=(x_i,y_i)\), signed area is

with indices taken cyclically. The sign identifies orientation under a chosen coordinate convention.

A compiler should adopt a consistent rule, such as counterclockwise outer boundaries and clockwise holes. The exact choice matters less than consistency.

Point containment should be defined using a winding rule or even–odd rule. The selected fill rule is part of the design semantics; it should not change accidentally during import or Boolean cleanup.

Robust polygon processing must handle:

• self-intersections;
• coincident or nearly coincident edges;
• tiny holes and slivers;
• duplicated vertices;
• collinear runs;
• nested regions;
• open paths mistakenly presented as fills.

Use robust orientation predicates and a documented tolerance model. A single global epsilon is rarely sufficient across designs with very different scales.

3.3 Boolean arrangements

Overlapping artwork is not yet a stitch plan. The compiler first needs a planar arrangement: a subdivision of the plane into cells whose ownership, color, and layer relationships are known.

For two regions \(A\) and \(B\), useful operations include:

But visual stacking is not always equivalent to geometric subtraction. If a foreground object will cover a background object, keeping an overlap may prevent registration gaps. The region model should therefore distinguish:

• visible geometry;
• nominal artwork geometry;
• sew geometry;
• coverage or bleed geometry.

Those four shapes may differ.

3.4 Offsets and morphological operations

A uniform outward offset by radius \(r\) can be expressed as a Minkowski sum:

where \(B_r\) is a disk of radius \(r\). An inward offset is an erosion:

Offsets appear everywhere in embroidery:

• pull compensation expands a boundary;
• underlay is often inset;
• border coverage extends across a shared edge;
• contour fills repeatedly erode a region;
• collision margins expand forbidden areas;
• appliqué tack-down paths may sit inside a cut line.

Uniform offsets are only a first approximation. A more general boundary displacement is

where \(n(s)\) and \(t(s)\) are the boundary normal and tangent, and \(\delta_n\), \(\delta_t\) vary with direction, material, stitch type, and local geometry.

Offset curves can self-intersect or change topology. Always run them through an arrangement or cleanup stage before treating them as valid regions.

3.5 Signed distance and the medial axis

The signed distance field of a region \(\Omega\) is commonly defined as

It supports:

• offsets as level sets \(d(x)=r\);
• width estimation;
• adaptive inset selection;
• centerline extraction;
• proximity-aware density;
• boundary penalties.

The medial axis is the set of interior points with more than one nearest boundary point. It is a natural skeleton for narrow columns and branching shapes, but it is sensitive to tiny boundary perturbations. Practical implementations prune short branches, simplify the boundary first, or use a scale-aware skeleton.

Topology: the shape of the problem before its measurements

Geometry asks how long, how wide, and at what angle. Topology asks what is connected, what encloses what, and where continuity is possible.

4.1 Components, holes, and Euler characteristic

For a planar region with \(c\) connected components and \(h\) holes,

For a planar cell complex,

These values are useful sanity checks after Boolean operations and offsets. If a small numerical perturbation unexpectedly changes the number of holes, a fill algorithm may produce a radically different path structure.

4.2 Topology changes are algorithmic events

Repeated insets do not merely shrink a shape. Loops can split, merge, appear, or disappear. A contour-fill generator must detect those events and decide how to connect the resulting loops.

A 2006 embroidery CAD method for spiral fills explicitly decomposes a region into ring-like subregions, organizes them in a tree, and connects their spiral paths.¹ The broader lesson is important: contour fill is a topology-management problem, not just “call offset in a loop.”

4.3 Layering creates a partial order

Suppose an object has underlay, fill, detail, and border. Their dependencies form a directed acyclic graph, or DAG:

Overlapping objects add more precedence edges. If a rear petal must be sewn before a front petal, add

A valid stitch order is any topological ordering of the DAG. The cheapest valid ordering is a scheduling problem with setup costs, because moving between objects, changing color, and trimming thread all have costs.

4.4 When a region should be split

A single visual shape does not have to be one embroidery object. Split it when one or more of these occurs:

• the desired direction field contains an unavoidable singularity or discontinuity;
• a satin column branches or becomes too wide relative to curvature;
• one section requires a different underlay or density;
• an overlap must be sewn at a different time;
• a contour fill undergoes a topology event that cannot be connected cleanly;
• a material constraint changes across the shape;
• the visual hierarchy benefits from separate textures.

A split is not necessarily a failure. Often it is the correct way to expose a topological seam and place it where the artwork can hide it.

Stitch primitives as mathematical objects

A stitch primitive is more than a visual name. It is a generator with geometry, sequencing rules, physical behavior, and machine constraints.

5.1 Running stitch

A running stitch follows a curve \(\gamma(s)\) and places needle penetrations at arc-length positions

with

For approximately constant target length \(\bar\ell\) and path length \(L\),

A better sampler adapts \(\ell_i\) to curvature, corners, local importance, and machine constraints.

Repeated running stitches can be modeled as edge multiplicity on a graph. A bean or triple-style pass is not merely “duplicate every point”; the reversal pattern affects where penetrations accumulate and how the line appears.

5.2 Satin columns

A satin column can be represented by a centerline \(c(s)\), a unit normal \(n(s)\), and width \(w(s)\). Its idealized rails are

Needle points alternate between the rails. The thread spans across the column while the sampling stations advance along it.

A useful local warning condition comes from offset geometry. An offset at distance \(d\) from a curve becomes singular when

For satin rails with \(d=w/2\), trouble is likely when

In plain language: a column should not be wider than the local bend can support. The compiler may need to narrow it, split it, alter the centerline, use explicit rungs, or choose another stitch type.

A complete satin generator must decide:

• centerline and rail correspondence;
• station spacing;
• corner behavior;
• width transitions;
• split-stitch behavior for long spans;
• entry and exit points;
• center-walk, contour, or zigzag underlay;
• pull and push compensation;
• branch decomposition.

Professional embroidery tools expose explicit “rungs” or direction lines because a centerline alone is not enough to define how opposite boundaries correspond.

5.3 Constant-angle fill

Let the desired thread direction be

and the row normal be

A family of parallel fill rows with physical spacing \(h\) is

For each row, intersect the line with the fill region. The intersections produce one or more intervals. Sample each interval along \(u_\theta\), usually reversing alternate rows to create a boustrophedon path.

There are two independent spacings:

• row spacing, which controls coverage across the region;
• stitch length, which controls penetrations along each row.

Many confusing user interfaces call both of these “density.” A clear compiler model keeps them separate.

Rows can be staggered by varying the along-row phase:

where \(\ell\) is nominal stitch length and \(\alpha\) controls the repeat cycle. Staggering prevents penetration columns from lining up into unwanted channels.

5.4 Contour and spiral fills

A contour fill follows level sets of a distance-like function. The simplest version repeatedly offsets the boundary inward:

The hard part is connecting the loops. Topology changes create a tree or graph of loops. Connection choices affect continuity, visible bridges, sharp turns, and deformation.

A spiral fill tries to turn nested contours into one continuous path. Possible strategies include:

• cutting each loop at a selected phase and joining adjacent loops;
• solving a continuous scalar field and tracing a spiral-like level path;
• decomposing topology into ring regions and connecting them through a tree;
• allowing deliberate seams at low-salience locations.

The center of the region is not always the best spiral origin. The geometric centroid, area centroid, medial-axis root, and user-specified focal point can all differ.

5.5 Field-guided fill

A field-guided fill follows a spatially varying direction \(d(x)\) and spacing \(h(x)\). This is the natural model for fur, feathers, leaves, muscles, waves, and thread painting.

Research on directionality-aware embroidery treats the stitched pattern as a set of optimized streamlines that approximate both a direction field and a color or density target.² Similar field-to-toolpath methods appear in continuous-fiber fabrication, where vector fields are converted into scalar fields and then into iso-curves.³

Field-guided fill is developed in detail in Chapter 6.

5.6 Meander, stipple, and space-filling paths

A meander fill is a connected path designed to distribute thread over an area without using regular rows. Possible constructions include:

• a path through Poisson-disk or blue-noise samples;
• a traveling-salesperson tour through weighted samples;
• a maze or spanning-tree traversal;
• contour-aware noise followed by smoothing;
• centroidal Voronoi sampling and graph connection.

These methods trade predictable grain for organic texture. Their main constraints are local coverage, turn radius, self-proximity, and continuity.

5.7 Motif and lattice fills

A motif fill begins with a repeated cell, graph, or tile. Let a motif be \(M\), and let \(T_{ij}\) be translations, rotations, or other transforms. The raw pattern is

then clipped to \(\Omega\).

Clipping can leave disconnected fragments. The compiler must choose whether to:

• sew fragments independently;
• connect them with hidden travel;
• alter motifs near the boundary;
• preserve complete motifs and leave a margin;
• deform the lattice to fit the shape.

For free-standing lace, connectivity is a structural constraint rather than a convenience. Every component must be tied into a load-bearing network, often with deliberate redundancy.⁴

5.8 Underlay is a layer, not a checkbox

Underlay changes the physical boundary conditions for everything above it. It can stabilize the fabric, lift top stitches, establish an edge, distribute load, and reduce sinking into textured material. Ink/Stitch’s documentation, for example, treats fill underlay as a lower-density layer that supports the top fill, often at a different angle.⁵

Common underlay primitives include:

• center walk;
• edge walk or contour underlay;
• zigzag underlay;
• low-density fill;
• lattice or tack-down structures.

Represent underlay explicitly in the layer DAG. That makes it possible to inspect, reorder, simulate, and optimize rather than hiding it inside a generator.

5.9 Appliqué and staged operations

Appliqué introduces non-stitch operations into the program:

1. placement line;
2. machine stop;
3. fabric placement;
4. tack-down line;
5. trimming or cutting step;
6. cover stitch;
7. decorative detail.

The stitch compiler becomes a workflow compiler. Stops, user actions, and material insertions are first-class instructions with precedence constraints.

Direction, density, and scalar fields

A flat fill angle is one number. Expressive embroidery needs a value at every point.

6.1 The field bundle

For a region \(\Omega\), a useful design representation contains several fields:

• color or target appearance \(c(x)\);
• direction \(d(x)\);
• desired row spacing \(h(x)\) or line density \(\rho(x)=1/h(x)\);
• salience or importance \(w(x)\);
• material compensation \(\delta(x)\);
• forbidden or low-confidence areas \(m(x)\).

These fields need not share the same resolution. Direction may be defined on a mesh, density in a raster, and user constraints as vector strokes. A field-sampling layer should hide those storage differences from path generators.

6.2 A stitch direction is usually a line, not an arrow

For most fill appearance, direction \(\theta\) and direction \(\theta+\pi\) are equivalent. The thread has an axis but no meaningful arrowhead. This makes the correct object a line field.

A convenient representation is the doubled-angle complex number

Because

opposite vectors map to the same value. This avoids a classic bug: directly averaging \(d\) and \(-d\) produces zero even though they represent the same stitch orientation.

For discrete samples with confidence weights \(w_j\), an average line orientation can be estimated by

This is the two-fold rotationally symmetric, or 2-RoSy, representation used in direction-field processing.

6.3 Sources of direction

Direction constraints can come from:

• user-drawn guide strokes;
• the tangent or normal of a boundary;
• a centerline or skeleton;
• image gradients;
• a structure tensor;
• estimated surface form;
• principal stress directions;
• neighboring stitch regions;
• a procedural pattern.

For an image \(I(x,y)\), the structure tensor is

where \(G_\sigma\) is a smoothing kernel. The eigenvectors indicate dominant local gradient and isophote directions. Which eigenvector should guide thread depends on the intended effect: following an edge and crossing an edge are both artistically useful.

6.4 Field smoothing and constraint fitting

Suppose \(\theta_0(x)\) is a noisy or incomplete target direction. A conceptual energy for a smooth line field is

The first term fits constraints. The second discourages rapid spatial variation. The doubled angle preserves the \(\pi\) symmetry.

On a mesh or pixel graph, the smoothness term becomes a weighted sum over neighbors:

Boundary constraints should usually be weighted, not blindly absolute. A demand that every stitch be tangent to every boundary can force singular behavior inside the shape.

6.5 Singularities are not necessarily bugs

A direction field cannot always satisfy all boundary and interior constraints while remaining smooth and nonzero. Poincaré–Hopf-type index constraints relate field singularities to topology.⁶

A simple mental example is a disk whose direction must be tangent to the circular boundary. The field must somehow turn through a full revolution. A singularity, seam, spiral center, or region split is unavoidable.

The application should therefore support:

• detecting singularities;
• assigning an index and confidence;
• moving them to less salient locations;
• opening a seam;
• splitting a region;
• switching fill strategy locally.

Trying to “smooth harder” often spreads the defect rather than solving it.

6.6 Method A: tracing streamlines

Given an oriented vector representative \(v(x)\) of the line field, a streamline satisfies

Numerical integration can use Euler, midpoint, or Runge–Kutta steps. The line-field sign must be chosen consistently from step to step, usually by selecting the orientation with positive dot product against the previous tangent.

The difficult part is not integrating one curve. It is seeding enough curves to achieve the target density without crowding, gaps, collisions, or dead ends.

A practical streamline system needs:

• seed placement;
• minimum separation tests;
• termination near boundaries or existing curves;
• singularity handling;
• merging or connection rules;
• smoothing with boundary containment;
• density-error feedback.

Liu and colleagues use divergence-derived sources and sinks to seed and organize embroidery streamlines, then optimize the paths for smoothness and connectedness while balancing direction and density objectives.²

6.7 Method B: scalar potentials and iso-curves

Instead of tracing many independent streamlines, solve for a scalar field \(\phi(x)\) whose level sets become stitch rows.

If the desired path tangent is \(d(x)\), then the desired gradient is perpendicular to it. Let

where \(R_{-\pi/2}\) rotates by \(-90^\circ\). Solve

The Euler–Lagrange equation is a weighted Poisson equation:

Then extract level sets

Their approximate physical spacing is

This formulation turns global row generation into a sparse linear or nonlinear solve, depending on the constraints. It also reveals an important fact: not every desired direction-and-density field is exactly integrable. The scalar solve finds a compromise.

Field-based fabrication research uses closely related vector-field, scalar-field, and iso-curve pipelines for anisotropic toolpaths.³

6.8 Method C: distance and offset fields

For contour fills, choose

or a modified distance field. Level sets of \(\phi\) follow the boundary. This is simple and robust for many shapes, but medial-axis events create corners, branches, and disappearing loops.

6.9 Density as coverage, not merely spacing

Row spacing is only a proxy for what the viewer sees. A more general model treats every thread segment as a narrow ribbon or capsule and accumulates coverage:

where \(s_j\) is a thread segment, \(r_j\) is an effective thread radius, \(a_j\) accounts for layer or color, and \(K\) is a compact or Gaussian kernel.

A coverage loss is

This model naturally handles curved paths, variable thread thickness, overlaps, and intentional open texture. It is more computationally expensive than checking row spacing, so it is often used for preview and refinement rather than initial generation.

6.10 Direction error

For unoriented directions, the angular error should ignore sign:

where \(t(x)\) is the local stitch tangent. An integrated metric is

Using \(1-t\cdot d\) would incorrectly penalize a path whose tangent is reversed but visually equivalent.

From continuous paths to needle penetrations

A continuous curve is not yet embroidery. The machine needs a finite sequence of positions, and every new point creates both a visible thread segment and a needle penetration.

7.1 The sampling problem

Let a path be parameterized by arc length:

Choose positions

and emit

A basic feasibility condition is

In practice, both limits have exceptions. Deliberate tie stitches may be shorter than the preferred minimum. Long satin spans may be allowed on one setup and unsafe on another. Store these as typed constraints with reasons, not as one unexplained global constant.

A useful target interval can depend on local state:

7.2 Adaptive resampling

A robust sampler can proceed as follows:

1. flatten or evaluate the source curve with a geometric error bound;
2. build cumulative arc length;
3. place provisional points at the target spacing;
4. insert mandatory points at corners, extrema, crossings, and entry or exit constraints;
5. subdivide segments that exceed maximum length or chord error;
6. merge accidental short segments when doing so preserves intent;
7. quantize only in the target-lowering pass;
8. validate again after quantization.

The order matters. Merging before preserving a sharp corner can round it away. Quantizing before curvature-aware subdivision can create unstable decisions near grid boundaries.

7.3 Turning angle

For consecutive displacement vectors

the turning angle is

A sharp reversal with tiny adjacent segments can create a dense knot of penetrations. A turn penalty might be

where \(\psi\) grows for sharp turns combined with short lengths.

Turning is not always undesirable. A crisp corner may require a deliberate penetration at the vertex. The validator should distinguish an intentional corner from accidental zigzag noise.

7.4 Corners

Common corner strategies include:

• point corner: one penetration at the exact corner;
• mitered corner: extend directional structure toward an intersection;
• capped corner: terminate one section and begin another;
• fanned satin: distribute several stitches around the outer rail;
• split corner: divide the region into separate objects.

A compiler should make the corner policy explicit in the primitive IR. Otherwise later resampling may unknowingly erase it.

7.5 Duplicate and near-duplicate points

A zero-length command may be:

• an accidental duplicate;
• a deliberate state marker;
• part of a lock sequence;
• an artifact of target quantization.

Do not delete all duplicates indiscriminately. Normalize commands using both geometry and operation semantics.

7.6 Penetration density

Thread coverage and needle penetration density are different quantities. Define a local penetration-density estimate with a kernel:

A hotspot penalty is

This detects needle clusters at corners, row endpoints, narrow necks, tie sequences, and overlapping layers. A design can have reasonable row spacing and still have dangerous penetration hotspots.

7.7 Path simplification

Polyline simplification can reduce unnecessary stitches, but ordinary visual simplification criteria are incomplete. A stitch-aware simplifier should preserve:

• corners and cusps;
• layer junctions;
• entry and exit points;
• intended lock sequences;
• maximum stitch length;
• direction-field error bounds;
• coverage near boundaries;
• command boundaries.

A useful objective is

subject to machine constraints, where \(d_H\) is a geometric deviation measure such as Hausdorff distance.

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.