Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.

Dismiss

137 views

Skip to first unread message

Feb 2, 2019, 7:10:45 PM2/2/19

to

A user has mathematical functions X[z] and Y[z] that define a smooth path over a range of z. The functions, or the range of z, might refer to other control parameters, known to your PostScript, but not shown here.

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 shown as a single cubic Bézier. (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 the PostScript (because the other control parameters are variables in PostScript), this heavy optimisation might not be possible.

So I have written a function that achieves something close to this. ApproximatingCurve takes some knowledge about what is happening at the ends of the curve, and makes a cubic Bézier from these numbers. It takes the following.

• The _s_tart and _e_nd points (Xs, Ys, Xe, Ye), which will be the start and end points of the Bézier.

• ∂X[z]/∂z and ∂Y[z]/∂z, at the start and end points (dXs, dYs, dXe, dYe), which specify the tangents.

• ∂²X[z]/∂z² and ∂²Y[z]/∂z², at the start and end points (ddXs, ddYs, ddXe, ddYe), which specify the curvatures.

Quartic polynomials are solved to deduce the end-point speeds, and the 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 is in

• http://www.jdawiseman.com/2019/20190200_ApproximatingCurve_examples.pdf

which was distilled from

• http://www.jdawiseman.com/2019/20190200_ApproximatingCurve_examples.ps

These files might be updated during February 2019, but will not be updated after that. Latest versions of these routines can be found in my big PostScript program at http://www.jdawiseman.com/papers/placemat/placemat.ps.

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. Of course, if drawing an arc in PostScript, use the operators arc or arcn, which 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.000151% and +0.000212%. Not bad. ApproximatingCurve chooses a speed of ≈0.54858, being ⅓(√7−1), which results in an error in the radius between zero and −0.00196% (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.000029%, one part in 34253.8, better than the 90° error by a factor of about 67.2. For those who care, with the angle small and in radians the worst error is of the order −angle⁶÷8192.

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, 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 https://groups.google.com/forum/#!topic/comp.lang.postscript/YiuM6lj5ngY

Comments, improvements, bug reports — all welcomed.

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 shown as a single cubic Bézier. (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 the PostScript (because the other control parameters are variables in PostScript), this heavy optimisation might not be possible.

So I have written a function that achieves something close to this. ApproximatingCurve takes some knowledge about what is happening at the ends of the curve, and makes a cubic Bézier from these numbers. It takes the following.

• The _s_tart and _e_nd points (Xs, Ys, Xe, Ye), which will be the start and end points of the Bézier.

• ∂X[z]/∂z and ∂Y[z]/∂z, at the start and end points (dXs, dYs, dXe, dYe), which specify the tangents.

• ∂²X[z]/∂z² and ∂²Y[z]/∂z², at the start and end points (ddXs, ddYs, ddXe, ddYe), which specify the curvatures.

Quartic polynomials are solved to deduce the end-point speeds, and the 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 is in

• http://www.jdawiseman.com/2019/20190200_ApproximatingCurve_examples.pdf

which was distilled from

• http://www.jdawiseman.com/2019/20190200_ApproximatingCurve_examples.ps

These files might be updated during February 2019, but will not be updated after that. Latest versions of these routines can be found in my big PostScript program at http://www.jdawiseman.com/papers/placemat/placemat.ps.

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. Of course, if drawing an arc in PostScript, use the operators arc or arcn, which 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.000151% and +0.000212%. Not bad. ApproximatingCurve chooses a speed of ≈0.54858, being ⅓(√7−1), which results in an error in the radius between zero and −0.00196% (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.000029%, one part in 34253.8, better than the 90° error by a factor of about 67.2. For those who care, with the angle small and in radians the worst error is of the order −angle⁶÷8192.

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, 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 https://groups.google.com/forum/#!topic/comp.lang.postscript/YiuM6lj5ngY

Comments, improvements, bug reports — all welcomed.

Feb 23, 2019, 6:31:05 AM2/23/19

to

Oops, typos. I added the “%” sign without multiplying by 100.

• “−0.000151% and +0.000212%” ➝ “−0.0151% and +0.0212%”.

• “−0.00196%” ➝ “−0.196%”.

• “−0.000029%” ➝ “−0.0029%”.

Sorry.

However, the one-part-in’s are correct.

Also, a minor change to the software which might sometimes slightly improve accuracy of PolynomialRoots when the coefficients are large.

• “−0.000151% and +0.000212%” ➝ “−0.0151% and +0.0212%”.

• “−0.00196%” ➝ “−0.196%”.

• “−0.000029%” ➝ “−0.0029%”.

Sorry.

However, the one-part-in’s are correct.

Also, a minor change to the software which might sometimes slightly improve accuracy of PolynomialRoots when the coefficients are large.

Jul 15, 2023, 9:18:10 AM7/15/23

to

Nov 20, 2023, 1:46:13 PM11/20/23

to

This method, and this post, are mentioned in https://math.stackexchange.com/a/4810490/822964

Jan 22, 2024, 4:57:19 PMJan 22

to

This answer also at https://stackoverflow.com/questions/77862965/

0 new messages

Search

Clear search

Close search

Google apps

Main menu