michael@0: michael@0: How FreeType's rasterizer work michael@0: michael@0: by David Turner michael@0: michael@0: Revised 2007-Feb-01 michael@0: michael@0: michael@0: This file is an attempt to explain the internals of the FreeType michael@0: rasterizer. The rasterizer is of quite general purpose and could michael@0: easily be integrated into other programs. michael@0: michael@0: michael@0: I. Introduction michael@0: michael@0: II. Rendering Technology michael@0: 1. Requirements michael@0: 2. Profiles and Spans michael@0: a. Sweeping the Shape michael@0: b. Decomposing Outlines into Profiles michael@0: c. The Render Pool michael@0: d. Computing Profiles Extents michael@0: e. Computing Profiles Coordinates michael@0: f. Sweeping and Sorting the Spans michael@0: michael@0: michael@0: I. Introduction michael@0: =============== michael@0: michael@0: A rasterizer is a library in charge of converting a vectorial michael@0: representation of a shape into a bitmap. The FreeType rasterizer michael@0: has been originally developed to render the glyphs found in michael@0: TrueType files, made up of segments and second-order Béziers. michael@0: Meanwhile it has been extended to render third-order Bézier curves michael@0: also. This document is an explanation of its design and michael@0: implementation. michael@0: michael@0: While these explanations start from the basics, a knowledge of michael@0: common rasterization techniques is assumed. michael@0: michael@0: michael@0: II. Rendering Technology michael@0: ======================== michael@0: michael@0: 1. Requirements michael@0: --------------- michael@0: michael@0: We assume that all scaling, rotating, hinting, etc., has been michael@0: already done. The glyph is thus described by a list of points in michael@0: the device space. michael@0: michael@0: - All point coordinates are in the 26.6 fixed float format. The michael@0: used orientation is: michael@0: michael@0: michael@0: ^ y michael@0: | reference orientation michael@0: | michael@0: *----> x michael@0: 0 michael@0: michael@0: michael@0: `26.6' means that 26 bits are used for the integer part of a michael@0: value and 6 bits are used for the fractional part. michael@0: Consequently, the `distance' between two neighbouring pixels is michael@0: 64 `units' (1 unit = 1/64th of a pixel). michael@0: michael@0: Note that, for the rasterizer, pixel centers are located at michael@0: integer coordinates. The TrueType bytecode interpreter, michael@0: however, assumes that the lower left edge of a pixel (which is michael@0: taken to be a square with a length of 1 unit) has integer michael@0: coordinates. michael@0: michael@0: michael@0: ^ y ^ y michael@0: | | michael@0: | (1,1) | (0.5,0.5) michael@0: +-----------+ +-----+-----+ michael@0: | | | | | michael@0: | | | | | michael@0: | | | o-----+-----> x michael@0: | | | (0,0) | michael@0: | | | | michael@0: o-----------+-----> x +-----------+ michael@0: (0,0) (-0.5,-0.5) michael@0: michael@0: TrueType bytecode interpreter FreeType rasterizer michael@0: michael@0: michael@0: A pixel line in the target bitmap is called a `scanline'. michael@0: michael@0: - A glyph is usually made of several contours, also called michael@0: `outlines'. A contour is simply a closed curve that delimits an michael@0: outer or inner region of the glyph. It is described by a series michael@0: of successive points of the points table. michael@0: michael@0: Each point of the glyph has an associated flag that indicates michael@0: whether it is `on' or `off' the curve. Two successive `on' michael@0: points indicate a line segment joining the two points. michael@0: michael@0: One `off' point amidst two `on' points indicates a second-degree michael@0: (conic) Bézier parametric arc, defined by these three points michael@0: (the `off' point being the control point, and the `on' ones the michael@0: start and end points). Similarly, a third-degree (cubic) Bézier michael@0: curve is described by four points (two `off' control points michael@0: between two `on' points). michael@0: michael@0: Finally, for second-order curves only, two successive `off' michael@0: points forces the rasterizer to create, during rendering, an michael@0: `on' point amidst them, at their exact middle. This greatly michael@0: facilitates the definition of successive Bézier arcs. michael@0: michael@0: The parametric form of a second-order Bézier curve is: michael@0: michael@0: P(t) = (1-t)^2*P1 + 2*t*(1-t)*P2 + t^2*P3 michael@0: michael@0: (P1 and P3 are the end points, P2 the control point.) michael@0: michael@0: The parametric form of a third-order Bézier curve is: michael@0: michael@0: P(t) = (1-t)^3*P1 + 3*t*(1-t)^2*P2 + 3*t^2*(1-t)*P3 + t^3*P4 michael@0: michael@0: (P1 and P4 are the end points, P2 and P3 the control points.) michael@0: michael@0: For both formulae, t is a real number in the range [0..1]. michael@0: michael@0: Note that the rasterizer does not use these formulae directly. michael@0: They exhibit, however, one very useful property of Bézier arcs: michael@0: Each point of the curve is a weighted average of the control michael@0: points. michael@0: michael@0: As all weights are positive and always sum up to 1, whatever the michael@0: value of t, each arc point lies within the triangle (polygon) michael@0: defined by the arc's three (four) control points. michael@0: michael@0: In the following, only second-order curves are discussed since michael@0: rasterization of third-order curves is completely identical. michael@0: michael@0: Here some samples for second-order curves. michael@0: michael@0: michael@0: * # on curve michael@0: * off curve michael@0: __---__ michael@0: #-__ _-- -_ michael@0: --__ _- - michael@0: --__ # \ michael@0: --__ # michael@0: -# michael@0: Two `on' points michael@0: Two `on' points and one `off' point michael@0: between them michael@0: michael@0: * michael@0: # __ Two `on' points with two `off' michael@0: \ - - points between them. The point michael@0: \ / \ marked `0' is the middle of the michael@0: - 0 \ `off' points, and is a `virtual michael@0: -_ _- # on' point where the curve passes. michael@0: -- It does not appear in the point michael@0: * list. michael@0: michael@0: michael@0: 2. Profiles and Spans michael@0: --------------------- michael@0: michael@0: The following is a basic explanation of the _kind_ of computations michael@0: made by the rasterizer to build a bitmap from a vector michael@0: representation. Note that the actual implementation is slightly michael@0: different, due to performance tuning and other factors. michael@0: michael@0: However, the following ideas remain in the same category, and are michael@0: more convenient to understand. michael@0: michael@0: michael@0: a. Sweeping the Shape michael@0: michael@0: The best way to fill a shape is to decompose it into a number of michael@0: simple horizontal segments, then turn them on in the target michael@0: bitmap. These segments are called `spans'. michael@0: michael@0: __---__ michael@0: _-- -_ michael@0: _- - michael@0: - \ michael@0: / \ michael@0: / \ michael@0: | \ michael@0: michael@0: __---__ Example: filling a shape michael@0: _----------_ with spans. michael@0: _-------------- michael@0: ----------------\ michael@0: /-----------------\ This is typically done from the top michael@0: / \ to the bottom of the shape, in a michael@0: | | \ movement called a `sweep'. michael@0: V michael@0: michael@0: __---__ michael@0: _----------_ michael@0: _-------------- michael@0: ----------------\ michael@0: /-----------------\ michael@0: /-------------------\ michael@0: |---------------------\ michael@0: michael@0: michael@0: In order to draw a span, the rasterizer must compute its michael@0: coordinates, which are simply the x coordinates of the shape's michael@0: contours, taken on the y scanlines. michael@0: michael@0: michael@0: /---/ |---| Note that there are usually michael@0: /---/ |---| several spans per scanline. michael@0: | /---/ |---| michael@0: | /---/_______|---| When rendering this shape to the michael@0: V /----------------| current scanline y, we must michael@0: /-----------------| compute the x values of the michael@0: a /----| |---| points a, b, c, and d. michael@0: - - - * * - - - - * * - - y - michael@0: / / b c| |d michael@0: michael@0: michael@0: /---/ |---| michael@0: /---/ |---| And then turn on the spans a-b michael@0: /---/ |---| and c-d. michael@0: /---/_______|---| michael@0: /----------------| michael@0: /-----------------| michael@0: a /----| |---| michael@0: - - - ####### - - - - ##### - - y - michael@0: / / b c| |d michael@0: michael@0: michael@0: b. Decomposing Outlines into Profiles michael@0: michael@0: For each scanline during the sweep, we need the following michael@0: information: michael@0: michael@0: o The number of spans on the current scanline, given by the michael@0: number of shape points intersecting the scanline (these are michael@0: the points a, b, c, and d in the above example). michael@0: michael@0: o The x coordinates of these points. michael@0: michael@0: x coordinates are computed before the sweep, in a phase called michael@0: `decomposition' which converts the glyph into *profiles*. michael@0: michael@0: Put it simply, a `profile' is a contour's portion that can only michael@0: be either ascending or descending, i.e., it is monotonic in the michael@0: vertical direction (we also say y-monotonic). There is no such michael@0: thing as a horizontal profile, as we shall see. michael@0: michael@0: Here are a few examples: michael@0: michael@0: michael@0: this square michael@0: 1 2 michael@0: ---->---- is made of two michael@0: | | | | michael@0: | | profiles | | michael@0: ^ v ^ + v michael@0: | | | | michael@0: | | | | michael@0: ----<---- michael@0: michael@0: up down michael@0: michael@0: michael@0: this triangle michael@0: michael@0: P2 1 2 michael@0: michael@0: |\ is made of two | \ michael@0: ^ | \ \ | \ michael@0: | | \ \ profiles | \ | michael@0: | | \ v ^ | \ | michael@0: | \ | | + \ v michael@0: | \ | | \ michael@0: P1 ---___ \ ---___ \ michael@0: ---_\ ---_ \ michael@0: <--__ P3 up down michael@0: michael@0: michael@0: michael@0: A more general contour can be made of more than two profiles: michael@0: michael@0: __ ^ michael@0: / | / ___ / | michael@0: / | / | / | / | michael@0: | | / / => | v / / michael@0: | | | | | | ^ | michael@0: ^ | |___| | | ^ + | + | + v michael@0: | | | v | | michael@0: | | | up | michael@0: |___________| | down | michael@0: michael@0: <-- up down michael@0: michael@0: michael@0: Successive profiles are always joined by horizontal segments michael@0: that are not part of the profiles themselves. michael@0: michael@0: For the rasterizer, a profile is simply an *array* that michael@0: associates one horizontal *pixel* coordinate to each bitmap michael@0: *scanline* crossed by the contour's section containing the michael@0: profile. Note that profiles are *oriented* up or down along the michael@0: glyph's original flow orientation. michael@0: michael@0: In other graphics libraries, profiles are also called `edges' or michael@0: `edgelists'. michael@0: michael@0: michael@0: c. The Render Pool michael@0: michael@0: FreeType has been designed to be able to run well on _very_ michael@0: light systems, including embedded systems with very few memory. michael@0: michael@0: A render pool will be allocated once; the rasterizer uses this michael@0: pool for all its needs by managing this memory directly in it. michael@0: The algorithms that are used for profile computation make it michael@0: possible to use the pool as a simple growing heap. This means michael@0: that this memory management is actually quite easy and faster michael@0: than any kind of malloc()/free() combination. michael@0: michael@0: Moreover, we'll see later that the rasterizer is able, when michael@0: dealing with profiles too large and numerous to lie all at once michael@0: in the render pool, to immediately decompose recursively the michael@0: rendering process into independent sub-tasks, each taking less michael@0: memory to be performed (see `sub-banding' below). michael@0: michael@0: The render pool doesn't need to be large. A 4KByte pool is michael@0: enough for nearly all renditions, though nearly 100% slower than michael@0: a more comfortable 16KByte or 32KByte pool (that was tested with michael@0: complex glyphs at sizes over 500 pixels). michael@0: michael@0: michael@0: d. Computing Profiles Extents michael@0: michael@0: Remember that a profile is an array, associating a _scanline_ to michael@0: the x pixel coordinate of its intersection with a contour. michael@0: michael@0: Though it's not exactly how the FreeType rasterizer works, it is michael@0: convenient to think that we need a profile's height before michael@0: allocating it in the pool and computing its coordinates. michael@0: michael@0: The profile's height is the number of scanlines crossed by the michael@0: y-monotonic section of a contour. We thus need to compute these michael@0: sections from the vectorial description. In order to do that, michael@0: we are obliged to compute all (local and global) y extrema of michael@0: the glyph (minima and maxima). michael@0: michael@0: michael@0: P2 For instance, this triangle has only michael@0: two y-extrema, which are simply michael@0: |\ michael@0: | \ P2.y as a vertical maximum michael@0: | \ P3.y as a vertical minimum michael@0: | \ michael@0: | \ P1.y is not a vertical extremum (though michael@0: | \ it is a horizontal minimum, which we michael@0: P1 ---___ \ don't need). michael@0: ---_\ michael@0: P3 michael@0: michael@0: michael@0: Note that the extrema are expressed in pixel units, not in michael@0: scanlines. The triangle's height is certainly (P3.y-P2.y+1) michael@0: pixel units, but its profiles' heights are computed in michael@0: scanlines. The exact conversion is simple: michael@0: michael@0: - min scanline = FLOOR ( min y ) michael@0: - max scanline = CEILING( max y ) michael@0: michael@0: A problem arises with Bézier Arcs. While a segment is always michael@0: necessarily y-monotonic (i.e., flat, ascending, or descending), michael@0: which makes extrema computations easy, the ascent of an arc can michael@0: vary between its control points. michael@0: michael@0: michael@0: P2 michael@0: * michael@0: # on curve michael@0: * off curve michael@0: __-x--_ michael@0: _-- -_ michael@0: P1 _- - A non y-monotonic Bézier arc. michael@0: # \ michael@0: - The arc goes from P1 to P3. michael@0: \ michael@0: \ P3 michael@0: # michael@0: michael@0: michael@0: We first need to be able to easily detect non-monotonic arcs, michael@0: according to their control points. I will state here, without michael@0: proof, that the monotony condition can be expressed as: michael@0: michael@0: P1.y <= P2.y <= P3.y for an ever-ascending arc michael@0: michael@0: P1.y >= P2.y >= P3.y for an ever-descending arc michael@0: michael@0: with the special case of michael@0: michael@0: P1.y = P2.y = P3.y where the arc is said to be `flat'. michael@0: michael@0: As you can see, these conditions can be very easily tested. michael@0: They are, however, extremely important, as any arc that does not michael@0: satisfy them necessarily contains an extremum. michael@0: michael@0: Note also that a monotonic arc can contain an extremum too, michael@0: which is then one of its `on' points: michael@0: michael@0: michael@0: P1 P2 michael@0: #---__ * P1P2P3 is ever-descending, but P1 michael@0: -_ is an y-extremum. michael@0: - michael@0: ---_ \ michael@0: -> \ michael@0: \ P3 michael@0: # michael@0: michael@0: michael@0: Let's go back to our previous example: michael@0: michael@0: michael@0: P2 michael@0: * michael@0: # on curve michael@0: * off curve michael@0: __-x--_ michael@0: _-- -_ michael@0: P1 _- - A non-y-monotonic Bézier arc. michael@0: # \ michael@0: - Here we have michael@0: \ P2.y >= P1.y && michael@0: \ P3 P2.y >= P3.y (!) michael@0: # michael@0: michael@0: michael@0: We need to compute the vertical maximum of this arc to be able michael@0: to compute a profile's height (the point marked by an `x'). The michael@0: arc's equation indicates that a direct computation is possible, michael@0: but we rely on a different technique, which use will become michael@0: apparent soon. michael@0: michael@0: Bézier arcs have the special property of being very easily michael@0: decomposed into two sub-arcs, which are themselves Bézier arcs. michael@0: Moreover, it is easy to prove that there is at most one vertical michael@0: extremum on each Bézier arc (for second-degree curves; similar michael@0: conditions can be found for third-order arcs). michael@0: michael@0: For instance, the following arc P1P2P3 can be decomposed into michael@0: two sub-arcs Q1Q2Q3 and R1R2R3: michael@0: michael@0: michael@0: P2 michael@0: * michael@0: # on curve michael@0: * off curve michael@0: michael@0: michael@0: original Bézier arc P1P2P3. michael@0: __---__ michael@0: _-- --_ michael@0: _- -_ michael@0: - - michael@0: / \ michael@0: / \ michael@0: # # michael@0: P1 P3 michael@0: michael@0: michael@0: michael@0: P2 michael@0: * michael@0: michael@0: michael@0: michael@0: Q3 Decomposed into two subarcs michael@0: Q2 R2 Q1Q2Q3 and R1R2R3 michael@0: * __-#-__ * michael@0: _-- --_ michael@0: _- R1 -_ Q1 = P1 R3 = P3 michael@0: - - Q2 = (P1+P2)/2 R2 = (P2+P3)/2 michael@0: / \ michael@0: / \ Q3 = R1 = (Q2+R2)/2 michael@0: # # michael@0: Q1 R3 Note that Q2, R2, and Q3=R1 michael@0: are on a single line which is michael@0: tangent to the curve. michael@0: michael@0: michael@0: We have then decomposed a non-y-monotonic Bézier curve into two michael@0: smaller sub-arcs. Note that in the above drawing, both sub-arcs michael@0: are monotonic, and that the extremum is then Q3=R1. However, in michael@0: a more general case, only one sub-arc is guaranteed to be michael@0: monotonic. Getting back to our former example: michael@0: michael@0: michael@0: Q2 michael@0: * michael@0: michael@0: __-x--_ R1 michael@0: _-- #_ michael@0: Q1 _- Q3 - R2 michael@0: # \ * michael@0: - michael@0: \ michael@0: \ R3 michael@0: # michael@0: michael@0: michael@0: Here, we see that, though Q1Q2Q3 is still non-monotonic, R1R2R3 michael@0: is ever descending: We thus know that it doesn't contain the michael@0: extremum. We can then re-subdivide Q1Q2Q3 into two sub-arcs and michael@0: go on recursively, stopping when we encounter two monotonic michael@0: subarcs, or when the subarcs become simply too small. michael@0: michael@0: We will finally find the vertical extremum. Note that the michael@0: iterative process of finding an extremum is called `flattening'. michael@0: michael@0: michael@0: e. Computing Profiles Coordinates michael@0: michael@0: Once we have the height of each profile, we are able to allocate michael@0: it in the render pool. The next task is to compute coordinates michael@0: for each scanline. michael@0: michael@0: In the case of segments, the computation is straightforward, michael@0: using the Euclidean algorithm (also known as Bresenham). michael@0: However, for Bézier arcs, the job is a little more complicated. michael@0: michael@0: We assume that all Béziers that are part of a profile are the michael@0: result of flattening the curve, which means that they are all michael@0: y-monotonic (ascending or descending, and never flat). We now michael@0: have to compute the intersections of arcs with the profile's michael@0: scanlines. One way is to use a similar scheme to flattening michael@0: called `stepping'. michael@0: michael@0: michael@0: Consider this arc, going from P1 to michael@0: --------------------- P3. Suppose that we need to michael@0: compute its intersections with the michael@0: drawn scanlines. As already michael@0: --------------------- mentioned this can be done michael@0: directly, but the involved michael@0: * P2 _---# P3 algorithm is far too slow. michael@0: ------------- _-- -- michael@0: _- michael@0: _/ Instead, it is still possible to michael@0: ---------/----------- use the decomposition property in michael@0: / the same recursive way, i.e., michael@0: | subdivide the arc into subarcs michael@0: ------|-------------- until these get too small to cross michael@0: | more than one scanline! michael@0: | michael@0: -----|--------------- This is very easily done using a michael@0: | rasterizer-managed stack of michael@0: | subarcs. michael@0: # P1 michael@0: michael@0: michael@0: f. Sweeping and Sorting the Spans michael@0: michael@0: Once all our profiles have been computed, we begin the sweep to michael@0: build (and fill) the spans. michael@0: michael@0: As both the TrueType and Type 1 specifications use the winding michael@0: fill rule (but with opposite directions), we place, on each michael@0: scanline, the present profiles in two separate lists. michael@0: michael@0: One list, called the `left' one, only contains ascending michael@0: profiles, while the other `right' list contains the descending michael@0: profiles. michael@0: michael@0: As each glyph is made of closed curves, a simple geometric michael@0: property ensures that the two lists contain the same number of michael@0: elements. michael@0: michael@0: Creating spans is thus straightforward: michael@0: michael@0: 1. We sort each list in increasing horizontal order. michael@0: michael@0: 2. We pair each value of the left list with its corresponding michael@0: value in the right list. michael@0: michael@0: michael@0: / / | | For example, we have here michael@0: / / | | four profiles. Two of michael@0: >/ / | | | them are ascending (1 & michael@0: 1// / ^ | | | 2 3), while the two others michael@0: // // 3| | | v are descending (2 & 4). michael@0: / //4 | | | On the given scanline, michael@0: a / /< | | the left list is (1,3), michael@0: - - - *-----* - - - - *---* - - y - and the right one is michael@0: / / b c| |d (4,2) (sorted). michael@0: michael@0: There are then two spans, joining michael@0: 1 to 4 (i.e. a-b) and 3 to 2 michael@0: (i.e. c-d)! michael@0: michael@0: michael@0: Sorting doesn't necessarily take much time, as in 99 cases out michael@0: of 100, the lists' order is kept from one scanline to the next. michael@0: We can thus implement it with two simple singly-linked lists, michael@0: sorted by a classic bubble-sort, which takes a minimum amount of michael@0: time when the lists are already sorted. michael@0: michael@0: A previous version of the rasterizer used more elaborate michael@0: structures, like arrays to perform `faster' sorting. It turned michael@0: out that this old scheme is not faster than the one described michael@0: above. michael@0: michael@0: Once the spans have been `created', we can simply draw them in michael@0: the target bitmap. michael@0: michael@0: ------------------------------------------------------------------------ michael@0: michael@0: Copyright 2003, 2007 by michael@0: David Turner, Robert Wilhelm, and Werner Lemberg. michael@0: michael@0: This file is part of the FreeType project, and may only be used, michael@0: modified, and distributed under the terms of the FreeType project michael@0: license, LICENSE.TXT. By continuing to use, modify, or distribute this michael@0: file you indicate that you have read the license and understand and michael@0: accept it fully. michael@0: michael@0: michael@0: --- end of raster.txt --- michael@0: michael@0: Local Variables: michael@0: coding: utf-8 michael@0: End: