Bitmap and Pixmap generation with FreeType ------------------------------------------ Table of Contents Introduction I. The rasterizer component II. Bitmap & pixmap descriptors III. Rendering an outline IV. Anti-aliasing palette and other concerns Conclusion Introduction ------------ This document describes the steps that are needed to render a glyph outline into a bitmap or a pixmap with the FreeType library. It contains several important details needed to generate bitmaps correctly in all situations, including if an outline has been transformed or translated. -------------------------------------------------------------------- I. The rasterizer component --------------------------- In FreeType, the component in charge of performing bitmap and pixmap rendering is called the `rasterizer'. Generation is performed through a traditional process called `scan-line conversion', but exhibits certain properties: - The rasterizer doesn't allocate bitmaps: In fact, it is only able to render an outline into an existing bitmap or pixmap, which is passed to one of its rendering functions. This means that the target bitmap/pixmap must be set up correctly by the caller to achieve desired results. Setting up bitmap and pixmap descriptors is explained in section II. - It is able to render anti-aliased pixmaps directly: This is unlike other graphics packages, which render to a `large' bitmap which is then filtered down. Putting the anti-aliasing logic within the rasterizer improves performance and reduces memory usage, as well as lets us use better algorithms which couldn't work in a `two-phase' process. The rasterizer is located in the files `ttraster.h' and `ttraster.c' (or `ttraster.pas' for the Pascal version -- unfortunately, this is severely out of date). The format of outlines isn't important for most developers and won't be discussed here. However, a few conventions must be explained regarding the vector outlines: 1. Units All point coordinates within an outline are stored in 32-bit fractional pixel values, using the 26.6 fixed float format (which uses 26 bits for the integer part, and 6 bits for the fractional part). The following table gives some examples of real versus 26.6 coordinates: ----------------------------------------- real real coord 26.6 coord coord. * 2^6 ----------------------------------------- 0 0*64 = 0.0 0 2.4 2.4*64 = 153.6 154 3 3*64 = 192.0 192 -1.7 -1.7*64 = -108.8 -109 As you can see, conversion is relatively simple -- basically a multiplication by 64. In order to differentiate coordinates expressed in real or 26.6 systems, we'll use in the following lines brackets (`[' and `]') for real coordinates, and simple parentheses (`(' and `)') for fractional coordinates so that [1.0,2.5] equals (64,160) [0,0] equals (0,0) [-2,3] equals (-128,192) 2. Orientation The rasterizer uses the traditional convention of an X axis oriented from left to right, and of a Y axis oriented from bottom to top. ^ Y | | | -*-----> X | You've probably already used it at school when doing math :-) Though the orientation of bitmap lines has the opposite direction on nearly all graphics systems, the former convention is the _right_ one when it comes to vector graphics. The reason is simply that for managing angles and vector cross-products resp. orientations in complex algorithms, a single convention, used in math as well as computing alike solves many headaches. And due to education, most people expect a 45 degrees angle to be in the top right quadrant, at coordinate (1,1). 3. Pixels and the grid In a vector outline, a point is immaterial and has no size or width, just like in usual geometry. A `pixel' is an element of a computer image called a `map' (like a bitmap or a pixmap). The FreeType rasterizer follows the convention defined by the TrueType specification regarding pixel placement: - The map can be seen as a `grid' placed in the vector plane. The grid lines are set on integer real coordinates (i.e., on multiples of 64 in 26.6 fractional notation). Each pixel is one `cell' of the grid, and can be `lit' with any color. Hence, each pixel has a width and a height of [1.0] units, (i.e., 64 fixed float units). ^ Y | | The pixel grid with two | points (not pixels!) +-----+-----+-----+-----+-----+ at coordinates [0,0] | | | | | | and [2,2]. | | | | | | | | | | |[2,2]| +-----+-----+-----+-----@-----+ The pixels are the | | |11111|22222| | grid's cells, and this | | |11111|22222| | example show the four | | |11111|22222| | pixels enclosed within +-----+-----+-----+-----+-----+ the rectangle delimited | | |33333|44444| | by these two points. | | |33333|44444| | | | |33333|44444| | --+-----+-----@-----+-----+-----+----> X | | |[0,0]| | | | | | | | | Note that the numbering | | | | | | of pixels isn't +-----+-----+-----+-----+-----+ meaningful here, it's | | | | | | only used to distinguish | | | | | | them. | | | | | | +-----+-----+-----+-----+-----+ | | - The `center' of each pixel is always located on a `half-integer' coordinate, i.e., at -1.5, -0.5, 0.5, 1.5, etc. - When drawing a shape, the rasterizer only `lits' a pixel when its center is placed _within_ the shape. This is important because an outline point may not be necessarily be on a grid line. - When a pixel center falls on the shape, the pixel is lit too. For example, the following graphics show the `lit' pixels corresponding to the rectangle enclosed by the points: [-0.2, 0] and [2.4, 2.7] ^ Y As one can see, the | newest pixels `1' | and `2' are now lit, | because its centers +-----+-----+-----+-----+--[2.4,2.7] are located at | | |11111|22222| @ | coordinates | . | . |11.11|22.22| . | [0.5,2.5] and | | |11111|22222| | [1.5,2.5], +-----+-----+-----+-----+-----+ respectively. | | |33333|44444| | | . | . |33.33|44.44| . | Note that pixel | | |33333|44444| | centers are +-----+-----+-----+-----+-----+ represented with a | | |55555|66666| | dot in the graphics. | . | . |55.55|66.66| . | | | |55555|66666| | --+-----+----@+-----+-----+-----+----> X | | [-0.2,0] | | | | . | . | . | . | . | | | | | | | Note also that pixel +-----+-----+-----+-----+-----+ numbering is still | | | | | | meaningless there. | . | . | . | . | . | | | | | | | +-----+-----+-----+-----+-----+ | | 4. Drop-out control Sometimes, a stroke is too thin to even contain a single pixel center. This results in `lost continuity' in the resulting bitmap, i.e., some unpleasant `holes' or `breaks' in the rendered shape, which are called a `drop-out'. Because a glyph representation uses curves (Bezier arcs), this case is not easily controllable during the `hinting' of glyph outlines by the font driver, which means that the rasterizer must be able to correct these `artefacts'. This processing is called `drop-out control', and can be performed in several modes, defined by the TrueType specification, and which details do not belong to this document. However, the important idea is that, in _some_ cases, a pixel may be lit even if its center isn't part of the shape. This case is relatively rare, but is mentioned because it has consequences of the rendering of maps. More precisely, in the way an outline's extent is computed (see below). -------------------------------------------------------------------- II. Bitmap and pixmap descriptors --------------------------------- The Freetype rasterizer only supports bitmaps and 8-bit pixmaps. In order to render an outline, a map descriptor must be sent to its rendering functions, along with a vectorial outline. 1. Bitmap properties This section explains how to set up a bitmap descriptor, and how vector coordinates in the outline plane relate to pixel positions within the bitmap buffer. A bitmap's `raw data' is made of a simple bit buffer where each bit corresponds to a monochrome pixel. For the sake of simplicity, the FreeType rasterizer uses the following conventions to store bitmaps in a buffer: - The value 0 is used for `unlit' pixels, usually the `background' when rendering text. Hence 1 is used for `lit'. - Lines are padded to 8 bits, i.e. bytes. A bitmap row thus takes an integral number of bytes in its buffer. No further alignment is required. (Some systems compress bitmaps by _not_ padding bit rows to byte boundaries. It is not possible to render into such a bitmap buffer with FreeType.) - In a bitmap buffer byte, the left-most pixel is represented by the most significant bit (i.e., 0x80). The opposite convention is not supported by the FreeType rasterizer, though it may possibly be implemented too if this ever comes useful (ask the developers -- for now, nobody did). - Increasing offsets within a row correspond to right-most positions in the bitmap (i.e., byte 1 contains the 8 bits/pixels that are located on the right of the 8 bits/pixels of byte 0). - A bitmap can be oriented in two ways: o If increasing row addresses within the buffer correspond to lower vertical lines, the bitmap is said to go `down'. This is, for example, the case of nearly all video RAMs. o If increasing row addresses within the buffer correspond to higher vertical lines, the bitmap is said to go `up'. This is the case, for example, for OS/2 bitmaps. The `direction' of a bitmap is called `flow' to avoid any confusion. In both cases, the rasterizer ALWAYS matches the vector coordinate (0,0) with the lower-left corner of the *lower-left* pixel in the bitmap. The following graphics illustrate these ideas: Y ^ | A `down-flow' bitmap. +--+--+--+--+--+--+--+--+ On the left is each | | | | | | | | | row's number and its 0: 0 | | | | | | | | | offset in the bitmap +--+--+--+--+--+--+--+--+ buffer (where `w' is | | | | | | | | | the width, in bytes, 1: w | | | | | | | | | of a single bitmap +--+--+--+--+--+--+--+--+ row). Note that the | | | | | | | | | origin is located at 2: 2*w | | | | | | | | | the lower left, i.e., +--+--+--+--+--+--+--+--+ near the leftmost bit | | | | | | | | | of the last bitmap 3: 3*w | | | | | | | | | row. -@--+--+--+--+--+--+--+-----> X |[0,0] Y ^ | An `up-flow' bitmap. +--+--+--+--+--+--+--+--+ On the left is each | | | | | | | | | row's number and its 3: 3*w | | | | | | | | | offset in the bitmap +--+--+--+--+--+--+--+--+ buffer (where `w' is | | | | | | | | | the width, in bytes, 2: 2*w | | | | | | | | | of a single bitmap +--+--+--+--+--+--+--+--+ row). Note that the | | | | | | | | | origin is located at 1: w | | | | | | | | | the lower left, i.e., +--+--+--+--+--+--+--+--+ near the first bit in | | | | | | | | | the buffer. 0: 0 | | | | | | | | | The first buffer bit -@--+--+--+--+--+--+--+-----> X corresponds to the |[0,0] rectangle [0,0]-[1,1] in the vector plane. 2. Bitmap descriptors Now that you understand all these details, a bitmap can be described to the rasterizer engine through a map, which structure must be set up by client application: struct TT_Raster_Map_ { int rows; /* number of rows */ int cols; /* number of columns (bytes) per row */ int width; /* number of pixels per line */ int flow; /* bitmap orientation */ void* bitmap; /* bit/pixmap buffer */ long size; /* bit/pixmap size in bytes */ }; typedef struct TT_Raster_Map_ TT_Raster_Map; where the fields stand for: rows: The number of rows within the bitmap buffer. cols: The number of columns, i.e. bytes per row within the buffer. It corresponds to the `w' value used in the above graphics. width: The number of pixels (i.e. bits) per row in the buffer. The rasterizer always clips its rendering to the bit width specified in this field, even if the `cols' fields corresponds to a larger width. flow: The bitmap flow. Use the constants TT_Flow_Up and TT_Flow_Down exclusively for this field. bitmap: A typeless pointer to the bit buffer. size: The total size of the bit buffer in bytes. This is not used directly by the rasterizer, so applications can use it. Note that the `cols' field should always be bigger than the value of `width' multiplied by 8. The rasterizer clips the generated bitmap to the `width' first bits in a row. Note also that it is of course allowed to create, for example, a Windows or X11 bitmap through a normal system-specific API call, using a TT_Raster_Map that describes it to the rasterizer. It is thus possible to draw directly into such OS specific structures. IMPORTANT: ***************************************************** When rendering a bitmap, the rasterizer always OR-es the shape on the target bitmap. It is thus possible to draw several shapes into a single surface which successive calls to the render functions. **************************************************************** 3. Pixmap properties The rasterizer only supports 8-bit pixmaps, where one pixel is represented by a single byte. They must conform to the following rules: - A 5-entries palette is used to generate an outline's pixmap in the buffer. They correspond to: palette[0] -> background palette[1] -> `light' palette[2] -> `medium' palette[3] -> `dark' palette[4] -> foreground where the terms `light', `medium', and `dark' correspond to intermediate values between the first (background) and last (foreground) entry. The upcoming FreeType 2.0 will feature an additional anti-aliasing logic with a 17-entries palette. - Lines are padded to 32 bits, i.e. 4 bytes. A pixmap row thus takes a multiple of 4 bytes in its buffer. - Increasing offsets within a row correspond to right-most positions in the bitmap (i.e., byte/pixel 1 is to the right of byte/pixel 0). - A pixmap can be oriented in two ways, following the same rules as a bitmap regarding its flow. IMPORTANT: ***************************************************** In order to improve performance when rendering large outlines with anti-aliasing, the rasterizer draws pixels in runs of 4-bytes ONLY when at least one of their `colour' isn't 0 (background). This means that you should ALWAYS CLEAR the pixmap buffer before calling the rendering function, you may otherwise experience ugly artefacts, which are possibly left from a previous rendering! In general, it is not possible to do colour compositing with the FreeType rasterizer (compositing is if you want to superpose a transparent coloured layer on top of an image). This is mainly due to the fact that: - There are too many pixel formats to support. - There is not a single portable way to do it anyway. - It really is a graphics processing question, not one that should be solved by a text rendering engine. **************************************************************** 4. Pixmap descriptors Pixmaps use the same descriptor structure as bitmaps, with a few differences in interpretation: - The `cols' field is used to indicate the number of _bytes_ in a pixmap row. It must thus be a multiple of 4! - The rasterizer clips the outline to the first `width' pixels/width within each buffer row. As usual, it should be possible to use a system-specific pixmap and render directly into it, as long as you set up a descriptor for it. ------------------------------------------------------------------------- III. Rendering an outline ------------------------- Now that you understand how the rasterizer sees the target bitmaps and pixmaps it renders to, this section will explain how the rendering eventually happen. 1. Outline coordinates and extents Let's first consider the case where we're rendering text directly into a huge single bitmap. To do that, we simply translate each glyph outline before calling the rasterizer. Here the roadmap: - Vectorial coordinates [0,0] are mapped to the lower left `corner' (in the grid) of the lower left pixel in the bitmap (whatever its flow is). - When the glyph loader returns an outline, the latter is placed so that the coordinate [0,0] corresponds to the current cursor position. This means that: - If we use our own cursor (cx,cy) within the bitmap during text rendering, we must translate the outline to its position before rendering it, e.g. with TT_Translate_Outline( outline, cx, cy ) (and the cursor position must be incremented after rendering each glyph). - Before translation (i.e., when it is returned by the glyph loader), the glyph outline doesn't necessarily lie on any of the coordinate axes, nor is it limited to the first quadrant (i.e., x>0 and y>0 is not true in general). Its extent can be computed with the function TT_Get_Outline_BBox(), which returns the minimum and maximum values of its X and Y point coordinates (in 26.6 format, of course). 2. Computing an outline's dimensions in pixels In many cases, however, it is much better to render individual glyph bitmaps, then cache them with appropriate metrics in order to render text much more quickly at a given point size. To be able to render the smallest possible bitmap, the exact outline's extent dimensions in pixel are required. Again a roadmap: - Get the outline's bounding box in vector coordinates: Simply call the TT_Get_Outline_BBox() function which will return the values of xMin, yMin, xMax, and yMax in vector (i.e. fractional) coordinates. - Grid-fit the bounding box: Because of the way pixels are lit in the bitmaps relative to the position of their `centers' within the shape (see section I), it is necessary to align the values of xMin, xMax, yMin, and yMax to the pixel grid in order to compute the width and height of the resulting bitmap. This can be done with: xMin = FLOOR ( xMin ); with FLOOR(x) == (x & -64) xMax = CEILING( xMax ); CEILING(x) == ((x+63) & -64) yMin = FLOOR ( yMin ); yMax = CEILING( yMax ); The extents in pixels can then be simply computed as: pixel_width = (xMax - xMin) / 64; pixel_height = (yMax - yMin) / 64; Note that because of drop-out control, and because the bounding box computed currently includes all Bezier control points from the outline, the bitmap may be slightly larger than necessary in some cases. Some improvements are planned for FreeType 2.0; for now, you should consider that finding the `exact' bitmap bounding box requires to scan all `borders' to detect null columns or rows. However, the values are right in most cases. NOTE: It seems that in some *rare* cases, which relate to weird drop-out control situations, the above dimensions are not enough to store all bits from the outline (there are one or more bits `cut' on the edge). This being hard to study (it only appears in very poorly hinted fonts), we leave this problem to FreeType 2.0. - Create/setup a bitmap with the computed dimensions. DON'T FORGET TO CLEAR ITS BUFFER TOO! - Translate the outline to stick within the bitmap space. This is done easily by translating it by (-xMin,-yMin), where you should ALWAYS USE THE GRID-FITTED VALUES computed above for xMin and yMin: TT_Translate_Outline( outline, -xMin, -yMin ); IMPORTANT: *************************************************** For technical reasons, you should never translate a HINTED outline by a non-integer vector (i.e., a vector which coordinates aren't multiples of 64)! This would CERTAINLY completely RUIN the delicate HINTING of the glyph, and will result probably in pure GARBAGE at small point sizes. Of course, if you're not interested in hinting, like when displaying rotated text, you can ignore this rule and translate to any position freely. ************************************************************** - Render the bitmap (or pixmap). DON'T FORGET TO STORE THE GRID-FITTED xMin and yMin WITH THE BITMAP! This will allow you later to place it correctly relative to your cursor position. Here's some example pseudo code: { ... load the glyph ... TT_Outline outline; TT_BBox bbox; TT_Raster_Map bitmap; /* get the outline */ TT_Get_Glyph_Outline( glyph, &outline ); /* compute its extent */ TT_Get_Outline_BBox( &outline, &bbox ); /* Grid-fit it */ bbox.xMin &= -64; bbox.xMax = ( bbox.xMax + 63 ) & -64; bbox.yMin &= -64; bbox.yMax = ( bbox.yMax + 63 ) & -64; /* compute pixel dimensions */ width = (bbox.xMax - bbox.xMin) / 64; height = (bbox.yMax - bbox.yMin) / 64; /* set up bitmap */ bitmap.rows = height; bitmap.width = width; bitmap.cols = (width + 7) / 8; bitmap.size = bitmap.rows * bitmap.cols; bitmap.bitmap = malloc( bitmap.size ); if ( !bitmap.bitmap ) return error_memory... /* clear the bitmap buffer! */ memset( bitmap.bitmap, 0, bitmap.size ); /* translate outline */ TT_Translate_Outline( &outline, -bbox.xMin, -bbox.yMin ); /* render it within the bitmap */ TT_Get_Outline_Bitmap( engine, &outline, &bitmap ); /* We're done; don't forget to save bbox.xMin and */ /* bbox.yMin to adjust the bitmap position when */ /* rendering text with it */ ... } 3. The case of transformed/rotated glyphs: You may want to apply a transformation other than a translation to your glyph outlines before rendering them. For example, a simple slant to synthesize italics, or a slight rotation. In all cases, it is possible to render individual glyph bitmaps. Just make sure to follow the same process AFTER you have transformed you outline! DON'T FORGET THAT YOU NEED TO RE-COMPUTE THE BBOX TO GET THE CORRECT PIXEL DIMENSIONS AFTER A TRANSFORMATION. -------------------------------------------------------------------- IV. Anti-aliasing palette and other concerns When rendering pixmaps, using the TT_Get_Outline_Pixmap() or TT_Get_Glyph_Pixmap() functions, the rasterizer uses a 5-entries palette of 8-bit deep `colors'. By default, this palette is set to ( 0, 1, 2, 3, 4 ), but one can change it to suit your needs with TT_Set_Raster_Palette(). While in bitmap mode, it simply OR-es the pixel values to the target bitmap that has been passed to TT_Get_Outline_Bitmap(). For pixmaps it simply writes directly the palette entries corresponding to the `color' of the `lit' pixels it has computed. This means that it is NOT POSSIBLE to render text in a single pixmap with multiple calls to TT_Get_Outline_Pixmaps() within the same target! The reason is that `gray' pixels of two distinct outlines are not `added' when they overlap (the operation called 'compositing'), as it could be expected by applications. The following graphic shows this effect when rendering two overlapping anti-aliased shapes: *** *** .** .** ** **. **. ** .*. .*.. .*..*. .*. + .*. = ---> ..*. .*. ** | .*. ** ** | ** **. | **. *** | *** | missing black pixel after second rendering... There is no simple way to perform a composition within the rasterizer. This would not be portable; moreover, it would be extremely slow if it is too general. This operation is thus left to client applications which can use their own system-specific API for transparently blitting the glyph pixmaps into a surface to form text. NOTE: If your system doesn't support transparent/alpha blits, you can still have a look at the source file `freetype/test/display.c'. It uses a large pixmap, with a special palette trick to render all text quickly, then convert everything to `real' colors for display. -------------------------------------------------------------------- Conclusion ---------- We've seen how the FreeType rasterizer sees bitmaps through descriptors, as well as the mapping which exists between the vector coordinate space and the pixel position space. You should now be able to render outlines into bitmaps and pixmaps while applying transformations like translation, slanting, or rotation. Don't forget a few rules, however: - Always clear the bitmap/pixmap buffer before rendering (unless you want to render several glyphs in a single _bitmap_; it won't work on a pixmap). - A pixmap `cols' field, i.e. the size in bytes of each rows, must be a multiple of 4. - Never translate a hinted outline by a non-integer vector if you want to preserve the hints (i.e., the vector's coordinates must be multiples of 64). - Finally, don't expect the rasterizer to composite transparent `grays' for you in a single target pixmap through multiple calls. --- end of bitmaps.txt ---