• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 ::
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
BBox_Move_To(FT_Vector * to,TBBox_Rec * user)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
BBox_Line_To(FT_Vector * to,TBBox_Rec * user)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
BBox_Conic_Check(FT_Pos y1,FT_Pos y2,FT_Pos y3,FT_Pos * min,FT_Pos * max)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
BBox_Conic_To(FT_Vector * control,FT_Vector * to,TBBox_Rec * user)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
cubic_peak(FT_Pos q1,FT_Pos q2,FT_Pos q3,FT_Pos q4)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 <<=  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;
321         q3 = q3 + q2;
322         q4 = ( q4 + q3 ) / 8;
323         q3 = q3 / 4;
324         q2 = q2 / 2;
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 ) / 8;
334         q2 = q2 / 4;
335         q3 = q3 / 2;
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
BBox_Cubic_Check(FT_Pos p1,FT_Pos p2,FT_Pos p3,FT_Pos p4,FT_Pos * min,FT_Pos * max)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
BBox_Cubic_To(FT_Vector * control1,FT_Vector * control2,FT_Vector * to,TBBox_Rec * user)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 
FT_EXPORT_DEF(FT_Error)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 */
532