Shapes and Curves

Curves

A shape is given as a vector of reals, six for each quadratic Bézier curve:

X0 Y0  CX CY  X1 Y1
start  control  end

in ems, with y up. Any vector of reals works: a simple-vector, a vector of single-floats such as cl-textrender:outline-quadratics returns, a vector of rationals. The type cl-slug:curves names it.

The curves form closed contours: each curve starts where the one before it ended, and each contour ends where it started. Contours follow one another in the vector. cl-slug does not check that contours close, but the fill is only right for closed ones.

;; A unit square, counterclockwise: four straight curves.
#(0 0  1/2 0  1 0
  1 0  1 1/2  1 1
  1 1  1/2 1  0 1
  0 1  0 1/2  0 0)

Straight lines

A straight line is a curve whose control point lies on it. Give the control point anywhere on the segment: at its middle, as cl-textrender:outline-quadratics packs lines, or at its end.

cl-slug moves the control point of every straight curve to its end point, the form the Slug shaders solve most exactly. A control point counts as on the line if it lies between the ends, within a hundred-thousandth of the line's length of it.

Curves left out

A curve whose three points are the same after rounding, which has no length, is left out. A shape whose curves are all left out, or which has none, is empty: shape-empty-p is true, it takes no texels, and a renderer draws nothing for it. A space is one.

Rounding

The curve texture holds 16-bit floats, so every coordinate is rounded to the nearest one when the shape is added, ties to even, as GPUs convert. Near 1 they are about a two-thousandth of an em apart; near 0.1, a sixteen-thousandth. The bounds a shape reports are the rounded ones:

(cl-slug:shape-xmin (cl-slug:store-add store #(0.1 0.1 0.5 0.1 0.9 0.1 ...)))
;; => 0.099975586

The bands are built from the rounded coordinates, so the shader finds every curve in the bands the builder put it in. A coordinate beyond 65504 signals a slug-error: give shapes in ems, not pixels or font units. half-float-bits and half-float-value convert by hand.

Fill rules

Which parts of a shape are inside is decided by how many times its contours wind around them, counting counterclockwise turns as +1 and clockwise as -1:

Fill rule	Inside where the winding number is	Used by
:nonzero, the default	anything but 0	Fonts, most vector icons
:even-odd	odd	Some SVG paths

So with :nonzero, a hole runs the other way from the contour around it:

;; A ring: an outer circle counterclockwise, an inner one clockwise.
(cl-slug:store-add store (concatenate 'vector outer-ccw inner-cw))

With :even-odd, a hole may run either way, and where two contours overlap is a hole too:

(cl-slug:store-add store curves :fill-rule :even-odd)

The shader takes coverage's absolute value, so a whole shape may run either way: TrueType glyphs run clockwise and CFF glyphs counterclockwise, and both fill.

Glyphs from a font

cl-textrender gives a glyph's outline. Make the font at size 1, so the outline is in ems, and ask for quadratics, which turns a CFF font's cubic curves into quadratics:

(cl-textrender:with-font (font "/usr/share/fonts/truetype/dejavu/DejaVuSans.ttf" :size 1)
  (let ((glyph (cl-textrender:font-glyph-id font #\A)))
    (cl-slug:store-find-or-add
     *store* (list font glyph)
     (lambda ()
       (cl-textrender:outline-quadratics
        (cl-textrender:glyph-outline font glyph :quadratic t))))))
;; => #<CL-SLUG:SHAPE 11 curves, 7 by 3 bands {...}>

With a font of another size, divide the coordinates by the size:

(let ((curves (cl-textrender:outline-quadratics
               (cl-textrender:glyph-outline font glyph :quadratic t)))
      (size (float (cl-textrender:font-size font) 1.0)))
  (map-into curves (lambda (value) (/ value size)) curves))

Key glyphs by font and glyph ID, as above. A renderer that looks glyphs up every frame should keep its own table from font and ID to shape: store-find-or-add is cheap, but a fresh key list allocates. Pyssel keeps a hash table per font, by glyph ID.

Vector icons

An icon is a shape like a glyph: quadratic curves in ems. Convert an SVG path's lines and quadratic curves directly; approximate its cubic curves and arcs with quadratics, as cl-textrender does for CFF fonts, within a small tolerance such as a thousandth of an em. Use :even-odd where the SVG says fill-rule="evenodd". Scale the icon's view box to about an em.

How the bands are chosen

For each direction, cl-slug tries every number of bands from 1 to 32, and no more than the shape has curves, and keeps the one whose fullest band holds the fewest curves; the fewest bands among equals. A curve is in a band if its control points reach into it, widened by the store's epsilon, 1/1024 of an em by default. A horizontal line is in no horizontal band and a vertical line in no vertical band, since a ray along them crosses nothing.

Bands of the same curves share one list in the band texture. A square has one band each way; the glyph "A" of DejaVu Sans, 7 vertical bands and 3 horizontal.

Limits

• A band holds at most 4096 curves, the width of a row: a shape with more curves crossing one band signals a slug-error. Split it into several shapes.
• A shape's band data spans at most 65536 texels of the band texture.
• A run of connected curves longer than a row is split, which costs one texel.

See Errors and Limits.