src/base/ftbbox.c

   1 /***************************************************************************/
   2 /*                                                                         */
   3 /*  ftbbox.c                                                               */
   4 /*                                                                         */
   5 /*    FreeType bbox computation (body).                                    */
   6 /*                                                                         */
   7 /*  Copyright 1996-2002, 2004, 2006, 2010, 2013, 2014 by                   */
   8 /*  David Turner, Robert Wilhelm, and Werner Lemberg.                      */
   9 /*                                                                         */
  10 /*  This file is part of the FreeType project, and may only be used        */
  11 /*  modified and distributed under the terms of the FreeType project       */
  12 /*  license, LICENSE.TXT.  By continuing to use, modify, or distribute     */
  13 /*  this file you indicate that you have read the license and              */
  14 /*  understand and accept it fully.                                        */
  15 /*                                                                         */
  16 /***************************************************************************/
  17
  18
  19   /*************************************************************************/
  20   /*                                                                       */
  21   /* This component has a _single_ role: to compute exact outline bounding */
  22   /* boxes.                                                                */
  23   /*                                                                       */
  24   /*************************************************************************/
  25
  26
  27 #include <ft2build.h>
  28 #include FT_INTERNAL_DEBUG_H
  29
  30 #include FT_BBOX_H
  31 #include FT_IMAGE_H
  32 #include FT_OUTLINE_H
  33 #include FT_INTERNAL_CALC_H
  34 #include FT_INTERNAL_OBJECTS_H
  35
  36
  37   typedef struct  TBBox_Rec_
  38   {
  39     FT_Vector  last;
  40     FT_BBox    bbox;
  41
  42   } TBBox_Rec;
  43
  44
  45 #define FT_UPDATE_BBOX( p, bbox ) \
  46   FT_BEGIN_STMNT                  \
  47     if ( p->x < bbox.xMin )       \
  48       bbox.xMin = p->x;           \
  49     if ( p->x > bbox.xMax )       \
  50       bbox.xMax = p->x;           \
  51     if ( p->y < bbox.yMin )       \
  52       bbox.yMin = p->y;           \
  53     if ( p->y > bbox.yMax )       \
  54       bbox.yMax = p->y;           \
  55   FT_END_STMNT
  56
  57 #define CHECK_X( p, bbox )                         \
  58           ( p->x < bbox.xMin || p->x > bbox.xMax )
  59
  60 #define CHECK_Y( p, bbox )                         \
  61           ( p->y < bbox.yMin || p->y > bbox.yMax )
  62
  63
  64   /*************************************************************************/
  65   /*                                                                       */
  66   /* <Function>                                                            */
  67   /*    BBox_Move_To                                                       */
  68   /*                                                                       */
  69   /* <Description>                                                         */
  70   /*    This function is used as a `move_to' emitter during                */
  71   /*    FT_Outline_Decompose().  It simply records the destination point   */
  72   /*    in `user->last'. We also update bbox in case contour starts with   */
  73   /*    an implicit `on' point.                                            */
  74   /*                                                                       */
  75   /* <Input>                                                               */
  76   /*    to   :: A pointer to the destination vector.                       */
  77   /*                                                                       */
  78   /* <InOut>                                                               */
  79   /*    user :: A pointer to the current walk context.                     */
  80   /*                                                                       */
  81   /* <Return>                                                              */
  82   /*    Always 0.  Needed for the interface only.                          */
  83   /*                                                                       */
  84   static int
  85   BBox_Move_To( FT_Vector*  to,
  86                 TBBox_Rec*  user )
  87   {
  88     FT_UPDATE_BBOX( to, user->bbox );
  89
  90     user->last = *to;
  91
  92     return 0;
  93   }
  94
  95
  96   /*************************************************************************/
  97   /*                                                                       */
  98   /* <Function>                                                            */
  99   /*    BBox_Line_To                                                       */
 100   /*                                                                       */
 101   /* <Description>                                                         */
 102   /*    This function is used as a `line_to' emitter during                */
 103   /*    FT_Outline_Decompose().  It simply records the destination point   */
 104   /*    in `user->last'; no further computations are necessary because     */
 105   /*    bbox already contains both explicit ends of the line segment.      */
 106   /*                                                                       */
 107   /* <Input>                                                               */
 108   /*    to   :: A pointer to the destination vector.                       */
 109   /*                                                                       */
 110   /* <InOut>                                                               */
 111   /*    user :: A pointer to the current walk context.                     */
 112   /*                                                                       */
 113   /* <Return>                                                              */
 114   /*    Always 0.  Needed for the interface only.                          */
 115   /*                                                                       */
 116   static int
 117   BBox_Line_To( FT_Vector*  to,
 118                 TBBox_Rec*  user )
 119   {
 120     user->last = *to;
 121
 122     return 0;
 123   }
 124
 125
 126   /*************************************************************************/
 127   /*                                                                       */
 128   /* <Function>                                                            */
 129   /*    BBox_Conic_Check                                                   */
 130   /*                                                                       */
 131   /* <Description>                                                         */
 132   /*    Find the extrema of a 1-dimensional conic Bezier curve and update  */
 133   /*    a bounding range.  This version uses direct computation, as it     */
 134   /*    doesn't need square roots.                                         */
 135   /*                                                                       */
 136   /* <Input>                                                               */
 137   /*    y1  :: The start coordinate.                                       */
 138   /*                                                                       */
 139   /*    y2  :: The coordinate of the control point.                        */
 140   /*                                                                       */
 141   /*    y3  :: The end coordinate.                                         */
 142   /*                                                                       */
 143   /* <InOut>                                                               */
 144   /*    min :: The address of the current minimum.                         */
 145   /*                                                                       */
 146   /*    max :: The address of the current maximum.                         */
 147   /*                                                                       */
 148   static void
 149   BBox_Conic_Check( FT_Pos   y1,
 150                     FT_Pos   y2,
 151                     FT_Pos   y3,
 152                     FT_Pos*  min,
 153                     FT_Pos*  max )
 154   {
 155     /* This function is only called when a control off-point is outside */
 156     /* the bbox that contains all on-points.  It finds a local extremum */
 157     /* within the segment, equal to (y1*y3 - y2*y2)/(y1 - 2*y2 + y3).   */
 158     /* Or, offsetting from y2, we get                                   */
 159
 160     y1 -= y2;
 161     y3 -= y2;
 162     y2 += FT_MulDiv( y1, y3, y1 + y3 );
 163
 164     if ( y2 < *min )
 165       *min = y2;
 166     if ( y2 > *max )
 167       *max = y2;
 168   }
 169
 170
 171   /*************************************************************************/
 172   /*                                                                       */
 173   /* <Function>                                                            */
 174   /*    BBox_Conic_To                                                      */
 175   /*                                                                       */
 176   /* <Description>                                                         */
 177   /*    This function is used as a `conic_to' emitter during               */
 178   /*    FT_Outline_Decompose().  It checks a conic Bezier curve with the   */
 179   /*    current bounding box, and computes its extrema if necessary to     */
 180   /*    update it.                                                         */
 181   /*                                                                       */
 182   /* <Input>                                                               */
 183   /*    control :: A pointer to a control point.                           */
 184   /*                                                                       */
 185   /*    to      :: A pointer to the destination vector.                    */
 186   /*                                                                       */
 187   /* <InOut>                                                               */
 188   /*    user    :: The address of the current walk context.                */
 189   /*                                                                       */
 190   /* <Return>                                                              */
 191   /*    Always 0.  Needed for the interface only.                          */
 192   /*                                                                       */
 193   /* <Note>                                                                */
 194   /*    In the case of a non-monotonous arc, we compute directly the       */
 195   /*    extremum coordinates, as it is sufficiently fast.                  */
 196   /*                                                                       */
 197   static int
 198   BBox_Conic_To( FT_Vector*  control,
 199                  FT_Vector*  to,
 200                  TBBox_Rec*  user )
 201   {
 202     /* in case `to' is implicit and not included in bbox yet */
 203     FT_UPDATE_BBOX( to, user->bbox );
 204
 205     if ( CHECK_X( control, user->bbox ) )
 206       BBox_Conic_Check( user->last.x,
 207                         control->x,
 208                         to->x,
 209                         &user->bbox.xMin,
 210                         &user->bbox.xMax );
 211
 212     if ( CHECK_Y( control, user->bbox ) )
 213       BBox_Conic_Check( user->last.y,
 214                         control->y,
 215                         to->y,
 216                         &user->bbox.yMin,
 217                         &user->bbox.yMax );
 218
 219     user->last = *to;
 220
 221     return 0;
 222   }
 223
 224
 225   /*************************************************************************/
 226   /*                                                                       */
 227   /* <Function>                                                            */
 228   /*    BBox_Cubic_Check                                                   */
 229   /*                                                                       */
 230   /* <Description>                                                         */
 231   /*    Find the extrema of a 1-dimensional cubic Bezier curve and         */
 232   /*    update a bounding range.  This version uses iterative splitting    */
 233   /*    because it is faster than the exact solution with square roots.    */
 234   /*                                                                       */
 235   /* <Input>                                                               */
 236   /*    p1  :: The start coordinate.                                       */
 237   /*                                                                       */
 238   /*    p2  :: The coordinate of the first control point.                  */
 239   /*                                                                       */
 240   /*    p3  :: The coordinate of the second control point.                 */
 241   /*                                                                       */
 242   /*    p4  :: The end coordinate.                                         */
 243   /*                                                                       */
 244   /* <InOut>                                                               */
 245   /*    min :: The address of the current minimum.                         */
 246   /*                                                                       */
 247   /*    max :: The address of the current maximum.                         */
 248   /*                                                                       */
 249   static FT_Pos
 250   cubic_peak( FT_Pos  q1,
 251               FT_Pos  q2,
 252               FT_Pos  q3,
 253               FT_Pos  q4 )
 254   {
 255     FT_Pos  peak = 0;
 256     FT_Int  shift;
 257
 258     /* This function finds a peak of a cubic segment if it is above 0    */
 259     /* using iterative bisection of the segment, or returns 0.           */
 260     /* The fixed-point arithmetic of bisection is inherently stable      */
 261     /* but may loose accuracy in the two lowest bits.  To compensate,    */
 262     /* we upscale the segment if there is room.  Large values may need   */
 263     /* to be downscaled to avoid overflows during bisection.             */
 264     /* It is called with either q2 or q3 positive, which is necessary    */
 265     /* for the peak to exist and avoids undefined FT_MSB.                */
 266
 267     shift = 27 -
 268       FT_MSB( FT_ABS( q1 ) | FT_ABS( q2 ) | FT_ABS( q3 ) | FT_ABS( q4 ) );
 269
 270     if ( shift > 0 )
 271     {
 272       /* upscaling too much just wastes time */
 273       if ( shift > 2 )
 274         shift = 2;
 275
 276       q1 <<=  shift;
 277       q2 <<=  shift;
 278       q3 <<=  shift;
 279       q4 <<=  shift;
 280     }
 281     else
 282     {
 283       q1 >>= -shift;
 284       q2 >>= -shift;
 285       q3 >>= -shift;
 286       q4 >>= -shift;
 287     }
 288
 289     /* for a peak to exist above 0, the cubic segment must have */
 290     /* at least one of its control off-points above 0.          */
 291     while ( q2 > 0 || q3 > 0 )
 292     {
 293       /* determine which half contains the maximum and split */
 294       if ( q1 + q2 > q3 + q4 ) /* first half */
 295       {
 296         q4 = q4 + q3;
 297         q3 = q3 + q2;
 298         q2 = q2 + q1;
 299         q4 = q4 + q3;
 300         q3 = q3 + q2;
 301         q4 = ( q4 + q3 ) / 8;
 302         q3 = q3 / 4;
 303         q2 = q2 / 2;
 304       }
 305       else                     /* second half */
 306       {
 307         q1 = q1 + q2;
 308         q2 = q2 + q3;
 309         q3 = q3 + q4;
 310         q1 = q1 + q2;
 311         q2 = q2 + q3;
 312         q1 = ( q1 + q2 ) / 8;
 313         q2 = q2 / 4;
 314         q3 = q3 / 2;
 315       }
 316
 317       /* check whether either end reached the maximum */
 318       if ( q1 == q2 && q1 >= q3 )
 319       {
 320         peak = q1;
 321         break;
 322       }
 323       if ( q3 == q4 && q2 <= q4 )
 324       {
 325         peak = q4;
 326         break;
 327       }
 328     }
 329
 330     if ( shift > 0 )
 331       peak >>=  shift;
 332     else
 333       peak <<= -shift;
 334
 335     return peak;
 336   }
 337
 338
 339   static void
 340   BBox_Cubic_Check( FT_Pos   p1,
 341                     FT_Pos   p2,
 342                     FT_Pos   p3,
 343                     FT_Pos   p4,
 344                     FT_Pos*  min,
 345                     FT_Pos*  max )
 346   {
 347     /* This function is only called when a control off-point is outside  */
 348     /* the bbox that contains all on-points.  So at least one of the     */
 349     /* conditions below holds and cubic_peak is called with at least one */
 350     /* non-zero argument.                                                */
 351
 352     if ( p2 > *max || p3 > *max )
 353       *max += cubic_peak( p1 - *max, p2 - *max, p3 - *max, p4 - *max );
 354
 355     /* now flip the signs to update the minimum */
 356     if ( p2 < *min || p3 < *min )
 357       *min -= cubic_peak( *min - p1, *min - p2, *min - p3, *min - p4 );
 358   }
 359
 360
 361   /*************************************************************************/
 362   /*                                                                       */
 363   /* <Function>                                                            */
 364   /*    BBox_Cubic_To                                                      */
 365   /*                                                                       */
 366   /* <Description>                                                         */
 367   /*    This function is used as a `cubic_to' emitter during               */
 368   /*    FT_Outline_Decompose().  It checks a cubic Bezier curve with the   */
 369   /*    current bounding box, and computes its extrema if necessary to     */
 370   /*    update it.                                                         */
 371   /*                                                                       */
 372   /* <Input>                                                               */
 373   /*    control1 :: A pointer to the first control point.                  */
 374   /*                                                                       */
 375   /*    control2 :: A pointer to the second control point.                 */
 376   /*                                                                       */
 377   /*    to       :: A pointer to the destination vector.                   */
 378   /*                                                                       */
 379   /* <InOut>                                                               */
 380   /*    user     :: The address of the current walk context.               */
 381   /*                                                                       */
 382   /* <Return>                                                              */
 383   /*    Always 0.  Needed for the interface only.                          */
 384   /*                                                                       */
 385   /* <Note>                                                                */
 386   /*    In the case of a non-monotonous arc, we don't compute directly     */
 387   /*    extremum coordinates, we subdivide instead.                        */
 388   /*                                                                       */
 389   static int
 390   BBox_Cubic_To( FT_Vector*  control1,
 391                  FT_Vector*  control2,
 392                  FT_Vector*  to,
 393                  TBBox_Rec*  user )
 394   {
 395     /* We don't need to check `to' since it is always an on-point,    */
 396     /* thus within the bbox.  Only segments with an off-point outside */
 397     /* the bbox can possibly reach new extreme values.                */
 398
 399     if ( CHECK_X( control1, user->bbox ) ||
 400          CHECK_X( control2, user->bbox ) )
 401       BBox_Cubic_Check( user->last.x,
 402                         control1->x,
 403                         control2->x,
 404                         to->x,
 405                         &user->bbox.xMin,
 406                         &user->bbox.xMax );
 407
 408     if ( CHECK_Y( control1, user->bbox ) ||
 409          CHECK_Y( control2, user->bbox ) )
 410       BBox_Cubic_Check( user->last.y,
 411                         control1->y,
 412                         control2->y,
 413                         to->y,
 414                         &user->bbox.yMin,
 415                         &user->bbox.yMax );
 416
 417     user->last = *to;
 418
 419     return 0;
 420   }
 421
 422
 423   FT_DEFINE_OUTLINE_FUNCS(bbox_interface,
 424     (FT_Outline_MoveTo_Func) BBox_Move_To,
 425     (FT_Outline_LineTo_Func) BBox_Line_To,
 426     (FT_Outline_ConicTo_Func)BBox_Conic_To,
 427     (FT_Outline_CubicTo_Func)BBox_Cubic_To,
 428     0, 0
 429   )
 430
 431
 432   /* documentation is in ftbbox.h */
 433
 434   FT_EXPORT_DEF( FT_Error )
 435   FT_Outline_Get_BBox( FT_Outline*  outline,
 436                        FT_BBox     *abbox )
 437   {
 438     FT_BBox     cbox = {  0x7FFFFFFFL,  0x7FFFFFFFL,
 439                          -0x7FFFFFFFL, -0x7FFFFFFFL };
 440     FT_BBox     bbox = {  0x7FFFFFFFL,  0x7FFFFFFFL,
 441                          -0x7FFFFFFFL, -0x7FFFFFFFL };
 442     FT_Vector*  vec;
 443     FT_UShort   n;
 444
 445
 446     if ( !abbox )
 447       return FT_THROW( Invalid_Argument );
 448
 449     if ( !outline )
 450       return FT_THROW( Invalid_Outline );
 451
 452     /* if outline is empty, return (0,0,0,0) */
 453     if ( outline->n_points == 0 || outline->n_contours <= 0 )
 454     {
 455       abbox->xMin = abbox->xMax = 0;
 456       abbox->yMin = abbox->yMax = 0;
 457       return 0;
 458     }
 459
 460     /* We compute the control box as well as the bounding box of  */
 461     /* all `on' points in the outline.  Then, if the two boxes    */
 462     /* coincide, we exit immediately.                             */
 463
 464     vec = outline->points;
 465
 466     for ( n = 0; n < outline->n_points; n++ )
 467     {
 468       FT_UPDATE_BBOX( vec, cbox);
 469
 470       if ( FT_CURVE_TAG( outline->tags[n] ) == FT_CURVE_TAG_ON )
 471         FT_UPDATE_BBOX( vec, bbox);
 472
 473       vec++;
 474     }
 475
 476     /* test two boxes for equality */
 477     if ( cbox.xMin < bbox.xMin || cbox.xMax > bbox.xMax ||
 478          cbox.yMin < bbox.yMin || cbox.yMax > bbox.yMax )
 479     {
 480       /* the two boxes are different, now walk over the outline to */
 481       /* get the Bezier arc extrema.                               */
 482
 483       FT_Error   error;
 484       TBBox_Rec  user;
 485
 486 #ifdef FT_CONFIG_OPTION_PIC
 487       FT_Outline_Funcs bbox_interface;
 488       Init_Class_bbox_interface(&bbox_interface);
 489 #endif
 490
 491       user.bbox = bbox;
 492
 493       error = FT_Outline_Decompose( outline, &bbox_interface, &user );
 494       if ( error )
 495         return error;
 496
 497       *abbox = user.bbox;
 498     }
 499     else
 500       *abbox = bbox;
 501
 502     return FT_Err_Ok;
 503   }
 504
 505
 506 /* END */