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