1 /****************************************************************************
2 *
3 * ftbbox.c
4 *
5 * FreeType bbox computation (body).
6 *
7 * Copyright (C) 1996-2019 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>
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;
|
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 <ft2build.h>
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 *= 1 << shift;
298 q2 *= 1 << shift;
299 q3 *= 1 << shift;
300 q4 *= 1 << 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;
|