jdaw1
jdaw1

Reputation: 251

PostScript circles: how accurate, how improve?

The PostScript command arc can draw circles, and part circles. Adobe Distiller draws angles ≤90° as a single Bézier cubic. How accurate is this; how can it be made more accurate?

Similar content to this was posted on comp.lang.postscript in July 2022. 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. This content is also at github.com/jdaw1/placemat/issues/164.

Upvotes: 1

Views: 137

Answers (1)

jdaw1
jdaw1

Reputation: 251

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 PostScript 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. Files: ArcAccurate.ps, ArcAccurate.pdf, Adobe error of +212 ppm, Adobe other error of +212 ppm, Adobe error of −151 ppm, worst ArcAccurate error, +0.37 ppm.

Output is shown in the PDF and the 30× .png extracts from it. The grey line, width 0.36pt, is an actual 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 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.

Observe that θ = 90° ⟹︎ speed is Tan[22½°]·4/3 = (√2 − 1)·4/3 ≈ 0.55228474983, which is only ≈+0.05% bigger than Adobe’s fixed value of 0.552.

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 build-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. So ArcAccurate and ArcAccurateN start have an extra parameter, one of three values:

  • /l ⟹︎ arc-style lineto;
  • /m ⟹︎ moveto, especially useful if previous command was closepath;
  • /n ⟹︎ nothing, presumably because the currentpoint is already the start of the curve.

So /arc {/l ArcAccurate} def replicates the current API, but is more accurate.

Upvotes: 1

Related Questions