Rasterization of vector fonts

Published on May 19, 2011

Rasterization of vector fonts

If you write programs for coffee grinders (refrigerators, ZX Spectrum, televisions, embedded systems, old computers - underline what you need), and want to use beautiful fonts, do not rush to save letters in raster format. Because now I will tell you how to make a rasterizer of vector fonts the size of a couple of kilobytes, not inferior in quality to FreeType 2 with hinting turned off.

The article will be interesting to those who just want to find out how rasterizer libraries work.


Vector fonts in SVG format


To make a rasterizer, you first need to understand how vector fonts work. I chose SVG as the main font format because it is based on XML and is perhaps the most readable and understandable for humans.

The first font I took for study is DejaVu Sans Mono Bold. Here's how it looks from the inside:

<? xml  version = "1.0"  standalone = "no" ?>
<! DOCTYPE svg PUBLIC "- // W3C // DTD SVG 1.0 // EN" "http://www.w3.org/TR/2001/REC -
SVG-20010904 / DTD / svg10.dtd ">
<svg  xmlns = " www.w3.org/2000/svg "  width = " 100% "  height = " 100% " >
<defs  >
<font  horiz-adv-x = "1233"  > <font-face
font-family = "DejaVu Sans Mono"
units-per-em = "2048"
panose-1 = "2 11 7 9 3 6 4 2 2 4"
ascent ="1901"
descent = "-483"
alphabetic = "0"  />
<glyph  unicode = ""  glyph-name = "space"  />
<glyph  unicode = "$"  glyph-name = "dollar"  d = "M 694 528 V 226 Q 757 235 792 274 T
827 375 Q 827 437 793 476 T 694 528 Z M 553 817 V 1100 Q 491 1092 460 1059 T 428
967 Q 428 910 459 872 T 553 817 ZM 694-301 H 553 L 552 0 Q 465 3 370 26 T 172
92 V 354 Q 275 293 371 260 T 553 226 V 555 Q 356
594 260 689 T 164 942 Q 164 1109 266 1208 T 553 1319 V 1556 H 694 L 695 1319 Q
766 1315 842 1301 T 999 1262 V 1006 Q 937 1046 861 1070 T 694 1100 V 793 Q 891
762 991 659 T 1092 383 Q 1092 219 984 114 T 695 0 L 694 -301 Z "  />
 
<! - ... omitted. ... ->
 
<glyph  unicode = "~"  glyph-name = "asciitilde"  d = "M 1145 811 V 578 Q 1070 518 999
491 T 848 463 Q 758 463 645 514 Q 623 524 612 528 Q 535 562 484 574 T 381 586 Q
303 586 233 557 T 88 465 V 694 Q 166 755 239 782 T 395 809 Q 448 809 498 798 T
622 756 Q 633 751 655 741 Q 771 686 864
686 Q 934 686 1003 716 T 1145 811 Z "  />
</ font >
</ defs >
</ svg >
 


The main part of the SVG format is the paths . They store most of the image information. The contour tag looks like this:

<path
d=" M 1145 811 V 578 Q 1070 518 999 491 T 848 463 Q 758 463 645 514 Q 623
524 612 528 Q 535 562 484 574 T 381 586 Q 303 586 233 557 T 88 465 V 694 Q 166
755 239 782 T 395 809 Q 448 809 498 798 T 622 756 Q 633 751 655 741 Q 771 686
864 686 Q 934 686 1003 716 T 1145 811 Z "
id="path4840"
style="fill:#000000;stroke:#000000;stroke-width:1px;stroke-
linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />


Style describes the color of the fill and stroke, id indicates the name of the path, and d is the path itself.

Stop ... wait a minute! Glyph tag from font:

<glyph unicode="~" glyph-name="asciitilde" d=" M 1145 811 V 578 Q 1070 518 999
491 T 848 463 Q 758 463 645 514 Q 623 524 612 528 Q 535 562 484 574 T 381 586 Q
303 586 233 557 T 88 465 V 694 Q 166 755 239 782 T 395 809 Q 448 809 498 798 T
622 756 Q 633 751 655 741 Q 771 686 864 686 Q 934 686 1003 716 T 1145 811 Z " />


Here it is. The shape of the letter (glyph) is described in exactly the same way as the contours of SVG. A full
description of the parameter d can be found in the specification , and I give a brief description below:


x_prev and y_prev - coordinates of the previous point
xc_prev and yc_prev - coordinates of the previous control point

Outline of the glyph and initial rasterization


Having the library at hand for outputting Bezier curves and converting the commands of the SVG path tag to the commands of this library, you can easily and quickly get the offline (stroke) of any glyph.

We have vector glyphs, and the screen is raster. This means that the task of outputting offline is to obtain an array of pixels from a set of segments and Bezier curves. It is very easy to turn segments into pixels, there are a lot of algorithms, they are good and different.

For Bezier curves, you can find many points of the curve by the coordinates of the start point (xz0, yz0), end point (xz2, yz2) and control point (xz1, yz1). This is done like this:

for (step=0;step<10;step++) {
t=step/10;
bx[step]=(1-t)*(1-t)*xz0+2*t*(1-t)*xz1+t*t*xz2;
by[step]=(1-t)*(1-t)*yz0+2*t*(1-t)*yz1+t*t*yz2;
}


As a result, we have an array of 10 coordinates of points belonging to the Bezier curve. Depending on the length of the curve from a complex system of differential equations, the number of points on which you want to split the curve is found (that is, the largest value of step).

However, turning Bezier curves into pixels by points is slow and bad. If the curve is complex in shape and long, then calculating the number of points will take a very long time. And if you draw a Bezier curve by points, and these points turn out to be less than necessary, there will be gaps in the offline glyph, which is unacceptable. Therefore, Bezier curves are divided into segments. The starting and ending coordinates of the segments are taken as the coordinates of the points lying on the curve. In most cases, this approximation gives good results.

How to determine the number of segments? I believe that it is enough to make the maximum value of step proportional to the difference between the start and end coordinates (for example, step = (xz2-yz2) / 100). By the way, for all the fonts that I met, with a glyph height of less than 32 pixels, it’s enough to split the Bezier curves into two segments.

The result of the rasterizer will be something like this:



Filling a glyph outline is the main stage of rasterization


All this is good, but on the screen we see letters that are filled with color. So, somehow it is possible? I spent about two months on improving the algorithms for filling the already rasterized contour, and in the end I was convinced that this approach was fundamentally wrong. To fill vector images, raster fill is not suitable.

In search of a solution to this fun task, I came across a MIT OCW lecture on computer graphics. I was interested in a lecture on rasterizing three-dimensional graphics (namely, triangular polygons). The essence of the method was as follows: in a vector form, the projection of a triangular polygon on the screen was built, and then the vector triangle was painted over. The shading was performed as follows: a region of the screen was selected beyond which the triangle clearly does not go out, and for each point of this region it was determined whether it belongs to this triangle. The same lecture claims that the Sweeping Line fill method (which Cairo and FreeType use) is deprecated, but more on this method later.

It remains to learn how to determine whether a point belongs to the outline of a glyph or does not belong. The glyph outline is always closed. So, if we draw a ray in any direction from any point, and it crosses the glyph outline an odd number of times, then the point belongs to the glyph, and if it is even, it does not.

Interestingly, this method works even if there are self-intersections or holes in the circuit. It turns out that this algorithm is a textbook, and one of its implementations is
this:


xp = new Array (10, 20, 30, 40);
yp = new Array (30, 40, 20, 10);
function inPoly(x,y){
 npol = xp.length;
 j = npol - 1;
 var c = 0;
 for (i = 0; i < npol;i++){
  if ((((yp[i]<=y) && (y<yp[j])) || ((yp[j]<=y) && (y<yp[i]))) &&
  (x > (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i])) {
   c = !c;}
  j = i;}
return c;}


Here xp and yp are the arrays of coordinates of the vertices of the polygon. The inPoly (x, y) function
returns 1 or 0 - the point belongs to the polygon or not. Considering that we are able to
break the glyph outline into segments (i.e. the sides of the polygon), this function is
great for us.

The simplest rasterizer


Now, translating the glyph into an array of xp and yp vertices, we can write a simple rasterizer. Let the array contain segments with coordinates from 0 to 2000. Then:

function simple(){
for (x=0;x<2000;x++) {
for (y=0;y<2000;y++) {
if (inPoly(x,y)>0) raster[x][y]=1;}}}


This simplest function will create a rasterized glyph image in the raster [x] [y] array. The result displayed on the screen will look something like this (I displayed several glyphs in turn and enlarged the image by about 20 times):



Glyphs with a resolution of 2000x2000 pixels on the screen are unlikely to be needed by anyone, and the inPoly algorithm will process them quite slowly. To display a smaller glyph, do something like this:

function simple(scalefactor){
for (x=0;x<2000/scalefactor;x++) {
for (y=0;y<2000/scalefactor;y++) {
if (inPoly(x*scalefactor,y*scalefactor)>0) raster[x][y]=1;}}}


If scalefactor = 2, then the glyph will be displayed in a square of 1000x1000 pixels, and if scalefactor = 100, then in a square of 20x20 (quite a normal size for screen fonts).

This rasterizer displays the sharpest (and most uneven) contours, and it needs hinting and cutoff control algorithms more than any other rasterizer (they change the shape of the contour depending on the resolution). To store one rasterized glyph in memory, x * y / 8 bytes are required. A full set of ASCII characters will occupy no more than x * y * 32 bytes in memory (3200 bytes for a 10x10 font and 8192 bytes for a 16x16 font). The rasterization process uses a little more than points * 2 * 4 bytes of memory (where points is the number of points in the glyph, points are usually less than 100, and sometimes less than 10).

Anti-aliasing (smoothing)


Rasterization with smoothing gives a much better result. The FreeType 1 library used
5-grayscale anti-aliasing, now FreeType2 uses something more substantial (10- or 17-grayscale anti-aliasing, I did not go into details). Having experimented, I was convinced that 10-grayscale smoothing is much better than 5-grayscale.

function aadraw(scalefactor){
//Мы растеризуем изображение в девять (3*3) раз больше, чем хотим получить
for (x=0;x<size*3/scalefactor;x++) {
for (y=0;y<size*3/scalefactor;y++) {
if (inpoly(x*scalefactor/3,y*scalefactor/3)>0) landscape[x][y]=1;}}
//Затем уменьшаем его в три раза с примитивным сглаживанием
for (x=0;x<size/scalefactor;x++) {
for (y=0;y<size/scalefactor;y++) {
//определяем цвет точки, он будет лежать в диапазоне от 00 до FF
color[x][y]=255-28*(landscape[x*3][y*3]+landscape[x*3][y*3+1]+landscape[x*3][y*3+2]+landscape[x*3+1][y*3]+landscape[x*3+1][y*3+1]+landscape[x*3+1][y*3+2]+landscape[x*3+2][y*3]+landscape[x*3+2][y*3+1]+landscape[x*3+2][y*3+2]));}}//Конец уменьшения
}//Конец функции


Here size is the size of the glyph (in a simple rasterizer, I substituted 2000 instead of size). The landscape array is used to store the intermediate data, and the final result is stored in the color [x] [y] byte array.



Subpixel Smoothing


Subpixel anti-aliasing is often used to display fonts on LCD monitors. On conventional monitors, subpixel smoothing gives the result almost the same as normal smoothing, but on LCD, smoothing by subpixel allows you to increase horizontal resolution three times. The essence of the method is as follows: the human eye distinguishes intensity rather than shade much better. Details are in many sources, and even on the Russian Wikipedia page, the description is sufficient for practical use.

The problem with simple sub-pixel anti-aliasing is that the image quality at the output is lower than that of the 10-grayscale anti-aliasing algorithm. To increase the quality, I use four-halftone smoothing vertically, and sub-pixel smoothing horizontally. The subpixel smoothing algorithm from the directories gives such terrible results:



To get rid of multi-colored “smudges,” I changed the
horizontal blur coefficients , and in addition changed the gamma a little. The result looks like this (the best
quality is achieved when viewing on an LCD monitor):



function xdraw(scalefactor){
//Нам нужно изображение в шесть (3*2) раз больше, чем мы хотим получить
for (x=0;x<size*3/scalefactor;x++) {
for (y=0;y<size*2/scalefactor;y++) {
if (inpoly(x*scalefactor/3,y*scalefactor/2)>0) landscape[x][y]=1;}}
//Применим к этому изображению стандартное размытие перед разбивкой на субпиксели
for (x=0;x<size*3/scalefactor;x++) {
for (y=0;y<size*2/scalefactor;y++) {
if (x>2 && x<size*3/scalefactor-2) landscape1[x][y]=landscape[x-2][y]*(1/9)+landscape[x+2][y]*(1/9)+landscape[x-1][y]*(2/9)+landscape[x+1][y]*(2/9)+landscape[x][y]*(1/3)}}
//Теперь сожмем изображение в два раза, с применением нелинейного размытия
for (x=0;x<size*3/scalefactor;x++) {
for (y=1;y<size/scalefactor;y++) {
landscape2[x][y]=landscape1[x][y*2-1]*(2/9)+landscape1[x][y*2+1]*(2/9)+landscape1[x][y*2]*(4/9);
if (landscape2[x][y]==8/9) landscape2[x][y]=1;}} //и подкорректируем гамму
//Распилим картинку на субпиксели
for (x=0;x<size/scalefactor;x++) {
for (y=0;y<size/scalefactor;y++) {
r[x][y]=Math.floor(255-255*landscape2[x*3][y]);g[x][y]=Math.floor(255-255*landscape2[x*3+1][y]);b[x][y]=Math.floor(255-255*landscape2[x*3+2][y]);}}
}//Конец функции


Sweeping line method main idea


Let's look at the inPoly algorithm that I talked about again. It works, but on large characters it works slowly. Why? Because the processing speed is proportional to the square size. Size doubled, speed decreased fourfold, size increased fourfold - speed dropped 16 times.

If you look a little at the algorithm and think, you will find that for each point of those we sort out, a horizontal ray is emitted and its intersections with the contours are determined. It turns out that a bunch of calculations are done in vain: for all points with the same Y coordinate, the equation of the horizontal line passing through these points will be the same.

Previously, we found a ray for each point, and counted how many times it crosses the contours. We found the intersection coordinates, but did not save. And now let's try to do this: we will find the ray only for the points (0, y), and save the coordinates of the intersection of the rays with the contours.

Please note:
1) If the part of the contour is horizontal and coincides with the sweeping lines, then intersections with this part of the contour are not taken into account.
2) On one sweeping always an even number of intersection points, because the circuit is closed.

All that remains is to fill in the spaces between the odd and even points, and leave the spaces between the even and odd intersection points (when passing the line from left to right). Fonts should be well designed, and the resolution of the glyphs should not be tiny, then the quality will not suffer.

Compare the speed. Our old algorithm would be to emit rays from 9x9 points and find the coordinates of their intersection with the contours. The new algorithm emitted only 9 rays - that is, it works an order of magnitude faster. And at the same time, the sweeping line algorithm is very close to the algorithm that we had.

Sweeping line. InPoly Code Changes


So, we have the inPoly function. Let's make the sweep function out of it.

function inPoly(x,y){
npol = xp.length;
j = npol - 1;
var c = 0;
for (i = 0; i < npol;i++){
if ((((yp[i]<=y) && (y<yp[j])) || ((yp[j]<=y) && (y<yp[i]))) &&
(x > (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i])) {
c = !c;}
j = i;}
return c;}


Obviously, the input parameter x is no longer needed. The input sweep function only gets the current line number. But the input parameter scale is useful - to get x immediately at the desired scale.

The x coordinate of the intersection of the current sweeping line with some straight contour was found like this:
(x >(xp[j]- xp[i])*(y - yp[i])/(yp[j]- yp[i])+ xp[i]))


That is, it will now be:
x =(xp[j]- xp[i])*(y - yp[i])/(yp[j]- yp[i])+ xp[i])


At the output of the function, we must get an array from the coordinates of the intersection points. It would be nice to know the length of this array. So now it will be not c =! C, but c ++.

As a result, we have this:

function sweep(y,scale){
npol = xp.length; //все как обычно....
j = npol -1;
var c =0;
for(i =0; i < npol;i++){
if(((yp[i]<=y)&&(y<yp[j]))||((yp[j]<=y)&&(y<yp[i])))
{ x =(xp[j]- xp[i])*(y - yp[i])/(yp[j]- yp[i])+ xp[i];
curline[c]=x/scale; c++;} //только теперь условия меньше, а точки пересечения сохраняются в массив
j = i;}
return c;} //пусть функция возвращает количество пересечений


And again - a simple rasterizer


So, for each row, we call sweep, find the intersections of the sweeping line and fill in the array at these intersections. However, the sweep function can return to us, for example, such an array of coordinates:

14, 8, 16, 7.

To correctly fill the contour, you need to fill it with the lines (7, y) - (8, y) and (14, y) - (16, y). In a word, you need to sort the results of the sweep function. Quicksort works well, and with a large number of coordinates it is advisable to use it. However, for the fonts that I had at hand, the curline array basically had 2 to 8 intersection coordinates, and in order not to complicate my life, I used bubble sorting. My bubble function accepts an array and its length as input, does not explicitly return anything, but the array becomes sorted.

We proceed directly to the rasterizer. First we need to call sweep for each line, then sort the curline array with the bubble command:

for(y=0;y<size/scale;y++){ //нам больше не нужен вложенный цикл для всех x
every=sweep(y*scale, scale); //every — это количество элементов массива
bubble(curline,every); //сортируем массив
for(point=0;point<every;point=point+2){ //для всех точек массива
for(x=curline[point];x<curline[point+1];x++){landscape[x][y]=1;}
//рисуем линии точками
}}//заканчиваем цикл и функцию


The array starts at 0 - so you need to draw lines from curline [0 + x] to curline [1 + x]. That's all. We got the landscape array, and you need to work with it in the same way as before. That is, after that it can be smoothed out by anti-aliasing or subpixel smoothing, or both. The main thing is to pay attention to the fact that the scale is also transferred to the sweep function, it determines the horizontal extension.

Work results


Now you know how to make a rasterizer of vector fonts with your own hands. A working example of a rasterizer can be downloaded here , but it is written for the Hummingbird operating system (so you will have to download it if you want to run this example). The size of the compiled program is 2589 bytes, the maximum use of RAM is about 300 kilobytes. And this is not the limit!