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.
Accuracy and Performance
Flattening
cl-sdf measures distances to straight lines. Curves are first flattened: each quadratic or cubic is halved by de Casteljau's construction until its control points lie within the tolerance of the chord from its start to its end. A Bézier curve lies inside the hull of its control points, so the whole piece is then within the tolerance of its chord, including curves that loop or double back on themselves.
| Used by | Default tolerance |
|---|---|
generate-sdf, generate-msdf, generate-mtsdf |
1/32 of the smaller texel dimension |
make-shape, inside-p, signed-distance, unsigned-distance, flatten-contours |
0.01 shape units |
At the default spread of 4 texels, an 8-bit sample steps every 8/255 of a texel, about 0.031. The generators' default of 1/32 texel, 0.03125, keeps the flattening error below one step, whatever units the outline uses. A finer tolerance makes no visible difference in an 8-bit texture, and costs time. Point queries have no texel to scale by, so their 0.01 is in shape units; choose your own for outlines much larger or smaller than one unit.
A circle of radius 1 flattens to 32 lines at 0.01, and to 376 at 0.0001.
What is exact and what is not
- True distances (SDF and MTSDF alpha) are exact distances to the flattened boundary, so within the tolerance of the distance to the curves.
- Fill is decided by winding numbers or crossing counts on the flattened outline, so it is exact for points further than the tolerance from an edge.
- Bounds are control-point bounds: they always contain the curve, but may be larger than its ink, by up to the distance of a control point from the curve.
- The MSDF channels are exact perpendicular distances to the flattened edges, extended past each edge's ends along its last line. msdfgen extends along the curve's tangent; the difference is a few hundredths of a texel at the default tolerance.
Precision
Geometry is computed in double-floats. When resolving the filled boundary, cl-sdf treats points closer than 64 × double-float-epsilon times the largest coordinate's magnitude, about 1.4 × 10⁻¹⁴ of it, as the same point. That merges vertices that are meant to coincide but were computed by different routes. It also means that features smaller than that, relative to the outline's distance from the origin, cannot be told apart: an outline a millionth of a unit across, placed a hundred million units from the origin, is beyond it. Translate such outlines near the origin first.
Samples are stored as single-floats, about seven significant digits, which is far finer than an 8-bit texture. So that every distance fits them, coordinates, bounds, padding and query points are limited to ±1e36, and spreads and tolerances to 1e36; see Errors.
Thin features
A distance field cannot represent anything thinner than about a texel, such as a hairline serif or two edges closer than a texel. Between two texel centers, interpolation assumes the distance changes linearly, and a feature narrower than that is missed or merged. The cure is more texels per unit, or a field drawn smaller. Error correction removes many of the stray artifacts such features cause in an MSDF, but cannot restore the feature.
Compared with msdfgen
cl-sdf follows msdfgen's method: its edge coloring, its perpendicular distance selection with endpoint extensions and alignment tie-breaking, and its default error correction. The test suite compares cl-sdf with msdfgen's own output, at revision 1c106ed8, kept as Lisp data:
| Fixture | What | Agreement required |
|---|---|---|
| 256 sample points | Raw RGBA distances of polygons (square, triangles, a concave L) with fixed colors: edge interiors, endpoints, ties, mixed signs, extension domains, concave corners. | 2 × 10⁻⁶ |
| Whole MTSDF fields | 16 by 16, uncorrected, of curved shapes (a quadratic teardrop and lens, a line-and-cubic D, a cubic circle with a triangular hole), with msdfgen's coloring. | Within the flattening error |
| Whole corrected MSDF fields | Four straight-edged stars, two twisted, with msdfgen's default error correction. | 10⁻⁴ of a texel |
When the error correction was ported, it was also run beside msdfgen on 18 real glyphs from DejaVu Sans and URW Bookman, and corrected exactly the same texels.
Matching msdfgen is not the only check. Separate tests compare fields with analytic distances, with independent Bézier sampling, with an oversampled true distance after reconstructing the field as a shader does, and under reversal, translation, scaling and rotation. See Development.
Expected differences
These are deliberate, and not bugs:
- Curves are flattened. Fields agree with msdfgen's to within the flattening tolerance.
- Endpoint extensions follow the last line, not the tangent. Past a curve's end, the RGB channels extend the curve's last flattened line rather than its exact tangent: a few hundredths of a texel.
- Overlapping contours are merged first. cl-sdf resolves the union's boundary before measuring, so internal edges never affect the field. msdfgen combines distances contour by contour, which can differ where contours overlap.
- Exact ties can resolve differently. At texels exactly symmetric between two edges, msdfgen's choice depends on single-float rounding noise, and cl-sdf's on edge order.
- Coloring of resolved boundaries. Where overlaps create new corners, cl-sdf recolors the merged boundary; msdfgen colors each input contour.
Performance
Measured on one core of an AMD Ryzen 9 9950X3D with SBCL 2.6.4, glyphs in ems with :padding 1/8 :spread 1/8, milliseconds per field:
| Glyph | Segments | Size | SDF | MSDF without correction | MSDF | MTSDF |
|---|---|---|---|---|---|---|
| DejaVu Sans A | 11 | 32² | 0.3 | 0.4 | 1.2 | 1.2 |
| 64² | 0.7 | 1.5 | 4.0 | 4.3 | ||
| 128² | 2.5 | 5.8 | 15 | 17 | ||
| DejaVu Sans g | 29 | 32² | 0.9 | 3.0 | 3.8 | 3.9 |
| 64² | 2.4 | 12 | 14 | 15 | ||
| 128² | 6.3 | 48 | 57 | 59 | ||
| DejaVu Sans @ | 53 | 32² | 1.4 | 4.7 | 5.5 | 5.5 |
| 128² | 7.3 | 74 | 84 | 86 | ||
| URW Bookman Light g (cubics) | 33 | 32² | 1.3 | 4.5 | 5.4 | 5.4 |
| 128² | 8.0 | 72 | 83 | 84 |
- Time grows with the number of texels and of segments. The true distance and the inside test look only at nearby segments, through a uniform grid. The MSDF channels compare every segment, as msdfgen does, because an endpoint extension can win far from its corner.
- An MTSDF costs the same as an MSDF: the MSDF already computes the true distance, for its sign checks.
- Error correction adds from a sixth to well over the channels' own cost: most, in proportion, for simple glyphs, whose channels are cheap.
- A page of new text, a few hundred glyphs, takes on the order of a second on one core, so generate on worker threads; see Concepts.
Point queries, on the same glyphs:
| Operation | Time |
|---|---|
make-shape |
0.03 to 0.3 ms |
inside-p on a shape |
0.02 to 0.04 µs |
signed-distance, unsigned-distance on a shape |
0.02 to 0.3 µs |
signed-distance on contours |
the same as make-shape |
Generation allocates the result, working arrays of about 40 bytes per texel for an MSDF, and the indexed geometry. A point query on a prepared shape allocates only the double-float it returns: inside-p and field-ref nothing, signed-distance and unsigned-distance 16 bytes.
Memory
A field's samples take 4 bytes per channel per texel as single-floats: 16 KiB for a 32 by 32 MTSDF, 64 KiB at 64 by 64. field-octets is a quarter of that. Keep the octets for upload and drop the field, unless you need the bounds and spread, which are four numbers to keep alongside.