4 ms·

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 techniqu

by bmer 6y ago

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/flatten-quadbez.html 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?

raphlinus 6y ago
Great questions, thanks! * 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.
- chrismorgan 6y ago
  (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.)
- dognotdog 6y ago
  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.
  - raphlinus 6y ago
    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.
Someone 6y ago
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.

by bmer 6y ago

raphlinus 6y ago

Great questions, thanks! * 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.

chrismorgan 6y ago
(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.)
dognotdog 6y ago
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.
- raphlinus 6y ago
  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.

Someone 6y ago

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.