Output Bézier splines not deterministic enough

[ctrlcctrlv]

Hello @JoesCat, good day.

A problem I've been thinking about for a while is how we can increase the determinism† of the output Béziers from libspiro, at the cost of increased path complexity, and, perhaps, even some mathematical accuracy.

This would make it much easier for Spiro splines to be used in variable fonts, or in other cases where we'd want interpolation. Right now, Spiro users such as me usually have to redraw one or both splines to create an interpolation-compatible spline.

It's clearly quite the challenge. Before I give you my thoughts, what are yours?

† The type of determinism I'm specifically referring to is determinism in the number of points. So, for two Spiro splines with n points, assuming all point types are equal, and both splines have the same openness/closedness, we always get back a Bézier spline with N points, no matter the configuration of the Spiro points.

[JoesCat]

Hi Fredrick,
I am guessing you might be making this problem more complicated than I think it is.
Having looked at some gifs showing variable fonts, it seems you're really just playing with X as a variable.
The frame of reference is important. When people believed Earth as the center of observation, there was a complicated set of wheels upon wheels charting the orbits of the planets and stars. When we moved our frame of reference to have the Sun at the centre (not the Earth), the orbits became a lot simpler to understand too.

Likewise, we may think of 0,0 as point of origin, but in terms of variable fonts, you really should think of the center of the char as 0,0 and everything stretches proportionally from the centre of the char (towards the left and towards the right).
Assuming a char X dimension is 1000points across, that would mean 500 on the left and 500 on the right. If we stretched the char out to 2000points, you will probably see everything stretches accordingly.
You should not think of 45deg angles, you should rethink of angles based on a changing X, so if you have Y=100,X=100,angle=45, it then becomes y=100,x=200,angle now 30degrees.
You will probably see this easier if you just draw some sort of char on graph paper, and redraw it 2x wider....the bezier curves should follow proportionally without anyone needing to recalc points to maintain smoothness.

In terms of maintaining the same number of curves when drawing with libspiro, you should consider having 2 grids. Let's say 1000x1000 as a "fixed" value for libspiro calculations, and a second grid, which is "variable" so the user can see the changes as X slides in or out....so if you shrink to 800x x 1000y, then you multiply all x values by 4/5 from the center of the char, or stretch to 1200x x 1000y, then you recalc display values by 6/5 from the center of the char.
Assuming the user is looking at a displayed stretched grid of 1200 x 1000, and you want to change a spiro point, you would be applying 5/6 x Xdisplay to use the 1000x1000 spiro calculation grid, or 5/4 x Xdisplay to convert from what you see to what libspiro calculates on.

This is not important to the question, but more of an FYI, the older libspiro calculations are based on 0,0, while the "2" functions are based on Xcenter/Ycenter ....but this should have nothing to do with the problem.

Just keep a fixed grid for calculating spiros, and translate to a variable grid for displaying your variable font.

Hope this helps

[ctrlcctrlv]

@JoesCat When I say "variable fonts", I don't mean a custom rasterizer which would support Spiro, or which would interpolate Spiro points, but rather OpenType 1.8 Font Variations, which only can be drawn using quadratic or cubic Bézier splines. So, we would have two slightly different Spiro splines, and the hope is, we get quadratic/cubic splines that are interpolation-compatible.

[skef]

Having thought about related issues I continue to think that there's no need for a tool specific to Spiro or Expand Stroke to support variable fonts. What is needed is a tool that can take two or more smooth (sub-)contours (occasionally closed (as in the middle of an "o") but usually open (as in the outside of an "e")) as input and outputs corresponding (sub-)contours with the same endpoints but having interpolation-compatible points and close to the same geometry. If you have that you can post-process the output of other tools to generate interpolable masters.

Given that in practice a (sub-)contour will be G1 smooth rather than C1 smooth (and often won't be G2 smooth) you can't just reparameterize to get the desired number of points. Therefore a sophisticated fitter is what is needed; one where you can influence the number of points fit and where some of them go. Ideally such a tool could also do something at least reasonable about geometric matches (such as when both (sub-)contours have an inflection point) and mis-matches (such as when only one does).

I had thought a bit about this before starting the stroke code and went down a large and ultimately unnecessary rabbit hole during its implementation trying to determine the best fit algorithm for these purposes. It doesn't appear that there is a best one -- it might be better to have a "toolbox" and try multiple approaches with multiple starting parameters, sometimes selected randomly.

It would also be nice if such a tool could do a better job at the Bezier->Spiro direction, so there can be fewer points when transitioning back.

[ctrlcctrlv]

Thanks @skef. If you say it's impossible I trust your judgment, you're the math wiz around here. 🧮

(By the way, I might not be pushing round 2 of fontforge/fontforge#4321 tonight, sorry about that. I have been working on it but have gotten bogged down in some part of it. Hopefully @davelab6 doesn't kill me.)

[ctrlcctrlv]

Although, maybe, for my sake, if you feel like educating the simple, you can explain why it's impossible to go segment-by-segment in a Spiro spline and come up with an approximation using n curve points of the normal Bézier conversion of that segment?

[skef]

The argument isn't that it's impossible it's that I don't see what a Spiro-specific tool would add.

go segment-by-segment in a Spiro spline and come up with an approximation using n curve points of the normal Bézier conversion of that segment

Here is a simple curve-fitting heuristic that could be applied to the variable font problem: Take each corresponding sub-contour and fit it with successive point counts until you're under an error threshold. Then take the max needed point count and refit the other ones to get the same number of points. This heuristic will fail in any number of circumstances but it's not a bad starting point.

Now:

1. What's the difference between fitting the "raw" Spiro curve that way instead of fitting the initial Bezier output? Very little, as long as do something reasonable with accuracy in both cases.
2. In order to choose "n" reasonably you need to consider the family of sub-contours that need to interpolate with one another. That information isn't typically available at Spiro -> Bezier conversion time. So you would need to expand that part of the code to be "other-master-aware" without obvious benefit.
3. It's bad to just choose a high-n for all cases both from an output-point-count perspective and from an interpolation perspective (with many or the wrong points you're more likely to get "wiggly" intermediate results). So you can't just hard-code the point count either.

[ctrlcctrlv]

Yes @skef you're right, I was already taking it for granted that we'd need a new Spiro conversion function which takes two Spiros, which would need to be checked for "Spiro compatibility" (essentially the same thing as cubic/quadratic compatibility, but marginally simpler with Spiro as all points are on-curve). Then, we'd call this function in e.g. Interpolate Fonts, and perhaps some future «MM→Create MM…» dialog which actually supports the current standards.

Definitely we cannot just go with a high n.

So really the only difference between the "raw" curve fitting and the "double" curve fitting is that whatever segment needs the most points, the other segment will get that many too.

[skef]

(essentially the same thing as cubic/quadratic compatibility, but marginally simpler with Spiro as all points are on-curve).

Except that in either case you're not fitting to FontForge points but to either the geometry of the curve as a whole (less likely) or to points sampled along it. Sampling with "native Spiro" vs Bezier isn't likely to make a substantial difference. Maybe Spiro makes uniform sampling easier (I haven't looked into it) but you probably only need approximately uniform sampling anyway.

I looked into direct geometric fitting vs sampled point fitting and the former seems really tricky and potentially expensive because you need to compute the shortest distance between to curves while still maintaining some proportionality along the curves. Sampling the source curve with points brings you back into the ordinary world of curve fitting.

[skef]

Incidentally Spiro point interpolation is easy: Just do it the same way as you would a normal transformation. However, given that linear transformations on Spiro points aren't affine there is no clear relation between Spiro point interpolation and true variable fonts. One could interpolate between Spiro masters for inspiration or as a potential source for more masters but the "end user" can't do so.

[JoesCat]

Thanks for the external links - weight and width.
I would agree with @skef - the better direction is a toolbox.
Let libspiro be good at what it does - draw a "single" curve.
Inkscape may appear to create two curves https://www.youtube.com/watch?v=3OaLZuFZxdk but this is a single curve - you see it at the beginning, and you see the knots again at 2:12 minutes.
What you need is a toolbox that takes the output curve, and then duplicates it, and you can apply the rules of weight and width far better at the FontForge level.

[skef]

@JoesCat As @ctrlcctrlv has noted, although variable fonts often support width and weight changes at the high level that goal doesn't have any direct analogue in the implementation. The nuts and bolts of variable fonts are implemented by linearly interpolating the corresponding Bezier points (on-curve and control) of "master" contours. When there is a "weight" knob it is because the designer has included "thick" and "thin" masters that interpolate cleanly. The knob setting determines the degree of interpolation.

[JoesCat]

ok - going back-n-forth between all the info in this thread...
...ok, think I gotcha.
...so the "interpolation" refers to trying to draw the same curve using quadratic and/or cubic.
Let's see.... back to the Original question...just to get this out of the way...
@ctrlcctrlv - I can see you had trouble trying to use libspiro to draw two sets of curves.
The math in libspiro seems to target -0.5...+0.5, but as libspiro is currently used, we are working at a huge offset from 0,0 towards 1000,1000 and also far beyond the scale of +/-0.5
The run_path portion of libspiro is okay with this offset from 0,0 because it's basically vector and angle math, but the latter set_path not so much, and started presenting itself as a bug in tests/call_testm that needed fixing. So rather than adjust hard cutoffs like 10^-8 or 10^-12 to account for size and offset, I just rescaled everything to fit inside -0.5...+0.5, then right-sized everything back into scale when done. This is the bug fix 7f739b4 but it is only visible through "TaggedSpiroCPsToBezier2()" to avoid causing negative effects on older code and curves.

In terms of reliably maintaining 'n' bezier curves, you can also break a curve into segments using '[]' or 'ah', but then this sort of defeats libspiro calculating best fit for you because now you force angles.

okay, back to interpolation....walking along the curve...see if this thought helps much...

1. libspiro == master curve.
   2a) cubic representation - substitute both of these "TaggedSpiroCPsToBezier0(spiros,bc)" with this "TaggedSpiroCPsToBezier2(spiros,0,bc)"
   2b) quadratic representation - substitute both of these "TaggedSpiroCPsToBezier0(spiros,bc)" with this "TaggedSpiroCPsToBezier2(spiros,SPIRO_QUAD0_TO_BEZIER,bc)"

...now, going back to @ctrlcctrlv reference at OP... for 2 curves, and @skef 's toolbox
3) Toolbox -> duplicate the master curve 2a or 2b for an outer line, and again for an inner line.
4) Toolbox -> apply other FontForge knobs like weight, width, slant, etc...
5 ) as a user... go back to 1 to modify master curve, and apply 3,4 toolbox and/or further edits.

6. when done "export" results, and hold onto master, plus toolbox knobs in master sfd file.

QUAD0 is pretty-much a first attempt. If you got plenty of bend, a quad can sort of be close to a cubic, but the flatter the cubic gets, the easier it is to see that you need more quads to represent the cubic (2 won't be enough unless you're willing to live with the error). If there is going to be a kink in the curve, I would expect it to show itself between these two Quads since it's a midpoint of the cubic, and angles weren't calculated here, a better compromise is going to have to be something like a straight line going through this point, or breaking-up the curve further.

[skef]

so the "interpolation" refers to trying to draw the same curve using quadratic and/or cubic.

@JoesCat Just to clarify the term (linear) "interpolation" is used in its ordinary sense. Say you have two reference numbers: 20 and 40. 30 is 50% of the way from the former to the latter, 35 is 75%, and so on. If you have points (20,20) and (40,40) then it's similarly (30,30) and (35,35).

As you turn the knob on a variable font all that's going on underneath is that the corresponding points in the corresponding contours of each master are being varied in this way. The problem of making a variable font is therefore the problem of having a good result under this simple operation. For corresponding "smooth curvature" portions of a contour that typically means having the same number of points in that section of the contour spaced roughly the same way.

[JoesCat]

Thanks @skef for the interpolation clarifications.
BTW, the sine wave reminds me of a past project, where you take a clean sinewave (let's say -1.0....+1.0) and approximate the best fit in an integer format.

I looked at this https://docs.microsoft.com/en-us/typography/opentype/font-variations which references a summary here https://medium.com/variable-fonts/https-medium-com-tiro-introducing-opentype-variable-fonts-12ba6cd2369

What I think may seem to be confusion between us, is @ctrlcctrlv started with spiro points.
At this high-level - We already have known points, and we want to manipulate them in a manner to make variable fonts in such a way to fit the defined boxes.
The suggestion I made, was basically a sky-view, here is how you can adjust the width knob, which was, stretch it out (Arbitrary 800/1000/1200 values). The number of points remain the same.
Rasterization was probably the wrong reply, because now you're thinking in pixels, not points.
If we continue to think in points, the count remains the same. I also don't see a problem in stretching-out a bezier. It's like if you are looking at a circle on a page head-on, or looking at the same page from 45deg, which then makes the very same circle appear stretched into an oval.

Where you came into this conversation seems to be a couple steps into sampling and curve fitting.
Although related, it is a solution for a different problem.

The toolbox is good - you really don't want to be importing all this complexity into spiro - it doesn't belong in that library, but I think the question was more of spiro->n_beziers->N_points. The solution was, keep spiro X and Y dimensions fixed, and use a different grid to work on variances.

The curve fitting is good, but it's more in the direction of curve->n_beziers->N_points.

Toolbox location....probably would fit best somewhere around the n_beziers point.

[terryspitz]

Fascinating discussion. I'm also interested in using spiro for variable fonts, but had basically given up: matching bezier output points sounds like a great solution tho'.
FYI: My current font is toybox here https://terryspitz.github.io/dactyl-font/explorer/public/index.html - note this recalculates spiros on every change in javascript compiles from F#!