libraries/freetype-2.0.5/ftbbox.c

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