1
/***************************************************************************/
5
/* A new `perfect' anti-aliasing renderer (body). */
7
/* Copyright 2000-2001, 2002, 2003 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, 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 */
25
/* - copy `src/smooth/ftgrays.c' (this file) to your current directory */
27
/* - copy `include/freetype/ftimage.h' and `src/smooth/ftgrays.h' to the */
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.raster_new'; an anti-aliased bitmap can be generated */
36
/* with a call to `ft_gray_raster.raster_render'. */
38
/* See the comments and documentation in the file `ftimage.h' for more */
39
/* 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 doesn't */
59
/* use floating point values. */
61
/* This renderer has the following advantages: */
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 */
69
/* - A perfect anti-aliaser, i.e., it computes the _exact_ coverage on */
70
/* each pixel cell. */
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
/*************************************************************************/
85
/* experimental support for gamma correction within the rasterizer */
86
#define xxxGRAYS_USE_GAMMA
89
/*************************************************************************/
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. */
96
#define FT_COMPONENT trace_smooth
99
#define ErrRaster_MemoryOverflow -4
104
#include <string.h> /* for ft_memcpy() */
107
#define FT_UINT_MAX UINT_MAX
109
#define ft_memset memset
111
#define ft_setjmp setjmp
112
#define ft_longjmp longjmp
113
#define ft_jmp_buf jmp_buf
116
#define ErrRaster_Invalid_Mode -2
117
#define ErrRaster_Invalid_Outline -1
119
#define FT_BEGIN_HEADER
120
#define FT_END_HEADER
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)
131
/* Disable the tracing mechanism for simplicity -- developers can */
132
/* activate it easily by redefining these two macros. */
134
#define FT_ERROR( x ) do ; while ( 0 ) /* nothing */
138
#define FT_TRACE( x ) do ; while ( 0 ) /* nothing */
142
#else /* _STANDALONE_ */
145
#include <ft2build.h>
147
#include FT_INTERNAL_OBJECTS_H
148
#include FT_INTERNAL_DEBUG_H
149
#include FT_OUTLINE_H
151
#include "ftsmerrs.h"
153
#define ErrRaster_Invalid_Mode Smooth_Err_Cannot_Render_Glyph
154
#define ErrRaster_Invalid_Outline Smooth_Err_Invalid_Outline
157
#endif /* _STANDALONE_ */
161
#define FT_MEM_SET( d, s, c ) ft_memset( d, s, c )
165
#define FT_MEM_ZERO( dest, count ) FT_MEM_SET( dest, 0, count )
168
/* define this to dump debugging information */
169
#define xxxDEBUG_GRAYS
171
/* as usual, for the speed hungry :-) */
173
#ifndef FT_STATIC_RASTER
176
#define RAS_ARG PRaster raster
177
#define RAS_ARG_ PRaster raster,
179
#define RAS_VAR raster
180
#define RAS_VAR_ raster,
182
#define ras (*raster)
185
#else /* FT_STATIC_RASTER */
188
#define RAS_ARG /* empty */
189
#define RAS_ARG_ /* empty */
190
#define RAS_VAR /* empty */
191
#define RAS_VAR_ /* empty */
196
#endif /* FT_STATIC_RASTER */
199
/* must be at least 6 bits! */
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 )
211
#define UPSCALE( x ) ( (x) << ( PIXEL_BITS - 6 ) )
212
#define DOWNSCALE( x ) ( (x) >> ( PIXEL_BITS - 6 ) )
214
#define UPSCALE( x ) ( (x) >> ( 6 - PIXEL_BITS ) )
215
#define DOWNSCALE( x ) ( (x) << ( 6 - PIXEL_BITS ) )
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 */
225
/*************************************************************************/
227
/* TYPE DEFINITIONS */
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 */
234
typedef int TCoord; /* integer scanline/pixel coordinate */
235
typedef long TPos; /* sub-pixel coordinate */
237
/* determine the type used to store cell areas. This normally takes at */
238
/* least PIXEL_BYTES*2 + 1. On 16-bit systems, we need to use `long' */
239
/* instead of `int', otherwise bad things happen */
245
#else /* PIXEL_BITS >= 8 */
247
/* approximately determine the size of integers using an ANSI-C header */
248
#if FT_UINT_MAX == 0xFFFFU
254
#endif /* PIXEL_BITS >= 8 */
257
/* maximal number of gray spans in a call to the span callback */
258
#define FT_MAX_GRAY_SPANS 32
263
typedef struct TCell_
267
int cover : PIXEL_BITS + 2;
268
int area : PIXEL_BITS * 2 + 2;
272
#else /* GRAYS_COMPACT */
274
typedef struct TCell_
283
#endif /* GRAYS_COMPACT */
286
typedef struct TRaster_
305
FT_Vector bez_stack[32 * 3 + 1];
312
FT_Span gray_spans[FT_MAX_GRAY_SPANS];
315
FT_Raster_Span_Func render_span;
316
void* render_span_data;
325
ft_jmp_buf jump_buffer;
327
#ifdef GRAYS_USE_GAMMA
328
unsigned char gamma[257];
334
/*************************************************************************/
336
/* Initialize the cells table. */
339
gray_init_cells( RAS_ARG_ void* buffer,
342
ras.cells = (PCell)buffer;
343
ras.max_cells = (int)( byte_size / sizeof ( TCell ) );
351
/*************************************************************************/
353
/* Compute the outline bounding box. */
356
gray_compute_cbox( RAS_ARG )
358
FT_Outline* outline = &ras.outline;
359
FT_Vector* vec = outline->points;
360
FT_Vector* limit = vec + outline->n_points;
363
if ( outline->n_points <= 0 )
365
ras.min_ex = ras.max_ex = 0;
366
ras.min_ey = ras.max_ey = 0;
370
ras.min_ex = ras.max_ex = vec->x;
371
ras.min_ey = ras.max_ey = vec->y;
375
for ( ; vec < limit; vec++ )
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;
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;
395
/*************************************************************************/
397
/* Record the current cell in the table. */
400
gray_record_cell( RAS_ARG )
405
if ( !ras.invalid && ( ras.area | ras.cover ) )
407
if ( ras.num_cells >= ras.max_cells )
408
ft_longjmp( ras.jump_buffer, 1 );
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;
419
/*************************************************************************/
421
/* Set the current cell to a new position. */
424
gray_set_cell( RAS_ARG_ TCoord ex,
427
int invalid, record, clean;
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: */
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 */
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. */
443
invalid = ( ey < ras.min_ey || ey >= ras.max_ey || ex >= ras.max_ex );
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);
451
/* if our position is new, then record the previous cell */
452
if ( ex != ras.ex || ey != ras.ey )
455
clean = ras.invalid; /* do not clean if we didn't move from */
459
/* record the previous cell if needed (i.e., if we changed the cell */
460
/* position, of changed the `invalid' flag) */
461
if ( ras.invalid != invalid || record )
462
gray_record_cell( RAS_VAR );
470
ras.invalid = invalid;
476
/*************************************************************************/
478
/* Start a new contour at a given cell. */
481
gray_start_cell( RAS_ARG_ TCoord ex,
484
if ( ex < ras.min_ex )
485
ex = (TCoord)(ras.min_ex - 1);
491
ras.last_ey = SUBPIXELS( ey );
494
gray_set_cell( RAS_VAR_ ex, ey );
498
/*************************************************************************/
500
/* Render a scanline as one or more cells. */
503
gray_render_scanline( RAS_ARG_ TCoord ey,
509
TCoord ex1, ex2, fx1, fx2, delta;
511
int incr, lift, mod, rem;
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 ) );
521
/* trivial case. Happens often */
524
gray_set_cell( RAS_VAR_ ex2, ey );
528
/* everything is located in a single cell. That is easy! */
533
ras.area += (TArea)( fx1 + fx2 ) * delta;
538
/* ok, we'll have to render a run of adjacent cells on the same */
541
p = ( ONE_PIXEL - fx1 ) * ( y2 - y1 );
547
p = fx1 * ( y2 - y1 );
553
delta = (TCoord)( p / dx );
554
mod = (TCoord)( p % dx );
561
ras.area += (TArea)( fx1 + first ) * delta;
565
gray_set_cell( RAS_VAR_ ex1, ey );
570
p = ONE_PIXEL * ( y2 - y1 + delta );
571
lift = (TCoord)( p / dx );
572
rem = (TCoord)( p % dx );
591
ras.area += (TArea)ONE_PIXEL * delta;
595
gray_set_cell( RAS_VAR_ ex1, ey );
600
ras.area += (TArea)( fx2 + ONE_PIXEL - first ) * delta;
605
/*************************************************************************/
607
/* Render a given line as a series of scanlines. */
610
gray_render_line( RAS_ARG_ TPos to_x,
613
TCoord ey1, ey2, fy1, fy2;
616
int delta, rem, mod, lift, incr;
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 ) );
627
/* XXX: we should do something about the trivial case where dx == 0, */
628
/* as it happens very often! */
630
/* perform vertical clipping */
642
if ( min >= ras.max_ey || max < ras.min_ey )
646
/* everything is on a single scanline */
649
gray_render_scanline( RAS_VAR_ ey1, ras.x, fy1, to_x, fy2 );
653
/* vertical line - avoid calling gray_render_scanline */
658
TCoord ex = TRUNC( ras.x );
659
TCoord two_fx = (TCoord)( ( ras.x - SUBPIXELS( ex ) ) << 1 );
670
delta = (int)( first - fy1 );
671
ras.area += (TArea)two_fx * delta;
675
gray_set_cell( raster, ex, ey1 );
677
delta = (int)( first + first - ONE_PIXEL );
678
area = (TArea)two_fx * delta;
684
gray_set_cell( raster, ex, ey1 );
687
delta = (int)( fy2 - ONE_PIXEL + first );
688
ras.area += (TArea)two_fx * delta;
693
/* ok, we have to render several scanlines */
694
p = ( ONE_PIXEL - fy1 ) * dx;
706
delta = (int)( p / dy );
707
mod = (int)( p % dy );
715
gray_render_scanline( RAS_VAR_ ey1, ras.x, fy1, x, (TCoord)first );
718
gray_set_cell( RAS_VAR_ TRUNC( x ), ey1 );
723
lift = (int)( p / dy );
724
rem = (int)( p % dy );
743
gray_render_scanline( RAS_VAR_ ey1, x,
744
(TCoord)( ONE_PIXEL - first ), x2,
749
gray_set_cell( RAS_VAR_ TRUNC( x ), ey1 );
753
gray_render_scanline( RAS_VAR_ ey1, x,
754
(TCoord)( ONE_PIXEL - first ), to_x,
760
ras.last_ey = SUBPIXELS( ey2 );
765
gray_split_conic( FT_Vector* base )
770
base[4].x = base[2].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;
776
base[4].y = base[2].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;
785
gray_render_conic( RAS_ARG_ FT_Vector* control,
794
dx = DOWNSCALE( ras.x ) + to->x - ( control->x << 1 );
797
dy = DOWNSCALE( ras.y ) + to->y - ( control->y << 1 );
804
dx = dx / ras.conic_level;
811
/* a shortcut to speed things up */
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;
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;
824
gray_render_line( RAS_VAR_ mid_x, mid_y );
825
gray_render_line( RAS_VAR_ to_x, to_y );
830
levels = ras.lev_stack;
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 );
846
/* check that the arc crosses the current band */
850
min = max = arc[0].y;
853
if ( y < min ) min = y;
854
if ( y > max ) max = y;
857
if ( y < min ) min = y;
858
if ( y > max ) max = y;
860
if ( TRUNC( min ) >= ras.max_ey || TRUNC( max ) < ras.min_ey )
863
gray_split_conic( arc );
866
levels[top] = levels[top - 1] = level - 1;
872
TPos to_x, to_y, mid_x, mid_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;
880
gray_render_line( RAS_VAR_ mid_x, mid_y );
881
gray_render_line( RAS_VAR_ to_x, to_y );
892
gray_split_cubic( FT_Vector* base )
897
base[6].x = base[3].x;
900
base[1].x = a = ( base[0].x + c ) / 2;
901
base[5].x = b = ( base[3].x + 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;
907
base[6].y = base[3].y;
910
base[1].y = a = ( base[0].y + c ) / 2;
911
base[5].y = b = ( base[3].y + 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;
920
gray_render_cubic( RAS_ARG_ FT_Vector* control1,
930
dx = DOWNSCALE( ras.x ) + to->x - ( control1->x << 1 );
933
dy = DOWNSCALE( ras.y ) + to->y - ( control1->y << 1 );
940
dx = DOWNSCALE( ras.x ) + to->x - 3 * ( control1->x + control2->x );
943
dy = DOWNSCALE( ras.y ) + to->y - 3 * ( control1->x + control2->y );
951
da = da / ras.cubic_level;
952
db = db / ras.conic_level;
953
while ( da > 0 || db > 0 )
962
TPos to_x, to_y, mid_x, mid_y;
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;
972
gray_render_line( RAS_VAR_ mid_x, mid_y );
973
gray_render_line( RAS_VAR_ to_x, to_y );
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 );
987
levels = ras.lev_stack;
996
/* check that the arc crosses the current band */
1000
min = max = arc[0].y;
1002
if ( y < min ) min = y;
1003
if ( y > max ) max = y;
1005
if ( y < min ) min = y;
1006
if ( y > max ) max = y;
1008
if ( y < min ) min = y;
1009
if ( y > max ) max = y;
1010
if ( TRUNC( min ) >= ras.max_ey || TRUNC( max ) < 0 )
1012
gray_split_cubic( arc );
1015
levels[top] = levels[top - 1] = level - 1;
1021
TPos to_x, to_y, mid_x, mid_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;
1029
gray_render_line( RAS_VAR_ mid_x, mid_y );
1030
gray_render_line( RAS_VAR_ to_x, to_y );
1039
/* a macro comparing two cell pointers. Returns true if a <= b. */
1042
#define PACK( a ) ( ( (long)(a)->y << 16 ) + (a)->x )
1043
#define LESS_THAN( a, b ) ( PACK( a ) < PACK( b ) )
1047
#define LESS_THAN( a, b ) ( (a)->y < (b)->y || \
1048
( (a)->y == (b)->y && (a)->x < (b)->x ) )
1052
#define SWAP_CELLS( a, b, temp ) do \
1063
/* a simple shell sort algorithm that works directly on our */
1066
gray_shell_sort ( PCell cells,
1069
PCell i, j, limit = cells + count;
1074
/* compute initial gap */
1075
for ( gap = 0; ++gap < count; gap *= 3 )
1080
for ( i = cells + gap; i < limit; i++ )
1082
for ( j = i - gap; ; j -= gap )
1087
if ( LESS_THAN( j, k ) )
1090
SWAP_CELLS( j, k, temp );
1092
if ( j < cells + gap )
1099
#endif /* SHELL_SORT */
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... */
1108
#define QSORT_THRESHOLD 9 /* below this size, a sub-array will be sorted */
1109
/* through a normal insertion sort */
1112
gray_quick_sort( PCell cells,
1115
PCell stack[40]; /* should be enough ;-) */
1116
PCell* top; /* top of stack */
1121
limit = cells + count;
1127
int len = (int)( limit - base );
1131
if ( len > QSORT_THRESHOLD )
1133
/* we use base + len/2 as the pivot */
1134
pivot = base + len / 2;
1135
SWAP_CELLS( base, pivot, temp );
1140
/* now ensure that *i <= *base <= *j */
1141
if ( LESS_THAN( j, i ) )
1142
SWAP_CELLS( i, j, temp );
1144
if ( LESS_THAN( base, i ) )
1145
SWAP_CELLS( base, i, temp );
1147
if ( LESS_THAN( j, base ) )
1148
SWAP_CELLS( base, j, temp );
1152
do i++; while ( LESS_THAN( i, base ) );
1153
do j--; while ( LESS_THAN( base, j ) );
1158
SWAP_CELLS( i, j, temp );
1161
SWAP_CELLS( base, j, temp );
1163
/* now, push the largest sub-array */
1164
if ( j - base > limit - i )
1180
/* the sub-array is small, perform insertion sort */
1184
for ( ; i < limit; j = i, i++ )
1186
for ( ; LESS_THAN( j + 1, j ); j-- )
1188
SWAP_CELLS( j + 1, j, temp );
1205
#endif /* QUICK_SORT */
1212
gray_check_sort( PCell cells,
1218
for ( p = cells + count - 2; p >= cells; p-- )
1221
if ( !LESS_THAN( p, q ) )
1227
#endif /* DEBUG_SORT */
1228
#endif /* DEBUG_GRAYS */
1232
gray_move_to( FT_Vector* to,
1238
/* record current cell, if any */
1239
gray_record_cell( (PRaster)raster );
1241
/* start to a new position */
1242
x = UPSCALE( to->x );
1243
y = UPSCALE( to->y );
1245
gray_start_cell( (PRaster)raster, TRUNC( x ), TRUNC( y ) );
1247
((PRaster)raster)->x = x;
1248
((PRaster)raster)->y = y;
1254
gray_line_to( FT_Vector* to,
1257
gray_render_line( (PRaster)raster,
1258
UPSCALE( to->x ), UPSCALE( to->y ) );
1264
gray_conic_to( FT_Vector* control,
1268
gray_render_conic( (PRaster)raster, control, to );
1274
gray_cubic_to( FT_Vector* control1,
1275
FT_Vector* control2,
1279
gray_render_cubic( (PRaster)raster, control1, control2, to );
1285
gray_render_span( int y,
1291
FT_Bitmap* map = &raster->target;
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;
1299
for ( ; count > 0; count--, spans++ )
1301
unsigned char coverage = spans->coverage;
1304
#ifdef GRAYS_USE_GAMMA
1305
coverage = raster->gamma[coverage];
1310
FT_MEM_SET( p + spans->x, (unsigned char)coverage, spans->len );
1314
limit = q + spans->len;
1315
for ( ; q < limit; q++ )
1316
q[0] = (unsigned char)coverage;
1328
gray_dump_cells( RAS_ARG )
1335
limit = cell + ras.num_cells;
1337
for ( ; cell < limit; cell++ )
1341
fprintf( stderr, "\n%2d: ", cell->y );
1344
fprintf( stderr, "[%d %d %d]",
1345
cell->x, cell->area, cell->cover );
1347
fprintf(stderr, "\n" );
1350
#endif /* DEBUG_GRAYS */
1354
gray_hline( RAS_ARG_ TCoord x,
1364
/* compute the coverage line's coverage, depending on the */
1365
/* outline fill rule */
1367
/* the coverage percentage is area/(PIXEL_BITS*PIXEL_BITS*2) */
1369
coverage = (int)( area >> ( PIXEL_BITS * 2 + 1 - 8 ) );
1370
/* use range 0..256 */
1372
coverage = -coverage;
1374
if ( ras.outline.flags & FT_OUTLINE_EVEN_ODD_FILL )
1378
if ( coverage > 256 )
1379
coverage = 512 - coverage;
1380
else if ( coverage == 256 )
1385
/* normal non-zero winding rule */
1386
if ( coverage >= 256 )
1390
y += (TCoord)ras.min_ey;
1391
x += (TCoord)ras.min_ex;
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;
1400
(int)span->x + span->len == (int)x &&
1401
span->coverage == coverage )
1403
span->len = (unsigned short)( span->len + acount );
1407
if ( ras.span_y != y || count >= FT_MAX_GRAY_SPANS )
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 ); */
1416
if ( ras.span_y >= 0 )
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" );
1429
#endif /* DEBUG_GRAYS */
1431
ras.num_gray_spans = 0;
1435
span = ras.gray_spans;
1440
/* add a gray span to the current list */
1442
span->len = (unsigned short)acount;
1443
span->coverage = (unsigned char)coverage;
1444
ras.num_gray_spans++;
1450
gray_sweep( RAS_ARG_ FT_Bitmap* target )
1454
PCell start, cur, limit;
1456
FT_UNUSED( target );
1459
if ( ras.num_cells == 0 )
1463
limit = cur + ras.num_cells;
1467
ras.num_gray_spans = 0;
1476
cover += start->cover;
1478
/* accumulate all start cells */
1482
if ( cur >= limit || cur->y != start->y || cur->x != start->x )
1486
cover += cur->cover;
1489
/* if the start cell has a non-null area, we must draw an */
1490
/* individual gray pixel there */
1491
if ( area && x >= 0 )
1493
gray_hline( RAS_VAR_ x, y, cover * ( ONE_PIXEL * 2 ) - area, 1 );
1500
if ( cur < limit && start->y == cur->y )
1502
/* draw a gray span between the start cell and the current one */
1504
gray_hline( RAS_VAR_ x, y,
1505
cover * ( ONE_PIXEL * 2 ), cur->x - x );
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 ) );
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 );
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" );
1540
#endif /* DEBUG_GRAYS */
1547
/*************************************************************************/
1549
/* The following function should only compile in stand_alone mode, */
1550
/* i.e., when building this component without the rest of FreeType. */
1552
/*************************************************************************/
1554
/*************************************************************************/
1557
/* FT_Outline_Decompose */
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. */
1566
/* outline :: A pointer to the source target. */
1568
/* func_interface :: A table of `emitters', i.e,. function pointers */
1569
/* called during decomposition to indicate path */
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. */
1578
/* Error code. 0 means sucess. */
1581
int FT_Outline_Decompose( FT_Outline* outline,
1582
const FT_Outline_Funcs* func_interface,
1587
#define SCALED( x ) ( ( (x) << shift ) - delta )
1589
#define SCALED( x ) (x)
1593
FT_Vector v_control;
1600
int n; /* index of contour in outline */
1601
int first; /* index of first point in contour */
1603
char tag; /* current point's state */
1606
int shift = func_interface->shift;
1607
TPos delta = func_interface->delta;
1613
for ( n = 0; n < outline->n_contours; n++ )
1615
int last; /* index of last point in contour */
1618
last = outline->contours[n];
1619
limit = outline->points + last;
1621
v_start = outline->points[first];
1622
v_last = outline->points[last];
1624
v_start.x = SCALED( v_start.x ); v_start.y = SCALED( v_start.y );
1625
v_last.x = SCALED( v_last.x ); v_last.y = SCALED( v_last.y );
1627
v_control = v_start;
1629
point = outline->points + first;
1630
tags = outline->tags + first;
1631
tag = FT_CURVE_TAG( tags[0] );
1633
/* A contour cannot start with a cubic control point! */
1634
if ( tag == FT_CURVE_TAG_CUBIC )
1635
goto Invalid_Outline;
1637
/* check first point to determine origin */
1638
if ( tag == FT_CURVE_TAG_CONIC )
1640
/* first point is conic control. Yes, this happens. */
1641
if ( FT_CURVE_TAG( outline->tags[last] ) == FT_CURVE_TAG_ON )
1643
/* start at last point if it is on the curve */
1649
/* if both first and last points are conic, */
1650
/* start at their middle and record its position */
1652
v_start.x = ( v_start.x + v_last.x ) / 2;
1653
v_start.y = ( v_start.y + v_last.y ) / 2;
1661
error = func_interface->move_to( &v_start, user );
1665
while ( point < limit )
1670
tag = FT_CURVE_TAG( tags[0] );
1673
case FT_CURVE_TAG_ON: /* emit a single line_to */
1678
vec.x = SCALED( point->x );
1679
vec.y = SCALED( point->y );
1681
error = func_interface->line_to( &vec, user );
1687
case FT_CURVE_TAG_CONIC: /* consume conic arcs */
1689
v_control.x = SCALED( point->x );
1690
v_control.y = SCALED( point->y );
1693
if ( point < limit )
1701
tag = FT_CURVE_TAG( tags[0] );
1703
vec.x = SCALED( point->x );
1704
vec.y = SCALED( point->y );
1706
if ( tag == FT_CURVE_TAG_ON )
1708
error = func_interface->conic_to( &v_control, &vec, user );
1714
if ( tag != FT_CURVE_TAG_CONIC )
1715
goto Invalid_Outline;
1717
v_middle.x = ( v_control.x + vec.x ) / 2;
1718
v_middle.y = ( v_control.y + vec.y ) / 2;
1720
error = func_interface->conic_to( &v_control, &v_middle, user );
1728
error = func_interface->conic_to( &v_control, &v_start, user );
1732
default: /* FT_CURVE_TAG_CUBIC */
1734
FT_Vector vec1, vec2;
1737
if ( point + 1 > limit ||
1738
FT_CURVE_TAG( tags[1] ) != FT_CURVE_TAG_CUBIC )
1739
goto Invalid_Outline;
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 );
1747
if ( point <= limit )
1752
vec.x = SCALED( point->x );
1753
vec.y = SCALED( point->y );
1755
error = func_interface->cubic_to( &vec1, &vec2, &vec, user );
1761
error = func_interface->cubic_to( &vec1, &vec2, &v_start, user );
1767
/* close the contour with a line segment */
1768
error = func_interface->line_to( &v_start, user );
1783
return ErrRaster_Invalid_Outline;
1786
#endif /* _STANDALONE_ */
1789
typedef struct TBand_
1797
gray_convert_glyph_inner( RAS_ARG )
1800
const FT_Outline_Funcs func_interface =
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,
1810
volatile int error = 0;
1812
if ( ft_setjmp( ras.jump_buffer ) == 0 )
1814
error = FT_Outline_Decompose( &ras.outline, &func_interface, &ras );
1815
gray_record_cell( RAS_VAR );
1819
error = ErrRaster_MemoryOverflow;
1827
gray_convert_glyph( RAS_ARG )
1830
TBand* volatile band;
1831
int volatile n, num_bands;
1832
TPos volatile min, max, max_y;
1836
/* Set up state in the raster object */
1837
gray_compute_cbox( RAS_VAR );
1839
/* clip to target bitmap, exit if nothing to do */
1840
clip = &ras.clip_box;
1842
if ( ras.max_ex <= clip->xMin || ras.min_ex >= clip->xMax ||
1843
ras.max_ey <= clip->yMin || ras.min_ey >= clip->yMax )
1846
if ( ras.min_ex < clip->xMin ) ras.min_ex = clip->xMin;
1847
if ( ras.min_ey < clip->yMin ) ras.min_ey = clip->yMin;
1849
if ( ras.max_ex > clip->xMax ) ras.max_ex = clip->xMax;
1850
if ( ras.max_ey > clip->yMax ) ras.max_ey = clip->yMax;
1852
/* simple heuristic used to speed-up the bezier decomposition -- see */
1853
/* the code in gray_render_conic() and gray_render_cubic() for more */
1855
ras.conic_level = 32;
1856
ras.cubic_level = 16;
1862
if ( ras.max_ex > 24 || ras.max_ey > 24 )
1864
if ( ras.max_ex > 120 || ras.max_ey > 120 )
1867
ras.conic_level <<= level;
1868
ras.cubic_level <<= level;
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;
1881
for ( n = 0; n < num_bands; n++, min = max )
1883
max = min + ras.band_size;
1884
if ( n == num_bands - 1 || max > max_y )
1891
while ( band >= bands )
1893
TPos bottom, top, middle;
1899
ras.min_ey = band->min;
1900
ras.max_ey = band->max;
1903
error = gray_convert_glyph_inner( RAS_VAR );
1905
error = FT_Outline_Decompose( outline, &func_interface, &ras ) ||
1906
gray_record_cell( RAS_VAR );
1912
gray_shell_sort( ras.cells, ras.num_cells );
1914
gray_quick_sort( ras.cells, ras.num_cells );
1918
gray_check_sort( ras.cells, ras.num_cells );
1919
gray_dump_cells( RAS_VAR );
1922
gray_sweep( RAS_VAR_ &ras.target );
1926
else if ( error != ErrRaster_MemoryOverflow )
1929
/* render pool overflow, we will reduce the render band by half */
1932
middle = bottom + ( ( top - bottom ) >> 1 );
1934
/* waoow! This is too complex for a single scanline, something */
1935
/* must be really rotten here! */
1936
if ( middle == bottom )
1939
fprintf( stderr, "Rotten glyph!\n" );
1944
if ( bottom-top >= ras.band_size )
1947
band[1].min = bottom;
1948
band[1].max = middle;
1949
band[0].min = middle;
1955
if ( ras.band_shoot > 8 && ras.band_size > 16 )
1956
ras.band_size = ras.band_size / 2;
1963
gray_raster_render( PRaster raster,
1964
FT_Raster_Params* params )
1966
FT_Outline* outline = (FT_Outline*)params->source;
1967
FT_Bitmap* target_map = params->target;
1970
if ( !raster || !raster->cells || !raster->max_cells )
1973
/* return immediately if the outline is empty */
1974
if ( outline->n_points == 0 || outline->n_contours <= 0 )
1977
if ( !outline || !outline->contours || !outline->points )
1978
return ErrRaster_Invalid_Outline;
1980
if ( outline->n_points !=
1981
outline->contours[outline->n_contours - 1] + 1 )
1982
return ErrRaster_Invalid_Outline;
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 ) )
1989
/* this version does not support monochrome rendering */
1990
if ( !( params->flags & FT_RASTER_FLAG_AA ) )
1991
return ErrRaster_Invalid_Mode;
1993
/* compute clipping box */
1994
if ( ( params->flags & FT_RASTER_FLAG_DIRECT ) == 0 )
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;
2002
else if ( params->flags & FT_RASTER_FLAG_CLIP )
2004
ras.clip_box = params->clip_box;
2008
ras.clip_box.xMin = -32768L;
2009
ras.clip_box.yMin = -32768L;
2010
ras.clip_box.xMax = 32767L;
2011
ras.clip_box.yMax = 32767L;
2014
ras.outline = *outline;
2019
ras.target = *target_map;
2021
ras.render_span = (FT_Raster_Span_Func)gray_render_span;
2022
ras.render_span_data = &ras;
2024
if ( params->flags & FT_RASTER_FLAG_DIRECT )
2026
ras.render_span = (FT_Raster_Span_Func)params->gray_spans;
2027
ras.render_span_data = params->user;
2030
return gray_convert_glyph( (PRaster)raster );
2034
/**** RASTER OBJECT CREATION: In standalone mode, we simply use *****/
2035
/**** a static object. *****/
2037
#ifdef GRAYS_USE_GAMMA
2039
/* initialize the "gamma" table. Yes, this is really a crummy function */
2040
/* but the results look pretty good for something that simple. */
2047
grays_init_gamma( PRaster raster )
2052
for ( x = 0; x < 256; x++ )
2055
a = ( x * M_Y + M_X / 2) / M_X;
2057
a = M_Y + ( ( x - M_X ) * ( M_MAX - M_Y ) +
2058
( M_MAX - M_X ) / 2 ) / ( M_MAX - M_X );
2060
raster->gamma[x] = (unsigned char)a;
2064
#endif /* GRAYS_USE_GAMMA */
2069
gray_raster_new( void* memory,
2070
FT_Raster* araster )
2072
static TRaster the_raster;
2074
FT_UNUSED( memory );
2077
*araster = (FT_Raster)&the_raster;
2078
FT_MEM_ZERO( &the_raster, sizeof ( the_raster ) );
2080
#ifdef GRAYS_USE_GAMMA
2081
grays_init_gamma( (PRaster)*araster );
2089
gray_raster_done( FT_Raster raster )
2092
FT_UNUSED( raster );
2095
#else /* _STANDALONE_ */
2098
gray_raster_new( FT_Memory memory,
2099
FT_Raster* araster )
2106
if ( !FT_ALLOC( raster, sizeof ( TRaster ) ) )
2108
raster->memory = memory;
2109
*araster = (FT_Raster)raster;
2111
#ifdef GRAYS_USE_GAMMA
2112
grays_init_gamma( raster );
2121
gray_raster_done( FT_Raster raster )
2123
FT_Memory memory = (FT_Memory)((PRaster)raster)->memory;
2129
#endif /* _STANDALONE_ */
2133
gray_raster_reset( FT_Raster raster,
2134
const char* pool_base,
2137
PRaster rast = (PRaster)raster;
2140
if ( raster && pool_base && pool_size >= 4096 )
2141
gray_init_cells( rast, (char*)pool_base, pool_size );
2143
rast->band_size = (int)( ( pool_size / sizeof ( TCell ) ) / 8 );
2147
const FT_Raster_Funcs ft_grays_raster =
2149
FT_GLYPH_FORMAT_OUTLINE,
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