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.
Contours and Fill Rules
The outline format
An outline is a list of contours. A contour is a list of segments. A segment is one of:
(:line x0 y0 x1 y1)
(:quadratic x0 y0 cx cy x1 y1) ; quadratic Bézier, one control point
(:cubic x0 y0 c1x c1y c2x c2y x1 y1) ; cubic Bézier, two control points
Every segment gives its start point explicitly. Coordinates are reals (integers, ratios, single or double floats) within ±1e36, the type sdf:coordinate, in shape units; cl-sdf computes in double-floats. Within that range every distance between points fits the single-floats a field stores, so larger coordinates are rejected with an invalid-contours-error that says to scale the outline down. This is the form of cl-textrender's outline-contours, so glyph outlines need no conversion.
The nesting matters: contours nest two levels deep, even for a single contour.
;; One contour, a unit square.
'(((:line 0 0 1 0) (:line 1 0 1 1) (:line 1 1 0 1) (:line 0 1 0 0)))
;; Two contours: a square with a square hole.
'(((:line 0 0 3 0) (:line 3 0 3 3) (:line 3 3 0 3) (:line 0 3 0 0))
((:line 1 1 1 2) (:line 1 2 2 2) (:line 2 2 2 1) (:line 2 1 1 1)))
The type sdf:segment matches one segment; sdf:rectangle matches (xmin ymin xmax ymax).
Closed contours
Field generation, make-shape, inside-p and signed-distance need a filled region, so their contours must be closed: each segment starts where the previous one ends, and the last ends where the first starts. The match must be exact, up to a few units in the last place of the coordinates' magnitude, so compute shared points once and reuse them rather than computing them twice. An open contour signals open-contour-error, which says where the gap is:
(sdf:make-shape '(((:line 0 0 1 0) (:line 1 0 1 1) (:line 1 1 0.5 1))))
;; Contour 0 is not closed: a segment ends at (0.5d0, 1.0d0) but the next starts at
;; (0.0d0, 0.0d0). Inside tests, signed distances and fields need closed contours, ...
;; Close the gap, for example with (:LINE 0.5d0 1.0d0 0.0d0 0.0d0), or use
;; UNSIGNED-DISTANCE for open paths.
The numbers are the exact double-floats cl-sdf compared, so the suggested segment, pasted in, closes the gap even when the coordinates were computed.
Segments of zero length, and curves whose points all coincide, are allowed; fields and signed distances ignore them. A contour with no segments is allowed and contributes nothing.
Orientation
Contours may run either way round, and different contours of one outline may disagree. cl-sdf works out which side of each edge is filled by testing the fill rule on both sides, so it never relies on winding direction. Reversing every contour of an outline gives the same SDF, and the same MTSDF alpha, bit for bit. The MSDF channels may be colored differently, since coloring starts from a different edge, but they draw the same shape.
Fill rules
:fill-rule decides which points are inside, from all contours together. Count how many times a ray from the point to infinity crosses the outline:
:nonzero, the default, adds +1 for each crossing of an edge that runs one way and −1 for the other. A point is inside when the sum is not zero. A hole must run the opposite way to the contour around it. TrueType and CFF glyphs are drawn for this rule.:even-oddcounts crossings. A point is inside when the count is odd. A contour inside another is a hole whatever its direction. SVG'sfill-rule="evenodd"is this rule.
A ring of two circles, both counterclockwise, is a disc under :nonzero and a ring under :even-odd; with the inner circle reversed, it is a ring under both:
;; CIRCLE-CONTOUR and REVERSE-CONTOUR are in Recipes.
(defparameter *same-way* (list (circle-contour 0 0 1) (circle-contour 0 0 0.5)))
(defparameter *opposite* (list (circle-contour 0 0 1)
(reverse-contour (circle-contour 0 0 0.5))))
(sdf:inside-p *same-way* 0 0) ; => T
(sdf:inside-p *same-way* 0 0 :fill-rule :even-odd) ; => NIL
(sdf:inside-p *opposite* 0 0) ; => NIL
(sdf:signed-distance *opposite* 0 0) ; => -0.4974786086415194d0
The center is half a unit from the hole's edge; the result is a little less because the circles are cubic approximations, flattened.
The generators, make-shape, inside-p and signed-distance take :fill-rule. A shape made with make-shape keeps the rule it was made with.
Overlaps and self-intersections
Contours may overlap one another and cross themselves. Before measuring signed distances, cl-sdf resolves the boundary of the filled region: it splits edges where they cross, drops every piece that has fill on both sides or on neither, merges edges that coincide, and keeps the rest. So:
- Two overlapping contours give the field of their union, without a seam where they overlap.
- A contour that does not change what is filled, such as a second copy of a contour under
:nonzero, is ignored. - A self-intersecting contour, such as a pentagram drawn in one stroke, gives the region its fill rule fills: a solid star under
:nonzero, a star with a pentagonal hole under:even-odd.
;; Two rectangles overlapping between x = 1 and x = 2.
(defparameter *two* (list (rectangle-contour 0 0 2 1) (rectangle-contour 1 0 3 1)))
(sdf:signed-distance *two* 1.25 0.5) ; => 0.5d0, to the top and bottom edges
(sdf:unsigned-distance *two* 1.25 0.5) ; => 0.25d0, to the edge at x = 1
unsigned-distance is the exception: it measures to every input segment, internal or not, and needs no closed contours. See Distance Queries.
This is a difference from msdfgen, which combines overlapping contours per contour rather than as one region. See Accuracy and Performance.
Open paths
An open path, such as a stroke's center line, has no inside. Only unsigned-distance accepts one, and it also accepts isolated points as zero-length segments; inside-p signals open-contour-error like the others:
(sdf:unsigned-distance '(((:line 0 0 1 0))) 0.5 1) ; => 1.0d0
(sdf:unsigned-distance '(((:line 0.5 0.5 0.5 0.5))) 0 0.5) ; => 0.5d0
Glyphs from a font
cl-textrender's glyph-outline returns a glyph's contours in this format, closed, in layout units of the font's size, y up from the glyph's origin. A font of size 1 gives outlines in ems:
(asdf:load-system :cl-textrender)
(defun glyph-contours (path char)
(textrender:with-font (font path :size 1)
(textrender:outline-contours
(textrender:glyph-outline font (textrender:font-glyph-id font char)))))
(defparameter *a* (glyph-contours "/usr/share/fonts/truetype/dejavu/DejaVuSans.ttf" #\A))
(mapcar #'length *a*) ; => (3 8), the counter and the outside
(sdf:bounds *a*) ; => (0.0078125d0 0.0d0 0.67578125d0 0.72900390625d0)
(sdf:generate-mtsdf *a* 32 32 :padding 0.125)
TrueType fonts give lines and quadratics, CFF fonts lines and cubics; cl-sdf takes both. Overlapping contours, which variable fonts often have, need no preparation.
For text, cl-textrender/sdf already does this per glyph, at a fixed number of texels per em, and packs the fields into an atlas; see cl-textrender's Distance Field Atlas page.
Geometry helpers
(sdf:bounds contours) ; => (xmin ymin xmax ymax)
(sdf:contour-bounds contour) ; => (xmin ymin xmax ymax), one contour
Both return double-floats, and all zeros for no points. The box contains every point including control points, so it always contains the curve, but may be larger than its ink. The generators use the same box when no :bounds is given.
(sdf:flatten-contours '(((:quadratic 0 0 1 2 2 0) (:line 2 0 0 0))) :tolerance 0.25)
;; => (((0.0d0 0.0d0 0.5d0 0.75d0) (0.5d0 0.75d0 1.0d0 1.0d0)
;; (1.0d0 1.0d0 1.5d0 0.75d0) (1.5d0 0.75d0 2.0d0 0.0d0)
;; (2.0d0 0.0d0 0.0d0 0.0d0)))
flatten-contours returns each contour as a list of lines (x0 y0 x1 y1), without the :line keyword. Curves are halved until each piece's control points lie within :tolerance (0.01 by default) of its chord, which keeps the whole piece within that distance. It is what cl-sdf does internally, exposed for drawing outlines, hit testing or debugging.
Validation
Every function that takes contours checks them first and signals invalid-contours-error, which is also a type-error, naming the contour and segment at fault:
(sdf:make-shape '(((:line 0 0 1 0) (:arc 1 0 0 0))))
;; CONTOURS contour 0 segment 1 is (:ARC 1 0 0 0): :ARC is not a segment kind.
;; CONTOURS is a list of contours, each a list of segments. A segment is
;; (:LINE x0 y0 x1 y1), (:QUADRATIC x0 y0 cx cy x1 y1) or
;; (:CUBIC x0 y0 c1x c1y c2x c2y x1 y1), all reals within ±1e36.
(sdf:make-shape '((:line 0 0 1 0)))
;; CONTOURS contour 0 is (:LINE 0 0 1 0): it is a single segment where a contour
;; was expected; wrap it in a list.
Errors lists every message.