Happy New Year!

2007 is going to be a good year: There will be many new things to learn. There will be many opportunities to love somebody. A lot of things wait for you to do them. So long, a happy new year to you all!

Raw Power

I rewrote the java based rasterizer that is used in the X peers of GNU Classpath. Heres some interesting numbers. Rendering a relatively complex shape (actually, the outline of a glyph vector) 250 times takes:

  • ~60ms on JDK1.5
  • ~780 ms on Cacao with the Cairo peers
  • ~350 ms on Cacao with the X peers and the new Rasterizer

Learned lesson: native code is not necessarily faster than java code. The whole rendering pipeline of the X peers is implemented in plain java. X only draws horizontal lines here.

The comparison with the JDK is not necessarily fair but gives an interesting impression what should be possible.

Find the test program here. Yes it is a microbenchmark that highlights one particular case (rendering complex shapes). I will make more interesting and comprehensive benchmarks as soon as I am able to run the Java2D and AWT benchmarks that ship with GNU Classpath.

One Laptop Per Child?

I am reading more and more about that OLPC thingy. I’m asking myself, who needs this? Who has thought out this crap? In my opinion and experience as father, the last thing that a child needs is a laptop (with my definition of a child beeing <= 10 years old).Sorry folks, I don't get this. Here's my opinion on what our children really need:

  • Parents. This does not mean that they have to be the physical parents. ‘Nuff said.
  • Time to learn. Nowadays many parents seem to assume that children must learn early and everything. What is really happening is that they project the pressure that _they_ experience in life (and most likely don’t feel capable to deal with) on their children and think they do something good when the child learns to deal with it early. Sorry, there’s no good here. Overloading children only has the effect that it makes them passive. The first thing you must keep in mind is that children actually _want_ to learn. Let me give an example. I was told many times by my own parents that my son must learn walking (back when he was <1 year old) so I should teach it to him. I said, no, he first must learn how to crawl (is that the right english word?). And he learns walking himself. So, instead of taking him by the hand and pulling him (despite that he simply could not stand for himself) I let him do what he actually can do and learn own his own. And yes, he learned walking completely on his own. No need to push him. After all, this enabled him to experience himself how complicated it is to stand on two legs and to put one foot after the other. And you should have seen him how proud he was: 'Look! I am standing here. And now I am making one step after the other' Wow! What a great experience. Don't take this experience of learning themselves own away from your children!
  • Childhood. No kidding. AFAICS, god (yeah yeah) made the children so that they play. Now what good is it to hammer all kinds of knowledge and abilities into them for what they were not made? Sure, later in life they need alot of this. But you must understand that playing is how children learn living. Their play is very much like our work. In fact, it is real work for them to play. Let the children play and don’t push them in the adult world too early.

On the contrary, I think that children don’t need:

  • Floods of information and media. Personally I have banned TV and radio from our household. The only music that plays is some good records or (better yet) self-made music. We all like to sing. My son is enjoying to play his drumkit (and he’s good at that! wow) as well as singing (loudly. too loudly sometimes 😉 ) and all kinds of music. There’s no asking for TV or radio at all. I can’t stand people who say that children need TV. That’s pure bullshit. My tip if you have hyperactive kids: Throw out the TV and radio. Do it! There’s only shit coming out of it anyway, and you don’t want to load stockpiles of shit on your children, right?
  • Plastic toys. What sensual experience is plastic? None at all. It’s clean, its flat, its boring. The best thing is some real wooden sticks or some earth and water. Nothing expensive. Really. Ok, this means you have to clean the clothes a little more often. In the summer I try to let my son play naked to avoid this problem. I guess he’s coming into an age where that is not an option anymore. That’s life.
  • And certainly, kids don’t need a computer. What good is that? What should they do with that? Learn how to play with an automat? Or, learn calculating or writing with it? Sorry, the computer is by far the worst teacher or playmate that I could think of. There’s really no use for computers for children under 11 years or so. Don’t get me wrong. I DO think that our kids need to learn how to deal with computers. But they need to learn this when it’s time to learn this. When they are adolescent for example.

I can’t hear all that crap that is coming out of the ministries of education, that children have to go to school early (<=5 years) or that children need computers early (<= 5 years). It makes me sad that I get into a situation where I have to go through real efforts because I don't agree with the general opinion. I want to decide how my child grows up and I don't want some minister to decide what's good. I don't want to grow up zombie kids.

Man, I am really upset.

Edge Detection

Last time around we were able to detect edges and link them in order to detect stems and serifs. In the meantime I have made another nice picture of the glyph ‘C’ with its segments:

The last thing we need to do before we can actually hint our glyphs is to detect edges. Edges are sets of 1 or more segments that are positioned (approximately) at the same position. For the vertical direction and the glyph ‘M’ this would look like this (every edge marked with another color):

These edges are then associated with our Blue Zones (where possible). Later we will move these edges around to fit on the grid (rather than moving single points).

Next time it will become interesting: Then we will start the actual grid-fitting process.

Hint!

Let me insert a small break in my series of font lectures to show the latest and greatest screenshots. Just today I got the first hinted text rendered (left without hinting, right with hinting):

Both are rendered using Sun’s Graphics2D impl with anti-aliasing turned on (via Graphics2D.fill(Shape) ). The outcome is quite similar with Cairo though. Unfortunately I haven’t found a rasterizer yet that can render this thing properly without AA. Classpath’s Cairo backend doesn’t support turning off AA right now and Sun’s rasterizer fails to render this nicely without AA, although I’m sure that the outlines are ok now. But Graphis2D.fill(Shape) is not exactly a font renderer though. I haven’t tried the X peers with the Java-only rasterizer yet. I will try this soon though.

Update:

Francis was so kind to quickly implement support for non-AA rendering. Here comes the comparison for rendering hinted text without AA. Left Sun, right Cairo (yes!):

This seems to confirm that the general hinting is mostly ok. The missing curve segments in the e and o are quite certainly to blame to Sun’s rasterizer. However, there are definitely small glitches in the hinting still, visible in the W, r and d glyphs.

Here are some more unsorted screenshots on my way to a hinting implementation:

A little accident:

A little accident

Some glyph outlines with the original (red) and hinted (green) shapes magnified to show the grid-fit:

Again, the ‘e’ glyph, where hinting was a work in progress. I made this screenshot for debugging purposes. Notice how the middle horizontal stem got accidentally collapsed:

While working with this I stumbled over a bug in Classpath’s Cairo peers when trying to render a shape magnified. Is this abstract art? (This should have been the ‘e’ glyph above).

Segments

We finished the global feature analysis last time and now get into the local (outline-specific) feature analysis. As a first step we detect so called segments. A segment is a set of consecutive points that form a approx horizontal or vertical line. The detection of segments is not too complicated. Simply iterate over the points of an outline and find points that have an in or out direction close to one of the major directions (up,down,right,left). The deviation of the angle must not be > arctan(1/12). Then group consecutive points with the same direction into segments.

Where it gets interesting is, when segments get linked to each other. Every segment can have zero or one ‘opposite’ segment. To find these linked segments, we compare each segment with every other segment to see if they are sufficiently close to each other and have a certain overlap in their major direction. The outcome of this is that we can now easily detect stems and serifs. We have a stem segment when s1->link == s2 and s2->link == s1. OTOH, we have a serif segment when s1->link == s2 and s2->link != s1. Look at the following diagram, which shows a typical serif. Segment A is linked to segment B (because that’s closest to A). But Segment B is NOT linked to segment A. So the segment A is forming a serif. The same is true for segment D. OTOH, segment B and C are linked to each other. They are forming a stem. This information is important for the hinting process; serifs and stems have to be rendered at a certain span, and all serifs and stems in a text should be the same width usually.

BTW. This is a good time to give some credits. This hinting implementation has been developed by David Turner and Werner Lemberg of the FreeType project. I am only studying their code, preparing a(nother) paper and doing a presentation about it and adapting it to Java. I have to say that I am really impressed by this work of genius! If this interests you, the original paper has a nice high-level overview.

Stems

Last time we looked at the blue zones. The other characteristic property of Latin fonts are the standard stem widths. Stems are the (basically) horizontal and (basically) vertical lines in a glyph. I.e. the glyph for ‘l’ normally has one vertical stem. In order to render glyphs smoothly, it must be assured that all stems are ‘snapped’ to approximately the same width (normally one pixel; unhinted glyphs tend to show 0 – 2 pixels instead).

So, in order to find out the standard width of the stems, we analyse the glyph for the character ‘o’ which proves to be very reliable for stem width detection. The diagram below shows how this glyph is represented as set of bezier points and control-points that ultimately span up the glyph.

Our algorithm first runs the local feature detection on this outline (explained later) which yields the segments of this glyph. Segments are sets of consecutive points that align approx. horizontally or vertically. The glyph ‘o’ below has 8 segments, each made up of 3 points. The local feature detection also ‘links’ pairs of segments to each other. Two linked segments form a stem. We have 4 stems in the ‘o’ glyph, which are highlighted in the diagram. Now it’s easy to get the standard stem widths, which is the distance between the segments that form the stems of our test glyph ‘o’.

BTW: If you don’t know what I’m talking about. I made two interesting screenshots that show how unhinted text is rendered. Left is without anti-aliasing (horrible) and right is with anti-aliasing (ok-ish but way to blurry). These screenshots are made with Classpath’s Java-only-TrueType implementation rendered with the Cairo backend.

Give me the Blues

Let’s continue with the automatic hinting. One characteristic property of (Latin) fonts are the so called Blue Zones. Think of the Blue Zones as the lines in your notebook from the 1st class in school when you learned writing. Translated to fonts, a blue zone is a horizontal stripe within which all points must be aligned to get evenly rendered text. The following diagram illustrates the six blue zones that are calculated in Freetype and Classpath for Latin fonts:

The blue zones are (from top to bottom) SMALL_F_TOP, CAPITAL_TOP, SMALL_TOP, SMALL_BOTTOM and CAPITAL_BOTTOM (collapsed into one zone) and SMALL_MINOR.
The above diagram can be a little misleading, as it seems to imply that these zones are lines. Which is not true. A blue zone is a thin stripe that envelopes the maxima of certain test glyphs. For instance, in order to find out the CAPITAL_TOP blue zone, we analyse the glyphs for the letters THEZOCQS. The maxima of their top points span up the blue zone as illustrated in the next figure:

Later in the hinting process we align all points within such a blue zone at a fixed height. This smooths out the vertical hoppledihopp that is visible in non-hinted rendered TrueType fonts.

Stay tuned to find out how the stem widths are comuted and what else there is done in the autohinter.

Come, die with me a little

Komm stirb mit mir ein Stück. This is the title of Wenzel‘s first LP back in 1986, still in the GDR. Last weekend I had the pleasure to meet him in a concert nearby. I must say that I am very impressed by this german bard. There’s still this youth and love and passion burning inside him. He manages to create a very special athmosphere, all alone on the stage. You know, when time stands still, this would be a good moment for the earth to stop turning around and you think you want to die a little. It’s a pity that so few people know him. Only < 50 people were visiting this concert. If you ever have the luck that he's performing near you (only likely when you live in germany. He made a US tour once with his english album Ticky Tock where he sings songs of Woody Guthrie though) then I strongly recommend you to go to the concert.

For the christmas time he was so nice to present us with one good song: Wenn wir des Nachts

Learning to Write

So I am looking into the automatic hinting right now. I always find it easier to grok something when I explain it to others, so let’s explain what I am doing right now. The automatic hinting process can roughly be divided into 3 phases:

  1. Global font analysis: Certain important properties of the font are determined and stored. The important properties for Latin fonts are the standard stem widths and the so-called blue zones. The former is the usual width of the character stems which has to be the same for all glyphs when things should look good (you know a non-hinted glyph when you see some stems 1 pixel width, others 2 etc). The blue zones are characteristic horizontal stripes, comparable to the lines in the notebook in your first year in school (namely these are capital-top, capital-bottom, small-top, small-bottom, small-minor and small-f-top. you can make up from the names what stripes these are). Later, all points that fall within one of these stripes is aligned. (Again, when you see non-hinted text the height of certain characteristic points is not regular). All this is not really performance critical as it is only performed once per font and not on each rendering of a glyph.
  2. Local glyph analysis: For each glyph to be rendered we need to detect the so-called Segments (points that form an approximately horizontal or vertical line), Edges (sets of Segments that all lie approximately on the same line. For instance, the glyph W has three segments at the top which frequently form an edge) and Stems (Segments that form the characteristic vertical or horizontal lines. For instance an I character has 1 vertical stem – which makes up the whole glyph for sansserif fonts). This is performance critical as it is done in realtime when beeing rendered.
  3. The actual hinting: With the information collected in step 1 and 2 we can now move around the outline points of a glyph so that it fits the target grid. The goal here is that points that fall within one of the blue zones get aligned into one height and points that make up a stem are moved so that all stems have the same rendered width. When this is done, the location of the remaining points of the glyph have to be interpolated so that the glyph is rendered smoothly.

I find it interesting to see what is performed behind the scenes on a normal desktop computer only to get the nice TrueType rendering that we got used to in the past couple of years.

For GNU Classpath I have already implemented most of phase one above which I will finish and test really soon plus some bits of phase 2 because that is actually needed for phase one too, after all, what is done in the global phase is to analyse a couple of characteristic glyphs.

More details to follow soon…