Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

ArcAccurate, an accurate arc #164

Closed
jdaw1 opened this issue Jul 22, 2022 · 2 comments
Closed

ArcAccurate, an accurate arc #164

jdaw1 opened this issue Jul 22, 2022 · 2 comments

Comments

@jdaw1
Copy link
Owner

jdaw1 commented Jul 22, 2022

On comp.lang.postscript is a discussion ArcPrecise, an accurate arc. Since that thread was created the new function has been renamed to ArcAccurate. There follows an updated version of the text of the first post.


The PostScript command arc can draw circles, and part circles. Adobe Distiller draws angles ≤90° as a single Bézier cubic.

A Bézier cubic has eight parameters, curveto receiving the two from the currentpoint, and six from the stack. An arc must go through the correct endpoints, using four parameters. At the endpoints the direction of travel must be tangent to the circle, so each end absorbs another parameter. And, by symmetry, at the two ends the speeds of departure must be the same. ⟹ Only one parameter remains to be chosen, being the speed of departure from the endpoints.

For a 90° part of a unit circle, Adobe uses a speed of 0.552. Mathematica shows that the worst error happens at t ≈ 0.18864 (and at one minus this), an angle ≈ 17.39° (and 90° minus this) where the radius is too large by about 212 parts per million. At t = ½, angle = 45°, the radius is too small by −151 parts per million. These values are confirmed by testing with flattenpathpathforall.

For a circle of radius 540pt = 7½″ = 190.5mm, plausible on A4 or 8½″×11″, the error is as large as 0.1145pt.

Typically, a ≈0.04mm error doesn’t matter: the eye would not perceive it midst an empty page. But if a circle is being drawn with arc, and things placed at its edge (locations computed with sin and cos), as my software does, then these things could be falsely apart by 0.11pt. That isn’t a disaster, but could be a multi-pixel visible imperfection. And an unnecessary imperfection.

This is solved by new PostScript routines ArcAccurate, and à la arcn, ArcAccurateN.

http://www.jdawiseman.com/2022/ArcPrecise.ps
http://www.jdawiseman.com/2022/ArcPrecise.pdf
http://www.jdawiseman.com/2022/ArcPrecise_bitmap_17.png (Adobe error of +212 ppm)
http://www.jdawiseman.com/2022/ArcPrecise_bitmap_73.png (Adobe error of +212 ppm)
http://www.jdawiseman.com/2022/ArcPrecise_bitmap_45.png (Adobe error of −151 ppm)
http://www.jdawiseman.com/2022/ArcPrecise_bitmap_06.png (worst ArcAccurate error, +0.37 ppm)

Output is shown in the PDF and the .png extracts from it. The grey line, width 0.36pt, is a precise circle, made of tiny linetos only ⅛° apart. Underneath is a red line, width 0.60pt, drawn with Adobe’s arc, the red diagonals touching its worst radii. On top is a blue line, width 0.12pt, drawn with ArcAccurate, short blue lines touching its worst points. The widths are chosen such that, where all are neatly aligned, each stripe of colour has width 0.12pt. Throughout, the grey and the blue are neatly aligned; but the red drifts out by almost 0.12pt, then in, then back out.

Assume curve of angle Θ. A speed of Tan[Θ/4]·4/3 has the radius precisely correct at the midpoint, t = ½, angle = Θ/2. The radius is never too small, and is maximal at t = ½ − ⅙√3 ≈ 0.2113. For Θ small and in radians, the maximal radius happens near angle (½ − ⅙√3)·Θ ≈ 0.2113 Θ, where the radius is too big by ≈ 2⁻¹¹·3⁻³·Θ⁶ = (Θ^6)/55296.

(If Θ = 90°, then the speed is Tan[22½°]·(1⅓) = (√2 − 1)·4/3 ≈ 0.55228474983, which is only 1-part-in-1939 bigger than Adobe’s fixed value of 0.552. If Θ < 90° then Adobe seems to use a value within ± a few machine precisions of Tan[Θ]·4/3.)

ArcAccurate chooses curves of no more than 30°. For a 30° curve the actual worst error is 0.372662 parts per million; this approximation says π⁶/2579890176 − 1 ≈ 0.372647 ppm. So it is a good approximation to the error.

For a 540pt radius, ArcAccurate has a peak error of 0.00020pt. If the smallest error we care about is 0.01pt, half a pixel at 3600d.p.i., that doesn’t happen with radius ≤ 9.46 metres ≈ 31 feet. This is bigger than the PDF standard’s maximum page size of only 200″ = 16⅔ feet = 5.08 metres. Further, PostScript’s arithmetic is single-precision, with a 23-bit mantissa, which is only slightly more accurate than 0.37 ppm. So 30° curves are sufficiently small.

There is also a little neatness in the choice of curve-end angles. If every multiple of 90° is a curve endpoint, then pathbbox returns the correct minimal box. So the angle choosing algorithm works as follows. It computes the next multiple of 90°, If that’s ≤30° away, done in one curve; else if ≤60° away, done in two equal-angle curves; otherwise split into three equal-angle curves. Then 30° curves until the final multiple of 90°; the final section, like the first, in at most three equal-angle curves each ≤30°. This means that: curves are all ≤30°; for a non-rotated frame pathbbox works optimally; and the number of curves is at most 1 + ⌈|ang₂ − ang₁| ÷ 30°⌉.

The built-in routines start with a line from a currentpoint, if there is one. This can be annoying. Consider an annulus: there’s a line between the inner and outer circles, avoiding which requires a manual moveto. But it can be useful, it making a shape such as a rectangle with rounded corners. So ArcAccurate and ArcAccurateN have an extra parameter, taking three possible values:
/larc-style lineto (if there is a current point; if not, moveto);
/mmoveto, especially useful if previous command was closepath;
/n ⟹ nothing, presumably because the currentpoint is already the start of the curve.

Those wishing to replace the old arc with this more accurate version can simply set

/arc {/l ArcPrecise} def
jdaw1 added a commit that referenced this issue Jul 24, 2022
Those calls of arc for which accuracy even slightly important replaced with calls of ArcAccurate. (So, e.g., not in fashioning droplets.) Closes issue #164. Closes https://groups.google.com/g/comp.lang.postscript/c/B23RW2QpIjU
@jdaw1 jdaw1 closed this as completed Jul 24, 2022
@jdaw1
Copy link
Owner Author

jdaw1 commented Jul 24, 2022

For the latest version of ArcAccurate, look in github.com/jdaw1/placemat/blob/main/PostScript/placemat.ps, and search for “ArcAccurateBoth” or “B23RW2QpIjU”.

@jdaw1
Copy link
Owner Author

jdaw1 commented Jan 22, 2024

Also see StackOverflow PostScript circles: how accurate, how improve?, asked and answered on Sunday 21 January 2024.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant