Older blog entries for raph (starting at number 391)

Just testing

Not sure what happened to the recent diaries. I tweaked the db by hand and hopefully it will work now.

More later.

Grayscale bitmap fonts

Hand-drawn grayscale fonts have been an interesting idea for some time, but have never really caught on. They certainly take a lot more skill and patience to do well than ordinary bitmap fonts.

That said, I think they can fill an interesting niche in the 100-130 dpi resolution range, which is of course where the vast majority of all users live today. At lower resolutions (in particular 72dpi, which was standard for a long time), the grayscaling is quite visible, which can be distracting. At much higher resolutions (say, 200dpi), hand-tuning is a waste of time because outline fonts can deliver somewhere around 95% of the optimal contrast levels even without sophisticated hinting techniques.

And, indeed, grayscale bitmap fonts are starting to come into existence. Check out this thread on typophiles about Firefox text rendering, and this one about monospaced fonts for programming. Also see the bitmap critique forum for some striking examples of grayscale (and monochrome bitmap) work.

Can we use grayscale bitmap fonts on our free software platforms? In theory, we should be able to, because Freetype2 supports the grayscale bdf format, as I was able to verify with the ftview demo program and a hacked-up font. However, if I put that bdf file in /usr/local/share/fonts (with a corresponding <dir> tag in .fonts.conf), then "xterm -fa Graytest" bombs quickly with a floating point exception. I don't really feel like debugging that right now.

So, I want to know a few things. Is it possible, by hook or by crook, to get fontconfig-enabled apps to load grayscale bitmap fonts out of the box? If there are stupid bugs keeping that from happening, how do we get those fixed?

I sense there is something of a chicken-and-egg problem here. If there are no good grayscale bitmap fonts out there, then there isn't a strong motivation to build support into infrastructure and apps. Conversely, if it's nearly impossible to deliver grayscale fonts, why spend the time drawing them?

But it may well be the case that the energy barrier is not that high, and that with a little directed force, we can break through it. Does the community have the collective will to make this happen, or is this just yet another of my crazy ideas that nobody cares enough to do anything about?

Coins and stamps

Thanks to everyone who sent Alan coins, stamps, and emails in response to my begging. He really appreciates it!


I've tentatively chosen a name for my curve editor: Spiro. I posted a "code escape" here and on the Typophile forums. So far, I've gotten little or no response from my posting here, but lots of people checking it out and sending feedback on the Typophile board. Interestingly, many of the commenters are encouraging me to patent the idea and/or otherwise try to make money off it.

I'll have a new code snapshot soon. In the meantime I've been tracing the miniscules from 72pt metal Centaur (see screenshot). There's nothing like trying to use the thing for real to point out what needs improving :)

There's no rush, as I'm still tweaking the core algorithms, but obviously this is something that should go into other free software applications, most especially Inkscape. What I'm most inclined to do is release all the core code as GPL, package up nice Win32 and MacOS versions with refined GUI's (especially cut'n'paste with the dominant apps on those platforms) as commercial apps, and also try to license the code for inclusion in proprietary apps. We'll see how all that plays out.

Alan wants your stamps and coins

Alan has revived his blog after some period of inactivity. Lately, he's really been into collecting stamps and coins from various countries. He's gotten some from tor (Swedish), rillian (Canadian and euro), and Igor Melichev (Russian), but I figured the Advogato crew could help him out with lots more exotic countries.

He'd also like to get mail about stamps and coins, N64 games, or how he puts up with having such a crazy dad - send 'em to alan dot levien at gmail dot com.


I've been playing with my curve editor, tracing characters from old ATF fonts and so on. It's quite fun, and it seems to be a lot faster to get good curves drawn than Bezier-based editors.

There's always just one more feature I want to add before doing a release, but at the same time I want people to play with it, so I've put up a new code escape. You'll just need a Linux/Unix/Fink system with Gtk+ and libart installed. I'm always pleased to get feedback on it.

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.


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.


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


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.


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.


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.


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.


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.

382 older entries...

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!