/*

 *      GPAC - Multimedia Framework C SDK

 *

 *      Authors: Jean Le Feuvre

 *      Copyright (c) Telecom ParisTech 2000-2023

 *          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>

#if !defined(GPAC_DISABLE_EVG) || defined(GPAC_HAS_FREETYPE)

GF_EXPORT

GF_Path *gf_path_new()

{

  GF_Path *gp;

  GF_SAFEALLOC(gp, GF_Path);

  if (!gp) return NULL;

  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) gf_free(gp->contours);

  if (gp->tags) gf_free(gp->tags);

  if (gp->points) gf_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 *)gf_malloc(sizeof(u32)*gp->n_contours);

  if (!dst->contours) {

    gf_free(dst);

    return NULL;

  }

  dst->points = (GF_Point2D *) gf_malloc(sizeof(GF_Point2D)*gp->n_points);

  if (!dst->points) {

    gf_free(dst->contours);

    gf_free(dst);

    return NULL;

  }

  dst->tags = (u8 *) gf_malloc(sizeof(u8)*gp->n_points);

  if (!dst->tags) {

    gf_free(dst->points);

    gf_free(dst->contours);

    gf_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) gf_free(gp->contours);

  if (gp->tags) gf_free(gp->tags);

  if (gp->points) gf_free(gp->points);

  gf_free(gp);

}

#define GF_2D_REALLOC(_gp)  \

  if (_gp->n_alloc_points < _gp->n_points+3) { \

    _gp->n_alloc_points = (_gp->n_alloc_points<5) ? 10 : (_gp->n_alloc_points*2); \

    _gp->points = (GF_Point2D *)gf_realloc(_gp->points, sizeof(GF_Point2D)*(_gp->n_alloc_points));  \

    _gp->tags = (u8 *) gf_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 0

  /*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;

  }

#endif

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

  GF_2D_REALLOC(gp)

  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(gp)

  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)

{

  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;

  if (FIX_ONE/100 < ABS(end.x) || FIX_ONE/100 < ABS(end.y)) {

    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(gp)

  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(gp)

  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+a_axis, cy);

  if (e) return e;

  for (i=1; i<GF_2D_DEFAULT_RES; i++) {

    cur = 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);

}

GF_Err gf_path_add_subpath(GF_Path *gp, GF_Path *src, GF_Matrix2D *mx)

{

  u32 i;

  if (!src) return GF_OK;

  gp->contours = (u32*)gf_realloc(gp->contours, sizeof(u32) * (gp->n_contours + src->n_contours));

  if (!gp->contours) return GF_OUT_OF_MEM;

  for (i=0; i<src->n_contours; i++) {

    gp->contours[i+gp->n_contours] = src->contours[i] + gp->n_points;

  }

  gp->n_contours += src->n_contours;

  gp->n_alloc_points += src->n_alloc_points;

  gp->points = (GF_Point2D*)gf_realloc(gp->points, sizeof(GF_Point2D)*gp->n_alloc_points);

  if (!gp->points) return GF_OUT_OF_MEM;

  gp->tags = (u8*)gf_realloc(gp->tags, sizeof(u8)*gp->n_alloc_points);

  if (!gp->tags) return GF_OUT_OF_MEM;

  if (src->n_points) {

    memcpy(gp->points + gp->n_points, src->points, sizeof(GF_Point2D)*src->n_points);

    if (mx) {

      for (i=0; i<src->n_points; i++) {

        gf_mx2d_apply_coords(mx, &gp->points[i+gp->n_points].x, &gp->points[i+gp->n_points].y);

      }

    }

    memcpy(gp->tags + gp->n_points, src->tags, sizeof(u8)*src->n_points);

    gp->n_points += src->n_points;

  }

  gf_rect_union(&gp->bbox, &src->bbox);

  if (!(src->flags & GF_PATH_FLATTENED)) gp->flags &= ~GF_PATH_FLATTENED;

  if (src->flags & GF_PATH_BBOX_DIRTY) gp->flags |= GF_PATH_BBOX_DIRTY;

  return GF_OK;

}

/*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 end;

  numPoints = (u32) FIX2INT(GF_2D_DEFAULT_RES * gp->fineness);

  mu = 0.0;

  if (numPoints) mu = 1/(Double)numPoints;

  for (i=1; i<numPoints; i++) {

    NBezier(newpts, nbPoints - 1, i*mu, &end);

    gf_path_add_line_to(gp, end.x, end.y);

  }

  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 *) gf_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);

  gf_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_svg_arc_to(GF_Path *gp, Fixed end_x, Fixed end_y, Fixed r_x, Fixed r_y, Fixed x_axis_rotation, Bool large_arc_flag, Bool sweep_flag)

{

  Fixed start_x, start_y;

  Fixed xmid,ymid;

  Fixed xmidp,ymidp;

  Fixed xmidpsq,ymidpsq;

  Fixed phi, cos_phi, sin_phi;

  Fixed c_x, c_y;

  Fixed cxp, cyp;

  Fixed scale;

  Fixed rxsq, rysq;

  Fixed start_angle, sweep_angle;

  Fixed radius_scale;

  Fixed vx, vy, normv;

  Fixed ux, uy, normu;

  Fixed sign;

  u32 i, num_steps;

  if (!gp->n_points) return GF_BAD_PARAM;

  if (!r_x || !r_y) {

    gf_path_add_line_to(gp, end_x, end_y);

    return GF_OK;

  }

  if (r_x < 0) r_x = -r_x;

  if (r_y < 0) r_y = -r_y;

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

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

  phi = gf_mulfix(x_axis_rotation/180, GF_PI);

  cos_phi = gf_cos(phi);

  sin_phi = gf_sin(phi);

  xmid = (start_x - end_x)/2;

  ymid = (start_y - end_y)/2;

  if (!xmid && !ymid) {

    gf_path_add_line_to(gp, end_x, end_y);

    return GF_OK;

  }

  xmidp = gf_mulfix(cos_phi, xmid) + gf_mulfix(sin_phi, ymid);

  ymidp = gf_mulfix(-sin_phi, xmid) + gf_mulfix(cos_phi, ymid);

  xmidpsq = gf_mulfix(xmidp, xmidp);

  ymidpsq = gf_mulfix(ymidp, ymidp);

  rxsq = gf_mulfix(r_x, r_x);

  rysq = gf_mulfix(r_y, r_y);

  gf_assert(rxsq && rysq);

  radius_scale = gf_divfix(xmidpsq, rxsq) + gf_divfix(ymidpsq, rysq);

  if (radius_scale > FIX_ONE) {

    r_x = gf_mulfix(gf_sqrt(radius_scale), r_x);

    r_y = gf_mulfix(gf_sqrt(radius_scale), r_y);

    rxsq = gf_mulfix(r_x, r_x);

    rysq = gf_mulfix(r_y, r_y);

  }

#if 0

  /* Old code with overflow problems in fixed point,

     sign was sometimes negative (cf tango SVG icons appointment-new.svg)*/

  sign = gf_mulfix(rxsq,ymidpsq) + gf_mulfix(rysq, xmidpsq);

  scale = FIX_ONE;

  /*FIXME - what if scale is 0 ??*/

  if (sign) scale = gf_divfix(

                          (gf_mulfix(rxsq,rysq) - gf_mulfix(rxsq, ymidpsq) - gf_mulfix(rysq,xmidpsq)),

                          sign

                      );

#else

  /* New code: the sign variable computation is split into simpler cases and

     the expression is divided by rxsq to reduce the range */

  if ((rxsq == 0 || ymidpsq ==0) && (rysq == 0 || xmidpsq == 0)) {

    scale = FIX_ONE;

  } else if (rxsq == 0 || ymidpsq ==0) {

    scale = gf_divfix(rxsq,xmidpsq) - FIX_ONE;

  } else if (rysq == 0 || xmidpsq == 0) {

    scale = gf_divfix(rysq,ymidpsq) - FIX_ONE;

  } else {

    Fixed tmp;

    tmp = gf_mulfix(gf_divfix(rysq, rxsq), xmidpsq);

    sign = ymidpsq + tmp;

    scale = gf_divfix((rysq - ymidpsq - tmp),sign);

  }

#endif

  /* precision problem may lead to negative value around zero, we need to take care of it before sqrt */

  scale = gf_sqrt(ABS(scale));

  cxp = gf_mulfix(scale, gf_divfix(gf_mulfix(r_x, ymidp),r_y));

  cyp = gf_mulfix(scale, -gf_divfix(gf_mulfix(r_y, xmidp),r_x));

  cxp = (large_arc_flag == sweep_flag ? - cxp : cxp);

  cyp = (large_arc_flag == sweep_flag ? - cyp : cyp);

  c_x = gf_mulfix(cos_phi, cxp) - gf_mulfix(sin_phi, cyp) + (start_x + end_x)/2;

  c_y = gf_mulfix(sin_phi, cxp) + gf_mulfix(cos_phi, cyp) + (start_y + end_y)/2;

  vx = gf_divfix(xmidp-cxp,r_x);

  vy = gf_divfix(ymidp-cyp,r_y);

  normv = gf_sqrt(gf_mulfix(vx, vx) + gf_mulfix(vy,vy));

  sign = vy;

  start_angle = gf_acos(gf_divfix(vx,normv));

  start_angle = (sign > 0 ? start_angle: -start_angle);

  ux = vx;

  uy = vy;

  vx = gf_divfix(-xmidp-cxp,r_x);

  vy = gf_divfix(-ymidp-cyp,r_y);

  normu = gf_sqrt(gf_mulfix(ux, ux) + gf_mulfix(uy,uy));

  sign = gf_mulfix(ux, vy) - gf_mulfix(uy, vx);

  sweep_angle = gf_divfix( gf_mulfix(ux,vx) + gf_mulfix(uy, vy), gf_mulfix(normu, normv) );

  /*numerical stability safety*/

  sweep_angle = MAX(-FIX_ONE, MIN(sweep_angle, FIX_ONE));

  sweep_angle = gf_acos(sweep_angle);

  sweep_angle = (sign > 0 ? sweep_angle: -sweep_angle);

  if (sweep_flag == 0) {

    if (sweep_angle > 0) sweep_angle -= GF_2PI;

  } else {

    if (sweep_angle < 0) sweep_angle += GF_2PI;

  }

  num_steps = GF_2D_DEFAULT_RES/2;

  for (i=1; i<=num_steps; i++) {

    Fixed _vx, _vy;

    Fixed _vxp, _vyp;

    Fixed angle = start_angle + sweep_angle*(s32)i/(s32)num_steps;

    _vx = gf_mulfix(r_x, gf_cos(angle));

    _vy = gf_mulfix(r_y, gf_sin(angle));

    _vxp = gf_mulfix(cos_phi, _vx) - gf_mulfix(sin_phi, _vy) + c_x;

    _vyp = gf_mulfix(sin_phi, _vx) + gf_mulfix(cos_phi, _vy) + c_y;

    gf_path_add_line_to(gp, _vxp, _vyp);

  }

  return GF_OK;

}

GF_EXPORT

GF_Err gf_path_add_arc(GF_Path *gp, Fixed radius, Fixed start_angle, Fixed end_angle, GF_Path2DArcCloseType 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==GF_PATH2D_ARC_PIE) {

    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!=GF_PATH2D_ARC_OPEN) 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;

#if 0

  /*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;

  }

#endif

  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 (ABS(y1)<FIX_EPSILON) arc[0] = y1 = 0;

    if (ABS(y2)<FIX_EPSILON) arc[1] = y2 = 0;

    if (ABS(y3)<FIX_EPSILON) arc[2] = y3 = 0;

    if (ABS(y4)<FIX_EPSILON) arc[3] = y4 = 0;

    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;

  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 e;

  }

  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;

  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)) {

    GF_Point2D *ctrl1, *ctrl2;

    /*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))