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