ftgrays.c

一个用于智能手机的多媒体库适合S60 WinCE的跨平台开发库

/***************************************************************************/
/*                                                                         */
/*  ftgrays.c                                                              */
/*                                                                         */
/*    A new `perfect' anti-aliasing renderer (body).                       */
/*                                                                         */
/*  Copyright 2000-2001, 2002 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 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.                                                           */
  /*                                                                       */
  /*************************************************************************/


/*
	GPAC version modifications:
		* removed all cubic/quadratic support (present in GPAC path objects)
		* moved span data memoru to dynamic allocation
		* bypassed Y-sorting of cells by using an array of scanlines: a bit more consuming
		in memory, but faster cell sorting (X-sorting only)
*/

#include "rast_soft.h"

#include <limits.h>

#define ErrRaster_MemoryOverflow   -4
#define ErrRaster_Invalid_Mode     -2
#define ErrRaster_Invalid_Outline  -1


#define GPAC_FIX_BITS		16
#define PIXEL_BITS  8
#define PIXEL_BITS_DIFF 8	/*GPAC_FIX_BITS - PIXEL_BITS*/

#define ONE_PIXEL       ( 1L << PIXEL_BITS )
#define PIXEL_MASK      ( -1L << PIXEL_BITS )
#define TRUNC( x )      ( (TCoord)((x) >> PIXEL_BITS) )
#define SUBPIXELS( x )  ( (TPos)(x) << PIXEL_BITS )
#define FLOOR( x )      ( (x) & -ONE_PIXEL )
#define CEILING( x )    ( ( (x) + ONE_PIXEL - 1 ) & -ONE_PIXEL )
#define ROUND( x )      ( ( (x) + ONE_PIXEL / 2 ) & -ONE_PIXEL )
#define UPSCALE( x )    ( (x) >> ( PIXEL_BITS_DIFF) )
#define DOWNSCALE( x )  ( (x) << ( PIXEL_BITS_DIFF) )


/*************************************************************************/
/*                                                                       */
/*   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 int   TCoord;   /* integer scanline/pixel coordinate */
typedef long  TPos;     /* sub-pixel coordinate              */

/* determine the type used to store cell areas.  This normally takes at */
/* least PIXEL_BYTES*2 + 1.  On 16-bit systems, we need to use `long'   */
/* instead of `int', otherwise bad things happen                        */

/* approximately determine the size of integers using an ANSI-C header */
#if UINT_MAX == 0xFFFFU
typedef long  TArea;
#else
typedef int  TArea;
#endif


  /* maximal number of gray spans in a call to the span callback */
#define FT_MAX_GRAY_SPANS  64

typedef struct  TCell_
{
	TCoord  x;
	int     cover;
	TArea   area;
} AACell;

typedef struct
{
	AACell *cells;
	int alloc, num;
} AAScanline;


typedef struct  TRaster_
{
	AAScanline *scanlines;
	int max_lines;
	TPos min_ex, max_ex, min_ey, max_ey;
	TCoord ex, ey;
	TPos x,  y, last_ey;
	TArea area;
	int cover;

	EVG_Span gray_spans[FT_MAX_GRAY_SPANS];
	int num_gray_spans;
	EVG_Raster_Span_Func  render_span;
	void *render_span_data;

#ifdef INLINE_POINT_CONVERSION
	GF_Matrix2D *mx;
#endif
} TRaster;

#define AA_CELL_STEP_ALLOC	8

static GFINLINE void gray_record_cell( TRaster *raster ) 
{
	if (( raster->area | raster->cover) && (raster->ey<raster->max_ey)) {
		AACell *cell;
		int y = raster->ey - raster->min_ey;
		if (y>=0) {
			AAScanline *sl = &raster->scanlines[y];
			if (sl->num >= sl->alloc) {
				sl->cells = (AACell*)realloc(sl->cells, sizeof(AACell)* (sl->alloc + AA_CELL_STEP_ALLOC));
				sl->alloc += AA_CELL_STEP_ALLOC;
			}
			cell = &sl->cells[sl->num];
			sl->num++;
			/*clip cell */
			if (raster->ex<raster->min_ex) cell->x = (TCoord) -1;
			else if (raster->ex>raster->max_ex) cell->x = (TCoord) (raster->max_ex - raster->min_ex);
			else cell->x = (TCoord)(raster->ex - raster->min_ex);
			cell->area = raster->area;
			cell->cover = raster->cover;
		}
	}
}

static GFINLINE void gray_set_cell( TRaster *raster, TCoord  ex, TCoord  ey )
{
	if ((raster->ex != ex) || (raster->ey != ey)) {
		gray_record_cell(raster);
		raster->ex = ex;
		raster->ey = ey;
		raster->area = 0;
		raster->cover = 0;
	}
}


#ifdef INLINE_POINT_CONVERSION

static GFINLINE void evg_translate_point(GF_Matrix2D *mx, EVG_Vector *pt, TPos *x, TPos *y)
{
		Fixed _x, _y;
		_x = pt->x;
		_y = pt->y;
		gf_mx2d_apply_coords(mx, &_x, &_y);
#ifdef GPAC_FIXED_POINT
		*x = UPSCALE(_x);
		*y = UPSCALE(_y);
#else
		*x = (s32) (_x * ONE_PIXEL);
		*y = (s32) (_y * ONE_PIXEL);
#endif
}
#endif

static GFINLINE int gray_move_to( EVG_Vector*  to, EVG_Raster   raster)
{
	TPos  x, y;
	TCoord  ex, ey;

	/* record current cell, if any */
	gray_record_cell(raster);

#ifdef INLINE_POINT_CONVERSION
	evg_translate_point(raster->mx, to, &x, &y);
#else
	x = UPSCALE( to->x );
	y = UPSCALE( to->y );
#endif
	ex = TRUNC(x);
	ey = TRUNC(y);
	if ( ex < raster->min_ex ) ex = (TCoord)(raster->min_ex - 1);
	raster->area    = 0;
	raster->cover   = 0;
	gray_set_cell( raster, ex, ey );
	raster->last_ey = SUBPIXELS( ey );

	raster->x = x;
	raster->y = y;
	return 0;
}

/*************************************************************************/
/*                                                                       */
/* Render a scanline as one or more cells.                               */
/*                                                                       */
static void gray_render_scanline( TRaster *raster,  TCoord  ey, TPos x1, TCoord y1, TPos x2, TCoord y2)
{
	TCoord  ex1, ex2, fx1, fx2, delta;
	long    p, first, dx;
	int     incr, lift, mod, rem;
	
	dx = x2 - x1;
	ex1 = TRUNC( x1 ); /* if (ex1 >= raster->max_ex) ex1 = raster->max_ex-1; */
	ex2 = TRUNC( x2 ); /* if (ex2 >= raster->max_ex) ex2 = raster->max_ex-1; */
	fx1 = (TCoord)( x1 - SUBPIXELS( ex1 ) );
	fx2 = (TCoord)( x2 - SUBPIXELS( ex2 ) );

	/* trivial case.  Happens often */
	if ( y1 == y2 ) {
		gray_set_cell( raster, ex2, ey );
		return;
	}

	/* everything is located in a single cell.  That is easy! */
	if ( ex1 == ex2 ) {
		delta      = y2 - y1;
		raster->area  += (TArea)( fx1 + fx2 ) * delta;
		raster->cover += delta;
		return;
	}
	
	/* ok, we'll have to render a run of adjacent cells on the same */
	/* scanline...                                                  */
	p     = ( ONE_PIXEL - fx1 ) * ( y2 - y1 );
	first = ONE_PIXEL;
	incr  = 1;
	
	if ( dx < 0 ) {
		p     = fx1 * ( y2 - y1 );
		first = 0;
		incr  = -1;
		dx    = -dx;
	}
	delta = (TCoord)( p / dx );
	mod   = (TCoord)( p % dx );
	if ( mod < 0 ) {
		delta--;
		mod += (TCoord)dx;
	}
	raster->area  += (TArea)( fx1 + first ) * delta;
	raster->cover += delta;

	ex1 += incr;
	gray_set_cell( raster, ex1, ey );
	y1  += delta;

	if ( ex1 != ex2 ) {
		p     = ONE_PIXEL * ( y2 - y1 + delta );
		lift  = (TCoord)( p / dx );
		rem   = (TCoord)( p % dx );
		if ( rem < 0 ) {
			lift--;
			rem += (TCoord)dx;
		}
		mod -= (int) dx;

		while ( ex1 != ex2 ) {
			delta = lift;
			mod  += rem;
			if ( mod >= 0 ) {
				mod -= (TCoord)dx;
				delta++; 
			}

			raster->area  += (TArea)ONE_PIXEL * delta;
			raster->cover += delta;
			y1        += delta;
			ex1       += incr;
			gray_set_cell( raster, ex1, ey );
		}
	}
	delta      = y2 - y1;
	raster->area  += (TArea)( fx2 + ONE_PIXEL - first ) * delta;
	raster->cover += delta;
}


/*************************************************************************/
/*                                                                       */
/* Render a given line as a series of scanlines.                         */
static GFINLINE void gray_render_line(TRaster *raster, TPos  to_x, TPos  to_y, int is_line)
{
	TCoord  min, max;
	TCoord  ey1, ey2, fy1, fy2;
	TPos    dx, dy, x, x2;
	long    p, first;
	int     delta, rem, mod, lift, incr;

	/*point filtering*/
#if 0
	if (is_line) {
		dx = (to_x - raster->x)>>PIXEL_BITS;
		dy = (to_y - raster->y)>>PIXEL_BITS;
		if ( dx*dx + dy*dy < 1) return;
	}
#endif


	ey1 = TRUNC( raster->last_ey );
	ey2 = TRUNC( to_y ); /* if (ey2 >= raster->max_ey) ey2 = raster->max_ey-1; */
	fy1 = (TCoord)( raster->y - raster->last_ey );
	fy2 = (TCoord)( to_y - SUBPIXELS( ey2 ) );

	dx = to_x - raster->x;
	dy = to_y - raster->y;

	/* perform vertical clipping */
	min = ey1;
	max = ey2;
	if ( ey1 > ey2 ) {
		min = ey2;
		max = ey1;
	}
	if ( min >= raster->max_ey || max < raster->min_ey ) goto End;

	/* everything is on a single scanline */
	if ( ey1 == ey2 ) {
		gray_render_scanline( raster, ey1, raster->x, fy1, to_x, fy2 );
		goto End;
	}
	/* vertical line - avoid calling gray_render_scanline */
	incr = 1;
	if ( dx == 0 ) {
		TCoord  ex     = TRUNC( raster->x );
		TCoord  two_fx = (TCoord)( ( raster->x - SUBPIXELS( ex ) ) << 1 );
		TPos    area;

		first = ONE_PIXEL;
		if ( dy < 0 ) {
			first = 0;
			incr  = -1;
		}

		delta      = (int)( first - fy1 );
		raster->area  += (TArea)two_fx * delta;
		raster->cover += delta;
		ey1       += incr;

		gray_set_cell( raster, ex, ey1 );

		delta = (int)( first + first - ONE_PIXEL );
		area  = (TArea)two_fx * delta;
		while ( ey1 != ey2 ) {
			raster->area  += area;