OLD | NEW |
1 /***************************************************************************/ | 1 /***************************************************************************/ |
2 /* */ | 2 /* */ |
3 /* ftbbox.c */ | 3 /* ftbbox.c */ |
4 /* */ | 4 /* */ |
5 /* FreeType bbox computation (body). */ | 5 /* FreeType bbox computation (body). */ |
6 /* */ | 6 /* */ |
7 /* Copyright 1996-2001, 2002, 2004, 2006, 2010 by */ | 7 /* Copyright 1996-2002, 2004, 2006, 2010, 2013 by */ |
8 /* David Turner, Robert Wilhelm, and Werner Lemberg. */ | 8 /* David Turner, Robert Wilhelm, and Werner Lemberg. */ |
9 /* */ | 9 /* */ |
10 /* This file is part of the FreeType project, and may only be used */ | 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 */ | 11 /* modified and distributed under the terms of the FreeType project */ |
12 /* license, LICENSE.TXT. By continuing to use, modify, or distribute */ | 12 /* license, LICENSE.TXT. By continuing to use, modify, or distribute */ |
13 /* this file you indicate that you have read the license and */ | 13 /* this file you indicate that you have read the license and */ |
14 /* understand and accept it fully. */ | 14 /* understand and accept it fully. */ |
15 /* */ | 15 /* */ |
16 /***************************************************************************/ | 16 /***************************************************************************/ |
17 | 17 |
18 | 18 |
19 /*************************************************************************/ | 19 /*************************************************************************/ |
20 /* */ | 20 /* */ |
21 /* This component has a _single_ role: to compute exact outline bounding */ | 21 /* This component has a _single_ role: to compute exact outline bounding */ |
22 /* boxes. */ | 22 /* boxes. */ |
23 /* */ | 23 /* */ |
24 /*************************************************************************/ | 24 /*************************************************************************/ |
25 | 25 |
26 | 26 |
27 #include <ft2build.h> | 27 #include <ft2build.h> |
| 28 #include FT_INTERNAL_DEBUG_H |
| 29 |
28 #include FT_BBOX_H | 30 #include FT_BBOX_H |
29 #include FT_IMAGE_H | 31 #include FT_IMAGE_H |
30 #include FT_OUTLINE_H | 32 #include FT_OUTLINE_H |
31 #include FT_INTERNAL_CALC_H | 33 #include FT_INTERNAL_CALC_H |
32 #include FT_INTERNAL_OBJECTS_H | 34 #include FT_INTERNAL_OBJECTS_H |
33 | 35 |
34 | 36 |
35 typedef struct TBBox_Rec_ | 37 typedef struct TBBox_Rec_ |
36 { | 38 { |
37 FT_Vector last; | 39 FT_Vector last; |
(...skipping 177 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
215 #if 0 | 217 #if 0 |
216 | 218 |
217 static void | 219 static void |
218 BBox_Cubic_Check( FT_Pos p1, | 220 BBox_Cubic_Check( FT_Pos p1, |
219 FT_Pos p2, | 221 FT_Pos p2, |
220 FT_Pos p3, | 222 FT_Pos p3, |
221 FT_Pos p4, | 223 FT_Pos p4, |
222 FT_Pos* min, | 224 FT_Pos* min, |
223 FT_Pos* max ) | 225 FT_Pos* max ) |
224 { | 226 { |
225 FT_Pos stack[32*3 + 1], *arc; | 227 FT_Pos q1, q2, q3, q4; |
226 | 228 |
227 | 229 |
228 arc = stack; | 230 q1 = p1; |
| 231 q2 = p2; |
| 232 q3 = p3; |
| 233 q4 = p4; |
229 | 234 |
230 arc[0] = p1; | 235 /* for a conic segment to possibly reach new maximum */ |
231 arc[1] = p2; | 236 /* one of its off-points must be above the current value */ |
232 arc[2] = p3; | 237 while ( q2 > *max || q3 > *max ) |
233 arc[3] = p4; | |
234 | |
235 do | |
236 { | 238 { |
237 FT_Pos y1 = arc[0]; | 239 /* determine which half contains the maximum and split */ |
238 FT_Pos y2 = arc[1]; | 240 if ( q1 + q2 > q3 + q4 ) /* first half */ |
239 FT_Pos y3 = arc[2]; | |
240 FT_Pos y4 = arc[3]; | |
241 | |
242 | |
243 if ( y1 == y4 ) | |
244 { | 241 { |
245 if ( y1 == y2 && y1 == y3 ) /* flat */ | 242 q4 = q4 + q3; |
246 goto Test; | 243 q3 = q3 + q2; |
| 244 q2 = q2 + q1; |
| 245 q4 = q4 + q3; |
| 246 q3 = q3 + q2; |
| 247 q4 = ( q4 + q3 ) / 8; |
| 248 q3 = q3 / 4; |
| 249 q2 = q2 / 2; |
247 } | 250 } |
248 else if ( y1 < y4 ) | 251 else /* second half */ |
249 { | 252 { |
250 if ( y2 >= y1 && y2 <= y4 && y3 >= y1 && y3 <= y4 ) /* ascending */ | 253 q1 = q1 + q2; |
251 goto Test; | 254 q2 = q2 + q3; |
252 } | 255 q3 = q3 + q4; |
253 else | 256 q1 = q1 + q2; |
254 { | 257 q2 = q2 + q3; |
255 if ( y2 >= y4 && y2 <= y1 && y3 >= y4 && y3 <= y1 ) /* descending */ | 258 q1 = ( q1 + q2 ) / 8; |
256 { | 259 q2 = q2 / 4; |
257 y2 = y1; | 260 q3 = q3 / 2; |
258 y1 = y4; | |
259 y4 = y2; | |
260 goto Test; | |
261 } | |
262 } | 261 } |
263 | 262 |
264 /* unknown direction -- split the arc in two */ | 263 /* check if either end reached the maximum */ |
265 arc[6] = y4; | 264 if ( q1 == q2 && q1 >= q3 ) |
266 arc[1] = y1 = ( y1 + y2 ) / 2; | 265 { |
267 arc[5] = y4 = ( y4 + y3 ) / 2; | 266 *max = q1; |
268 y2 = ( y2 + y3 ) / 2; | 267 break; |
269 arc[2] = y1 = ( y1 + y2 ) / 2; | 268 } |
270 arc[4] = y4 = ( y4 + y2 ) / 2; | 269 if ( q3 == q4 && q2 <= q4 ) |
271 arc[3] = ( y1 + y4 ) / 2; | 270 { |
| 271 *max = q4; |
| 272 break; |
| 273 } |
| 274 } |
272 | 275 |
273 arc += 3; | 276 q1 = p1; |
274 goto Suite; | 277 q2 = p2; |
| 278 q3 = p3; |
| 279 q4 = p4; |
275 | 280 |
276 Test: | 281 /* for a conic segment to possibly reach new minimum */ |
277 if ( y1 < *min ) *min = y1; | 282 /* one of its off-points must be below the current value */ |
278 if ( y4 > *max ) *max = y4; | 283 while ( q2 < *min || q3 < *min ) |
279 arc -= 3; | 284 { |
| 285 /* determine which half contains the minimum and split */ |
| 286 if ( q1 + q2 < q3 + q4 ) /* first half */ |
| 287 { |
| 288 q4 = q4 + q3; |
| 289 q3 = q3 + q2; |
| 290 q2 = q2 + q1; |
| 291 q4 = q4 + q3; |
| 292 q3 = q3 + q2; |
| 293 q4 = ( q4 + q3 ) / 8; |
| 294 q3 = q3 / 4; |
| 295 q2 = q2 / 2; |
| 296 } |
| 297 else /* second half */ |
| 298 { |
| 299 q1 = q1 + q2; |
| 300 q2 = q2 + q3; |
| 301 q3 = q3 + q4; |
| 302 q1 = q1 + q2; |
| 303 q2 = q2 + q3; |
| 304 q1 = ( q1 + q2 ) / 8; |
| 305 q2 = q2 / 4; |
| 306 q3 = q3 / 2; |
| 307 } |
280 | 308 |
281 Suite: | 309 /* check if either end reached the minimum */ |
282 ; | 310 if ( q1 == q2 && q1 <= q3 ) |
283 } while ( arc >= stack ); | 311 { |
| 312 *min = q1; |
| 313 break; |
| 314 } |
| 315 if ( q3 == q4 && q2 >= q4 ) |
| 316 { |
| 317 *min = q4; |
| 318 break; |
| 319 } |
| 320 } |
284 } | 321 } |
285 | 322 |
286 #else | 323 #else |
287 | 324 |
288 static void | 325 static void |
289 test_cubic_extrema( FT_Pos y1, | 326 test_cubic_extrema( FT_Pos y1, |
290 FT_Pos y2, | 327 FT_Pos y2, |
291 FT_Pos y3, | 328 FT_Pos y3, |
292 FT_Pos y4, | 329 FT_Pos y4, |
293 FT_Fixed u, | 330 FT_Fixed u, |
(...skipping 57 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
351 if ( y1 <= y2 && y2 <= y4 && y1 <= y3 && y3 <= y4 ) | 388 if ( y1 <= y2 && y2 <= y4 && y1 <= y3 && y3 <= y4 ) |
352 return; | 389 return; |
353 } | 390 } |
354 else /* y1 > y4 */ | 391 else /* y1 > y4 */ |
355 { | 392 { |
356 /* descending arc test */ | 393 /* descending arc test */ |
357 if ( y1 >= y2 && y2 >= y4 && y1 >= y3 && y3 >= y4 ) | 394 if ( y1 >= y2 && y2 >= y4 && y1 >= y3 && y3 >= y4 ) |
358 return; | 395 return; |
359 } | 396 } |
360 | 397 |
361 /* There are some split points. Find them. */ | 398 /* There are some split points. Find them. */ |
| 399 /* We already made sure that a, b, and c below cannot be all zero. */ |
362 { | 400 { |
363 FT_Pos a = y4 - 3*y3 + 3*y2 - y1; | 401 FT_Pos a = y4 - 3*y3 + 3*y2 - y1; |
364 FT_Pos b = y3 - 2*y2 + y1; | 402 FT_Pos b = y3 - 2*y2 + y1; |
365 FT_Pos c = y2 - y1; | 403 FT_Pos c = y2 - y1; |
366 FT_Pos d; | 404 FT_Pos d; |
367 FT_Fixed t; | 405 FT_Fixed t; |
| 406 FT_Int shift; |
368 | 407 |
369 | 408 |
370 /* We need to solve `ax^2+2bx+c' here, without floating points! */ | 409 /* We need to solve `ax^2+2bx+c' here, without floating points! */ |
371 /* The trick is to normalize to a different representation in order */ | 410 /* The trick is to normalize to a different representation in order */ |
372 /* to use our 16.16 fixed point routines. */ | 411 /* to use our 16.16 fixed-point routines. */ |
373 /* */ | 412 /* */ |
374 /* We compute FT_MulFix(b,b) and FT_MulFix(a,c) after normalization. */ | 413 /* We compute FT_MulFix(b,b) and FT_MulFix(a,c) after normalization. */ |
375 /* These values must fit into a single 16.16 value. */ | 414 /* These values must fit into a single 16.16 value. */ |
376 /* */ | 415 /* */ |
377 /* We normalize a, b, and c to `8.16' fixed float values to ensure */ | 416 /* We normalize a, b, and c to `8.16' fixed-point values to ensure */ |
378 /* that its product is held in a `16.16' value. */ | 417 /* that their product is held in a `16.16' value including the sign. */ |
| 418 /* Necessarily, we need to shift `a', `b', and `c' so that the most */ |
| 419 /* significant bit of their absolute values is at position 22. */ |
| 420 /* */ |
| 421 /* This also means that we are using 23 bits of precision to compute */ |
| 422 /* the zeros, independently of the range of the original polynomial */ |
| 423 /* coefficients. */ |
| 424 /* */ |
| 425 /* This algorithm should ensure reasonably accurate values for the */ |
| 426 /* zeros. Note that they are only expressed with 16 bits when */ |
| 427 /* computing the extrema (the zeros need to be in 0..1 exclusive */ |
| 428 /* to be considered part of the arc). */ |
379 | 429 |
| 430 shift = FT_MSB( FT_ABS( a ) | FT_ABS( b ) | FT_ABS( c ) ); |
| 431 |
| 432 if ( shift > 22 ) |
380 { | 433 { |
381 FT_ULong t1, t2; | 434 shift -= 22; |
382 int shift = 0; | |
383 | 435 |
| 436 /* this loses some bits of precision, but we use 23 of them */ |
| 437 /* for the computation anyway */ |
| 438 a >>= shift; |
| 439 b >>= shift; |
| 440 c >>= shift; |
| 441 } |
| 442 else |
| 443 { |
| 444 shift = 22 - shift; |
384 | 445 |
385 /* The following computation is based on the fact that for */ | 446 a <<= shift; |
386 /* any value `y', if `n' is the position of the most */ | 447 b <<= shift; |
387 /* significant bit of `abs(y)' (starting from 0 for the */ | 448 c <<= shift; |
388 /* least significant bit), then `y' is in the range */ | |
389 /* */ | |
390 /* -2^n..2^n-1 */ | |
391 /* */ | |
392 /* We want to shift `a', `b', and `c' concurrently in order */ | |
393 /* to ensure that they all fit in 8.16 values, which maps */ | |
394 /* to the integer range `-2^23..2^23-1'. */ | |
395 /* */ | |
396 /* Necessarily, we need to shift `a', `b', and `c' so that */ | |
397 /* the most significant bit of its absolute values is at */ | |
398 /* _most_ at position 23. */ | |
399 /* */ | |
400 /* We begin by computing `t1' as the bitwise `OR' of the */ | |
401 /* absolute values of `a', `b', `c'. */ | |
402 | |
403 t1 = (FT_ULong)( ( a >= 0 ) ? a : -a ); | |
404 t2 = (FT_ULong)( ( b >= 0 ) ? b : -b ); | |
405 t1 |= t2; | |
406 t2 = (FT_ULong)( ( c >= 0 ) ? c : -c ); | |
407 t1 |= t2; | |
408 | |
409 /* Now we can be sure that the most significant bit of `t1' */ | |
410 /* is the most significant bit of either `a', `b', or `c', */ | |
411 /* depending on the greatest integer range of the particular */ | |
412 /* variable. */ | |
413 /* */ | |
414 /* Next, we compute the `shift', by shifting `t1' as many */ | |
415 /* times as necessary to move its MSB to position 23. This */ | |
416 /* corresponds to a value of `t1' that is in the range */ | |
417 /* 0x40_0000..0x7F_FFFF. */ | |
418 /* */ | |
419 /* Finally, we shift `a', `b', and `c' by the same amount. */ | |
420 /* This ensures that all values are now in the range */ | |
421 /* -2^23..2^23, i.e., they are now expressed as 8.16 */ | |
422 /* fixed-float numbers. This also means that we are using */ | |
423 /* 24 bits of precision to compute the zeros, independently */ | |
424 /* of the range of the original polynomial coefficients. */ | |
425 /* */ | |
426 /* This algorithm should ensure reasonably accurate values */ | |
427 /* for the zeros. Note that they are only expressed with */ | |
428 /* 16 bits when computing the extrema (the zeros need to */ | |
429 /* be in 0..1 exclusive to be considered part of the arc). */ | |
430 | |
431 if ( t1 == 0 ) /* all coefficients are 0! */ | |
432 return; | |
433 | |
434 if ( t1 > 0x7FFFFFUL ) | |
435 { | |
436 do | |
437 { | |
438 shift++; | |
439 t1 >>= 1; | |
440 | |
441 } while ( t1 > 0x7FFFFFUL ); | |
442 | |
443 /* this loses some bits of precision, but we use 24 of them */ | |
444 /* for the computation anyway */ | |
445 a >>= shift; | |
446 b >>= shift; | |
447 c >>= shift; | |
448 } | |
449 else if ( t1 < 0x400000UL ) | |
450 { | |
451 do | |
452 { | |
453 shift++; | |
454 t1 <<= 1; | |
455 | |
456 } while ( t1 < 0x400000UL ); | |
457 | |
458 a <<= shift; | |
459 b <<= shift; | |
460 c <<= shift; | |
461 } | |
462 } | 449 } |
463 | 450 |
464 /* handle a == 0 */ | 451 /* handle a == 0 */ |
465 if ( a == 0 ) | 452 if ( a == 0 ) |
466 { | 453 { |
467 if ( b != 0 ) | 454 if ( b != 0 ) |
468 { | 455 { |
469 t = - FT_DivFix( c, b ) / 2; | 456 t = - FT_DivFix( c, b ) / 2; |
470 test_cubic_extrema( y1, y2, y3, y4, t, min, max ); | 457 test_cubic_extrema( y1, y2, y3, y4, t, min, max ); |
471 } | 458 } |
(...skipping 102 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
574 FT_Outline_Get_BBox( FT_Outline* outline, | 561 FT_Outline_Get_BBox( FT_Outline* outline, |
575 FT_BBox *abbox ) | 562 FT_BBox *abbox ) |
576 { | 563 { |
577 FT_BBox cbox; | 564 FT_BBox cbox; |
578 FT_BBox bbox; | 565 FT_BBox bbox; |
579 FT_Vector* vec; | 566 FT_Vector* vec; |
580 FT_UShort n; | 567 FT_UShort n; |
581 | 568 |
582 | 569 |
583 if ( !abbox ) | 570 if ( !abbox ) |
584 return FT_Err_Invalid_Argument; | 571 return FT_THROW( Invalid_Argument ); |
585 | 572 |
586 if ( !outline ) | 573 if ( !outline ) |
587 return FT_Err_Invalid_Outline; | 574 return FT_THROW( Invalid_Outline ); |
588 | 575 |
589 /* if outline is empty, return (0,0,0,0) */ | 576 /* if outline is empty, return (0,0,0,0) */ |
590 if ( outline->n_points == 0 || outline->n_contours <= 0 ) | 577 if ( outline->n_points == 0 || outline->n_contours <= 0 ) |
591 { | 578 { |
592 abbox->xMin = abbox->xMax = 0; | 579 abbox->xMin = abbox->xMax = 0; |
593 abbox->yMin = abbox->yMax = 0; | 580 abbox->yMin = abbox->yMax = 0; |
594 return 0; | 581 return 0; |
595 } | 582 } |
596 | 583 |
597 /* We compute the control box as well as the bounding box of */ | 584 /* We compute the control box as well as the bounding box of */ |
(...skipping 55 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
653 *abbox = user.bbox; | 640 *abbox = user.bbox; |
654 } | 641 } |
655 else | 642 else |
656 *abbox = bbox; | 643 *abbox = bbox; |
657 | 644 |
658 return FT_Err_Ok; | 645 return FT_Err_Ok; |
659 } | 646 } |
660 | 647 |
661 | 648 |
662 /* END */ | 649 /* END */ |
OLD | NEW |