Hi Raph! This was a fun read, and I have some questions to help me contextualize this post with respect to your other work.
* In terms of mathematical technique, this is a "sister post" to https://raphlinus.github.io/graphics/curves/2019/12/23/flatt... , because they both use the idea of using the relationship between arclength and curvature to determine how best approximate one type of curve as another curve?
* Have you done the analysis in this paper with a Euler spirals -> cubic Beziers because they are the "cultural norm", or because quadratic Beziers are problematic here for some reason?
* When you say that you look forward to exploring using Euler spirals for other "classical 2D geometry problems", do you mean "classical 2D geometry problems, related to 2D graphics rendering", or are you actually thinking more generally? If you're thinking in terms of 2D graphics rendering, do you have a short-list of problems in mind?
* Here's an idea for a book. On the cover, a thousand cartoon Raphs are pictured, each equipped with a typewriter. The title is: "1000 problems your 2D graphics renderer NEEDS to handle (no solutions included)". Do-able for 2021?
* Yes, absolutely. The fundamental concept common to both posts is the error metric. There's no general cookbook formula for coming up with good ones (see Trefethen's work for mathematical foundations), but if the function you're approximating has simple mathematical properties, it's often possible to come up with something. The technique that seems to work best for me is some integral based on curvature and curvature variation. With Euler spirals it's super easy to compute those.
* I'm actually working on both cubic and quadratic Béziers as the final output format. I thought the story here with the n^5 scaling of cubics was simple and compelling, and the two-parabola picture might be helpful to designers.
* Related to font design and rendering, yes. The main problems I'm thinking about right now include generating optimized simplified representations (mostly for fonts), overlap removal, and warping (waving flags for emoji was a motivation). One particular facet that's especially fascinating is generating variable fonts, where the outlines need to be "interpolation compatible."
* The problem with that idea is that HN would strip the leading number from the title, which would be confusing. In my opinion, that's a valid reason not to go with it.
Is there a decent FOSS solver or algorithm for Cornu splines these days?
I did write a road digitizing tool for an internal simulation, based on raphlinus's thesis, about 12-13 years ago, but always had trouble with numerical stability.
It's such a fantastically better tool for vector art than regular splines, though, especially with higher-order continuity.
Numerical stability is a fundamental problem with interpolating splines defined over Euler spirals because a unique solution is not always guaranteed to exist. I'm pretty sure there's a theorem in there somewhere if deflections can be bounded, but I haven't found it yet.
If you don't need exact Euler spirals and are ok with increasing the tension on high deflection (which imho is valid for design tasks like making fonts), then the approach of the hyperbezier spline might be an appealing alternative. I believe that always has a solution, but the current solver is kinda dumb and can fail when points are very close together. I plan on improving it.
The general idea of the hyperbezier solver - use Hermite geometric interpolation, and solve the tangent angles for G2 continuity - is a better approach than what the Spiro code does. That has technically richer capabilities (including G4 continuity if needed), but is less stable.
I don't promise anything, but if you want to file an issue against linebender/spline with more detailed requirements of what you need, I will at least take a look at it.
(Note that if HN mangles your title, you can go back and edit it to fix it. But in this sort of a case, the number would be contrary to one of the HN guidelines, so if you reinstated it it’d be liable to be removed by mods.)
For that book, I would take a look at Apples long dead QuickDraw GX. It did the offsetting, even-odd rule and non-zero rule, all kinds of intersections, color spaces, text along paths, affine transforms, etc.
I don’t know any more complete 2D graphics API (but then I don’t know many well)
Following TrueType, it used quadratic Bézier curves. It also made the, I think somewhat contentious, choice to use fixed-point coordinates. That guaranteed that translations of graphics didn’t change their rendering, though.
Oh this is very interesting to me. Currently working on adding proper cubic bézier primitives to a geometry engine I'm working on, and curve offsetting is an operation I haven't implemented yet. Skimmed the essay, and will have to sit down and read it properly next week.
This is a tangentially related question, but seems like a good opportunity to ask:
I recently found myself trying to figure out how to implement "parallel curves" to arbitrary polyline shapes with small (relative to the offset), complicated details (world map borders from shapefiles). Eventually I found a way to accomplish my goal with existing software, so gave up on implementing it myself, but I'm still curious how it might be done.
Parallel curves are conceptually straightforward when you're working with shapes defined by some sort of splines. I'm not sure if the problem is even well-defined when working with complicated polylines. It doesn't seem that Minkowski operations or PH curves are quite enough to solve this problem. Is there solid math that addresses it? Do existing CAD tools use proprietary heuristics? Is there a simple solution that I missed?
So the underlying operation of finding a parallel "curve" is trivial when the curve is a line, as it's just another line. That doesn't mean the problems is simple, though. One challenge (which I didn't address in the post, nor do I have code yet) is dealing with corners, as there are the usual choices of round, miter, and bevel. Of these, only round represents a true Minkowski sum. The others are generally more commonly used. Btw, see "Polar Stroking" [1] for more details on this. I came very close to linking it.
The second detail is the "trimming" as the parallel curve paths generally have self-intersections, and very often you don't want those. So in the general case you have to do something similar to, say, Skia path ops. It's very difficult to make those operations completely numerically robust, and I think most implementations have gone through some pain as more test cases pop up which break.
It is a fascinating area. I'm glad you're curious.
* In terms of mathematical technique, this is a "sister post" to https://raphlinus.github.io/graphics/curves/2019/12/23/flatt... , because they both use the idea of using the relationship between arclength and curvature to determine how best approximate one type of curve as another curve?
* Have you done the analysis in this paper with a Euler spirals -> cubic Beziers because they are the "cultural norm", or because quadratic Beziers are problematic here for some reason?
* When you say that you look forward to exploring using Euler spirals for other "classical 2D geometry problems", do you mean "classical 2D geometry problems, related to 2D graphics rendering", or are you actually thinking more generally? If you're thinking in terms of 2D graphics rendering, do you have a short-list of problems in mind?
* Here's an idea for a book. On the cover, a thousand cartoon Raphs are pictured, each equipped with a typewriter. The title is: "1000 problems your 2D graphics renderer NEEDS to handle (no solutions included)". Do-able for 2021?