111 views

Skip to first unread message

Jul 19, 2022, 3:47:27 PM7/19/22

to

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.

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.

Jul 20, 2022, 2:25:22 PM7/20/22

to

> 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.
Jul 21, 2022, 4:29:38 AM7/21/22

to

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
>> 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.

(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.

Jul 21, 2022, 10:17:26 AM7/21/22

to

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
>> 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.

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".

Jul 21, 2022, 3:02:40 PM7/21/22

to

> 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'.

`/arc {/l ArcPrecise} def`

would work as you require.

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

Jul 21, 2022, 5:31:22 PM7/21/22

to

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.

Jul 21, 2022, 6:00:19 PM7/21/22

to

> { lineto } stopped { moveto } if

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

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

Jul 21, 2022, 6:24:18 PM7/21/22

to

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.

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

Jul 22, 2022, 3:58:03 AM7/22/22

to

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

Jul 22, 2022, 4:42:18 AM7/22/22

to

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.
> Is it the best name? Is an error fo 0.37 ppm ‘precise’, or merely ‘accurate’? Should it be ArcAccurate?

Jul 22, 2022, 4:52:33 AM7/22/22

to

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

Jul 22, 2022, 5:03:12 PM7/22/22

to

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

Jul 24, 2022, 12:02:26 PM7/24/22

to

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”.

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”.

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu