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