/***************************************************************************/

/*                                                                         */

/*  ftstroke.c                                                             */

/*                                                                         */

/*    FreeType path stroker (body).                                        */

/*                                                                         */

/*  Copyright 2002-2006, 2008-2011 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 <ft2build.h>

#include FT_STROKER_H

#include FT_TRIGONOMETRY_H

#include FT_OUTLINE_H

#include FT_INTERNAL_MEMORY_H

#include FT_INTERNAL_DEBUG_H

#include FT_INTERNAL_OBJECTS_H

  /* documentation is in ftstroke.h */

  FT_EXPORT_DEF( FT_StrokerBorder )

  FT_Outline_GetInsideBorder( FT_Outline*  outline )

  {

    FT_Orientation  o = FT_Outline_Get_Orientation( outline );

    return o == FT_ORIENTATION_TRUETYPE ? FT_STROKER_BORDER_RIGHT

                                        : FT_STROKER_BORDER_LEFT ;

  }

  /* documentation is in ftstroke.h */

  FT_EXPORT_DEF( FT_StrokerBorder )

  FT_Outline_GetOutsideBorder( FT_Outline*  outline )

  {

    FT_Orientation  o = FT_Outline_Get_Orientation( outline );

    return o == FT_ORIENTATION_TRUETYPE ? FT_STROKER_BORDER_LEFT

                                        : FT_STROKER_BORDER_RIGHT ;

  }

 /***************************************************************************/

 /***************************************************************************/

 /*****                                                                 *****/

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

 /*****                                                                 *****/

 /***************************************************************************/

 /***************************************************************************/

#define FT_SMALL_CONIC_THRESHOLD  ( FT_ANGLE_PI / 6 )

#define FT_SMALL_CUBIC_THRESHOLD  ( FT_ANGLE_PI / 6 )

#define FT_EPSILON  2

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

  static FT_Pos

  ft_pos_abs( FT_Pos  x )

  {

    return x >= 0 ? x : -x ;

  }

  static void

  ft_conic_split( FT_Vector*  base )

  {

    FT_Pos  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 FT_Bool

  ft_conic_is_small_enough( FT_Vector*  base,

                            FT_Angle   *angle_in,

                            FT_Angle   *angle_out )

  {

    FT_Vector  d1, d2;

    FT_Angle   theta;

    FT_Int     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 = FT_Atan2( d2.x, d2.y );

    }

    else if ( close2 )

    {

      *angle_in = *angle_out = FT_Atan2( d1.x, d1.y );

    }

    else

    {

      *angle_in  = FT_Atan2( d1.x, d1.y );

      *angle_out = FT_Atan2( d2.x, d2.y );

    }

    theta = ft_pos_abs( FT_Angle_Diff( *angle_in, *angle_out ) );

    return FT_BOOL( theta < FT_SMALL_CONIC_THRESHOLD );

  }

  static void

  ft_cubic_split( FT_Vector*  base )

  {

    FT_Pos  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 FT_Bool

  ft_cubic_is_small_enough( FT_Vector*  base,

                            FT_Angle   *angle_in,

                            FT_Angle   *angle_mid,

                            FT_Angle   *angle_out )

  {

    FT_Vector  d1, d2, d3;

    FT_Angle   theta1, theta2;

    FT_Int     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 = FT_Atan2( d2.x, d2.y );

        *angle_out = FT_Atan2( d3.x, d3.y );

      }

      else  /* close2 */

      {

        *angle_in  = FT_Atan2( d1.x, d1.y );

        *angle_mid = *angle_out = FT_Atan2( d2.x, d2.y );

      }

    }

    else if ( close2 )

    {

      *angle_in  = *angle_mid = FT_Atan2( d1.x, d1.y );

      *angle_out = FT_Atan2( d3.x, d3.y );

    }

    else

    {

      *angle_in  = FT_Atan2( d1.x, d1.y );

      *angle_mid = FT_Atan2( d2.x, d2.y );

      *angle_out = FT_Atan2( d3.x, d3.y );

    }

    theta1 = ft_pos_abs( FT_Angle_Diff( *angle_in,  *angle_mid ) );

    theta2 = ft_pos_abs( FT_Angle_Diff( *angle_mid, *angle_out ) );

    return FT_BOOL( theta1 < FT_SMALL_CUBIC_THRESHOLD &&

                    theta2 < FT_SMALL_CUBIC_THRESHOLD );

  }

 /***************************************************************************/

 /***************************************************************************/

 /*****                                                                 *****/

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

 /*****                                                                 *****/

 /***************************************************************************/

 /***************************************************************************/

  typedef enum  FT_StrokeTags_

  {

    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;

#define  FT_STROKE_TAG_BEGIN_END  (FT_STROKE_TAG_BEGIN|FT_STROKE_TAG_END)

  typedef struct  FT_StrokeBorderRec_

  {

    FT_UInt     num_points;

    FT_UInt     max_points;

    FT_Vector*  points;

    FT_Byte*    tags;

    FT_Bool     movable;

    FT_Int      start;    /* index of current sub-path start point */

    FT_Memory   memory;

    FT_Bool     valid;

  } FT_StrokeBorderRec, *FT_StrokeBorder;

  static FT_Error

  ft_stroke_border_grow( FT_StrokeBorder  border,

                         FT_UInt          new_points )

  {

    FT_UInt   old_max = border->max_points;

    FT_UInt   new_max = border->num_points + new_points;

    FT_Error  error   = FT_Err_Ok;

    if ( new_max > old_max )

    {

      FT_UInt    cur_max = old_max;

      FT_Memory  memory  = border->memory;

      while ( cur_max < new_max )

        cur_max += ( cur_max >> 1 ) + 16;

      if ( FT_RENEW_ARRAY( border->points, old_max, cur_max ) ||

           FT_RENEW_ARRAY( border->tags,   old_max, cur_max ) )

        goto Exit;

      border->max_points = cur_max;

    }

  Exit:

    return error;

  }

  static void

  ft_stroke_border_close( FT_StrokeBorder  border,

                          FT_Bool          reverse )

  {

    FT_UInt  start = border->start;

    FT_UInt  count = border->num_points;

    FT_ASSERT( border->start >= 0 );

    /* don't record empty paths! */

    if ( count <= start + 1U )

      border->num_points = start;

    else

    {

      /* copy the last point to the start of this sub-path, since */

      /* it contains the `adjusted' starting coordinates          */

      border->num_points    = --count;

      border->points[start] = border->points[count];

      if ( reverse )

      {

        /* reverse the points */

        {

          FT_Vector*  vec1 = border->points + start + 1;

          FT_Vector*  vec2 = border->points + count - 1;

          for ( ; vec1 < vec2; vec1++, vec2-- )

          {

            FT_Vector  tmp;

            tmp   = *vec1;

            *vec1 = *vec2;

            *vec2 = tmp;

          }

        }

        /* then the tags */

        {

          FT_Byte*  tag1 = border->tags + start + 1;

          FT_Byte*  tag2 = border->tags + count - 1;

          for ( ; tag1 < tag2; tag1++, tag2-- )

          {

            FT_Byte  tmp;

            tmp   = *tag1;

            *tag1 = *tag2;

            *tag2 = tmp;

          }

        }

      }

      border->tags[start    ] |= FT_STROKE_TAG_BEGIN;

      border->tags[count - 1] |= FT_STROKE_TAG_END;

    }

    border->start   = -1;

    border->movable = FALSE;

  }

  static FT_Error

  ft_stroke_border_lineto( FT_StrokeBorder  border,

                           FT_Vector*       to,

                           FT_Bool          movable )

  {

    FT_Error  error = FT_Err_Ok;

    FT_ASSERT( border->start >= 0 );

    if ( border->movable )

    {

      /* move last point */

      border->points[border->num_points - 1] = *to;

    }

    else

    {

      /* add one point */

      error = ft_stroke_border_grow( border, 1 );

      if ( !error )

      {

        FT_Vector*  vec = border->points + border->num_points;

        FT_Byte*    tag = border->tags   + border->num_points;

        vec[0] = *to;

        tag[0] = FT_STROKE_TAG_ON;

        border->num_points += 1;

      }

    }

    border->movable = movable;

    return error;

  }

  static FT_Error

  ft_stroke_border_conicto( FT_StrokeBorder  border,

                            FT_Vector*       control,

                            FT_Vector*       to )

  {

    FT_Error  error;

    FT_ASSERT( border->start >= 0 );

    error = ft_stroke_border_grow( border, 2 );

    if ( !error )

    {

      FT_Vector*  vec = border->points + border->num_points;

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

    }

    border->movable = FALSE;

    return error;

  }

  static FT_Error

  ft_stroke_border_cubicto( FT_StrokeBorder  border,

                            FT_Vector*       control1,

                            FT_Vector*       control2,

                            FT_Vector*       to )

  {

    FT_Error  error;

    FT_ASSERT( border->start >= 0 );

    error = ft_stroke_border_grow( border, 3 );

    if ( !error )

    {

      FT_Vector*  vec = border->points + border->num_points;

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

    }

    border->movable = FALSE;

    return error;

  }

#define FT_ARC_CUBIC_ANGLE  ( FT_ANGLE_PI / 2 )

  static FT_Error

  ft_stroke_border_arcto( FT_StrokeBorder  border,

                          FT_Vector*       center,

                          FT_Fixed         radius,

                          FT_Angle         angle_start,

                          FT_Angle         angle_diff )

  {

    FT_Angle   total, angle, step, rotate, next, theta;

    FT_Vector  a, b, a2, b2;

    FT_Fixed   length;

    FT_Error   error = FT_Err_Ok;

    /* compute start point */

    FT_Vector_From_Polar( &a, radius, angle_start );

    a.x += center->x;

    a.y += center->y;

    total  = angle_diff;

    angle  = angle_start;

    rotate = ( angle_diff >= 0 ) ? FT_ANGLE_PI2 : -FT_ANGLE_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;

      theta >>= 1;

      /* compute end point */

      FT_Vector_From_Polar( &b, radius, next );

      b.x += center->x;

      b.y += center->y;

      /* compute first and second control points */

      length = FT_MulDiv( radius, FT_Sin( theta ) * 4,

                          ( 0x10000L + FT_Cos( theta ) ) * 3 );

      FT_Vector_From_Polar( &a2, length, angle + rotate );

      a2.x += a.x;

      a2.y += a.y;

      FT_Vector_From_Polar( &b2, length, next - rotate );

      b2.x += b.x;

      b2.y += b.y;

      /* add cubic arc */

      error = ft_stroke_border_cubicto( border, &a2, &b2, &b );

      if ( error )

        break;

      /* process the rest of the arc ?? */

      a      = b;

      total -= step;

      angle  = next;

    }

    return error;

  }

  static FT_Error

  ft_stroke_border_moveto( FT_StrokeBorder  border,

                           FT_Vector*       to )

  {

    /* close current open path if any ? */