hedgewars: comparison misc/libfreetype/docs/raster.txt

equal deleted inserted replaced

-:92af50454cf2
+:8054d9d775fd
-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:

branch	webgl
changeset 9521	8054d9d775fd
parent 9282	92af50454cf2
parent 9519	b8b5c82eb61b
child 9950	2759212a27de