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