Older blog entries for raph (starting at number 392)

Thesis work

My thesis work is going great, although I'm now less in the mood to write about it publicly in detail, because I might seek patent protection on some of the ideas.

For one, I've started to seriously dig into the study of real splines (i.e. thin strips of wood and the like). I just got Love's Treatise on the Mathematical Theory of Elasticity and am trying to wrap my head around the math and physics concepts contained therein. I think it's possible to do as well as, or even better than, real splines, as long as you're not afraid of using advanced math to make the numerical problems tractable.

The math involved is mostly Calculus of variations. I came across it a little when I was a taking math classes over my head as a young teenager, so it feels like nice closure to actually be using it now.

Grayscale bitmaps

The response to my query on grayscale bitmap fonts was disappointing, to say the least. Hrant Papazian is working on a series of monospace grayscale fonts called Coda. He is offering to release them for free assuming the community gets its act in gear and is actually able to use them.

Why have grayscale bitmaps utterly failed to take hold? One theory is simply that they are too hard to design, but I don't think that holds water; there is now a small community of grayscale font designers producing very impressive work. A more disturbing theory is that, failing copyright or other "intellectual property" protection, the incentive to create the fonts has been missing. It's a strange quirk of US copyright law that typeface designs and bitmap images are free of copyright, while packaging a typeface design as "font software" (presumably, executable code rather than a static data structure) confers upon it the protection given to software in general. Thus, we have something of an testbed for a public domain utopia advocated by anti-copyright extremists.

And the empirical result of that testbed are devastating. The technological limitations of the early '80s created a golden era of monochrome bitmap design (most especially the work of Susan Kare for Apple and others). But as soon as technology made scalable fonts feasible (with the corresponding upgrade in copyright protection), bitmaps were abandoned as fast as possible.

Even in the scalable domain, we still have lots of effort poured into making hinted TrueType fonts as opposed to nurturing the development of unpatented font technology. It's the triumph of GIF and MP3 over PNG and Vorbis all over again.

I think there is an optimum level of copyright-style protection to serve the public interest. The current Mickey Mouse-dominated legal environment almost certainly errs on the side of too much protection. The experience with bitmap fonts provides another datapoint on the "too little" side. Who will make the case for the baby bear?

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!

Spiro

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.

Curves

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.

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

383 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!