1/***************************************************************************/
2/*                                                                         */
3/*  ftbbox.c                                                               */
4/*                                                                         */
5/*    FreeType bbox computation (body).                                    */
6/*                                                                         */
7/*  Copyright 1996-2002, 2004, 2006, 2010, 2013 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 "../../include/ft2build.h"
28#include "../../include/freetype/internal/ftdebug.h"
29
30#include "../../include/freetype/ftbbox.h"
31#include "../../include/freetype/ftimage.h"
32#include "../../include/freetype/ftoutln.h"
33#include "../../include/freetype/internal/ftcalc.h"
34#include "../../include/freetype/internal/ftobjs.h"
35
36
37  typedef struct  TBBox_Rec_
38  {
39    FT_Vector  last;
40    FT_BBox    bbox;
41
42  } TBBox_Rec;
43
44
45  /*************************************************************************/
46  /*                                                                       */
47  /* <Function>                                                            */
48  /*    BBox_Move_To                                                       */
49  /*                                                                       */
50  /* <Description>                                                         */
51  /*    This function is used as a `move_to' and `line_to' emitter during  */
52  /*    FT_Outline_Decompose().  It simply records the destination point   */
53  /*    in `user->last'; no further computations are necessary since we    */
54  /*    use the cbox as the starting bbox which must be refined.           */
55  /*                                                                       */
56  /* <Input>                                                               */
57  /*    to   :: A pointer to the destination vector.                       */
58  /*                                                                       */
59  /* <InOut>                                                               */
60  /*    user :: A pointer to the current walk context.                     */
61  /*                                                                       */
62  /* <Return>                                                              */
63  /*    Always 0.  Needed for the interface only.                          */
64  /*                                                                       */
65  static int
66  BBox_Move_To( FT_Vector*  to,
67                TBBox_Rec*  user )
68  {
69    user->last = *to;
70
71    return 0;
72  }
73
74
75#define CHECK_X( p, bbox )  \
76          ( p->x < bbox.xMin || p->x > bbox.xMax )
77
78#define CHECK_Y( p, bbox )  \
79          ( p->y < bbox.yMin || p->y > bbox.yMax )
80
81
82  /*************************************************************************/
83  /*                                                                       */
84  /* <Function>                                                            */
85  /*    BBox_Conic_Check                                                   */
86  /*                                                                       */
87  /* <Description>                                                         */
88  /*    Finds the extrema of a 1-dimensional conic Bezier curve and update */
89  /*    a bounding range.  This version uses direct computation, as it     */
90  /*    doesn't need square roots.                                         */
91  /*                                                                       */
92  /* <Input>                                                               */
93  /*    y1  :: The start coordinate.                                       */
94  /*                                                                       */
95  /*    y2  :: The coordinate of the control point.                        */
96  /*                                                                       */
97  /*    y3  :: The end coordinate.                                         */
98  /*                                                                       */
99  /* <InOut>                                                               */
100  /*    min :: The address of the current minimum.                         */
101  /*                                                                       */
102  /*    max :: The address of the current maximum.                         */
103  /*                                                                       */
104  static void
105  BBox_Conic_Check( FT_Pos   y1,
106                    FT_Pos   y2,
107                    FT_Pos   y3,
108                    FT_Pos*  min,
109                    FT_Pos*  max )
110  {
111    if ( y1 <= y3 && y2 == y1 )     /* flat arc */
112      goto Suite;
113
114    if ( y1 < y3 )
115    {
116      if ( y2 >= y1 && y2 <= y3 )   /* ascending arc */
117        goto Suite;
118    }
119    else
120    {
121      if ( y2 >= y3 && y2 <= y1 )   /* descending arc */
122      {
123        y2 = y1;
124        y1 = y3;
125        y3 = y2;
126        goto Suite;
127      }
128    }
129
130    y1 = y3 = y1 - FT_MulDiv( y2 - y1, y2 - y1, y1 - 2*y2 + y3 );
131
132  Suite:
133    if ( y1 < *min ) *min = y1;
134    if ( y3 > *max ) *max = y3;
135  }
136
137
138  /*************************************************************************/
139  /*                                                                       */
140  /* <Function>                                                            */
141  /*    BBox_Conic_To                                                      */
142  /*                                                                       */
143  /* <Description>                                                         */
144  /*    This function is used as a `conic_to' emitter during               */
145  /*    FT_Outline_Decompose().  It checks a conic Bezier curve with the   */
146  /*    current bounding box, and computes its extrema if necessary to     */
147  /*    update it.                                                         */
148  /*                                                                       */
149  /* <Input>                                                               */
150  /*    control :: A pointer to a control point.                           */
151  /*                                                                       */
152  /*    to      :: A pointer to the destination vector.                    */
153  /*                                                                       */
154  /* <InOut>                                                               */
155  /*    user    :: The address of the current walk context.                */
156  /*                                                                       */
157  /* <Return>                                                              */
158  /*    Always 0.  Needed for the interface only.                          */
159  /*                                                                       */
160  /* <Note>                                                                */
161  /*    In the case of a non-monotonous arc, we compute directly the       */
162  /*    extremum coordinates, as it is sufficiently fast.                  */
163  /*                                                                       */
164  static int
165  BBox_Conic_To( FT_Vector*  control,
166                 FT_Vector*  to,
167                 TBBox_Rec*  user )
168  {
169    /* we don't need to check `to' since it is always an `on' point, thus */
170    /* within the bbox                                                    */
171
172    if ( CHECK_X( control, user->bbox ) )
173      BBox_Conic_Check( user->last.x,
174                        control->x,
175                        to->x,
176                        &user->bbox.xMin,
177                        &user->bbox.xMax );
178
179    if ( CHECK_Y( control, user->bbox ) )
180      BBox_Conic_Check( user->last.y,
181                        control->y,
182                        to->y,
183                        &user->bbox.yMin,
184                        &user->bbox.yMax );
185
186    user->last = *to;
187
188    return 0;
189  }
190
191
192  /*************************************************************************/
193  /*                                                                       */
194  /* <Function>                                                            */
195  /*    BBox_Cubic_Check                                                   */
196  /*                                                                       */
197  /* <Description>                                                         */
198  /*    Finds the extrema of a 1-dimensional cubic Bezier curve and        */
199  /*    updates a bounding range.  This version uses splitting because we  */
200  /*    don't want to use square roots and extra accuracy.                 */
201  /*                                                                       */
202  /* <Input>                                                               */
203  /*    p1  :: The start coordinate.                                       */
204  /*                                                                       */
205  /*    p2  :: The coordinate of the first control point.                  */
206  /*                                                                       */
207  /*    p3  :: The coordinate of the second control point.                 */
208  /*                                                                       */
209  /*    p4  :: The end coordinate.                                         */
210  /*                                                                       */
211  /* <InOut>                                                               */
212  /*    min :: The address of the current minimum.                         */
213  /*                                                                       */
214  /*    max :: The address of the current maximum.                         */
215  /*                                                                       */
216
217#if 0
218
219  static void
220  BBox_Cubic_Check( FT_Pos   p1,
221                    FT_Pos   p2,
222                    FT_Pos   p3,
223                    FT_Pos   p4,
224                    FT_Pos*  min,
225                    FT_Pos*  max )
226  {
227    FT_Pos  q1, q2, q3, q4;
228
229
230    q1 = p1;
231    q2 = p2;
232    q3 = p3;
233    q4 = p4;
234
235    /* for a conic segment to possibly reach new maximum     */
236    /* one of its off-points must be above the current value */
237    while ( q2 > *max || q3 > *max )
238    {
239      /* determine which half contains the maximum and split */
240      if ( q1 + q2 > q3 + q4 ) /* first half */
241      {
242        q4 = q4 + q3;
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;
250      }
251      else                     /* second half */
252      {
253        q1 = q1 + q2;
254        q2 = q2 + q3;
255        q3 = q3 + q4;
256        q1 = q1 + q2;
257        q2 = q2 + q3;
258        q1 = ( q1 + q2 ) / 8;
259        q2 = q2 / 4;
260        q3 = q3 / 2;
261      }
262
263      /* check if either end reached the maximum */
264      if ( q1 == q2 && q1 >= q3 )
265      {
266        *max = q1;
267        break;
268      }
269      if ( q3 == q4 && q2 <= q4 )
270      {
271        *max = q4;
272        break;
273      }
274    }
275
276    q1 = p1;
277    q2 = p2;
278    q3 = p3;
279    q4 = p4;
280
281    /* for a conic segment to possibly reach new minimum     */
282    /* one of its off-points must be below the current value */
283    while ( q2 < *min || q3 < *min )
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      }
308
309      /* check if either end reached the minimum */
310      if ( q1 == q2 && q1 <= q3 )
311      {
312        *min = q1;
313        break;
314      }
315      if ( q3 == q4 && q2 >= q4 )
316      {
317        *min = q4;
318        break;
319      }
320    }
321  }
322
323#else
324
325  static void
326  test_cubic_extrema( FT_Pos    y1,
327                      FT_Pos    y2,
328                      FT_Pos    y3,
329                      FT_Pos    y4,
330                      FT_Fixed  u,
331                      FT_Pos*   min,
332                      FT_Pos*   max )
333  {
334 /* FT_Pos    a = y4 - 3*y3 + 3*y2 - y1; */
335    FT_Pos    b = y3 - 2*y2 + y1;
336    FT_Pos    c = y2 - y1;
337    FT_Pos    d = y1;
338    FT_Pos    y;
339    FT_Fixed  uu;
340
341    FT_UNUSED ( y4 );
342
343
344    /* The polynomial is                      */
345    /*                                        */
346    /*    P(x) = a*x^3 + 3b*x^2 + 3c*x + d  , */
347    /*                                        */
348    /*   dP/dx = 3a*x^2 + 6b*x + 3c         . */
349    /*                                        */
350    /* However, we also have                  */
351    /*                                        */
352    /*   dP/dx(u) = 0                       , */
353    /*                                        */
354    /* which implies by subtraction that      */
355    /*                                        */
356    /*   P(u) = b*u^2 + 2c*u + d            . */
357
358    if ( u > 0 && u < 0x10000L )
359    {
360      uu = FT_MulFix( u, u );
361      y  = d + FT_MulFix( c, 2*u ) + FT_MulFix( b, uu );
362
363      if ( y < *min ) *min = y;
364      if ( y > *max ) *max = y;
365    }
366  }
367
368
369  static void
370  BBox_Cubic_Check( FT_Pos   y1,
371                    FT_Pos   y2,
372                    FT_Pos   y3,
373                    FT_Pos   y4,
374                    FT_Pos*  min,
375                    FT_Pos*  max )
376  {
377    /* always compare first and last points */
378    if      ( y1 < *min )  *min = y1;
379    else if ( y1 > *max )  *max = y1;
380
381    if      ( y4 < *min )  *min = y4;
382    else if ( y4 > *max )  *max = y4;
383
384    /* now, try to see if there are split points here */
385    if ( y1 <= y4 )
386    {
387      /* flat or ascending arc test */
388      if ( y1 <= y2 && y2 <= y4 && y1 <= y3 && y3 <= y4 )
389        return;
390    }
391    else /* y1 > y4 */
392    {
393      /* descending arc test */
394      if ( y1 >= y2 && y2 >= y4 && y1 >= y3 && y3 >= y4 )
395        return;
396    }
397
398    /* There are some split points.  Find them.                        */
399    /* We already made sure that a, b, and c below cannot be all zero. */
400    {
401      FT_Pos    a = y4 - 3*y3 + 3*y2 - y1;
402      FT_Pos    b = y3 - 2*y2 + y1;
403      FT_Pos    c = y2 - y1;
404      FT_Pos    d;
405      FT_Fixed  t;
406      FT_Int    shift;
407
408
409      /* We need to solve `ax^2+2bx+c' here, without floating points!      */
410      /* The trick is to normalize to a different representation in order  */
411      /* to use our 16.16 fixed-point routines.                            */
412      /*                                                                   */
413      /* We compute FT_MulFix(b,b) and FT_MulFix(a,c) after normalization. */
414      /* These values must fit into a single 16.16 value.                  */
415      /*                                                                   */
416      /* We normalize a, b, and c to `8.16' fixed-point values to ensure   */
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).                                */
429
430      shift = FT_MSB( FT_ABS( a ) | FT_ABS( b ) | FT_ABS( c ) );
431
432      if ( shift > 22 )
433      {
434        shift -= 22;
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;
445
446        a <<= shift;
447        b <<= shift;
448        c <<= shift;
449      }
450
451      /* handle a == 0 */
452      if ( a == 0 )
453      {
454        if ( b != 0 )
455        {
456          t = - FT_DivFix( c, b ) / 2;
457          test_cubic_extrema( y1, y2, y3, y4, t, min, max );
458        }
459      }
460      else
461      {
462        /* solve the equation now */
463        d = FT_MulFix( b, b ) - FT_MulFix( a, c );
464        if ( d < 0 )
465          return;
466
467        if ( d == 0 )
468        {
469          /* there is a single split point at -b/a */
470          t = - FT_DivFix( b, a );
471          test_cubic_extrema( y1, y2, y3, y4, t, min, max );
472        }
473        else
474        {
475          /* there are two solutions; we need to filter them */
476          d = FT_SqrtFixed( (FT_Int32)d );
477          t = - FT_DivFix( b - d, a );
478          test_cubic_extrema( y1, y2, y3, y4, t, min, max );
479
480          t = - FT_DivFix( b + d, a );
481          test_cubic_extrema( y1, y2, y3, y4, t, min, max );
482        }
483      }
484    }
485  }
486
487#endif
488
489
490  /*************************************************************************/
491  /*                                                                       */
492  /* <Function>                                                            */
493  /*    BBox_Cubic_To                                                      */
494  /*                                                                       */
495  /* <Description>                                                         */
496  /*    This function is used as a `cubic_to' emitter during               */
497  /*    FT_Outline_Decompose().  It checks a cubic Bezier curve with the   */
498  /*    current bounding box, and computes its extrema if necessary to     */
499  /*    update it.                                                         */
500  /*                                                                       */
501  /* <Input>                                                               */
502  /*    control1 :: A pointer to the first control point.                  */
503  /*                                                                       */
504  /*    control2 :: A pointer to the second control point.                 */
505  /*                                                                       */
506  /*    to       :: A pointer to the destination vector.                   */
507  /*                                                                       */
508  /* <InOut>                                                               */
509  /*    user     :: The address of the current walk context.               */
510  /*                                                                       */
511  /* <Return>                                                              */
512  /*    Always 0.  Needed for the interface only.                          */
513  /*                                                                       */
514  /* <Note>                                                                */
515  /*    In the case of a non-monotonous arc, we don't compute directly     */
516  /*    extremum coordinates, we subdivide instead.                        */
517  /*                                                                       */
518  static int
519  BBox_Cubic_To( FT_Vector*  control1,
520                 FT_Vector*  control2,
521                 FT_Vector*  to,
522                 TBBox_Rec*  user )
523  {
524    /* we don't need to check `to' since it is always an `on' point, thus */
525    /* within the bbox                                                    */
526
527    if ( CHECK_X( control1, user->bbox ) ||
528         CHECK_X( control2, user->bbox ) )
529      BBox_Cubic_Check( user->last.x,
530                        control1->x,
531                        control2->x,
532                        to->x,
533                        &user->bbox.xMin,
534                        &user->bbox.xMax );
535
536    if ( CHECK_Y( control1, user->bbox ) ||
537         CHECK_Y( control2, user->bbox ) )
538      BBox_Cubic_Check( user->last.y,
539                        control1->y,
540                        control2->y,
541                        to->y,
542                        &user->bbox.yMin,
543                        &user->bbox.yMax );
544
545    user->last = *to;
546
547    return 0;
548  }
549
550FT_DEFINE_OUTLINE_FUNCS(bbox_interface,
551    (FT_Outline_MoveTo_Func) BBox_Move_To,
552    (FT_Outline_LineTo_Func) BBox_Move_To,
553    (FT_Outline_ConicTo_Func)BBox_Conic_To,
554    (FT_Outline_CubicTo_Func)BBox_Cubic_To,
555    0, 0
556  )
557
558  /* documentation is in ftbbox.h */
559
560  FT_EXPORT_DEF( FT_Error )
561  FT_Outline_Get_BBox( FT_Outline*  outline,
562                       FT_BBox     *abbox )
563  {
564    FT_BBox     cbox;
565    FT_BBox     bbox;
566    FT_Vector*  vec;
567    FT_UShort   n;
568
569
570    if ( !abbox )
571      return FT_THROW( Invalid_Argument );
572
573    if ( !outline )
574      return FT_THROW( Invalid_Outline );
575
576    /* if outline is empty, return (0,0,0,0) */
577    if ( outline->n_points == 0 || outline->n_contours <= 0 )
578    {
579      abbox->xMin = abbox->xMax = 0;
580      abbox->yMin = abbox->yMax = 0;
581      return 0;
582    }
583
584    /* We compute the control box as well as the bounding box of  */
585    /* all `on' points in the outline.  Then, if the two boxes    */
586    /* coincide, we exit immediately.                             */
587
588    vec = outline->points;
589    bbox.xMin = bbox.xMax = cbox.xMin = cbox.xMax = vec->x;
590    bbox.yMin = bbox.yMax = cbox.yMin = cbox.yMax = vec->y;
591    vec++;
592
593    for ( n = 1; n < outline->n_points; n++ )
594    {
595      FT_Pos  x = vec->x;
596      FT_Pos  y = vec->y;
597
598
599      /* update control box */
600      if ( x < cbox.xMin ) cbox.xMin = x;
601      if ( x > cbox.xMax ) cbox.xMax = x;
602
603      if ( y < cbox.yMin ) cbox.yMin = y;
604      if ( y > cbox.yMax ) cbox.yMax = y;
605
606      if ( FT_CURVE_TAG( outline->tags[n] ) == FT_CURVE_TAG_ON )
607      {
608        /* update bbox for `on' points only */
609        if ( x < bbox.xMin ) bbox.xMin = x;
610        if ( x > bbox.xMax ) bbox.xMax = x;
611
612        if ( y < bbox.yMin ) bbox.yMin = y;
613        if ( y > bbox.yMax ) bbox.yMax = y;
614      }
615
616      vec++;
617    }
618
619    /* test two boxes for equality */
620    if ( cbox.xMin < bbox.xMin || cbox.xMax > bbox.xMax ||
621         cbox.yMin < bbox.yMin || cbox.yMax > bbox.yMax )
622    {
623      /* the two boxes are different, now walk over the outline to */
624      /* get the Bezier arc extrema.                               */
625
626      FT_Error   error;
627      TBBox_Rec  user;
628
629#ifdef FT_CONFIG_OPTION_PIC
630      FT_Outline_Funcs bbox_interface;
631      Init_Class_bbox_interface(&bbox_interface);
632#endif
633
634      user.bbox = bbox;
635
636      error = FT_Outline_Decompose( outline, &bbox_interface, &user );
637      if ( error )
638        return error;
639
640      *abbox = user.bbox;
641    }
642    else
643      *abbox = bbox;
644
645    return FT_Err_Ok;
646  }
647
648
649/* END */
650