QRScanner/mobile/jni/thirdparty/freetype/src/base/ftbbox.c

   1 /***************************************************************************/
   2 /*                                                                         */
   3 /*  ftbbox.c                                                               */
   4 /*                                                                         */
   5 /*    FreeType bbox computation (body).                                    */
   6 /*                                                                         */
   7 /*  Copyright 1996-2001, 2002, 2004, 2006, 2010 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_BBOX_H
  29 #include FT_IMAGE_H
  30 #include FT_OUTLINE_H
  31 #include FT_INTERNAL_CALC_H
  32 #include FT_INTERNAL_OBJECTS_H
  33
  34
  35   typedef struct  TBBox_Rec_
  36   {
  37     FT_Vector  last;
  38     FT_BBox    bbox;
  39
  40   } TBBox_Rec;
  41
  42
  43   /*************************************************************************/
  44   /*                                                                       */
  45   /* <Function>                                                            */
  46   /*    BBox_Move_To                                                       */
  47   /*                                                                       */
  48   /* <Description>                                                         */
  49   /*    This function is used as a `move_to' and `line_to' emitter during  */
  50   /*    FT_Outline_Decompose().  It simply records the destination point   */
  51   /*    in `user->last'; no further computations are necessary since we    */
  52   /*    use the cbox as the starting bbox which must be refined.           */
  53   /*                                                                       */
  54   /* <Input>                                                               */
  55   /*    to   :: A pointer to the destination vector.                       */
  56   /*                                                                       */
  57   /* <InOut>                                                               */
  58   /*    user :: A pointer to the current walk context.                     */
  59   /*                                                                       */
  60   /* <Return>                                                              */
  61   /*    Always 0.  Needed for the interface only.                          */
  62   /*                                                                       */
  63   static int
  64   BBox_Move_To( FT_Vector*  to,
  65                 TBBox_Rec*  user )
  66   {
  67     user->last = *to;
  68
  69     return 0;
  70   }
  71
  72
  73 #define CHECK_X( p, bbox )  \
  74           ( p->x < bbox.xMin || p->x > bbox.xMax )
  75
  76 #define CHECK_Y( p, bbox )  \
  77           ( p->y < bbox.yMin || p->y > bbox.yMax )
  78
  79
  80   /*************************************************************************/
  81   /*                                                                       */
  82   /* <Function>                                                            */
  83   /*    BBox_Conic_Check                                                   */
  84   /*                                                                       */
  85   /* <Description>                                                         */
  86   /*    Finds the extrema of a 1-dimensional conic Bezier curve and update */
  87   /*    a bounding range.  This version uses direct computation, as it     */
  88   /*    doesn't need square roots.                                         */
  89   /*                                                                       */
  90   /* <Input>                                                               */
  91   /*    y1  :: The start coordinate.                                       */
  92   /*                                                                       */
  93   /*    y2  :: The coordinate of the control point.                        */
  94   /*                                                                       */
  95   /*    y3  :: The end coordinate.                                         */
  96   /*                                                                       */
  97   /* <InOut>                                                               */
  98   /*    min :: The address of the current minimum.                         */
  99   /*                                                                       */
 100   /*    max :: The address of the current maximum.                         */
 101   /*                                                                       */
 102   static void
 103   BBox_Conic_Check( FT_Pos   y1,
 104                     FT_Pos   y2,
 105                     FT_Pos   y3,
 106                     FT_Pos*  min,
 107                     FT_Pos*  max )
 108   {
 109     if ( y1 <= y3 && y2 == y1 )     /* flat arc */
 110       goto Suite;
 111
 112     if ( y1 < y3 )
 113     {
 114       if ( y2 >= y1 && y2 <= y3 )   /* ascending arc */
 115         goto Suite;
 116     }
 117     else
 118     {
 119       if ( y2 >= y3 && y2 <= y1 )   /* descending arc */
 120       {
 121         y2 = y1;
 122         y1 = y3;
 123         y3 = y2;
 124         goto Suite;
 125       }
 126     }
 127
 128     y1 = y3 = y1 - FT_MulDiv( y2 - y1, y2 - y1, y1 - 2*y2 + y3 );
 129
 130   Suite:
 131     if ( y1 < *min ) *min = y1;
 132     if ( y3 > *max ) *max = y3;
 133   }
 134
 135
 136   /*************************************************************************/
 137   /*                                                                       */
 138   /* <Function>                                                            */
 139   /*    BBox_Conic_To                                                      */
 140   /*                                                                       */
 141   /* <Description>                                                         */
 142   /*    This function is used as a `conic_to' emitter during               */
 143   /*    FT_Outline_Decompose().  It checks a conic Bezier curve with the   */
 144   /*    current bounding box, and computes its extrema if necessary to     */
 145   /*    update it.                                                         */
 146   /*                                                                       */
 147   /* <Input>                                                               */
 148   /*    control :: A pointer to a control point.                           */
 149   /*                                                                       */
 150   /*    to      :: A pointer to the destination vector.                    */
 151   /*                                                                       */
 152   /* <InOut>                                                               */
 153   /*    user    :: The address of the current walk context.                */
 154   /*                                                                       */
 155   /* <Return>                                                              */
 156   /*    Always 0.  Needed for the interface only.                          */
 157   /*                                                                       */
 158   /* <Note>                                                                */
 159   /*    In the case of a non-monotonous arc, we compute directly the       */
 160   /*    extremum coordinates, as it is sufficiently fast.                  */
 161   /*                                                                       */
 162   static int
 163   BBox_Conic_To( FT_Vector*  control,
 164                  FT_Vector*  to,
 165                  TBBox_Rec*  user )
 166   {
 167     /* we don't need to check `to' since it is always an `on' point, thus */
 168     /* within the bbox                                                    */
 169
 170     if ( CHECK_X( control, user->bbox ) )
 171       BBox_Conic_Check( user->last.x,
 172                         control->x,
 173                         to->x,
 174                         &user->bbox.xMin,
 175                         &user->bbox.xMax );
 176
 177     if ( CHECK_Y( control, user->bbox ) )
 178       BBox_Conic_Check( user->last.y,
 179                         control->y,
 180                         to->y,
 181                         &user->bbox.yMin,
 182                         &user->bbox.yMax );
 183
 184     user->last = *to;
 185
 186     return 0;
 187   }
 188
 189
 190   /*************************************************************************/
 191   /*                                                                       */
 192   /* <Function>                                                            */
 193   /*    BBox_Cubic_Check                                                   */
 194   /*                                                                       */
 195   /* <Description>                                                         */
 196   /*    Finds the extrema of a 1-dimensional cubic Bezier curve and        */
 197   /*    updates a bounding range.  This version uses splitting because we  */
 198   /*    don't want to use square roots and extra accuracy.                 */
 199   /*                                                                       */
 200   /* <Input>                                                               */
 201   /*    p1  :: The start coordinate.                                       */
 202   /*                                                                       */
 203   /*    p2  :: The coordinate of the first control point.                  */
 204   /*                                                                       */
 205   /*    p3  :: The coordinate of the second control point.                 */
 206   /*                                                                       */
 207   /*    p4  :: The end coordinate.                                         */
 208   /*                                                                       */
 209   /* <InOut>                                                               */
 210   /*    min :: The address of the current minimum.                         */
 211   /*                                                                       */
 212   /*    max :: The address of the current maximum.                         */
 213   /*                                                                       */
 214
 215 #if 0
 216
 217   static void
 218   BBox_Cubic_Check( FT_Pos   p1,
 219                     FT_Pos   p2,
 220                     FT_Pos   p3,
 221                     FT_Pos   p4,
 222                     FT_Pos*  min,
 223                     FT_Pos*  max )
 224   {
 225     FT_Pos  stack[32*3 + 1], *arc;
 226
 227
 228     arc = stack;
 229
 230     arc[0] = p1;
 231     arc[1] = p2;
 232     arc[2] = p3;
 233     arc[3] = p4;
 234
 235     do
 236     {
 237       FT_Pos  y1 = arc[0];
 238       FT_Pos  y2 = arc[1];
 239       FT_Pos  y3 = arc[2];
 240       FT_Pos  y4 = arc[3];
 241
 242
 243       if ( y1 == y4 )
 244       {
 245         if ( y1 == y2 && y1 == y3 )                         /* flat */
 246           goto Test;
 247       }
 248       else if ( y1 < y4 )
 249       {
 250         if ( y2 >= y1 && y2 <= y4 && y3 >= y1 && y3 <= y4 ) /* ascending */
 251           goto Test;
 252       }
 253       else
 254       {
 255         if ( y2 >= y4 && y2 <= y1 && y3 >= y4 && y3 <= y1 ) /* descending */
 256         {
 257           y2 = y1;
 258           y1 = y4;
 259           y4 = y2;
 260           goto Test;
 261         }
 262       }
 263
 264       /* unknown direction -- split the arc in two */
 265       arc[6] = y4;
 266       arc[1] = y1 = ( y1 + y2 ) / 2;
 267       arc[5] = y4 = ( y4 + y3 ) / 2;
 268       y2 = ( y2 + y3 ) / 2;
 269       arc[2] = y1 = ( y1 + y2 ) / 2;
 270       arc[4] = y4 = ( y4 + y2 ) / 2;
 271       arc[3] = ( y1 + y4 ) / 2;
 272
 273       arc += 3;
 274       goto Suite;
 275
 276    Test:
 277       if ( y1 < *min ) *min = y1;
 278       if ( y4 > *max ) *max = y4;
 279       arc -= 3;
 280
 281     Suite:
 282       ;
 283     } while ( arc >= stack );
 284   }
 285
 286 #else
 287
 288   static void
 289   test_cubic_extrema( FT_Pos    y1,
 290                       FT_Pos    y2,
 291                       FT_Pos    y3,
 292                       FT_Pos    y4,
 293                       FT_Fixed  u,
 294                       FT_Pos*   min,
 295                       FT_Pos*   max )
 296   {
 297  /* FT_Pos    a = y4 - 3*y3 + 3*y2 - y1; */
 298     FT_Pos    b = y3 - 2*y2 + y1;
 299     FT_Pos    c = y2 - y1;
 300     FT_Pos    d = y1;
 301     FT_Pos    y;
 302     FT_Fixed  uu;
 303
 304     FT_UNUSED ( y4 );
 305
 306
 307     /* The polynomial is                      */
 308     /*                                        */
 309     /*    P(x) = a*x^3 + 3b*x^2 + 3c*x + d  , */
 310     /*                                        */
 311     /*   dP/dx = 3a*x^2 + 6b*x + 3c         . */
 312     /*                                        */
 313     /* However, we also have                  */
 314     /*                                        */
 315     /*   dP/dx(u) = 0                       , */
 316     /*                                        */
 317     /* which implies by subtraction that      */
 318     /*                                        */
 319     /*   P(u) = b*u^2 + 2c*u + d            . */
 320
 321     if ( u > 0 && u < 0x10000L )
 322     {
 323       uu = FT_MulFix( u, u );
 324       y  = d + FT_MulFix( c, 2*u ) + FT_MulFix( b, uu );
 325
 326       if ( y < *min ) *min = y;
 327       if ( y > *max ) *max = y;
 328     }
 329   }
 330
 331
 332   static void
 333   BBox_Cubic_Check( FT_Pos   y1,
 334                     FT_Pos   y2,
 335                     FT_Pos   y3,
 336                     FT_Pos   y4,
 337                     FT_Pos*  min,
 338                     FT_Pos*  max )
 339   {
 340     /* always compare first and last points */
 341     if      ( y1 < *min )  *min = y1;
 342     else if ( y1 > *max )  *max = y1;
 343
 344     if      ( y4 < *min )  *min = y4;
 345     else if ( y4 > *max )  *max = y4;
 346
 347     /* now, try to see if there are split points here */
 348     if ( y1 <= y4 )
 349     {
 350       /* flat or ascending arc test */
 351       if ( y1 <= y2 && y2 <= y4 && y1 <= y3 && y3 <= y4 )
 352         return;
 353     }
 354     else /* y1 > y4 */
 355     {
 356       /* descending arc test */
 357       if ( y1 >= y2 && y2 >= y4 && y1 >= y3 && y3 >= y4 )
 358         return;
 359     }
 360
 361     /* There are some split points.  Find them. */
 362     {
 363       FT_Pos    a = y4 - 3*y3 + 3*y2 - y1;
 364       FT_Pos    b = y3 - 2*y2 + y1;
 365       FT_Pos    c = y2 - y1;
 366       FT_Pos    d;
 367       FT_Fixed  t;
 368
 369
 370       /* We need to solve `ax^2+2bx+c' here, without floating points!      */
 371       /* The trick is to normalize to a different representation in order  */
 372       /* to use our 16.16 fixed point routines.                            */
 373       /*                                                                   */
 374       /* We compute FT_MulFix(b,b) and FT_MulFix(a,c) after normalization. */
 375       /* These values must fit into a single 16.16 value.                  */
 376       /*                                                                   */
 377       /* We normalize a, b, and c to `8.16' fixed float values to ensure   */
 378       /* that its product is held in a `16.16' value.                      */
 379
 380       {
 381         FT_ULong  t1, t2;
 382         int       shift = 0;
 383
 384
 385         /* The following computation is based on the fact that for   */
 386         /* any value `y', if `n' is the position of the most         */
 387         /* significant bit of `abs(y)' (starting from 0 for the      */
 388         /* least significant bit), then `y' is in the range          */
 389         /*                                                           */
 390         /*   -2^n..2^n-1                                             */
 391         /*                                                           */
 392         /* We want to shift `a', `b', and `c' concurrently in order  */
 393         /* to ensure that they all fit in 8.16 values, which maps    */
 394         /* to the integer range `-2^23..2^23-1'.                     */
 395         /*                                                           */
 396         /* Necessarily, we need to shift `a', `b', and `c' so that   */
 397         /* the most significant bit of its absolute values is at     */
 398         /* _most_ at position 23.                                    */
 399         /*                                                           */
 400         /* We begin by computing `t1' as the bitwise `OR' of the     */
 401         /* absolute values of `a', `b', `c'.                         */
 402
 403         t1  = (FT_ULong)( ( a >= 0 ) ? a : -a );
 404         t2  = (FT_ULong)( ( b >= 0 ) ? b : -b );
 405         t1 |= t2;
 406         t2  = (FT_ULong)( ( c >= 0 ) ? c : -c );
 407         t1 |= t2;
 408
 409         /* Now we can be sure that the most significant bit of `t1'  */
 410         /* is the most significant bit of either `a', `b', or `c',   */
 411         /* depending on the greatest integer range of the particular */
 412         /* variable.                                                 */
 413         /*                                                           */
 414         /* Next, we compute the `shift', by shifting `t1' as many    */
 415         /* times as necessary to move its MSB to position 23.  This  */
 416         /* corresponds to a value of `t1' that is in the range       */
 417         /* 0x40_0000..0x7F_FFFF.                                     */
 418         /*                                                           */
 419         /* Finally, we shift `a', `b', and `c' by the same amount.   */
 420         /* This ensures that all values are now in the range         */
 421         /* -2^23..2^23, i.e., they are now expressed as 8.16         */
 422         /* fixed-float numbers.  This also means that we are using   */
 423         /* 24 bits of precision to compute the zeros, independently  */
 424         /* of the range of the original polynomial coefficients.     */
 425         /*                                                           */
 426         /* This algorithm should ensure reasonably accurate values   */
 427         /* for the zeros.  Note that they are only expressed with    */
 428         /* 16 bits when computing the extrema (the zeros need to     */
 429         /* be in 0..1 exclusive to be considered part of the arc).   */
 430
 431         if ( t1 == 0 )  /* all coefficients are 0! */
 432           return;
 433
 434         if ( t1 > 0x7FFFFFUL )
 435         {
 436           do
 437           {
 438             shift++;
 439             t1 >>= 1;
 440
 441           } while ( t1 > 0x7FFFFFUL );
 442
 443           /* this loses some bits of precision, but we use 24 of them */
 444           /* for the computation anyway                               */
 445           a >>= shift;
 446           b >>= shift;
 447           c >>= shift;
 448         }
 449         else if ( t1 < 0x400000UL )
 450         {
 451           do
 452           {
 453             shift++;
 454             t1 <<= 1;
 455
 456           } while ( t1 < 0x400000UL );
 457
 458           a <<= shift;
 459           b <<= shift;
 460           c <<= shift;
 461         }
 462       }
 463
 464       /* handle a == 0 */
 465       if ( a == 0 )
 466       {
 467         if ( b != 0 )
 468         {
 469           t = - FT_DivFix( c, b ) / 2;
 470           test_cubic_extrema( y1, y2, y3, y4, t, min, max );
 471         }
 472       }
 473       else
 474       {
 475         /* solve the equation now */
 476         d = FT_MulFix( b, b ) - FT_MulFix( a, c );
 477         if ( d < 0 )
 478           return;
 479
 480         if ( d == 0 )
 481         {
 482           /* there is a single split point at -b/a */
 483           t = - FT_DivFix( b, a );
 484           test_cubic_extrema( y1, y2, y3, y4, t, min, max );
 485         }
 486         else
 487         {
 488           /* there are two solutions; we need to filter them */
 489           d = FT_SqrtFixed( (FT_Int32)d );
 490           t = - FT_DivFix( b - d, a );
 491           test_cubic_extrema( y1, y2, y3, y4, t, min, max );
 492
 493           t = - FT_DivFix( b + d, a );
 494           test_cubic_extrema( y1, y2, y3, y4, t, min, max );
 495         }
 496       }
 497     }
 498   }
 499
 500 #endif
 501
 502
 503   /*************************************************************************/
 504   /*                                                                       */
 505   /* <Function>                                                            */
 506   /*    BBox_Cubic_To                                                      */
 507   /*                                                                       */
 508   /* <Description>                                                         */
 509   /*    This function is used as a `cubic_to' emitter during               */
 510   /*    FT_Outline_Decompose().  It checks a cubic Bezier curve with the   */
 511   /*    current bounding box, and computes its extrema if necessary to     */
 512   /*    update it.                                                         */
 513   /*                                                                       */
 514   /* <Input>                                                               */
 515   /*    control1 :: A pointer to the first control point.                  */
 516   /*                                                                       */
 517   /*    control2 :: A pointer to the second control point.                 */
 518   /*                                                                       */
 519   /*    to       :: A pointer to the destination vector.                   */
 520   /*                                                                       */
 521   /* <InOut>                                                               */
 522   /*    user     :: The address of the current walk context.               */
 523   /*                                                                       */
 524   /* <Return>                                                              */
 525   /*    Always 0.  Needed for the interface only.                          */
 526   /*                                                                       */
 527   /* <Note>                                                                */
 528   /*    In the case of a non-monotonous arc, we don't compute directly     */
 529   /*    extremum coordinates, we subdivide instead.                        */
 530   /*                                                                       */
 531   static int
 532   BBox_Cubic_To( FT_Vector*  control1,
 533                  FT_Vector*  control2,
 534                  FT_Vector*  to,
 535                  TBBox_Rec*  user )
 536   {
 537     /* we don't need to check `to' since it is always an `on' point, thus */
 538     /* within the bbox                                                    */
 539
 540     if ( CHECK_X( control1, user->bbox ) ||
 541          CHECK_X( control2, user->bbox ) )
 542       BBox_Cubic_Check( user->last.x,
 543                         control1->x,
 544                         control2->x,
 545                         to->x,
 546                         &user->bbox.xMin,
 547                         &user->bbox.xMax );
 548
 549     if ( CHECK_Y( control1, user->bbox ) ||
 550          CHECK_Y( control2, user->bbox ) )
 551       BBox_Cubic_Check( user->last.y,
 552                         control1->y,
 553                         control2->y,
 554                         to->y,
 555                         &user->bbox.yMin,
 556                         &user->bbox.yMax );
 557
 558     user->last = *to;
 559
 560     return 0;
 561   }
 562
 563 FT_DEFINE_OUTLINE_FUNCS(bbox_interface,
 564     (FT_Outline_MoveTo_Func) BBox_Move_To,
 565     (FT_Outline_LineTo_Func) BBox_Move_To,
 566     (FT_Outline_ConicTo_Func)BBox_Conic_To,
 567     (FT_Outline_CubicTo_Func)BBox_Cubic_To,
 568     0, 0
 569   )
 570
 571   /* documentation is in ftbbox.h */
 572
 573   FT_EXPORT_DEF( FT_Error )
 574   FT_Outline_Get_BBox( FT_Outline*  outline,
 575                        FT_BBox     *abbox )
 576   {
 577     FT_BBox     cbox;
 578     FT_BBox     bbox;
 579     FT_Vector*  vec;
 580     FT_UShort   n;
 581
 582
 583     if ( !abbox )
 584       return FT_Err_Invalid_Argument;
 585
 586     if ( !outline )
 587       return FT_Err_Invalid_Outline;
 588
 589     /* if outline is empty, return (0,0,0,0) */
 590     if ( outline->n_points == 0 || outline->n_contours <= 0 )
 591     {
 592       abbox->xMin = abbox->xMax = 0;
 593       abbox->yMin = abbox->yMax = 0;
 594       return 0;
 595     }
 596
 597     /* We compute the control box as well as the bounding box of  */
 598     /* all `on' points in the outline.  Then, if the two boxes    */
 599     /* coincide, we exit immediately.                             */
 600
 601     vec = outline->points;
 602     bbox.xMin = bbox.xMax = cbox.xMin = cbox.xMax = vec->x;
 603     bbox.yMin = bbox.yMax = cbox.yMin = cbox.yMax = vec->y;
 604     vec++;
 605
 606     for ( n = 1; n < outline->n_points; n++ )
 607     {
 608       FT_Pos  x = vec->x;
 609       FT_Pos  y = vec->y;
 610
 611
 612       /* update control box */
 613       if ( x < cbox.xMin ) cbox.xMin = x;
 614       if ( x > cbox.xMax ) cbox.xMax = x;
 615
 616       if ( y < cbox.yMin ) cbox.yMin = y;
 617       if ( y > cbox.yMax ) cbox.yMax = y;
 618
 619       if ( FT_CURVE_TAG( outline->tags[n] ) == FT_CURVE_TAG_ON )
 620       {
 621         /* update bbox for `on' points only */
 622         if ( x < bbox.xMin ) bbox.xMin = x;
 623         if ( x > bbox.xMax ) bbox.xMax = x;
 624
 625         if ( y < bbox.yMin ) bbox.yMin = y;
 626         if ( y > bbox.yMax ) bbox.yMax = y;
 627       }
 628
 629       vec++;
 630     }
 631
 632     /* test two boxes for equality */
 633     if ( cbox.xMin < bbox.xMin || cbox.xMax > bbox.xMax ||
 634          cbox.yMin < bbox.yMin || cbox.yMax > bbox.yMax )
 635     {
 636       /* the two boxes are different, now walk over the outline to */
 637       /* get the Bezier arc extrema.                               */
 638
 639       FT_Error   error;
 640       TBBox_Rec  user;
 641
 642 #ifdef FT_CONFIG_OPTION_PIC
 643       FT_Outline_Funcs bbox_interface;
 644       Init_Class_bbox_interface(&bbox_interface);
 645 #endif
 646
 647       user.bbox = bbox;
 648
 649       error = FT_Outline_Decompose( outline, &bbox_interface, &user );
 650       if ( error )
 651         return error;
 652
 653       *abbox = user.bbox;
 654     }
 655     else
 656       *abbox = bbox;
 657
 658     return FT_Err_Ok;
 659   }
 660
 661
 662 /* END */