path2d.c

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

/*
 *			GPAC - Multimedia Framework C SDK
 *
 *			Copyright (c) Jean Le Feuvre 2000-2005
 *					All rights reserved
 *
 *  This file is part of GPAC / common tools sub-project
 *
 *  GPAC is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU Lesser General Public License as published by
 *  the Free Software Foundation; either version 2, or (at your option)
 *  any later version.
 *   
 *  GPAC is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU Lesser General Public License for more details.
 *   
 *  You should have received a copy of the GNU Lesser General Public
 *  License along with this library; see the file COPYING.  If not, write to
 *  the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. 
 *
 */


#include <gpac/path2d.h>

GF_EXPORT
GF_Path *gf_path_new()
{
	GF_Path *gp;
	GF_SAFEALLOC(gp, GF_Path);
	gp->fineness = FIX_ONE;
	return gp;
}

GF_EXPORT
void gf_path_reset(GF_Path *gp)
{
	Fixed fineness;
	u32 flags;
	if (!gp) return;
	if (gp->contours) free(gp->contours);
	if (gp->tags) free(gp->tags);
	if (gp->points) free(gp->points);
	fineness = gp->fineness ? gp->fineness : FIX_ONE;
	flags = gp->flags;
	memset(gp, 0, sizeof(GF_Path));
	gp->flags = flags | GF_PATH_FLATTENED | GF_PATH_BBOX_DIRTY;
	gp->fineness = fineness;
}

GF_EXPORT
GF_Path *gf_path_clone(GF_Path *gp)
{
	GF_Path *dst;
	GF_SAFEALLOC(dst, GF_Path);
	if (!dst) return NULL;
	dst->contours = (u32 *)malloc(sizeof(u32)*gp->n_contours);
	if (!dst->contours) { free(dst); return NULL; }
	dst->points = (GF_Point2D *) malloc(sizeof(GF_Point2D)*gp->n_points);
	if (!dst->points) { free(dst->contours); free(dst); return NULL; }
	dst->tags = (u8 *) malloc(sizeof(u8)*gp->n_points);
	if (!dst->tags) { free(dst->points); free(dst->contours); free(dst); return NULL; }
	memcpy(dst->contours, gp->contours, sizeof(u32)*gp->n_contours);
	dst->n_contours = gp->n_contours;
	memcpy(dst->points, gp->points, sizeof(GF_Point2D)*gp->n_points);
	memcpy(dst->tags, gp->tags, sizeof(u8)*gp->n_points);
	dst->n_alloc_points = dst->n_points = gp->n_points;
	dst->flags = gp->flags;
	dst->bbox = gp->bbox;
	dst->fineness = gp->fineness;
	return dst;
}

GF_EXPORT
void gf_path_del(GF_Path *gp)
{
	if (!gp) return;
	if (gp->contours) free(gp->contours);
	if (gp->tags) free(gp->tags);
	if (gp->points) free(gp->points);
	free(gp);
}

#define PATH_POINT_ALLOC_STEP	10

#define GF_2D_REALLOC_POINT(_gp, _nb)	\
	if (_gp->n_alloc_points < _gp->n_points+_nb+1) {	\
		_gp->n_alloc_points = _gp->n_points+_nb+1;	\
		_gp->points = (GF_Point2D *)realloc(_gp->points, sizeof(GF_Point2D)*(_gp->n_alloc_points));	\
		_gp->tags = (u8 *) realloc(_gp->tags, sizeof(u8)*(_gp->n_alloc_points));	\
	}	\


GF_EXPORT
GF_Err gf_path_add_move_to(GF_Path *gp, Fixed x, Fixed y)
{
	if (!gp) return GF_BAD_PARAM;
	if (gp->n_points && (gp->points[gp->n_points-1].x == x) && (gp->points[gp->n_points-1].y == y)) return GF_OK;
	/*skip empty paths*/
	if ((gp->n_contours>=2) && (gp->contours[gp->n_contours-2]+1==gp->contours[gp->n_contours-1])) {
		gp->points[gp->n_points].x = x;
		gp->points[gp->n_points].y = y;
		return GF_OK;
	}

	gp->contours = (u32 *) realloc(gp->contours, sizeof(u32)*(gp->n_contours+1));
	GF_2D_REALLOC_POINT(gp, 1)

	gp->points[gp->n_points].x = x;
	gp->points[gp->n_points].y = y;
	gp->tags[gp->n_points] = 1;
	/*set end point*/
	gp->contours[gp->n_contours] = gp->n_points;
	/*new contour*/
	gp->n_contours++;
	gp->n_points++;
	gp->flags |= GF_PATH_BBOX_DIRTY;
	return GF_OK;
}

GF_EXPORT
GF_Err gf_path_add_move_to_vec(GF_Path *gp, GF_Point2D *pt) { return gf_path_add_move_to(gp, pt->x, pt->y); }

GF_EXPORT
GF_Err gf_path_add_line_to(GF_Path *gp, Fixed x, Fixed y)
{
	if (!gp || !gp->n_contours) return GF_BAD_PARAM;
	/*we allow line to same point as move (seen in SVG sequences) - striking will make a point*/

	GF_2D_REALLOC_POINT(gp, 1)
	gp->points[gp->n_points].x = x;
	gp->points[gp->n_points].y = y;
	gp->tags[gp->n_points] = 1;
	/*set end point*/
	gp->contours[gp->n_contours-1] = gp->n_points;
	gp->n_points++;
	gp->flags |= GF_PATH_BBOX_DIRTY;
	return GF_OK;
}

GF_EXPORT
GF_Err gf_path_add_line_to_vec(GF_Path *gp, GF_Point2D *pt) { return gf_path_add_line_to(gp, pt->x, pt->y); }

GF_EXPORT
GF_Err gf_path_close(GF_Path *gp)
{
	Fixed diff;
	GF_Point2D start, end;
	if (!gp || !gp->n_contours) return GF_BAD_PARAM;
	
	if (gp->n_contours<=1) start = gp->points[0];
	else start = gp->points[gp->contours[gp->n_contours-2] + 1];
	end = gp->points[gp->n_points-1];
	end.x -= start.x;
	end.y -= start.y;
	diff = gf_mulfix(end.x, end.x) + gf_mulfix(end.y, end.y);
	if (900*diff > FIX_ONE) {
		GF_Err e = gf_path_add_line_to(gp, start.x, start.y);
		if (e) return e;
	}
	gp->tags[gp->n_points-1] = GF_PATH_CLOSE;
	return GF_OK;
}

GF_EXPORT
GF_Err gf_path_add_cubic_to(GF_Path *gp, Fixed c1_x, Fixed c1_y, Fixed c2_x, Fixed c2_y, Fixed x, Fixed y)
{
	if (!gp || !gp->n_contours) return GF_BAD_PARAM;
	GF_2D_REALLOC_POINT(gp, 3)
	gp->points[gp->n_points].x = c1_x;
	gp->points[gp->n_points].y = c1_y;
	gp->tags[gp->n_points] = GF_PATH_CURVE_CUBIC;
	gp->n_points++;
	gp->points[gp->n_points].x = c2_x;
	gp->points[gp->n_points].y = c2_y;
	gp->tags[gp->n_points] = GF_PATH_CURVE_CUBIC;
	gp->n_points++;
	gp->points[gp->n_points].x = x;
	gp->points[gp->n_points].y = y;
	gp->tags[gp->n_points] = GF_PATH_CURVE_ON;
	/*set end point*/
	gp->contours[gp->n_contours-1] = gp->n_points;
	gp->n_points++;
	gp->flags |= GF_PATH_BBOX_DIRTY;
	gp->flags &= ~GF_PATH_FLATTENED;
	return GF_OK;
}

GF_EXPORT
GF_Err gf_path_add_cubic_to_vec(GF_Path *gp, GF_Point2D *c1, GF_Point2D *c2, GF_Point2D *pt)
{
	return gf_path_add_cubic_to(gp, c1->x, c1->y, c2->x, c2->y, pt->x, pt->y);
}


GF_EXPORT
GF_Err gf_path_add_quadratic_to(GF_Path *gp, Fixed c_x, Fixed c_y, Fixed x, Fixed y)
{
	if (!gp || !gp->n_contours) return GF_BAD_PARAM;
	GF_2D_REALLOC_POINT(gp, 2)
	gp->points[gp->n_points].x = c_x;
	gp->points[gp->n_points].y = c_y;
	gp->tags[gp->n_points] = GF_PATH_CURVE_CONIC;
	gp->n_points++;
	gp->points[gp->n_points].x = x;
	gp->points[gp->n_points].y = y;
	gp->tags[gp->n_points] = GF_PATH_CURVE_ON;
	/*set end point*/
	gp->contours[gp->n_contours-1] = gp->n_points;
	gp->n_points++;
	gp->flags |= GF_PATH_BBOX_DIRTY;
	gp->flags &= ~GF_PATH_FLATTENED;
	return GF_OK;
}
GF_EXPORT
GF_Err gf_path_add_quadratic_to_vec(GF_Path *gp, GF_Point2D *c, GF_Point2D *pt)
{
	return gf_path_add_quadratic_to(gp, c->x, c->y, pt->x, pt->y);
}

/*adds rectangle centered on cx, cy*/
GF_EXPORT
GF_Err gf_path_add_rect_center(GF_Path *gp, Fixed cx, Fixed cy, Fixed w, Fixed h)
{
	GF_Err e = gf_path_add_move_to(gp, cx - w/2, cy - h/2);
	if (e) return e;
	e = gf_path_add_line_to(gp, cx + w/2, cy - h/2);
	if (e) return e;
	e = gf_path_add_line_to(gp, cx + w/2, cy + h/2);
	if (e) return e;
	e = gf_path_add_line_to(gp, cx - w/2, cy + h/2);
	if (e) return e;
	return gf_path_close(gp);
}

GF_EXPORT
GF_Err gf_path_add_rect(GF_Path *gp, Fixed ox, Fixed oy, Fixed w, Fixed h)
{
	GF_Err e = gf_path_add_move_to(gp, ox, oy);
	if (e) return e;
	e = gf_path_add_line_to(gp, ox + w, oy);
	if (e) return e;
	e = gf_path_add_line_to(gp, ox+w, oy-h);
	if (e) return e;
	e = gf_path_add_line_to(gp, ox, oy-h);
	if (e) return e;
	return gf_path_close(gp);
}

#define GF_2D_DEFAULT_RES	64

GF_EXPORT
GF_Err gf_path_add_ellipse(GF_Path *gp, Fixed cx, Fixed cy, Fixed a_axis, Fixed b_axis)
{
	GF_Err e;
	Fixed _vx, _vy, cur;
	u32 i;
	a_axis /= 2;
	b_axis /= 2;
	e = gf_path_add_move_to(gp, cx, cy+b_axis);
	if (e) return e;
	for (i=1; i<GF_2D_DEFAULT_RES; i++) {
		cur = GF_PI2 + GF_2PI*i/GF_2D_DEFAULT_RES;
		_vx = gf_mulfix(a_axis, gf_cos(cur) );
		_vy = gf_mulfix(b_axis, gf_sin(cur) );
		e = gf_path_add_line_to(gp, _vx + cx, _vy + cy);
		if (e) return e;
	}
	return gf_path_close(gp);
}

/*generic N-bezier*/
static void NBezier(GF_Point2D *pts, s32 n, Double mu, GF_Point2D *pt_out)
{
	s32 k,kn,nn,nkn;
	Double blend, muk, munk;
	pt_out->x = pt_out->y = 0;

	muk = 1;
	munk = pow(1-mu,(Double)n);
	for (k=0;k<=n;k++) {
		nn = n;
		kn = k;
		nkn = n - k;
		blend = muk * munk;
		muk *= mu;
		munk /= (1-mu);
		while (nn >= 1) {
			blend *= nn;
			nn--;
			if (kn > 1) {
				blend /= (double)kn;
				kn--;
			}
			if (nkn > 1) {
				blend /= (double)nkn;
				nkn--;
			}
		}
		pt_out->x += gf_mulfix(pts[k].x, FLT2FIX(blend));
		pt_out->y += gf_mulfix(pts[k].y, FLT2FIX(blend));
	}
}

static void gf_add_n_bezier(GF_Path *gp, GF_Point2D *newpts, u32 nbPoints)
{
	Double mu;
	u32 numPoints, i;
	GF_Point2D start, end;
	numPoints = (u32) FIX2INT(GF_2D_DEFAULT_RES * gp->fineness);
	mu = 0.0;
	if (numPoints) mu = 1/(Double)numPoints;
	start = newpts[0];
	for (i=1; i<numPoints; i++) {
		NBezier(newpts, nbPoints - 1, i*mu, &end);
		gf_path_add_line_to(gp, end.x, end.y);
		start = end;
	}
	gf_path_add_line_to(gp, newpts[nbPoints-1].x, newpts[nbPoints-1].y);
}

GF_EXPORT
GF_Err gf_path_add_bezier(GF_Path *gp, GF_Point2D *pts, u32 nbPoints)
{
	GF_Point2D *newpts;
	if (!gp->n_points) return GF_BAD_PARAM;

	newpts = (GF_Point2D *) malloc(sizeof(GF_Point2D) * (nbPoints+1));
	newpts[0] = gp->points[gp->n_points-1];
	memcpy(&newpts[1], pts, sizeof(GF_Point2D) * nbPoints);
	
	gf_add_n_bezier(gp, newpts, nbPoints + 1);

	free(newpts);
	return GF_OK;
}

GF_EXPORT
GF_Err gf_path_add_arc_to(GF_Path *gp, Fixed end_x, Fixed end_y, Fixed fa_x, Fixed fa_y, Fixed fb_x, Fixed fb_y, Bool cw)
{
	GF_Matrix2D mat, inv;
	Fixed angle, start_angle, end_angle, sweep, axis_w, axis_h, tmp, cx, cy, _vx, _vy, start_x, start_y;
	s32 i, num_steps;

	if (!gp->n_points) return GF_BAD_PARAM;

	start_x = gp->points[gp->n_points-1].x;
	start_y = gp->points[gp->n_points-1].y;

	cx = (fb_x + fa_x)/2;
	cy = (fb_y + fa_y)/2;

	angle = gf_atan2(fb_y-fa_y, fb_x-fa_x);
	gf_mx2d_init(mat);
	gf_mx2d_add_rotation(&mat, 0, 0, angle);
	gf_mx2d_add_translation(&mat, cx, cy);

	gf_mx2d_copy(inv, mat);
	gf_mx2d_inverse(&inv);
	gf_mx2d_apply_coords(&inv, &start_x, &start_y);
	gf_mx2d_apply_coords(&inv, &end_x, &end_y);
	gf_mx2d_apply_coords(&inv, &fa_x, &fa_y);
	gf_mx2d_apply_coords(&inv, &fb_x, &fb_y);

	//start angle and end angle
	start_angle = gf_atan2(start_y, start_x);
	end_angle = gf_atan2(end_y, end_x);
	tmp = gf_mulfix((start_x - fa_x), (start_x - fa_x)) + gf_mulfix((start_y - fa_y), (start_y - fa_y));
	axis_w = gf_sqrt(tmp);
	tmp = gf_mulfix((start_x - fb_x) , (start_x - fb_x)) + gf_mulfix((start_y - fb_y), (start_y - fb_y)); 
	axis_w += gf_sqrt(tmp);
	axis_w /= 2;
	axis_h = gf_sqrt(gf_mulfix(axis_w, axis_w) - gf_mulfix(fa_x,fa_x));
	sweep = end_angle - start_angle;

	if (cw) {
		if (sweep>0) sweep -= 2*GF_PI;
	} else {
		if (sweep<0) sweep += 2*GF_PI;
	}
	num_steps = GF_2D_DEFAULT_RES/2;
	for (i=1; i<=num_steps; i++) {
		angle = start_angle + sweep*i/num_steps;
		_vx = gf_mulfix(axis_w, gf_cos(angle));
		_vy = gf_mulfix(axis_h, gf_sin(angle));
		/*re-invert*/
		gf_mx2d_apply_coords(&mat, &_vx, &_vy);
		gf_path_add_line_to(gp, _vx, _vy);
	}
	return GF_OK;
}

GF_EXPORT
GF_Err gf_path_add_arc(GF_Path *gp, Fixed radius, Fixed start_angle, Fixed end_angle, u32 close_type)
{
	GF_Err e;
	Fixed _vx, _vy, step, cur;
	s32 i, do_run;

	step = (end_angle - start_angle) / (GF_2D_DEFAULT_RES);
	radius *= 2;

	/*pie*/
	i=0;
	if (close_type==2) {
		gf_path_add_move_to(gp, 0, 0);
		i=1;
	}
	do_run = 1;
	cur=start_angle;
	while (do_run) {
		if (cur>=end_angle) {
			do_run = 0;
			cur = end_angle;
		}
		_vx = gf_mulfix(radius, gf_cos(cur));
		_vy = gf_mulfix(radius, gf_sin(cur));
		if (!i) {
			e = gf_path_add_move_to(gp, _vx, _vy);
			i = 1;
		} else {
			e = gf_path_add_line_to(gp, _vx, _vy);
		}
		if (e) return e;
		cur+=step;
	}
	if (close_type) e = gf_path_close(gp);
	return e;
}


GF_EXPORT
GF_Err gf_path_get_control_bounds(GF_Path *gp, GF_Rect *rc)
{
	GF_Point2D *pt, *end;
	Fixed xMin, xMax, yMin, yMax;
	if (!gp || !rc) return GF_BAD_PARAM;

	if (!gp->n_points) {
		rc->x = rc->y = rc->width = rc->height = 0;
		return GF_OK;
	}
	pt = gp->points;
	end = pt + gp->n_points;
	xMin = xMax = pt->x;
	yMin = yMax = pt->y;
	pt++;
	for ( ; pt < end; pt++ ) {
		Fixed v;
		v = pt->x;
		if (v < xMin) xMin = v;
		if (v > xMax) xMax = v;
		v = pt->y;
		if (v < yMin) yMin = v;
		if (v > yMax) yMax = v;
	}
	rc->x = xMin;
	rc->y = yMax;
	rc->width = xMax - xMin;
	rc->height = yMax - yMin;

	/*take care of straight line path by adding a default width if height and vice-versa*/
	if (rc->height && !rc->width) {
		rc->width = 2*FIX_ONE;
		rc->x -= FIX_ONE;
	}
	else if (!rc->height && rc->width) {
		rc->height = 2*FIX_ONE;
		rc->y += FIX_ONE;
	}
	return GF_OK;
}

/*
 *	conic bbox computing taken from freetype
 *		Copyright 1996-2001, 2002, 2004 by                                   
 *		David Turner, Robert Wilhelm, and Werner Lemberg.
 *	License: FTL or GPL
 */
static void gf_conic_check(Fixed y1, Fixed y2, Fixed y3, Fixed *min, Fixed *max)
{
	/* flat arc */
	if ((y1 <= y3) && (y2 == y1)) goto Suite;

	if ( y1 < y3 ) {
		/* ascending arc */
		if ((y2 >= y1) && (y2 <= y3)) goto Suite;
	} else {
		/* descending arc */
		if ((y2 >= y3) && (y2 <= y1)) {
			y2 = y1;
			y1 = y3;
			y3 = y2;
			goto Suite;
		}
	}
	y1 = y3 = y1 - gf_muldiv(y2 - y1, y2 - y1, y1 - 2*y2 + y3);

Suite:
	if ( y1 < *min ) *min = y1;
	if ( y3 > *max ) *max = y3;
}


/*
 *	cubic bbox computing taken from freetype
 *		Copyright 1996-2001, 2002, 2004 by                                   
 *		David Turner, Robert Wilhelm, and Werner Lemberg.
 *	License: FTL or GPL

 *	Note: we're using the decomposition method, not the equation one which is not usable with Floats (only 16.16 fixed)
*/
static void gf_cubic_check(Fixed p1, Fixed p2, Fixed p3, Fixed p4, Fixed *min, Fixed *max)
{
	Fixed stack[32*3 + 1], *arc;
	arc = stack;
	arc[0] = p1;
	arc[1] = p2;
	arc[2] = p3;
	arc[3] = p4;

	do {
		Fixed y1 = arc[0];
		Fixed y2 = arc[1];
		Fixed y3 = arc[2];
		Fixed y4 = arc[3];
		
		if ( y1 == y4 ) {
			/* flat */
			if ((y1 == y2) && (y1 == y3)) goto Test;
		}
		else if ( y1 < y4 ) {
			/* ascending */
			if ((y2 >= y1) && (y2 <= y4) && (y3 >= y1) && (y3 <= y4)) goto Test;
		} else {
			/* descending */
			if ((y2 >= y4) && (y2 <= y1) && (y3 >= y4) && (y3 <= y1)) {
				y2 = y1;
				y1 = y4;
				y4 = y2;
				goto Test;
			}
		}
		/* unknown direction -- split the arc in two */
		arc[6] = y4;
		arc[1] = y1 = ( y1 + y2 ) / 2;
		arc[5] = y4 = ( y4 + y3 ) / 2;
		y2 = ( y2 + y3 ) / 2;
		arc[2] = y1 = ( y1 + y2 ) / 2;
		arc[4] = y4 = ( y4 + y2 ) / 2;
		arc[3] = ( y1 + y4 ) / 2;

		arc += 3;
		goto Suite;

Test:
		if ( y1 < *min ) *min = y1;
		if ( y4 > *max ) *max = y4;
		arc -= 3;
Suite:
		;
	}
	while ( arc >= stack );
}


GF_EXPORT
GF_Err gf_path_get_bounds(GF_Path *gp, GF_Rect *rc)
{
	u32 i;
	GF_Point2D *pt, *end, *ctrl1, *ctrl2;
	Fixed xMin, xMax, yMin, yMax, cxMin, cxMax, cyMin, cyMax;
	if (!gp || !rc) return GF_BAD_PARAM;

	if (!(gp->flags & GF_PATH_BBOX_DIRTY)) {
		*rc = gp->bbox;
		return GF_OK;
	}
	/*no curves in path*/
	if (gp->flags & GF_PATH_FLATTENED) {
		GF_Err e;
		gp->flags &= ~GF_PATH_BBOX_DIRTY;
		e = gf_path_get_control_bounds(gp, &gp->bbox);
		*rc = gp->bbox;
		return GF_OK;