/***************************************************************************//*                                                                         *//*  ftbbox.c                                                               *//*                                                                         *//*    FreeType bbox computation (body).                                    *//*                                                                         *//*  Copyright 1996-2001, 2002 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.                                        *//*                                                                         *//***************************************************************************/  /*************************************************************************/  /*                                                                       */  /* This component has a _single_ role: to compute exact outline bounding */  /* boxes.                                                                */  /*                                                                       */  /*************************************************************************/#include <ft2build.h>#include FT_BBOX_H#include FT_IMAGE_H#include FT_OUTLINE_H#include FT_INTERNAL_CALC_H  typedef struct  TBBox_Rec_  {    FT_Vector  last;    FT_BBox    bbox;  } TBBox_Rec;  /*************************************************************************/  /*                                                                       */  /* <Function>                                                            */  /*    BBox_Move_To                                                       */  /*                                                                       */  /* <Description>                                                         */  /*    This function is used as a `move_to' and `line_to' emitter during  */  /*    FT_Outline_Decompose().  It simply records the destination point   */  /*    in `user->last'; no further computations are necessary since we    */  /*    the cbox as the starting bbox which must be refined.               */  /*                                                                       */  /* <Input>                                                               */  /*    to   :: A pointer to the destination vector.                       */  /*                                                                       */  /* <InOut>                                                               */  /*    user :: A pointer to the current walk context.                     */  /*                                                                       */  /* <Return>                                                              */  /*    Always 0.  Needed for the interface only.                          */  /*                                                                       */  static int  BBox_Move_To( FT_Vector*  to,                TBBox_Rec*  user )  {    user->last = *to;    return 0;  }#define CHECK_X( p, bbox )  \          ( p->x < bbox.xMin || p->x > bbox.xMax )#define CHECK_Y( p, bbox )  \          ( p->y < bbox.yMin || p->y > bbox.yMax )  /*************************************************************************/  /*                                                                       */  /* <Function>                                                            */  /*    BBox_Conic_Check                                                   */  /*                                                                       */  /* <Description>                                                         */  /*    Finds the extrema of a 1-dimensional conic Bezier curve and update */  /*    a bounding range.  This version uses direct computation, as it     */  /*    doesn't need square roots.                                         */  /*                                                                       */  /* <Input>                                                               */  /*    y1  :: The start coordinate.                                       */  /*    y2  :: The coordinate of the control point.                        */  /*    y3  :: The end coordinate.                                         */  /*                                                                       */  /* <InOut>                                                               */  /*    min :: The address of the current minimum.                         */  /*    max :: The address of the current maximum.                         */  /*                                                                       */  static void  BBox_Conic_Check( FT_Pos   y1,                    FT_Pos   y2,                          FT_Pos   y3,                          FT_Pos*  min,                          FT_Pos*  max )  {    if ( y1 <= y3 )    {      if ( y2 == y1 )               /* Flat arc */        goto Suite;    }    else if ( y1 < y3 )    {      if ( y2 >= y1 && y2 <= y3 )   /* Ascending arc */        goto Suite;    }    else    {      if ( y2 >= y3 && y2 <= y1 )   /* Descending arc */      {        y2 = y1;        y1 = y3;        y3 = y2;        goto Suite;      }    }    y1 = y3 = y1 - FT_MulDiv( y2 - y1, y2 - y1, y1 - 2*y2 + y3 );  Suite:    if ( y1 < *min ) *min = y1;    if ( y3 > *max ) *max = y3;  }  /*************************************************************************/  /*                                                                       */  /* <Function>                                                            */  /*    BBox_Conic_To                                                      */  /*                                                                       */  /* <Description>                                                         */  /*    This function is used as a `conic_to' emitter during               */  /*    FT_Raster_Decompose().  It checks a conic Bezier curve with the    */  /*    current bounding box, and computes its extrema if necessary to     */  /*    update it.                                                         */  /*                                                                       */  /* <Input>                                                               */  /*    control :: A pointer to a control point.                           */  /*    to      :: A pointer to the destination vector.                    */  /*                                                                       */  /* <InOut>                                                               */  /*    user    :: The address of the current walk context.                */  /*                                                                       */  /* <Return>                                                              */  /*    Always 0.  Needed for the interface only.                          */  /*                                                                       */  /* <Note>                                                                */  /*    In the case of a non-monotonous arc, we compute directly the       */  /*    extremum coordinates, as it is sufficiently fast.                  */  /*                                                                       */  static int  BBox_Conic_To( FT_Vector*  control,                 FT_Vector*  to,                 TBBox_Rec*  user )  {    /* we don't need to check `to' since it is always an `on' point, thus */    /* within the bbox                                                    */    if ( CHECK_X( control, user->bbox ) )      BBox_Conic_Check( user->last.x,                        control->x,                        to->x,                        &user->bbox.xMin,                        &user->bbox.xMax );    if ( CHECK_Y( control, user->bbox ) )      BBox_Conic_Check( user->last.y,                        control->y,                        to->y,                        &user->bbox.yMin,                        &user->bbox.yMax );    user->last = *to;    return 0;  }  /*************************************************************************/  /*                                                                       */  /* <Function>                                                            */  /*    BBox_Cubic_Check                                                   */  /*                                                                       */  /* <Description>                                                         */  /*    Finds the extrema of a 1-dimensional cubic Bezier curve and        */  /*    updates a bounding range.  This version uses splitting because we  */  /*    don't want to use square roots and extra accuracies.               */  /*                                                                       */  /* <Input>                                                               */  /*    p1  :: The start coordinate.                                       */  /*    p2  :: The coordinate of the first control point.                  */  /*    p3  :: The coordinate of the second control point.                 */  /*    p4  :: The end coordinate.                                         */  /*                                                                       */  /* <InOut>                                                               */  /*    min :: The address of the current minimum.                         */  /*    max :: The address of the current maximum.                         */  /*                                                                       */#if 0  static void  BBox_Cubic_Check( FT_Pos   p1,                    FT_Pos   p2,                    FT_Pos   p3,                    FT_Pos   p4,                    FT_Pos*  min,                    FT_Pos*  max )  {    FT_Pos  stack[32*3 + 1], *arc;    arc = stack;    arc[0] = p1;    arc[1] = p2;    arc[2] = p3;    arc[3] = p4;    do    {      FT_Pos  y1 = arc[0];      FT_Pos  y2 = arc[1];      FT_Pos  y3 = arc[2];      FT_Pos  y4 = arc[3];      if ( y1 == y4 )      {        if ( y1 == y2 && y1 == y3 )                         /* Flat */          goto Test;      }      else if ( y1 < y4 )      {        if ( y2 >= y1 && y2 <= y4 && y3 >= y1 && y3 <= y4 ) /* Ascending */          goto Test;      }      else      {        if ( y2 >= y4 && y2 <= y1 && y3 >= y4 && y3 <= y1 ) /* Descending */        {          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 );  }#else  static void  test_cubic_extrema( FT_Pos    y1,                      FT_Pos    y2,                      FT_Pos    y3,                      FT_Pos    y4,                      FT_Fixed  u,                      FT_Pos*   min,                      FT_Pos*   max )  { /* FT_Pos    a = y4 - 3*y3 + 3*y2 - y1; */    FT_Pos    b = y3 - 2*y2 + y1;    FT_Pos    c = y2 - y1;    FT_Pos    d = y1;    FT_Pos    y;    FT_Fixed  uu;    FT_UNUSED ( y4 );    /* The polynom is                       */    /*                                      */    /*   a*x^3 + 3b*x^2 + 3c*x + d      .   */    /*                                      */    /* However, we also have                */    /*                                      */    /*   dP/dx(u) = 0       ,               */    /*                                      */    /* which implies that                   */    /*                                      */    /*   P(u) = b*u^2 + 2c*u + d            */    if ( u > 0 && u < 0x10000L )    {      uu = FT_MulFix( u, u );      y  = d + FT_MulFix( c, 2*u ) + FT_MulFix( b, uu );      if ( y < *min ) *min = y;      if ( y > *max ) *max = y;    }  }  static void  BBox_Cubic_Check( FT_Pos   y1,                    FT_Pos   y2,                    FT_Pos   y3,                    FT_Pos   y4,                    FT_Pos*  min,