← Back to branch summary

~oif-team/ubuntu/natty/qt4-x11/xi2.1

« back to all changes in this revision

Viewing changes to src/3rdparty/freetype/docs/raster.txt

  • Committer: Bazaar Package Importer
  • Author(s): Adam Conrad
  • Date: 2005-08-24 04:09:09 UTC
  • Revision ID: james.westby@ubuntu.com-20050824040909-xmxe9jfr4a0w5671
Tags: upstream-4.0.0
Import upstream version 4.0.0

Show diffs side-by-side

added added

removed removed

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