misc/libfreetype/docs/raster.txt
author nemo
Tue, 06 Sep 2011 17:10:03 -0400
changeset 5796 663eea4da344
parent 5172 88f2e05288ba
permissions -rw-r--r--
Another mass hat rename, because people were just about finished fixing their teams.
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
5172
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
     1
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
     2
                   How FreeType's rasterizer work
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
     3
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
     4
                          by David Turner
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
     5
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
     6
                        Revised 2007-Feb-01
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
     7
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
     8
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
     9
This file  is an  attempt to explain  the internals of  the FreeType
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    10
rasterizer.  The  rasterizer is of  quite general purpose  and could
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    11
easily be integrated into other programs.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    12
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    13
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    14
  I. Introduction
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    15
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    16
 II. Rendering Technology
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    17
     1. Requirements
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    18
     2. Profiles and Spans
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    19
        a. Sweeping the Shape
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    20
        b. Decomposing Outlines into Profiles
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    21
        c. The Render Pool
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    22
        d. Computing Profiles Extents
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    23
        e. Computing Profiles Coordinates
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    24
        f. Sweeping and Sorting the Spans
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    25
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    26
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    27
I. Introduction
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    28
===============
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    29
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    30
  A  rasterizer is  a library  in charge  of converting  a vectorial
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    31
  representation of a shape  into a bitmap.  The FreeType rasterizer
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    32
  has  been  originally developed  to  render  the  glyphs found  in
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    33
  TrueType  files, made  up  of segments  and second-order  Béziers.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    34
  Meanwhile it has been extended to render third-order Bézier curves
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    35
  also.   This  document  is   an  explanation  of  its  design  and
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    36
  implementation.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    37
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    38
  While  these explanations start  from the  basics, a  knowledge of
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    39
  common rasterization techniques is assumed.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    40
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    41
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    42
II. Rendering Technology
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    43
========================
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    44
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    45
1. Requirements
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    46
---------------
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    47
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    48
  We  assume that  all scaling,  rotating, hinting,  etc.,  has been
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    49
  already done.  The glyph is thus  described by a list of points in
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    50
  the device space.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    51
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    52
  - All point coordinates  are in the 26.6 fixed  float format.  The
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    53
    used orientation is:
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    54
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    55
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    56
       ^ y
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    57
       |         reference orientation
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    58
       |
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    59
       *----> x
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    60
      0
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    61
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    62
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    63
    `26.6' means  that 26 bits  are used for  the integer part  of a
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    64
    value   and  6   bits  are   used  for   the   fractional  part.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    65
    Consequently, the `distance'  between two neighbouring pixels is
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    66
    64 `units' (1 unit = 1/64th of a pixel).
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    67
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    68
    Note  that, for  the rasterizer,  pixel centers  are  located at
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    69
    integer   coordinates.   The   TrueType   bytecode  interpreter,
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    70
    however, assumes that  the lower left edge of  a pixel (which is
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    71
    taken  to be  a square  with  a length  of 1  unit) has  integer
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    72
    coordinates.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    73
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    74
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    75
        ^ y                                        ^ y
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    76
        |                                          |
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    77
        |            (1,1)                         |      (0.5,0.5)
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    78
        +-----------+                        +-----+-----+
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    79
        |           |                        |     |     |
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    80
        |           |                        |     |     |
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    81
        |           |                        |     o-----+-----> x
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    82
        |           |                        |   (0,0)   |
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    83
        |           |                        |           |
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    84
        o-----------+-----> x                +-----------+
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    85
      (0,0)                             (-0.5,-0.5)
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    86
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    87
   TrueType bytecode interpreter          FreeType rasterizer
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    88
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    89
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    90
    A pixel line in the target bitmap is called a `scanline'.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    91
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    92
  - A  glyph  is  usually  made  of several  contours,  also  called
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    93
    `outlines'.  A contour is simply a closed curve that delimits an
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    94
    outer or inner region of the glyph.  It is described by a series
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    95
    of successive points of the points table.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    96
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    97
    Each point  of the glyph  has an associated flag  that indicates
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    98
    whether  it is  `on' or  `off' the  curve.  Two  successive `on'
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    99
    points indicate a line segment joining the two points.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   100
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   101
    One `off' point amidst two `on' points indicates a second-degree
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   102
    (conic)  Bézier parametric  arc, defined  by these  three points
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   103
    (the `off' point being the  control point, and the `on' ones the
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   104
    start and end points).  Similarly, a third-degree (cubic) Bézier
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   105
    curve  is described  by four  points (two  `off'  control points
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   106
    between two `on' points).
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   107
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   108
    Finally,  for  second-order curves  only,  two successive  `off'
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   109
    points  forces the  rasterizer to  create, during  rendering, an
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   110
    `on'  point amidst them,  at their  exact middle.   This greatly
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   111
    facilitates the  definition of  successive Bézier arcs.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   112
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   113
  The parametric form of a second-order Bézier curve is:
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   114
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   115
      P(t) = (1-t)^2*P1 + 2*t*(1-t)*P2 + t^2*P3
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   116
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   117
      (P1 and P3 are the end points, P2 the control point.)
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   118
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   119
  The parametric form of a third-order Bézier curve is:
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   120
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   121
      P(t) = (1-t)^3*P1 + 3*t*(1-t)^2*P2 + 3*t^2*(1-t)*P3 + t^3*P4
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   122
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   123
      (P1 and P4 are the end points, P2 and P3 the control points.)
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   124
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   125
  For both formulae, t is a real number in the range [0..1].
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   126
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   127
  Note  that the rasterizer  does not  use these  formulae directly.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   128
  They exhibit,  however, one very  useful property of  Bézier arcs:
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   129
  Each  point of  the curve  is a  weighted average  of  the control
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   130
  points.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   131
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   132
  As all weights  are positive and always sum up  to 1, whatever the
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   133
  value  of t,  each arc  point lies  within the  triangle (polygon)
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   134
  defined by the arc's three (four) control points.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   135
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   136
  In  the following,  only second-order  curves are  discussed since
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   137
  rasterization of third-order curves is completely identical.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   138
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   139
  Here some samples for second-order curves.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   140
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   141
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   142
                                        *            # on curve
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   143
                                                     * off curve
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   144
                                     __---__
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   145
        #-__                      _--       -_
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   146
            --__                _-            -
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   147
                --__           #               \
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   148
                    --__                        #
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   149
                        -#
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   150
                                 Two `on' points
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   151
         Two `on' points       and one `off' point
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   152
                                  between them
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   153
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   154
                      *
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   155
        #            __      Two `on' points with two `off'
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   156
         \          -  -     points between them. The point
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   157
          \        /    \    marked `0' is the middle of the
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   158
           -      0      \   `off' points, and is a `virtual
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   159
            -_  _-       #   on' point where the curve passes.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   160
              --             It does not appear in the point
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   161
              *              list.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   162
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   163
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   164
2. Profiles and Spans
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   165
---------------------
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   166
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   167
  The following is a basic explanation of the _kind_ of computations
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   168
  made  by  the   rasterizer  to  build  a  bitmap   from  a  vector
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   169
  representation.  Note  that the actual  implementation is slightly
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   170
  different, due to performance tuning and other factors.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   171
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   172
  However, the following ideas remain  in the same category, and are
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   173
  more convenient to understand.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   174
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   175
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   176
  a. Sweeping the Shape
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   177
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   178
    The best way to fill a shape is to decompose it into a number of
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   179
    simple  horizontal segments,  then turn  them on  in  the target
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   180
    bitmap.  These segments are called `spans'.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   181
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   182
                __---__
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   183
             _--       -_
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   184
           _-            -
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   185
          -               \
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   186
         /                 \
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   187
        /                   \
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   188
       |                     \
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   189
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   190
                __---__         Example: filling a shape
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   191
             _----------_                with spans.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   192
           _--------------
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   193
          ----------------\
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   194
         /-----------------\    This is typically done from the top
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   195
        /                   \   to the bottom of the shape, in a
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   196
       |           |         \  movement called a `sweep'.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   197
                   V
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   198
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   199
                __---__
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   200
             _----------_
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   201
           _--------------
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   202
          ----------------\
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   203
         /-----------------\
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   204
        /-------------------\
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   205
       |---------------------\
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   206
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   207
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   208
    In  order  to draw  a  span,  the  rasterizer must  compute  its
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   209
    coordinates, which  are simply the x coordinates  of the shape's
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   210
    contours, taken on the y scanlines.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   211
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   212
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   213
                   /---/    |---|   Note that there are usually
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   214
                  /---/     |---|   several spans per scanline.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   215
        |        /---/      |---|
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   216
        |       /---/_______|---|   When rendering this shape to the
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   217
        V      /----------------|   current scanline y, we must
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   218
              /-----------------|   compute the x values of the
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   219
           a /----|         |---|   points a, b, c, and d.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   220
      - - - *     * - - - - *   * - - y -
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   221
           /     / b       c|   |d
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   222
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   223
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   224
                   /---/    |---|
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   225
                  /---/     |---|  And then turn on the spans a-b
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   226
                 /---/      |---|  and c-d.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   227
                /---/_______|---|
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   228
               /----------------|
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   229
              /-----------------|
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   230
           a /----|         |---|
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   231
      - - - ####### - - - - ##### - - y -
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   232
           /     / b       c|   |d
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   233
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   234
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   235
  b. Decomposing Outlines into Profiles
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   236
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   237
    For  each  scanline during  the  sweep,  we  need the  following
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   238
    information:
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   239
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   240
    o The  number of  spans on  the current  scanline, given  by the
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   241
      number of  shape points  intersecting the scanline  (these are
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   242
      the points a, b, c, and d in the above example).
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   243
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   244
    o The x coordinates of these points.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   245
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   246
    x coordinates are  computed before the sweep, in  a phase called
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   247
    `decomposition' which converts the glyph into *profiles*.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   248
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   249
    Put it simply, a `profile'  is a contour's portion that can only
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   250
    be either ascending or descending,  i.e., it is monotonic in the
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   251
    vertical direction (we also say  y-monotonic).  There is no such
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   252
    thing as a horizontal profile, as we shall see.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   253
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   254
    Here are a few examples:
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   255
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   256
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   257
      this square
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   258
                                          1         2
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   259
         ---->----     is made of two
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   260
        |         |                       |         |
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   261
        |         |       profiles        |         |
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   262
        ^         v                       ^    +    v
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   263
        |         |                       |         |
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   264
        |         |                       |         |
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   265
         ----<----
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   266
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   267
                                         up        down
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   268
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   269
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   270
      this triangle
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   271
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   272
             P2                             1          2
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   273
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   274
             |\        is made of two       |         \
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   275
          ^  | \  \                         |          \
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   276
          | |   \  \      profiles         |            \      |
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   277
         |  |    \  v                  ^   |             \     |
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   278
           |      \                    |  |         +     \    v
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   279
           |       \                   |  |                \
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   280
        P1 ---___   \                     ---___            \
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   281
                 ---_\                          ---_         \
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   282
             <--__     P3                   up           down
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   283
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   284
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   285
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   286
      A more general contour can be made of more than two profiles:
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   287
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   288
              __     ^
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   289
             /  |   /  ___          /    |
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   290
            /   |     /   |        /     |       /     |
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   291
           |    |    /   /    =>  |      v      /     /
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   292
           |    |   |   |         |      |     ^     |
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   293
        ^  |    |___|   |  |      ^   +  |  +  |  +  v
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   294
        |  |           |   v      |                 |
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   295
           |           |          |           up    |
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   296
           |___________|          |    down         |
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   297
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   298
                <--               up              down
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   299
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   300
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   301
    Successive  profiles are  always joined  by  horizontal segments
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   302
    that are not part of the profiles themselves.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   303
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   304
    For  the  rasterizer,  a  profile  is  simply  an  *array*  that
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   305
    associates  one  horizontal *pixel*  coordinate  to each  bitmap
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   306
    *scanline*  crossed  by  the  contour's section  containing  the
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   307
    profile.  Note that profiles are *oriented* up or down along the
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   308
    glyph's original flow orientation.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   309
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   310
    In other graphics libraries, profiles are also called `edges' or
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   311
    `edgelists'.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   312
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   313
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   314
  c. The Render Pool
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   315
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   316
    FreeType  has been designed  to be  able to  run well  on _very_
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   317
    light systems, including embedded systems with very few memory.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   318
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   319
    A render pool  will be allocated once; the  rasterizer uses this
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   320
    pool for all  its needs by managing this  memory directly in it.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   321
    The  algorithms that are  used for  profile computation  make it
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   322
    possible to use  the pool as a simple  growing heap.  This means
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   323
    that this  memory management is  actually quite easy  and faster
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   324
    than any kind of malloc()/free() combination.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   325
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   326
    Moreover,  we'll see  later that  the rasterizer  is  able, when
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   327
    dealing with profiles too large  and numerous to lie all at once
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   328
    in  the render  pool, to  immediately decompose  recursively the
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   329
    rendering process  into independent sub-tasks,  each taking less
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   330
    memory to be performed (see `sub-banding' below).
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   331
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   332
    The  render pool doesn't  need to  be large.   A 4KByte  pool is
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   333
    enough for nearly all renditions, though nearly 100% slower than
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   334
    a more comfortable 16KByte or 32KByte pool (that was tested with
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   335
    complex glyphs at sizes over 500 pixels).
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   336
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   337
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   338
  d. Computing Profiles Extents
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   339
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   340
    Remember that a profile is an array, associating a _scanline_ to
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   341
    the x pixel coordinate of its intersection with a contour.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   342
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   343
    Though it's not exactly how the FreeType rasterizer works, it is
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   344
    convenient  to think  that  we need  a  profile's height  before
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   345
    allocating it in the pool and computing its coordinates.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   346
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   347
    The profile's height  is the number of scanlines  crossed by the
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   348
    y-monotonic section of a contour.  We thus need to compute these
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   349
    sections from  the vectorial description.  In order  to do that,
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   350
    we are  obliged to compute all  (local and global)  y extrema of
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   351
    the glyph (minima and maxima).
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   352
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   353
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   354
           P2             For instance, this triangle has only
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   355
                          two y-extrema, which are simply
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   356
           |\
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   357
           | \               P2.y  as a vertical maximum
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   358
          |   \              P3.y  as a vertical minimum
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   359
          |    \
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   360
         |      \            P1.y is not a vertical extremum (though
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   361
         |       \           it is a horizontal minimum, which we
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   362
      P1 ---___   \          don't need).
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   363
               ---_\
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   364
                     P3
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   365
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   366
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   367
    Note  that the  extrema are  expressed  in pixel  units, not  in
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   368
    scanlines.   The triangle's  height  is certainly  (P3.y-P2.y+1)
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   369
    pixel  units,   but  its  profiles'  heights   are  computed  in
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   370
    scanlines.  The exact conversion is simple:
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   371
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   372
      - min scanline = FLOOR  ( min y )
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   373
      - max scanline = CEILING( max y )
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   374
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   375
    A problem  arises with Bézier  Arcs.  While a segment  is always
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   376
    necessarily y-monotonic (i.e.,  flat, ascending, or descending),
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   377
    which makes extrema computations easy,  the ascent of an arc can
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   378
    vary between its control points.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   379
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   380
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   381
                          P2
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   382
                         *
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   383
                                       # on curve
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   384
                                       * off curve
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   385
                   __-x--_
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   386
                _--       -_
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   387
          P1  _-            -          A non y-monotonic Bézier arc.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   388
             #               \
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   389
                              -        The arc goes from P1 to P3.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   390
                               \
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   391
                                \  P3
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   392
                                 #
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   393
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   394
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   395
    We first  need to be  able to easily detect  non-monotonic arcs,
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   396
    according to  their control points.  I will  state here, without
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   397
    proof, that the monotony condition can be expressed as:
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   398
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   399
      P1.y <= P2.y <= P3.y   for an ever-ascending arc
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   400
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   401
      P1.y >= P2.y >= P3.y   for an ever-descending arc
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   402
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   403
    with the special case of
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   404
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   405
      P1.y = P2.y = P3.y     where the arc is said to be `flat'.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   406
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   407
    As  you can  see, these  conditions can  be very  easily tested.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   408
    They are, however, extremely important, as any arc that does not
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   409
    satisfy them necessarily contains an extremum.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   410
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   411
    Note  also that  a monotonic  arc can  contain an  extremum too,
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   412
    which is then one of its `on' points:
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   413
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   414
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   415
        P1           P2
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   416
          #---__   *         P1P2P3 is ever-descending, but P1
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   417
                -_           is an y-extremum.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   418
                  -
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   419
           ---_    \
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   420
               ->   \
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   421
                     \  P3
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   422
                      #
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   423
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   424
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   425
    Let's go back to our previous example:
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   426
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   427
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   428
                          P2
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   429
                         *
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   430
                                       # on curve
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   431
                                       * off curve
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   432
                   __-x--_
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   433
                _--       -_
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   434
          P1  _-            -          A non-y-monotonic Bézier arc.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   435
             #               \
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   436
                              -        Here we have
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   437
                               \              P2.y >= P1.y &&
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   438
                                \  P3         P2.y >= P3.y      (!)
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   439
                                 #
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   440
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   441
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   442
    We need to  compute the vertical maximum of this  arc to be able
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   443
    to compute a profile's height (the point marked by an `x').  The
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   444
    arc's equation indicates that  a direct computation is possible,
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   445
    but  we rely  on a  different technique,  which use  will become
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   446
    apparent soon.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   447
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   448
    Bézier  arcs have  the  special property  of  being very  easily
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   449
    decomposed into two sub-arcs,  which are themselves Bézier arcs.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   450
    Moreover, it is easy to prove that there is at most one vertical
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   451
    extremum on  each Bézier arc (for  second-degree curves; similar
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   452
    conditions can be found for third-order arcs).
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   453
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   454
    For instance,  the following arc  P1P2P3 can be  decomposed into
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   455
    two sub-arcs Q1Q2Q3 and R1R2R3:
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   456
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   457
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   458
                    P2
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   459
                   *
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   460
                                    # on  curve
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   461
                                    * off curve
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   462
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   463
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   464
                                    original Bézier arc P1P2P3.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   465
                __---__
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   466
             _--       --_
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   467
           _-             -_
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   468
          -                 -
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   469
         /                   \
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   470
        /                     \
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   471
       #                       #
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   472
     P1                         P3
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   473
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   474
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   475
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   476
                    P2
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   477
                   *
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   478
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   479
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   480
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   481
                   Q3                 Decomposed into two subarcs
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   482
          Q2                R2        Q1Q2Q3 and R1R2R3
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   483
            *   __-#-__   *
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   484
             _--       --_
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   485
           _-       R1    -_          Q1 = P1         R3 = P3
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   486
          -                 -         Q2 = (P1+P2)/2  R2 = (P2+P3)/2
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   487
         /                   \
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   488
        /                     \            Q3 = R1 = (Q2+R2)/2
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   489
       #                       #
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   490
     Q1                         R3    Note that Q2, R2, and Q3=R1
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   491
                                      are on a single line which is
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   492
                                      tangent to the curve.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   493
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   494
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   495
    We have then decomposed  a non-y-monotonic Bézier curve into two
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   496
    smaller sub-arcs.  Note that in the above drawing, both sub-arcs
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   497
    are monotonic, and that the extremum is then Q3=R1.  However, in
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   498
    a  more general  case,  only  one sub-arc  is  guaranteed to  be
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   499
    monotonic.  Getting back to our former example:
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   500
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   501
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   502
                    Q2
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   503
                   *
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   504
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   505
                   __-x--_ R1
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   506
                _--       #_
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   507
          Q1  _-        Q3  -   R2
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   508
             #               \ *
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   509
                              -
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   510
                               \
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   511
                                \  R3
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   512
                                 #
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   513
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   514
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   515
    Here, we see that,  though Q1Q2Q3 is still non-monotonic, R1R2R3
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   516
    is ever  descending: We  thus know that  it doesn't  contain the
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   517
    extremum.  We can then re-subdivide Q1Q2Q3 into two sub-arcs and
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   518
    go  on recursively,  stopping  when we  encounter two  monotonic
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   519
    subarcs, or when the subarcs become simply too small.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   520
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   521
    We  will finally  find  the vertical  extremum.   Note that  the
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   522
    iterative process of finding an extremum is called `flattening'.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   523
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   524
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   525
  e. Computing Profiles Coordinates
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   526
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   527
    Once we have the height of each profile, we are able to allocate
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   528
    it in the render pool.   The next task is to compute coordinates
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   529
    for each scanline.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   530
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   531
    In  the case  of segments,  the computation  is straightforward,
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   532
    using  the  Euclidean   algorithm  (also  known  as  Bresenham).
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   533
    However, for Bézier arcs, the job is a little more complicated.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   534
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   535
    We assume  that all Béziers that  are part of a  profile are the
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   536
    result of  flattening the curve,  which means that they  are all
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   537
    y-monotonic (ascending  or descending, and never  flat).  We now
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   538
    have  to compute the  intersections of  arcs with  the profile's
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   539
    scanlines.  One  way is  to use a  similar scheme  to flattening
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   540
    called `stepping'.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   541
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   542
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   543
                                 Consider this arc, going from P1 to
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   544
      ---------------------      P3.  Suppose that we need to
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   545
                                 compute its intersections with the
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   546
                                 drawn scanlines.  As already
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   547
      ---------------------      mentioned this can be done
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   548
                                 directly, but the involved
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   549
          * P2         _---# P3  algorithm is far too slow.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   550
      ------------- _--  --
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   551
                  _-
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   552
                _/               Instead, it is still possible to
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   553
      ---------/-----------      use the decomposition property in
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   554
              /                  the same recursive way, i.e.,
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   555
             |                   subdivide the arc into subarcs
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   556
      ------|--------------      until these get too small to cross
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   557
            |                    more than one scanline!
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   558
           |
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   559
      -----|---------------      This is very easily done using a
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   560
          |                      rasterizer-managed stack of
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   561
          |                      subarcs.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   562
          # P1
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   563
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   564
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   565
  f. Sweeping and Sorting the Spans
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   566
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   567
    Once all our profiles have  been computed, we begin the sweep to
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   568
    build (and fill) the spans.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   569
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   570
    As both the  TrueType and Type 1 specifications  use the winding
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   571
    fill  rule (but  with opposite  directions), we  place,  on each
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   572
    scanline, the present profiles in two separate lists.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   573
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   574
    One  list,  called  the  `left'  one,  only  contains  ascending
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   575
    profiles, while  the other `right' list  contains the descending
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   576
    profiles.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   577
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   578
    As  each glyph  is made  of  closed curves,  a simple  geometric
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   579
    property ensures that  the two lists contain the  same number of
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   580
    elements.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   581
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   582
    Creating spans is thus straightforward:
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   583
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   584
    1. We sort each list in increasing horizontal order.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   585
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   586
    2. We pair  each value of  the left list with  its corresponding
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   587
       value in the right list.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   588
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   589
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   590
                   /     /  |   |          For example, we have here
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   591
                  /     /   |   |          four profiles.  Two of
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   592
                >/     /    |   |  |       them are ascending (1 &
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   593
              1//     /   ^ |   |  | 2     3), while the two others
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   594
              //     //  3| |   |  v       are descending (2 & 4).
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   595
              /     //4   | |   |          On the given scanline,
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   596
           a /     /<       |   |          the left list is (1,3),
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   597
      - - - *-----* - - - - *---* - - y -  and the right one is
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   598
           /     / b       c|   |d         (4,2) (sorted).
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   599
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   600
                                   There are then two spans, joining
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   601
                                   1 to 4 (i.e. a-b) and 3 to 2
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   602
                                   (i.e. c-d)!
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   603
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   604
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   605
    Sorting doesn't necessarily  take much time, as in  99 cases out
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   606
    of 100, the lists' order is  kept from one scanline to the next.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   607
    We can  thus implement it  with two simple  singly-linked lists,
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   608
    sorted by a classic bubble-sort, which takes a minimum amount of
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   609
    time when the lists are already sorted.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   610
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   611
    A  previous  version  of  the  rasterizer  used  more  elaborate
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   612
    structures, like arrays to  perform `faster' sorting.  It turned
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   613
    out that  this old scheme is  not faster than  the one described
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   614
    above.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   615
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   616
    Once the spans  have been `created', we can  simply draw them in
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   617
    the target bitmap.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   618
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   619
------------------------------------------------------------------------
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   620
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   621
Copyright 2003, 2007 by
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   622
David Turner, Robert Wilhelm, and Werner Lemberg.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   623
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   624
This  file  is  part  of the  FreeType  project, and may  only be  used,
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   625
modified,  and  distributed  under  the  terms of  the FreeType  project
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   626
license, LICENSE.TXT.   By continuing to use, modify, or distribute this
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   627
file you  indicate that  you have  read the  license and understand  and
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   628
accept it fully.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   629
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   630
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   631
--- end of raster.txt ---
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   632
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   633
Local Variables:
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   634
coding: utf-8
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   635
End: