--- a/misc/libfreetype/docs/raster.txt Fri Oct 11 11:55:31 2013 +0200
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,635 +0,0 @@
-
- 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: