Visualization Library 2.0.0-b5

A lightweight C++ OpenGL middleware for 2D/3D graphics

VL     Star     Watch     Fork     Issue

[Download] [Tutorials] [All Classes] [Grouped Classes]
ftbbox.c
Go to the documentation of this file.
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 <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  /*************************************************************************/
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 
562  FT_BBox *abbox )
563  {
564  FT_BBox cbox;
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 */
FT_BEGIN_HEADER FT_Outline_Get_BBox(FT_Outline *outline, FT_BBox *abbox)
#define CHECK_Y(p, bbox)
Definition: ftbbox.c:78
int FT_Error
Definition: fttypes.h:296
FT_DivFix(FT_Long a, FT_Long b)
Definition: ftcalc.c:586
FT_DEFINE_OUTLINE_FUNCS(bbox_interface,(FT_Outline_MoveTo_Func) BBox_Move_To,(FT_Outline_LineTo_Func) BBox_Move_To,(FT_Outline_ConicTo_Func) BBox_Conic_To,(FT_Outline_CubicTo_Func) BBox_Cubic_To, 0, 0) FT_Outline_Get_BBox(FT_Outline *outline
FT_BEGIN_HEADER typedef signed long FT_Pos
Definition: ftimage.h:59
GLboolean GLboolean GLboolean GLboolean a
struct TBBox_Rec_ TBBox_Rec
GLint GLint GLint GLint GLint GLint y
signed int FT_Int
Definition: fttypes.h:216
short n_contours
Definition: ftimage.h:385
#define FT_ABS(a)
Definition: ftobjs.h:73
FT_BBox bbox
Definition: ftbbox.c:565
return FT_THROW(Missing_Property)
#define FT_UNUSED(arg)
Definition: ftconfig.h:76
char * tags
Definition: ftimage.h:389
FT_BBox * abbox
Definition: ftbbox.c:563
GLint GLint GLint GLint GLint x
return FT_Err_Ok
Definition: ftbbox.c:645
#define FT_Outline_ConicTo_Func
Definition: ftimage.h:618
GLboolean GLboolean GLboolean b
#define FT_Outline_MoveTo_Func
Definition: ftimage.h:559
FT_UShort n
Definition: ftbbox.c:567
FT_Pos yMax
Definition: ftimage.h:119
FT_Pos xMin
Definition: ftimage.h:118
#define FT_EXPORT_DEF(x)
Definition: ftconfig.h:32
FT_MulDiv(FT_Long a, FT_Long b, FT_Long c)
Definition: ftcalc.c:412
FT_Error error
Definition: cffdrivr.c:411
FT_Pos x
Definition: ftimage.h:77
float min(float a, float b)
Definition: Vector2.hpp:307
FT_Pos y
Definition: ftimage.h:78
#define CHECK_X(p, bbox)
Definition: ftbbox.c:75
const GLubyte * c
signed int FT_Int32
Definition: ftconfig.h:132
#define FT_Outline_LineTo_Func
Definition: ftimage.h:586
FT_BEGIN_HEADER FT_Outline_Decompose(FT_Outline *outline, const FT_Outline_Funcs *func_interface, void *user)
Definition: ftoutln.c:51
FT_Vector * vec
Definition: ftbbox.c:566
FT_Pos xMax
Definition: ftimage.h:119
short n_points
Definition: ftimage.h:386
FT_BEGIN_HEADER FT_SqrtFixed(FT_Int32 x)
Definition: ftcalc.c:856
local int max
Definition: enough.c:170
FT_MSB(FT_UInt32 z)
Definition: ftcalc.c:104
FT_MulFix(FT_Long a, FT_Long b)
Definition: ftcalc.c:485
signed long FT_Fixed
Definition: fttypes.h:284
#define FT_Outline_CubicTo_Func
Definition: ftimage.h:651
#define FT_CURVE_TAG_ON
Definition: ftimage.h:516
GLdouble GLdouble t
#define FT_CURVE_TAG(flag)
Definition: ftimage.h:514
unsigned short FT_UShort
Definition: fttypes.h:205
FT_Pos yMin
Definition: ftimage.h:118
FT_Vector * points
Definition: ftimage.h:388