Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.postscript > #3774 > unrolled thread

ArcPrecise, an accurate arc

Back to article view | Back to comp.lang.postscript

Contents

  ArcPrecise, an accurate arc jdaw1 <jdawiseman@gmail.com> - 2022-07-19 12:47 -0700
    Re: ArcPrecise, an accurate arc jdaw1 <jdawiseman@gmail.com> - 2022-07-20 11:25 -0700
      Re: ArcPrecise, an accurate arc David Newall <davidn@davidnewall.com> - 2022-07-21 18:29 +1000
      Re: ArcPrecise, an accurate arc John Reiser <vendor@BitWagon.com> - 2022-07-21 07:17 -0700
        Re: ArcPrecise, an accurate arc jdaw1 <jdawiseman@gmail.com> - 2022-07-21 12:02 -0700
        Re: ArcPrecise, an accurate arc luser droog <luser.droog@gmail.com> - 2022-07-21 14:31 -0700
          Re: ArcPrecise, an accurate arc jdaw1 <jdawiseman@gmail.com> - 2022-07-21 15:00 -0700
            Re: ArcPrecise, an accurate arc jdaw1 <jdawiseman@gmail.com> - 2022-07-21 15:24 -0700
              Re: ArcPrecise, an accurate arc jdaw1 <jdawiseman@gmail.com> - 2022-07-22 00:58 -0700
                Re: ArcPrecise, an accurate arc Phil Wakely <pwakely99@googlemail.com> - 2022-07-22 01:42 -0700
                  Re: ArcPrecise, an accurate arc Phil Wakely <pwakely99@googlemail.com> - 2022-07-22 01:52 -0700
                    Re: ArcAccurate, an accurate arc jdaw1 <jdawiseman@gmail.com> - 2022-07-22 14:03 -0700
                      Re: ArcAccurate, an accurate arc jdaw1 <jdawiseman@gmail.com> - 2022-07-24 09:02 -0700
    Re: ArcPrecise, an accurate arc jdaw1 <jdawiseman@gmail.com> - 2024-01-22 11:07 -0800

#3774 — ArcPrecise, an accurate arc

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 `flattenpath` … `pathforall`.

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 http://github.com/jdaw1/placemat/ 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 `ArcPrecise`, and à la `arcn`, `ArcPreciseN`.

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 ArcPrecise 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 `lineto`s 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 `ArcPrecise`, 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.

`ArcPrecise` 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, `ArcPrecise` 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 is annoying. Consider an annulus: there’s a line between the inner and outer circles, avoiding which requires a manual moveto. `ArcPrecise` and `ArcPreciseN` prevent this annoyance by starting, always, with a moveto, never a lineto. 

Comment welcomed.

[toc] | [next] | [standalone]

#3775

> The build-in routines start with a line from a currentpoint, if there is one. This is annoying. Consider an annulus: there’s a line between the inner and outer circles, avoiding which requires a manual moveto. `ArcPrecise` and `ArcPreciseN` prevent this annoyance by starting, always, with a moveto, never a lineto. 

I think this is an error. What if the user wants a rounded rectangle. That isn’t possible if `ArcPrecise` starts with a `moveto`. Perhaps there could be an extra parameter, code, usually being one of {moveto}, {lineto}, {pop pop}. Advice welcomed.

[toc] | [prev] | [next] | [standalone]

#3776

On 21/7/22 04:25, jdaw1 wrote:
>> The build-in routines start with a line from a currentpoint, if there is one. This is annoying. Consider an annulus: there’s a line between the inner and outer circles, avoiding which requires a manual moveto. `ArcPrecise` and `ArcPreciseN` prevent this annoyance by starting, always, with a moveto, never a lineto.
> 
> I think this is an error. What if the user wants a rounded rectangle. That isn’t possible if `ArcPrecise` starts with a `moveto`. Perhaps there could be an extra parameter, code, usually being one of {moveto}, {lineto}, {pop pop}. Advice welcomed.

Use PS arc: you (often) have to add moveto.  Use ArcPrecise: you 
(sometimes) have to add lineto.  It seems unimportant.

OTOH, if the goal is to make a better arc, start with lineto instead of 
moveto so programmers have no surprises when they use ArcPrecise.

[toc] | [prev] | [next] | [standalone]

#3777

On 7/20/22 11:25, jdaw1 wrote:
>> The build-in routines start with a line from a currentpoint, if there is one. This is annoying. Consider an annulus: there’s a line between the inner and outer circles, avoiding which requires a manual moveto. `ArcPrecise` and `ArcPreciseN` prevent this annoyance by starting, always, with a moveto, never a lineto.
> 
> I think this is an error. What if the user wants a rounded rectangle. That isn’t possible if `ArcPrecise` starts with a `moveto`. Perhaps there could be an extra parameter, code, usually being one of {moveto}, {lineto}, {pop pop}. Advice welcomed.

Advice: 'ArcPrecise' should have the same API as 'arc'.  Why?  When I see
an image that I want to improve by using ArcPrecise instead of arc, then
I want the *option* to interpose a global dictionary which defines 'arc'
as 'ArcPrecise', and have better arcs be the only change to the image.
I might not have access to the innards of the rest of the Postscript code;
it might not be possible to use a text editor to change all calls on "arc".

[toc] | [prev] | [next] | [standalone]

#3778

> so programmers have no surprises when they use ArcPrecise.

Good desideratum. 

I’m coming to the view that ArcPrecise should have an extra parameter, which could be 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.

The compulsory extra parameter prevents surprises.


> Advice: 'ArcPrecise' should have the same API as 'arc'. 

Good desideratum. And 
`/arc {/l ArcPrecise} def`
would work as you require.


Would this extra final parameter, `/l` | `/m` | `/n`, satisfy everybody?

[toc] | [prev] | [next] | [standalone]

#3779

On Thursday, July 21, 2022 at 9:17:26 AM UTC-5, John Reiser wrote:
> On 7/20/22 11:25, jdaw1 wrote: 
> >> The build-in routines start with a line from a currentpoint, if there is one. This is annoying. Consider an annulus: there’s a line between the inner and outer circles, avoiding which requires a manual moveto. `ArcPrecise` and `ArcPreciseN` prevent this annoyance by starting, always, with a moveto, never a lineto. 
> > 
> > I think this is an error. What if the user wants a rounded rectangle. That isn’t possible if `ArcPrecise` starts with a `moveto`. Perhaps there could be an extra parameter, code, usually being one of {moveto}, {lineto}, {pop pop}. Advice welcomed.
> Advice: 'ArcPrecise' should have the same API as 'arc'. Why? When I see 
> an image that I want to improve by using ArcPrecise instead of arc, then 
> I want the *option* to interpose a global dictionary which defines 'arc' 
> as 'ArcPrecise', and have better arcs be the only change to the image. 
> I might not have access to the innards of the rest of the Postscript code; 
> it might not be possible to use a text editor to change all calls on "arc".

I lean towards endorsing this view, but I don't hold the opinion very strongly.
Having a drop-in replacement is very useful. Having a considered and improved
behavior based on the common use cases is very useful. I'm not sure how
to weigh these benefits against each other.

For the implementation side -- apart from the policy decision -- mimicking
the existing API of `arc` can be pretty short and sweet:

  % x0 y0
  { lineto } stopped { moveto } if

This leads to the question: how can you (most) easily get the starting point
out of `arc` or `ArcPrecise` (were it to follow this convention) in order to 
call `moveto` first to eliminate the line segment (erhm, make its length zero)?

If you call `arc` or `ArcPrecise` with an angular difference of zero, it ought
to result in adding to the path just that initial point, right? Then you'd just
need a crazy function to rewrite the path where the very last `lineto` is
changed to a `moveto`. Too ugly for me to want to write it right now, but
feels possible to write.

The extra parameter idea is nice. Extra parameterization is the obvious
way to select variant behaviors. Whether it "looks nice" is a subjective
judgement.

[toc] | [prev] | [next] | [standalone]

#3780

> { lineto } stopped { moveto } if 

Nice. I was testing `currentpoint` with `stopped`: this is more concise. Thank you.

[toc] | [prev] | [next] | [standalone]

#3781

An observation about the maths. 

> A speed of Tan[θ/4]·4/3 has the radius precisely correct at the midpoint

If θ = 90°, then the speed is Tan[22½°]·4/3 = (√2 − 1)·4/3 ≈ 0.55228474983, which is only an edge bigger than Adobe’s fixed value of 0.552.

[toc] | [prev] | [next] | [standalone]

#3782

Is it the best name? Is an error fo 0.37 ppm ‘precise’, or merely ‘accurate’? Should it be ArcAccurate?

[toc] | [prev] | [next] | [standalone]

#3783

On Friday, 22 July 2022 at 08:58:03 UTC+1, jdaw1 wrote:
> Is it the best name? Is an error fo 0.37 ppm ‘precise’, or merely ‘accurate’? Should it be ArcAccurate?
Are you achieving a more accurate result by calculating with greater precision, or by using a better method? Increased precision usually increases accuracy (exception cases aside), but accuracy can often be improved without increasing precision using better approaches or calculation sequence adjustment (typically to maintain improved precision through the calculation especially with limited precision variables). Both "Accurate" and "Precise" would nominally require qualification or quantification (how precise or accurate); ArcImproved could also work.

[toc] | [prev] | [next] | [standalone]

#3784

Really it should be ArcImprovedAccuracy; but I suspect that may be too long for most people's taste.

[toc] | [prev] | [next] | [standalone]

#3785 — Re: ArcAccurate, an accurate arc

Cross-link: also mentioned at https://github.com/jdaw1/placemat/issues/164

[toc] | [prev] | [next] | [standalone]

#3786 — Re: ArcAccurate, an accurate arc

Done. Added to my code
https://github.com/jdaw1/placemat/blob/main/PostScript/placemat.ps
with commit
https://github.com/jdaw1/placemat/commit/77143c29d01f9352a53fa98361cf4589cace92e8
For the latest version, look in that .ps, searching for “ArcAccurateBoth” or “B23RW2QpIjU”.

[toc] | [prev] | [next] | [standalone]

#3975

Also see https://stackoverflow.com/questions/77855798/postscript-circles-how-accurate-how-improve/

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.postscript

csiph-web