path2d_stroker.c

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

/***************************************************************************/
/*                                                                         */
/*  ftstroke.c                                                             */
/*                                                                         */
/*    FreeType path stroker (body).                                        */
/*                                                                         */
/*  Copyright 2002, 2003, 2004 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.                                        */
/*                                                                         */
/***************************************************************************/


#include <gpac/path2d.h>

/***************************************************************************/
/***************************************************************************/
/*****                                                                 *****/
/*****                       BEZIER COMPUTATIONS                       *****/
/*****                                                                 *****/
/***************************************************************************/
/***************************************************************************/

#define FT_SMALL_CONIC_THRESHOLD  ( GF_PI / 6 )
#define FT_SMALL_CUBIC_THRESHOLD  ( GF_PI / 6 )

#define FT_IS_SMALL( x )  ( (x) > -FIX_EPSILON && (x) < FIX_EPSILON )

static void ft_conic_split(GF_Point2D*  base )
{
	Fixed  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 Bool ft_conic_is_small_enough( GF_Point2D*  base, Fixed *angle_in, Fixed *angle_out)
{
	GF_Point2D  d1, d2;
	Fixed theta;
	s32 close1, close2;
	d1.x = base[1].x - base[2].x;
	d1.y = base[1].y - base[2].y;
	d2.x = base[0].x - base[1].x;
	d2.y = base[0].y - base[1].y;
	close1 = FT_IS_SMALL( d1.x ) && FT_IS_SMALL( d1.y );
	close2 = FT_IS_SMALL( d2.x ) && FT_IS_SMALL( d2.y );
	
	if ( close1 ) {
		if ( close2 )
			*angle_in = *angle_out = 0;
		else
			*angle_in = *angle_out = gf_atan2(d2.y, d2.x);
	}
	else if ( close2 ) {
		*angle_in = *angle_out = gf_atan2(d1.y, d1.x);
	} else {
		*angle_in  = gf_atan2(d1.y, d1.x);
		*angle_out = gf_atan2(d2.y, d2.x);
	}
	theta = ABS( gf_angle_diff(*angle_in, *angle_out));
	return ( theta < FT_SMALL_CONIC_THRESHOLD ) ? 1 : 0;
}

static void ft_cubic_split( GF_Point2D*  base )
{
    Fixed  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 Bool ft_cubic_is_small_enough(GF_Point2D *base, Fixed *angle_in, Fixed *angle_mid, Fixed *angle_out)
{
    GF_Point2D  d1, d2, d3;
    Fixed theta1, theta2;
    s32 close1, close2, close3;
    d1.x = base[2].x - base[3].x;
    d1.y = base[2].y - base[3].y;
    d2.x = base[1].x - base[2].x;
    d2.y = base[1].y - base[2].y;
    d3.x = base[0].x - base[1].x;
    d3.y = base[0].y - base[1].y;

    close1 = FT_IS_SMALL( d1.x ) && FT_IS_SMALL( d1.y );
    close2 = FT_IS_SMALL( d2.x ) && FT_IS_SMALL( d2.y );
    close3 = FT_IS_SMALL( d3.x ) && FT_IS_SMALL( d3.y );

    if ( close1 || close3 ) {
		if ( close2 ) {
			/* basically a point */
			*angle_in = *angle_out = *angle_mid = 0;
		} else if ( close1 ) {
			*angle_in  = *angle_mid = gf_atan2( d2.y, d2.x);
			*angle_out = gf_atan2( d3.y, d3.x);
		} 
		/* close2 */ 
		else {
			*angle_in  = gf_atan2(d1.y, d1.x);
			*angle_mid = *angle_out = gf_atan2(d2.y, d2.x);
		}
    }
    else if ( close2 ) {
		*angle_in  = *angle_mid = gf_atan2(d1.y, d1.x);
		*angle_out = gf_atan2(d3.y, d3.x);
    } else {
		*angle_in  = gf_atan2(d1.y, d1.x);
		*angle_mid = gf_atan2(d2.y, d2.x);
		*angle_out = gf_atan2(d3.y, d3.x);
    }
    theta1 = ABS( gf_angle_diff( *angle_in,  *angle_mid ) );
    theta2 = ABS( gf_angle_diff( *angle_mid, *angle_out ) );
    return ((theta1 < FT_SMALL_CUBIC_THRESHOLD) && (theta2 < FT_SMALL_CUBIC_THRESHOLD )) ? 1 : 0;
}


/***************************************************************************/
/***************************************************************************/
/*****                                                                 *****/
/*****                       STROKE BORDERS                            *****/
/*****                                                                 *****/
/***************************************************************************/
/***************************************************************************/

typedef enum
{
	FT_STROKE_TAG_ON    = 1,   /* on-curve point  */
	FT_STROKE_TAG_CUBIC = 2,   /* cubic off-point */
	FT_STROKE_TAG_BEGIN = 4,   /* sub-path start  */
	FT_STROKE_TAG_END   = 8    /* sub-path end    */
} FT_StrokeTags;


typedef struct  FT_StrokeBorderRec_
{
	u32 num_points;
	u32 max_points;
	GF_Point2D*  points;
	u8 *tags;
	Bool movable;
	/* index of current sub-path start point */
	s32 start;
	Bool valid;
} FT_StrokeBorderRec, *FT_StrokeBorder;


static s32 ft_stroke_border_grow(FT_StrokeBorder  border, u32 new_points)
{
	u32 new_max = border->num_points + new_points;
	if (new_max > border->max_points) {
		u32 cur_max = new_max*2;
		border->points = (GF_Point2D *) realloc(border->points, sizeof(GF_Point2D)*cur_max);
		border->tags = (u8 *) realloc(border->tags, sizeof(u8)*cur_max);
		if (!border->points || !border->tags) return -1;
		border->max_points = cur_max;
	}
	return 0;
}

static void ft_stroke_border_close( FT_StrokeBorder  border )
{
	/* don't record empty paths! */
	if ((border->start <0) || !border->num_points ) return;
	if ( border->num_points > (u32)border->start ) {
		border->tags[border->start] |= FT_STROKE_TAG_BEGIN;
		border->tags[border->num_points - 1] |= FT_STROKE_TAG_END;
	}
	border->start   = -1;
	border->movable = 0;
}

static s32 ft_stroke_border_lineto( FT_StrokeBorder  border, GF_Point2D*       to, Bool movable )
{
	assert(border->start >= 0);

	if ( border->movable ) {
		/* move last point */
		border->points[border->num_points - 1] = *to;
	} else {
		/* add one point */
		if (ft_stroke_border_grow( border, 1 )==0) {
			GF_Point2D*  vec = border->points + border->num_points;
			u8 *tag = border->tags   + border->num_points;

			vec[0] = *to;
			tag[0] = FT_STROKE_TAG_ON;
			border->num_points += 1;
		} else {
			return -1;
		}
	}
	border->movable = movable;
	return 0;
}


static s32 ft_stroke_border_conicto( FT_StrokeBorder  border, GF_Point2D*       control, GF_Point2D*       to )
{
    assert( border->start >= 0 );
    if (ft_stroke_border_grow( border, 2 )==0) {
		GF_Point2D*  vec = border->points + border->num_points;
		u8 *tag = border->tags   + border->num_points;

		vec[0] = *control;
		vec[1] = *to;

		tag[0] = 0;
		tag[1] = FT_STROKE_TAG_ON;

		border->num_points += 2;
    } else {
		return -1;
	}
    border->movable = 0;
    return 0;
}

static s32 ft_stroke_border_cubicto( FT_StrokeBorder  border,
                            GF_Point2D*       control1,
                            GF_Point2D*       control2,
                            GF_Point2D*       to )
{
	assert( border->start >= 0 );

	if (!ft_stroke_border_grow( border, 3 )) {
		GF_Point2D*  vec = border->points + border->num_points;
		u8*    tag = border->tags   + border->num_points;
		vec[0] = *control1;
		vec[1] = *control2;
		vec[2] = *to;

		tag[0] = FT_STROKE_TAG_CUBIC;
		tag[1] = FT_STROKE_TAG_CUBIC;
		tag[2] = FT_STROKE_TAG_ON;

		border->num_points += 3;
	} else {
		return -1;
	}
	border->movable = 0;
	return 0;
}

#define FT_ARC_CUBIC_ANGLE  ( GF_PI / 2 )


static s32 ft_stroke_border_arcto( FT_StrokeBorder  border,
                          GF_Point2D*       center,
                          Fixed         radius,
                          Fixed angle_start,
                          Fixed angle_diff )
{
	Fixed total, angle, step, rotate, next, theta;
	GF_Point2D  a, b, a2, b2;
	Fixed length;
	/* compute start point */
	a = gf_v2d_from_polar(radius, angle_start );
	a.x += center->x;
	a.y += center->y;

	total  = angle_diff;
	angle  = angle_start;
	rotate = ( angle_diff >= 0 ) ? GF_PI2 : -GF_PI2;

	while ( total != 0 ) {
		step = total;
		if ( step > FT_ARC_CUBIC_ANGLE )
			step = FT_ARC_CUBIC_ANGLE;
		else if ( step < -FT_ARC_CUBIC_ANGLE )
			step = -FT_ARC_CUBIC_ANGLE;
		
		next  = angle + step;
		theta = step;
		if ( theta < 0 )
			theta = -theta;

#ifdef GPAC_FIXED_POINT
		theta >>= 1;
#else
		theta /= 2;
#endif

		/* compute end point */
		b = gf_v2d_from_polar(radius, next );
		b.x += center->x;
		b.y += center->y;

		/* compute first and second control points */
		length = gf_muldiv( radius, gf_sin( theta ) * 4, ( FIX_ONE + gf_cos( theta ) ) * 3 );

		a2 = gf_v2d_from_polar(length, angle + rotate );
		a2.x += a.x;
		a2.y += a.y;

		b2 = gf_v2d_from_polar(length, next - rotate );
		b2.x += b.x;
		b2.y += b.y;

		/* add cubic arc */
		if (ft_stroke_border_cubicto( border, &a2, &b2, &b ) != 0) return -1;

		/* process the rest of the arc ?? */
		a      = b;
		total -= step;
		angle  = next;
	}
	return 0;
}


static s32 ft_stroke_border_moveto(FT_StrokeBorder  border, GF_Point2D*       to )
{
    /* close current open path if any ? */
    if ( border->start >= 0 )
		ft_stroke_border_close( border );

    border->start   = border->num_points;
    border->movable = 0;
    return ft_stroke_border_lineto( border, to, 0 );
}


static s32 ft_stroke_border_get_counts(FT_StrokeBorder  border,
                               u32 *anum_points,
                               u32 *anum_contours )
{
	s32 error        = 0;
	u32 num_points   = 0;
	u32 num_contours = 0;
	u32 count      = border->num_points;
	GF_Point2D *point      = border->points;
	u8 *tags       = border->tags;
	s32 in_contour = 0;

	for ( ; count > 0; count--, num_points++, point++, tags++ ) {
		if ( tags[0] & FT_STROKE_TAG_BEGIN ) {
			if ( in_contour != 0 ) goto Fail;

			in_contour = 1;
		} else if ( in_contour == 0 )
			goto Fail;
		
		if ( tags[0] & FT_STROKE_TAG_END ) {
			if ( in_contour == 0 ) 
				goto Fail;
			in_contour = 0;
			num_contours++;
		}
	}

	if ( in_contour != 0 )
		goto Fail;

	border->valid = 1;

Exit:
	*anum_points   = num_points;
	*anum_contours = num_contours;
	return error;

Fail:
	num_points   = 0;
	num_contours = 0;
	error = -1;
	goto Exit;
}


static void ft_stroke_border_export( FT_StrokeBorder  border, GF_Path*      outline )
{
	if (!border->num_points) return;

	/* copy point locations */
	memcpy(outline->points + outline->n_points, border->points, sizeof(GF_Point2D)*border->num_points);
	
	/* copy tags */
	{
		u32 count = border->num_points;
		u8*  read  = border->tags;
		u8*  write = (u8*)outline->tags + outline->n_points;

		for ( ; count > 0; count--, read++, write++ ) {
			if ( *read & FT_STROKE_TAG_ON )
				*write = GF_PATH_CURVE_ON;
			else if ( *read & FT_STROKE_TAG_CUBIC )
				*write = GF_PATH_CURVE_CUBIC;
			else
				*write = GF_PATH_CURVE_CONIC;
		}
	}

	/* copy contours */
	{
		u32 count = border->num_points;
		u8 *tags  = border->tags;
		u32 *write = outline->contours + outline->n_contours;
		u32 idx = outline->n_points;

		for ( ; count > 0; count--, tags++, idx++ ) {
			if ( *tags & FT_STROKE_TAG_END ) {
				*write++ = idx;
				outline->n_contours++;