How approximate {X[z],Y[z]} functions as Bézier cubic

Question

A user has smooth mathematical functions X[z] and Y[z] which define a smooth path over a range of z. My use case is that these functions define an Archimedes spiral, but the question can be more general. The functions, or the range of z, might refer to other control parameters, known to your code, but yet known here. Most especially in PostScript, but perhaps more generally, how can such a path be best and simply approximated with a Bézier cubic?

Similar content to this was posted on comp.lang.postscript in February 2019. In late 2023 google announced that Google Groups would soon to cease providing write access to Usenet, and it seemed plausible that read access would later be lost. So I asked on StackExchange/Meta, copied to comp.lang.postscript, whether such questions should be ported across, and the nobody said not.

Answer 1

One way to make this path is to loop over small steps of z, and moveto lineto lineto … lineto. That’s inelegant, and can make a ‘heavy’ PDF, and if the curve must appear smooth even if very zoomed, so tiny steps of z, a very a heavy PDF. Ick!

Assume that the path is not complicated, in the sense that it could be plausibly shown as a single Bézier cubic. (If the curve is complicated, that might be fixable by breaking it into smaller pieces.) Given some optimisation effort, a good Bézier curve could perhaps be found.

But if generating the Bézier within PostScript (because the other control parameters are variables in PostScript), this heavy optimisation might not be possible, and happily, can be avoided.

A Bézier cubic has eight parameters, in PostScript two from the currentpoint, and six from the stack. Constraints:

• Go through endpoints (four parameters);
• At endpoints, tangent angles correct (two parameters); and
• At endpoints, curvatures correct (two parameters).

Written has been a function ApproximatingCurve that takes values, for both endpoints, of X[z] and Y[z], and their first and second derivatives. For many possible cases, these should be readily codeable.

Quartic polynomials are then solved to deduce the end-point speeds, and ApproximatingCurve leaves on the stack the middle two control points of the cubic Bézier. This Bézier curve goes through the end points, with matching tangents, and matching local curvatures.

Examples output: .pdf, which was distilled from .ps. The latest version of the function is in github.com/jdaw1/placemat/blob/main/PostScript/placemat.ps (search for “/ApproximatingCurve”).

In the output the green line is the correct moveto lineto … lineto mathematical curve; the thin black is the Bézier cubic approximation. For all examples except the spirals, the black line is a single cubic Bézier; for the spirals there is one cubic Bézier per 60° piece.

In many of the examples, the Bézier is a very close approximation to the desired curve. In a few, it’s awful.

Let’s discuss one of these examples in more detail: the part circle (which has an even better answer in PostScript circles: how accurate, how improve?). If drawing an arc in PostScript with the operators arc or arcn, these render a 90° unit-radius arc as a single Bézier, with a ‘speed’ (distance from end control points to adjacent inner control points) of 0.552 (which isn’t quite identical to the limit of the speeds as the angle tends to 90°, so has likely been coded as a special case). This speed of 0.552 results in an error in the radius between −0.0151% and +0.0212%. Not bad. ApproximatingCurve chooses a speed of ≈0.54858, being (√7 − 1)/3, which results in an error in the radius between zero and −0.196% (one part in 509.5). Not bad, but worst error is about 9× worse than the Adobe’s optimised special case. Of course, a curve that spans less than 90° has a less-bad worst error, the error dropping slightly better than sixth power of the angle spanned. E.g., a 45° piece has a worst error in the radius of −0.0029%, one part in 34253.8, better than the 90° error by a factor of about 67.2.

These errors are errors in the cubic Bézier. But the Bézier curve itself is not perfectly rendered to screen or page: errors come from the flatness coefficient used in de Casteljau’s algorithm; and from physical imperfections such as the speed of the rollers. Given these, for an Archimedes spiral it surely suffices to choose a 60° piece, the Bézier curve of which has a worst error of about one part in 6012.8.

Finally, this algorithm — preserving curvature — is not scale invariant if the X and Y scalings differ. But the game isn’t to minimise anything like ∫(Y[X]−YY[X])²∂X; instead, the aim is to make a Bézier curve which ‘looks like’ the actual function. And that desideratum is not scale invariant: things look different at different aspect ratios. So this non-invariance is a ‘feature’ rather than a ‘bug’.

Also see How does 'arc' work?, Nov 2013, on comp.lang.postscript.