# Older blog entries for raph (starting at number 387)

The election

I'm still in a state of shock. I think things are going to get quite a bit worse before they get better again. I also think this outcome is likely to be bad for free software in many different ways, including strong anti-American sentiment around the world, shoring up of corporate power, and a general devaluation of the public interest as an important factor in political decision-making.

Curves: Ikarus

Ikarus is a near-legendary system for digitizing outline curves for fonts. I had a copy of Karow's 1987 book explaining the system (complete with FORTRAN source code, no less), but somehow managed to let it go. I've been meaning to get back to it for a while.

A month or so ago, I wrote that I was pretty sure that Ikarus used Hermite splines. In response, haruspex disagreed and said it was circular arcs. I was dubious because assigning one circular arc between each pair of adjacent knot points yields an overly rigid numerical system.

It turns that we were both right. The actual Ikarus system uses a hybrid approach. The first step is to fit a cubic spline to the knot points (with weighting based on distance between knots, to improve cases when the knots are not evenly spaced). However, from this phase, only the tangents are preserved; the spline curves themselves are discarded.

At this point, you have position (the original input) and tangent constraints for each knot. Those constraints uniquely determine a biarc for each segment between two knots. Since a biarc is made up of two circular arcs (tangent continuous at the join), you have an extra degree of flexibility that avoids the rigidity I was worried about.

So now I can state clearly the similarities and differences between Ikarus and my Cornu-based approach. They both try to fit a smooth curve through the input points, and both work in two passes, the first of which finds the tangents and the second of which draws instances of the primitive geometric curve. However, I use a Cornu spiral segment where Karow uses a biarc, and I choose the tangents so that the curvature of the final curve is continuous. Ikarus, by contrast, chooses the tangents so that the curvature of the intermediate cubic polynomial is continuous. By nature, you can't make biarcs continuous in curvature, but Karow's solution certainly counts as a rough approximation of that goal.

I need to make a visual illustration of the differences, but I expect the Cornu approach to be better in all respects. Cornu spiral segments, while resembling biarcs (and having precisely the same control parameters) have smoother variation of curvature. Similarly, I expect the tangent solution to be more accurate, not least because it guarantees curvature continuity of the final curve. When there is a large number of points (Ikarus recommends one knot for every 30 degrees of arc, and the illustrations in Karow's book seem to be even finer), the two solutions should be nearly identical. However, I think you can get away with about half as many points with the Cornu spline without sacrificing smoothness. That should make it easier to maintain high quality while editing and otherwise distorting, as well as the obvious savings in time because you don't need to enter as many points.

Btw, the Ikarus book also clears up my hazy memories about previous spiral approaches to curves. I thought there was a historical spiral format due to Coueignoux, but the one I was thinking of is actually by Purdy and McIntosh. A survey paper by Lynn Ruggles has all the details for the curious, or read the patent.

Update

I spent this last week in the Boston area, visiting a customer site. The work went well, so I'm feeling pretty good about the trip.

While I was there, I had dinner with Norm Megill (of Metamath fame). I'm really glad I finally got to meet him in person. While we have had a great correspondence solely over the Internet, there's nothing like really getting to know a person. I want to make more room in my life for this kind of thing.

Cross-platform UI design

There's been quite a thread on the recentlog, with contributions by elanthis, haruspex, mathrick, and davidw.

I'm not claiming that my way is necessarily best, but for the time being I am building a separate UI for each platform, and trying to factor as much as possible into platform-independent code.

And so far it seems to be going well. It helps that (at least so far) my app is not very "UI-heavy", meaning that I don't have lots of buttons, menus, special widgets, and the like.

There's some duplication, but actually less than I expected. I deal with duplication all the time when I code. When Excessive duplication is a sign that the code needs re-factoring, and I generally find I can do that. On the other hand, if such refactoring would add more bloat with the new abstraction layer or whatever than saved by eliminating the duplication, it's maybe not such a great idea.

I also want to make a distinction between the problems of coding, which I don't mind, and problems of building and packaging, which I do. I expect that my lightweight C approach, without taking on lots of dependencies to libraries, scripting language implementations, and so on, will generate small, simple executables (or app bundles or whatever the hell platforms want) that should be generally pretty easy to build and package.

I've been thinking about these issues a bit, so...

A small rant about building and packaging

It's not hard to get a program written, compiled, and running on your own development system. It is generally harder to get that program packaged so that others can do development on it, and so that end users can get it installed correctly.

The problem gets a lot worse if you want your program to be cross-platform. Most IDE's and other development tools have a strong tendency to lock you into a specific platform. For example, I generally find using XCode pleasant, but it's not really helpful if you want to deploy those projects to other platforms. I'm sure the reasons for encouraging lock-in are more political than technical, but I also think there is a technical issue at the core.

An analogy comes to mind. Many, many programmers feel that they shouldn't have to deal with manual memory management. A good implementation of garbage collection in the runtime avoids the time investment needed to match up all the mallocs with corresponding frees, not to mention avoiding the problems that inevitably happen when the programmer gets it wrong: memory leaks, double-free and similar bugs, and, in many cases, security holes.

I actually don't feel this way strongly about memory management, at least for the type of programming I usually do. Typically, I spend so much time and effort working out the algorithms that I don't really mind the additional time needed to nail down the memory management. And, of course, since most of what I do is very performance-sensitive (2D graphics), I really appreciate the control over things like memory layout, with its strong implications on cache efficiency and so on. But if I were doing a different kind of programming (say, focussed on user interaction), I could totally understand the feeling. Why spend the time?

And I do feel that way about the build and packaging issues. Why should I have to spend a significant fraction of the time it takes me to write a program to write makefiles, config scripts, and so on? Further, why should I have to do so much more of that work if I want my program to be cross-platform, even though for the most part the algorithms should be equally valid on any platform?

To make matters worse, I consider most of the extra packaging work to be man-made, and quite ephemeral. Twenty years from now, I think there will still be runtimes with manual memory management, for which carefully crafted code is still useful (I grant that GC runtimes are likely to gain in popularity, though). However, I doubt that .pbxproj directories, MS Visual Studio Solution files, or the like will still be of much use.

Interpreted languages, or JIT bytecodes for that matter, have the potential to solve some of these packaging issues, but just being interpreted is nowhere near sufficient. I want to be able to take a source directory, press a button, and have ready-to-use packages for Linux, Win32, and Mac pop out. By "ready-to-use", I mean that the end user doesn't have to manually install prerequisite packages or libraries (as is almost invariably the case with, say, Java). In theory, it shouldn't be hard to do something like this; you just glue your source directory to a template that contains everything you need, and tar it up in whatever package format the target system expects.

When it comes down to it, though, even using an interpreted language doesn't buy you all that much. Cross-compiling C (or, for that matter, most any currently popular language) into x86 or PPC machine code is a solved problem. As far as I can see it, the only thing that's really missing is the will to actually make an infrastructure for cross-platform package building.

Life

Things seem to be calming down a bit. Thanks to everyone for the good words and support.

Fonts

I lamented a few weeks ago about the sad state of free fonts. That post seems to have touched a chord. I've not gotten a large number of emails and so on, but what I have received is deeply felt.

And I now believe there is an answer to many of the problems I posed, mainly the lack of community support for the kind souls who wish to contribute to the world by releasing high quality fonts under the principles of free software. I now plan to release my fonts under the auspices of TeX Users Group.

Karl Berry and I have been in touch, and he's interested in implementing some of the ideas I sketched out to make the presentation of free fonts more appealing. I'm sure he'd be interested in help, so if you feel like volunteering, drop him a line. Probably the existing fonts page would be a starting point, but as you can see it could definitely use some sprucing up.

I also plan to move my archive of specimen book scans to tug.org, who have the space and bandwidth to host the 5G or so of high quality 2400 dpi scans I've made so far, with hopefully more to come. I'm only hosting 200 dpi scans on my personal site, but have been fulfilling a steady stream of requests for the higher res versions.

The thing that I really like about TUG is that it's a respected organization, with a good history and a solid existing user community. If people like the fonts I release, I encourage them to donate to TUG. They'll use the money well in any case, including, with luck, funding font designers who contribute their work. I definitely have no plans to become rich from this flow of funds, but money is important as a token of acknowledgement of the value of the work, if nothing else.

This is all very tentative so far, but I wanted to keep interested people in the loop. Possibly Karl and I (and others!) will do some kind of formal annoncement sometime in the coming weeks.

haruspex: yes, I have seen the parameterizable shape paper, but I wasn't entirely blown away by it. The fonts are pretty good, but definitely not up to the quality of, say, Adobe's. My main concern is the same as with Metafont: it looks like it requires some serious rocket science knowledge to get really excellent results out of it.

Cornu spiral

I'm on fire about my new thesis plan. The core idea, of course, is to make a smooth interpolating spline using segments cut from the spiral of Cornu. There are so many interesting directions to take from that starting point, though. Is there always a curvature-continuous solution for any set of input points? If so, is it always unique (modulo crazy windings)? Can you add tangent constraints (like you'd see on rounded corners) without sacrificing curvature continuity, perhaps by using higher-order polynomial spirals? How does the Cornu primitive relate to MVC curves, or for that matter to French Curves? I'm defining smoothness as low variation in curvature, but is that really what the human visual system sees? I want the answers, and really look forward to the process of finding them, and writing that up.

Meanwhile, my interactive curve editor is coming along nicely. I've gotten some nice ooohs and aaahs over demos and the latest screenshot. The code is knocking at the casing of my hard drive, desperately trying to escape.

Cross platform UI

And since I'm interested in getting the editor out to a larger audience, I've started thinking about cross-platform UI development. I'm pretty happy with the C-language libart/gtk+/x11 framework I'm using, but there are a lot more Mac and Windows users out there, especially in the graphic design world.

There are a few cross-platform frameworks to choose from, but I don't find any truly compelling. By all rights, Java should be the answer to what I'm trying to do, but I'm definitely not convinced that the user experience will be anywhere nearly as good as it would be for a native app. As long as we're talking about deployment in a browser, Flash is seductive, but has nowhere nearly the free software support it needs.

Wx would be fine for just getting an app launched with the menus and windows, but it doesn't have an abstraction for high quality drawing, even though all the target platforms do (libart, Quartz, GDI+).

So far, I'm leaning towards just replicating native UI code for the three major platforms, but even within the context of an OS X native app, there is a bewildering array of choices. Cocoa or Carbon? If the latter (which does make sense given the choice of C language and desire for portability), use kEventWindowDrawContent or make a custom HIView to take advantage of the compositing framework? Unarchive the UI from a NIB or use C code to build it?

If I go this route, I'll need to factor the code into UI dependent and UI independent parts. That's probably good discipline in any case, especially if I'm hoping for the code to be adapted into other apps that need curve editing (Gimp paths, inkscape, etc.).

It's just frustrating that there doesn't seem to be a "best practices" for this kind of thing. I know I'm far from the first to try to wrestle with it.

Life

I'm going through a bit of a rough patch right now. Heather and I are trying to keep the divorce amicable, but now it's looking likely that we'll need to bring in adversarial lawyers.

Emotional turmoil like this does bad things to my productivity. I'm trying to keep work obligations and fun stuff balanced, and mostly managing, but hopefully my dear readers will understand if this diary is a bit thin these days.

I'm not asking for help - I have a great network of friends who are helping me through this. But maybe it wouldn't hurt to think good thoughts in my direction.

Fonts

I've gotten some very nice feedback on my recent posts about fonts, especially my musings on juicing up the web presence of free fonts and free font developers. Thanks!

I've been making steady progress on my Cornu spline editor. It now handles both corner and smooth points, has undo, and can save (but not yet load back). There are still lots of rough edges in the code, so I'm not really feeling like making a release right now, but hopefully soon. When I do, I'm also likely to ask for help porting the code to other platforms so that I can get more feedback from graphic designers. Probably the most bang for the buck will be an OSX package with gtk and libart libraries, for use with the native X server.

3 Oct 2004 (updated 3 Oct 2004 at 07:24 UTC) »
Curves, curves, and more curves

My obsession with curves shows no sign of abating. Fortunately, there's a good chance I can harness that energy towards at least one of my life goals. I'm now seriously exploring the possibility of doing a "small but beautiful" PhD thesis on smooth interpolating splines, with Carlo Sequín at Berkeley.

I still feel the trust metric work is valuable, but emotionally it's very difficult for me to stay motivated. Among other things, it's very difficult to explain that work to others, much less convince them that it's worthwhile.

Meanwhile, I now have a rough interactive app for drawing with Cornu splines. Take a look at a screenshot, or try building from source (libart and Gtk1). It's not optimized for speed, and it's not yet numerically robust, but you can get a pretty good sense of how it's going to work. I drew the letter R freehand, without even looking at a reference image. I think it turned out fairly well, and the relation between the point placement and the resulting curve felt quite a bit more intuitive than Bezier editors I've used.

haruspex wrote:

IKARUS' circle fitting method is actually well damped, and behaves much more like the second example (as does METAFONT's IIRC).

Metafont I'm very, very familiar with. The technique I use (solving for curvature continuity at knot points) is directly adapted from Hobby's Metafont work, and from what I've seen so far, the numerical behavior of the Cornu spiral segments resembles Hobby's cubic Beziers fairly strongly. Obviously I need to study the Ikarus book, but my feeling is that if it's damped the same way as Metafont and the example I posted, it can't be based on rigid circular arcs.

I'm willing to tolerate a significantly larger number of primitives in this internal representation than either input through the UI or exported into a font file format after all manipulations have been done

Doesn't this have some major implications for hinting? I get the impression from FontFocus that stroke-oriented hinting is still a favoured approach.

Ordinarily it would, but I think traditional hinting is becoming obsolete. You really don't need it at all for printing as resolution is going through the roof. FontFocus doesn't care at all about the underlying geometric primitive, because it doesn't distort the curves at all (it works by tweaking spacing and scaling in the x direction).

Ankh wrote: (good to hook up with you again, btw!)

I'm reminded that the Folio/F3 system by (I think) Jakob Valdez added conic sections to PostScript's primitives, which is why NeWS, which used F3 fonts, had an extra codeblock argument to "pathforall". The F3 font hinter had an excellent reputation, anf F3 fonts were typically smaller than TrueType for a roughly comparable (hard to measure) quality. Sorry if this is off-topic, I haven't been following Advogato after it went off-line for a while.

Not at all off-topic. I'm releasing all my curve code as GPL, and there's a chance some of it will hybridize with potrace. In any case, to the extent that Folio/F3 is an improvement over TrueType or Type 1, I am very optimistic that splines made from Cornu spiral segments will turn out to be even more of an improvement. Right now, that's a gut feeling, but if I do my thesis on it, I expect to be able to show it definitively, using both analytical and aesthetic arguments.

Fonts

I have a bunch of fonts in the pipeline, and finally got around to making a page so you can view the progress. In most cases I've posted FontForge files as well. The one major exception is Centaur (Museum), which I'm unsure exactly how to handle. One idea I'm toying with is approaching Agfa/Monotype (holder of the Centaur trademark) and propose doing an authorized "pro" version of the font.

There's not much community support for free font development. On the typophile boards I get a strong sense that freeware fonts mostly just poison the well for type designers trying to make some money for what they do. I'm not sure whether it's better to go with the flow, or try to be a crusader for the cause of free fonts. Certainly, a webpage for free fonts (with nice organization, "test drive", and other features common to commercial font sites), but with forums and other features geared towards supporting free font developers, rather than merely exploiting their work, would be a great step in that direction. But I don't think I'm the right person to create such a site; there are lots of people who have the skills needed.

UTF8

mathrick: yes, I agree that real UTF8 support is worthwhile. It shouldn't be that hard to add - mostly just need to tweak the code to transcode Latin1 to UTF8 when it reads in legacy XML files. Not sure when I'll get time to work on it, but in the meantime I would accept a patch :)

Curves

haruspex wrote (in context of advocating circular arcs as a curve-drawing primitive):

That's a good point. But rather than having the user think about the circles, I wonder if they could use the abstraction of a digital spline and ducks (the non-mathematical meaning of spline). I suspect this is what Dr Karow had in mind when he came up with IKARUS' curve model.

Very likely it is. I think we're vehemently in agreement that drawing a curve using on-curve points (as in Ikarus) is good UI, as long as everybody is happy with the curve drawn between the points.

I will argue the superiority of Cornu spiral segments over circular arcs visually[*]. Here you see the same sequence of points fit both by tangent-continuous circular arcs, and by tangent- and curvature-continuous Cornu spiral segments. The main lesson here is that the perturbation of the middle knot damps out very quickly as you traverse (S-shaped) Cornu spiral segments, but doesn't damp out at all with the circular arcs. I think this is true in general, not just for the example shown here. The tangent continuity constraints for circular arcs propagate like a gear train: tweaking the angle up on one side of the arc pushes it down by an equal amount on the other side.

*Note to self: tweak mod_virgule code to allow high-ranked diary authors to post <img> tags inline.

There has been a certain amount of work duplicating the traditional spline-with-ducks. The relevant mathematical abstraction is an elastica. A good introduction is given in the paper Euler Spiral for Shape Completion. I think it's a nice curve with most of the properties you want for curve design. The big one that it's missing is scale invariance; in the physical analogy, you need a thinner strip of wood to wrap around tight corners than broad curves. For boats, that's not a serious problem, because it's rare for curves to have sections of both very tight and very broad curvature, but I believe that's a much more serious problem for fonts and other curves used in 2D graphics. The Cornu spiral shares many desirable properties with the elastica, and is scale invariant to boot.

There's a bunch more material I haven't had a chance to study yet at Shin Yoshizawa's page.

nomis wrote:

Unless I misunderstood you, your assumption about a maximum of two intersections for two (180°-angle) cornu segments is wrong. Have a look at this image which shows three intersections. Since I don't have a tool to easily create cornu segments I used the image at mathworld for the shape of the cornu segment. The second segments (red) are flipped and 90°-rotated versions of the first segments.

You are right and I was wrong. I still believe my intuition is correct that intersections between two Cornu spiral segments are more economical than corresponding intersections between two Bezier curves, (especially cubic, but I think quadratic also), but the details are trickier than I first guessed. Among the many subtleties is the question of how to measure "degrees of arc" for an S-shaped curve segment (i.e. one containing an inflection point). I don't think I'm going to try to solve this problem right now, but it should make a hell of an exercise for the reader :)

Can you point me to some more in-depth literature? My knowledge is basically limited to the mathworld entry and I am curious on the parameter set used to pick a certain segment of the cornu spiral.

The best literature I've found for Cornu spirals is the Euler Spiral for Shape Completion paper mentioned above. They have a fairly hairy algorithm for choosing the parameters (based on first fitting a biarc, then doing gradient descent to find the parameters for a Cornu spiral segment with similar endpoint tangents). I worked out a much simpler solution to the same problem, for which I can refer you to RTFS. I do want to explain this in more detail, but my queue for doing writeups is pretty clogged up right now.

The ease of affine transformations for bezier segments basically stems from the fact, that all points on a segment are a linear (even convex) combination of the control points. I wonder how to transfer at least some of this ease to cornu segments.

The short answer, I think, is that this ease does not transfer. The affine transformation of a circular arc is an elliptical arc, and that cannot be represented exactly by Cornu spiral segments, only approximated. Thus, my current plan is for the low level representation of curves to be a high resolution sequence of quadratic Beziers. By high resolution, I mean that I'm willing to tolerate a significantly larger number of primitives in this internal representation than either input through the UI or exported into a font file format after all manipulations have been done (most importantly affine transforms, stroke offset, self-intersection removal, and possibly special effects such as "antiquing" as well).

In your diary entry from august 13th you mentioned a presentation from siggraph. Interesting read. I think this would be awesome for interpolating the coordinates of a quick mouse movement which sometimes result in jaggy brush strokes with a paint tool

Yes! In fact, this problem is closely related to autotracing, of which potrace is currently the most advanced free solution. I have some ideas here, which I'm hoping to write up in an email to Peter Selinger soon. In very brief outline, the steps are:

• Get a polygonal approximation of the source shape; this takes some doing when you're starting from a bitmap, but if you have a mouse or pen stroke, you're already there.
• Numerically evaluate curvature along the path.
• Find a sequence of points along the path such that linear interpolation between curvature sampled at these points is a good approximation to the numerically evaluated curvature.
• Use these points as input to a Cornu spline fitter.

There are more subtleties for dealing with corners and the endpoints of smooth curve sections, but I think the basic idea has lots of potential. In particular, finding a good linear approximation to curvature will tend to put knot points at curvature minima and maxima, which I believe is exactly where they belong. I also think you'll get very graceful curve simplification behavior as you use decrease the number of points and get a looser linear fit to the curvature profile.

Curves

haruspex, nomis: it's great having this discussion with people who care about curves and the UI's for editing them.

haruspex wrote:

The fact is, any geometrical figure - ellipse, circle, parabola - is irrelevant to the problem of fitting a natural, drawn curve. Pure geometric shapes (with the exception of straight lines) rarely occur in a letter outline, so I disregard them as modelling test cases. Instead, I ask, how well can this primitive deal with a pre-mathematical, natural curve, as might have come from the designer's hand? How awkward is the translation? (Your curve continuity arguments are relevant theoretical ammunition here I think, although my assessments are usually subjective, not objective.)

Absolutely. I wasn't trying to say that an ellipse had any special status as a smooth curve, or that its simple mathematical representation has any relevance to the question of smoothness. However, I do believe it is an example of a smooth curve.

That said, I could probably have come up with a better example, for example, an "S" curve. Whatever curve primitive you use has to interpolate between a fairly tight negative curvature on one side and a roughly equal positive curvature on the other, with an inflection point somewhere near the middle. Obviously, some fonts have smooth S curves, and others don't. Cubic Beziers are actually pretty good at making an S curve, in my opinion. Certainly, it's not uncommon in professional fonts to see a single Bezier traverse from a vertical tangent in the upper left corner to another vertical tangent in the lower right.

And here, I believe, circular segments don't necessarily do a good job. If you try to do it in two or three arcs, you'll be able to see the knots pretty clearly. The S in Computer Modern has three, and suffers badly from it in my opinion.

The UI makes a pretty big difference when designing with circular arcs, too. Most of the masters I've seen from Bitstream have the centers of the circular arcs explicitly drawn. If you draw the main slope of the S with, say, eight arcs, then the centers should describe a fairly continuous path in and of themselves. In the hands of a master designer, I'm sure that using one circular arc for every 15 to 30 degrees of the original curve can lead to some of the cleanest, smoothest curves you can imagine. But if you don't do a good job visualizing the radii of curvature, and put the tool in novice hands, my guess is that you'll see bad curves.

To sum, cubic Beziers do a good job fitting smooth curves, such as the main body of an S, but it's also very easy to draw unsmooth curves. Circular arcs take more primitives to fit the same curves, but, at least with good discipline and a good UI for visualizing curvature, result in much more reliably smooth curves.

I think the Cornu spiral has a good chance of combining the best of both primitives. A single Cornu spiral segment can make a pretty darn good S all by itself. Conversely, I'm hoping that any unsmoothness that results from drawing a curve from curvature-continuous Cornu spiral segments was placed there deliberately, or at the very least, should be obvious to a moderately trained eye just from looking at the control points. [this last property is related to the property I mentioned last time of maintaining smoothness when the control points are perturbed, but is expressed more in terms of user experience than math.] I don't believe any other geometric primitive can come close to claiming all these properties.

nomis asked what a UI for Cornu spiral curves might look like. While there are no doubt many ways to do it, my first cut is going to look something like this. Basically, you just put down a series of on-curve points. Math fills in the rest. I like to keep things simple.

nomis also wrote:

The point I am trying to make: I don't think that the fundamental primitive is that important. It is the way we present it to the user that makes the difference.

I very much agree that the UI is important, more important even than the choice of primitive, but I still feel there's a strong case to be made for a primitive which yields very good results with a small number of control points.

That having said: Cornu splines obviously will be approximated with e.g. beziers at some point, so we are actually talking about user interface here... :-)

Not surprisingly, one of the first things I've implemented is a converter from Cornu segments to quadratic Beziers, but that transformation is not as inevitable as you might think. The killer advantages of Beziers are ease of affine transformation and subdivision (using De Casteljau), the latter of which is especially nice for rendering. That said, the Cornu spiral is remarkably well behaved for being a "special function", and it's probably not anywhere nearly as painful as you might think to work directly in the space of the Cornu parameters. The key property is that the motion along arclength goes at a constant rate with respect to the parameter; with Beziers, it's not hard to set up curves for which this motion goes through or near zero, which results in numerically fairly tricky curves. Also, two cubic Beziers can intersect at up to nine points, while I think it may be true that two Cornu spiral segments each traversing no more than 180 degrees of arc intersect at no more than two points.

Also, thanks for the kind feedback on FontFocus! Your eyes are sharp - it does indeed work in the X direction (on vertical stems) but not in the Y direction (on horizontals). In general, having an uneven baseline or x-height line is a pretty serious artifact, while subtly distorting widths and spacing isn't. It might still be worth playing around with, though, especially for non-latin scripts.

haruspex wrote:

I think it's long been clear that Beziers are not a good user abstraction for curve editing - but what's wrong with circle segments between on-curve knots, as chosen by IKARUS, METAFONT, et al? I am not sure anything could be more natural. I suppose the Cornu could be seen as a French-curve style extension of circles. I think I need to write that experimental path editor I always planned, to play with these alternatives :)

What's wrong with circle segments? I'll tell you what's wrong...

But first, while circular arcs were the basis of some font formats (most notably Bitstream), they were definitely not the primitive of Metafont, and I'm not sure about Ikarus either. Metafont's primitive is the cubic Bezier, just like PostScript, but, unlike Type1 fonts, Metafont lets you do stroking with elliptical pens and constructive area geometry.

From what I've been able to learn about Ikarus, the IK file format itself just specified corner points, tangent points, and on-curve points. It was basically up to the application to figure out how to fit an actual curve to those points. Certainly, circular arcs would be one approach, but I suspect that Hermite splines may have been used as well.

Now, in order to argue which geometric primitive is best, I have to define the goals. One such goal is that it be expressive, meaning that, given an arbitrary smooth curve, I can fit it with a relatively small number of primitives (each with a relatively small number of paramters). Love or hate them, cubic Beziers are awesomely expressive.

And circular arcs do not have this property. You need quite a few of them to closely fit an ellipse, say. Take a look at some Bitstream designs -- you'll see a great many more control points than in a typical Type1 font.

I believe that curve smoothness is best defined as variation in curvature. By this metric, circular arcs are not that great; as you follow a curve, you'll have constant curvature along arcs, but a discontinuities at the joins between arcs. Of course, the more arcs you use, the less the discontinuity, but that's true of just about any primitive. Heck, you can make a decent enough outline from straight lines if you're willing to use enough.

Beziers can in fact be made to be curvature-continuous, at joins as well as the interior of the primitive. In fact, one of the central themes of John Hobby's work on Metafont was a global optimizer to choose tangents at knots to minimize curvature discontinuities (technically, for reasons of numerical stability, his algorithm zeros out the discontinuity in "mock curvature", a linear approximation to curvature, but the difference is subtle).

But Beziers are not naturally curvature continuous. In fact, my experience is that it's very difficult to design smooth Bezier curves by eyeball, especially as more control points are added. This is a subjective criterion, but I think it's possible to quantify it, as well: how well does curve smoothness hold up when you perturb the control points (or other parameters)? In general, if you start with a smooth Bezier curve, perturbation will make it worse.

This criterion is especially important when you're dealing with meta-fonts (of whatever flavor). In fact, Adobe's use of linear interpolation of cubic Bezier control points in their Multiple Master technology doesn't even guarantee tangent continuity, much less smoothness. It can be made to work well, but requires care and skill.

By these criteria, segments of the Cornu spiral are an excellent primitive. They are expressive in a way that circular arcs are not (in particular, you can cut from the central segment to make a very pretty "S" curve), while at the same time a Hobby-style global optimizer to determine the tangents can guarantee continuity of curvature across the whole curve. Variation of curvature is linear along the interior of the primitive, so you can't get wide swings there either, as you can in Beziers.

It also helps that the Cornu spiral representation is so concise - the primitive is fully determined by the endpoints and tangents at the endpoints (six degrees of freedom, as opposed to four for straight lines and eight for cubic Beziers). I believe this will help make the user interface both simple to learn and productive to use.

And I am hacking on a pattern plate editor, so if you're patient you will be able to play with it before too long.

Personal

I haven't said much here except for hints, but it now looks like Heather and I are getting divorced. We hadn't talked about it with the kids, but yesterday Alan asked some direct questions, so now he knows. I didn't want him learning about it by someone saying, "hey, I read on your dad's blog that your parents are getting divorced, sorry to hear about it." Stranger things have happened, though, I suppose.

Other than that, things are reasonably good. I was at a post-birthday party for my longtime friend Dan Rice on Saturday, and had a great time.

The spam in my mailbox is rather out of control. I'm experimenting now with a gmail account. If you want to contact me there, use the firstname.lastname@gmail.com convention.

Fonts

Fonts have been my friend through all the turmoil. I've been active on the typophile discussion board. Also, I was pleased to see some of my previous postings on fonts picked up by typographica and Luc Devroye.

My Century Catalogue is coming along well; I have all alphanumerics and a bunch of punctuation, but have to draw a bunch more fiddly shapes to fill out an AdobeStandard encoding vector. I'm also playing around with Centaur, an astonishingly beautiful font, and have a rough draft of the capitals.

I've also been playing with the Cornu spline (PDF of the curve) as a primitive for curve design, and am now absolutely convinced that it's better than Bezier curves.

FontFocus

And now for something of a dramatic announcement. The secret font rendering project I've been working on can now be discussed publicly. Ladies and Gentlemen, I introduce FontFocus.

We're primarily looking for commercial licenses of this technology, but also plan to sort out some kind of free software release soon. I personally would love to see this rendering technology integrated into a good web browser.

Scans of font books

The British Library is doing it right: they are making their high quality scans of Shakespeare editions and other rare books available for all. Most other rare book collections are much more proprietary about their holdings.

The Million Books project has scans available of two landmark font books: the ATF 1923 specimen book and the Manual of Linotype Typography. I've had trouble with the DjVu viewer (it seems to hang Safari on my Mac), but these look like good resources. Of course, I have many of my own scans of the ATF 1923 on my own site. I've done the original scans at 2400 dpi, but don't have the big scans up on the server (it's about 5G worth of data right now). Maybe I should contact the archive.org folks to see if they're receptive to hosting my scans.

13 Aug 2004 (updated 13 Aug 2004 at 22:36 UTC) »
Musings on fonts

I've been kinda immersed in fonts for the past week or so, and have some things to share with you font nuts out there.

First, I've picked a font revival to work on: ATF Century Catalogue. I think this may be one of the most underappreciated fonts out there. It's definitely a representative of Beatrice Warde's Crystal Goblet theory of font design, as opposed to all the ego-driven stuff work churned out now.

In particular, I believe an adaptation of Century Catalogue is an excellent candidate for a font to supplant Computer Modern as a font for setting math. In addition to aesthetic beauty, an important consideration is continuity with existing traditions of math typography. A great many math texts in the last century have been set in Monotype Roman No. 8, of which Knuth's Computer Modern fonts are a reasonably accurate digital revival. But this is far from the only font well represented in the literature, nor, arguably, the best.

The model that Knuth acknowledges as the most aesthetically pleasing is Volumes 23 and 24 of the Transactions of the AMS (see p. 20 of his book, Digital Typography). The sample he shows appears to be set in a variant of Monotype Old Style (not exactly No. 2, as the tail of the 'c' in the latter are curved up more). Even so, he doesn't like some aspects, for example the angularity of the italic 'x'.

I agree that the shape of the italic 'x' is important - indeed, to me, it strongly connotes variableness, in much the same way that a copperplate gothic connotes the style of a banker or lawyer, or Old English Gothic connotes an old-style newspaper banner.

So, after looking at dozens of fonts, I've concluded that Century Catalogue is the one. The roman resembles the Monotype Old Style fairly strongly, but is in my opinion better drawn (by master typographer Morris Benton Fuller). In addition, its italic (which is more closely based on ATF's Baskerville Italic than a member of the Century family, but is nonetheless stylistically quite coherent with the Roman) is much closer to what people now expect from math fonts.

Gain

Perhaps the biggest complaint about Computer Modern is that it's too light. Both the weight of vertical stems, and the relative weight of serifs and hairlines compared to the vertical stems are lighter than mainstream text fonts.

When I got my copy of Knuth's Digital Typography, I was struck by how much better it looked than most of the TeX output I'm used to seeing, especially from laser printers. I now believe I know the secret: press gain, probably in this case introduced deliberately to make the body text look good. You can see the effect pretty clearly in my 2400dpi scans.

What is the best primitive for curve design?

Most 2D curve design (including fonts) done today uses cubic Bezier splines. Almost all of the remainder is quadratic Beziers. There are other choices, and I wonder if some might be better.

In particular, I find it tricky to make smooth curves when there are a lot of control points. I'm sure it gets easier with practice, but I'm not sure people should have to adapt to the underlying polynomial nature of the spline, when perhaps smoother, more natural primitives exist.

For example, Ikarus used Hermite splines, in which all the control points lie on the curve. In Beziers, you have to position the off-curve control points so that they "magically" adjust the curve how you want it.

From what I can see, the main reason inexpertly drawn Beziers look unsmooth is large variations in curvature, both discontinuities at the knots and in greater deviation in curves than needed to smoothly connect the endpoints. I'm thinking of building a tool that graphs curvature along the path of an outline. I have little doubt that this tool's output would reveal much less variation and discontinuity in splines drawn by experts than by newbies.

So, to me, the most promising approach is to use a primitive that has smoothness of curvature built-in, so that by default it's easier to draw smooth curves than unsmooth. Of course, it should still be possible to do the latter, but I have no problem with making it require more control points than an equivalent unsmooth Bezier curve.

The most promising primitive I've seen so far is the "circle spline" of Carlo Sequin and students [SIGGRAPH PowerPoint presentation]. Near the end of that presentation, he raises the possibility of using a Cornu Spiral, which is mathematically constructed so that curvature is continuous at endpoints, and linearly interpolated in between.

For those more interested in this issue, John Hobby's paper "Smooth, Easy to Compute Interpolating Splines" is a must-read. My gut feeling is that his work is good, but that replacing his choice of cubic Bezier as a primitive with a circle spline or Cornu Spiral may give better results. He found that making curvature continuous can yield instable results, so he uses a linear approximation which guarantees stability. I wouldn't be surprised if this instability would go away with a better primitive.

Ripoffs

The Wikipedia is fun (and I've been contributing a bit to it), but one of the things that really irritates me is how ripoff sites usually manage to get higher Google rankings than the real thing. Most people don't know better, and often link to the ripoff pages, further strengthening their rank.

It's not just the wikipedia, of course, even though that's a notable and recent case. If you go searching for free fonts, you don't come across many sites of people who've put time and effort into creating, collecting, and critiquing the fonts, but you sure do find the ones that aggregate thousands of fonts (most of which are ripoffs of proprietary versions themselves), then presumably make some money off ads and whatnot.

I'll be releasing the math fonts under some form of free license so that they can be included in Ghilbert, of course, but it would be nice if there were some way to discourage them from being ripped off. If I continue to make fonts, I'm tempted not to release them freely, partly because of the ripoffs, and partly because free fonts are seen as junky.

378 older entries...