Older blog entries for raph (starting at number 383)

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 :)

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.

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.

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.

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.

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.

The inestimable Paul Graham has another essay out: Great Hackers. Worth reading. Go ahead, I'll wait.

Back already? Ok, good. I find a lot of what Paul writes to be resonant. I especially liked his section on "nasty little problems" - I think the elimination of nasty little problems, as opposed to genuinely difficult and challenging ones, should be a top priority, especially for free software developers. Longtime readers will not be surprised to hear me categorize the auto* suite as a particularly rich source of such nasty little problems, for all that it does a pretty good job solving a set of real problems, and is a huge improvement over what came before.

Paul seems to be addressing the issues at the scale of individuals or small (startup) companies. I would like to see more attention given to issues at a much broader scale: the interaction between hackers and society as a whole.

One way for society to view its great hackers is as a resource, comparable to a natural resource such as mines for valuable metals, or fertile fields for agriculture. Most healthy societies try to convert the potential of those resources into wealth. They plant good seed and tend the land, rather than salting the fields. Of course, societies vary in the extent to which they do a good job of this; famine is much more common in Africa than in the West.

Societies vary even more widely in their ability to get good work out of hackers. Paul explains fairly well what's needed: mostly, let us do our thing and get the hell out of the way. I think his section "More than Money" tells part of the story. I don't think hackers hate money, but I do think we hate spending time hustling for money. There are plenty of people who do, and they tend to become investment bankers and the like. I don't think those people understand us very well.

Fonts

There's a fair amount of emotional turmoil in my marriage right now, and I've been taking refuge by spending time with a subject very dear to my heart: font design.

In particular, I've been scanning ATF type specimen books and carefully studying the designs therein. I now have a great scanner (Epson 4870), and the scans at 2400 dpi really pick up the detail, and let you see the quality of the printing.

I was especially surprised to compare the quality across the decades. I have four books, one each from 1912, 1921, 1934, and 1941 (all collected by my father). The printing quality from 1912 is head and shoulders above the rest. As a seat-of-the-pants estimate, I'd say it's roughly equivalent to a 2000dpi digital printer.

I've especially grown to appreciate the work of Morris Benton, the chief type designer at ATF for many years. I get the feeling that he was positively obsessed with printing quality. His father was a very gifted inventor, and worked on many machines used in type design and typefounding. In particular, his pantographic "delineating machine" and matrix engraver not only scaled a single design to many sizes, but could also apply general affine transformations, just like PostScript today.

One of the secrets revealed by close study of these specimen books is how type scaled to different sizes. Most fonts today are designed at one size, then enlarged or reduced using strictly mathematical scaling. Master printers over the centuries, however, have long understood that smaller fonts should have more robust features, while larger ones can be more elegant and refined. Periodically, type designers working with new technologies try to rediscover this fact, but it always seems like an uphill battle, probably because of how much extra work it takes to optically scale a font. Adobe is producing many fine optically scaled fonts now, but one gets the impression they're still a small minority of their entire font catalog. Another important example, from the world of free software no less, is the Computer Modern fonts of TeX, which, while technically way ahead of their time, are not considered especially appealing by serious typographers.

So it's especially interesting to learn that ATF used almost purely automated techniques to produce different sizes of font from a single "pattern plate". I came across an excellent article by Patricia Cost which explains the process in considerable detail.

I'll try to strip out the mechanical and historical stuff and just describe the underlying "algorithm". The scaling happens when a matrix (or mold from which the actual metal type with raised letter is cast) is engraved from a pattern plate.

The pattern plate is a piece of metal about 4 inches high, which contains a raised outline of the letter. Placed in the matrix engraving machine, a "follower," or stylus, traces the inside of this outline. The motion of this follower describes a path.

At the same time, a high-speed drill traces a scaled version of this path, cutting into the matrix. Through the mechanical ingenuity of Linn Boyd Benton, the scale factors can be different for horizontal and vertical movement. Typically, the pattern plate was designed for a 36pt font size. To cut a matrix for a 6pt letter, the x scaling would be a factor of 1.19 of the y scaling.

The path traced by the follower, though, isn't exactly the same as the inner outline on the pattern plate, nor is the outline of the letter engraved in the matrix exactly the same as the path of the drill. The follower has a nonzero diameter, so the path it traces is "shrunk" by half that diameter, so that the width of strokes is reduced by one diameter. Similarly, the cutting tool has a nonzero diameter, so the outline engraved into the matrix is "grown" by half that diameter, so that stroke width is increased by one diameter. When the ratio between these two diameters is the same as the scaling factor, the outlines correspond closely (especially if the letter on the pattern plate has slightly rounded, rather than perfectly square, corners), and stroke weight should be identical (after scaling, of course).

However, by using a smaller or larger diameter follower, it's possible to increase or decrease the stroke weight, respectively. And, after studying the font books, I see that the typefounders at ATF did consistently apply this technique for scaling fonts. A typical recipe would be to use a grow radius of 100/ptsize - 3 units (on a 1000 unit/em grid), while applying a horizontal scaling of 1.18/ptsize + .967 (both additive factors chosen to normalize for 36pt design). It's worth noting that the Computer Modern fonts use a width scaling of about 1.3/ptsize, so the stretch of smaller sizes is even more exaggerated compared to the ATF example.

I want to write this stuff up, but to do it justice will require quite a bit of time, especially to produce the illustrations. In the meantime, this image of two lowercase a's from Lightline should whet the appetite of you type fiends out there. The two images are superimposed with a "difference" blend mode, so you can see two outlines. The sharper image is an 18pt "a", scanned at 2400 dpi, and scaled in the horizontal direction by a factor of 1.15. The fuzzer image is a 6pt version of the same character, scanned at 2400 dpi, then enlarged by a factor of 3x. Thus, 0.001" at that size corresponds to 7.2 pixels. You should be able to see, then, that the 6pt version is grown by a little less than a mil with respect to the 18pt version.

The good news is that it wouldn't be that hard to adapt this process to the present-day practice of digital typography, and that it can be almost entirely automated, so generating a good family of optically scaled fonts wouldn't be that much more labor-intensive than drawing a single good font (which is difficult enough as it is!)

<placeholder>

I still haven't re-caught the blogging bug, for whatever reason. So I'll just weigh in with a few bits of personal trivia.

My mom just went back home to Virginia after visiting here for a couple weeks. It was a good visit - she and the kids get along famously.

Both the server hosting Advogato (casper2) and the original casper.ghostscript.com have had various problems as of late - the latter a failing hard drive. rillian has been doing the heavy lifting on recovering these systems, but I helped out some, including a laying-on-of hands to the physical servers (located at transbay.net in Oakland).

Experiencing such server failures, I can't help but think that the future will hold self-configuring high-availability features, especially for content repositories such as CVS and blogs. There's no reason why the data can't be replicated across several servers, and if one fails, for whatever reason, it should be possible to just throw it away and have the others take up the slack.

I think a large part of what makes P2P apps so compelling is the fact that, at heart, they are self-configuring high-availability servers, albeit with limited functionality. I'm most struck by BitTorrent's ability to resume a download (or upload, for that matter) even on a laptop which hops from one WiFi network to another.

I've also been spending some quality time with my collection of type specimen books. I'm enjoying rediscovering the beauty and engineering mastery that Morris Fuller Benton put into his classic ATF fonts from the first quarter of the last century. I'll happily write a blog post about what I've been finding if there is interest.

There are a couple of other things in my blogging queue, including progress on my Ghilbert proof language and applications of formal logic to programming. I may subject my reading audience to further thoughts on the economics of free software, as well. Feedback on which of these topics, if any, you're interested in hearing (or, for that matter, dread), is always appreciated.

Whew, it's been a long time since I've blogged. That's largely because of the site outage here, but also just inclination - after all, if I really wanted to, I could blog at my personal site.

I'm mostly doing well. Among other things, I'm really trying to put some time aside to finish my thesis. I had a great dinner last night (at the Blue Agave in Pleasanton) with Roger Dingledine and Rachel Greenstadt, during which we mostly talked about trust networks, stamp trading in particular, and how to make at least some of that work in the real world.

In any case, welcome back, everyone!

You don't see too much sign of it on his weblog, but Robb Beal is going absolutely wild researching issues around letter quality displays, and what it'll take to get free software to adequately support them. If you care about these things (which, from the response I typically get from my LQ blog entries, is rather improbable), he'd be a great person to get in touch with.

The near-letter quality and letter-quality devices continue to roll out. In the former camp is the Sony EBR-1000 book reader, which has an exotic monochrome 170 dpi e-ink display. The software is a mixed bag - apparently it has really crippling DRM, but on the other hand it's Linux based, so presumably people will be able to run good software on it. Hey, send me one and I'll see that Ghostscript gets ported.

One of the newest letter quality devices is the Archos AV500, sporting an approximately 200dpi 706x480 screen. The main app for this thing is playing movies stored on its internal hard drive. As far as I know, it's the first such device play at near-DVD resolution (and, in the 4" form factor, DVD resolution and letter quality are pretty much synonymous). The main competition in this field would appear to be the Portable Media Center platform from Microsoft, which as far as I can tell specs a 320x240 LCD.

LQ: What is to be done?

The issue of how to best support LQ displays is among the many things tor and I discussed. He disagrees with my proposal to have a global "pixels per px" (pppx) ratio for the entire display, and do pixel-doubling at a low level for applications which are not LQ-aware.

I see his point. Presumably, new LQ-aware apps are going to do the right thing, so having extra machinery for automatic pixel-doubling is just more cruft. Pixel-doubling is only relevant for older, legacy apps. I tend to use xv as something of a canonical example, given it's very old-school handcoded X interface (clearly, toolkits are for weenies), a website more than three years stale, a questionable license, and, last but not least, the fact that it's still my image viewer of choice.

Obviously, if you run xv on a letter quality screen, the 5 point fonts won't be very appealing. There are several ways to fix, or at least partially fix, the problem. Probably the way most consistent with the free software philosophy is to build an old-school, yet 2 pppx UI for xv, and patch it in. Of all the approaches, this one probably gives the best overall results.

Alternatively, you could do automatic pixel doubling, somehow recognizing that xv is not LQ-aware. You could do pixel doubling manually (this would, of course, be the most Unix-like way of doing things - provide an incredibly powerful array of tools for solving problems, but don't go 1/200th of an inch towards making them do the right thing by default). In the latter case, you'd have any number of different choices for implementing the pixel-doubling, including an Xnest-like application, running everything through VNC, and I'm sure others will think of more.

Other possibilities include ditching xv and upgrading to an image viewer which is LQ aware, or treating the entire dot matrix resolution X desktop as a retrocomputing target (it's worth noting that many emulators already do pixel-doubling, to adequately display really low res UI's on modern dot-matrix displays).

I still think that automatic pixel-doubling is the most user-friendly thing to do, but perhaps not implementing it is exactly the sort of mosquito bite necessary to motivate the army of Linux developers to fix their favorite apps to be properly LQ aware.

The pppx ratio should be a global configuration parameter

So, while I'm not going to make a strong argument about a pixel-doubling policy, I would like to make a strong argument in favor of explicitly promoting pppx to the status of global configuration parameter. After all, pixel-doubling is merely a stopgap along the road of true LQ support, while fucking up the pppx ratio will continue to make life difficult until my grandkids get sick of the situation and decide to do something about it. (and hopefully, while they're at it, will they please fix the last vestige of the backspace problem? That's generally ok in a Linux-only world, but still bites people when mixing with Mac OS X)

Unless people actually start listening to me, we most likely won't see a global pppx parameter, and so here are my predictions of the bad things that will happen.

Without an explicit pppx ratio, application writers will invariably attempt to guess it on their own, based on information such as monitor resolution information reported through the EDID channel. Inevitably, different apps will come to different conclusions, depending on the exact parameters, so the relative visual size of interface units will be even more inconsistent than today (however, inconsistent UI appearance is very much the X/Unix way, so maybe that doesn't bother people - perhaps I've simply been spoiled by the time I've spent using Mac OS X).

What are the different ways to derive a pppx ratio? I'm sure the most common will be to try to dictate the physical size of a px. If you read the literature on scalable user interfaces, you'll see many people advocating the "point" as the unit of user interfaces, which would effectively nail the pppx ratio to the monitor dpi divided by seventy-two. Other reasonable approaches would be to set pppx to 1 for dot-matrix displays, 2 for letter-quality, and flip a coin for intermediate values of resolution.

Worse, when people are unsatisfied with the pppx ratio guessed on their behalf, they will resort to even uglier hacks to work around it. If the pppx is derived from the monitor dpi, then people will figure out ways to lie about that, which will of course break other apps that actually depend on a correct value.

What's wrong with nailing a px to a definite physical size unit (for example, equating px with point)? In short, because not everybody has the same visual acuity. Software developers, who tend to be uniformly young and virile, easily lose sight of that fact. Currently, on almost all systems, the pppx ratio is fixed at 1, so users have a very handy way to configure the physical size of a px - simply choose a monitor resolution. On CRT's, this is easily done with modelines, but for LCD's, you pretty much have to choose that when you buy the panel. Even so, for most people the choice of an LCD is a fairly intimate, personal decision, and I imagine people consider the size of the px carefully, whether they're consciously aware of it or not. For me, low-res panels display blocky-looking text, and images are not crisp enough. For many others, on higher-res panels, text is too small. I wrote about this over three years ago; Apple was actually touting the low resolution of their expensive displays as a feature, which of course it is if your preference is a fairly large px value, and the only way to achieve that preference is through hardware choice.

Of course, the whole point of high resolution displays is to not have to make the tradeoff between desired px value and display sharpness (the third prong of the tradeoff, of course, is the added cost of generating all those extra pixels in the CPU and turning them into light, but Moore's Law should take care of that, in time).

If, as a software developer, you are tempted to fix the px to a definite physical size, then I suggest you go to your local bookstore, library, or church, and suggest banning all large print books and small print bibles. After all, readability studies have proven that 10-12 point text has optimum readability (for the average reader, anyway).

A bit of bitterness

Based on my experience in the world of free software, I feel reasonably confident predicting that we won't get the pppx configuration parameter right. If I were dictator of the universe, there wouldn't be any such problem, but of course that's not the way free software works, and for the most part that's a good thing. (the primary exception, of course, being the chain of keycode mappings applied to the backspace key - if it were up to me, I'd say that everybody should use the mappings that happened to correspond to the keyboard config I'm typing on now, and then of course the problem would be solved for everybody)

The world of proprietary software has been very good to me lately. I don't get to make the big architectural decisions (those are up to space aliens holed up near Redmond), but I do tend to get a lot of appreciation for my ability to solve problems. Money too, which is nice, but here I'm talking about appreciation.

Lately, I've been making gorgeous prints on inkjet devices (most of my work is on an Epson 2200). I love experiencing people's reactions when they see those prints, and the obvious impact that they have on people's decision to license our technology. It's a rush, a high, and I haven't felt anything like that from the free software world in some time.

I do, however, get emails like this one:

To whom it may concern, I have installed the ghost..garbage, and the gsvu garbage software, and it's a bunch of crap. It doesn't work nor does it convert ps to text. Go-on publishing your version after version-it's useless. Moreover, nearly everything you guys have published about it is a bunch of gobledee-gook that says nothing, and is repititious and loops back to nothingness. Why can't you do or say something useful that normal people can understand and use.

Leon Stambler

Another one that stung, perhaps more than it should have, was a recent description of Libart as having been written by a "monkey with a PHD in low level programming." When I started Libart, I had very warm, fuzzy feelings about solving problems of 2D graphics rendering for the benefit of the free software world. Now, while I'm pleased that some of the ideas of Libart seem to have made an impact, every time I see an app develop their own new graphics library, it bugs me a bit (xpdf's splash, sodipodi/inkscape's libnr, mozilla's gfx, qt's "arthur"), not to mention the fact that fontforge still doesn't do aa rendering, roughly five years after my gfonted prototype.

I'm not just trying to whine at the world here. I know I'm not great at coordinating distributed projects, especially with volunteers. What I am saying is that the free software community has a pretty serious process bug in that it's not very good at making use of my knowledge and skill at 2D graphics, nor at giving me back much in the way of "goodies" in return for my contributions.

So, looking forward at the professional work I contemplate, I find myself getting excited about the prospect of building a top-notch printer controller, to be sold as a part of real products. I do not find myself getting excited at all about solving, say, the printing problems of Linux.

That said, my feelings toward free software and the free sofware community are decidedly bittersweet rather than purely bitter. While I don't especially enjoy having my work NIH'd, I do appreciate and respect the culture of learning that so often leads people to code up their own solution to a problem rather than taking an existing solution off the shelf. Hell, I've been guilty of that enough times myself. Further, in the above I'm talking about my professional work. For other things, such as pure speculative research (including, most definitely, Ghilbert), it's impossible to imagine doing things in any other way than free software. Finally, as long as my professional work is Ghostscript, all of my code gets released under the GPL after a year in any case, so I could get as bitter and negative as I wanted, and everybody would still get the benefit of my work.

Apologies for whining. But I did want to get some of these thoughts off my chest, and I do think that writing about these issues is preferable to not writing at all, which is mostly what I've been doing.