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