path2d.c

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

	}

	gp->flags &= ~GF_PATH_BBOX_DIRTY;

	if (!gp->n_points) {
		gp->bbox.x = gp->bbox.y = gp->bbox.width = gp->bbox.height = 0;
		*rc = gp->bbox;
		return GF_OK;
	}
	pt = gp->points;
	end = pt + gp->n_points;
	xMin = xMax = cxMin = cxMax = pt->x;
	yMin = yMax = cyMin = cyMax = pt->y;
	pt++;
	for (i=1 ; i < gp->n_points; i++ ) {
		Fixed x, y;
		x = pt->x;
		y = pt->y;
		if (x < cxMin) cxMin = x;
		if (x > cxMax) cxMax = x;
		if (y < cyMin) cyMin = y;
		if (y > cyMax) cyMax = y;
		/*point on curve, update*/
		if (gp->tags[i] & GF_PATH_CURVE_ON) {
			if (x < xMin) xMin = x;
			if (x > xMax) xMax = x;
			if (y < yMin) yMin = y;
			if (y > yMax) yMax = y;
		}
		pt++;
	}

	/*control box is bigger than box , decompose curves*/
    if ((cxMin < xMin) || (cxMax > xMax) || (cyMin < yMin) || (cyMax > yMax)) {
		/*decompose all control points*/
		pt = gp->points;
		for (i=1 ; i < gp->n_points; ) {
			switch (gp->tags[i]) {
			case GF_PATH_CURVE_ON:
			case GF_PATH_CLOSE:
				pt = &gp->points[i];
				i++;
				break;
			case GF_PATH_CURVE_CONIC:
				/*decompose*/
				ctrl1 = &gp->points[i];
				end = &gp->points[i+1];
				if ((ctrl1->x < xMin) || (ctrl1->x > xMax))
					gf_conic_check(pt->x, ctrl1->x, end->x, &xMin, &xMax);
 
				if ((ctrl1->y < yMin) || (ctrl1->y > yMax)) 
					gf_conic_check(pt->y, ctrl1->y, end->y, &yMin, &yMax);

				/*and move*/
				pt = end;
				i+=2;
				break;
			case GF_PATH_CURVE_CUBIC:
				/*decompose*/
				ctrl1 = &gp->points[i];
				ctrl2 = &gp->points[i+1];
				end = &gp->points[i+2];
				if ((ctrl1->x < xMin) || (ctrl1->x > xMax) || (ctrl2->x < xMin) || (ctrl2->x > xMax))
					gf_cubic_check(pt->x, ctrl1->x, ctrl2->x, end->x, &xMin, &xMax);
 
				if ((ctrl1->y < yMin) || (ctrl1->y > yMax) || (ctrl2->y < yMin) || (ctrl2->y > yMax)) 
					gf_cubic_check(pt->y, ctrl1->y, ctrl2->y, end->y, &yMin, &yMax);

				/*and move*/
				pt = end;
				i+=3;
				break;
			}
		}
	}
	gp->bbox.x = xMin;
	gp->bbox.y = yMax;
	gp->bbox.width = xMax - xMin;
	gp->bbox.height = yMax - yMin;
	*rc = gp->bbox;
	return GF_OK;
}

/*flattening algo taken from libart but passed to sqrt tests for line distance to avoid 16.16 fixed overflow*/
static GF_Err gf_subdivide_cubic(GF_Path *gp, Fixed x0, Fixed y0, Fixed x1, Fixed y1, Fixed x2, Fixed y2, Fixed x3, Fixed y3, Fixed fineness)
{
	GF_Point2D pt;
	Fixed x3_0, y3_0, z3_0, z1_0, z1_dot, z2_dot, z1_perp, z2_perp;
	Fixed max_perp;
	Fixed x_m, y_m, xa1, ya1, xa2, ya2, xb1, yb1, xb2, yb2;
	GF_Err e;

	pt.x = x3_0 = x3 - x0;
	pt.y = y3_0 = y3 - y0;

	/*z3_0 is dist z0-z3*/
	z3_0 = gf_v2d_len(&pt);

	pt.x = x1 - x0;
	pt.y = y1 - y0;
	z1_0 = gf_v2d_len(&pt);

	if ((z3_0 < FIX_ONE/100) && (z1_0 < FIX_ONE/100)) 
		goto nosubdivide;

	/* perp is distance from line, multiplied by dist z0-z3 */
	max_perp = gf_mulfix(fineness, z3_0);

	z1_perp = gf_mulfix((y1 - y0), x3_0) - gf_mulfix((x1 - x0), y3_0);
	if (ABS(z1_perp) > max_perp)
		goto subdivide;

	z2_perp = gf_mulfix((y3 - y2), x3_0) - gf_mulfix((x3 - x2), y3_0);
	if (ABS(z2_perp) > max_perp)
		goto subdivide;

	z1_dot = gf_mulfix((x1 - x0), x3_0) + gf_mulfix((y1 - y0), y3_0);
	if ((z1_dot < 0) && (ABS(z1_dot) > max_perp))
		goto subdivide;

	z2_dot = gf_mulfix((x3 - x2), x3_0) + gf_mulfix((y3 - y2), y3_0);
	if ((z2_dot < 0) && (ABS(z2_dot) > max_perp))
		goto subdivide;

	if (gf_divfix(z1_dot + z1_dot, z3_0) > z3_0)
		goto subdivide;

	if (gf_divfix(z2_dot + z2_dot, z3_0) > z3_0)
		goto subdivide;

nosubdivide:
	/* don't subdivide */
	return gf_path_add_line_to(gp, x3, y3);

subdivide:
	xa1 = (x0 + x1) / 2;
	ya1 = (y0 + y1) / 2;
	xa2 = (x0 + 2 * x1 + x2) / 4;
	ya2 = (y0 + 2 * y1 + y2) / 4;
	xb1 = (x1 + 2 * x2 + x3) / 4;
	yb1 = (y1 + 2 * y2 + y3) / 4;
	xb2 = (x2 + x3) / 2;
	yb2 = (y2 + y3) / 2;
	x_m = (xa2 + xb1) / 2;
	y_m = (ya2 + yb1) / 2;

	e = gf_subdivide_cubic(gp, x0, y0, xa1, ya1, xa2, ya2, x_m, y_m, fineness);
	if (e) return e;
	return gf_subdivide_cubic(gp, x_m, y_m, xb1, yb1, xb2, yb2, x3, y3, fineness);
}

GF_EXPORT
GF_Path *gf_path_get_flatten(GF_Path *gp)
{
	GF_Path *ngp;
	Fixed fineness;
	u32 i, *countour;
	GF_Point2D *pt;
	if (!gp || !gp->n_points) return NULL;

	if (gp->flags & GF_PATH_FLATTENED) return gf_path_clone(gp);

	/*avoid too high precision */
	fineness = MAX(FIX_ONE - gp->fineness, FIX_ONE / 100);

	ngp = gf_path_new();
	pt = &gp->points[0];
	gf_path_add_move_to_vec(ngp, pt);
	countour = gp->contours;
	for (i=1; i<gp->n_points; ) {
		switch (gp->tags[i]) {
		case GF_PATH_CURVE_ON:
		case GF_PATH_CLOSE:
			pt = &gp->points[i];
			if (*countour == i-1) {
				gf_path_add_move_to_vec(ngp, pt);
				countour++;
			} else {
				gf_path_add_line_to_vec(ngp, pt);
			}
			if (gp->tags[i]==GF_PATH_CLOSE) gf_path_close(ngp);
			i++;
			break;
		case GF_PATH_CURVE_CONIC:
		{
			GF_Point2D *ctl, *end, c1, c2;
			ctl = &gp->points[i];
			end = &gp->points[i+1];
			c1.x = pt->x + 2*(ctl->x - pt->x)/3;
			c1.y = pt->y + 2*(ctl->y - pt->y)/3;
			c2.x = c1.x + (end->x - pt->x) / 3;
			c2.y = c1.y + (end->y - pt->y) / 3;

			gf_subdivide_cubic(ngp, pt->x, pt->y, c1.x, c1.y, c2.x, c2.y, end->x, end->y, fineness);
			pt = end;
			if (gp->tags[i+1]==GF_PATH_CLOSE) gf_path_close(ngp);
			i+=2;
		}
			break;
		case GF_PATH_CURVE_CUBIC:
			gf_subdivide_cubic(ngp, pt->x, pt->y, gp->points[i].x, gp->points[i].y, gp->points[i+1].x, gp->points[i+1].y, gp->points[i+2].x, gp->points[i+2].y, fineness);
			pt = &gp->points[i+2];
			if (gp->tags[i+2]==GF_PATH_CLOSE) gf_path_close(ngp);
			i+=3;
			break;
		}
	}
	if (gp->flags & GF_PATH_FILL_ZERO_NONZERO) ngp->flags |= GF_PATH_FILL_ZERO_NONZERO;
	ngp->flags |= (GF_PATH_BBOX_DIRTY | GF_PATH_FLATTENED);
	return ngp;
}

GF_EXPORT
void gf_path_flatten(GF_Path *gp)
{
	GF_Path *res;
	if (gp->flags & GF_PATH_FLATTENED) return;
	if (!gp->n_points) return;
	res = gf_path_get_flatten(gp);
	if (gp->contours) free(gp->contours);
	if (gp->points) free(gp->points);
	if (gp->tags) free(gp->tags);
	memcpy(gp, res, sizeof(GF_Path));
	free(res);
}



#define isLeft(P0, P1, P2) \
	( gf_mulfix((P1.x - P0.x), (P2.y - P0.y)) - gf_mulfix((P2.x - P0.x), (P1.y - P0.y)) )


static void gf_subdivide_cubic_hit_test(Fixed h_x, Fixed h_y, Fixed x0, Fixed y0, Fixed x1, Fixed y1, Fixed x2, Fixed y2, Fixed x3, Fixed y3, s32 *wn)
{
	GF_Point2D s, e, pt;
	Fixed x_m, y_m, xa1, ya1, xa2, ya2, xb1, yb1, xb2, yb2, y_min, y_max;

	/*if hit line doesn't intersects control box abort*/
	y_min = MIN(y0, MIN(y1, MIN(y2, y3)));
	y_max = MAX(y0, MAX(y1, MAX(y2, y3)));
	if ((h_y<y_min) || (h_y>y_max) ) return;

	/*if vert diff between end points larger than 1 pixels, subdivide (we need pixel accuracy for is_over)*/
	if (y_max - y_min > FIX_ONE) {
		xa1 = (x0 + x1) / 2;
		ya1 = (y0 + y1) / 2;
		xa2 = (x0 + 2 * x1 + x2) / 4;
		ya2 = (y0 + 2 * y1 + y2) / 4;
		xb1 = (x1 + 2 * x2 + x3) / 4;
		yb1 = (y1 + 2 * y2 + y3) / 4;
		xb2 = (x2 + x3) / 2;
		yb2 = (y2 + y3) / 2;
		x_m = (xa2 + xb1) / 2;
		y_m = (ya2 + yb1) / 2;

		gf_subdivide_cubic_hit_test(h_x, h_y, x0, y0, xa1, ya1, xa2, ya2, x_m, y_m, wn);
		gf_subdivide_cubic_hit_test(h_x, h_y, x_m, y_m, xb1, yb1, xb2, yb2, x3, y3, wn);
		return;
	}

	s.x = x0;
	s.y = y0;
	e.x = x3;
	e.y = y3;
	pt.x = h_x;
	pt.y= h_y;

	if (s.y<=pt.y) {
		if (e.y>pt.y) {
			if (isLeft(s, e, pt) > 0) 
				(*wn)++;
		}
	}
	else if (e.y<=pt.y) {
		if (isLeft(s, e, pt) < 0) 
			(*wn)--;
	}
}

GF_EXPORT
Bool gf_path_point_over(GF_Path *gp, Fixed x, Fixed y)
{
	u32 i, *contour, start_idx;
	s32 wn;
	GF_Point2D start, s, e, pt;
	GF_Rect rc;

	/*check if not in bounds*/
	gf_path_get_bounds(gp, &rc);
	if ((x<rc.x) || (y>rc.y) || (x>rc.x+rc.width) || (y<rc.y-rc.height)) return 0;

	if (!gp || (gp->n_points<2)) return 0;
	
	pt.x = x;
	pt.y = y;
	wn = 0;
	s = start = gp->points[0];
	start_idx = 0;
	contour = gp->contours;
	for (i=1; i<gp->n_points; ) {
		switch (gp->tags[i]) {
		case GF_PATH_CURVE_ON:
		case GF_PATH_CLOSE:
			e = gp->points[i];
			if (s.y<=pt.y) {
				if (e.y>pt.y) {
					if (isLeft(s, e, pt) > 0) wn++;
				}
			}
			else if (e.y<=pt.y) {
				if (isLeft(s, e, pt) < 0) wn--;
			}
			s = e;
			i++;
			break;
		case GF_PATH_CURVE_CONIC:
		{
			GF_Point2D *ctl, *end, c1, c2;
			ctl = &gp->points[i];
			end = &gp->points[i+1];
			c1.x = s.x + 2*(ctl->x - s.x) / 3;
			c1.y = s.y + 2*(ctl->y - s.y) / 3;
			c2.x = c1.x + (end->x - s.x) / 3;
			c2.y = c1.y + (end->y - s.y) / 3;
			gf_subdivide_cubic_hit_test(x, y, s.x, s.y, c1.x, c1.y, c2.x, c2.y, end->x, end->y, &wn);
			s = *end;
		}
			i+=2;
			break;
		case GF_PATH_CURVE_CUBIC:
			gf_subdivide_cubic_hit_test(x, y, s.x, s.y, gp->points[i].x, gp->points[i].y, gp->points[i+1].x, gp->points[i+1].y, gp->points[i+2].x, gp->points[i+2].y, &wn);
			s = gp->points[i+2];
			i+=3;
			break;
		}
		/*end of subpath*/
		if (*contour==i-1) {
			/*close path if needed, but don't test for lines...*/
			if ((i-start_idx > 2) && (pt.y<s.y)) {
				if ((start.x != s.x) || (start.y != s.y)) {
					e = start;
					if (s.x<=pt.x) {
						if (e.y>pt.y) {
							if (isLeft(s, e, pt) > 0) wn++;
						}
					}
					else if (e.y<=pt.y) {
						if (isLeft(s, e, pt) < 0) wn--;
					}
				}
			}
			s = start = gp->points[i];
			i++;
		}
	}
	if (gp->flags & GF_PATH_FILL_ZERO_NONZERO) return wn ? 1 : 0;
	return wn%2 ? 1 : 0;
}

GF_EXPORT
Bool gf_path_is_empty(GF_Path *gp)
{
	if (gp && gp->contours) return 0;
	return 1;
}

/*iteration info*/	
typedef struct 
{
	Fixed len;
	Fixed dx, dy;
	Fixed start_x, start_y;
} IterInfo;

struct _path_iterator
{
	u32 num_seg;
	IterInfo *seg;
	Fixed length;
};

GF_EXPORT
GF_PathIterator *gf_path_iterator_new(GF_Path *gp)
{
	GF_Path *flat;
	GF_PathIterator *it;
	u32 i, j, cur;
	GF_Point2D start, end;

	GF_SAFEALLOC(it, GF_PathIterator);
	if (!it) return NULL;
	flat = gf_path_get_flatten(gp);
	if (!flat) {
		free(it);
		return NULL;
	}
	it->seg = (IterInfo *) malloc(sizeof(IterInfo) * flat->n_points);
	it->num_seg = 0;
	it->length = 0;
	cur = 0;
	for (i=0; i<flat->n_contours; i++) {
		Fixed dx, dy;
		u32 nb_pts = 1+flat->contours[i]-cur;
		start = flat->points[cur];
		for (j=1; j<nb_pts; j++) {
			end = flat->points[cur+j];
			it->seg[it->num_seg].start_x = start.x;
			it->seg[it->num_seg].start_y = start.y;
			dx = it->seg[it->num_seg].dx = end.x - start.x;
			dy = it->seg[it->num_seg].dy = end.y - start.y;
			it->seg[it->num_seg].len = gf_sqrt(gf_mulfix(dx, dx) + gf_mulfix(dy, dy));
			it->length += it->seg[it->num_seg].len;
			start = end;
			it->num_seg++;
		}
		cur += nb_pts;
	}
	gf_path_del(flat);
	return it;
}

GF_EXPORT
Fixed gf_path_iterator_get_length(GF_PathIterator *it)
{
	return it ? it->length : 0;
}

GF_EXPORT
Bool gf_path_iterator_get_transform(GF_PathIterator *path, Fixed offset, Bool follow_tangent, GF_Matrix2D *mat, Bool smooth_edges, Fixed length_after_point)
{
	GF_Matrix2D final, rot;
	Bool tang = 0;
	Fixed res, angle, angleNext;
	u32 i;
	Fixed curLen = 0;
	if (!path) return 0;

	for (i=0; i<path->num_seg; i++) {
		if (curLen + path->seg[i].len >= offset) goto found;
		curLen += path->seg[i].len;
	}
	if (!follow_tangent) return 0;
	tang = 1;
	i--;

found:
	gf_mx2d_init(final);

	res = gf_divfix(offset - curLen, path->seg[i].len);
	if (tang) res += 1;

	/*move to current point*/
	gf_mx2d_add_translation(&final, path->seg[i].start_x + gf_mulfix(path->seg[i].dx, res), path->seg[i].start_y + gf_mulfix(path->seg[i].dy, res));

	if (!path->seg[i].dx) {
		angle = GF_PI2;
	} else {
		angle = gf_acos( gf_divfix(path->seg[i].dx , path->seg[i].len) );
	}
	if (path->seg[i].dy<0) angle *= -1;

	if (smooth_edges) {
		if (offset + length_after_point > curLen + path->seg[i].len) {
			Fixed ratio = gf_divfix(curLen + path->seg[i].len-offset, length_after_point);
			if (i < path->num_seg - 1) {
				if (!path->seg[i+1].dx) {
					angleNext = GF_PI2;
				} else {
					angleNext = gf_acos( gf_divfix(path->seg[i+1].dx, path->seg[i+1].len) );
				}
				if (path->seg[i+1].dy<0) angleNext *= -1;

				if (angle<0 && angleNext>0) {
					angle = gf_mulfix(FIX_ONE-ratio, angleNext) - gf_mulfix(ratio, angle);
				} else {
					angle = gf_mulfix(ratio, angle) + gf_mulfix(FIX_ONE-ratio, angleNext);
				}
			}
		}
	}
	/*handle res=0 case for rotation (point on line join)*/
	else if (res==1) {
		if (i < path->num_seg - 1) {
			if (!path->seg[i+1].dx) {
				angleNext = GF_PI2;
			} else {
				angleNext = gf_acos( gf_divfix(path->seg[i+1].dx, path->seg[i+1].len) );
			}
			if (path->seg[i+1].dy<0) angleNext *= -1;
			angle = ( angle + angleNext) / 2;
		}
	}

	gf_mx2d_init(rot);
	gf_mx2d_add_rotation(&rot, 0, 0, angle);
	gf_mx2d_add_matrix(mat, &rot);
	gf_mx2d_add_matrix(mat, &final);
	return 1;
}

GF_EXPORT
void gf_path_iterator_del(GF_PathIterator *it)
{
	if (it->seg) free(it->seg);
	free(it);
}


#define ConvexCompare(delta)	\
    ( (delta.x > 0) ? -1 :		\
      (delta.x < 0) ?	1 :		\
      (delta.y > 0) ? -1 :		\
      (delta.y < 0) ?	1 :	\
      0 )

#define ConvexGetPointDelta(delta, pprev, pcur )			\
    /* Given a previous point 'pprev', read a new point into 'pcur' */	\
    /* and return delta in 'delta'.				    */	\
    pcur = pts[iread++];						\
    delta.x = pcur.x - pprev.x;					\
    delta.y = pcur.y - pprev.y;					\

#define ConvexCross(p, q) gf_mulfix(p.x,q.y) - gf_mulfix(p.y,q.x);

#define ConvexCheckTriple						\
    if ( (thisDir = ConvexCompare(dcur)) == -curDir ) {			\
	  ++dirChanges;							\
	  /* if ( dirChanges > 2 ) return NotConvex;		     */ \
    }									\
    curDir = thisDir;							\
    cross = ConvexCross(dprev, dcur);					\
    if ( cross > 0 ) { \
		if ( angleSign == -1 ) return GF_POLYGON_COMPLEX_CW;		\
		angleSign = 1;					\
	}							\
    else if (cross < 0) {	\
		if (angleSign == 1) return GF_POLYGON_COMPLEX_CCW;		\
		angleSign = -1;				\
	}						\
    pSecond = pThird;		\
    dprev.x = dcur.x;		\
    dprev.y = dcur.y;							\

GF_EXPORT
u32 gf_polygone2d_get_convexity(GF_Point2D *pts, u32 len)
{
	s32 curDir, thisDir = 0, dirChanges = 0, angleSign = 0;
	u32 iread;
    Fixed cross;
	GF_Point2D pSecond, pThird, pSaveSecond;
	GF_Point2D dprev, dcur;

    /* Get different point, return if less than 3 diff points. */
    if (len < 3 ) return GF_POLYGON_CONVEX_LINE;
    iread = 1;
	ConvexGetPointDelta(dprev, (pts[0]), pSecond);
    pSaveSecond = pSecond;
	/*initial direction */
    curDir = ConvexCompare(dprev);
    while ( iread < len) {
		/* Get different point, break if no more points */
		ConvexGetPointDelta(dcur, pSecond, pThird );
		if ( (dcur.x == 0) && (dcur.y == 0) ) continue;
		/* Check current three points */
		ConvexCheckTriple;
    }

    /* Must check for direction changes from last vertex back to first */
	/* Prepare for 'ConvexCheckTriple' */
    pThird = pts[0];
    dcur.x = pThird.x - pSecond.x;
    dcur.y = pThird.y - pSecond.y;
    if ( ConvexCompare(dcur) ) ConvexCheckTriple;

    /* and check for direction changes back to second vertex */
    dcur.x = pSaveSecond.x - pSecond.x;
    dcur.y = pSaveSecond.y - pSecond.y;
	/* Don't care about 'pThird' now */
    ConvexCheckTriple;			

    /* Decide on polygon type given accumulated status */
    if ( dirChanges > 2 ) return GF_POLYGON_COMPLEX;
    if ( angleSign > 0 ) return GF_POLYGON_CONVEX_CCW;
    if ( angleSign < 0 ) return GF_POLYGON_CONVEX_CW;
    return GF_POLYGON_CONVEX_LINE;
}