XFA: merge patch from CL 817753002
[pdfium.git] / core / src / fxge / fx_freetype / fxft2.5.01 / src / base / ftbbox.c
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
550 FT_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 */