This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

How It Works

This page follows a call to generate-mtsdf through the source, for maintainers and for anyone who wants to know why a field looks the way it does. Nothing here is needed to use cl-sdf.

File	Holds
src/package.lisp	The package and its exports.
src/conditions.lisp	The domain types, the conditions, and contour validation.
src/geometry.lisp	Bounds and curve flattening.
src/grid.lisp	A uniform grid over boxes, and the macros that walk it.
src/edge-table.lisp	Flattened lines packed into typed arrays, and the per-sample distance kernels.
src/distance.lisp	shape, the point queries, encode-distance and decode-distance.
src/boundary.lisp	Resolving the filled region's boundary.
src/coloring.lisp	colored-edge and color-edges.
src/error-correction.lisp	The port of msdfgen's MSDF error correction.
src/field.lisp	field and its accessors.
src/generate.lisp	The three generators.

1. Arguments

Every public function checks its arguments first: options and points by their declared types, which SBCL checks on entry, and contours with a walk that names the first bad contour and segment. Coordinates and lengths must lie within ±1e36, so that no distance later exceeds the single-float range. The generators also accept contours of colored edges: then the caller's colors are kept for step 6, and their segments are the outline for every other step.

The generators then fix the mapping. The bounds are the given :bounds, or the contours' control-point box widened by half a unit along an axis where it has no extent, and padded. The spread is :spread, or :px-spread times the larger texel dimension. The flattening tolerance is :flatten-tolerance, or 1/32 of the smaller texel dimension.

2. Flattening

Each curve is split in half by de Casteljau's construction until its control points are within the tolerance of the chord, at most 24 times deep. Each flattened line is a list (x0 y0 x1 y1) of double-floats. For the MSDF, each line also carries the list of channels of the edge it came from.

3. The filled boundary

prepare-boundary turns flattened contours, which may overlap, cross themselves and run either way, into the closed boundary of the region the fill rule fills, with the fill on the left of every line.

1. Closure. The epsilon for all comparisons is 64 × double-float-epsilon × the largest coordinate's magnitude. Each contour must close within it, or open-contour-error is signalled. Lines no longer than epsilon are dropped.
2. Splitting. Every line is split at its intersections with every other line, and at the ends of collinear overlaps. Candidates come from a grid of the lines' boxes, ⌈√n⌉ cells a side, so only lines with overlapping boxes are compared.
3. Classification. For each piece, two points are taken, one on each side of its middle, at a clearance smaller than both a quarter of the piece's length and a quarter of the distance to any other line. The fill rule, applied to all the input lines, decides whether each point is inside. A piece is kept only if exactly one side is inside, and it is turned so that the inside is on its left. Coincident pieces are classified together, since both test points see both lines, and duplicates are kept once.
4. Joining. Pieces are joined end to start into closed loops. Where several pieces start at the same point, the walk takes the largest left turn, which keeps to the same filled face, so shapes that touch at a vertex stay separate loops. Vertices are made numerically identical where pieces meet, which the MSDF's tie-breaking relies on.

It also reports whether the topology changed: whether any line was split, or a contour lost some but not all of its lines. Automatic coloring is then redone on the result.

4. Edge tables and the grid

make-edge-table packs lines into typed double-float arrays: ends, length, unit direction, the directions of the previous and next line in the contour, and a 3-bit channel mask. Two grids index them:

• Bands: one column and as many rows as lines, for inside tests. Only lines whose y range contains the point's y can cross the horizontal ray from it.
• Cells: ⌈√n⌉ by ⌈√n⌉, for nearest-line searches, the true distance and point queries. A search visits rings of cells outward from the point's cell, skips cells farther than the best distance so far, and stops when every unvisited cell is farther. The result does not depend on visiting order.

The per-sample kernels run on these arrays without allocating.

5. The true distance

At each texel center: the distance to the nearest boundary line, computed as a squared distance and rooted once, signed by an inside test on the boundary. The inside test is a winding number for :nonzero and a crossing count for :even-odd, both along a horizontal ray. An SDF stores this; an MTSDF stores it in alpha.

6. Coloring

Unless the caller passed colored edges, automatic coloring runs on the input contours, before flattening, so that a curve keeps one color and corners are found from exact tangents. See Edge Coloring for the rules. The colored contours are flattened with their channels, and their boundary resolved as in step 3. If the topology changed, the resolved boundary is colored again, as lines, so that corners made by intersections get a color change.

The alpha channel is computed from the uncolored segments' own flattening, so splitting a curve in thirds for coloring cannot change it. Colored edges given by the caller are used as they are, even if overlaps changed the topology.

7. The channel distances

table-perpendicular-distances is msdfgen's perpendicular distance selector, over lines. For each channel:

1. The nearest line of that channel wins, by distance. At a shared endpoint two lines are equally near; the tie goes to the line the sample lies most nearly square to (msdfgen's alignment test), then to the first line in order.
2. Its perpendicular distance, the signed distance to the infinite line through it, is the candidate. Inside the line's span, that is just the distance; beyond an end, it extends the line past its end, which is what keeps corners sharp.
3. Other lines' extensions count too, but only within their endpoint's wedge: past the end, and beyond the bisector with the neighboring line. Unrestricted extensions would create false edges far from corners. Among those, the nearest of the right sign is a second candidate.
4. The channel takes whichever candidate is nearer. A channel with no lines at all takes the true distance.

Unlike the true distance, this pass visits every line, in table order, as msdfgen does, and table order settles the ties. An endpoint extension can win far from its corner, so a grid search bounded by how far extensions reach still visited most of a glyph's lines at sharp corners, and walking the cells cost more than it saved.

8. Clash fix

If the median of the three channels has a different sign from the true distance, the texel would be drawn on the wrong side of the edge. All three channels are then set to the true distance. Mixed signs among the channels themselves are allowed: that is how a corner is encoded.

9. Error correction

The channels, rounded to single-floats as they will be stored, go through the port of msdfgen's error correction. Its reference distance for the final check is the single-channel perpendicular distance of all colored lines together, as one channel would see them, without the clash fix. See Error Correction.

10. Encoding

Each distance is encoded with the spread, 0.5 + d / (2 × spread) clamped, unless :normalize nil, and stored as a single-float in a row-major array, row zero where :y-axis puts it.

Point queries

make-shape does steps 2 to 4 once, and keeps two edge tables: the outline, every flattened input line, used by inside-p and unsigned-distance; and the boundary, from step 3, used by signed-distance. With contours instead of a shape, inside-p and unsigned-distance build only the outline table, inside-p after checking that the contours close, and signed-distance makes a whole shape.

signed-distance computes the unsigned distance inline, so that the only double-float a query on a shape allocates is its result.