This note’s for you

Yesterday I did the antialiasing, which is needed especially for TrueType font rendering to look nice. Today I fought a little with window manager hints. I found it a little surprising that there’s apparently no standard way to open undecorated windows. Most toolkits seem to rely on Motif proprietary hints. There’s the other two options to make a Window ‘override-redirect’, which creates a Window without decorations, but also one that sticks in front of all other windows, or you can use one of the logical hints in the Extended Window Manager Hints spec, in this case I declare the window as TOOLBAR, which isn’t semantically correct, but does the job, at least under GNOME’s window manager.

Anyway, all this makes Swing apps look much better now (except for icons):

And it’s even quite snappy, considering that almost everything is done in Java.

BTW, I consider to attend the X developer summit 2007, and probably do a presentation about Escher. Not sure if I can make it though.

I was able to improve the antialiasing rasterizer significantly. So far I calculated the coverage on ‘intersection pixels’ by scanning each scanline 4 times (or any other power of 2 for that matter) and counting the intersections within each pixels. The coverage (delta) for each pixel is then calculated as count / max. For example, if we count 4 intersections in a pixel when we did 8 scans, then we have a coverage delta of 0.5 for that pixel.

So far so good. But it quickly turned out that this approach is flawed. Imagine for example a straight vertical line right through the middle of a pixel. The above calculation would result in the maximum number of intersections, and thus the coverage delta is 1.0 rather than the expected 0.5. Visually this looked like vertical edges are ‘cut off’, in contrast to the horizontal edges which are smooth.

Luckily this problem can be solved without any penalty. I only needed to account for the actual intersection point inside the pixel. So now I not only count the intersections, but also add up the ‘fractions’ that the intersections create. I can increase the accuracy by a factor of 16 (or more, but I reserve only 4 binary digits accuracy for the ‘horizonal’ coverage, and leave up to another 4 digits for the ‘vertical’ coverage). Of course, the actual math behind all that is slightly more complex than this, but you get the idea.

This makes the rasterizer good enough for rendering arbitrary shapes smoothly. Even TrueType glyphs can be rendered nicely with it. The following screenshot uses 4x scanning only with 16x horizontal resolution.

I proposed this rasterizer as possible replacement for the encumbered graphics rasterizer in OpenJDK. Let’s see if it turns out to be feasible. If yes, then it’s going to be interesting to solve the legal issues around it. I think the worst (and likely) case would be to do the copyright grantback dance with the FSF and provide the code to OpenJDK via the SCA. If not it’s going to be used anyway in the Escher AWT peers, in the JamaicaVM graphics backends and font rasterizer and hopefully soon in the Odonata toolkit (which has been proposed as new OpenJDK project, which is an exciting idea for itself).

I’m off now for two weeks, celebrating my birthday tomorrow and my marriage in a week, hurray! Must be my lucky year. Absolutely incredible so far.

These days I did what I wanted to do for a long time, that is implement an efficient anti-aliasing for the rasterizer of the Escher peers (this rasterizer can be used in arbitrary other scenarios as well though). This was mainly triggered by OpenJDK’s need for a replacement for their encumbered rasterizer, and I hope that mine is probably a good fit. Let me outline how it works.

Before doing anti-aliasing, let me show how shapes are generally rendered to a raster in general:

Basically, we scan the shape line by line, and at the intersection points we ‘turn on’ or ‘turn off’ the pixel at that intersection point. In order to do this efficiently, we first sort the edges of the shape according to their Y and X coordinates.

Ok, but what about anti-aliasing? Basically it’s the same, only that we scan each line more than once. Usually each line is scanned a -power-of-2 times, for example 8. Depending on how often we intersect the shape in a pixel, we can calculate a coverage value. This coverage value is then used as alpha value when filling the actual pixel.

The interesting part here is how the coverage values are managed.  A simple and naive approach is of course to store them in an array, one entry for each pixel. Now if we scan a line we proceed just like in non-AA rasterization and turn on (add 1) to the entry in this array that corresponds to the pixel when we ‘enter’ the shape, do the same for all pixel entries in between until we ‘leave’ the shape for that scanline. This is repeated for the same pixel line 2^N times. In the end we have an array that has the correct coverage values for each pixel.

Of course, iterating over the array and adding up the coverage entries isn’t exactly efficient. A better idea is to only store deltas. So, instead of adding 1 to all the pixel entries ‘inside’ the shape, we only add 1 at the entry pixel and substract 1 at the exit pixel. This is much better.

We must still iterate over the whole array though when we want to display it to the destination surface, to find consecutive chunks of equal pixels. Imagine that for a simple 600 pixels wide rectangle. Pretty bad. So what I did today and the last couple of days is design a datastructure that manages the coverage values in a much more efficient way. Basically, it is a simple linked list of deltas together with their X coordinates. This list is always sorted according to the X coordinates. Each time we scan a line, we insert one entry into that list for each intersection point. In order to find the insertion point, we do a linear search. A linear search? Haven’t we all learned that this is pretty inefficient. Yes. But here we make use of the fact that the scanline is always scanned in a linear fashion, from left to right, and that the list is always sorted. The data structure has a pointer to the last item that got inserted, and starting from there, it is not possible (or at least highly unlikely) that the next insertion point is more than 2 items away. When the next scanline inside the same Y pixel row is scanned, we ‘rewind’ the data structure to point to the first item again, and start searching there. Finally, when doing the actual rendering, we can simply iterate this list, and fill complete segments in one go. This can be quite efficiently implemented on most backends (for example, for a framebuffer it’s basically a simple memset operation when the color is opaque).

A nice side effect of this technique is that non-anti-aliased rendering can now be handled as a special case of anti-aliased rendering, with no performance penalty. Another little detail of the implementation is that the datastructure doesn’t throw away and re-allocate its entries, but keeps unused items for later reuse. This way, the scanline converter usually needs allocation, after some initial setup of its tables and structures.

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.

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:

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

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.

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.

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.

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…

During the last couple of days I finally got my hands a little dirty with hacking the first bits of the TrueType gridfitter for GNU Classpath. Gridfitting is a key technology in TrueType font rendering, as otherwise you might get very bad rasterization, with buckles and missing pixels etc.

My goal is to adapt the automatic gridfitter from FreeType in pure Java. This will bypass the TTF bytecodes that Apple holds patents on. This seems fairly straightforward as the FreeType code is nicely clean (well mostly), and even implements some kind of object orientation. My guess is that I
will have something working by the end of the year, maybe earlier.

I’m trying to design this carefully, so that we can probably plugin the real TTF gridfitter when the patent expires some day. For the start I will implement the gridfitting for Latin chars only, but leave room for extensions (this interface also adapted from FreeType) so that this can be implemented for CJK and other fonts too.
When this thing is finished, we will have a reasonable usable 100% Java font rendering stack in GNU Classpath, the core TTF engine by Sascha plus the rasterizer (AbstractGraphics2D) and the gridfitter by myself. This might not be of much use in a desktop Linux world, as we already can use the CairoGraphics2D and FreeTypeGlyphVector implementations directly. It will be useful however for embedded systems, all platforms where we don’t have FreeType/Cairo (.NET maybe?) and projects like JNode. And for people who happen to like pure Java, if only for the fun of it Stay tuned for updates.

PS: This work will even be accompanied by extensive documentation about the inner workings, as I have to do something like this as part of my study.