CAD paper on interpolating splines

[raph]

This topic was imported from the Typophile platform

My paper for CAD Conferences is done. If you just happen to be in Reno on Jun 11, then by all means stop by.

The paper is entitled "Interpolating Splines: Which is the Fairest of them all?" It tells the story in some considerably technical detail about my explorations to make a spline based on curves even better than the Euler spiral (also known as Cornu spiral) I've been working with for years.

Part of the paper includes the results of the survey I did here a few months ago. Thanks again to all who participated in that.

Here's an image comparing the two splines. The new curve is in black, the Euler spiral spline in blue. You can certainly do the desired curve with the older spline, it would just need more points. A major goal in pursuing the new curve is to make it possible to create good results with very sparse points, which, in turn, is especially useful when doing interpolation and other forms of variation.

 

I don't want to put the paper up at a public URL until the conference (as that's my understanding of the proper etiquette), but if anyone here is interested, just drop me a note and I'll be happy to send a private link.

I haven't yet put it together into a tool useful enough to actually draw fonts with (there are issues with stability, and the numerical work is difficult), but I do think it's a promising path to explore.

[mr]

Forgive my confusion, but is this about spiros or a different family of curves? Are spiros the "Euler spirals" you mentioned?

I've been using spiros lately, and they certainly make quick design easier (for me, anyway), but I haven't had a chance to see how they turn out in the long run (compared to Beziers, of course). I like the way one adjusts a curve simply by moving a point or adding a point where you want it. So I'm interested how a different family of curves would compare.

[Tim Ahrens]

I'm a bit confused. What you refer to as "interpolation" has nothing to do with interpolating between different shapes, does it? I mean, this is not about MM-like blending of different weights or so?

In any case, I'd be very interested in your paper. Can you send me the link using my profile "contact" page? Thanks!

[miha]

Hi, Raph! I am also interested, and would be very happy if you sent me the link (via contact page).

>So I’m interested how a different family of curves would compare.
Me too, and I am actually doing first degree about this topic from a typographical point of view. Although there is a long way to go, and I still don’t know how exactly is visual Metafont going to look like :-)

[dberlowgone]

>A major goal in pursuing the new curve is to make it possible to create good results with very sparse points, which, in turn, is especially useful when doing interpolation and other forms of variation.

And what are very sparse points? I mean, points are never sparser than those required for a given shape, nor are they often less than sparse in professionally crafted fonts.

>... haven’t had a chance to see how they turn out in the long run (compared to Beziers, of course)...

And that's not considering how they turn out 'in the long run' converted to Beziers...

I'd suggest going back to the previous threads if you don't understand what Ralph is doing, and I suggest being quieter than I if you do. :)

Cheers!

[sgh]

Raph, this is very interesting. I would also like a copy of the paper. Thanks!

[William Berkson]

I am wondering how the work you have done, Raph, relates to Tim Ahren's effort to have a Bezier drawing program be constrained to 'nice curves'. Thirty five minutes into this presentation: http://blip.tv/file/1911354

[Thomas Phinney]

I'd love to read that paper, too.

DB, you wrote:

And what are very sparse points? I mean, points are never sparser than those required for a given shape,"

Yes, but that minimum sparseness can be dependent on the math being used. There's a relationship between the way the curves are described (mathematical representation), and what shapes are most efficiently described by a given kind of math. Think about the differences between cubic and quadratic Bezier curves, for instance....

"... nor are they often less than sparse in professionally crafted fonts."

Sure, but it's hardly unusual to be forced to put an extra on-curve point on the curve of an "s," is it? The minimal sparse curve is defined by the combination of the desired shape and the math being used to describe it. Sometimes the shape requires more than just the minimum on-curve points one needs for that class of curve... at which point it becomes a reasonable question where there's some kind of math that would work better.

Leastways, that's my way of thinking.

Cheers,

T

[John Hudson]

Thomas: The minimal sparse curve is defined by the combination of the desired shape and the math being used to describe it.

And how you intend to affect its rasterisation to a grid, i.e. how you intend to hint it.

I'm always happy to see new outline creation tools, but at the end of the day what matters most is the outline format of the font itself, and what one can do with or to that format.

I'm interested in seeing a couple of things:

Conversion quality from Raph's curves to cubic and quadratic beziers, or a proposal for a font format using his curves natively.

[Tim Ahrens]

Conversion quality from Raph’s curves to cubic and quadratic beziers

John, you can test that (at least for Euler spirals) if you get FontForge and the Spiro plugin, then generate a PS font.

I vaguely remember there is a variable somewhere that allows you to control how many Bezier poits are being used to represent the internal format. This is a sort of dilemma, of course: either you deviate from the desired shape because there are not enough points, or you deviate because there are many rounding errors.

Another problem is that it does not generate extrema but fixing that should be easy.

[dberlowgone]

>I’m interested in seeing ...Conversion quality from Raph’s curves to cubic and quadratic beziers,
Same here. Previous requests led to unexplaination.

>or a proposal for a font format using his curves natively.
That's just what we need. ;)

>Think about the differences between cubic and quadratic Bezier curves, for instance....
Yes? If a type designer digitizes both with a well wrought tool, the only difference is that the off-curve points are in slightly different places.

>it becomes a reasonable question where there’s some kind of math that would work better.
It does? Perhaps for people who don't know how to, or can't draw very specific curves. But in 20 years of facing every kind of curve from Beowolf to Zapfino, with no market-driven suggestion of a lack of efficiency or accuracy, there are far more reasonable questions than this.

>... either you deviate from the desired shape because there are not enough points, or you deviate because there are many rounding errors.
Sorry? Tim, you don't deviate from the desired shape unless, somewhere along the line, resolution makes it mandatory.

Cheers!

[William Berkson]

Tim, in your Robothon talk I linked above, you seemed to argue that the main problem with 'bad' curves was not their being Bezier curves, but rather too big a change in curvature at nodes joining two curves.

If this is so, then having the Euler curve is not necessarily any advantage, which I take to be David's view.

Now everything is in the end converted to Beziers in Raph's approach. I believe that Raph did illustrate this sometime here on typophile, and the conversion was very good. So I think the question of usefulness is really whether this tool--or the one you are developing, or neither or both--make it easier to get curves of the kinds that type designers want to get.

Since, as David says, we are in any case dealing with finite resolutions--2700 dpi or 96 dpi or something in between--many different closely related curves are equally "ideal". So the question is ease of use in getting curves you want.

[mr]

Tim, in your Robothon talk I linked above, you seemed to argue that the main problem with ’bad’ curves was not their being Bezier curves, but rather too big a change in curvature at nodes joining two curves.

I totally agree that the problem is with bad Beziers rather than Beziers, but if one has a tool that makes it easier to have continuous curvature, isn't that worth exploring? I'd be the first to admit that there are better curve-sketchers than me, but there are times when I spend hours trying to get a Bezier "good".

Of course a new curve family isn't going to magically make type design easy, especially when we have to convert to a different curve family for output, but I think new tools are worth exploring.

With regards to John Hudson's idea of "a proposal for a font format using his curves natively," my intuition is that evaluation of these curves is rather resource-intensive, especially now that devices like phones are using standard font technology. On the other hand, if they can handle Splinter Cell, maybe they can handle a few continuous-curvature curves. Bezier curves, in contrast, are extremely fast to evaluate.

So, Raph, colour me interested and send me a preprint.

[Tim Ahrens]

Tim, in your Robothon talk I linked above, you seemed to argue that the main problem with ’bad’ curves was not their being Bezier curves

Correct. I guess nobody considers Bezier curves "bad", and if Raph uses spirals internally and it leads to a useful curve editor then that's fair enough. The current conversion problems are obvious but are not impossible to overcome. Time will tell how well the approach of on-curve points without any tangents works in real-life design.

... but rather too big a change in curvature at nodes joining two curves.

Exactly. Not having (too big) a change in curvature, in other words continuous curvature, is not my own concept. Mathematicians call it G2 continuity. I guess it is one of the most fundamental characteristics of a harmonious curve and establishing G2 (or making it "built in") is the most important step toward "good curves".

Btw, this is a similar concept to what happens when we switch a node to "smooth" in FontLab: this means that FL enforces continuous diection, in mathematics this is called G1. Note that FL actively keeps the nodes smooth by secretly adjusting the other BCP as you drag the other. Smooth nodes are an application feature, not expressed in the curve mathematics and not even stored in the font files.

So, G2 is just the next logical step from "kink" to "smooth" and as you may guess, there is also G3: a continuity of the derivative of curvature. Sounds a bit over the top, but it expresses the difference between "bumps" or "dents" in the outline (think of the top left part of Palatino's c, d or f, where this is intentional) or a really very smooth curve. In my SpotOn tool, G3 is built-into diagonals, and the Harmonizer will soon have it as an option.

If this is so, then having the Euler curve is not necessarily any advantage, which I take to be David’s view.

If it helps to find curves that have G2, G3 and even G4 (if I remember correctly) then it is may be a ueful means to an end.

I see the main difference not in the mathematics used but in the "philosophy". One is the classic mathematical aproach of "something is given" (in this case, a set of points) and "something is to be found" (a curve through it). I am not sure whether this is the right approach for an interactive tool, however.
My concept is to say, the tool simply "does something" while the designer drags nodes/point/curves/lines until they get the shape they want. The "does something" could be anything. Although (or probably because) this gives me a lot of freedom, finding a good "does something" is quite a challenge. For me, the crucial question when developing a curve editor is: how does moving the points change the curve? This change should be predictable and traceable despite all the magic built-in smoothness.

[John Hudson]

[Drifting perhaps off-topic, since this no longer involves Raph's work.]

Tim, I've been testing your Harmoniser, and apart from problems with distorting serif structure, due to the tightness of the curves, it generally does what is advertised: makes nicely smooth curves. But there is a built-in problem with how it does this -- by adjusting the position of the on curve node -- because overall good letter form depends not only on the quality of individual curves but on the relationship between inner curves and outer curves. The Harmoniser frequently changes that relationship, by shifting the relative positions of extrema on inner and outer curves, thereby changing the nature of the stroke. In terms of Noordzijan stroke modelling, Harmoniser changes the angle of the moving front.

[mr]

Although (or probably because) this gives me a lot of freedom, finding a good “does something” is quite a challenge. For me, the crucial question when developing a curve editor is: how does moving the points change the curve? This change should be predictable and traceable despite all the magic built-in smoothness.

That's interesting, because while I see what you're saying, I find spiros less "action-at-a-distance-y". If I don't have the curve I want, I ask myself, where should this curve go instead, and I add a point there (or if there is already one nearby, I adjust it); with Beziers, on the other hand, I have to think which of the four relevant points (two on-curve and two off-curve) do I need to move, and where, to get the change I want. With a bit of practice, one learns to do this pretty easily, but it's not wholly intuitive (especially if the off-curve points are invisible -- ever used MS Paint's Bezier tool?).

By the way, Tim, spiros as implemented in FontForge with libspiro give a choice between G4 and G2 points. I use G4 points by default, but sometimes switch a few to G2 points when I want less smoothness (usually I just add more points closer together) or when my curve is unstable. Stability is certainly something that needs work (perhaps these new curves are better in that regard).

[raph]

I'll follow on with some images and other things when I'm on my home computer, but I did want to address a few of the questions.

Spiro is based on Euler spirals, but with some refinement. The main thing is the straight-to-curve transition, which can't readily be done using pure Euler spirals. It also gives you a choice between G4 continuity and G2 (as Tim explained above). I used to use G4 for most of my outlines, but have more recently decided that it's virtually impossible to see the difference visually, so I can get just as good results with less effort using primarily G2 instead.

The prototype tool I built for the paper uses a slightly different curve than Euler spirals - it has a shallower variation of curvature near the inflection point (center of an "S" curve), and that gives both a more taut (less "loopy") response and also better locality. Moving a control point causes less rippling outward. However, this tool is just open curves - it doesn't do the straight-to-curve transitions, or even corners and closed curves, so it's not very useful for making fonts (yet).

I have an optimized conversion to cubic Beziers also, part of the spiro release. It's not well integrated with FontForge yet, and is very very slow (I've been hacking on both those issues, but haven't released the new version yet). The results, I think, are entirely suitable for real font production. However, I haven't addressed the issue of hinting at all. The resulting Beziers are clean and sparse enough that they're pretty easy to hint manually, but that doesn't help much in the case of variation.

And by variation, yes, I mean things like interpolating between different widths or weights, but I also mean adding parameters for things like extender height - something that Metafont handled well, but Multiple Master doesn't.

I know how to convert to optimized quadratics as well, but haven't actually written the code. For what I'm doing now, getting it into one industry-standard form is good enough. But perhaps quadratics are also interesting. Among other things,

You can see one example of a conversion from spiro to Beziers on: http://levien.com/spiro/

Thomas's description of sparseness is about what I'd say. I also have a fair amount of experience by now tracing outlines from metal type. Some representations require more points than others to get comparable results. In particular, evidence suggests that Spiro requires about half as many on-curve points as Ikarus, and lots and lots of real fonts got made using that tool.

A new font format is certainly an interesting idea, but getting apps to adopt it is well-nigh impossible. So mostly I'm thinking about this as a technique for mastering fonts, then generating industry-standard formats from those masters.

More later.

[John Hudson]

Raph: A new font format is certainly an interesting idea, but getting apps to adopt it is well-nigh impossible.

Certainly true. But it's time to start talking about fonts post-OpenType, and my opinion is that anything and everything should be on the table, including outline formats. We should know what all the options are, and catalogue their pros and cons -- both technical and 'industrial' (in the sense of what might target industries accept) --, before we start describing the kind of fonts we'd like to be making ten-to-twenty years from now. Last time around, we -- font developers -- didn't get much of a say about it, and despite the huge improvements of OpenType over 8-bit Type 1, we're still stuck with a format with inherent limits (particularly with regard to table sizes, and some of us are already hitting those limits).

[dberlowgone]

"...But it’s time to start talking about fonts post-OpenType..."
You are joking right?
"... before we start describing the kind of fonts we’d like to be making ten-to-twenty years from now..."
... we ought to be making fonts people can read today. I'm dazzled to hear you talking about anything past next month, but as things are going with the OFF std and technological cooperation among the 'competing' systems, there will be no need for another std, John, none whatsoever. Table sizes?! lol.

Cheers!

[John Hudson]

David, if you mean that the OFF standard will simply evolve continuously into a new format, then yes, that is one way it could go, although the result will be a giant mess of legacy compatibility issues: the MS Word of font formats. Within this framework, discussion is already under way about how to get past the 64k glyph limit and things like different vertical metrics requirements of different scripts, using composite fonts. Which of course raises issues of how to implement cross-font kerning and other layout intelligence. Doubtless some bright mind will come up with a solution to those problems, but in doing so will add layers of complexity to font development that wouldn't be necessary if the format were not saddled with that 64k limit in the first place.

Then there are the things that OpenType can do -- and hence the way in which they do them will not be changed, because inertia is the measure of success for a standard -- but does so in ways that are painfully difficult. Have you tried contextual interaction of dynamic mark positioning with kerning?

Then there are the incompatibility issues between different OT layout engines. Having a single font format standard is nice, but there is no single standard for implementing OT layout in systems and applications. I spent some time over the past couple of weeks helping a major software developer figure out what they were doing wrong in their OTL implementation, all the while with them complaining about the lack of an OTL implementation spec and lack of clarity in the OT font spec.

Nor is there anything like cross-platform compatible script and language support, and since the OT standard relies on system and application resources for such things -- without the option of AAT/Graphite-like font level implementation -- the ability to create text in your native language may be tightly constrained or even impossible, while you wait for your culture to become a priority for someone else's strategic marketing.

Yes, these issues can be addressed by hacking extensions on to the OT spec -- just as CFF PS support was hacked onto the TTO spec to create OT in the first place -- but its a heck of a lot cleaner to ask 'Okay, what have we learned from OpenType, and how can we do it better?'

[Tim Ahrens]

Following up on what I called my crucial question above, "How does moving the points change the curve?"

While playing around with Spiro, I noticed the following:

If I drag a point perpendicular to the contour then the contour is pushed in or out. Not surprising, and this is how you want a drawing tool to behave, of course.
However, if I move the point in the other direction, i.e. along the contour, then almost nothing happens. In other words: of the two dimensions you can move a point in, one seems to be "unused". Two degrees of freedom effectively controlling one. Isn't that redundancy a pity? I am quite convinced that redundancy is the root of all evil when it comes to curve editing. Another consequence is obviously that this increases the number of points that are necessary to control the shape.

I think an ideal curve editing tool (independent of the underlying mathematics) should make use of the two degrees of freedom in which the user can tell the computer the desired change. Dragging the curve or an on-curve point should control two things: pushing the contour it in and out, i.e. removing or adding black "material", but also pushing the material to the side, making the curve move out on one side and in on the other. This is what happens when you move the on-curve Bezier nodes, so at least in this respect they behave like you would expect it. Bezier splines have their oddities, of course, but if the computer helps the designer tame them they come pretty close to what I consider an ideal tool.

[raph]

Tim: interesting observation about moving points along the curve. In my experience, that's much more true for G4 points than G2, especially if the point is on a curvature maxima. With the G2 points, all curvature minima and maxima must occur at the control points.

And if moving the point really doesn't affect the curve at all, then perhaps that means some points could be removed.

I certainly agree that redundancy is a bad thing. As for the Beziers or interpolating splines are fundamentally better for designing fonts, that may come down to a matter of individual preference. Beziers are cool, and are of course capable of really good work. Serious designers like David have invested years into making them do exactly what is wanted. He no doubt avoids "bad Beziers" completely subconsciously.

I do suspect that the advantages of interpolating splines will come out more strongly when designing fonts with variation. Making a single Bezier outline G2 continuous (or nearly so) is not too hard if you have tools. Making a set of Multiple Masters that preserve that property across a wide range of interpolations is, uh, not so easy. Yet, with my interpolating splines, you get that by construction. I have only played around with interpolations a bit, because I don't (yet) have interactive tools for it, but so far it does seem much easier to get good results.

[dberlowgone]

John: Have you tried contextual interaction of dynamic mark positioning with kerning?
I hope someone gets your message in a bottle. Have you tried giving 80,000 users the same screen font? Specializing more in size and resolution issues, I've kept sending more and better illustrated bottles on my topics until, I decided maybe I misunderstood something, and started sending messages in battles.

John: ... if you mean that the OFF standard will simply evolve continuously into a new format [...] the result will be a giant mess of legacy compatibility issues...

I don't mean that the OFF standard should or could or will Simply evolve, or evolve at all. But I think if OFF is to influence typographic improvements for users, OFF should evolve enough to cover the 'mess' created from OT/ATT/Bravo's failure to evolve enough together, in the past, for the purposes required for the WWW. That is the point, isn't it? That would also be the point of an OFF2, with less baggage claimed. Its a heck of a lot smarter to ask ’Okay, what have we learned from Everything (including the stuff spiraling out of control;), and how can we do it better, rather than just thinking OT, which was broken by it's backward-leaning/looking birthing, I think.
And finally to your point; culture waiting to become a priority for someone else’s strategic marketing is over. Though I think you mean linguistic cultures, I unfortunately do not.

Cheers!

[k.l.]

J.H. -- Have you tried contextual interaction of dynamic mark positioning with kerning?
D.B. -- I hope someone gets your message in a bottle. [...] I've kept sending more and better illustrated bottles [...]

No need for wasting time on illustrating bottles. DecoType has done so already, both with their ACE technology and typefaces, Naskh and their new Nastaleeq. Another kind of illustration is a little exercise. Produce such a Nastaleeq in OpenType, with as few glyphs and with comparable layout behavior. Or, for beginners, do systematic mark attachment in Latin script fonts. (Doing some trials right now which involves not just usual class/exception kerning but also contextual kerning of all possible base-mark combinations -- a simplified case of "contextual interaction of dynamic mark positioning with kerning" --, OpenType's limitations beat back around every corner. Unfortunately these limitations are structural.)

Perhaps the most crucial point is to put more emphasis on the "open" in OT or OFF, as a platform that serves multiple specialized layout engines tailored around the needs of individual scripts, with special tables addressing each script and layout engine's logic. Maybe even additional shape description formats, like CJK may profit from stylized strokes. But then keep each of these closed and well documented so it is reliable for all parties.

Karsten