linebender / spline

A spline for interactive 2D curve design
Apache License 2.0
112 stars 8 forks source link

Is it possible to get a lossless (or even lossy) upgrade of a Spiro spline to a Hyperbezier? #25

Open ctrlcctrlv opened 1 year ago

ctrlcctrlv commented 1 year ago

Now that I have implemented https://github.com/MFEK/spiro.rlib, I am very curious if it's possible to upgrade my Spiros to the superior Hyperbezier.

I have a lot of Spiros, that's why I maintain it.

In https://github.com/raphlinus/raphlinus.github.io/issues/40 @raphlinus wrote:

Introduction: hyperbezier is a synthesis of three curves: cubic bezier, euler spiral, and elastica. Tension is a central concept.

This is very similar to how Spiro works, if I understood the thesis right. So really perhaps hyperbezier is "spiro v2", but perhaps that's ignorant of the maths of it all.

Is there a way to upgrade Spiros, Raph?

raphlinus commented 1 year ago

This is on my backlog, but I do hope to get back to it. There are three things holding me back.

The first is that I couldn't at the time figure out a good way to render hyperbeziers to ordinary cubic Béziers. That's a much harder problem than Spiros because of the high tension. I am pleased to say that I have done the conceptual work for this (see fitting cubic Bézier curves and the followup parallel curves of cubic Béziers) and, by happy coincidence, happen to be noodling on the Rust implementation in my holiday break. I believe this will be a completely satisfactory solution, as it will generate extremely accurate cubics, and I think the performance will be good as well, as it will generate a smaller number of segments to attain the desired accuracy bound.

Second, I'm not sure the existing formulation of the hyperbezier is perfect, though it is very good in its current state. One section of the parameter space I'm not sure about are when one side has very high tension and the other low but with a large deflection. There, hyperbezier produces a curve with a dip in curvature in the interior, while I think a curve closer to the semicubical parabola would be more aesthetically appealing. Another range I'm not completely satisfied with is when both tensions are low, as this should probably produce something closer to a superellipse with high-ish exponent. I might be able to figure out better math but haven't yet.

Third, the solver is not 100% numerically robust (problems are most likely to occur when knots are very irregularly spaced, with some very close together). I suspect there is a theorem that a unique solution is possible (at least under some reasonable conditions, as in the Hobby spline), which would illuminate an algorithm that can't diverge, but I believe this is fairly difficult math - I've played with it some, and asked advice of better mathematicians than myself. I should note though that it's already much better than the Spiro code, which as we all know is easily prone to divergence, related to the fact that we know mathematically that there are some inputs that do not have unique solutions.

So hopefully with patience we will see some more progress. The best way to speed that up would be to learn the math or recruit somebody with math skills.

ctrlcctrlv commented 1 year ago

Thanks for the general update @raphlinus, very interesting and appreciated. But, sorry, regarding my initial question, I think perhaps you overlooked it. If I have a lot of Spiro splines is there some way, even theoretical / with no implementation plan, to upgrade it to a Hyperbezier format spline?

raphlinus commented 1 year ago

Ah, I misunderstood the question, I thought you were asking about upgrading the code, but now I see it's about changing curve representations. That is a very interesting question indeed.

First, all Spiro curve segments with tension <= 1 are automatically hyperbeziers (at least in the current representation). That includes Euler spirals, which are the result of plain G2 curve interpolation. So those could be converted with a relatively straightforward re-parametrization.

But that's not a fully satisfying answer, as it's certainly possible to create curves with higher tension (though, that said, it would be interesting to see what fraction actually are in your dataset). I believe the best way to go about that is to do general hyperbezier curve fitting. That will be useful in converting existing cubic Bézier splines, as well as freeform pen strokes. I just spent a bunch of effort doing curve fitting with cubic Béziers (see https://github.com/linebender/kurbo/pull/230), and in particular I think the ParamCurveFit trait can work for this. You could either implement this trait analytically for Spiro, or just do a spammy conversion to Béziers and use the implementation in that PR; the accuracy and performance of curve fitting basically doesn't depend on the number of subdivisions of the source curve for piecewise representations.

I haven't fully worked out how to do curve fitting, but I think Newton iteration of the tension parameter to match area/moment will probably work most of the time, especially if initial setting of the tension parameters is reasonably good. The reason I think Newton iteration will work is that area/moment should (in most cases, though this bears experimental validation) be monotonic and in fact nearly linear.

As before, the fastest way to see progress on this is to get someone who would enjoy getting deep in the math.

ctrlcctrlv commented 1 year ago

Very cool. I'm going to have to check how many are tension ≤ 1. Thank you for all your work on non-Bézier spline formats! :-)