Rethink ParamCurve trait hierarchy

[raphlinus]

Right now, there are a lot of essentially one-method traits in the ParamCurve hierarchy. The main motivation is to encourage implementations of parametrized curves, and not all of the traits are easy to implement, so implementers might want to pick and choose. Another strong motivation is to allow finite numbers of derivatives. (Infinite differentiation is of course totally reasonable for parametric polynomials, and another way to get there more generally is to implement symbolic math, but going finite is a tradeoff I'm quite willing to make). But having tons of fine-grained traits is annoying for users, and ultimately I think not all that useful.

Here's my current thinking. Have three main traits: ParamCurveRaw (which is basically the current ParamCurve), ParamCurveDeriv (basically the same as now), and ParamCurve, where the last one is "batteries included." The first two exist to support differentiation: the deriv method of ParamCurveDeriv outputs a ParamCurveRaw which can either impl ParamCurveDeriv or not. And ParamCurve will probably have a bound of first and second derivatives.

To ParamCurve we add the rather powerful to_bez_path which takes a tolerance. This is the gateway to Shape, allowing all curves to be rendered very easily in piet. (For coherence reasons, I think that'll be a newtype rather than a blanket impl, but that doesn't feel bad to me). More important, it lets us add new methods to ParamCurve as long as there's a default impl in terms of the Bézier path; I'm particularly thinking of things like area, which can get tricky for general curves, and maybe not that useful.

Many users will just be able to import ParamCurve. If they want derivatives, they'll need to import ParamCurveDeriv, and if they want to evaluate or subdivide, they'll need to import ParamCurveRaw as well. This seems like a reasonable balance.

Here are some remaining issues to sort out:

The type of extrema should probably not be ArrayVec<[f64; 4]>, as in general a curve can have more than 4 extrema. My current thinking is a SmallVec so it's efficient in the common case, but fully general. I'm open to ideas.

(Going to post this now, but will probably think of other issues, expect edits or followups)

[raphlinus]

More thoughts:

After thinking a bit more, I'm more receptive to infinite differentiation. There can be a default method that does central differencing. Obviously that's going to get pretty janky for high derivatives, but also for the curves I really care about (take polynomial spirals for example) symbolic approaches to differentiation should be pretty tractable.

One of the most important methods to add is parallel curve. This is also among the trickiest for general curves. I'll point out now, one of the reasons I'm interested in Euler spirals as a primitive is because the parallel curve is very well behaved - you know exactly where the cusp is because curvature is explicit, and it's always first-order. Cusps in the parallel curve of cubic Béziers can get... interesting.

Adding additional methods that are supported by associated types, without breaking semver, would be possible if there were default associated types. These don't exist yet in stable Rust, but seem to be on track. David Tolnay a few months ago posted a workaround, but I don't know if it's important. For a really important additional method like parallel curve, I'm more than willing to break semver.

[jrus]

Are there some high-level docs which explain your goals, plans, code organization, etc.?

I’m having trouble following your comments above; I feel like I am missing a lot of context. (Disclaimer: haven’t tried to read through all the code.)

[raphlinus]

Documentation is very thin, sorry about that. I'm doing this somewhat improvisationally, writing code and seeing where it takes me.

Maybe this will clarify some: a secondary goal of kurbo is support of general mathematical curves. Think hyperbola, elastica, lemniscate, cardioid, etc. The reason for the ParamCurve family of traits is to let people define curves with a moderate amount of work, then get back very high quality solutions to problems such as arclength, conversion to beziers, parallel curve, etc. A goal is to be able to exploit particular properties of curves; for example arclength and inverse arclength are much easier for Euler spiral (and polynomial spirals in general) due to the parametrization.

Somewhere between the primary and secondary goals is the fact that I suspect Euler spirals will be useful as an intermediate for parallel curve. So this support for "curves in general" has to work well for Euler spirals particularly.

I realize that doesn't describe the primary goal well. That's something I should write up properly and put on the README. But, very briefly: solid support for rendering, vector graphics creative tools, and math and science, and engineering applications that use 2D curves.

[jrus]

Personally I recommend as an intermediate format approximating most types of reasonably smooth parametric curves as high-degree polynomials, split into segments if necessary. This makes it cheap and easy to approximately (e.g. to within machine precision) compute curve points, tangents, curvature, area, extrema, intersections, offset curves, to apply arbitrary transformations to the curves, ....

Arclength-uniform parametrization / inverse arclength lookups are still a bit annoying for some types of curves, but shouldn’t be intractably expensive with care.

[jrus]

For quick conversion to Béziers for rendering arbitrary parametric curves in SVG I have been generally very happy with my approach in https://beta.observablehq.com/@jrus/bezplot though it doesn’t try to optimize for the fewest curve segments or anything.

For more serious production use it should be iterative instead of recursive, and probably needs better error handling and treatment of various edge cases, but for my purposes it has generally worked quite well.

See example uses at
https://beta.observablehq.com/@jrus/roses
https://beta.observablehq.com/@jrus/double-archimedean-spiral

It’s worth also having some tools for optimizing for the fewest number of Bézier segments possible, but use cases benefiting appreciably from that are relatively rare, I expect.

[raphlinus]

I think use cases where you want at least reasonably efficient conversion into Bézier segments are common enough. Aside from fonts (a serious motivator for kurbo), I am imagining server-side generation of paths that will be served as SVG over the web.

High-degree polynomials are great for representing smooth curves accurately, but for problems like parallel curve they can make things worse. A comparison paper suggests that quadratics give superior results to cubics, probably because it's relatively easy to reason about and characterize the cusps and so on. I'm not sure those results are still considered state of the art.

The bezplot idea certainly looks like a reasonable approach, and the results look good. My intuition is that computing the error metric using Legendre-Gauss approximation will be more robust and not significantly more expensive, but that's largely an empirical question and partly a matter of style. It also looks like this is not G1-continuous by construction and you're fudging that? Maybe it's my bias from font applications, but I tend to nail down the endpoints and let the error happen in the interior. Of course I know that doesn't always minimize an error norm.

But that's getting slightly far afield from this issue. What is relevant is how easy or hard it would be to implement the ParamCurve metrics for the curve of your choice. If you can easily do higher order polynomials, and I can do variants of Euler spiral, then kurbo will be fulfilling its role well.

[jrus]

computing the error metric using Legendre-Gauss approximation

I’m not exactly sure what you are suggesting instead.

One of the main points of my “bezplot” code is to reduce the number of evaluations of the source function. I chose evaluating at 7 points because when subdividing the interval into two pieces, 5 of those can be re-used in the computation at the next level; for each new subinterval only 4 new evaluations are needed.

not G1-continuous by construction and you're fudging that?

It’s not even necessarily precisely C0 by construction (since we are replacing a degree 6 polynomial with a cubic), but in practice my typical SVG output truncates the number of digits of output, and at any reasonable tolerance the points end up the same, and for reasonably smooth functions end up being G1 or nearly so.

I had some other doodles with different methods of constructing the final cubics, including trying to make them G1, but they were more or less visually identical at reasonable tolerance (which was good enough for my purpose making plots on screen; someone doing something else with the results might want have more precise needs).

I didn’t necessarily want to enforce arbitrary functions to plot being G1, because some functions are not G1 everywhere, and I still want to be able to plot those decently. As an alternative if the goal were to output as few cubic segments as possible it would be possible to have some fancier code which searched for split points where one of the first few derivatives of the function was discontinuous. Or maybe use the current bisection method but then at the end throw in a step which tries to consolidate segments.

My code is trying to make a parametric cubic which matches the function in terms of its original parameter; a method which ignores the parameter and just matches the shape of the curve can get an equally good result with fewer segments (potentially a lot fewer), but then figuring out a tolerance metric might be trickier. I’m not remotely an expert on these topics though. E.g. something like https://scholar.google.com/scholar?cluster=16543315902845975714

[jrus]

High-degree polynomials are great for representing smooth curves accurately, but for problems like parallel curve they can make things worse.

What does “make things worse” mean? It is possible to just keep jacking up the degree until you get an exact (to within machine precision) representation of the offset curve in terms of the original parameter. This is straight-forward to compute, and the result is easy to work with afterward.

If you just want to plot the offset curve you can try to split that thing up into straight or cubic segments or whatever using whatever generic parametric curve plotting tool.

[raphlinus]

Ok, this discussion has been wide-ranging, but I think that's actually helpful to getting this issue resolved.

The first question is: what is the ParmCurve family of traits for? Upthread I suggested it was for arbitrary curves. I've reconsidered, and now think it's for curves that are suitable as universal representations. The fundamental question is: how exclusive is the club? If it's intended for a very small number of primitive curves that will be widely used, then it should be designed to be not necessarily easy to implement, but easy to use. In practice that means consolidating into a small number of individual traits, having a rich set of methods, etc. On the other hand, if it's intended for encoding any curve a user envisions, then it has to be easier to implement, a different set of tradeoffs. But now I think that the latter is a fundamentally different problem, more or less the scope of bezplot above. I think whether kurbo should have an arbitrary curve plotting facility is another issue, and then if so whether it should be based on Chebyshev approximation or something else.

What are plausibile universal representations? Obviously cubic Béziers, but there are a few more. One is Euler spirals, for reasons I don't feel I need to go into more deeply. Another is high-degree polynomials, which have specific superpowers: being easy to manipulate in Chebyshev basis, ability to represent smooth curves to very high precision with a small number of primitives, trivial to differentiate. But the flip side is that other problems get harder. To avoid getting into controversial territory, I'll just name "extrema," which is extremely important in graphics contexts to compute bounding boxes, and is quite straightforward up to cubic but then starts requiring more sophisticated root-finding as powers go up.

Another curve that is maybe not a great universal representation but absolutely deserves ParamCurve is circular arcs, and most likely ellipses as well so it's closed under affine (though things are quite different - arclength and inverse arclength is trivial for circle, hard for ellipse. So there's a question whether you want to detect eccentricity numerically and special-case those computations, or whether to use types so that you can know at compile time that you've got only circular arcs. This question is related to whether I want a separate orthonormal transformation type to complement affine)

All of the above is likely or at least plausible to land in kurbo at some point.

I do want to keep this a publicly implementable trait, so that motivated people can do their own universal curve representations. There are a few more that come to mind, including Pythagorean Hodograph curves, rational Béziers, probably one or two more.

So given those constraints, I see a pretty clear plan: basically make things easy for consumers of the traits. People implementing it will have to do infinite differentiation (either symbolically or forward differencing), solve extrema exactly, etc.

There are some unresolved issues.

One is the signature of extrema. Right now, it's pretty tuned to the maximum number of extrema of a cubic Bezier. I think the cleanest way to solve this is to promote an ArrayVec of 4 floats to a SmallVec.

The next is the mix-and-match of that you can get of all the fancy methods applied to the derivatives. There's no reason to compute the Green's theorem area of a "curve" that's the derivative of an Euler spiral, so I think it's wasteful for these to exist, even if there's some backfill implementation based on quaddening to Béziers. ("Quaddening" is a word I just made up, but I like it!). So I think having just one ParamCurve trait is too little.

So I don't feel completely converged, but here's a plan I think will work: new ParamCurve is old ParamCurve + ParamCurveDeriv, and new ParamCurveExtra: ParamCurve has all the other methods: acrlen, inv_arclen, area, nearest, and extrema. It also gets to_bez_path, which is of course trivial for all existing impls, but will be interesting and important for, eg, Euler spiral. Since there will be more than one trait, I'm also open to keeping ParamCurveDeriv separate so infinite differentiation is not needed, but I lean towards keeping it. Derivatives are good, and having analytic derivatives doesn't seem too onerous for any of the curves I'm envisioning implementing the base trait.

[jrus]

The first question is: what is the ParmCurve family of traits for?

Yes, this is the main thing I was not clear about.

high-degree polynomials, which have specific superpowers [...] but the flip side is that other problems get harder. To avoid getting into controversial territory, I'll just name "extrema," which is extremely important in graphics contexts to compute bounding boxes, and is quite straightforward up to cubic but then starts requiring more sophisticated root-finding as powers go up.

Yes. This can be done pretty efficiently but is definitely non-trivial to implement.

Let me add that there are reasons to put even cubic curves in Chebyshev basis. A bunch of operations are cheaper, the ones that aren’t are about the same cost, and I think there are probably some ways to handle some additional fancier operations with implementation effort. For example I think there’s some reasonably fast method for computing precise intersections.

---

Another curve that is maybe not a great universal representation but absolutely deserves ParamCurve is circular arcs, and most likely ellipses as well so it's closed under affine (though things are quite different - arclength and inverse arclength is trivial for circle, hard for ellipse. So there's a question whether you want to detect eccentricity numerically and special-case those computations, or whether to use types so that you can know at compile time that you've got only circular arcs. This question is related to whether I want a separate orthonormal transformation type to complement affine)

If you want to support circular or elliptical arcs (or pieces of other conics for that matter) I definitely recommend using a rational representation rather than parametrizing by angle measure. Then you can apply whatever projective transformations you like.

Just compute arclength numerically.

I do want to keep this a publicly implementable trait, so that motivated people can do their own universal curve representations. There are a few more that come to mind, including Pythagorean Hodograph curves, rational Béziers, probably one or two more.

While you are at it, you probably want to eventually add NURBS and maybe some other CAD/3d animation curve types.

One is the signature of extrema. Right now, it's pretty tuned to the maximum number of extrema of a cubic Bezier. I think the cleanest way to solve this is to promote an ArrayVec of 4 floats to a SmallVec.

Does your extrema just output parameter values?

[raphlinus]

While you are at it, you probably want to eventually add NURBS and maybe some other CAD/3d animation curve types.

NURBS are one of the main reasons I said "rational B-spline". For the others, I think kurbo will remain 2d, but perhaps I can be persuaded.

Does your extrema just output parameter values?

Yes. This seems handiest, as you can trivially evaluate the curve at that point when computing bboxes, and then the parameter is also what you need if you're going to subdivide into monotonic segments.

[raphlinus]

We discussed this in office hours this morning. I'm now inclined to close this issue as not planned. The top-level summary is that the existing ParamCurve traits seem to be good enough, and some of the use cases contemplated are best handled in other ways.

We now have experience implementing Euler spirals (see #229), and the existing trait hierarchy did not get in the way of that. The original goal was to make it relatively easy to implement new curve families and consume them in kurbo. This has been happening a bit, but slowly. That means I don't think we have to cater specifically to that use case, it's reasonable to imagine creating new curves as "expert level" and requiring some extra work to make the trait implementations work.

The other major use case is converting to Béziers, which is the scope of the to_bez_path method proposed for the "batteries included" ParamCurve. Now that we have lots more experience doing curve fitting, it's clear this is not so straightforward. What is desired here? If the answer is highly optimized Bézier paths, then the ParamCurveFit trait in #230 is more appropriate. That trait is also more general in that it could be used to generate other targets than cubic Béziers, as well. Other source curves may admit more "quick and dirty" conversions. Because of the variety of uses, I think these are best handled on a case by case basis, rather than trying to have one method in a common trait do everything.

The need to import traits to get access to methods is a minor ergonomic paper cut (and one of the motivators of this issue), but less so now that tools (including rust-analyzer) helpfully suggest a trait import.

Thus, I'm not seeing a compelling reason to change the trait structure, or that the new proposal will be that much better in practice.