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