← Back to branch summary

~oif-team/ubuntu/natty/qt4-x11/xi2.1

« back to all changes in this revision

Viewing changes to src/3rdparty/freetype/src/base/ftbbox.c

  • Committer: Bazaar Package Importer
  • Author(s): Adam Conrad
  • Date: 2005-08-24 04:09:09 UTC
  • Revision ID: james.westby@ubuntu.com-20050824040909-xmxe9jfr4a0w5671
Tags: upstream-4.0.0
Import upstream version 4.0.0

Show diffs side-by-side

added added

removed removed

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