Font Rasterization for Mobile Devices
MSc Thesis
Lunds Tekniska Högskola
Advisors: Tomas Akenine-Möller
Completed: 2008-07-01
Abstract
Writing memory efficient and fast vector font rendering software for mobile devices can prove quite a challenge. This is the premise for this thesis. Two widely different vector based rasterizer algorithms were examined, one triangle- and one plane sweep-algorithm. Memory efficiency, speed and rendering quality was measured. To enable these measurements, the rasterizers were implemented in C and compared to each other, as well as to the leading open-source rasterizer found in the font rendering library FreeType.
It was found that the triangle rasterizer always used less memory than FreeType [3] for font sizes smaller than 60 pixels. The plane sweep rasterizer, in turn, was about 10-15% faster than FreeType, given the right parameters, when test run on a desktop computer. Depending on specific demands, either of the rasterizers described in this report can be useful for mobile systems, although the triangle rasterizer will probably benefit from the use of new technology such as hardware acceleration on mobile devices in the future.
Motivation
The memory size and performance in mobile devices increase very rapidly. Improved hardware open new possibilites for the quality and complexity of the device's software. We have more advanced text capabilities through J2ME programs, Web browsers, etc, than ever before. For a very long time text on mobile phones was rendered with bitmap fonts, but in recent years this has begun to change. More and more companies take the leap to scalable (vector) fonts to replace the old bitmap systems. This offers much improved rendering quality, but at the cost of greatly more complex text rendering software and rendering speed.
The main bottleneck for vector font rendering is the rasterization step. This thesis evaluated two rasterization algorithms and compared them to the (by far) most widely used rasterizer which is found as a component of the FreeType text rendering library.
Current techniques
Over the years there have been many rasterizers for outline fonts and vector graphics in general. They have been needed for almost as long as computers have had the capability to display any graphics at all. The target platforms have also varied a lot, so rasterizers tend to be rewritten to suit new demands and limitations. Basically, there are two main approaches to produce a bitmap from an outline, be it a glyph or any vectorial shape. One is the triangle rasterizer (which we call the Xorizer) and the other is the scanline rasterizer (which we call the Scanliner). The most common rasterizer type for text is the scanline rasterizer (also known as plane sweep rasterizer).
As mentioned before one perticular of the FreeType rasterizers, called ftgrays, is the fastest, anti-alias open-source rasterizer and by far the most used rasterizer today (except, perhaps, for the Microsoft Windows internal software). The techniques are not invented by the FreeType developers, though, but has been around for many years [1]. In fact, that rasterizer is based on another open-source algorithm found in libart [2].Triangle rasterizers are usually most useful in hardware accelerated rendering, where triangles are very quickly processed in hardware. A triangle rasterizer is actually not unlike the scanline rasterizer. One can even argue that the triangle rasterizer is a scanline rasterizer with the limitation that it can only handle triangles and not arbitrary polygons. There is truth to this; the triangle is (most often) traversed and drawn scanline by scanline. However, knowing that we are dealing with only triangles opens certain opportunities but sets some restrictions. It's not that common to use triangle rasterizers in font rendering solutions. Mostly these rasterizers are used for games and simulations where a lot of information is stored and interpolated for the triangles.
Our techniques
The two rasterizers implemented showed different strengths and weaknesses.The Scanliner
When memory consumption is not vital but correctness is essential, one would benefit from using an algorithm that computes the exact pixel coverage. Thus it gives the most accurate results. The Scanliner is just such an algorithm. The goal with this algorithm was basically to try to reassemble the scanline algorithm to utilize the best techniques of such solutions as FreeType [3], libart [2] and algorithms found in [1]. The result was about 10-15% faster than ftgrays both when tests were run on a desktop computer and a SonyEricsson P1i (UIQ).
The memory usage of the Scanliner was found to be the weak point. Even though it doesn't need much memory in most cases (about 16kB or so), it won't be able to complete its task unless it can hold all its intermediary data in memory before rendering to the target bitmap, and there is no way of knowing before hand how much data it'll need. The Xorizer is much more predictable and cheap to run, and even ftgrays can produce correct results with significantly less memory than the Scanliner.
The Xorizer
This algorithm is quite different from the Scanliner and much more resembles what you would call a "classic" triangle rasterizer nowadays found implemented in hardware on our GPU's.
Although the idea behind the Xorizer was not entirely new [4], a lot of optimization ideas, some based on very recent research, was implemented and evaluated. Most notably much effort was put into trying to benefit from the fast Bézier curve evaluation presented by Loop & Blinn [5]. Unfortunatelly this optimization only give a small speed boost. As mentioned above the Xorizer only needs a small amount of memory. But, even with all it's optimizations, it was still much slower than ftgrays and the Scanliner. However, it is believed that the Xorizer could greatly benefit from new graphics hardware which will soon be part of the standard mobile phone. The newly completed standard OpenGL ES is a very interesting platform upon which the Xorizer could be implemented, although this is left for future research.
Downloads
ThesisPictures
Comparison of output between our algorithms and FreeType's ftgrays.
Speed comparison overview. The black line (a) is the Xorizer and the red line (b) is FreeType with 3400 bytes of memory. The green line (c) is FreeType with 16k memory. The dotted lines (d) are the Scanliner with fine and coarse subdivision cutoffs.
References
[1] David F. Rogers, Procedural Elements for Computer Graphics. McGraw-Hill Book Co., Singapore, 1985, ISBN: 0-07-053534-5
[2] Mathieu Lacage and Raph Levien, The libart Library. http://www.gnome.org/~mathieu/libart/libart.html, 2001
[3] David Turner, Robert Wilhelm and Werner Lemberg, The FreeType Project. http://freetype.sourceforge.net/index2.html, 1996-2007
[4] Yoshiyuki Kokojima, Kaoru Sugita, Takahiro Saito and Takashi Takemoto Resolution Independent Rendering of Deformable Vector Objects using Graphics Hardware. ToshibaCorp.
[5] Charles Loop and Jim Blinn Resolution Independent Curve Rendering using Programmable Graphics Hardware. http://research.microsoft.com/~cloop/LoopBlinn05.pdf, Microsoft, 2005