ReactOS  0.4.13-dev-563-g0561610
ftbbox.c
Go to the documentation of this file.
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  {
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
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
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
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
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
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
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
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 
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 
442  FT_BBox *abbox )
443  {
444  FT_BBox cbox = { 0x7FFFFFFFL, 0x7FFFFFFFL,
445  -0x7FFFFFFFL, -0x7FFFFFFFL };
446  FT_BBox bbox = { 0x7FFFFFFFL, 0x7FFFFFFFL,
447  -0x7FFFFFFFL, -0x7FFFFFFFL };
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 */
_In_ CLIPOBJ _In_ BRUSHOBJ _In_ LONG _In_ LONG y1
Definition: winddi.h:3706
FT_BEGIN_HEADER FT_Outline_Get_BBox(FT_Outline *outline, FT_BBox *abbox)
#define CHECK_Y(p, bbox)
Definition: ftbbox.c:60
static int BBox_Move_To(FT_Vector *to, TBBox_Rec *user)
Definition: ftbbox.c:85
int FT_Error
Definition: fttypes.h:300
#define max(a, b)
Definition: svc.c:63
FT_Pos y
Definition: ftimage.h:77
#define shift
Definition: input.c:1668
FT_BEGIN_HEADER typedef signed long FT_Pos
Definition: ftimage.h:58
#define error(str)
Definition: mkdosfs.c:1605
static FT_Pos cubic_peak(FT_Pos q1, FT_Pos q2, FT_Pos q3, FT_Pos q4)
Definition: ftbbox.c:250
static void BBox_Conic_Check(FT_Pos y1, FT_Pos y2, FT_Pos y3, FT_Pos *min, FT_Pos *max)
Definition: ftbbox.c:149
FT_BBox bbox
Definition: ftbbox.c:40
struct TBBox_Rec_ TBBox_Rec
FT_Pos x
Definition: ftimage.h:76
signed int FT_Int
Definition: fttypes.h:220
#define FT_ABS(a)
Definition: ftobjs.h:74
FT_BBox bbox
Definition: ftbbox.c:446
#define FT_UPDATE_BBOX(p, bbox)
Definition: ftbbox.c:45
GLdouble n
Definition: glext.h:7729
static int BBox_Line_To(FT_Vector *to, TBBox_Rec *user)
Definition: ftbbox.c:117
FT_BBox * abbox
Definition: ftbbox.c:443
return FT_Err_Ok
Definition: ftbbox.c:511
#define FT_Outline_ConicTo_Func
Definition: ftimage.h:555
#define FT_THROW(e)
Definition: ftdebug.h:213
#define FT_Outline_MoveTo_Func
Definition: ftimage.h:496
FT_Vector last
Definition: ftbbox.c:39
FT_Pos yMax
Definition: ftimage.h:118
FT_UShort n
Definition: ftbbox.c:449
FT_MulDiv(FT_Long a, FT_Long b, FT_Long c)
Definition: ftcalc.c:416
FT_Pos xMin
Definition: ftimage.h:117
#define CHECK_X(p, bbox)
Definition: ftbbox.c:57
FT_Pos xMax
Definition: ftimage.h:118
static int BBox_Cubic_To(FT_Vector *control1, FT_Vector *control2, FT_Vector *to, TBBox_Rec *user)
Definition: ftbbox.c:393
#define FT_Outline_LineTo_Func
Definition: ftimage.h:523
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:448
static const WCHAR L[]
Definition: oid.c:1250
FT_MSB(FT_UInt32 z)
Definition: ftcalc.c:114
_In_ CLIPOBJ _In_ BRUSHOBJ _In_ LONG _In_ LONG _In_ LONG _In_ LONG y2
Definition: winddi.h:3706
Definition: mesh.c:5329
#define FT_EXPORT_DEF(x)
Definition: ftconfig.h:483
FT_Pos yMin
Definition: ftimage.h:117
#define min(a, b)
Definition: monoChain.cc:55
#define FT_Outline_CubicTo_Func
Definition: ftimage.h:588
#define FT_CURVE_TAG_ON
Definition: ftimage.h:453
#define FT_CURVE_TAG(flag)
Definition: ftimage.h:451
FT_DEFINE_OUTLINE_FUNCS(bbox_interface,(FT_Outline_MoveTo_Func) BBox_Move_To,(FT_Outline_LineTo_Func) BBox_Line_To,(FT_Outline_ConicTo_Func) BBox_Conic_To,(FT_Outline_CubicTo_Func) BBox_Cubic_To, 0, 0) FT_Outline_Get_BBox(FT_Outline *outline
unsigned short FT_UShort
Definition: fttypes.h:209
static int BBox_Conic_To(FT_Vector *control, FT_Vector *to, TBBox_Rec *user)
Definition: ftbbox.c:198
void user(int argc, const char *argv[])
Definition: cmds.c:1350
static void BBox_Cubic_Check(FT_Pos p1, FT_Pos p2, FT_Pos p3, FT_Pos p4, FT_Pos *min, FT_Pos *max)
Definition: ftbbox.c:343