1
/***************************************************************************/
3
/* qgrayraster.c, derived from ftgrays.c */
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, ../../3rdparty/freetype/docs/FTL.TXT. By continuing to use, */
13
/* modify, or distribute this file you indicate that you have read */
14
/* the license and 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
/* `qt_ft_gray_raster.raster_new'; an anti-aliased bitmap can be generated */
36
/* with a call to `qt_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
/*************************************************************************/
83
/* experimental support for gamma correction within the rasterizer */
84
#define xxxGRAYS_USE_GAMMA
87
/*************************************************************************/
89
/* The macro QT_FT_COMPONENT is used in trace mode. It is an implicit */
90
/* parameter of the QT_FT_TRACE() and QT_FT_ERROR() macros, used to print/log */
91
/* messages during execution. */
93
#undef QT_FT_COMPONENT
94
#define QT_FT_COMPONENT trace_smooth
97
#define ErrRaster_MemoryOverflow -4
100
#include <string.h> /* for qt_ft_memcpy() */
103
#define QT_FT_UINT_MAX UINT_MAX
105
#define qt_ft_memset memset
107
#define qt_ft_setjmp setjmp
108
#define qt_ft_longjmp longjmp
109
#define qt_ft_jmp_buf jmp_buf
112
#define ErrRaster_Invalid_Mode -2
113
#define ErrRaster_Invalid_Outline -1
115
#define QT_FT_BEGIN_HEADER
116
#define QT_FT_END_HEADER
118
#include <private/qrasterdefs_p.h>
119
#include <private/qgrayraster_p.h>
121
/* This macro is used to indicate that a function parameter is unused. */
122
/* Its purpose is simply to reduce compiler warnings. Note also that */
123
/* simply defining it as `(void)x' doesn't avoid warnings with certain */
124
/* ANSI compilers (e.g. LCC). */
125
#define QT_FT_UNUSED( x ) (x) = (x)
127
/* Disable the tracing mechanism for simplicity -- developers can */
128
/* activate it easily by redefining these two macros. */
130
#define QT_FT_ERROR( x ) do ; while ( 0 ) /* nothing */
134
#define QT_FT_TRACE( x ) do ; while ( 0 ) /* nothing */
138
#ifndef QT_FT_MEM_SET
139
#define QT_FT_MEM_SET( d, s, c ) qt_ft_memset( d, s, c )
142
#ifndef QT_FT_MEM_ZERO
143
#define QT_FT_MEM_ZERO( dest, count ) QT_FT_MEM_SET( dest, 0, count )
146
/* define this to dump debugging information */
147
#define xxxDEBUG_GRAYS
149
/* as usual, for the speed hungry :-) */
151
#ifndef QT_FT_STATIC_RASTER
154
#define RAS_ARG PRaster raster
155
#define RAS_ARG_ PRaster raster,
157
#define RAS_VAR raster
158
#define RAS_VAR_ raster,
160
#define ras (*raster)
163
#else /* QT_FT_STATIC_RASTER */
166
#define RAS_ARG /* empty */
167
#define RAS_ARG_ /* empty */
168
#define RAS_VAR /* empty */
169
#define RAS_VAR_ /* empty */
174
#endif /* QT_FT_STATIC_RASTER */
177
/* must be at least 6 bits! */
180
#define ONE_PIXEL ( 1L << PIXEL_BITS )
181
#define PIXEL_MASK ( -1L << PIXEL_BITS )
182
#define TRUNC( x ) ( (TCoord)((x) >> PIXEL_BITS) )
183
#define SUBPIXELS( x ) ( (TPos)(x) << PIXEL_BITS )
184
#define FLOOR( x ) ( (x) & -ONE_PIXEL )
185
#define CEILING( x ) ( ( (x) + ONE_PIXEL - 1 ) & -ONE_PIXEL )
186
#define ROUND( x ) ( ( (x) + ONE_PIXEL / 2 ) & -ONE_PIXEL )
189
#define UPSCALE( x ) ( (x) << ( PIXEL_BITS - 6 ) )
190
#define DOWNSCALE( x ) ( (x) >> ( PIXEL_BITS - 6 ) )
192
#define UPSCALE( x ) ( (x) >> ( 6 - PIXEL_BITS ) )
193
#define DOWNSCALE( x ) ( (x) << ( 6 - PIXEL_BITS ) )
196
/* Define this if you want to use a more compact storage scheme. This */
197
/* increases the number of cells available in the render pool but slows */
198
/* down the rendering a bit. It is useful if you have a really tiny */
203
/*************************************************************************/
205
/* TYPE DEFINITIONS */
208
/* don't change the following types to QT_FT_Int or QT_FT_Pos, since we might */
209
/* need to define them to "float" or "double" when experimenting with */
212
typedef int TCoord; /* integer scanline/pixel coordinate */
213
typedef long TPos; /* sub-pixel coordinate */
215
/* determine the type used to store cell areas. This normally takes at */
216
/* least PIXEL_BYTES*2 + 1. On 16-bit systems, we need to use `long' */
217
/* instead of `int', otherwise bad things happen */
223
#else /* PIXEL_BITS >= 8 */
225
/* approximately determine the size of integers using an ANSI-C header */
226
#if QT_FT_UINT_MAX == 0xFFFFU
232
#endif /* PIXEL_BITS >= 8 */
235
/* maximal number of gray spans in a call to the span callback */
236
#define QT_FT_MAX_GRAY_SPANS 32
241
typedef struct TCell_
245
int cover : PIXEL_BITS + 2;
246
int area : PIXEL_BITS * 2 + 2;
250
#else /* GRAYS_COMPACT */
252
typedef struct TCell_
261
#endif /* GRAYS_COMPACT */
264
typedef struct TRaster_
283
QT_FT_Vector bez_stack[32 * 3 + 1];
286
QT_FT_Outline outline;
290
QT_FT_Span gray_spans[QT_FT_MAX_GRAY_SPANS];
293
QT_FT_Raster_Span_Func render_span;
294
void* render_span_data;
303
qt_ft_jmp_buf jump_buffer;
305
#ifdef GRAYS_USE_GAMMA
306
unsigned char gamma[257];
312
/*************************************************************************/
314
/* Initialize the cells table. */
317
gray_init_cells( RAS_ARG_ void* buffer,
320
ras.cells = (PCell)buffer;
321
ras.max_cells = (int)( byte_size / sizeof ( TCell ) );
329
/*************************************************************************/
331
/* Compute the outline bounding box. */
334
gray_compute_cbox( RAS_ARG )
336
QT_FT_Outline* outline = &ras.outline;
337
QT_FT_Vector* vec = outline->points;
338
QT_FT_Vector* limit = vec + outline->n_points;
341
if ( outline->n_points <= 0 )
343
ras.min_ex = ras.max_ex = 0;
344
ras.min_ey = ras.max_ey = 0;
348
ras.min_ex = ras.max_ex = vec->x;
349
ras.min_ey = ras.max_ey = vec->y;
353
for ( ; vec < limit; vec++ )
359
if ( x < ras.min_ex ) ras.min_ex = x;
360
if ( x > ras.max_ex ) ras.max_ex = x;
361
if ( y < ras.min_ey ) ras.min_ey = y;
362
if ( y > ras.max_ey ) ras.max_ey = y;
365
/* truncate the bounding box to integer pixels */
366
ras.min_ex = ras.min_ex >> 6;
367
ras.min_ey = ras.min_ey >> 6;
368
ras.max_ex = ( ras.max_ex + 63 ) >> 6;
369
ras.max_ey = ( ras.max_ey + 63 ) >> 6;
373
/*************************************************************************/
375
/* Record the current cell in the table. */
378
gray_record_cell( RAS_ARG )
383
if ( !ras.invalid && ( ras.area | ras.cover ) )
385
if ( ras.num_cells >= ras.max_cells )
386
qt_ft_longjmp( ras.jump_buffer, 1 );
388
cell = ras.cells + ras.num_cells++;
389
cell->x = (TCoord)(ras.ex - ras.min_ex);
390
cell->y = (TCoord)(ras.ey - ras.min_ey);
391
cell->area = ras.area;
392
cell->cover = ras.cover;
397
/*************************************************************************/
399
/* Set the current cell to a new position. */
402
gray_set_cell( RAS_ARG_ TCoord ex,
405
int invalid, record, clean;
408
/* Move the cell pointer to a new position. We set the `invalid' */
409
/* flag to indicate that the cell isn't part of those we're interested */
410
/* in during the render phase. This means that: */
412
/* . the new vertical position must be within min_ey..max_ey-1. */
413
/* . the new horizontal position must be strictly less than max_ex */
415
/* Note that if a cell is to the left of the clipping region, it is */
416
/* actually set to the (min_ex-1) horizontal position. */
421
invalid = ( ey < ras.min_ey || ey >= ras.max_ey || ex >= ras.max_ex );
424
/* All cells that are on the left of the clipping region go to the */
425
/* min_ex - 1 horizontal position. */
426
if ( ex < ras.min_ex )
427
ex = (TCoord)(ras.min_ex - 1);
429
/* if our position is new, then record the previous cell */
430
if ( ex != ras.ex || ey != ras.ey )
433
clean = ras.invalid; /* do not clean if we didn't move from */
437
/* record the previous cell if needed (i.e., if we changed the cell */
438
/* position, of changed the `invalid' flag) */
439
if ( ras.invalid != invalid || record )
440
gray_record_cell( RAS_VAR );
448
ras.invalid = invalid;
454
/*************************************************************************/
456
/* Start a new contour at a given cell. */
459
gray_start_cell( RAS_ARG_ TCoord ex,
462
if ( ex < ras.min_ex )
463
ex = (TCoord)(ras.min_ex - 1);
469
ras.last_ey = SUBPIXELS( ey );
472
gray_set_cell( RAS_VAR_ ex, ey );
476
/*************************************************************************/
478
/* Render a scanline as one or more cells. */
481
gray_render_scanline( RAS_ARG_ TCoord ey,
487
TCoord ex1, ex2, fx1, fx2, delta;
489
int incr, lift, mod, rem;
494
ex1 = TRUNC( x1 ); /* if (ex1 >= ras.max_ex) ex1 = ras.max_ex-1; */
495
ex2 = TRUNC( x2 ); /* if (ex2 >= ras.max_ex) ex2 = ras.max_ex-1; */
496
fx1 = (TCoord)( x1 - SUBPIXELS( ex1 ) );
497
fx2 = (TCoord)( x2 - SUBPIXELS( ex2 ) );
499
/* trivial case. Happens often */
502
gray_set_cell( RAS_VAR_ ex2, ey );
506
/* everything is located in a single cell. That is easy! */
511
ras.area += (TArea)( fx1 + fx2 ) * delta;
516
/* ok, we'll have to render a run of adjacent cells on the same */
519
p = ( ONE_PIXEL - fx1 ) * ( y2 - y1 );
525
p = fx1 * ( y2 - y1 );
531
delta = (TCoord)( p / dx );
532
mod = (TCoord)( p % dx );
539
ras.area += (TArea)( fx1 + first ) * delta;
543
gray_set_cell( RAS_VAR_ ex1, ey );
548
p = ONE_PIXEL * ( y2 - y1 + delta );
549
lift = (TCoord)( p / dx );
550
rem = (TCoord)( p % dx );
569
ras.area += (TArea)ONE_PIXEL * delta;
573
gray_set_cell( RAS_VAR_ ex1, ey );
578
ras.area += (TArea)( fx2 + ONE_PIXEL - first ) * delta;
583
/*************************************************************************/
585
/* Render a given line as a series of scanlines. */
588
gray_render_line( RAS_ARG_ TPos to_x,
591
TCoord ey1, ey2, fy1, fy2;
594
int delta, rem, mod, lift, incr;
597
ey1 = TRUNC( ras.last_ey );
598
ey2 = TRUNC( to_y ); /* if (ey2 >= ras.max_ey) ey2 = ras.max_ey-1; */
599
fy1 = (TCoord)( ras.y - ras.last_ey );
600
fy2 = (TCoord)( to_y - SUBPIXELS( ey2 ) );
605
/* XXX: we should do something about the trivial case where dx == 0, */
606
/* as it happens very often! */
608
/* perform vertical clipping */
620
if ( min >= ras.max_ey || max < ras.min_ey )
624
/* everything is on a single scanline */
627
gray_render_scanline( RAS_VAR_ ey1, ras.x, fy1, to_x, fy2 );
631
/* vertical line - avoid calling gray_render_scanline */
636
TCoord ex = TRUNC( ras.x );
637
TCoord two_fx = (TCoord)( ( ras.x - SUBPIXELS( ex ) ) << 1 );
648
delta = (int)( first - fy1 );
649
ras.area += (TArea)two_fx * delta;
653
gray_set_cell( raster, ex, ey1 );
655
delta = (int)( first + first - ONE_PIXEL );
656
area = (TArea)two_fx * delta;
662
gray_set_cell( raster, ex, ey1 );
665
delta = (int)( fy2 - ONE_PIXEL + first );
666
ras.area += (TArea)two_fx * delta;
671
/* ok, we have to render several scanlines */
672
p = ( ONE_PIXEL - fy1 ) * dx;
684
delta = (int)( p / dy );
685
mod = (int)( p % dy );
693
gray_render_scanline( RAS_VAR_ ey1, ras.x, fy1, x, (TCoord)first );
696
gray_set_cell( RAS_VAR_ TRUNC( x ), ey1 );
701
lift = (int)( p / dy );
702
rem = (int)( p % dy );
721
gray_render_scanline( RAS_VAR_ ey1, x,
722
(TCoord)( ONE_PIXEL - first ), x2,
727
gray_set_cell( RAS_VAR_ TRUNC( x ), ey1 );
731
gray_render_scanline( RAS_VAR_ ey1, x,
732
(TCoord)( ONE_PIXEL - first ), to_x,
738
ras.last_ey = SUBPIXELS( ey2 );
743
gray_split_conic( QT_FT_Vector* base )
748
base[4].x = base[2].x;
750
a = base[3].x = ( base[2].x + b ) / 2;
751
b = base[1].x = ( base[0].x + b ) / 2;
752
base[2].x = ( a + b ) / 2;
754
base[4].y = base[2].y;
756
a = base[3].y = ( base[2].y + b ) / 2;
757
b = base[1].y = ( base[0].y + b ) / 2;
758
base[2].y = ( a + b ) / 2;
763
gray_render_conic( RAS_ARG_ QT_FT_Vector* control,
772
dx = DOWNSCALE( ras.x ) + to->x - ( control->x << 1 );
775
dy = DOWNSCALE( ras.y ) + to->y - ( control->y << 1 );
782
dx = dx / ras.conic_level;
789
/* a shortcut to speed things up */
792
/* we compute the mid-point directly in order to avoid */
793
/* calling gray_split_conic() */
794
TPos to_x, to_y, mid_x, mid_y;
797
to_x = UPSCALE( to->x );
798
to_y = UPSCALE( to->y );
799
mid_x = ( ras.x + to_x + 2 * UPSCALE( control->x ) ) / 4;
800
mid_y = ( ras.y + to_y + 2 * UPSCALE( control->y ) ) / 4;
802
gray_render_line( RAS_VAR_ mid_x, mid_y );
803
gray_render_line( RAS_VAR_ to_x, to_y );
808
levels = ras.lev_stack;
812
arc[0].x = UPSCALE( to->x );
813
arc[0].y = UPSCALE( to->y );
814
arc[1].x = UPSCALE( control->x );
815
arc[1].y = UPSCALE( control->y );
824
/* check that the arc crosses the current band */
828
min = max = arc[0].y;
831
if ( y < min ) min = y;
832
if ( y > max ) max = y;
835
if ( y < min ) min = y;
836
if ( y > max ) max = y;
838
if ( TRUNC( min ) >= ras.max_ey || TRUNC( max ) < ras.min_ey )
841
gray_split_conic( arc );
844
levels[top] = levels[top - 1] = level - 1;
850
TPos to_x, to_y, mid_x, mid_y;
855
mid_x = ( ras.x + to_x + 2 * arc[1].x ) / 4;
856
mid_y = ( ras.y + to_y + 2 * arc[1].y ) / 4;
858
gray_render_line( RAS_VAR_ mid_x, mid_y );
859
gray_render_line( RAS_VAR_ to_x, to_y );
870
gray_split_cubic( QT_FT_Vector* base )
875
base[6].x = base[3].x;
878
base[1].x = a = ( base[0].x + c ) / 2;
879
base[5].x = b = ( base[3].x + d ) / 2;
881
base[2].x = a = ( a + c ) / 2;
882
base[4].x = b = ( b + c ) / 2;
883
base[3].x = ( a + b ) / 2;
885
base[6].y = base[3].y;
888
base[1].y = a = ( base[0].y + c ) / 2;
889
base[5].y = b = ( base[3].y + d ) / 2;
891
base[2].y = a = ( a + c ) / 2;
892
base[4].y = b = ( b + c ) / 2;
893
base[3].y = ( a + b ) / 2;
898
gray_render_cubic( RAS_ARG_ QT_FT_Vector* control1,
899
QT_FT_Vector* control2,
908
dx = DOWNSCALE( ras.x ) + to->x - ( control1->x << 1 );
911
dy = DOWNSCALE( ras.y ) + to->y - ( control1->y << 1 );
918
dx = DOWNSCALE( ras.x ) + to->x - 3 * ( control1->x + control2->x );
921
dy = DOWNSCALE( ras.y ) + to->y - 3 * ( control1->x + control2->y );
929
da = da / ras.cubic_level;
930
db = db / ras.conic_level;
931
while ( da > 0 || db > 0 )
940
TPos to_x, to_y, mid_x, mid_y;
943
to_x = UPSCALE( to->x );
944
to_y = UPSCALE( to->y );
945
mid_x = ( ras.x + to_x +
946
3 * UPSCALE( control1->x + control2->x ) ) / 8;
947
mid_y = ( ras.y + to_y +
948
3 * UPSCALE( control1->y + control2->y ) ) / 8;
950
gray_render_line( RAS_VAR_ mid_x, mid_y );
951
gray_render_line( RAS_VAR_ to_x, to_y );
956
arc[0].x = UPSCALE( to->x );
957
arc[0].y = UPSCALE( to->y );
958
arc[1].x = UPSCALE( control2->x );
959
arc[1].y = UPSCALE( control2->y );
960
arc[2].x = UPSCALE( control1->x );
961
arc[2].y = UPSCALE( control1->y );
965
levels = ras.lev_stack;
974
/* check that the arc crosses the current band */
978
min = max = arc[0].y;
980
if ( y < min ) min = y;
981
if ( y > max ) max = y;
983
if ( y < min ) min = y;
984
if ( y > max ) max = y;
986
if ( y < min ) min = y;
987
if ( y > max ) max = y;
988
if ( TRUNC( min ) >= ras.max_ey || TRUNC( max ) < 0 )
990
gray_split_cubic( arc );
993
levels[top] = levels[top - 1] = level - 1;
999
TPos to_x, to_y, mid_x, mid_y;
1004
mid_x = ( ras.x + to_x + 3 * ( arc[1].x + arc[2].x ) ) / 8;
1005
mid_y = ( ras.y + to_y + 3 * ( arc[1].y + arc[2].y ) ) / 8;
1007
gray_render_line( RAS_VAR_ mid_x, mid_y );
1008
gray_render_line( RAS_VAR_ to_x, to_y );
1017
/* a macro comparing two cell pointers. Returns true if a <= b. */
1020
#define PACK( a ) ( ( (long)(a)->y << 16 ) + (a)->x )
1021
#define LESS_THAN( a, b ) ( PACK( a ) < PACK( b ) )
1025
#define LESS_THAN( a, b ) ( (a)->y < (b)->y || \
1026
( (a)->y == (b)->y && (a)->x < (b)->x ) )
1030
#define SWAP_CELLS( a, b, temp ) do \
1041
/* a simple shell sort algorithm that works directly on our */
1044
gray_shell_sort ( PCell cells,
1047
PCell i, j, limit = cells + count;
1052
/* compute initial gap */
1053
for ( gap = 0; ++gap < count; gap *= 3 )
1058
for ( i = cells + gap; i < limit; i++ )
1060
for ( j = i - gap; ; j -= gap )
1065
if ( LESS_THAN( j, k ) )
1068
SWAP_CELLS( j, k, temp );
1070
if ( j < cells + gap )
1077
#endif /* SHELL_SORT */
1082
/* This is a non-recursive quicksort that directly process our cells */
1083
/* array. It should be faster than calling the stdlib qsort(), and we */
1084
/* can even tailor our insertion threshold... */
1086
#define QSORT_THRESHOLD 9 /* below this size, a sub-array will be sorted */
1087
/* through a normal insertion sort */
1090
gray_quick_sort( PCell cells,
1093
PCell stack[40]; /* should be enough ;-) */
1094
PCell* top; /* top of stack */
1099
limit = cells + count;
1105
int len = (int)( limit - base );
1109
if ( len > QSORT_THRESHOLD )
1111
/* we use base + len/2 as the pivot */
1112
pivot = base + len / 2;
1113
SWAP_CELLS( base, pivot, temp );
1118
/* now ensure that *i <= *base <= *j */
1119
if ( LESS_THAN( j, i ) )
1120
SWAP_CELLS( i, j, temp );
1122
if ( LESS_THAN( base, i ) )
1123
SWAP_CELLS( base, i, temp );
1125
if ( LESS_THAN( j, base ) )
1126
SWAP_CELLS( base, j, temp );
1130
do i++; while ( LESS_THAN( i, base ) );
1131
do j--; while ( LESS_THAN( base, j ) );
1136
SWAP_CELLS( i, j, temp );
1139
SWAP_CELLS( base, j, temp );
1141
/* now, push the largest sub-array */
1142
if ( j - base > limit - i )
1158
/* the sub-array is small, perform insertion sort */
1162
for ( ; i < limit; j = i, i++ )
1164
for ( ; LESS_THAN( j + 1, j ); j-- )
1166
SWAP_CELLS( j + 1, j, temp );
1183
#endif /* QUICK_SORT */
1190
gray_check_sort( PCell cells,
1196
for ( p = cells + count - 2; p >= cells; p-- )
1199
if ( !LESS_THAN( p, q ) )
1205
#endif /* DEBUG_SORT */
1206
#endif /* DEBUG_GRAYS */
1210
gray_move_to( QT_FT_Vector* to,
1211
QT_FT_Raster raster )
1215
/* record current cell, if any */
1216
gray_record_cell( (PRaster)raster );
1218
/* start to a new position */
1219
x = UPSCALE( to->x );
1220
y = UPSCALE( to->y );
1222
gray_start_cell( (PRaster)raster, TRUNC( x ), TRUNC( y ) );
1224
((PRaster)raster)->x = x;
1225
((PRaster)raster)->y = y;
1231
gray_line_to( QT_FT_Vector* to,
1232
QT_FT_Raster raster )
1234
gray_render_line( (PRaster)raster,
1235
UPSCALE( to->x ), UPSCALE( to->y ) );
1241
gray_conic_to( QT_FT_Vector* control,
1243
QT_FT_Raster raster )
1245
gray_render_conic( (PRaster)raster, control, to );
1251
gray_cubic_to( QT_FT_Vector* control1,
1252
QT_FT_Vector* control2,
1254
QT_FT_Raster raster )
1256
gray_render_cubic( (PRaster)raster, control1, control2, to );
1262
gray_render_span( int y,
1268
QT_FT_Bitmap* map = &raster->target;
1271
/* first of all, compute the scanline offset */
1272
p = (unsigned char*)map->buffer - y * map->pitch;
1273
if ( map->pitch >= 0 )
1274
p += ( map->rows - 1 ) * map->pitch;
1276
for ( ; count > 0; count--, spans++ )
1278
unsigned char coverage = spans->coverage;
1281
#ifdef GRAYS_USE_GAMMA
1282
coverage = raster->gamma[coverage];
1287
QT_FT_MEM_SET( p + spans->x, (unsigned char)coverage, spans->len );
1291
limit = q + spans->len;
1292
for ( ; q < limit; q++ )
1293
q[0] = (unsigned char)coverage;
1305
gray_dump_cells( RAS_ARG )
1312
limit = cell + ras.num_cells;
1314
for ( ; cell < limit; cell++ )
1318
fprintf( stderr, "\n%2d: ", cell->y );
1321
fprintf( stderr, "[%d %d %d]",
1322
cell->x, cell->area, cell->cover );
1324
fprintf(stderr, "\n" );
1327
#endif /* DEBUG_GRAYS */
1331
gray_hline( RAS_ARG_ TCoord x,
1341
/* compute the coverage line's coverage, depending on the */
1342
/* outline fill rule */
1344
/* the coverage percentage is area/(PIXEL_BITS*PIXEL_BITS*2) */
1346
coverage = (int)( area >> ( PIXEL_BITS * 2 + 1 - 8 ) );
1347
/* use range 0..256 */
1349
coverage = -coverage;
1351
if ( ras.outline.flags & QT_FT_OUTLINE_EVEN_ODD_FILL )
1355
if ( coverage > 256 )
1356
coverage = 512 - coverage;
1357
else if ( coverage == 256 )
1362
/* normal non-zero winding rule */
1363
if ( coverage >= 256 )
1367
y += (TCoord)ras.min_ey;
1368
x += (TCoord)ras.min_ex;
1372
/* see if we can add this span to the current list */
1373
count = ras.num_gray_spans;
1374
span = ras.gray_spans + count - 1;
1377
(int)span->x + span->len == (int)x &&
1378
span->coverage == coverage )
1380
span->len = (unsigned short)( span->len + acount );
1384
if ( ras.span_y != y || count >= QT_FT_MAX_GRAY_SPANS )
1386
if ( ras.render_span && count > 0 )
1387
ras.render_span( ras.span_y, count, ras.gray_spans,
1388
ras.render_span_data );
1389
/* ras.render_span( span->y, ras.gray_spans, count ); */
1393
if ( ras.span_y >= 0 )
1398
fprintf( stderr, "y=%3d ", ras.span_y );
1399
span = ras.gray_spans;
1400
for ( n = 0; n < count; n++, span++ )
1401
fprintf( stderr, "[%d..%d]:%02x ",
1402
span->x, span->x + span->len - 1, span->coverage );
1403
fprintf( stderr, "\n" );
1406
#endif /* DEBUG_GRAYS */
1408
ras.num_gray_spans = 0;
1412
span = ras.gray_spans;
1417
/* add a gray span to the current list */
1419
span->len = (unsigned short)acount;
1420
span->coverage = (unsigned char)coverage;
1421
ras.num_gray_spans++;
1427
gray_sweep( RAS_ARG_ QT_FT_Bitmap* target )
1431
PCell start, cur, limit;
1433
QT_FT_UNUSED( target );
1436
if ( ras.num_cells == 0 )
1440
limit = cur + ras.num_cells;
1444
ras.num_gray_spans = 0;
1453
cover += start->cover;
1455
/* accumulate all start cells */
1459
if ( cur >= limit || cur->y != start->y || cur->x != start->x )
1463
cover += cur->cover;
1466
/* if the start cell has a non-null area, we must draw an */
1467
/* individual gray pixel there */
1468
if ( area && x >= 0 )
1470
gray_hline( RAS_VAR_ x, y, cover * ( ONE_PIXEL * 2 ) - area, 1 );
1477
if ( cur < limit && start->y == cur->y )
1479
/* draw a gray span between the start cell and the current one */
1481
gray_hline( RAS_VAR_ x, y,
1482
cover * ( ONE_PIXEL * 2 ), cur->x - x );
1486
/* draw a gray span until the end of the clipping region */
1487
if ( cover && x < ras.max_ex - ras.min_ex )
1488
gray_hline( RAS_VAR_ x, y,
1489
cover * ( ONE_PIXEL * 2 ),
1490
(int)( ras.max_ex - x - ras.min_ex ) );
1498
if ( ras.render_span && ras.num_gray_spans > 0 )
1499
ras.render_span( ras.span_y, ras.num_gray_spans,
1500
ras.gray_spans, ras.render_span_data );
1509
fprintf( stderr, "y=%3d ", ras.span_y );
1510
span = ras.gray_spans;
1511
for ( n = 0; n < ras.num_gray_spans; n++, span++ )
1512
fprintf( stderr, "[%d..%d]:%02x ",
1513
span->x, span->x + span->len - 1, span->coverage );
1514
fprintf( stderr, "\n" );
1517
#endif /* DEBUG_GRAYS */
1522
/*************************************************************************/
1524
/* The following function should only compile in stand_alone mode, */
1525
/* i.e., when building this component without the rest of FreeType. */
1527
/*************************************************************************/
1529
/*************************************************************************/
1532
/* QT_FT_Outline_Decompose */
1535
/* Walks over an outline's structure to decompose it into individual */
1536
/* segments and Bezier arcs. This function is also able to emit */
1537
/* `move to' and `close to' operations to indicate the start and end */
1538
/* of new contours in the outline. */
1541
/* outline :: A pointer to the source target. */
1543
/* func_interface :: A table of `emitters', i.e,. function pointers */
1544
/* called during decomposition to indicate path */
1547
/* user :: A typeless pointer which is passed to each */
1548
/* emitter during the decomposition. It can be */
1549
/* used to store the state during the */
1550
/* decomposition. */
1553
/* Error code. 0 means sucess. */
1556
int QT_FT_Outline_Decompose( QT_FT_Outline* outline,
1557
const QT_FT_Outline_Funcs* func_interface,
1562
#define SCALED( x ) ( ( (x) << shift ) - delta )
1564
#define SCALED( x ) (x)
1567
QT_FT_Vector v_last;
1568
QT_FT_Vector v_control;
1569
QT_FT_Vector v_start;
1571
QT_FT_Vector* point;
1572
QT_FT_Vector* limit;
1575
int n; /* index of contour in outline */
1576
int first; /* index of first point in contour */
1578
char tag; /* current point's state */
1581
int shift = func_interface->shift;
1582
TPos delta = func_interface->delta;
1588
for ( n = 0; n < outline->n_contours; n++ )
1590
int last; /* index of last point in contour */
1593
last = outline->contours[n];
1594
limit = outline->points + last;
1596
v_start = outline->points[first];
1597
v_last = outline->points[last];
1599
v_start.x = SCALED( v_start.x ); v_start.y = SCALED( v_start.y );
1600
v_last.x = SCALED( v_last.x ); v_last.y = SCALED( v_last.y );
1602
v_control = v_start;
1604
point = outline->points + first;
1605
tags = outline->tags + first;
1606
tag = QT_FT_CURVE_TAG( tags[0] );
1608
/* A contour cannot start with a cubic control point! */
1609
if ( tag == QT_FT_CURVE_TAG_CUBIC )
1610
goto Invalid_Outline;
1612
/* check first point to determine origin */
1613
if ( tag == QT_FT_CURVE_TAG_CONIC )
1615
/* first point is conic control. Yes, this happens. */
1616
if ( QT_FT_CURVE_TAG( outline->tags[last] ) == QT_FT_CURVE_TAG_ON )
1618
/* start at last point if it is on the curve */
1624
/* if both first and last points are conic, */
1625
/* start at their middle and record its position */
1627
v_start.x = ( v_start.x + v_last.x ) / 2;
1628
v_start.y = ( v_start.y + v_last.y ) / 2;
1636
error = func_interface->move_to( &v_start, user );
1640
while ( point < limit )
1645
tag = QT_FT_CURVE_TAG( tags[0] );
1648
case QT_FT_CURVE_TAG_ON: /* emit a single line_to */
1653
vec.x = SCALED( point->x );
1654
vec.y = SCALED( point->y );
1656
error = func_interface->line_to( &vec, user );
1662
case QT_FT_CURVE_TAG_CONIC: /* consume conic arcs */
1664
v_control.x = SCALED( point->x );
1665
v_control.y = SCALED( point->y );
1668
if ( point < limit )
1671
QT_FT_Vector v_middle;
1676
tag = QT_FT_CURVE_TAG( tags[0] );
1678
vec.x = SCALED( point->x );
1679
vec.y = SCALED( point->y );
1681
if ( tag == QT_FT_CURVE_TAG_ON )
1683
error = func_interface->conic_to( &v_control, &vec, user );
1689
if ( tag != QT_FT_CURVE_TAG_CONIC )
1690
goto Invalid_Outline;
1692
v_middle.x = ( v_control.x + vec.x ) / 2;
1693
v_middle.y = ( v_control.y + vec.y ) / 2;
1695
error = func_interface->conic_to( &v_control, &v_middle, user );
1703
error = func_interface->conic_to( &v_control, &v_start, user );
1707
default: /* QT_FT_CURVE_TAG_CUBIC */
1709
QT_FT_Vector vec1, vec2;
1712
if ( point + 1 > limit ||
1713
QT_FT_CURVE_TAG( tags[1] ) != QT_FT_CURVE_TAG_CUBIC )
1714
goto Invalid_Outline;
1719
vec1.x = SCALED( point[-2].x ); vec1.y = SCALED( point[-2].y );
1720
vec2.x = SCALED( point[-1].x ); vec2.y = SCALED( point[-1].y );
1722
if ( point <= limit )
1727
vec.x = SCALED( point->x );
1728
vec.y = SCALED( point->y );
1730
error = func_interface->cubic_to( &vec1, &vec2, &vec, user );
1736
error = func_interface->cubic_to( &vec1, &vec2, &v_start, user );
1742
/* close the contour with a line segment */
1743
error = func_interface->line_to( &v_start, user );
1758
return ErrRaster_Invalid_Outline;
1762
typedef struct TBand_
1770
gray_convert_glyph_inner( RAS_ARG )
1773
const QT_FT_Outline_Funcs func_interface =
1775
(QT_FT_Outline_MoveTo_Func) gray_move_to,
1776
(QT_FT_Outline_LineTo_Func) gray_line_to,
1777
(QT_FT_Outline_ConicTo_Func)gray_conic_to,
1778
(QT_FT_Outline_CubicTo_Func)gray_cubic_to,
1783
volatile int error = 0;
1785
if ( qt_ft_setjmp( ras.jump_buffer ) == 0 )
1787
error = QT_FT_Outline_Decompose( &ras.outline, &func_interface, &ras );
1788
gray_record_cell( RAS_VAR );
1792
error = ErrRaster_MemoryOverflow;
1800
gray_convert_glyph( RAS_ARG )
1803
TBand* volatile band;
1804
int volatile n, num_bands;
1805
TPos volatile min, max, max_y;
1809
/* Set up state in the raster object */
1810
gray_compute_cbox( RAS_VAR );
1812
/* clip to target bitmap, exit if nothing to do */
1813
clip = &ras.clip_box;
1815
if ( ras.max_ex <= clip->xMin || ras.min_ex >= clip->xMax ||
1816
ras.max_ey <= clip->yMin || ras.min_ey >= clip->yMax )
1819
if ( ras.min_ex < clip->xMin ) ras.min_ex = clip->xMin;
1820
if ( ras.min_ey < clip->yMin ) ras.min_ey = clip->yMin;
1822
if ( ras.max_ex > clip->xMax ) ras.max_ex = clip->xMax;
1823
if ( ras.max_ey > clip->yMax ) ras.max_ey = clip->yMax;
1825
/* simple heuristic used to speed-up the bezier decomposition -- see */
1826
/* the code in gray_render_conic() and gray_render_cubic() for more */
1828
ras.conic_level = 32;
1829
ras.cubic_level = 16;
1835
if ( ras.max_ex > 24 || ras.max_ey > 24 )
1837
if ( ras.max_ex > 120 || ras.max_ey > 120 )
1840
ras.conic_level <<= level;
1841
ras.cubic_level <<= level;
1844
/* setup vertical bands */
1845
num_bands = (int)( ( ras.max_ey - ras.min_ey ) / ras.band_size );
1846
if ( num_bands == 0 ) num_bands = 1;
1847
if ( num_bands >= 39 ) num_bands = 39;
1854
for ( n = 0; n < num_bands; n++, min = max )
1856
max = min + ras.band_size;
1857
if ( n == num_bands - 1 || max > max_y )
1864
while ( band >= bands )
1866
TPos bottom, top, middle;
1872
ras.min_ey = band->min;
1873
ras.max_ey = band->max;
1876
error = gray_convert_glyph_inner( RAS_VAR );
1878
error = QT_FT_Outline_Decompose( outline, &func_interface, &ras ) ||
1879
gray_record_cell( RAS_VAR );
1885
gray_shell_sort( ras.cells, ras.num_cells );
1887
gray_quick_sort( ras.cells, ras.num_cells );
1891
gray_check_sort( ras.cells, ras.num_cells );
1892
gray_dump_cells( RAS_VAR );
1895
gray_sweep( RAS_VAR_ &ras.target );
1899
else if ( error != ErrRaster_MemoryOverflow )
1902
/* render pool overflow, we will reduce the render band by half */
1905
middle = bottom + ( ( top - bottom ) >> 1 );
1907
/* waoow! This is too complex for a single scanline, something */
1908
/* must be really rotten here! */
1909
if ( middle == bottom )
1912
fprintf( stderr, "Rotten glyph!\n" );
1917
if ( bottom-top >= ras.band_size )
1920
band[1].min = bottom;
1921
band[1].max = middle;
1922
band[0].min = middle;
1928
if ( ras.band_shoot > 8 && ras.band_size > 16 )
1929
ras.band_size = ras.band_size / 2;
1936
gray_raster_render( PRaster raster,
1937
QT_FT_Raster_Params* params )
1939
QT_FT_Outline* outline = (QT_FT_Outline*)params->source;
1940
QT_FT_Bitmap* target_map = params->target;
1943
if ( !raster || !raster->cells || !raster->max_cells )
1946
/* return immediately if the outline is empty */
1947
if ( outline->n_points == 0 || outline->n_contours <= 0 )
1950
if ( !outline || !outline->contours || !outline->points )
1951
return ErrRaster_Invalid_Outline;
1953
if ( outline->n_points !=
1954
outline->contours[outline->n_contours - 1] + 1 )
1955
return ErrRaster_Invalid_Outline;
1957
/* if direct mode is not set, we must have a target bitmap */
1958
if ( ( params->flags & QT_FT_RASTER_FLAG_DIRECT ) == 0 &&
1959
( !target_map || !target_map->buffer ) )
1962
/* this version does not support monochrome rendering */
1963
if ( !( params->flags & QT_FT_RASTER_FLAG_AA ) )
1964
return ErrRaster_Invalid_Mode;
1966
/* compute clipping box */
1967
if ( ( params->flags & QT_FT_RASTER_FLAG_DIRECT ) == 0 )
1969
/* compute clip box from target pixmap */
1970
ras.clip_box.xMin = 0;
1971
ras.clip_box.yMin = 0;
1972
ras.clip_box.xMax = target_map->width;
1973
ras.clip_box.yMax = target_map->rows;
1975
else if ( params->flags & QT_FT_RASTER_FLAG_CLIP )
1977
ras.clip_box = params->clip_box;
1981
ras.clip_box.xMin = -32768L;
1982
ras.clip_box.yMin = -32768L;
1983
ras.clip_box.xMax = 32767L;
1984
ras.clip_box.yMax = 32767L;
1987
ras.outline = *outline;
1992
ras.target = *target_map;
1994
ras.render_span = (QT_FT_Raster_Span_Func)gray_render_span;
1995
ras.render_span_data = &ras;
1997
if ( params->flags & QT_FT_RASTER_FLAG_DIRECT )
1999
ras.render_span = (QT_FT_Raster_Span_Func)params->gray_spans;
2000
ras.render_span_data = params->user;
2003
return gray_convert_glyph( (PRaster)raster );
2007
/**** RASTER OBJECT CREATION: In standalone mode, we simply use *****/
2008
/**** a static object. *****/
2010
#ifdef GRAYS_USE_GAMMA
2012
/* initialize the "gamma" table. Yes, this is really a crummy function */
2013
/* but the results look pretty good for something that simple. */
2020
grays_init_gamma( PRaster raster )
2025
for ( x = 0; x < 256; x++ )
2028
a = ( x * M_Y + M_X / 2) / M_X;
2030
a = M_Y + ( ( x - M_X ) * ( M_MAX - M_Y ) +
2031
( M_MAX - M_X ) / 2 ) / ( M_MAX - M_X );
2033
raster->gamma[x] = (unsigned char)a;
2037
#endif /* GRAYS_USE_GAMMA */
2040
gray_raster_new( void* memory,
2041
QT_FT_Raster* araster )
2043
static TRaster the_raster;
2045
QT_FT_UNUSED( memory );
2048
*araster = (QT_FT_Raster)&the_raster;
2049
QT_FT_MEM_ZERO( &the_raster, sizeof ( the_raster ) );
2051
#ifdef GRAYS_USE_GAMMA
2052
grays_init_gamma( (PRaster)*araster );
2060
gray_raster_done( QT_FT_Raster raster )
2063
QT_FT_UNUSED( raster );
2067
gray_raster_reset( QT_FT_Raster raster,
2068
const char* pool_base,
2071
PRaster rast = (PRaster)raster;
2074
if ( raster && pool_base && pool_size >= 4096 )
2075
gray_init_cells( rast, (char*)pool_base, pool_size );
2077
rast->band_size = (int)( ( pool_size / sizeof ( TCell ) ) / 8 );
2081
const QT_FT_Raster_Funcs qt_ft_grays_raster =
2083
QT_FT_GLYPH_FORMAT_OUTLINE,
2085
(QT_FT_Raster_New_Func) gray_raster_new,
2086
(QT_FT_Raster_Reset_Func) gray_raster_reset,
2087
(QT_FT_Raster_Set_Mode_Func)0,
2088
(QT_FT_Raster_Render_Func) gray_raster_render,
2089
(QT_FT_Raster_Done_Func) gray_raster_done