diff options
Diffstat (limited to 'src/freetype/ftgrays.c')
| -rw-r--r-- | src/freetype/ftgrays.c | 1377 |
1 files changed, 1377 insertions, 0 deletions
diff --git a/src/freetype/ftgrays.c b/src/freetype/ftgrays.c new file mode 100644 index 0000000..afbe609 --- /dev/null +++ b/src/freetype/ftgrays.c @@ -0,0 +1,1377 @@ +/***************************************************************************/ +/* */ +/* ftgrays.c */ +/* */ +/* A new `perfect' anti-aliasing renderer (body). */ +/* */ +/* Copyright 2000-2018 by */ +/* David Turner, Robert Wilhelm, and Werner Lemberg. */ +/* */ +/* This file is part of the FreeType project, and may only be used, */ +/* modified, and distributed under the terms of the FreeType project */ +/* license, LICENSE.TXT. By continuing to use, modify, or distribute */ +/* this file you indicate that you have read the license and */ +/* understand and accept it fully. */ +/* */ +/***************************************************************************/ + + /*************************************************************************/ + /* */ + /* This file can be compiled without the rest of the FreeType engine, by */ + /* defining the STANDALONE_ macro when compiling it. You also need to */ + /* put the files `ftgrays.h' and `ftimage.h' into the current */ + /* compilation directory. Typically, you could do something like */ + /* */ + /* - copy `src/smooth/ftgrays.c' (this file) to your current directory */ + /* */ + /* - copy `include/freetype/ftimage.h' and `src/smooth/ftgrays.h' to the */ + /* same directory */ + /* */ + /* - compile `ftgrays' with the STANDALONE_ macro defined, as in */ + /* */ + /* cc -c -DSTANDALONE_ ftgrays.c */ + /* */ + /* The renderer can be initialized with a call to */ + /* `ft_gray_raster.raster_new'; an anti-aliased bitmap can be generated */ + /* with a call to `ft_gray_raster.raster_render'. */ + /* */ + /* See the comments and documentation in the file `ftimage.h' for more */ + /* details on how the raster works. */ + /* */ + /*************************************************************************/ + + /*************************************************************************/ + /* */ + /* This is a new anti-aliasing scan-converter for FreeType 2. The */ + /* algorithm used here is _very_ different from the one in the standard */ + /* `ftraster' module. Actually, `ftgrays' computes the _exact_ */ + /* coverage of the outline on each pixel cell. */ + /* */ + /* It is based on ideas that I initially found in Raph Levien's */ + /* excellent LibArt graphics library (see http://www.levien.com/libart */ + /* for more information, though the web pages do not tell anything */ + /* about the renderer; you'll have to dive into the source code to */ + /* understand how it works). */ + /* */ + /* Note, however, that this is a _very_ different implementation */ + /* compared to Raph's. Coverage information is stored in a very */ + /* different way, and I don't use sorted vector paths. Also, it doesn't */ + /* use floating point values. */ + /* */ + /* This renderer has the following advantages: */ + /* */ + /* - It doesn't need an intermediate bitmap. Instead, one can supply a */ + /* callback function that will be called by the renderer to draw gray */ + /* spans on any target surface. You can thus do direct composition on */ + /* any kind of bitmap, provided that you give the renderer the right */ + /* callback. */ + /* */ + /* - A perfect anti-aliaser, i.e., it computes the _exact_ coverage on */ + /* each pixel cell. */ + /* */ + /* - It performs a single pass on the outline (the `standard' FT2 */ + /* renderer makes two passes). */ + /* */ + /* - It can easily be modified to render to _any_ number of gray levels */ + /* cheaply. */ + /* */ + /* - For small (< 20) pixel sizes, it is faster than the standard */ + /* renderer. */ + /* */ + /*************************************************************************/ + + + /*************************************************************************/ + /* */ + /* The macro FT_COMPONENT is used in trace mode. It is an implicit */ + /* parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log */ + /* messages during execution. */ + /* */ +#undef FT_COMPONENT +#define FT_COMPONENT trace_smooth + + +#include "ft2build.h" +#include "ftgrays.h" +#include FT_INTERNAL_OBJECTS_H +#include FT_INTERNAL_DEBUG_H +#include FT_INTERNAL_CALC_H +#include FT_OUTLINE_H + +#include "ftsmerrs.h" + +#define Smooth_Err_Invalid_Mode Smooth_Err_Cannot_Render_Glyph +#define Smooth_Err_Memory_Overflow Smooth_Err_Out_Of_Memory +#define ErrRaster_Memory_Overflow Smooth_Err_Out_Of_Memory + + + /* as usual, for the speed hungry :-) */ + +#undef RAS_ARG +#undef RAS_ARG_ +#undef RAS_VAR +#undef RAS_VAR_ + +#ifndef FT_STATIC_RASTER + +#define RAS_ARG gray_PWorker worker +#define RAS_ARG_ gray_PWorker worker, + +#define RAS_VAR worker +#define RAS_VAR_ worker, + +#else /* FT_STATIC_RASTER */ + +#define RAS_ARG void +#define RAS_ARG_ /* empty */ +#define RAS_VAR /* empty */ +#define RAS_VAR_ /* empty */ + +#endif /* FT_STATIC_RASTER */ + + + /* must be at least 6 bits! */ +#define PIXEL_BITS 8 + +#undef FLOOR +#undef CEILING +#undef TRUNC +#undef SCALED + +#define ONE_PIXEL ( 1 << PIXEL_BITS ) +#define TRUNC( x ) ( (TCoord)( (x) >> PIXEL_BITS ) ) +#define SUBPIXELS( x ) ( (TPos)(x) * ONE_PIXEL ) +#define FLOOR( x ) ( (x) & -ONE_PIXEL ) +#define CEILING( x ) ( ( (x) + ONE_PIXEL - 1 ) & -ONE_PIXEL ) +#define ROUND( x ) ( ( (x) + ONE_PIXEL / 2 ) & -ONE_PIXEL ) + +#if PIXEL_BITS >= 6 +#define UPSCALE( x ) ( (x) * ( ONE_PIXEL >> 6 ) ) +#define DOWNSCALE( x ) ( (x) >> ( PIXEL_BITS - 6 ) ) +#else +#define UPSCALE( x ) ( (x) >> ( 6 - PIXEL_BITS ) ) +#define DOWNSCALE( x ) ( (x) * ( 64 >> PIXEL_BITS ) ) +#endif + + + /* Compute `dividend / divisor' and return both its quotient and */ + /* remainder, cast to a specific type. This macro also ensures that */ + /* the remainder is always positive. We use the remainder to keep */ + /* track of accumulating errors and compensate for them. */ +#define FT_DIV_MOD( type, dividend, divisor, quotient, remainder ) \ + FT_BEGIN_STMNT \ + (quotient) = (type)( (dividend) / (divisor) ); \ + (remainder) = (type)( (dividend) % (divisor) ); \ + if ( (remainder) < 0 ) \ + { \ + (quotient)--; \ + (remainder) += (type)(divisor); \ + } \ + FT_END_STMNT + +#ifdef __arm__ + /* Work around a bug specific to GCC which make the compiler fail to */ + /* optimize a division and modulo operation on the same parameters */ + /* into a single call to `__aeabi_idivmod'. See */ + /* */ + /* https://gcc.gnu.org/bugzilla/show_bug.cgi?id=43721 */ +#undef FT_DIV_MOD +#define FT_DIV_MOD( type, dividend, divisor, quotient, remainder ) \ + FT_BEGIN_STMNT \ + (quotient) = (type)( (dividend) / (divisor) ); \ + (remainder) = (type)( (dividend) - (quotient) * (divisor) ); \ + if ( (remainder) < 0 ) \ + { \ + (quotient)--; \ + (remainder) += (type)(divisor); \ + } \ + FT_END_STMNT +#endif /* __arm__ */ + + + /* These macros speed up repetitive divisions by replacing them */ + /* with multiplications and right shifts. */ +#define FT_UDIVPREP( c, b ) \ + long b ## _r = c ? (long)( FT_ULONG_MAX >> PIXEL_BITS ) / ( b ) \ + : 0 +#define FT_UDIV( a, b ) \ + ( ( (unsigned long)( a ) * (unsigned long)( b ## _r ) ) >> \ + ( sizeof( long ) * FT_CHAR_BIT - PIXEL_BITS ) ) + + + /*************************************************************************/ + /* */ + /* TYPE DEFINITIONS */ + /* */ + + /* don't change the following types to FT_Int or FT_Pos, since we might */ + /* need to define them to "float" or "double" when experimenting with */ + /* new algorithms */ + + typedef long TPos; /* subpixel coordinate */ + typedef int TCoord; /* integer scanline/pixel coordinate */ + typedef int TArea; /* cell areas, coordinate products */ + + + typedef struct TCell_* PCell; + + typedef struct TCell_ + { + TCoord x; /* same with gray_TWorker.ex */ + TCoord cover; /* same with gray_TWorker.cover */ + TArea area; + PCell next; + + } TCell; + + typedef struct TPixmap_ + { + unsigned char* origin; /* pixmap origin at the bottom-left */ + int pitch; /* pitch to go down one row */ + + } TPixmap; + + /* maximum number of gray cells in the buffer */ +#if FT_RENDER_POOL_SIZE > 2048 +#define FT_MAX_GRAY_POOL ( FT_RENDER_POOL_SIZE / sizeof ( TCell ) ) +#else +#define FT_MAX_GRAY_POOL ( 2048 / sizeof ( TCell ) ) +#endif + + +#if defined( _MSC_VER ) /* Visual C++ (and Intel C++) */ + /* We disable the warning `structure was padded due to */ + /* __declspec(align())' in order to compile cleanly with */ + /* the maximum level of warnings. */ +#pragma warning( push ) +#pragma warning( disable : 4324 ) +#endif /* _MSC_VER */ + + typedef struct gray_TWorker_ + { + ft_jmp_buf jump_buffer; + + TCoord ex, ey; + TCoord min_ex, max_ex; + TCoord min_ey, max_ey; + + TArea area; + TCoord cover; + int invalid; + + PCell* ycells; + PCell cells; + FT_PtrDist max_cells; + FT_PtrDist num_cells; + + TPos x, y; + + FT_Outline outline; + TPixmap target; + + FT_Raster_Span_Func render_span; + void* render_span_data; + + } gray_TWorker, *gray_PWorker; + +#if defined( _MSC_VER ) +#pragma warning( pop ) +#endif + + +#ifndef FT_STATIC_RASTER +#define ras (*worker) +#else + static gray_TWorker ras; +#endif + + +#ifdef FT_DEBUG_LEVEL_TRACE + + /* to be called while in the debugger -- */ + /* this function causes a compiler warning since it is unused otherwise */ + static void + gray_dump_cells( RAS_ARG ) + { + int y; + + + for ( y = ras.min_ey; y < ras.max_ey; y++ ) + { + PCell cell = ras.ycells[y - ras.min_ey]; + + + printf( "%3d:", y ); + + for ( ; cell != NULL; cell = cell->next ) + printf( " (%3d, c:%4d, a:%6d)", + cell->x, cell->cover, cell->area ); + printf( "\n" ); + } + } + +#endif /* FT_DEBUG_LEVEL_TRACE */ + + + /*************************************************************************/ + /* */ + /* Record the current cell in the table. */ + /* */ + static void + gray_record_cell( RAS_ARG ) + { + PCell *pcell, cell; + TCoord x = ras.ex; + + + pcell = &ras.ycells[ras.ey - ras.min_ey]; + for (;;) + { + cell = *pcell; + if ( !cell || cell->x > x ) + break; + + if ( cell->x == x ) + goto Found; + + pcell = &cell->next; + } + + if ( ras.num_cells >= ras.max_cells ) + ft_longjmp( ras.jump_buffer, 1 ); + + /* insert new cell */ + cell = ras.cells + ras.num_cells++; + cell->x = x; + cell->area = ras.area; + cell->cover = ras.cover; + + cell->next = *pcell; + *pcell = cell; + + return; + + Found: + /* update old cell */ + cell->area += ras.area; + cell->cover += ras.cover; + } + + + /*************************************************************************/ + /* */ + /* Set the current cell to a new position. */ + /* */ + static void + gray_set_cell( RAS_ARG_ TCoord ex, + TCoord ey ) + { + /* Move the cell pointer to a new position. We set the `invalid' */ + /* flag to indicate that the cell isn't part of those we're interested */ + /* in during the render phase. This means that: */ + /* */ + /* . the new vertical position must be within min_ey..max_ey-1. */ + /* . the new horizontal position must be strictly less than max_ex */ + /* */ + /* Note that if a cell is to the left of the clipping region, it is */ + /* actually set to the (min_ex-1) horizontal position. */ + + if ( ex < ras.min_ex ) + ex = ras.min_ex - 1; + + /* record the current one if it is valid and substantial */ + if ( !ras.invalid && ( ras.area || ras.cover ) ) + gray_record_cell( RAS_VAR ); + + ras.area = 0; + ras.cover = 0; + ras.ex = ex; + ras.ey = ey; + + ras.invalid = ( ey >= ras.max_ey || ey < ras.min_ey || + ex >= ras.max_ex ); + } + + +#ifndef FT_LONG64 + + /*************************************************************************/ + /* */ + /* Render a scanline as one or more cells. */ + /* */ + static void + gray_render_scanline( RAS_ARG_ TCoord ey, + TPos x1, + TCoord y1, + TPos x2, + TCoord y2 ) + { + TCoord ex1, ex2, fx1, fx2, first, dy, delta, mod; + TPos p, dx; + int incr; + + + ex1 = TRUNC( x1 ); + ex2 = TRUNC( x2 ); + + /* trivial case. Happens often */ + if ( y1 == y2 ) + { + gray_set_cell( RAS_VAR_ ex2, ey ); + return; + } + + fx1 = (TCoord)( x1 - SUBPIXELS( ex1 ) ); + fx2 = (TCoord)( x2 - SUBPIXELS( ex2 ) ); + + /* everything is located in a single cell. That is easy! */ + /* */ + if ( ex1 == ex2 ) + goto End; + + /* ok, we'll have to render a run of adjacent cells on the same */ + /* scanline... */ + /* */ + dx = x2 - x1; + dy = y2 - y1; + + if ( dx > 0 ) + { + p = ( ONE_PIXEL - fx1 ) * dy; + first = ONE_PIXEL; + incr = 1; + } + else + { + p = fx1 * dy; + first = 0; + incr = -1; + dx = -dx; + } + + FT_DIV_MOD( TCoord, p, dx, delta, mod ); + + ras.area += (TArea)( ( fx1 + first ) * delta ); + ras.cover += delta; + y1 += delta; + ex1 += incr; + gray_set_cell( RAS_VAR_ ex1, ey ); + + if ( ex1 != ex2 ) + { + TCoord lift, rem; + + + p = ONE_PIXEL * dy; + FT_DIV_MOD( TCoord, p, dx, lift, rem ); + + do + { + delta = lift; + mod += rem; + if ( mod >= (TCoord)dx ) + { + mod -= (TCoord)dx; + delta++; + } + + ras.area += (TArea)( ONE_PIXEL * delta ); + ras.cover += delta; + y1 += delta; + ex1 += incr; + gray_set_cell( RAS_VAR_ ex1, ey ); + } while ( ex1 != ex2 ); + } + + fx1 = ONE_PIXEL - first; + + End: + dy = y2 - y1; + + ras.area += (TArea)( ( fx1 + fx2 ) * dy ); + ras.cover += dy; + } + + + /*************************************************************************/ + /* */ + /* Render a given line as a series of scanlines. */ + /* */ + static void + gray_render_line( RAS_ARG_ TPos to_x, + TPos to_y ) + { + TCoord ey1, ey2, fy1, fy2, first, delta, mod; + TPos p, dx, dy, x, x2; + int incr; + + + ey1 = TRUNC( ras.y ); + ey2 = TRUNC( to_y ); /* if (ey2 >= ras.max_ey) ey2 = ras.max_ey-1; */ + + /* perform vertical clipping */ + if ( ( ey1 >= ras.max_ey && ey2 >= ras.max_ey ) || + ( ey1 < ras.min_ey && ey2 < ras.min_ey ) ) + goto End; + + fy1 = (TCoord)( ras.y - SUBPIXELS( ey1 ) ); + fy2 = (TCoord)( to_y - SUBPIXELS( ey2 ) ); + + /* everything is on a single scanline */ + if ( ey1 == ey2 ) + { + gray_render_scanline( RAS_VAR_ ey1, ras.x, fy1, to_x, fy2 ); + goto End; + } + + dx = to_x - ras.x; + dy = to_y - ras.y; + + /* vertical line - avoid calling gray_render_scanline */ + if ( dx == 0 ) + { + TCoord ex = TRUNC( ras.x ); + TCoord two_fx = (TCoord)( ( ras.x - SUBPIXELS( ex ) ) << 1 ); + TArea area; + + + if ( dy > 0) + { + first = ONE_PIXEL; + incr = 1; + } + else + { + first = 0; + incr = -1; + } + + delta = first - fy1; + ras.area += (TArea)two_fx * delta; + ras.cover += delta; + ey1 += incr; + + gray_set_cell( RAS_VAR_ ex, ey1 ); + + delta = first + first - ONE_PIXEL; + area = (TArea)two_fx * delta; + while ( ey1 != ey2 ) + { + ras.area += area; + ras.cover += delta; + ey1 += incr; + + gray_set_cell( RAS_VAR_ ex, ey1 ); + } + + delta = fy2 - ONE_PIXEL + first; + ras.area += (TArea)two_fx * delta; + ras.cover += delta; + + goto End; + } + + /* ok, we have to render several scanlines */ + if ( dy > 0) + { + p = ( ONE_PIXEL - fy1 ) * dx; + first = ONE_PIXEL; + incr = 1; + } + else + { + p = fy1 * dx; + first = 0; + incr = -1; + dy = -dy; + } + + FT_DIV_MOD( TCoord, p, dy, delta, mod ); + + x = ras.x + delta; + gray_render_scanline( RAS_VAR_ ey1, ras.x, fy1, x, first ); + + ey1 += incr; + gray_set_cell( RAS_VAR_ TRUNC( x ), ey1 ); + + if ( ey1 != ey2 ) + { + TCoord lift, rem; + + + p = ONE_PIXEL * dx; + FT_DIV_MOD( TCoord, p, dy, lift, rem ); + + do + { + delta = lift; + mod += rem; + if ( mod >= (TCoord)dy ) + { + mod -= (TCoord)dy; + delta++; + } + + x2 = x + delta; + gray_render_scanline( RAS_VAR_ ey1, + x, ONE_PIXEL - first, + x2, first ); + x = x2; + + ey1 += incr; + gray_set_cell( RAS_VAR_ TRUNC( x ), ey1 ); + } while ( ey1 != ey2 ); + } + + gray_render_scanline( RAS_VAR_ ey1, + x, ONE_PIXEL - first, + to_x, fy2 ); + + End: + ras.x = to_x; + ras.y = to_y; + } + +#else + + /*************************************************************************/ + /* */ + /* Render a straight line across multiple cells in any direction. */ + /* */ + static void + gray_render_line( RAS_ARG_ TPos to_x, + TPos to_y ) + { + TPos dx, dy, fx1, fy1, fx2, fy2; + TCoord ex1, ex2, ey1, ey2; + + + ey1 = TRUNC( ras.y ); + ey2 = TRUNC( to_y ); + + /* perform vertical clipping */ + if ( ( ey1 >= ras.max_ey && ey2 >= ras.max_ey ) || + ( ey1 < ras.min_ey && ey2 < ras.min_ey ) ) + goto End; + + ex1 = TRUNC( ras.x ); + ex2 = TRUNC( to_x ); + + fx1 = ras.x - SUBPIXELS( ex1 ); + fy1 = ras.y - SUBPIXELS( ey1 ); + + dx = to_x - ras.x; + dy = to_y - ras.y; + + if ( ex1 == ex2 && ey1 == ey2 ) /* inside one cell */ + ; + else if ( dy == 0 ) /* ex1 != ex2 */ /* any horizontal line */ + { + ex1 = ex2; + gray_set_cell( RAS_VAR_ ex1, ey1 ); + } + else if ( dx == 0 ) + { + if ( dy > 0 ) /* vertical line up */ + do + { + fy2 = ONE_PIXEL; + ras.cover += ( fy2 - fy1 ); + ras.area += ( fy2 - fy1 ) * fx1 * 2; + fy1 = 0; + ey1++; + gray_set_cell( RAS_VAR_ ex1, ey1 ); + } while ( ey1 != ey2 ); + else /* vertical line down */ + do + { + fy2 = 0; + ras.cover += ( fy2 - fy1 ); + ras.area += ( fy2 - fy1 ) * fx1 * 2; + fy1 = ONE_PIXEL; + ey1--; + gray_set_cell( RAS_VAR_ ex1, ey1 ); + } while ( ey1 != ey2 ); + } + else /* any other line */ + { + TPos prod = dx * fy1 - dy * fx1; + FT_UDIVPREP( ex1 != ex2, dx ); + FT_UDIVPREP( ey1 != ey2, dy ); + + + /* The fundamental value `prod' determines which side and the */ + /* exact coordinate where the line exits current cell. It is */ + /* also easily updated when moving from one cell to the next. */ + do + { + if ( prod <= 0 && + prod - dx * ONE_PIXEL > 0 ) /* left */ + { + fx2 = 0; + fy2 = (TPos)FT_UDIV( -prod, -dx ); + prod -= dy * ONE_PIXEL; + ras.cover += ( fy2 - fy1 ); + ras.area += ( fy2 - fy1 ) * ( fx1 + fx2 ); + fx1 = ONE_PIXEL; + fy1 = fy2; + ex1--; + } + else if ( prod - dx * ONE_PIXEL <= 0 && + prod - dx * ONE_PIXEL + dy * ONE_PIXEL > 0 ) /* up */ + { + prod -= dx * ONE_PIXEL; + fx2 = (TPos)FT_UDIV( -prod, dy ); + fy2 = ONE_PIXEL; + ras.cover += ( fy2 - fy1 ); + ras.area += ( fy2 - fy1 ) * ( fx1 + fx2 ); + fx1 = fx2; + fy1 = 0; + ey1++; + } + else if ( prod - dx * ONE_PIXEL + dy * ONE_PIXEL <= 0 && + prod + dy * ONE_PIXEL >= 0 ) /* right */ + { + prod += dy * ONE_PIXEL; + fx2 = ONE_PIXEL; + fy2 = (TPos)FT_UDIV( prod, dx ); + ras.cover += ( fy2 - fy1 ); + ras.area += ( fy2 - fy1 ) * ( fx1 + fx2 ); + fx1 = 0; + fy1 = fy2; + ex1++; + } + else /* ( prod + dy * ONE_PIXEL < 0 && + prod > 0 ) down */ + { + fx2 = (TPos)FT_UDIV( prod, -dy ); + fy2 = 0; + prod += dx * ONE_PIXEL; + ras.cover += ( fy2 - fy1 ); + ras.area += ( fy2 - fy1 ) * ( fx1 + fx2 ); + fx1 = fx2; + fy1 = ONE_PIXEL; + ey1--; + } + + gray_set_cell( RAS_VAR_ ex1, ey1 ); + } while ( ex1 != ex2 || ey1 != ey2 ); + } + + fx2 = to_x - SUBPIXELS( ex2 ); + fy2 = to_y - SUBPIXELS( ey2 ); + + ras.cover += ( fy2 - fy1 ); + ras.area += ( fy2 - fy1 ) * ( fx1 + fx2 ); + + End: + ras.x = to_x; + ras.y = to_y; + } + +#endif + + static void + gray_split_conic( FT_Vector* base ) + { + TPos a, b; + + + base[4].x = base[2].x; + b = base[1].x; + a = base[3].x = ( base[2].x + b ) / 2; + b = base[1].x = ( base[0].x + b ) / 2; + base[2].x = ( a + b ) / 2; + + base[4].y = base[2].y; + b = base[1].y; + a = base[3].y = ( base[2].y + b ) / 2; + b = base[1].y = ( base[0].y + b ) / 2; + base[2].y = ( a + b ) / 2; + } + + + static void + gray_render_conic( RAS_ARG_ const FT_Vector* control, + const FT_Vector* to ) + { + FT_Vector bez_stack[16 * 2 + 1]; /* enough to accommodate bisections */ + FT_Vector* arc = bez_stack; + TPos dx, dy; + int draw, split; + + + arc[0].x = UPSCALE( to->x ); + arc[0].y = UPSCALE( to->y ); + arc[1].x = UPSCALE( control->x ); + arc[1].y = UPSCALE( control->y ); + arc[2].x = ras.x; + arc[2].y = ras.y; + + /* short-cut the arc that crosses the current band */ + if ( ( TRUNC( arc[0].y ) >= ras.max_ey && + TRUNC( arc[1].y ) >= ras.max_ey && + TRUNC( arc[2].y ) >= ras.max_ey ) || + ( TRUNC( arc[0].y ) < ras.min_ey && + TRUNC( arc[1].y ) < ras.min_ey && + TRUNC( arc[2].y ) < ras.min_ey ) ) + { + ras.x = arc[0].x; + ras.y = arc[0].y; + return; + } + + dx = FT_ABS( arc[2].x + arc[0].x - 2 * arc[1].x ); + dy = FT_ABS( arc[2].y + arc[0].y - 2 * arc[1].y ); + if ( dx < dy ) + dx = dy; + + /* We can calculate the number of necessary bisections because */ + /* each bisection predictably reduces deviation exactly 4-fold. */ + /* Even 32-bit deviation would vanish after 16 bisections. */ + draw = 1; + while ( dx > ONE_PIXEL / 4 ) + { + dx >>= 2; + draw <<= 1; + } + + /* We use decrement counter to count the total number of segments */ + /* to draw starting from 2^level. Before each draw we split as */ + /* many times as there are trailing zeros in the counter. */ + do + { + split = 1; + while ( ( draw & split ) == 0 ) + { + gray_split_conic( arc ); + arc += 2; + split <<= 1; + } + + gray_render_line( RAS_VAR_ arc[0].x, arc[0].y ); + arc -= 2; + + } while ( --draw ); + } + + + static void + gray_split_cubic( FT_Vector* base ) + { + TPos a, b, c, d; + + + base[6].x = base[3].x; + c = base[1].x; + d = base[2].x; + base[1].x = a = ( base[0].x + c ) / 2; + base[5].x = b = ( base[3].x + d ) / 2; + c = ( c + d ) / 2; + base[2].x = a = ( a + c ) / 2; + base[4].x = b = ( b + c ) / 2; + base[3].x = ( a + b ) / 2; + + base[6].y = base[3].y; + c = base[1].y; + d = base[2].y; + base[1].y = a = ( base[0].y + c ) / 2; + base[5].y = b = ( base[3].y + d ) / 2; + c = ( c + d ) / 2; + base[2].y = a = ( a + c ) / 2; + base[4].y = b = ( b + c ) / 2; + base[3].y = ( a + b ) / 2; + } + + + static void + gray_render_cubic( RAS_ARG_ const FT_Vector* control1, + const FT_Vector* control2, + const FT_Vector* to ) + { + FT_Vector bez_stack[16 * 3 + 1]; /* enough to accommodate bisections */ + FT_Vector* arc = bez_stack; + TPos dx, dy, dx_, dy_; + TPos dx1, dy1, dx2, dy2; + TPos L, s, s_limit; + + + arc[0].x = UPSCALE( to->x ); + arc[0].y = UPSCALE( to->y ); + arc[1].x = UPSCALE( control2->x ); + arc[1].y = UPSCALE( control2->y ); + arc[2].x = UPSCALE( control1->x ); + arc[2].y = UPSCALE( control1->y ); + arc[3].x = ras.x; + arc[3].y = ras.y; + + /* short-cut the arc that crosses the current band */ + if ( ( TRUNC( arc[0].y ) >= ras.max_ey && + TRUNC( arc[1].y ) >= ras.max_ey && + TRUNC( arc[2].y ) >= ras.max_ey && + TRUNC( arc[3].y ) >= ras.max_ey ) || + ( TRUNC( arc[0].y ) < ras.min_ey && + TRUNC( arc[1].y ) < ras.min_ey && + TRUNC( arc[2].y ) < ras.min_ey && + TRUNC( arc[3].y ) < ras.min_ey ) ) + { + ras.x = arc[0].x; + ras.y = arc[0].y; + return; + } + + for (;;) + { + /* Decide whether to split or draw. See `Rapid Termination */ + /* Evaluation for Recursive Subdivision of Bezier Curves' by Thomas */ + /* F. Hain, at */ + /* http://www.cis.southalabama.edu/~hain/general/Publications/Bezier/Camera-ready%20CISST02%202.pdf */ + + /* dx and dy are x and y components of the P0-P3 chord vector. */ + dx = dx_ = arc[3].x - arc[0].x; + dy = dy_ = arc[3].y - arc[0].y; + + L = FT_HYPOT( dx_, dy_ ); + + /* Avoid possible arithmetic overflow below by splitting. */ + if ( L > 32767 ) + goto Split; + + /* Max deviation may be as much as (s/L) * 3/4 (if Hain's v = 1). */ + s_limit = L * (TPos)( ONE_PIXEL / 6 ); + + /* s is L * the perpendicular distance from P1 to the line P0-P3. */ + dx1 = arc[1].x - arc[0].x; + dy1 = arc[1].y - arc[0].y; + s = FT_ABS( SUB_LONG( MUL_LONG( dy, dx1 ), MUL_LONG( dx, dy1 ) ) ); + + if ( s > s_limit ) + goto Split; + + /* s is L * the perpendicular distance from P2 to the line P0-P3. */ + dx2 = arc[2].x - arc[0].x; + dy2 = arc[2].y - arc[0].y; + s = FT_ABS( SUB_LONG( MUL_LONG( dy, dx2 ), MUL_LONG( dx, dy2 ) ) ); + + if ( s > s_limit ) + goto Split; + + /* Split super curvy segments where the off points are so far + from the chord that the angles P0-P1-P3 or P0-P2-P3 become + acute as detected by appropriate dot products. */ + if ( dx1 * ( dx1 - dx ) + dy1 * ( dy1 - dy ) > 0 || + dx2 * ( dx2 - dx ) + dy2 * ( dy2 - dy ) > 0 ) + goto Split; + + gray_render_line( RAS_VAR_ arc[0].x, arc[0].y ); + + if ( arc == bez_stack ) + return; + + arc -= 3; + continue; + + Split: + gray_split_cubic( arc ); + arc += 3; + } + } + + + static int + gray_move_to( const FT_Vector* to, + gray_PWorker worker ) + { + TPos x, y; + + + /* start to a new position */ + x = UPSCALE( to->x ); + y = UPSCALE( to->y ); + + gray_set_cell( RAS_VAR_ TRUNC( x ), TRUNC( y ) ); + + ras.x = x; + ras.y = y; + return 0; + } + + + static int + gray_line_to( const FT_Vector* to, + gray_PWorker worker ) + { + gray_render_line( RAS_VAR_ UPSCALE( to->x ), UPSCALE( to->y ) ); + return 0; + } + + + static int + gray_conic_to( const FT_Vector* control, + const FT_Vector* to, + gray_PWorker worker ) + { + gray_render_conic( RAS_VAR_ control, to ); + return 0; + } + + + static int + gray_cubic_to( const FT_Vector* control1, + const FT_Vector* control2, + const FT_Vector* to, + gray_PWorker worker ) + { + gray_render_cubic( RAS_VAR_ control1, control2, to ); + return 0; + } + + + static void + gray_hline( RAS_ARG_ TCoord x, + TCoord y, + TArea coverage, + TCoord acount ) + { + /* scale the coverage from 0..(ONE_PIXEL*ONE_PIXEL*2) to 0..256 */ + coverage >>= PIXEL_BITS * 2 + 1 - 8; + if ( coverage < 0 ) + coverage = -coverage - 1; + + /* compute the line's coverage depending on the outline fill rule */ + if ( ras.outline.flags & FT_OUTLINE_EVEN_ODD_FILL ) + { + coverage &= 511; + + if ( coverage >= 256 ) + coverage = 511 - coverage; + } + else + { + /* normal non-zero winding rule */ + if ( coverage >= 256 ) + coverage = 255; + } + + if ( ras.render_span ) /* for FT_RASTER_FLAG_DIRECT only */ + { + FT_Span span; + + + span.x = (short)x; + span.len = (unsigned short)acount; + span.coverage = (unsigned char)coverage; + + ras.render_span( y, 1, &span, ras.render_span_data ); + } + else + { + unsigned char* q = ras.target.origin - ras.target.pitch * y + x; + unsigned char c = (unsigned char)coverage; + + + /* For small-spans it is faster to do it by ourselves than + * calling `memset'. This is mainly due to the cost of the + * function call. + */ + switch ( acount ) + { + case 7: *q++ = c; + case 6: *q++ = c; + case 5: *q++ = c; + case 4: *q++ = c; + case 3: *q++ = c; + case 2: *q++ = c; + case 1: *q = c; + case 0: break; + default: + FT_MEM_SET( q, c, acount ); + } + } + } + + + static void + gray_sweep( RAS_ARG ) + { + int y; + + + for ( y = ras.min_ey; y < ras.max_ey; y++ ) + { + PCell cell = ras.ycells[y - ras.min_ey]; + TCoord x = ras.min_ex; + TArea cover = 0; + TArea area; + + + for ( ; cell != NULL; cell = cell->next ) + { + if ( cover != 0 && cell->x > x ) + gray_hline( RAS_VAR_ x, y, cover, cell->x - x ); + + cover += (TArea)cell->cover * ( ONE_PIXEL * 2 ); + area = cover - cell->area; + + if ( area != 0 && cell->x >= ras.min_ex ) + gray_hline( RAS_VAR_ cell->x, y, area, 1 ); + + x = cell->x + 1; + } + + if ( cover != 0 ) + gray_hline( RAS_VAR_ x, y, cover, ras.max_ex - x ); + } + } + + + FT_DEFINE_OUTLINE_FUNCS( + func_interface, + + (FT_Outline_MoveTo_Func) gray_move_to, /* move_to */ + (FT_Outline_LineTo_Func) gray_line_to, /* line_to */ + (FT_Outline_ConicTo_Func)gray_conic_to, /* conic_to */ + (FT_Outline_CubicTo_Func)gray_cubic_to, /* cubic_to */ + + 0, /* shift */ + 0 /* delta */ + ) + + + static int + gray_convert_glyph_inner( RAS_ARG ) + { + + volatile int error = 0; + + if ( ft_setjmp( ras.jump_buffer ) == 0 ) + { + error = FT_Outline_Decompose( &ras.outline, &func_interface, &ras ); + if ( !ras.invalid ) + gray_record_cell( RAS_VAR ); + + FT_TRACE7(( "band [%d..%d]: %d cell%s\n", + ras.min_ey, + ras.max_ey, + ras.num_cells, + ras.num_cells == 1 ? "" : "s" )); + } + else + { + error = FT_THROW( Memory_Overflow ); + + FT_TRACE7(( "band [%d..%d]: to be bisected\n", + ras.min_ey, ras.max_ey )); + } + + return error; + } + + + static int + gray_convert_glyph( RAS_ARG ) + { + const TCoord yMin = ras.min_ey; + const TCoord yMax = ras.max_ey; + const TCoord xMin = ras.min_ex; + const TCoord xMax = ras.max_ex; + + TCell buffer[FT_MAX_GRAY_POOL]; + size_t height = (size_t)( yMax - yMin ); + size_t n = FT_MAX_GRAY_POOL / 8; + TCoord y; + TCoord bands[32]; /* enough to accommodate bisections */ + TCoord* band; + + + /* set up vertical bands */ + if ( height > n ) + { + /* two divisions rounded up */ + n = ( height + n - 1 ) / n; + height = ( height + n - 1 ) / n; + } + + /* memory management */ + n = ( height * sizeof ( PCell ) + sizeof ( TCell ) - 1 ) / sizeof ( TCell ); + + ras.cells = buffer + n; + ras.max_cells = (FT_PtrDist)( FT_MAX_GRAY_POOL - n ); + ras.ycells = (PCell*)buffer; + + for ( y = yMin; y < yMax; ) + { + ras.min_ey = y; + y += height; + ras.max_ey = FT_MIN( y, yMax ); + + band = bands; + band[1] = xMin; + band[0] = xMax; + + do + { + TCoord width = band[0] - band[1]; + int error; + + + FT_MEM_ZERO( ras.ycells, height * sizeof ( PCell ) ); + + ras.num_cells = 0; + ras.invalid = 1; + ras.min_ex = band[1]; + ras.max_ex = band[0]; + + error = gray_convert_glyph_inner( RAS_VAR ); + + if ( !error ) + { + gray_sweep( RAS_VAR ); + band--; + continue; + } + else if ( error != ErrRaster_Memory_Overflow ) + return 1; + + /* render pool overflow; we will reduce the render band by half */ + width >>= 1; + + /* this should never happen even with tiny rendering pool */ + if ( width == 0 ) + { + FT_TRACE7(( "gray_convert_glyph: rotten glyph\n" )); + return 1; + } + + band++; + band[1] = band[0]; + band[0] += width; + } while ( band >= bands ); + } + + return 0; + } + + + static int + gray_raster_render( const FT_Raster_Params* params ) + { + const FT_Outline* outline = (const FT_Outline*)params->source; + const FT_Bitmap* target_map = params->target; + FT_BBox cbox, clip; + +#ifndef FT_STATIC_RASTER + gray_TWorker worker[1]; +#endif + + /* this version does not support monochrome rendering */ + if ( !( params->flags & FT_RASTER_FLAG_AA ) ) + return FT_THROW( Invalid_Mode ); + + if ( !outline ) + return FT_THROW( Invalid_Outline ); + + /* return immediately if the outline is empty */ + if ( outline->n_points == 0 || outline->n_contours <= 0 ) + return 0; + + if ( !outline->contours || !outline->points ) + return FT_THROW( Invalid_Outline ); + + if ( outline->n_points != + outline->contours[outline->n_contours - 1] + 1 ) + return FT_THROW( Invalid_Outline ); + + ras.outline = *outline; + + if ( params->flags & FT_RASTER_FLAG_DIRECT ) + { + if ( !params->gray_spans ) + return 0; + + ras.render_span = (FT_Raster_Span_Func)params->gray_spans; + ras.render_span_data = params->user; + } + else + { + /* if direct mode is not set, we must have a target bitmap */ + if ( !target_map ) + return FT_THROW( Invalid_Argument ); + + /* nothing to do */ + if ( !target_map->width || !target_map->rows ) + return 0; + + if ( !target_map->buffer ) + return FT_THROW( Invalid_Argument ); + + if ( target_map->pitch < 0 ) + ras.target.origin = target_map->buffer; + else + ras.target.origin = target_map->buffer + + ( target_map->rows - 1 ) * (unsigned int)target_map->pitch; + + ras.target.pitch = target_map->pitch; + + ras.render_span = (FT_Raster_Span_Func)NULL; + ras.render_span_data = NULL; + } + + FT_Outline_Get_CBox( outline, &cbox ); + + /* reject too large outline coordinates */ + if ( cbox.xMin < -0x1000000L || cbox.xMax > 0x1000000L || + cbox.yMin < -0x1000000L || cbox.yMax > 0x1000000L ) + return FT_THROW( Invalid_Outline ); + + /* truncate the bounding box to integer pixels */ + cbox.xMin = cbox.xMin >> 6; + cbox.yMin = cbox.yMin >> 6; + cbox.xMax = ( cbox.xMax + 63 ) >> 6; + cbox.yMax = ( cbox.yMax + 63 ) >> 6; + + /* compute clipping box */ + if ( !( params->flags & FT_RASTER_FLAG_DIRECT ) ) + { + /* compute clip box from target pixmap */ + clip.xMin = 0; + clip.yMin = 0; + clip.xMax = (FT_Pos)target_map->width; + clip.yMax = (FT_Pos)target_map->rows; + } + else if ( params->flags & FT_RASTER_FLAG_CLIP ) + clip = params->clip_box; + else + { + clip.xMin = -32768L; + clip.yMin = -32768L; + clip.xMax = 32767L; + clip.yMax = 32767L; + } + + /* clip to target bitmap, exit if nothing to do */ + ras.min_ex = FT_MAX( cbox.xMin, clip.xMin ); + ras.min_ey = FT_MAX( cbox.yMin, clip.yMin ); + ras.max_ex = FT_MIN( cbox.xMax, clip.xMax ); + ras.max_ey = FT_MIN( cbox.yMax, clip.yMax ); + + if ( ras.max_ex <= ras.min_ex || ras.max_ey <= ras.min_ey ) + return 0; + + return gray_convert_glyph( RAS_VAR ); + } + + + FT_DEFINE_RASTER_FUNCS( + ft_grays_raster, + + (FT_Raster_Render_Func) gray_raster_render /* raster_render */ + ) + + +/* END */ + + +/* Local Variables: */ +/* coding: utf-8 */ +/* End: */ |