source: trunk/poppler/freetype-2.1.10/src/smooth/ftgrays.c @ 2

Last change on this file since 2 was 2, checked in by Eugene Romanenko, 16 years ago

First import

File size: 57.4 KB
Line 
1/***************************************************************************/
2/*                                                                         */
3/*  ftgrays.c                                                              */
4/*                                                                         */
5/*    A new `perfect' anti-aliasing renderer (body).                       */
6/*                                                                         */
7/*  Copyright 2000-2001, 2002, 2003, 2005 by                               */
8/*  David Turner, Robert Wilhelm, and Werner Lemberg.                      */
9/*                                                                         */
10/*  This file is part of the FreeType project, and may only be used,       */
11/*  modified, and distributed under the terms of the FreeType project      */
12/*  license, LICENSE.TXT.  By continuing to use, modify, or distribute     */
13/*  this file you indicate that you have read the license and              */
14/*  understand and accept it fully.                                        */
15/*                                                                         */
16/***************************************************************************/
17
18  /*************************************************************************/
19  /*                                                                       */
20  /* This file can be compiled without the rest of the FreeType engine, by */
21  /* defining the _STANDALONE_ macro when compiling it.  You also need to  */
22  /* put the files `ftgrays.h' and `ftimage.h' into the current            */
23  /* compilation directory.  Typically, you could do something like        */
24  /*                                                                       */
25  /* - copy `src/smooth/ftgrays.c' (this file) to your current directory   */
26  /*                                                                       */
27  /* - copy `include/freetype/ftimage.h' and `src/smooth/ftgrays.h' to the */
28  /*   same directory                                                      */
29  /*                                                                       */
30  /* - compile `ftgrays' with the _STANDALONE_ macro defined, as in        */
31  /*                                                                       */
32  /*     cc -c -D_STANDALONE_ ftgrays.c                                    */
33  /*                                                                       */
34  /* The renderer can be initialized with a call to                        */
35  /* `ft_gray_raster.raster_new'; an anti-aliased bitmap can be generated  */
36  /* with a call to `ft_gray_raster.raster_render'.                        */
37  /*                                                                       */
38  /* See the comments and documentation in the file `ftimage.h' for more   */
39  /* details on how the raster works.                                      */
40  /*                                                                       */
41  /*************************************************************************/
42
43  /*************************************************************************/
44  /*                                                                       */
45  /* This is a new anti-aliasing scan-converter for FreeType 2.  The       */
46  /* algorithm used here is _very_ different from the one in the standard  */
47  /* `ftraster' module.  Actually, `ftgrays' computes the _exact_          */
48  /* coverage of the outline on each pixel cell.                           */
49  /*                                                                       */
50  /* It is based on ideas that I initially found in Raph Levien's          */
51  /* excellent LibArt graphics library (see http://www.levien.com/libart   */
52  /* for more information, though the web pages do not tell anything       */
53  /* about the renderer; you'll have to dive into the source code to       */
54  /* understand how it works).                                             */
55  /*                                                                       */
56  /* Note, however, that this is a _very_ different implementation         */
57  /* compared to Raph's.  Coverage information is stored in a very         */
58  /* different way, and I don't use sorted vector paths.  Also, it doesn't */
59  /* use floating point values.                                            */
60  /*                                                                       */
61  /* This renderer has the following advantages:                           */
62  /*                                                                       */
63  /* - It doesn't need an intermediate bitmap.  Instead, one can supply a  */
64  /*   callback function that will be called by the renderer to draw gray  */
65  /*   spans on any target surface.  You can thus do direct composition on */
66  /*   any kind of bitmap, provided that you give the renderer the right   */
67  /*   callback.                                                           */
68  /*                                                                       */
69  /* - A perfect anti-aliaser, i.e., it computes the _exact_ coverage on   */
70  /*   each pixel cell.                                                    */
71  /*                                                                       */
72  /* - It performs a single pass on the outline (the `standard' FT2        */
73  /*   renderer makes two passes).                                         */
74  /*                                                                       */
75  /* - It can easily be modified to render to _any_ number of gray levels  */
76  /*   cheaply.                                                            */
77  /*                                                                       */
78  /* - For small (< 20) pixel sizes, it is faster than the standard        */
79  /*   renderer.                                                           */
80  /*                                                                       */
81  /*************************************************************************/
82
83
84
85/* experimental support for gamma correction within the rasterizer */
86#define xxxGRAYS_USE_GAMMA
87
88
89  /*************************************************************************/
90  /*                                                                       */
91  /* The macro FT_COMPONENT is used in trace mode.  It is an implicit      */
92  /* parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log  */
93  /* messages during execution.                                            */
94  /*                                                                       */
95#undef  FT_COMPONENT
96#define FT_COMPONENT  trace_smooth
97
98
99#define ErrRaster_MemoryOverflow   -4
100
101
102#ifdef _STANDALONE_
103
104#include <string.h>             /* for ft_memcpy() */
105#include <setjmp.h>
106#include <limits.h>
107#define FT_UINT_MAX  UINT_MAX
108
109#define ft_memset   memset
110
111#define ft_setjmp   setjmp
112#define ft_longjmp  longjmp
113#define ft_jmp_buf  jmp_buf
114
115
116#define ErrRaster_Invalid_Mode     -2
117#define ErrRaster_Invalid_Outline  -1
118
119#define FT_BEGIN_HEADER
120#define FT_END_HEADER
121
122#include "ftimage.h"
123#include "ftgrays.h"
124
125  /* This macro is used to indicate that a function parameter is unused. */
126  /* Its purpose is simply to reduce compiler warnings.  Note also that  */
127  /* simply defining it as `(void)x' doesn't avoid warnings with certain */
128  /* ANSI compilers (e.g. LCC).                                          */
129#define FT_UNUSED( x )  (x) = (x)
130
131  /* Disable the tracing mechanism for simplicity -- developers can      */
132  /* activate it easily by redefining these two macros.                  */
133#ifndef FT_ERROR
134#define FT_ERROR( x )  do ; while ( 0 )     /* nothing */
135#endif
136
137#ifndef FT_TRACE
138#define FT_TRACE( x )  do ; while ( 0 )     /* nothing */
139#endif
140
141
142#else /* _STANDALONE_ */
143
144
145#include <ft2build.h>
146#include "ftgrays.h"
147#include FT_INTERNAL_OBJECTS_H
148#include FT_INTERNAL_DEBUG_H
149#include FT_OUTLINE_H
150
151#include "ftsmerrs.h"
152
153#define ErrRaster_Invalid_Mode     Smooth_Err_Cannot_Render_Glyph
154#define ErrRaster_Invalid_Outline  Smooth_Err_Invalid_Outline
155
156
157#endif /* _STANDALONE_ */
158
159
160#ifndef FT_MEM_SET
161#define FT_MEM_SET( d, s, c )  ft_memset( d, s, c )
162#endif
163
164#ifndef FT_MEM_ZERO
165#define FT_MEM_ZERO( dest, count )  FT_MEM_SET( dest, 0, count )
166#endif
167
168  /* define this to dump debugging information */
169#define xxxDEBUG_GRAYS
170
171  /* as usual, for the speed hungry :-) */
172
173#ifndef FT_STATIC_RASTER
174
175
176#define RAS_ARG   PRaster  raster
177#define RAS_ARG_  PRaster  raster,
178
179#define RAS_VAR   raster
180#define RAS_VAR_  raster,
181
182#define ras       (*raster)
183
184
185#else /* FT_STATIC_RASTER */
186
187
188#define RAS_ARG   /* empty */
189#define RAS_ARG_  /* empty */
190#define RAS_VAR   /* empty */
191#define RAS_VAR_  /* empty */
192
193  static TRaster  ras;
194
195
196#endif /* FT_STATIC_RASTER */
197
198
199  /* must be at least 6 bits! */
200#define PIXEL_BITS  8
201
202#define ONE_PIXEL       ( 1L << PIXEL_BITS )
203#define PIXEL_MASK      ( -1L << PIXEL_BITS )
204#define TRUNC( x )      ( (TCoord)((x) >> PIXEL_BITS) )
205#define SUBPIXELS( x )  ( (TPos)(x) << PIXEL_BITS )
206#define FLOOR( x )      ( (x) & -ONE_PIXEL )
207#define CEILING( x )    ( ( (x) + ONE_PIXEL - 1 ) & -ONE_PIXEL )
208#define ROUND( x )      ( ( (x) + ONE_PIXEL / 2 ) & -ONE_PIXEL )
209
210#if PIXEL_BITS >= 6
211#define UPSCALE( x )    ( (x) << ( PIXEL_BITS - 6 ) )
212#define DOWNSCALE( x )  ( (x) >> ( PIXEL_BITS - 6 ) )
213#else
214#define UPSCALE( x )    ( (x) >> ( 6 - PIXEL_BITS ) )
215#define DOWNSCALE( x )  ( (x) << ( 6 - PIXEL_BITS ) )
216#endif
217
218  /* Define this if you want to use a more compact storage scheme.  This   */
219  /* increases the number of cells available in the render pool but slows  */
220  /* down the rendering a bit.  It is useful if you have a really tiny     */
221  /* render pool.                                                          */
222#undef GRAYS_COMPACT
223
224
225  /*************************************************************************/
226  /*                                                                       */
227  /*   TYPE DEFINITIONS                                                    */
228  /*                                                                       */
229
230  /* don't change the following types to FT_Int or FT_Pos, since we might */
231  /* need to define them to "float" or "double" when experimenting with   */
232  /* new algorithms                                                       */
233
234  typedef int   TCoord;   /* integer scanline/pixel coordinate */
235  typedef long  TPos;     /* sub-pixel coordinate              */
236
237  /* determine the type used to store cell areas.  This normally takes at */
238  /* least PIXEL_BITS*2 + 1 bits.  On 16-bit systems, we need to use      */
239  /* `long' instead of `int', otherwise bad things happen                 */
240
241#if PIXEL_BITS <= 7
242
243  typedef int   TArea;
244
245#else /* PIXEL_BITS >= 8 */
246
247  /* approximately determine the size of integers using an ANSI-C header */
248#if FT_UINT_MAX == 0xFFFFU
249  typedef long  TArea;
250#else
251  typedef int  TArea;
252#endif
253
254#endif /* PIXEL_BITS >= 8 */
255
256
257  /* maximal number of gray spans in a call to the span callback */
258#define FT_MAX_GRAY_SPANS  32
259
260
261#ifdef GRAYS_COMPACT
262
263  typedef struct  TCell_
264  {
265    short  x     : 14;
266    short  y     : 14;
267    int    cover : PIXEL_BITS + 2;
268    int    area  : PIXEL_BITS * 2 + 2;
269
270  } TCell, *PCell;
271
272#else /* GRAYS_COMPACT */
273
274  typedef struct  TCell_
275  {
276    TCoord  x;
277    TCoord  y;
278    int     cover;
279    TArea   area;
280
281  } TCell, *PCell;
282
283#endif /* GRAYS_COMPACT */
284
285
286  typedef struct  TRaster_
287  {
288    PCell   cells;
289    int     max_cells;
290    int     num_cells;
291
292    TPos    min_ex, max_ex;
293    TPos    min_ey, max_ey;
294
295    TArea   area;
296    int     cover;
297    int     invalid;
298
299    TCoord  ex, ey;
300    TCoord  cx, cy;
301    TPos    x,  y;
302
303    TPos    last_ey;
304
305    FT_Vector   bez_stack[32 * 3 + 1];
306    int         lev_stack[32];
307
308    FT_Outline  outline;
309    FT_Bitmap   target;
310    FT_BBox     clip_box;
311
312    FT_Span     gray_spans[FT_MAX_GRAY_SPANS];
313    int         num_gray_spans;
314
315    FT_Raster_Span_Func  render_span;
316    void*                render_span_data;
317    int                  span_y;
318
319    int  band_size;
320    int  band_shoot;
321    int  conic_level;
322    int  cubic_level;
323
324    void*       memory;
325    ft_jmp_buf  jump_buffer;
326
327#ifdef GRAYS_USE_GAMMA
328    unsigned char  gamma[257];
329#endif
330
331  } TRaster, *PRaster;
332
333
334  /*************************************************************************/
335  /*                                                                       */
336  /* Initialize the cells table.                                           */
337  /*                                                                       */
338  static void
339  gray_init_cells( RAS_ARG_ void*  buffer,
340                   long            byte_size )
341  {
342    ras.cells     = (PCell)buffer;
343    ras.max_cells = (int)( byte_size / sizeof ( TCell ) );
344    ras.num_cells = 0;
345    ras.area      = 0;
346    ras.cover     = 0;
347    ras.invalid   = 1;
348  }
349
350
351  /*************************************************************************/
352  /*                                                                       */
353  /* Compute the outline bounding box.                                     */
354  /*                                                                       */
355  static void
356  gray_compute_cbox( RAS_ARG )
357  {
358    FT_Outline*  outline = &ras.outline;
359    FT_Vector*   vec     = outline->points;
360    FT_Vector*   limit   = vec + outline->n_points;
361
362
363    if ( outline->n_points <= 0 )
364    {
365      ras.min_ex = ras.max_ex = 0;
366      ras.min_ey = ras.max_ey = 0;
367      return;
368    }
369
370    ras.min_ex = ras.max_ex = vec->x;
371    ras.min_ey = ras.max_ey = vec->y;
372
373    vec++;
374
375    for ( ; vec < limit; vec++ )
376    {
377      TPos  x = vec->x;
378      TPos  y = vec->y;
379
380
381      if ( x < ras.min_ex ) ras.min_ex = x;
382      if ( x > ras.max_ex ) ras.max_ex = x;
383      if ( y < ras.min_ey ) ras.min_ey = y;
384      if ( y > ras.max_ey ) ras.max_ey = y;
385    }
386
387    /* truncate the bounding box to integer pixels */
388    ras.min_ex = ras.min_ex >> 6;
389    ras.min_ey = ras.min_ey >> 6;
390    ras.max_ex = ( ras.max_ex + 63 ) >> 6;
391    ras.max_ey = ( ras.max_ey + 63 ) >> 6;
392  }
393
394
395  /*************************************************************************/
396  /*                                                                       */
397  /* Record the current cell in the table.                                 */
398  /*                                                                       */
399  static void
400  gray_record_cell( RAS_ARG )
401  {
402    PCell  cell;
403
404
405    if ( !ras.invalid && ( ras.area | ras.cover ) )
406    {
407      if ( ras.num_cells >= ras.max_cells )
408        ft_longjmp( ras.jump_buffer, 1 );
409
410      cell        = ras.cells + ras.num_cells++;
411      cell->x     = (TCoord)(ras.ex - ras.min_ex);
412      cell->y     = (TCoord)(ras.ey - ras.min_ey);
413      cell->area  = ras.area;
414      cell->cover = ras.cover;
415    }
416  }
417
418
419  /*************************************************************************/
420  /*                                                                       */
421  /* Set the current cell to a new position.                               */
422  /*                                                                       */
423  static void
424  gray_set_cell( RAS_ARG_ TCoord  ex,
425                          TCoord  ey )
426  {
427    int  invalid, record, clean;
428
429
430    /* Move the cell pointer to a new position.  We set the `invalid'      */
431    /* flag to indicate that the cell isn't part of those we're interested */
432    /* in during the render phase.  This means that:                       */
433    /*                                                                     */
434    /* . the new vertical position must be within min_ey..max_ey-1.        */
435    /* . the new horizontal position must be strictly less than max_ex     */
436    /*                                                                     */
437    /* Note that if a cell is to the left of the clipping region, it is    */
438    /* actually set to the (min_ex-1) horizontal position.                 */
439
440    record  = 0;
441    clean   = 1;
442
443    invalid = ( ey < ras.min_ey || ey >= ras.max_ey || ex >= ras.max_ex );
444    if ( !invalid )
445    {
446      /* All cells that are on the left of the clipping region go to the */
447      /* min_ex - 1 horizontal position.                                 */
448      if ( ex < ras.min_ex )
449        ex = (TCoord)(ras.min_ex - 1);
450
451      /* if our position is new, then record the previous cell */
452      if ( ex != ras.ex || ey != ras.ey )
453        record = 1;
454      else
455        clean = ras.invalid;  /* do not clean if we didn't move from */
456                              /* a valid cell                        */
457    }
458
459    /* record the previous cell if needed (i.e., if we changed the cell */
460    /* position, or changed the `invalid' flag)                         */
461    if ( ras.invalid != invalid || record )
462      gray_record_cell( RAS_VAR );
463
464    if ( clean )
465    {
466      ras.area  = 0;
467      ras.cover = 0;
468    }
469
470    ras.invalid = invalid;
471    ras.ex      = ex;
472    ras.ey      = ey;
473  }
474
475
476  /*************************************************************************/
477  /*                                                                       */
478  /* Start a new contour at a given cell.                                  */
479  /*                                                                       */
480  static void
481  gray_start_cell( RAS_ARG_  TCoord  ex,
482                             TCoord  ey )
483  {
484    if ( ex < ras.min_ex )
485      ex = (TCoord)(ras.min_ex - 1);
486
487    ras.area    = 0;
488    ras.cover   = 0;
489    ras.ex      = ex;
490    ras.ey      = ey;
491    ras.last_ey = SUBPIXELS( ey );
492    ras.invalid = 0;
493
494    gray_set_cell( RAS_VAR_ ex, ey );
495  }
496
497
498  /*************************************************************************/
499  /*                                                                       */
500  /* Render a scanline as one or more cells.                               */
501  /*                                                                       */
502  static void
503  gray_render_scanline( RAS_ARG_  TCoord  ey,
504                                  TPos    x1,
505                                  TCoord  y1,
506                                  TPos    x2,
507                                  TCoord  y2 )
508  {
509    TCoord  ex1, ex2, fx1, fx2, delta;
510    long    p, first, dx;
511    int     incr, lift, mod, rem;
512
513
514    dx = x2 - x1;
515
516    ex1 = TRUNC( x1 ); /* if (ex1 >= ras.max_ex) ex1 = ras.max_ex-1; */
517    ex2 = TRUNC( x2 ); /* if (ex2 >= ras.max_ex) ex2 = ras.max_ex-1; */
518    fx1 = (TCoord)( x1 - SUBPIXELS( ex1 ) );
519    fx2 = (TCoord)( x2 - SUBPIXELS( ex2 ) );
520
521    /* trivial case.  Happens often */
522    if ( y1 == y2 )
523    {
524      gray_set_cell( RAS_VAR_ ex2, ey );
525      return;
526    }
527
528    /* everything is located in a single cell.  That is easy! */
529    /*                                                        */
530    if ( ex1 == ex2 )
531    {
532      delta      = y2 - y1;
533      ras.area  += (TArea)( fx1 + fx2 ) * delta;
534      ras.cover += delta;
535      return;
536    }
537
538    /* ok, we'll have to render a run of adjacent cells on the same */
539    /* scanline...                                                  */
540    /*                                                              */
541    p     = ( ONE_PIXEL - fx1 ) * ( y2 - y1 );
542    first = ONE_PIXEL;
543    incr  = 1;
544
545    if ( dx < 0 )
546    {
547      p     = fx1 * ( y2 - y1 );
548      first = 0;
549      incr  = -1;
550      dx    = -dx;
551    }
552
553    delta = (TCoord)( p / dx );
554    mod   = (TCoord)( p % dx );
555    if ( mod < 0 )
556    {
557      delta--;
558      mod += (TCoord)dx;
559    }
560
561    ras.area  += (TArea)( fx1 + first ) * delta;
562    ras.cover += delta;
563
564    ex1 += incr;
565    gray_set_cell( RAS_VAR_ ex1, ey );
566    y1  += delta;
567
568    if ( ex1 != ex2 )
569    {
570      p    = ONE_PIXEL * ( y2 - y1 + delta );
571      lift = (TCoord)( p / dx );
572      rem  = (TCoord)( p % dx );
573      if ( rem < 0 )
574      {
575        lift--;
576        rem += (TCoord)dx;
577      }
578
579      mod -= (int)dx;
580
581      while ( ex1 != ex2 )
582      {
583        delta = lift;
584        mod  += rem;
585        if ( mod >= 0 )
586        {
587          mod -= (TCoord)dx;
588          delta++;
589        }
590
591        ras.area  += (TArea)ONE_PIXEL * delta;
592        ras.cover += delta;
593        y1        += delta;
594        ex1       += incr;
595        gray_set_cell( RAS_VAR_ ex1, ey );
596      }
597    }
598
599    delta      = y2 - y1;
600    ras.area  += (TArea)( fx2 + ONE_PIXEL - first ) * delta;
601    ras.cover += delta;
602  }
603
604
605  /*************************************************************************/
606  /*                                                                       */
607  /* Render a given line as a series of scanlines.                         */
608  /*                                                                       */
609  static void
610  gray_render_line( RAS_ARG_ TPos  to_x,
611                             TPos  to_y )
612  {
613    TCoord  ey1, ey2, fy1, fy2;
614    TPos    dx, dy, x, x2;
615    long    p, first;
616    int     delta, rem, mod, lift, incr;
617
618
619    ey1 = TRUNC( ras.last_ey );
620    ey2 = TRUNC( to_y ); /* if (ey2 >= ras.max_ey) ey2 = ras.max_ey-1; */
621    fy1 = (TCoord)( ras.y - ras.last_ey );
622    fy2 = (TCoord)( to_y - SUBPIXELS( ey2 ) );
623
624    dx = to_x - ras.x;
625    dy = to_y - ras.y;
626
627    /* XXX: we should do something about the trivial case where dx == 0, */
628    /*      as it happens very often!                                    */
629
630    /* perform vertical clipping */
631    {
632      TCoord  min, max;
633
634
635      min = ey1;
636      max = ey2;
637      if ( ey1 > ey2 )
638      {
639        min = ey2;
640        max = ey1;
641      }
642      if ( min >= ras.max_ey || max < ras.min_ey )
643        goto End;
644    }
645
646    /* everything is on a single scanline */
647    if ( ey1 == ey2 )
648    {
649      gray_render_scanline( RAS_VAR_ ey1, ras.x, fy1, to_x, fy2 );
650      goto End;
651    }
652
653    /* vertical line - avoid calling gray_render_scanline */
654    incr = 1;
655
656    if ( dx == 0 )
657    {
658      TCoord  ex     = TRUNC( ras.x );
659      TCoord  two_fx = (TCoord)( ( ras.x - SUBPIXELS( ex ) ) << 1 );
660      TPos    area;
661
662
663      first = ONE_PIXEL;
664      if ( dy < 0 )
665      {
666        first = 0;
667        incr  = -1;
668      }
669
670      delta      = (int)( first - fy1 );
671      ras.area  += (TArea)two_fx * delta;
672      ras.cover += delta;
673      ey1       += incr;
674
675      gray_set_cell( raster, ex, ey1 );
676
677      delta = (int)( first + first - ONE_PIXEL );
678      area  = (TArea)two_fx * delta;
679      while ( ey1 != ey2 )
680      {
681        ras.area  += area;
682        ras.cover += delta;
683        ey1       += incr;
684        gray_set_cell( raster, ex, ey1 );
685      }
686
687      delta      = (int)( fy2 - ONE_PIXEL + first );
688      ras.area  += (TArea)two_fx * delta;
689      ras.cover += delta;
690      goto End;
691    }
692
693    /* ok, we have to render several scanlines */
694    p     = ( ONE_PIXEL - fy1 ) * dx;
695    first = ONE_PIXEL;
696    incr  = 1;
697
698    if ( dy < 0 )
699    {
700      p     = fy1 * dx;
701      first = 0;
702      incr  = -1;
703      dy    = -dy;
704    }
705
706    delta = (int)( p / dy );
707    mod   = (int)( p % dy );
708    if ( mod < 0 )
709    {
710      delta--;
711      mod += (TCoord)dy;
712    }
713
714    x = ras.x + delta;
715    gray_render_scanline( RAS_VAR_ ey1, ras.x, fy1, x, (TCoord)first );
716
717    ey1 += incr;
718    gray_set_cell( RAS_VAR_ TRUNC( x ), ey1 );
719
720    if ( ey1 != ey2 )
721    {
722      p     = ONE_PIXEL * dx;
723      lift  = (int)( p / dy );
724      rem   = (int)( p % dy );
725      if ( rem < 0 )
726      {
727        lift--;
728        rem += (int)dy;
729      }
730      mod -= (int)dy;
731
732      while ( ey1 != ey2 )
733      {
734        delta = lift;
735        mod  += rem;
736        if ( mod >= 0 )
737        {
738          mod -= (int)dy;
739          delta++;
740        }
741
742        x2 = x + delta;
743        gray_render_scanline( RAS_VAR_ ey1, x,
744                                       (TCoord)( ONE_PIXEL - first ), x2,
745                                       (TCoord)first );
746        x = x2;
747
748        ey1 += incr;
749        gray_set_cell( RAS_VAR_ TRUNC( x ), ey1 );
750      }
751    }
752
753    gray_render_scanline( RAS_VAR_ ey1, x,
754                                   (TCoord)( ONE_PIXEL - first ), to_x,
755                                   fy2 );
756
757  End:
758    ras.x       = to_x;
759    ras.y       = to_y;
760    ras.last_ey = SUBPIXELS( ey2 );
761  }
762
763
764  static void
765  gray_split_conic( FT_Vector*  base )
766  {
767    TPos  a, b;
768
769
770    base[4].x = base[2].x;
771    b = base[1].x;
772    a = base[3].x = ( base[2].x + b ) / 2;
773    b = base[1].x = ( base[0].x + b ) / 2;
774    base[2].x = ( a + b ) / 2;
775
776    base[4].y = base[2].y;
777    b = base[1].y;
778    a = base[3].y = ( base[2].y + b ) / 2;
779    b = base[1].y = ( base[0].y + b ) / 2;
780    base[2].y = ( a + b ) / 2;
781  }
782
783
784  static void
785  gray_render_conic( RAS_ARG_ const FT_Vector*  control,
786                              const FT_Vector*  to )
787  {
788    TPos        dx, dy;
789    int         top, level;
790    int*        levels;
791    FT_Vector*  arc;
792
793
794    dx = DOWNSCALE( ras.x ) + to->x - ( control->x << 1 );
795    if ( dx < 0 )
796      dx = -dx;
797    dy = DOWNSCALE( ras.y ) + to->y - ( control->y << 1 );
798    if ( dy < 0 )
799      dy = -dy;
800    if ( dx < dy )
801      dx = dy;
802
803    level = 1;
804    dx = dx / ras.conic_level;
805    while ( dx > 0 )
806    {
807      dx >>= 2;
808      level++;
809    }
810
811    /* a shortcut to speed things up */
812    if ( level <= 1 )
813    {
814      /* we compute the mid-point directly in order to avoid */
815      /* calling gray_split_conic()                          */
816      TPos   to_x, to_y, mid_x, mid_y;
817
818
819      to_x  = UPSCALE( to->x );
820      to_y  = UPSCALE( to->y );
821      mid_x = ( ras.x + to_x + 2 * UPSCALE( control->x ) ) / 4;
822      mid_y = ( ras.y + to_y + 2 * UPSCALE( control->y ) ) / 4;
823
824      gray_render_line( RAS_VAR_ mid_x, mid_y );
825      gray_render_line( RAS_VAR_ to_x, to_y );
826      return;
827    }
828
829    arc       = ras.bez_stack;
830    levels    = ras.lev_stack;
831    top       = 0;
832    levels[0] = level;
833
834    arc[0].x = UPSCALE( to->x );
835    arc[0].y = UPSCALE( to->y );
836    arc[1].x = UPSCALE( control->x );
837    arc[1].y = UPSCALE( control->y );
838    arc[2].x = ras.x;
839    arc[2].y = ras.y;
840
841    while ( top >= 0 )
842    {
843      level = levels[top];
844      if ( level > 1 )
845      {
846        /* check that the arc crosses the current band */
847        TPos  min, max, y;
848
849
850        min = max = arc[0].y;
851
852        y = arc[1].y;
853        if ( y < min ) min = y;
854        if ( y > max ) max = y;
855
856        y = arc[2].y;
857        if ( y < min ) min = y;
858        if ( y > max ) max = y;
859
860        if ( TRUNC( min ) >= ras.max_ey || TRUNC( max ) < ras.min_ey )
861          goto Draw;
862
863        gray_split_conic( arc );
864        arc += 2;
865        top++;
866        levels[top] = levels[top - 1] = level - 1;
867        continue;
868      }
869
870    Draw:
871      {
872        TPos  to_x, to_y, mid_x, mid_y;
873
874
875        to_x  = arc[0].x;
876        to_y  = arc[0].y;
877        mid_x = ( ras.x + to_x + 2 * arc[1].x ) / 4;
878        mid_y = ( ras.y + to_y + 2 * arc[1].y ) / 4;
879
880        gray_render_line( RAS_VAR_ mid_x, mid_y );
881        gray_render_line( RAS_VAR_ to_x, to_y );
882
883        top--;
884        arc -= 2;
885      }
886    }
887    return;
888  }
889
890
891  static void
892  gray_split_cubic( FT_Vector*  base )
893  {
894    TPos  a, b, c, d;
895
896
897    base[6].x = base[3].x;
898    c = base[1].x;
899    d = base[2].x;
900    base[1].x = a = ( base[0].x + c ) / 2;
901    base[5].x = b = ( base[3].x + d ) / 2;
902    c = ( c + d ) / 2;
903    base[2].x = a = ( a + c ) / 2;
904    base[4].x = b = ( b + c ) / 2;
905    base[3].x = ( a + b ) / 2;
906
907    base[6].y = base[3].y;
908    c = base[1].y;
909    d = base[2].y;
910    base[1].y = a = ( base[0].y + c ) / 2;
911    base[5].y = b = ( base[3].y + d ) / 2;
912    c = ( c + d ) / 2;
913    base[2].y = a = ( a + c ) / 2;
914    base[4].y = b = ( b + c ) / 2;
915    base[3].y = ( a + b ) / 2;
916  }
917
918
919  static void
920  gray_render_cubic( RAS_ARG_ const FT_Vector*  control1,
921                              const FT_Vector*  control2,
922                              const FT_Vector*  to )
923  {
924    TPos        dx, dy, da, db;
925    int         top, level;
926    int*        levels;
927    FT_Vector*  arc;
928
929
930    dx = DOWNSCALE( ras.x ) + to->x - ( control1->x << 1 );
931    if ( dx < 0 )
932      dx = -dx;
933    dy = DOWNSCALE( ras.y ) + to->y - ( control1->y << 1 );
934    if ( dy < 0 )
935      dy = -dy;
936    if ( dx < dy )
937      dx = dy;
938    da = dx;
939
940    dx = DOWNSCALE( ras.x ) + to->x - 3 * ( control1->x + control2->x );
941    if ( dx < 0 )
942      dx = -dx;
943    dy = DOWNSCALE( ras.y ) + to->y - 3 * ( control1->x + control2->y );
944    if ( dy < 0 )
945      dy = -dy;
946    if ( dx < dy )
947      dx = dy;
948    db = dx;
949
950    level = 1;
951    da    = da / ras.cubic_level;
952    db    = db / ras.conic_level;
953    while ( da > 0 || db > 0 )
954    {
955      da >>= 2;
956      db >>= 3;
957      level++;
958    }
959
960    if ( level <= 1 )
961    {
962      TPos   to_x, to_y, mid_x, mid_y;
963
964
965      to_x  = UPSCALE( to->x );
966      to_y  = UPSCALE( to->y );
967      mid_x = ( ras.x + to_x +
968                3 * UPSCALE( control1->x + control2->x ) ) / 8;
969      mid_y = ( ras.y + to_y +
970                3 * UPSCALE( control1->y + control2->y ) ) / 8;
971
972      gray_render_line( RAS_VAR_ mid_x, mid_y );
973      gray_render_line( RAS_VAR_ to_x, to_y );
974      return;
975    }
976
977    arc      = ras.bez_stack;
978    arc[0].x = UPSCALE( to->x );
979    arc[0].y = UPSCALE( to->y );
980    arc[1].x = UPSCALE( control2->x );
981    arc[1].y = UPSCALE( control2->y );
982    arc[2].x = UPSCALE( control1->x );
983    arc[2].y = UPSCALE( control1->y );
984    arc[3].x = ras.x;
985    arc[3].y = ras.y;
986
987    levels    = ras.lev_stack;
988    top       = 0;
989    levels[0] = level;
990
991    while ( top >= 0 )
992    {
993      level = levels[top];
994      if ( level > 1 )
995      {
996        /* check that the arc crosses the current band */
997        TPos  min, max, y;
998
999
1000        min = max = arc[0].y;
1001        y = arc[1].y;
1002        if ( y < min ) min = y;
1003        if ( y > max ) max = y;
1004        y = arc[2].y;
1005        if ( y < min ) min = y;
1006        if ( y > max ) max = y;
1007        y = arc[3].y;
1008        if ( y < min ) min = y;
1009        if ( y > max ) max = y;
1010        if ( TRUNC( min ) >= ras.max_ey || TRUNC( max ) < 0 )
1011          goto Draw;
1012        gray_split_cubic( arc );
1013        arc += 3;
1014        top ++;
1015        levels[top] = levels[top - 1] = level - 1;
1016        continue;
1017      }
1018
1019    Draw:
1020      {
1021        TPos  to_x, to_y, mid_x, mid_y;
1022
1023
1024        to_x  = arc[0].x;
1025        to_y  = arc[0].y;
1026        mid_x = ( ras.x + to_x + 3 * ( arc[1].x + arc[2].x ) ) / 8;
1027        mid_y = ( ras.y + to_y + 3 * ( arc[1].y + arc[2].y ) ) / 8;
1028
1029        gray_render_line( RAS_VAR_ mid_x, mid_y );
1030        gray_render_line( RAS_VAR_ to_x, to_y );
1031        top --;
1032        arc -= 3;
1033      }
1034    }
1035    return;
1036  }
1037
1038
1039  /* a macro comparing two cell pointers.  Returns true if a <= b. */
1040#if 1
1041
1042#define PACK( a )          ( ( (long)(a)->y << 16 ) + (a)->x )
1043#define LESS_THAN( a, b )  ( PACK( a ) < PACK( b ) )
1044
1045#else /* 1 */
1046
1047#define LESS_THAN( a, b )  ( (a)->y < (b)->y || \
1048                             ( (a)->y == (b)->y && (a)->x < (b)->x ) )
1049
1050#endif /* 1 */
1051
1052#define SWAP_CELLS( a, b, temp )  do             \
1053                                  {              \
1054                                    temp = *(a); \
1055                                    *(a) = *(b); \
1056                                    *(b) = temp; \
1057                                  } while ( 0 )
1058#define DEBUG_SORT
1059#define QUICK_SORT
1060
1061#ifdef SHELL_SORT
1062
1063  /* a simple shell sort algorithm that works directly on our */
1064  /* cells table                                              */
1065  static void
1066  gray_shell_sort ( PCell  cells,
1067                    int    count )
1068  {
1069    PCell  i, j, limit = cells + count;
1070    TCell  temp;
1071    int    gap;
1072
1073
1074    /* compute initial gap */
1075    for ( gap = 0; ++gap < count; gap *= 3 )
1076      ;
1077
1078    while ( gap /= 3 )
1079    {
1080      for ( i = cells + gap; i < limit; i++ )
1081      {
1082        for ( j = i - gap; ; j -= gap )
1083        {
1084          PCell  k = j + gap;
1085
1086
1087          if ( LESS_THAN( j, k ) )
1088            break;
1089
1090          SWAP_CELLS( j, k, temp );
1091
1092          if ( j < cells + gap )
1093            break;
1094        }
1095      }
1096    }
1097  }
1098
1099#endif /* SHELL_SORT */
1100
1101
1102#ifdef QUICK_SORT
1103
1104  /* This is a non-recursive quicksort that directly process our cells     */
1105  /* array.  It should be faster than calling the stdlib qsort(), and we   */
1106  /* can even tailor our insertion threshold...                            */
1107
1108#define QSORT_THRESHOLD  9  /* below this size, a sub-array will be sorted */
1109                            /* through a normal insertion sort             */
1110
1111  static void
1112  gray_quick_sort( PCell  cells,
1113                   int    count )
1114  {
1115    PCell   stack[40];  /* should be enough ;-) */
1116    PCell*  top;        /* top of stack */
1117    PCell   base, limit;
1118    TCell   temp;
1119
1120
1121    limit = cells + count;
1122    base  = cells;
1123    top   = stack;
1124
1125    for (;;)
1126    {
1127      int    len = (int)( limit - base );
1128      PCell  i, j, pivot;
1129
1130
1131      if ( len > QSORT_THRESHOLD )
1132      {
1133        /* we use base + len/2 as the pivot */
1134        pivot = base + len / 2;
1135        SWAP_CELLS( base, pivot, temp );
1136
1137        i = base + 1;
1138        j = limit - 1;
1139
1140        /* now ensure that *i <= *base <= *j */
1141        if ( LESS_THAN( j, i ) )
1142          SWAP_CELLS( i, j, temp );
1143
1144        if ( LESS_THAN( base, i ) )
1145          SWAP_CELLS( base, i, temp );
1146
1147        if ( LESS_THAN( j, base ) )
1148          SWAP_CELLS( base, j, temp );
1149
1150        for (;;)
1151        {
1152          do i++; while ( LESS_THAN( i, base ) );
1153          do j--; while ( LESS_THAN( base, j ) );
1154
1155          if ( i > j )
1156            break;
1157
1158          SWAP_CELLS( i, j, temp );
1159        }
1160
1161        SWAP_CELLS( base, j, temp );
1162
1163        /* now, push the largest sub-array */
1164        if ( j - base > limit - i )
1165        {
1166          top[0] = base;
1167          top[1] = j;
1168          base   = i;
1169        }
1170        else
1171        {
1172          top[0] = i;
1173          top[1] = limit;
1174          limit  = j;
1175        }
1176        top += 2;
1177      }
1178      else
1179      {
1180        /* the sub-array is small, perform insertion sort */
1181        j = base;
1182        i = j + 1;
1183
1184        for ( ; i < limit; j = i, i++ )
1185        {
1186          for ( ; LESS_THAN( j + 1, j ); j-- )
1187          {
1188            SWAP_CELLS( j + 1, j, temp );
1189            if ( j == base )
1190              break;
1191          }
1192        }
1193        if ( top > stack )
1194        {
1195          top  -= 2;
1196          base  = top[0];
1197          limit = top[1];
1198        }
1199        else
1200          break;
1201      }
1202    }
1203  }
1204
1205#endif /* QUICK_SORT */
1206
1207
1208#ifdef DEBUG_GRAYS
1209#ifdef DEBUG_SORT
1210
1211  static int
1212  gray_check_sort( PCell  cells,
1213                   int    count )
1214  {
1215    PCell  p, q;
1216
1217
1218    for ( p = cells + count - 2; p >= cells; p-- )
1219    {
1220      q = p + 1;
1221      if ( !LESS_THAN( p, q ) )
1222        return 0;
1223    }
1224    return 1;
1225  }
1226
1227#endif /* DEBUG_SORT */
1228#endif /* DEBUG_GRAYS */
1229
1230
1231  static int
1232  gray_move_to( const FT_Vector*  to,
1233                FT_Raster         raster )
1234  {
1235    TPos  x, y;
1236
1237
1238    /* record current cell, if any */
1239    gray_record_cell( (PRaster)raster );
1240
1241    /* start to a new position */
1242    x = UPSCALE( to->x );
1243    y = UPSCALE( to->y );
1244
1245    gray_start_cell( (PRaster)raster, TRUNC( x ), TRUNC( y ) );
1246
1247    ((PRaster)raster)->x = x;
1248    ((PRaster)raster)->y = y;
1249    return 0;
1250  }
1251
1252
1253  static int
1254  gray_line_to( const FT_Vector*  to,
1255                FT_Raster         raster )
1256  {
1257    gray_render_line( (PRaster)raster,
1258                      UPSCALE( to->x ), UPSCALE( to->y ) );
1259    return 0;
1260  }
1261
1262
1263  static int
1264  gray_conic_to( const FT_Vector*  control,
1265                 const FT_Vector*  to,
1266                 FT_Raster         raster )
1267  {
1268    gray_render_conic( (PRaster)raster, control, to );
1269    return 0;
1270  }
1271
1272
1273  static int
1274  gray_cubic_to( const FT_Vector*  control1,
1275                 const FT_Vector*  control2,
1276                 const FT_Vector*  to,
1277                 FT_Raster         raster )
1278  {
1279    gray_render_cubic( (PRaster)raster, control1, control2, to );
1280    return 0;
1281  }
1282
1283
1284  static void
1285  gray_render_span( int             y,
1286                    int             count,
1287                    const FT_Span*  spans,
1288                    PRaster         raster )
1289  {
1290    unsigned char*  p;
1291    FT_Bitmap*      map = &raster->target;
1292
1293
1294    /* first of all, compute the scanline offset */
1295    p = (unsigned char*)map->buffer - y * map->pitch;
1296    if ( map->pitch >= 0 )
1297      p += ( map->rows - 1 ) * map->pitch;
1298
1299    for ( ; count > 0; count--, spans++ )
1300    {
1301      unsigned char  coverage = spans->coverage;
1302
1303
1304#ifdef GRAYS_USE_GAMMA
1305      coverage = raster->gamma[coverage];
1306#endif
1307
1308      if ( coverage )
1309#if 1
1310        FT_MEM_SET( p + spans->x, (unsigned char)coverage, spans->len );
1311#else /* 1 */
1312      {
1313        q     = p + spans->x;
1314        limit = q + spans->len;
1315        for ( ; q < limit; q++ )
1316          q[0] = (unsigned char)coverage;
1317      }
1318#endif /* 1 */
1319    }
1320  }
1321
1322
1323#ifdef DEBUG_GRAYS
1324
1325#include <stdio.h>
1326
1327  static void
1328  gray_dump_cells( RAS_ARG )
1329  {
1330    PCell  cell, limit;
1331    int    y = -1;
1332
1333
1334    cell  = ras.cells;
1335    limit = cell + ras.num_cells;
1336
1337    for ( ; cell < limit; cell++ )
1338    {
1339      if ( cell->y != y )
1340      {
1341        fprintf( stderr, "\n%2d: ", cell->y );
1342        y = cell->y;
1343      }
1344      fprintf( stderr, "[%d %d %d]",
1345               cell->x, cell->area, cell->cover );
1346    }
1347    fprintf(stderr, "\n" );
1348  }
1349
1350#endif /* DEBUG_GRAYS */
1351
1352
1353  static void
1354  gray_hline( RAS_ARG_ TCoord  x,
1355                       TCoord  y,
1356                       TPos    area,
1357                       int     acount )
1358  {
1359    FT_Span*   span;
1360    int        count;
1361    int        coverage;
1362
1363
1364    /* compute the coverage line's coverage, depending on the    */
1365    /* outline fill rule                                         */
1366    /*                                                           */
1367    /* the coverage percentage is area/(PIXEL_BITS*PIXEL_BITS*2) */
1368    /*                                                           */
1369    coverage = (int)( area >> ( PIXEL_BITS * 2 + 1 - 8 ) );
1370                                                    /* use range 0..256 */
1371    if ( coverage < 0 )
1372      coverage = -coverage;
1373
1374    if ( ras.outline.flags & FT_OUTLINE_EVEN_ODD_FILL )
1375    {
1376      coverage &= 511;
1377
1378      if ( coverage > 256 )
1379        coverage = 512 - coverage;
1380      else if ( coverage == 256 )
1381        coverage = 255;
1382    }
1383    else
1384    {
1385      /* normal non-zero winding rule */
1386      if ( coverage >= 256 )
1387        coverage = 255;
1388    }
1389
1390    y += (TCoord)ras.min_ey;
1391    x += (TCoord)ras.min_ex;
1392
1393    if ( coverage )
1394    {
1395      /* see if we can add this span to the current list */
1396      count = ras.num_gray_spans;
1397      span  = ras.gray_spans + count - 1;
1398      if ( count > 0                          &&
1399           ras.span_y == y                    &&
1400           (int)span->x + span->len == (int)x &&
1401           span->coverage == coverage )
1402      {
1403        span->len = (unsigned short)( span->len + acount );
1404        return;
1405      }
1406
1407      if ( ras.span_y != y || count >= FT_MAX_GRAY_SPANS )
1408      {
1409        if ( ras.render_span && count > 0 )
1410          ras.render_span( ras.span_y, count, ras.gray_spans,
1411                           ras.render_span_data );
1412        /* ras.render_span( span->y, ras.gray_spans, count ); */
1413
1414#ifdef DEBUG_GRAYS
1415
1416        if ( ras.span_y >= 0 )
1417        {
1418          int  n;
1419
1420
1421          fprintf( stderr, "y=%3d ", ras.span_y );
1422          span = ras.gray_spans;
1423          for ( n = 0; n < count; n++, span++ )
1424            fprintf( stderr, "[%d..%d]:%02x ",
1425                     span->x, span->x + span->len - 1, span->coverage );
1426          fprintf( stderr, "\n" );
1427        }
1428
1429#endif /* DEBUG_GRAYS */
1430
1431        ras.num_gray_spans = 0;
1432        ras.span_y         = y;
1433
1434        count = 0;
1435        span  = ras.gray_spans;
1436      }
1437      else
1438        span++;
1439
1440      /* add a gray span to the current list */
1441      span->x        = (short)x;
1442      span->len      = (unsigned short)acount;
1443      span->coverage = (unsigned char)coverage;
1444      ras.num_gray_spans++;
1445    }
1446  }
1447
1448
1449  static void
1450  gray_sweep( RAS_ARG_ const FT_Bitmap*  target )
1451  {
1452    TCoord  x, y, cover;
1453    TArea   area;
1454    PCell   start, cur, limit;
1455
1456    FT_UNUSED( target );
1457
1458
1459    if ( ras.num_cells == 0 )
1460      return;
1461
1462    cur   = ras.cells;
1463    limit = cur + ras.num_cells;
1464
1465    cover              = 0;
1466    ras.span_y         = -1;
1467    ras.num_gray_spans = 0;
1468
1469    for (;;)
1470    {
1471      start  = cur;
1472      y      = start->y;
1473      x      = start->x;
1474
1475      area   = start->area;
1476      cover += start->cover;
1477
1478      /* accumulate all start cells */
1479      for (;;)
1480      {
1481        ++cur;
1482        if ( cur >= limit || cur->y != start->y || cur->x != start->x )
1483          break;
1484
1485        area  += cur->area;
1486        cover += cur->cover;
1487      }
1488
1489      /* if the start cell has a non-null area, we must draw an */
1490      /* individual gray pixel there                            */
1491      if ( area && x >= 0 )
1492      {
1493        gray_hline( RAS_VAR_ x, y, cover * ( ONE_PIXEL * 2 ) - area, 1 );
1494        x++;
1495      }
1496
1497      if ( x < 0 )
1498        x = 0;
1499
1500      if ( cur < limit && start->y == cur->y )
1501      {
1502        /* draw a gray span between the start cell and the current one */
1503        if ( cur->x > x )
1504          gray_hline( RAS_VAR_ x, y,
1505                      cover * ( ONE_PIXEL * 2 ), cur->x - x );
1506      }
1507      else
1508      {
1509        /* draw a gray span until the end of the clipping region */
1510        if ( cover && x < ras.max_ex - ras.min_ex )
1511          gray_hline( RAS_VAR_ x, y,
1512                      cover * ( ONE_PIXEL * 2 ),
1513                      (int)( ras.max_ex - x - ras.min_ex ) );
1514        cover = 0;
1515      }
1516
1517      if ( cur >= limit )
1518        break;
1519    }
1520
1521    if ( ras.render_span && ras.num_gray_spans > 0 )
1522      ras.render_span( ras.span_y, ras.num_gray_spans,
1523                       ras.gray_spans, ras.render_span_data );
1524
1525#ifdef DEBUG_GRAYS
1526
1527    {
1528      int       n;
1529      FT_Span*  span;
1530
1531
1532      fprintf( stderr, "y=%3d ", ras.span_y );
1533      span = ras.gray_spans;
1534      for ( n = 0; n < ras.num_gray_spans; n++, span++ )
1535        fprintf( stderr, "[%d..%d]:%02x ",
1536                 span->x, span->x + span->len - 1, span->coverage );
1537      fprintf( stderr, "\n" );
1538    }
1539
1540#endif /* DEBUG_GRAYS */
1541
1542  }
1543
1544
1545#ifdef _STANDALONE_
1546
1547  /*************************************************************************/
1548  /*                                                                       */
1549  /*  The following function should only compile in stand_alone mode,      */
1550  /*  i.e., when building this component without the rest of FreeType.     */
1551  /*                                                                       */
1552  /*************************************************************************/
1553
1554  /*************************************************************************/
1555  /*                                                                       */
1556  /* <Function>                                                            */
1557  /*    FT_Outline_Decompose                                               */
1558  /*                                                                       */
1559  /* <Description>                                                         */
1560  /*    Walks over an outline's structure to decompose it into individual  */
1561  /*    segments and Bezier arcs.  This function is also able to emit      */
1562  /*    `move to' and `close to' operations to indicate the start and end  */
1563  /*    of new contours in the outline.                                    */
1564  /*                                                                       */
1565  /* <Input>                                                               */
1566  /*    outline        :: A pointer to the source target.                  */
1567  /*                                                                       */
1568  /*    func_interface :: A table of `emitters', i.e,. function pointers   */
1569  /*                      called during decomposition to indicate path     */
1570  /*                      operations.                                      */
1571  /*                                                                       */
1572  /*    user           :: A typeless pointer which is passed to each       */
1573  /*                      emitter during the decomposition.  It can be     */
1574  /*                      used to store the state during the               */
1575  /*                      decomposition.                                   */
1576  /*                                                                       */
1577  /* <Return>                                                              */
1578  /*    Error code.  0 means sucess.                                       */
1579  /*                                                                       */
1580  static
1581  int  FT_Outline_Decompose( const FT_Outline*        outline,
1582                             const FT_Outline_Funcs*  func_interface,
1583                             void*                    user )
1584  {
1585#undef SCALED
1586#if 0
1587#define SCALED( x )  ( ( (x) << shift ) - delta )
1588#else
1589#define SCALED( x )  (x)
1590#endif
1591
1592    FT_Vector   v_last;
1593    FT_Vector   v_control;
1594    FT_Vector   v_start;
1595
1596    FT_Vector*  point;
1597    FT_Vector*  limit;
1598    char*       tags;
1599
1600    int   n;         /* index of contour in outline     */
1601    int   first;     /* index of first point in contour */
1602    int   error;
1603    char  tag;       /* current point's state           */
1604
1605#if 0
1606    int   shift = func_interface->shift;
1607    TPos  delta = func_interface->delta;
1608#endif
1609
1610
1611    first = 0;
1612
1613    for ( n = 0; n < outline->n_contours; n++ )
1614    {
1615      int  last;  /* index of last point in contour */
1616
1617
1618      last  = outline->contours[n];
1619      limit = outline->points + last;
1620
1621      v_start = outline->points[first];
1622      v_last  = outline->points[last];
1623
1624      v_start.x = SCALED( v_start.x ); v_start.y = SCALED( v_start.y );
1625      v_last.= SCALED( v_last.x );  v_last.= SCALED( v_last.y );
1626
1627      v_control = v_start;
1628
1629      point = outline->points + first;
1630      tags  = outline->tags  + first;
1631      tag   = FT_CURVE_TAG( tags[0] );
1632
1633      /* A contour cannot start with a cubic control point! */
1634      if ( tag == FT_CURVE_TAG_CUBIC )
1635        goto Invalid_Outline;
1636
1637      /* check first point to determine origin */
1638      if ( tag == FT_CURVE_TAG_CONIC )
1639      {
1640        /* first point is conic control.  Yes, this happens. */
1641        if ( FT_CURVE_TAG( outline->tags[last] ) == FT_CURVE_TAG_ON )
1642        {
1643          /* start at last point if it is on the curve */
1644          v_start = v_last;
1645          limit--;
1646        }
1647        else
1648        {
1649          /* if both first and last points are conic,         */
1650          /* start at their middle and record its position    */
1651          /* for closure                                      */
1652          v_start.x = ( v_start.x + v_last.x ) / 2;
1653          v_start.y = ( v_start.y + v_last.y ) / 2;
1654
1655          v_last = v_start;
1656        }
1657        point--;
1658        tags--;
1659      }
1660
1661      error = func_interface->move_to( &v_start, user );
1662      if ( error )
1663        goto Exit;
1664
1665      while ( point < limit )
1666      {
1667        point++;
1668        tags++;
1669
1670        tag = FT_CURVE_TAG( tags[0] );
1671        switch ( tag )
1672        {
1673        case FT_CURVE_TAG_ON:  /* emit a single line_to */
1674          {
1675            FT_Vector  vec;
1676
1677
1678            vec.x = SCALED( point->x );
1679            vec.y = SCALED( point->y );
1680
1681            error = func_interface->line_to( &vec, user );
1682            if ( error )
1683              goto Exit;
1684            continue;
1685          }
1686
1687        case FT_CURVE_TAG_CONIC:  /* consume conic arcs */
1688          {
1689            v_control.x = SCALED( point->x );
1690            v_control.y = SCALED( point->y );
1691
1692          Do_Conic:
1693            if ( point < limit )
1694            {
1695              FT_Vector  vec;
1696              FT_Vector  v_middle;
1697
1698
1699              point++;
1700              tags++;
1701              tag = FT_CURVE_TAG( tags[0] );
1702
1703              vec.x = SCALED( point->x );
1704              vec.y = SCALED( point->y );
1705
1706              if ( tag == FT_CURVE_TAG_ON )
1707              {
1708                error = func_interface->conic_to( &v_control, &vec, user );
1709                if ( error )
1710                  goto Exit;
1711                continue;
1712              }
1713
1714              if ( tag != FT_CURVE_TAG_CONIC )
1715                goto Invalid_Outline;
1716
1717              v_middle.x = ( v_control.x + vec.x ) / 2;
1718              v_middle.y = ( v_control.y + vec.y ) / 2;
1719
1720              error = func_interface->conic_to( &v_control, &v_middle, user );
1721              if ( error )
1722                goto Exit;
1723
1724              v_control = vec;
1725              goto Do_Conic;
1726            }
1727
1728            error = func_interface->conic_to( &v_control, &v_start, user );
1729            goto Close;
1730          }
1731
1732        default:  /* FT_CURVE_TAG_CUBIC */
1733          {
1734            FT_Vector  vec1, vec2;
1735
1736
1737            if ( point + 1 > limit                             ||
1738                 FT_CURVE_TAG( tags[1] ) != FT_CURVE_TAG_CUBIC )
1739              goto Invalid_Outline;
1740
1741            point += 2;
1742            tags  += 2;
1743
1744            vec1.x = SCALED( point[-2].x ); vec1.y = SCALED( point[-2].y );
1745            vec2.x = SCALED( point[-1].x ); vec2.y = SCALED( point[-1].y );
1746
1747            if ( point <= limit )
1748            {
1749              FT_Vector  vec;
1750
1751
1752              vec.x = SCALED( point->x );
1753              vec.y = SCALED( point->y );
1754
1755              error = func_interface->cubic_to( &vec1, &vec2, &vec, user );
1756              if ( error )
1757                goto Exit;
1758              continue;
1759            }
1760
1761            error = func_interface->cubic_to( &vec1, &vec2, &v_start, user );
1762            goto Close;
1763          }
1764        }
1765      }
1766
1767      /* close the contour with a line segment */
1768      error = func_interface->line_to( &v_start, user );
1769
1770   Close:
1771      if ( error )
1772        goto Exit;
1773
1774      first = last + 1;
1775    }
1776
1777    return 0;
1778
1779  Exit:
1780    return error;
1781
1782  Invalid_Outline:
1783    return ErrRaster_Invalid_Outline;
1784  }
1785
1786#endif /* _STANDALONE_ */
1787
1788
1789  typedef struct  TBand_
1790  {
1791    TPos  min, max;
1792
1793  } TBand;
1794
1795
1796  static int
1797  gray_convert_glyph_inner( RAS_ARG )
1798  {
1799    static
1800    const FT_Outline_Funcs  func_interface =
1801    {
1802      (FT_Outline_MoveTo_Func) gray_move_to,
1803      (FT_Outline_LineTo_Func) gray_line_to,
1804      (FT_Outline_ConicTo_Func)gray_conic_to,
1805      (FT_Outline_CubicTo_Func)gray_cubic_to,
1806      0,
1807      0
1808    };
1809
1810    volatile int  error = 0;
1811
1812    if ( ft_setjmp( ras.jump_buffer ) == 0 )
1813    {
1814      error = FT_Outline_Decompose( &ras.outline, &func_interface, &ras );
1815      gray_record_cell( RAS_VAR );
1816    }
1817    else
1818    {
1819      error = ErrRaster_MemoryOverflow;
1820    }
1821
1822    return error;
1823  }
1824
1825
1826  static int
1827  gray_convert_glyph( RAS_ARG )
1828  {
1829    TBand            bands[40];
1830    TBand* volatile  band;
1831    int volatile     n, num_bands;
1832    TPos volatile    min, max, max_y;
1833    FT_BBox*         clip;
1834
1835
1836    /* Set up state in the raster object */
1837    gray_compute_cbox( RAS_VAR );
1838
1839    /* clip to target bitmap, exit if nothing to do */
1840    clip = &ras.clip_box;
1841
1842    if ( ras.max_ex <= clip->xMin || ras.min_ex >= clip->xMax ||
1843         ras.max_ey <= clip->yMin || ras.min_ey >= clip->yMax )
1844      return 0;
1845
1846    if ( ras.min_ex < clip->xMin ) ras.min_ex = clip->xMin;
1847    if ( ras.min_ey < clip->yMin ) ras.min_ey = clip->yMin;
1848
1849    if ( ras.max_ex > clip->xMax ) ras.max_ex = clip->xMax;
1850    if ( ras.max_ey > clip->yMax ) ras.max_ey = clip->yMax;
1851
1852    /* simple heuristic used to speed-up the bezier decomposition -- see */
1853    /* the code in gray_render_conic() and gray_render_cubic() for more  */
1854    /* details                                                           */
1855    ras.conic_level = 32;
1856    ras.cubic_level = 16;
1857
1858    {
1859      int level = 0;
1860
1861
1862      if ( ras.max_ex > 24 || ras.max_ey > 24 )
1863        level++;
1864      if ( ras.max_ex > 120 || ras.max_ey > 120 )
1865        level++;
1866
1867      ras.conic_level <<= level;
1868      ras.cubic_level <<= level;
1869    }
1870
1871    /* setup vertical bands */
1872    num_bands = (int)( ( ras.max_ey - ras.min_ey ) / ras.band_size );
1873    if ( num_bands == 0 )  num_bands = 1;
1874    if ( num_bands >= 39 ) num_bands = 39;
1875
1876    ras.band_shoot = 0;
1877
1878    min   = ras.min_ey;
1879    max_y = ras.max_ey;
1880
1881    for ( n = 0; n < num_bands; n++, min = max )
1882    {
1883      max = min + ras.band_size;
1884      if ( n == num_bands - 1 || max > max_y )
1885        max = max_y;
1886
1887      bands[0].min = min;
1888      bands[0].max = max;
1889      band         = bands;
1890
1891      while ( band >= bands )
1892      {
1893        TPos  bottom, top, middle;
1894        int   error;
1895
1896
1897        ras.num_cells = 0;
1898        ras.invalid   = 1;
1899        ras.min_ey    = band->min;
1900        ras.max_ey    = band->max;
1901
1902#if 1
1903        error = gray_convert_glyph_inner( RAS_VAR );
1904#else
1905        error = FT_Outline_Decompose( outline, &func_interface, &ras ) ||
1906                gray_record_cell( RAS_VAR );
1907#endif
1908
1909        if ( !error )
1910        {
1911#ifdef SHELL_SORT
1912          gray_shell_sort( ras.cells, ras.num_cells );
1913#else
1914          gray_quick_sort( ras.cells, ras.num_cells );
1915#endif
1916
1917#ifdef DEBUG_GRAYS
1918          gray_check_sort( ras.cells, ras.num_cells );
1919          gray_dump_cells( RAS_VAR );
1920#endif
1921
1922          gray_sweep( RAS_VAR_  &ras.target );
1923          band--;
1924          continue;
1925        }
1926        else if ( error != ErrRaster_MemoryOverflow )
1927          return 1;
1928
1929        /* render pool overflow, we will reduce the render band by half */
1930        bottom = band->min;
1931        top    = band->max;
1932        middle = bottom + ( ( top - bottom ) >> 1 );
1933
1934        /* waoow! This is too complex for a single scanline, something */
1935        /* must be really rotten here!                                 */
1936        if ( middle == bottom )
1937        {
1938#ifdef DEBUG_GRAYS
1939          fprintf( stderr, "Rotten glyph!\n" );
1940#endif
1941          return 1;
1942        }
1943
1944        if ( bottom-top >= ras.band_size )
1945          ras.band_shoot++;
1946
1947        band[1].min = bottom;
1948        band[1].max = middle;
1949        band[0].min = middle;
1950        band[0].max = top;
1951        band++;
1952      }
1953    }
1954
1955    if ( ras.band_shoot > 8 && ras.band_size > 16 )
1956      ras.band_size = ras.band_size / 2;
1957
1958    return 0;
1959  }
1960
1961
1962  extern int
1963  gray_raster_render( PRaster                  raster,
1964                      const FT_Raster_Params*  params )
1965  {
1966    const FT_Outline*  outline    = (const FT_Outline*)params->source;
1967    const FT_Bitmap*   target_map = params->target;
1968
1969
1970    if ( !raster || !raster->cells || !raster->max_cells )
1971      return -1;
1972
1973    /* return immediately if the outline is empty */
1974    if ( outline->n_points == 0 || outline->n_contours <= 0 )
1975      return 0;
1976
1977    if ( !outline || !outline->contours || !outline->points )
1978      return ErrRaster_Invalid_Outline;
1979
1980    if ( outline->n_points !=
1981           outline->contours[outline->n_contours - 1] + 1 )
1982      return ErrRaster_Invalid_Outline;
1983
1984    /* if direct mode is not set, we must have a target bitmap */
1985    if ( ( params->flags & FT_RASTER_FLAG_DIRECT ) == 0 &&
1986         ( !target_map || !target_map->buffer )         )
1987      return -1;
1988
1989    /* this version does not support monochrome rendering */
1990    if ( !( params->flags & FT_RASTER_FLAG_AA ) )
1991      return ErrRaster_Invalid_Mode;
1992
1993    /* compute clipping box */
1994    if ( ( params->flags & FT_RASTER_FLAG_DIRECT ) == 0 )
1995    {
1996      /* compute clip box from target pixmap */
1997      ras.clip_box.xMin = 0;
1998      ras.clip_box.yMin = 0;
1999      ras.clip_box.xMax = target_map->width;
2000      ras.clip_box.yMax = target_map->rows;
2001    }
2002    else if ( params->flags & FT_RASTER_FLAG_CLIP )
2003    {
2004      ras.clip_box = params->clip_box;
2005    }
2006    else
2007    {
2008      ras.clip_box.xMin = -32768L;
2009      ras.clip_box.yMin = -32768L;
2010      ras.clip_box.xMax =  32767L;
2011      ras.clip_box.yMax =  32767L;
2012    }
2013
2014    ras.outline   = *outline;
2015    ras.num_cells = 0;
2016    ras.invalid   = 1;
2017
2018    if ( target_map )
2019      ras.target = *target_map;
2020
2021    ras.render_span      = (FT_Raster_Span_Func)gray_render_span;
2022    ras.render_span_data = &ras;
2023
2024    if ( params->flags & FT_RASTER_FLAG_DIRECT )
2025    {
2026      ras.render_span      = (FT_Raster_Span_Func)params->gray_spans;
2027      ras.render_span_data = params->user;
2028    }
2029
2030    return gray_convert_glyph( (PRaster)raster );
2031  }
2032
2033
2034  /**** RASTER OBJECT CREATION: In standalone mode, we simply use *****/
2035  /****                         a static object.                  *****/
2036
2037#ifdef GRAYS_USE_GAMMA
2038
2039  /* initialize the "gamma" table. Yes, this is really a crummy function */
2040  /* but the results look pretty good for something that simple.         */
2041  /*                                                                     */
2042#define M_MAX  255
2043#define M_X    128
2044#define M_Y    192
2045
2046  static void
2047  grays_init_gamma( PRaster  raster )
2048  {
2049    unsigned int  x, a;
2050
2051
2052    for ( x = 0; x < 256; x++ )
2053    {
2054      if ( x <= M_X )
2055        a = ( x * M_Y + M_X / 2) / M_X;
2056      else
2057        a = M_Y + ( ( x - M_X ) * ( M_MAX - M_Y ) +
2058            ( M_MAX - M_X ) / 2 ) / ( M_MAX - M_X );
2059
2060      raster->gamma[x] = (unsigned char)a;
2061    }
2062  }
2063
2064#endif /* GRAYS_USE_GAMMA */
2065
2066#ifdef _STANDALONE_
2067
2068  static int
2069  gray_raster_new( void*       memory,
2070                   FT_Raster*  araster )
2071  {
2072    static TRaster  the_raster;
2073
2074    FT_UNUSED( memory );
2075
2076
2077    *araster = (FT_Raster)&the_raster;
2078    FT_MEM_ZERO( &the_raster, sizeof ( the_raster ) );
2079
2080#ifdef GRAYS_USE_GAMMA
2081    grays_init_gamma( (PRaster)*araster );
2082#endif
2083
2084    return 0;
2085  }
2086
2087
2088  static void
2089  gray_raster_done( FT_Raster  raster )
2090  {
2091    /* nothing */
2092    FT_UNUSED( raster );
2093  }
2094
2095#else /* _STANDALONE_ */
2096
2097  static int
2098  gray_raster_new( FT_Memory   memory,
2099                   FT_Raster*  araster )
2100  {
2101    FT_Error  error;
2102    PRaster   raster;
2103
2104
2105    *araster = 0;
2106    if ( !FT_ALLOC( raster, sizeof ( TRaster ) ) )
2107    {
2108      raster->memory = memory;
2109      *araster = (FT_Raster)raster;
2110
2111#ifdef GRAYS_USE_GAMMA
2112      grays_init_gamma( raster );
2113#endif
2114    }
2115
2116    return error;
2117  }
2118
2119
2120  static void
2121  gray_raster_done( FT_Raster  raster )
2122  {
2123    FT_Memory  memory = (FT_Memory)((PRaster)raster)->memory;
2124
2125
2126    FT_FREE( raster );
2127  }
2128
2129#endif /* _STANDALONE_ */
2130
2131
2132  static void
2133  gray_raster_reset( FT_Raster    raster,
2134                     char*        pool_base,
2135                     long         pool_size )
2136  {
2137    PRaster  rast = (PRaster)raster;
2138
2139
2140    if ( raster && pool_base && pool_size >= 4096 )
2141      gray_init_cells( rast, (char*)pool_base, pool_size );
2142
2143    rast->band_size  = (int)( ( pool_size / sizeof ( TCell ) ) / 8 );
2144  }
2145
2146
2147  const FT_Raster_Funcs  ft_grays_raster =
2148  {
2149    FT_GLYPH_FORMAT_OUTLINE,
2150
2151    (FT_Raster_New_Func)     gray_raster_new,
2152    (FT_Raster_Reset_Func)   gray_raster_reset,
2153    (FT_Raster_Set_Mode_Func)0,
2154    (FT_Raster_Render_Func)  gray_raster_render,
2155    (FT_Raster_Done_Func)    gray_raster_done
2156  };
2157
2158
2159/* END */
Note: See TracBrowser for help on using the repository browser.