src/base/ftbbox.c

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