Item — HN Reader

Numerical solutions are better. Having a closed form solution is overrated. For example, the closed form solution for arc length of a quadratic Bézier becomes numerically unstable for curves that are close to a straight line. In those cases, you definitely want the numerical approach.

I also think Pythagorean Hodograph curves are overrated. Euler spirals, on the other hand, are extremely easy to work with in an arc length parametrization, it's just that you need to compute a "special function" to get back to parametrized land. Fortunately, that's easy enough to compute very accurately using standard numerical techniques.

4 comments

Hey I was about to write a comment suggesting Euler spirals may be easier to calculate the arc length because they are literally defined as a curve whose curvature changes linearly with its curve length, and then the Euler spiral guy himself shows up. :)

GPU-Friendly Stroke Expansion - 177 points - 11 days ago - 40 comments https://news.ycombinator.com/item?id=40856431

Numerical solutions are usually much more accurate, yes. However, especially when computing with fragment shaders for example, closed form formulas tend to be faster. But the main reason for looking into it was because i had fun doing it.

This is a little mixed up. If you write the arc length as an elliptic integral and evaluate it using a special function library, you may just be evaluating a Chebyshev series or some rational approximation (or some piecewise combination). It may indeed be quite accurate... but that will be for a general case which may be too heavyweight (e.g. a library function which evaluates a special function for any choice of parameters to 15 digits). It might be that directly approximating the arc length if your particular curve on the fly (a smooth function!) with a Chebyshev series will be faster for the same accuracy, but now you can also reduce the accuracy to get more speed if you like. This is the sense in which numerical methods are almost guaranteed to be the superior tool for the job.

That's a really good reason, and thanks for the writeup!

My main point is that I believe there are tons of excellent numerical techniques just waiting to be discovered. Lately I've been exploring a Chebyshev polynomial basis for the Whewell equation, and I think that'll bear fruit.

Pythagorean hodograph curves may be impractical, but they're a pretty theoretically cute idea. Farouki's book is nice.

(From what I can tell PH curves are rarely if ever used in practice. They were ostensibly developed for CNC machining and robot motion planning, etc., but are there real products or even serious physical research projects implementing them? What they do have going for them is a huge pile of research papers, of highly variable quality – Google Scholar turns up >2,500 entries.)

We're using them in practice for C⁴ corner smoothing in a motion controller [1]. All credit for the actual maths to [2].

[1]: https://github.com/Prunt3D/prunt_notebooks/blob/master/Pytha...

[2]: https://link.springer.com/article/10.1007/s00170-022-09463-y

Thanks for the links! What's Prunt, and does it have a website?

> What's Prunt, and does it have a website?

A motion controller for 3D printers (notably with crackle-constrained trajectory planning), and no website since it is still in the early stages.

Following up on your recent article about stroking: is there any hope for general convolutions (or at least more general ones than with circles) via Euler spirals? Such as for pens in METAFONT and Illustrator and so on.

I think it's a great avenue for research. I'm probably not going to work on it myself any time soon, as I have a very full queue of ideas to pursue.

> any hope for general convolutions (or at least more general ones than with circles)

Interesting question.

Knuth's METAFONT can describe glyphs not simply as filled outlines, but ALSO as strokes of pens shaped by circles, ellipses, and EVEN convex polygons (e.g., a an acute triangular wedge perhaps).

And the description of a METAFONT glyph is all parameterized (it's really a program! -- hence the META) so there's not even an actual outline for a glyph but a tunable family of glyph variations.

METAFONT's model is humanistic as human ideographs and letter forms were (once) scratchings, engravings, and pen strokes. However the shape of movable type, as captured with Bezier splines by TrueType and Postscript outline glyphs, lack a first-class stroking capability.

So could you support the humanistic METAFONT-style approach efficiently in today's world of GPU rendering? Yes, if you could, as suggested above, efficiently convolve a pen's shape with a stroke trajectory.

Circles for pens are no problem; and ellipses are just squished transforms of circular stroking. But (convex) polygonal pens for stroking?

Polar stroking provides a starting framework for such a convolution approach for convex polygonal pens (say, a triangular wedge or other convex polygonal shape). Step in small changes in gradient direction change. Rather than assuming a conventional circular or nib pen shape, snap each tessellated rib to the closest polygonal pen vertex. The result is the polygonal convolution you seek.

So a question almost nobody is asking: What if we could revive METAFONT for the 21st century?

Imagine a Jurassic Park scenario applied -- not to dinosaurs -- but rather to Knuth's Computer Modern.

https://en.m.wikipedia.org/wiki/Computer_Modern

"Your scientists were so preoccupied with whether or not they could, they didn't stop to think if they should."