w32tex
About: TeX Live provides a comprehensive TeX system including all the major TeX-related programs, macro packages, and fonts that are free software. Windows sources.
  Fossies Dox: w32tex-src.tar.xz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

ftbbox.c
Go to the documentation of this file.
1 /****************************************************************************
2  *
3  * ftbbox.c
4  *
5  * FreeType bbox computation (body).
6  *
7  * Copyright (C) 1996-2020 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 <freetype/internal/ftdebug.h>
28 
29 #include <freetype/ftbbox.h>
30 #include <freetype/ftimage.h>
31 #include <freetype/ftoutln.h>
32 #include <freetype/internal/ftcalc.h>
33 #include <freetype/internal/ftobjs.h>
34 
35 
36  typedef struct TBBox_Rec_
37  {
40 
42 
43 
44 #define FT_UPDATE_BBOX( p, bbox ) \
45  FT_BEGIN_STMNT \
46  if ( p->x < bbox.xMin ) \
47  bbox.xMin = p->x; \
48  if ( p->x > bbox.xMax ) \
49  bbox.xMax = p->x; \
50  if ( p->y < bbox.yMin ) \
51  bbox.yMin = p->y; \
52  if ( p->y > bbox.yMax ) \
53  bbox.yMax = p->y; \
54  FT_END_STMNT
55 
56 #define CHECK_X( p, bbox ) \
57  ( p->x < bbox.xMin || p->x > bbox.xMax )
58 
59 #define CHECK_Y( p, bbox ) \
60  ( p->y < bbox.yMin || p->y > bbox.yMax )
61 
62 
63  /**************************************************************************
64  *
65  * @Function:
66  * BBox_Move_To
67  *
68  * @Description:
69  * This function is used as a `move_to' emitter during
70  * FT_Outline_Decompose(). It simply records the destination point
71  * in `user->last'. We also update bbox in case contour starts with
72  * an implicit `on' point.
73  *
74  * @Input:
75  * to ::
76  * A pointer to the destination vector.
77  *
78  * @InOut:
79  * user ::
80  * A pointer to the current walk context.
81  *
82  * @Return:
83  * Always 0. Needed for the interface only.
84  */
85  static int
87  TBBox_Rec* user )
88  {
89  FT_UPDATE_BBOX( to, user->bbox );
90 
91  user->last = *to;
92 
93  return 0;
94  }
95 
96 
97  /**************************************************************************
98  *
99  * @Function:
100  * BBox_Line_To
101  *
102  * @Description:
103  * This function is used as a `line_to' emitter during
104  * FT_Outline_Decompose(). It simply records the destination point
105  * in `user->last'; no further computations are necessary because
106  * bbox already contains both explicit ends of the line segment.
107  *
108  * @Input:
109  * to ::
110  * A pointer to the destination vector.
111  *
112  * @InOut:
113  * user ::
114  * A pointer to the current walk context.
115  *
116  * @Return:
117  * Always 0. Needed for the interface only.
118  */
119  static int
121  TBBox_Rec* user )
122  {
123  user->last = *to;
124 
125  return 0;
126  }
127 
128 
129  /**************************************************************************
130  *
131  * @Function:
132  * BBox_Conic_Check
133  *
134  * @Description:
135  * Find the extrema of a 1-dimensional conic Bezier curve and update
136  * a bounding range. This version uses direct computation, as it
137  * doesn't need square roots.
138  *
139  * @Input:
140  * y1 ::
141  * The start coordinate.
142  *
143  * y2 ::
144  * The coordinate of the control point.
145  *
146  * y3 ::
147  * The end coordinate.
148  *
149  * @InOut:
150  * min ::
151  * The address of the current minimum.
152  *
153  * max ::
154  * The address of the current maximum.
155  */
156  static void
158  FT_Pos y2,
159  FT_Pos y3,
160  FT_Pos* min,
161  FT_Pos* max )
162  {
163  /* This function is only called when a control off-point is outside */
164  /* the bbox that contains all on-points. It finds a local extremum */
165  /* within the segment, equal to (y1*y3 - y2*y2)/(y1 - 2*y2 + y3). */
166  /* Or, offsetting from y2, we get */
167 
168  y1 -= y2;
169  y3 -= y2;
170  y2 += FT_MulDiv( y1, y3, y1 + y3 );
171 
172  if ( y2 < *min )
173  *min = y2;
174  if ( y2 > *max )
175  *max = y2;
176  }
177 
178 
179  /**************************************************************************
180  *
181  * @Function:
182  * BBox_Conic_To
183  *
184  * @Description:
185  * This function is used as a `conic_to' emitter during
186  * FT_Outline_Decompose(). It checks a conic Bezier curve with the
187  * current bounding box, and computes its extrema if necessary to
188  * update it.
189  *
190  * @Input:
191  * control ::
192  * A pointer to a control point.
193  *
194  * to ::
195  * A pointer to the destination vector.
196  *
197  * @InOut:
198  * user ::
199  * The address of the current walk context.
200  *
201  * @Return:
202  * Always 0. Needed for the interface only.
203  *
204  * @Note:
205  * In the case of a non-monotonous arc, we compute directly the
206  * extremum coordinates, as it is sufficiently fast.
207  */
208  static int
210  FT_Vector* to,
211  TBBox_Rec* user )
212  {
213  /* in case `to' is implicit and not included in bbox yet */
214  FT_UPDATE_BBOX( to, user->bbox );
215 
216  if ( CHECK_X( control, user->bbox ) )
217  BBox_Conic_Check( user->last.x,
218  control->x,
219  to->x,
220  &user->bbox.xMin,
221  &user->bbox.xMax );
222 
223  if ( CHECK_Y( control, user->bbox ) )
224  BBox_Conic_Check( user->last.y,
225  control->y,
226  to->y,
227  &user->bbox.yMin,
228  &user->bbox.yMax );
229 
230  user->last = *to;
231 
232  return 0;
233  }
234 
235 
236  /**************************************************************************
237  *
238  * @Function:
239  * BBox_Cubic_Check
240  *
241  * @Description:
242  * Find the extrema of a 1-dimensional cubic Bezier curve and
243  * update a bounding range. This version uses iterative splitting
244  * because it is faster than the exact solution with square roots.
245  *
246  * @Input:
247  * p1 ::
248  * The start coordinate.
249  *
250  * p2 ::
251  * The coordinate of the first control point.
252  *
253  * p3 ::
254  * The coordinate of the second control point.
255  *
256  * p4 ::
257  * The end coordinate.
258  *
259  * @InOut:
260  * min ::
261  * The address of the current minimum.
262  *
263  * max ::
264  * The address of the current maximum.
265  */
266  static FT_Pos
268  FT_Pos q2,
269  FT_Pos q3,
270  FT_Pos q4 )
271  {
272  FT_Pos peak = 0;
273  FT_Int shift;
274 
275 
276  /* This function finds a peak of a cubic segment if it is above 0 */
277  /* using iterative bisection of the segment, or returns 0. */
278  /* The fixed-point arithmetic of bisection is inherently stable */
279  /* but may loose accuracy in the two lowest bits. To compensate, */
280  /* we upscale the segment if there is room. Large values may need */
281  /* to be downscaled to avoid overflows during bisection. */
282  /* It is called with either q2 or q3 positive, which is necessary */
283  /* for the peak to exist and avoids undefined FT_MSB. */
284 
285  shift = 27 - FT_MSB( (FT_UInt32)( FT_ABS( q1 ) |
286  FT_ABS( q2 ) |
287  FT_ABS( q3 ) |
288  FT_ABS( q4 ) ) );
289 
290  if ( shift > 0 )
291  {
292  /* upscaling too much just wastes time */
293  if ( shift > 2 )
294  shift = 2;
295 
296  q1 *= 1 << shift;
297  q2 *= 1 << shift;
298  q3 *= 1 << shift;
299  q4 *= 1 << shift;
300  }
301  else
302  {
303  q1 >>= -shift;
304  q2 >>= -shift;
305  q3 >>= -shift;
306  q4 >>= -shift;
307  }
308 
309  /* for a peak to exist above 0, the cubic segment must have */
310  /* at least one of its control off-points above 0. */
311  while ( q2 > 0 || q3 > 0 )
312  {
313  /* determine which half contains the maximum and split */
314  if ( q1 + q2 > q3 + q4 ) /* first half */
315  {
316  q4 = q4 + q3;
317  q3 = q3 + q2;
318  q2 = q2 + q1;
319  q4 = q4 + q3;
320  q3 = q3 + q2;
321  q4 = ( q4 + q3 ) >> 3;
322  q3 = q3 >> 2;
323  q2 = q2 >> 1;
324  }
325  else /* second half */
326  {
327  q1 = q1 + q2;
328  q2 = q2 + q3;
329  q3 = q3 + q4;
330  q1 = q1 + q2;
331  q2 = q2 + q3;
332  q1 = ( q1 + q2 ) >> 3;
333  q2 = q2 >> 2;
334  q3 = q3 >> 1;
335  }
336 
337  /* check whether either end reached the maximum */
338  if ( q1 == q2 && q1 >= q3 )
339  {
340  peak = q1;
341  break;
342  }
343  if ( q3 == q4 && q2 <= q4 )
344  {
345  peak = q4;
346  break;
347  }
348  }
349 
350  if ( shift > 0 )
351  peak >>= shift;
352  else
353  peak <<= -shift;
354 
355  return peak;
356  }
357 
358 
359  static void
361  FT_Pos p2,
362  FT_Pos p3,
363  FT_Pos p4,
364  FT_Pos* min,
365  FT_Pos* max )
366  {
367  /* This function is only called when a control off-point is outside */
368  /* the bbox that contains all on-points. So at least one of the */
369  /* conditions below holds and cubic_peak is called with at least one */
370  /* non-zero argument. */
371 
372  if ( p2 > *max || p3 > *max )
373  *max += cubic_peak( p1 - *max, p2 - *max, p3 - *max, p4 - *max );
374 
375  /* now flip the signs to update the minimum */
376  if ( p2 < *min || p3 < *min )
377  *min -= cubic_peak( *min - p1, *min - p2, *min - p3, *min - p4 );
378  }
379 
380 
381  /**************************************************************************
382  *
383  * @Function:
384  * BBox_Cubic_To
385  *
386  * @Description:
387  * This function is used as a `cubic_to' emitter during
388  * FT_Outline_Decompose(). It checks a cubic Bezier curve with the
389  * current bounding box, and computes its extrema if necessary to
390  * update it.
391  *
392  * @Input:
393  * control1 ::
394  * A pointer to the first control point.
395  *
396  * control2 ::
397  * A pointer to the second control point.
398  *
399  * to ::
400  * A pointer to the destination vector.
401  *
402  * @InOut:
403  * user ::
404  * The address of the current walk context.
405  *
406  * @Return:
407  * Always 0. Needed for the interface only.
408  *
409  * @Note:
410  * In the case of a non-monotonous arc, we don't compute directly
411  * extremum coordinates, we subdivide instead.
412  */
413  static int
415  FT_Vector* control2,
416  FT_Vector* to,
417  TBBox_Rec* user )
418  {
419  /* We don't need to check `to' since it is always an on-point, */
420  /* thus within the bbox. Only segments with an off-point outside */
421  /* the bbox can possibly reach new extreme values. */
422 
423  if ( CHECK_X( control1, user->bbox ) ||
424  CHECK_X( control2, user->bbox ) )
425  BBox_Cubic_Check( user->last.x,
426  control1->x,
427  control2->x,
428  to->x,
429  &user->bbox.xMin,
430  &user->bbox.xMax );
431 
432  if ( CHECK_Y( control1, user->bbox ) ||
433  CHECK_Y( control2, user->bbox ) )
434  BBox_Cubic_Check( user->last.y,
435  control1->y,
436  control2->y,
437  to->y,
438  &user->bbox.yMin,
439  &user->bbox.yMax );
440 
441  user->last = *to;
442 
443  return 0;
444  }
445 
446 
448  bbox_interface,
449 
450  (FT_Outline_MoveTo_Func) BBox_Move_To, /* move_to */
451  (FT_Outline_LineTo_Func) BBox_Line_To, /* line_to */
452  (FT_Outline_ConicTo_Func)BBox_Conic_To, /* conic_to */
453  (FT_Outline_CubicTo_Func)BBox_Cubic_To, /* cubic_to */
454  0, /* shift */
455  0 /* delta */
456  )
457 
458 
459  /* documentation is in ftbbox.h */
460 
464  {
465  FT_BBox cbox = { 0x7FFFFFFFL, 0x7FFFFFFFL,
466  -0x7FFFFFFFL, -0x7FFFFFFFL };
467  FT_BBox bbox = { 0x7FFFFFFFL, 0x7FFFFFFFL,
468  -0x7FFFFFFFL, -0x7FFFFFFFL };
471 
472 
473  if ( !abbox )
474  return FT_THROW( Invalid_Argument );
475 
476  if ( !outline )
477  return FT_THROW( Invalid_Outline );
478 
479  /* if outline is empty, return (0,0,0,0) */
480  if ( outline->n_points == 0 || outline->n_contours <= 0 )
481  {
482  abbox->xMin = abbox->xMax = 0;
483  abbox->yMin = abbox->yMax = 0;
484 
485  return 0;
486  }
487 
488  /* We compute the control box as well as the bounding box of */
489  /* all `on' points in the outline. Then, if the two boxes */
490  /* coincide, we exit immediately. */
491 
492  vec = outline->points;
493 
494  for ( n = 0; n < outline->n_points; n++ )
495  {
496  FT_UPDATE_BBOX( vec, cbox );
497 
498  if ( FT_CURVE_TAG( outline->tags[n] ) == FT_CURVE_TAG_ON )
499  FT_UPDATE_BBOX( vec, bbox );
500 
501  vec++;
502  }
503 
504  /* test two boxes for equality */
505  if ( cbox.xMin < bbox.xMin || cbox.xMax > bbox.xMax ||
506  cbox.yMin < bbox.yMin || cbox.yMax > bbox.yMax )
507  {
508  /* the two boxes are different, now walk over the outline to */
509  /* get the Bezier arc extrema. */
510 
511  FT_Error error;
512  TBBox_Rec user;
513 
514 
515  user.bbox = bbox;
516 
517  error = FT_Outline_Decompose( outline, &bbox_interface, &user );
518  if ( error )
519  return error;
520 
521  *abbox = user.bbox;
522  }
523  else
524  *abbox = bbox;
525 
526  return FT_Err_Ok;
527  }
528 
529 
530 /* END */
#define y3
char * p2
Definition: bmpfont.h:62
char * p1
Definition: bmpfont.h:62
#define control
Definition: devnag.c:323
#define q1
#define q3
#define q2
#define error(a)
Definition: dviinfo.c:48
#define shift
Definition: exp3.c:154
#define FT_EXPORT_DEF(x)
Definition: ftconfig.h:32
FT_MulDiv(FT_Long a, FT_Long b, FT_Long c)
Definition: ftcalc.c:415
FT_BEGIN_HEADER FT_Outline_Get_BBox(FT_Outline *outline, FT_BBox *abbox)
#define FT_Outline_CubicTo_Func
Definition: ftimage.h:612
#define FT_Outline_LineTo_Func
Definition: ftimage.h:540
#define FT_CURVE_TAG(flag)
Definition: ftimage.h:459
#define FT_Outline_ConicTo_Func
Definition: ftimage.h:575
#define FT_CURVE_TAG_ON
Definition: ftimage.h:462
#define FT_Outline_MoveTo_Func
Definition: ftimage.h:511
FT_BEGIN_HEADER typedef signed long FT_Pos
Definition: ftimage.h:57
FT_BEGIN_HEADER FT_Outline_Decompose(FT_Outline *outline, const FT_Outline_Funcs *func_interface, void *user)
Definition: ftoutln.c:43
int FT_Error
Definition: fttypes.h:299
unsigned short FT_UShort
Definition: fttypes.h:209
signed int FT_Int
Definition: fttypes.h:220
FT_Int FT_MSB(FT_UInt32 z)
Definition: ftcalc.c:113
#define FT_THROW(e)
Definition: ftdebug.h:243
#define FT_ABS(a)
Definition: ftobjs.h:73
static FT_Pos cubic_peak(FT_Pos q1, FT_Pos q2, FT_Pos q3, FT_Pos q4)
Definition: ftbbox.c:267
#define CHECK_X(p, bbox)
Definition: ftbbox.c:56
FT_Vector * vec
Definition: ftbbox.c:469
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:360
return FT_Err_Ok
Definition: ftbbox.c:526
static int BBox_Cubic_To(FT_Vector *control1, FT_Vector *control2, FT_Vector *to, TBBox_Rec *user)
Definition: ftbbox.c:414
#define FT_UPDATE_BBOX(p, bbox)
Definition: ftbbox.c:44
static int BBox_Move_To(FT_Vector *to, TBBox_Rec *user)
Definition: ftbbox.c:86
FT_UShort n
Definition: ftbbox.c:470
static int BBox_Line_To(FT_Vector *to, TBBox_Rec *user)
Definition: ftbbox.c:120
FT_BBox * abbox
Definition: ftbbox.c:464
static int BBox_Conic_To(FT_Vector *control, FT_Vector *to, TBBox_Rec *user)
Definition: ftbbox.c:209
#define CHECK_Y(p, bbox)
Definition: ftbbox.c:59
struct TBBox_Rec_ TBBox_Rec
FT_BBox bbox
Definition: ftbbox.c:467
static void BBox_Conic_Check(FT_Pos y1, FT_Pos y2, FT_Pos y3, FT_Pos *min, FT_Pos *max)
Definition: ftbbox.c:157
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
#define min(a, b)
Definition: pbmplus.h:223
#define max(a, b)
Definition: pbmto4425.c:11
real to[600]
Definition: pmxab.c:87
#define y1
#define y2
FT_Pos xMin
Definition: ftimage.h:120
FT_Pos yMax
Definition: ftimage.h:121
FT_Pos yMin
Definition: ftimage.h:120
FT_Pos xMax
Definition: ftimage.h:121
FT_Pos x
Definition: ftimage.h:77
FT_Pos y
Definition: ftimage.h:78
FT_BBox bbox
Definition: ftbbox.c:39
FT_Vector last
Definition: ftbbox.c:38
TT_Short n_contours
Definition: freetype.h:175
TT_UShort n_points
Definition: freetype.h:176
TT_Vector * points
Definition: freetype.h:178
Definition: nsfix.c:44
TT_Outline outline
Definition: ttf2pfb.c:167