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>
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
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
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
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
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
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 *= 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;
321 q3 = q3 + q2;
322 q4 = ( q4 + q3 ) >> 3;
323 q3 = q3 >> 2;
324 q2 = q2 >> 1;
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 ) >> 3;
334 q2 = q2 >> 2;
335 q3 = q3 >> 1;
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
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
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
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 */