--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/misc/libfreetype/docs/raster.txt Mon Apr 25 01:46:54 2011 +0200
@@ -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: