1 /***************************************************************************/
5 /* A new `perfect' anti-aliasing renderer (body). */
7 /* Copyright 2000-2001 by */
8 /* David Turner, Robert Wilhelm, and Werner Lemberg. */
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. */
16 /***************************************************************************/
18 /*************************************************************************/
20 /* This file can be compiled without the rest of the FreeType engine, */
21 /* by defining the _STANDALONE_ macro when compiling it. You also need */
22 /* to put the files `ftgrays.h' and `ftimage.h' into the current */
23 /* compilation directory. Typically, you could do something like */
25 /* - copy `src/base/ftgrays.c' to your current directory */
27 /* - copy `include/freetype/ftimage.h' and */
28 /* `include/freetype/ftgrays.h' to the same directory */
30 /* - compile `ftgrays' with the _STANDALONE_ macro defined, as in */
32 /* cc -c -D_STANDALONE_ ftgrays.c */
34 /* The renderer can be initialized with a call to */
35 /* `ft_gray_raster.gray_raster_new'; an anti-aliased bitmap can be */
36 /* generated with a call to `ft_gray_raster.gray_raster_render'. */
38 /* See the comments and documentation in the file `ftimage.h' for */
39 /* more details on how the raster works. */
41 /*************************************************************************/
43 /*************************************************************************/
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. */
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). */
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 */
59 /* doesn't use floating point values. */
61 /* This renderer has the following advantages: */
63 /* - It doesn't need an intermediate bitmap. Instead, one can supply */
64 /* a callback function that will be called by the renderer to draw */
65 /* gray spans on any target surface. You can thus do direct */
66 /* composition on any kind of bitmap, provided that you give the */
67 /* renderer the right callback. */
69 /* - A perfect anti-aliaser, i.e., it computes the _exact_ coverage on */
72 /* - It performs a single pass on the outline (the `standard' FT2 */
73 /* renderer makes two passes). */
75 /* - It can easily be modified to render to _any_ number of gray levels */
78 /* - For small (< 20) pixel sizes, it is faster than the standard */
81 /*************************************************************************/
84 #include <string.h> /* for memcpy() */
87 /*************************************************************************/
89 /* The macro FT_COMPONENT is used in trace mode. It is an implicit */
90 /* parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log */
91 /* messages during execution. */
94 #define FT_COMPONENT trace_aaraster
97 #define ErrRaster_MemoryOverflow -4
102 #define ErrRaster_Invalid_Mode -2
103 #define ErrRaster_Invalid_Outline -1
108 /* This macro is used to indicate that a function parameter is unused. */
109 /* Its purpose is simply to reduce compiler warnings. Note also that */
110 /* simply defining it as `(void)x' doesn't avoid warnings with certain */
111 /* ANSI compilers (e.g. LCC). */
112 #define FT_UNUSED( x ) (x) = (x)
114 /* Disable the tracing mechanism for simplicity -- developers can */
115 /* activate it easily by redefining these two macros. */
117 #define FT_ERROR( x ) do ; while ( 0 ) /* nothing */
121 #define FT_TRACE( x ) do ; while ( 0 ) /* nothing */
125 #else /* _STANDALONE_ */
128 #include <ft2build.h>
130 #include FT_INTERNAL_OBJECTS_H
131 #include FT_INTERNAL_DEBUG_H
132 #include FT_OUTLINE_H
134 #include "ftsmerrs.h"
136 #define ErrRaster_Invalid_Mode Smooth_Err_Cannot_Render_Glyph
137 #define ErrRaster_Invalid_Outline Smooth_Err_Invalid_Outline
140 #endif /* _STANDALONE_ */
143 /* define this to dump debugging information */
144 #define xxxDEBUG_GRAYS
146 /* as usual, for the speed hungry :-) */
148 #ifndef FT_STATIC_RASTER
151 #define RAS_ARG PRaster raster
152 #define RAS_ARG_ PRaster raster,
154 #define RAS_VAR raster
155 #define RAS_VAR_ raster,
157 #define ras (*raster)
160 #else /* FT_STATIC_RASTER */
163 #define RAS_ARG /* empty */
164 #define RAS_ARG_ /* empty */
165 #define RAS_VAR /* empty */
166 #define RAS_VAR_ /* empty */
171 #endif /* FT_STATIC_RASTER */
174 /* must be at least 6 bits! */
177 #define ONE_PIXEL ( 1L << PIXEL_BITS )
178 #define PIXEL_MASK ( -1L << PIXEL_BITS )
179 #define TRUNC( x ) ( (x) >> PIXEL_BITS )
180 #define SUBPIXELS( x ) ( (x) << PIXEL_BITS )
181 #define FLOOR( x ) ( (x) & -ONE_PIXEL )
182 #define CEILING( x ) ( ( (x) + ONE_PIXEL - 1 ) & -ONE_PIXEL )
183 #define ROUND( x ) ( ( (x) + ONE_PIXEL / 2 ) & -ONE_PIXEL )
186 #define UPSCALE( x ) ( (x) << ( PIXEL_BITS - 6 ) )
187 #define DOWNSCALE( x ) ( (x) >> ( PIXEL_BITS - 6 ) )
189 #define UPSCALE( x ) ( (x) >> ( 6 - PIXEL_BITS ) )
190 #define DOWNSCALE( x ) ( (x) << ( 6 - PIXEL_BITS ) )
193 /* Define this if you want to use a more compact storage scheme. This */
194 /* increases the number of cells available in the render pool but slows */
195 /* down the rendering a bit. It is useful if you have a really tiny */
197 #define xxxGRAYS_COMPACT
200 /*************************************************************************/
202 /* TYPE DEFINITIONS */
205 /* don't change the following types to FT_Int or FT_Pos, since we might */
206 /* need to define them to "float" or "double" when experimenting with */
209 typedef int TScan; /* integer scanline/pixel coordinate */
210 typedef long TPos; /* sub-pixel coordinate */
212 /* determine the type used to store cell areas. This normally takes at */
213 /* least PIXEL_BYTES*2 + 1. On 16-bit systems, we need to use `long' */
214 /* instead of `int', otherwise bad things happen */
220 #else /* PIXEL_BITS >= 8 */
222 /* approximately determine the size of integers using an ANSI-C header */
225 #if UINT_MAX == 0xFFFFU
231 #endif /* PIXEL_BITS >= 8 */
234 /* maximal number of gray spans in a call to the span callback */
235 #define FT_MAX_GRAY_SPANS 32
240 typedef struct TCell_
244 int cover : PIXEL_BITS + 2;
245 int area : PIXEL_BITS * 2 + 2;
249 #else /* GRAYS_COMPACT */
251 typedef struct TCell_
260 #endif /* GRAYS_COMPACT */
263 typedef struct TRaster_
269 TScan min_ex, max_ex;
270 TScan min_ey, max_ey;
282 FT_Vector bez_stack[32 * 3 + 1];
289 FT_Span gray_spans[FT_MAX_GRAY_SPANS];
292 FT_Raster_Span_Func render_span;
293 void* render_span_data;
307 /*************************************************************************/
309 /* Initialize the cells table. */
312 gray_init_cells( RAS_ARG_ void* buffer,
315 ras.cells = (PCell)buffer;
316 ras.max_cells = byte_size / sizeof ( TCell );
324 /*************************************************************************/
326 /* Compute the outline bounding box. */
329 gray_compute_cbox( RAS_ARG )
331 FT_Outline* outline = &ras.outline;
332 FT_Vector* vec = outline->points;
333 FT_Vector* limit = vec + outline->n_points;
336 if ( outline->n_points <= 0 )
338 ras.min_ex = ras.max_ex = 0;
339 ras.min_ey = ras.max_ey = 0;
343 ras.min_ex = ras.max_ex = vec->x;
344 ras.min_ey = ras.max_ey = vec->y;
348 for ( ; vec < limit; vec++ )
354 if ( x < ras.min_ex ) ras.min_ex = x;
355 if ( x > ras.max_ex ) ras.max_ex = x;
356 if ( y < ras.min_ey ) ras.min_ey = y;
357 if ( y > ras.max_ey ) ras.max_ey = y;
360 /* truncate the bounding box to integer pixels */
361 ras.min_ex = ras.min_ex >> 6;
362 ras.min_ey = ras.min_ey >> 6;
363 ras.max_ex = ( ras.max_ex + 63 ) >> 6;
364 ras.max_ey = ( ras.max_ey + 63 ) >> 6;
368 /*************************************************************************/
370 /* Record the current cell in the table. */
373 gray_record_cell( RAS_ARG )
378 if ( !ras.invalid && ( ras.area | ras.cover ) )
380 if ( ras.num_cells >= ras.max_cells )
381 longjmp( ras.jump_buffer, 1 );
383 cell = ras.cells + ras.num_cells++;
384 cell->x = ras.ex - ras.min_ex;
385 cell->y = ras.ey - ras.min_ey;
386 cell->area = ras.area;
387 cell->cover = ras.cover;
392 /*************************************************************************/
394 /* Set the current cell to a new position. */
397 gray_set_cell( RAS_ARG_ TScan ex,
400 int invalid, record, clean;
403 /* Move the cell pointer to a new position. We set the `invalid' */
404 /* flag to indicate that the cell isn't part of those we're interested */
405 /* in during the render phase. This means that: */
407 /* . the new vertical position must be within min_ey..max_ey-1. */
408 /* . the new horizontal position must be strictly less than max_ex */
410 /* Note that if a cell is to the left of the clipping region, it is */
411 /* actually set to the (min_ex-1) horizontal position. */
416 invalid = ( ey < ras.min_ey || ey >= ras.max_ey || ex >= ras.max_ex );
419 /* All cells that are on the left of the clipping region go to the */
420 /* min_ex - 1 horizontal position. */
421 if ( ex < ras.min_ex )
424 /* if our position is new, then record the previous cell */
425 if ( ex != ras.ex || ey != ras.ey )
428 clean = ras.invalid; /* do not clean if we didn't move from */
432 /* record the previous cell if needed (i.e., if we changed the cell */
433 /* position, of changed the `invalid' flag) */
434 if ( ras.invalid != invalid || record )
435 gray_record_cell( RAS_VAR );
443 ras.invalid = invalid;
449 /*************************************************************************/
451 /* Start a new contour at a given cell. */
454 gray_start_cell( RAS_ARG_ TScan ex,
457 if ( ex < ras.min_ex )
464 ras.last_ey = SUBPIXELS( ey );
467 gray_set_cell( RAS_VAR_ ex, ey );
471 /*************************************************************************/
473 /* Render a scanline as one or more cells. */
476 gray_render_scanline( RAS_ARG_ TScan ey,
482 TScan ex1, ex2, fx1, fx2, delta;
484 int incr, lift, mod, rem;
489 ex1 = TRUNC( x1 ); /* if (ex1 >= ras.max_ex) ex1 = ras.max_ex-1; */
490 ex2 = TRUNC( x2 ); /* if (ex2 >= ras.max_ex) ex2 = ras.max_ex-1; */
491 fx1 = x1 - SUBPIXELS( ex1 );
492 fx2 = x2 - SUBPIXELS( ex2 );
494 /* trivial case. Happens often */
497 gray_set_cell( RAS_VAR_ ex2, ey );
501 /* everything is located in a single cell. That is easy! */
506 ras.area += (TArea)( fx1 + fx2 ) * delta;
511 /* ok, we'll have to render a run of adjacent cells on the same */
514 p = ( ONE_PIXEL - fx1 ) * ( y2 - y1 );
520 p = fx1 * ( y2 - y1 );
534 ras.area += (TArea)( fx1 + first ) * delta;
538 gray_set_cell( RAS_VAR_ ex1, ey );
543 p = ONE_PIXEL * ( y2 - y1 );
564 ras.area += (TArea)ONE_PIXEL * delta;
568 gray_set_cell( RAS_VAR_ ex1, ey );
573 ras.area += (TArea)( fx2 + ONE_PIXEL - first ) * delta;
578 /*************************************************************************/
580 /* Render a given line as a series of scanlines. */
583 gray_render_line( RAS_ARG_ TPos to_x,
586 TScan ey1, ey2, fy1, fy2;
588 int p, rem, mod, lift, delta, first, incr;
591 ey1 = TRUNC( ras.last_ey );
592 ey2 = TRUNC( to_y ); /* if (ey2 >= ras.max_ey) ey2 = ras.max_ey-1; */
593 fy1 = ras.y - ras.last_ey;
594 fy2 = to_y - SUBPIXELS( ey2 );
599 /* XXX: we should do something about the trivial case where dx == 0, */
600 /* as it happens very often! */
602 /* perform vertical clipping */
614 if ( min >= ras.max_ey || max < ras.min_ey )
618 /* everything is on a single scanline */
621 gray_render_scanline( RAS_VAR_ ey1, ras.x, fy1, to_x, fy2 );
625 /* ok, we have to render several scanlines */
626 p = ( ONE_PIXEL - fy1 ) * dx;
647 gray_render_scanline( RAS_VAR_ ey1, ras.x, fy1, x, first );
650 gray_set_cell( RAS_VAR_ TRUNC( x ), ey1 );
675 gray_render_scanline( RAS_VAR_ ey1, x, ONE_PIXEL - first, x2, first );
679 gray_set_cell( RAS_VAR_ TRUNC( x ), ey1 );
683 gray_render_scanline( RAS_VAR_ ey1, x, ONE_PIXEL - first, to_x, fy2 );
688 ras.last_ey = SUBPIXELS( ey2 );
693 gray_split_conic( FT_Vector* base )
698 base[4].x = base[2].x;
700 a = base[3].x = ( base[2].x + b ) / 2;
701 b = base[1].x = ( base[0].x + b ) / 2;
702 base[2].x = ( a + b ) / 2;
704 base[4].y = base[2].y;
706 a = base[3].y = ( base[2].y + b ) / 2;
707 b = base[1].y = ( base[0].y + b ) / 2;
708 base[2].y = ( a + b ) / 2;
713 gray_render_conic( RAS_ARG_ FT_Vector* control,
722 dx = DOWNSCALE( ras.x ) + to->x - ( control->x << 1 );
725 dy = DOWNSCALE( ras.y ) + to->y - ( control->y << 1 );
732 dx = dx / ras.conic_level;
739 /* a shortcut to speed things up */
742 /* we compute the mid-point directly in order to avoid */
743 /* calling gray_split_conic() */
744 TPos to_x, to_y, mid_x, mid_y;
747 to_x = UPSCALE( to->x );
748 to_y = UPSCALE( to->y );
749 mid_x = ( ras.x + to_x + 2 * UPSCALE( control->x ) ) / 4;
750 mid_y = ( ras.y + to_y + 2 * UPSCALE( control->y ) ) / 4;
752 gray_render_line( RAS_VAR_ mid_x, mid_y );
753 gray_render_line( RAS_VAR_ to_x, to_y );
758 levels = ras.lev_stack;
762 arc[0].x = UPSCALE( to->x );
763 arc[0].y = UPSCALE( to->y );
764 arc[1].x = UPSCALE( control->x );
765 arc[1].y = UPSCALE( control->y );
774 /* check that the arc crosses the current band */
778 min = max = arc[0].y;
781 if ( y < min ) min = y;
782 if ( y > max ) max = y;
785 if ( y < min ) min = y;
786 if ( y > max ) max = y;
788 if ( TRUNC( min ) >= ras.max_ey || TRUNC( max ) < 0 )
791 gray_split_conic( arc );
794 levels[top] = levels[top - 1] = level - 1;
800 TPos to_x, to_y, mid_x, mid_y;
805 mid_x = ( ras.x + to_x + 2 * arc[1].x ) / 4;
806 mid_y = ( ras.y + to_y + 2 * arc[1].y ) / 4;
808 gray_render_line( RAS_VAR_ mid_x, mid_y );
809 gray_render_line( RAS_VAR_ to_x, to_y );
820 gray_split_cubic( FT_Vector* base )
825 base[6].x = base[3].x;
828 base[1].x = a = ( base[0].x + c ) / 2;
829 base[5].x = b = ( base[3].x + d ) / 2;
831 base[2].x = a = ( a + c ) / 2;
832 base[4].x = b = ( b + c ) / 2;
833 base[3].x = ( a + b ) / 2;
835 base[6].y = base[3].y;
838 base[1].y = a = ( base[0].y + c ) / 2;
839 base[5].y = b = ( base[3].y + d ) / 2;
841 base[2].y = a = ( a + c ) / 2;
842 base[4].y = b = ( b + c ) / 2;
843 base[3].y = ( a + b ) / 2;
848 gray_render_cubic( RAS_ARG_ FT_Vector* control1,
858 dx = DOWNSCALE( ras.x ) + to->x - ( control1->x << 1 );
861 dy = DOWNSCALE( ras.y ) + to->y - ( control1->y << 1 );
868 dx = DOWNSCALE( ras.x ) + to->x - 3 * ( control1->x + control2->x );
871 dy = DOWNSCALE( ras.y ) + to->y - 3 * ( control1->x + control2->y );
879 da = da / ras.cubic_level;
880 db = db / ras.conic_level;
881 while ( da > 0 || db > 0 )
890 TPos to_x, to_y, mid_x, mid_y;
893 to_x = UPSCALE( to->x );
894 to_y = UPSCALE( to->y );
895 mid_x = ( ras.x + to_x +
896 3 * UPSCALE( control1->x + control2->x ) ) / 8;
897 mid_y = ( ras.y + to_y +
898 3 * UPSCALE( control1->y + control2->y ) ) / 8;
900 gray_render_line( RAS_VAR_ mid_x, mid_y );
901 gray_render_line( RAS_VAR_ to_x, to_y );
906 arc[0].x = UPSCALE( to->x );
907 arc[0].y = UPSCALE( to->y );
908 arc[1].x = UPSCALE( control2->x );
909 arc[1].y = UPSCALE( control2->y );
910 arc[2].x = UPSCALE( control1->x );
911 arc[2].y = UPSCALE( control1->y );
915 levels = ras.lev_stack;
924 /* check that the arc crosses the current band */
928 min = max = arc[0].y;
930 if ( y < min ) min = y;
931 if ( y > max ) max = y;
933 if ( y < min ) min = y;
934 if ( y > max ) max = y;
936 if ( y < min ) min = y;
937 if ( y > max ) max = y;
938 if ( TRUNC( min ) >= ras.max_ey || TRUNC( max ) < 0 )
940 gray_split_cubic( arc );
943 levels[top] = levels[top - 1] = level - 1;
949 TPos to_x, to_y, mid_x, mid_y;
954 mid_x = ( ras.x + to_x + 3 * ( arc[1].x + arc[2].x ) ) / 8;
955 mid_y = ( ras.y + to_y + 3 * ( arc[1].y + arc[2].y ) ) / 8;
957 gray_render_line( RAS_VAR_ mid_x, mid_y );
958 gray_render_line( RAS_VAR_ to_x, to_y );
967 /* a macro comparing two cell pointers. Returns true if a <= b. */
970 #define PACK( a ) ( ( (long)(a)->y << 16 ) + (a)->x )
971 #define LESS_THAN( a, b ) ( PACK( a ) < PACK( b ) )
975 #define LESS_THAN( a, b ) ( (a)->y < (b)->y || \
976 ( (a)->y == (b)->y && (a)->x < (b)->x ) )
980 #define SWAP_CELLS( a, b, temp ) do \
991 /* a simple shell sort algorithm that works directly on our */
994 gray_shell_sort ( PCell cells,
997 PCell i, j, limit = cells + count;
1002 /* compute initial gap */
1003 for ( gap = 0; ++gap < count; gap *= 3 )
1008 for ( i = cells + gap; i < limit; i++ )
1010 for ( j = i - gap; ; j -= gap )
1015 if ( LESS_THAN( j, k ) )
1018 SWAP_CELLS( j, k, temp );
1020 if ( j < cells + gap )
1027 #endif /* SHELL_SORT */
1032 /* This is a non-recursive quicksort that directly process our cells */
1033 /* array. It should be faster than calling the stdlib qsort(), and we */
1034 /* can even tailor our insertion threshold... */
1036 #define QSORT_THRESHOLD 9 /* below this size, a sub-array will be sorted */
1037 /* through a normal insertion sort */
1040 gray_quick_sort( PCell cells,
1043 PCell stack[40]; /* should be enough ;-) */
1044 PCell* top; /* top of stack */
1049 limit = cells + count;
1055 int len = (int)( limit - base );
1059 if ( len > QSORT_THRESHOLD )
1061 /* we use base + len/2 as the pivot */
1062 pivot = base + len / 2;
1063 SWAP_CELLS( base, pivot, temp );
1068 /* now ensure that *i <= *base <= *j */
1069 if ( LESS_THAN( j, i ) )
1070 SWAP_CELLS( i, j, temp );
1072 if ( LESS_THAN( base, i ) )
1073 SWAP_CELLS( base, i, temp );
1075 if ( LESS_THAN( j, base ) )
1076 SWAP_CELLS( base, j, temp );
1080 do i++; while ( LESS_THAN( i, base ) );
1081 do j--; while ( LESS_THAN( base, j ) );
1086 SWAP_CELLS( i, j, temp );
1089 SWAP_CELLS( base, j, temp );
1091 /* now, push the largest sub-array */
1092 if ( j - base > limit - i )
1108 /* the sub-array is small, perform insertion sort */
1112 for ( ; i < limit; j = i, i++ )
1114 for ( ; LESS_THAN( j + 1, j ); j-- )
1116 SWAP_CELLS( j + 1, j, temp );
1133 #endif /* QUICK_SORT */
1140 gray_check_sort( PCell cells,
1146 for ( p = cells + count - 2; p >= cells; p-- )
1149 if ( !LESS_THAN( p, q ) )
1155 #endif /* DEBUG_SORT */
1156 #endif /* DEBUG_GRAYS */
1160 gray_move_to( FT_Vector* to,
1166 /* record current cell, if any */
1167 gray_record_cell( (PRaster)raster );
1169 /* start to a new position */
1170 x = UPSCALE( to->x );
1171 y = UPSCALE( to->y );
1173 gray_start_cell( (PRaster)raster, TRUNC( x ), TRUNC( y ) );
1175 ((PRaster)raster)->x = x;
1176 ((PRaster)raster)->y = y;
1182 gray_line_to( FT_Vector* to,
1185 gray_render_line( (PRaster)raster,
1186 UPSCALE( to->x ), UPSCALE( to->y ) );
1192 gray_conic_to( FT_Vector* control,
1196 gray_render_conic( (PRaster)raster, control, to );
1202 gray_cubic_to( FT_Vector* control1,
1203 FT_Vector* control2,
1207 gray_render_cubic( (PRaster)raster, control1, control2, to );
1213 gray_render_span( int y,
1219 FT_Bitmap* map = &raster->target;
1222 /* first of all, compute the scanline offset */
1223 p = (unsigned char*)map->buffer - y * map->pitch;
1224 if ( map->pitch >= 0 )
1225 p += ( map->rows - 1 ) * map->pitch;
1227 for ( ; count > 0; count--, spans++ )
1229 if ( spans->coverage )
1231 memset( p + spans->x, (unsigned char)spans->coverage, spans->len );
1235 limit = q + spans->len;
1236 for ( ; q < limit; q++ )
1237 q[0] = (unsigned char)spans->coverage;
1249 gray_dump_cells( RAS_ARG )
1256 limit = cell + ras.num_cells;
1258 for ( ; cell < limit; cell++ )
1262 fprintf( stderr, "\n%2d: ", cell->y );
1265 fprintf( stderr, "[%d %d %d]",
1266 cell->x, cell->area, cell->cover );
1268 fprintf(stderr, "\n" );
1271 #endif /* DEBUG_GRAYS */
1275 gray_hline( RAS_ARG_ TScan x,
1285 /* compute the coverage line's coverage, depending on the */
1286 /* outline fill rule */
1288 /* the coverage percentage is area/(PIXEL_BITS*PIXEL_BITS*2) */
1290 coverage = area >> ( PIXEL_BITS * 2 + 1 - 8); /* use range 0..256 */
1292 if ( ras.outline.flags & ft_outline_even_odd_fill )
1295 coverage = -coverage;
1297 while ( coverage >= 512 )
1300 if ( coverage > 256 )
1301 coverage = 512 - coverage;
1302 else if ( coverage == 256 )
1307 /* normal non-zero winding rule */
1309 coverage = -coverage;
1311 if ( coverage >= 256 )
1320 /* see if we can add this span to the current list */
1321 count = ras.num_gray_spans;
1322 span = ras.gray_spans + count - 1;
1325 (int)span->x + span->len == (int)x &&
1326 span->coverage == coverage )
1328 span->len = (unsigned short)( span->len + acount );
1332 if ( ras.span_y != y || count >= FT_MAX_GRAY_SPANS )
1334 if ( ras.render_span && count > 0 )
1335 ras.render_span( ras.span_y, count, ras.gray_spans,
1336 ras.render_span_data );
1337 /* ras.render_span( span->y, ras.gray_spans, count ); */
1341 if ( ras.span_y >= 0 )
1346 fprintf( stderr, "y=%3d ", ras.span_y );
1347 span = ras.gray_spans;
1348 for ( n = 0; n < count; n++, span++ )
1349 fprintf( stderr, "[%d..%d]:%02x ",
1350 span->x, span->x + span->len - 1, span->coverage );
1351 fprintf( stderr, "\n" );
1354 #endif /* DEBUG_GRAYS */
1356 ras.num_gray_spans = 0;
1360 span = ras.gray_spans;
1365 /* add a gray span to the current list */
1367 span->len = (unsigned short)acount;
1368 span->coverage = (unsigned char)coverage;
1369 ras.num_gray_spans++;
1375 gray_sweep( RAS_ARG_ FT_Bitmap* target )
1379 PCell start, cur, limit;
1381 FT_UNUSED( target );
1383 if ( ras.num_cells == 0 )
1387 limit = cur + ras.num_cells;
1391 ras.num_gray_spans = 0;
1400 cover += start->cover;
1402 /* accumulate all start cells */
1406 if ( cur >= limit || cur->y != start->y || cur->x != start->x )
1410 cover += cur->cover;
1413 /* if the start cell has a non-null area, we must draw an */
1414 /* individual gray pixel there */
1415 if ( area && x >= 0 )
1417 gray_hline( RAS_VAR_ x, y, cover * ( ONE_PIXEL * 2 ) - area, 1 );
1424 if ( cur < limit && start->y == cur->y )
1426 /* draw a gray span between the start cell and the current one */
1428 gray_hline( RAS_VAR_ x, y,
1429 cover * ( ONE_PIXEL * 2 ), cur->x - x );
1433 /* draw a gray span until the end of the clipping region */
1434 if ( cover && x < ras.max_ex - ras.min_ex )
1435 gray_hline( RAS_VAR_ x, y,
1436 cover * ( ONE_PIXEL * 2 ),
1437 ras.max_ex - x - ras.min_ex );
1445 if ( ras.render_span && ras.num_gray_spans > 0 )
1446 ras.render_span( ras.span_y, ras.num_gray_spans,
1447 ras.gray_spans, ras.render_span_data );
1456 fprintf( stderr, "y=%3d ", ras.span_y );
1457 span = ras.gray_spans;
1458 for ( n = 0; n < ras.num_gray_spans; n++, span++ )
1459 fprintf( stderr, "[%d..%d]:%02x ",
1460 span->x, span->x + span->len - 1, span->coverage );
1461 fprintf( stderr, "\n" );
1464 #endif /* DEBUG_GRAYS */
1471 /*************************************************************************/
1473 /* The following function should only compile in stand_alone mode, */
1474 /* i.e., when building this component without the rest of FreeType. */
1476 /*************************************************************************/
1478 /*************************************************************************/
1481 /* FT_Outline_Decompose */
1484 /* Walks over an outline's structure to decompose it into individual */
1485 /* segments and Bezier arcs. This function is also able to emit */
1486 /* `move to' and `close to' operations to indicate the start and end */
1487 /* of new contours in the outline. */
1490 /* outline :: A pointer to the source target. */
1492 /* interface :: A table of `emitters', i.e,. function pointers called */
1493 /* during decomposition to indicate path operations. */
1495 /* user :: A typeless pointer which is passed to each emitter */
1496 /* during the decomposition. It can be used to store */
1497 /* the state during the decomposition. */
1500 /* Error code. 0 means sucess. */
1503 int FT_Outline_Decompose( FT_Outline* outline,
1504 const FT_Outline_Funcs* interface,
1509 #define SCALED( x ) ( ( (x) << shift ) - delta )
1511 #define SCALED( x ) (x)
1515 FT_Vector v_control;
1522 int n; /* index of contour in outline */
1523 int first; /* index of first point in contour */
1525 char tag; /* current point's state */
1528 int shift = interface->shift;
1529 FT_Pos delta = interface->delta;
1535 for ( n = 0; n < outline->n_contours; n++ )
1537 int last; /* index of last point in contour */
1540 last = outline->contours[n];
1541 limit = outline->points + last;
1543 v_start = outline->points[first];
1544 v_last = outline->points[last];
1546 v_start.x = SCALED( v_start.x ); v_start.y = SCALED( v_start.y );
1547 v_last.x = SCALED( v_last.x ); v_last.y = SCALED( v_last.y );
1549 v_control = v_start;
1551 point = outline->points + first;
1552 tags = outline->tags + first;
1553 tag = FT_CURVE_TAG( tags[0] );
1555 /* A contour cannot start with a cubic control point! */
1556 if ( tag == FT_Curve_Tag_Cubic )
1557 goto Invalid_Outline;
1559 /* check first point to determine origin */
1560 if ( tag == FT_Curve_Tag_Conic )
1562 /* first point is conic control. Yes, this happens. */
1563 if ( FT_CURVE_TAG( outline->tags[last] ) == FT_Curve_Tag_On )
1565 /* start at last point if it is on the curve */
1571 /* if both first and last points are conic, */
1572 /* start at their middle and record its position */
1574 v_start.x = ( v_start.x + v_last.x ) / 2;
1575 v_start.y = ( v_start.y + v_last.y ) / 2;
1583 error = interface->move_to( &v_start, user );
1587 while ( point < limit )
1592 tag = FT_CURVE_TAG( tags[0] );
1595 case FT_Curve_Tag_On: /* emit a single line_to */
1600 vec.x = SCALED( point->x );
1601 vec.y = SCALED( point->y );
1603 error = interface->line_to( &vec, user );
1609 case FT_Curve_Tag_Conic: /* consume conic arcs */
1611 v_control.x = SCALED( point->x );
1612 v_control.y = SCALED( point->y );
1615 if ( point < limit )
1623 tag = FT_CURVE_TAG( tags[0] );
1625 vec.x = SCALED( point->x );
1626 vec.y = SCALED( point->y );
1628 if ( tag == FT_Curve_Tag_On )
1630 error = interface->conic_to( &v_control, &vec, user );
1636 if ( tag != FT_Curve_Tag_Conic )
1637 goto Invalid_Outline;
1639 v_middle.x = ( v_control.x + vec.x ) / 2;
1640 v_middle.y = ( v_control.y + vec.y ) / 2;
1642 error = interface->conic_to( &v_control, &v_middle, user );
1650 error = interface->conic_to( &v_control, &v_start, user );
1654 default: /* FT_Curve_Tag_Cubic */
1656 FT_Vector vec1, vec2;
1659 if ( point + 1 > limit ||
1660 FT_CURVE_TAG( tags[1] ) != FT_Curve_Tag_Cubic )
1661 goto Invalid_Outline;
1666 vec1.x = SCALED( point[-2].x ); vec1.y = SCALED( point[-2].y );
1667 vec2.x = SCALED( point[-1].x ); vec2.y = SCALED( point[-1].y );
1669 if ( point <= limit )
1674 vec.x = SCALED( point->x );
1675 vec.y = SCALED( point->y );
1677 error = interface->cubic_to( &vec1, &vec2, &vec, user );
1683 error = interface->cubic_to( &vec1, &vec2, &v_start, user );
1689 /* close the contour with a line segment */
1690 error = interface->line_to( &v_start, user );
1705 return ErrRaster_Invalid_Outline;
1708 #endif /* _STANDALONE_ */
1711 typedef struct TBand_
1719 gray_convert_glyph_inner( RAS_ARG )
1722 const FT_Outline_Funcs interface =
1724 (FT_Outline_MoveTo_Func) gray_move_to,
1725 (FT_Outline_LineTo_Func) gray_line_to,
1726 (FT_Outline_ConicTo_Func)gray_conic_to,
1727 (FT_Outline_CubicTo_Func)gray_cubic_to,
1732 volatile int error = 0;
1734 if ( setjmp( ras.jump_buffer ) == 0 )
1736 error = FT_Outline_Decompose( &ras.outline, &interface, &ras );
1737 gray_record_cell( RAS_VAR );
1741 error = ErrRaster_MemoryOverflow;
1749 gray_convert_glyph( RAS_ARG )
1751 TBand bands[40], *band;
1753 TPos min, max, max_y;
1757 /* Set up state in the raster object */
1758 gray_compute_cbox( RAS_VAR );
1760 /* clip to target bitmap, exit if nothing to do */
1761 clip = &ras.clip_box;
1763 if ( ras.max_ex <= clip->xMin || ras.min_ex >= clip->xMax ||
1764 ras.max_ey <= clip->yMin || ras.min_ey >= clip->yMax )
1767 if ( ras.min_ex < clip->xMin ) ras.min_ex = clip->xMin;
1768 if ( ras.min_ey < clip->yMin ) ras.min_ey = clip->yMin;
1770 if ( ras.max_ex > clip->xMax ) ras.max_ex = clip->xMax;
1771 if ( ras.max_ey > clip->yMax ) ras.max_ey = clip->yMax;
1773 /* simple heuristic used to speed-up the bezier decomposition -- see */
1774 /* the code in gray_render_conic() and gray_render_cubic() for more */
1776 ras.conic_level = 32;
1777 ras.cubic_level = 16;
1783 if ( ras.max_ex > 24 || ras.max_ey > 24 )
1785 if ( ras.max_ex > 120 || ras.max_ey > 120 )
1788 ras.conic_level <<= level;
1789 ras.cubic_level <<= level;
1792 /* setup vertical bands */
1793 num_bands = ( ras.max_ey - ras.min_ey ) / ras.band_size;
1794 if ( num_bands == 0 ) num_bands = 1;
1795 if ( num_bands >= 39 ) num_bands = 39;
1802 for ( n = 0; n < num_bands; n++, min = max )
1804 max = min + ras.band_size;
1805 if ( n == num_bands - 1 || max > max_y )
1812 while ( band >= bands )
1814 FT_Pos bottom, top, middle;
1820 ras.min_ey = band->min;
1821 ras.max_ey = band->max;
1824 error = gray_convert_glyph_inner( RAS_VAR );
1826 error = FT_Outline_Decompose( outline, &interface, &ras ) ||
1827 gray_record_cell( RAS_VAR );
1833 gray_shell_sort( ras.cells, ras.num_cells );
1835 gray_quick_sort( ras.cells, ras.num_cells );
1839 gray_check_sort( ras.cells, ras.num_cells );
1840 gray_dump_cells( RAS_VAR );
1843 gray_sweep( RAS_VAR_ &ras.target );
1847 else if ( error != ErrRaster_MemoryOverflow )
1850 /* render pool overflow, we will reduce the render band by half */
1853 middle = bottom + ( ( top - bottom ) >> 1 );
1855 /* waoow! This is too complex for a single scanline, something */
1856 /* must be really rotten here! */
1857 if ( middle == bottom )
1860 fprintf( stderr, "Rotten glyph!\n" );
1865 if ( bottom-top >= ras.band_size )
1868 band[1].min = bottom;
1869 band[1].max = middle;
1870 band[0].min = middle;
1876 if ( ras.band_shoot > 8 && ras.band_size > 16 )
1877 ras.band_size = ras.band_size / 2;
1884 gray_raster_render( PRaster raster,
1885 FT_Raster_Params* params )
1887 FT_Outline* outline = (FT_Outline*)params->source;
1888 FT_Bitmap* target_map = params->target;
1891 if ( !raster || !raster->cells || !raster->max_cells )
1894 /* return immediately if the outline is empty */
1895 if ( outline->n_points == 0 || outline->n_contours <= 0 )
1898 if ( !outline || !outline->contours || !outline->points )
1899 return ErrRaster_Invalid_Outline;
1901 if ( outline->n_points !=
1902 outline->contours[outline->n_contours - 1] + 1 )
1903 return ErrRaster_Invalid_Outline;
1905 /* if direct mode is not set, we must have a target bitmap */
1906 if ( ( params->flags & ft_raster_flag_direct ) == 0 &&
1907 ( !target_map || !target_map->buffer ) )
1910 /* this version does not support monochrome rendering */
1911 if ( !( params->flags & ft_raster_flag_aa ) )
1912 return ErrRaster_Invalid_Mode;
1914 /* compute clipping box */
1915 if ( ( params->flags & ft_raster_flag_direct ) == 0 )
1917 /* compute clip box from target pixmap */
1918 ras.clip_box.xMin = 0;
1919 ras.clip_box.yMin = 0;
1920 ras.clip_box.xMax = target_map->width;
1921 ras.clip_box.yMax = target_map->rows;
1923 else if ( params->flags & ft_raster_flag_clip )
1925 ras.clip_box = params->clip_box;
1929 ras.clip_box.xMin = -32768L;
1930 ras.clip_box.yMin = -32768L;
1931 ras.clip_box.xMax = 32767L;
1932 ras.clip_box.yMax = 32767L;
1935 ras.outline = *outline;
1940 ras.target = *target_map;
1942 ras.render_span = (FT_Raster_Span_Func)gray_render_span;
1943 ras.render_span_data = &ras;
1945 if ( params->flags & ft_raster_flag_direct )
1947 ras.render_span = (FT_Raster_Span_Func)params->gray_spans;
1948 ras.render_span_data = params->user;
1951 return gray_convert_glyph( (PRaster)raster );
1955 /**** RASTER OBJECT CREATION: In standalone mode, we simply use *****/
1956 /**** a static object. *****/
1961 gray_raster_new( void* memory,
1962 FT_Raster* araster )
1964 static TRaster the_raster;
1966 FT_UNUSED( memory );
1969 *araster = (FT_Raster)&the_raster;
1970 memset( &the_raster, 0, sizeof ( the_raster ) );
1977 gray_raster_done( FT_Raster raster )
1980 FT_UNUSED( raster );
1983 #else /* _STANDALONE_ */
1986 gray_raster_new( FT_Memory memory,
1987 FT_Raster* araster )
1994 if ( !ALLOC( raster, sizeof ( TRaster ) ) )
1996 raster->memory = memory;
1997 *araster = (FT_Raster)raster;
2005 gray_raster_done( FT_Raster raster )
2007 FT_Memory memory = (FT_Memory)((PRaster)raster)->memory;
2013 #endif /* _STANDALONE_ */
2017 gray_raster_reset( FT_Raster raster,
2018 const char* pool_base,
2021 PRaster rast = (PRaster)raster;
2024 if ( raster && pool_base && pool_size >= 4096 )
2025 gray_init_cells( rast, (char*)pool_base, pool_size );
2027 rast->band_size = ( pool_size / sizeof ( TCell ) ) / 8;
2031 const FT_Raster_Funcs ft_grays_raster =
2033 ft_glyph_format_outline,
2035 (FT_Raster_New_Func) gray_raster_new,
2036 (FT_Raster_Reset_Func) gray_raster_reset,
2037 (FT_Raster_Set_Mode_Func) 0,
2038 (FT_Raster_Render_Func) gray_raster_render,
2039 (FT_Raster_Done_Func) gray_raster_done