1/***************************************************************************/
2/*                                                                         */
3/*  ftoutln.c                                                              */
4/*                                                                         */
5/*    FreeType outline management (body).                                  */
6/*                                                                         */
7/*  Copyright 1996-2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2010 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  /* All functions are declared in freetype.h.                             */
22  /*                                                                       */
23  /*************************************************************************/
24
25
26#include <ft2build.h>
27#include FT_OUTLINE_H
28#include FT_INTERNAL_OBJECTS_H
29#include FT_INTERNAL_DEBUG_H
30#include FT_TRIGONOMETRY_H
31
32
33  /*************************************************************************/
34  /*                                                                       */
35  /* The macro FT_COMPONENT is used in trace mode.  It is an implicit      */
36  /* parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log  */
37  /* messages during execution.                                            */
38  /*                                                                       */
39#undef  FT_COMPONENT
40#define FT_COMPONENT  trace_outline
41
42
43  static
44  const FT_Outline  null_outline = { 0, 0, 0, 0, 0, 0 };
45
46
47  /* documentation is in ftoutln.h */
48
49  FT_EXPORT_DEF( FT_Error )
50  FT_Outline_Decompose( FT_Outline*              outline,
51                        const FT_Outline_Funcs*  func_interface,
52                        void*                    user )
53  {
54#undef SCALED
55#define SCALED( x )  ( ( (x) << shift ) - delta )
56
57    FT_Vector   v_last;
58    FT_Vector   v_control;
59    FT_Vector   v_start;
60
61    FT_Vector*  point;
62    FT_Vector*  limit;
63    char*       tags;
64
65    FT_Error    error;
66
67    FT_Int   n;         /* index of contour in outline     */
68    FT_UInt  first;     /* index of first point in contour */
69    FT_Int   tag;       /* current point's state           */
70
71    FT_Int   shift;
72    FT_Pos   delta;
73
74
75    if ( !outline || !func_interface )
76      return FT_Err_Invalid_Argument;
77
78    shift = func_interface->shift;
79    delta = func_interface->delta;
80    first = 0;
81
82    for ( n = 0; n < outline->n_contours; n++ )
83    {
84      FT_Int  last;  /* index of last point in contour */
85
86
87      FT_TRACE5(( "FT_Outline_Decompose: Outline %d\n", n ));
88
89      last = outline->contours[n];
90      if ( last < 0 )
91        goto Invalid_Outline;
92      limit = outline->points + last;
93
94      v_start   = outline->points[first];
95      v_start.x = SCALED( v_start.x );
96      v_start.y = SCALED( v_start.y );
97
98      v_last   = outline->points[last];
99      v_last.x = SCALED( v_last.x );
100      v_last.y = SCALED( v_last.y );
101
102      v_control = v_start;
103
104      point = outline->points + first;
105      tags  = outline->tags   + first;
106      tag   = FT_CURVE_TAG( tags[0] );
107
108      /* A contour cannot start with a cubic control point! */
109      if ( tag == FT_CURVE_TAG_CUBIC )
110        goto Invalid_Outline;
111
112      /* check first point to determine origin */
113      if ( tag == FT_CURVE_TAG_CONIC )
114      {
115        /* first point is conic control.  Yes, this happens. */
116        if ( FT_CURVE_TAG( outline->tags[last] ) == FT_CURVE_TAG_ON )
117        {
118          /* start at last point if it is on the curve */
119          v_start = v_last;
120          limit--;
121        }
122        else
123        {
124          /* if both first and last points are conic,         */
125          /* start at their middle and record its position    */
126          /* for closure                                      */
127          v_start.x = ( v_start.x + v_last.x ) / 2;
128          v_start.y = ( v_start.y + v_last.y ) / 2;
129
130          v_last = v_start;
131        }
132        point--;
133        tags--;
134      }
135
136      FT_TRACE5(( "  move to (%.2f, %.2f)\n",
137                  v_start.x / 64.0, v_start.y / 64.0 ));
138      error = func_interface->move_to( &v_start, user );
139      if ( error )
140        goto Exit;
141
142      while ( point < limit )
143      {
144        point++;
145        tags++;
146
147        tag = FT_CURVE_TAG( tags[0] );
148        switch ( tag )
149        {
150        case FT_CURVE_TAG_ON:  /* emit a single line_to */
151          {
152            FT_Vector  vec;
153
154
155            vec.x = SCALED( point->x );
156            vec.y = SCALED( point->y );
157
158            FT_TRACE5(( "  line to (%.2f, %.2f)\n",
159                        vec.x / 64.0, vec.y / 64.0 ));
160            error = func_interface->line_to( &vec, user );
161            if ( error )
162              goto Exit;
163            continue;
164          }
165
166        case FT_CURVE_TAG_CONIC:  /* consume conic arcs */
167          v_control.x = SCALED( point->x );
168          v_control.y = SCALED( point->y );
169
170        Do_Conic:
171          if ( point < limit )
172          {
173            FT_Vector  vec;
174            FT_Vector  v_middle;
175
176
177            point++;
178            tags++;
179            tag = FT_CURVE_TAG( tags[0] );
180
181            vec.x = SCALED( point->x );
182            vec.y = SCALED( point->y );
183
184            if ( tag == FT_CURVE_TAG_ON )
185            {
186              FT_TRACE5(( "  conic to (%.2f, %.2f)"
187                          " with control (%.2f, %.2f)\n",
188                          vec.x / 64.0, vec.y / 64.0,
189                          v_control.x / 64.0, v_control.y / 64.0 ));
190              error = func_interface->conic_to( &v_control, &vec, user );
191              if ( error )
192                goto Exit;
193              continue;
194            }
195
196            if ( tag != FT_CURVE_TAG_CONIC )
197              goto Invalid_Outline;
198
199            v_middle.x = ( v_control.x + vec.x ) / 2;
200            v_middle.y = ( v_control.y + vec.y ) / 2;
201
202            FT_TRACE5(( "  conic to (%.2f, %.2f)"
203                        " with control (%.2f, %.2f)\n",
204                        v_middle.x / 64.0, v_middle.y / 64.0,
205                        v_control.x / 64.0, v_control.y / 64.0 ));
206            error = func_interface->conic_to( &v_control, &v_middle, user );
207            if ( error )
208              goto Exit;
209
210            v_control = vec;
211            goto Do_Conic;
212          }
213
214          FT_TRACE5(( "  conic to (%.2f, %.2f)"
215                      " with control (%.2f, %.2f)\n",
216                      v_start.x / 64.0, v_start.y / 64.0,
217                      v_control.x / 64.0, v_control.y / 64.0 ));
218          error = func_interface->conic_to( &v_control, &v_start, user );
219          goto Close;
220
221        default:  /* FT_CURVE_TAG_CUBIC */
222          {
223            FT_Vector  vec1, vec2;
224
225
226            if ( point + 1 > limit                             ||
227                 FT_CURVE_TAG( tags[1] ) != FT_CURVE_TAG_CUBIC )
228              goto Invalid_Outline;
229
230            point += 2;
231            tags  += 2;
232
233            vec1.x = SCALED( point[-2].x );
234            vec1.y = SCALED( point[-2].y );
235
236            vec2.x = SCALED( point[-1].x );
237            vec2.y = SCALED( point[-1].y );
238
239            if ( point <= limit )
240            {
241              FT_Vector  vec;
242
243
244              vec.x = SCALED( point->x );
245              vec.y = SCALED( point->y );
246
247              FT_TRACE5(( "  cubic to (%.2f, %.2f)"
248                          " with controls (%.2f, %.2f) and (%.2f, %.2f)\n",
249                          vec.x / 64.0, vec.y / 64.0,
250                          vec1.x / 64.0, vec1.y / 64.0,
251                          vec2.x / 64.0, vec2.y / 64.0 ));
252              error = func_interface->cubic_to( &vec1, &vec2, &vec, user );
253              if ( error )
254                goto Exit;
255              continue;
256            }
257
258            FT_TRACE5(( "  cubic to (%.2f, %.2f)"
259                        " with controls (%.2f, %.2f) and (%.2f, %.2f)\n",
260                        v_start.x / 64.0, v_start.y / 64.0,
261                        vec1.x / 64.0, vec1.y / 64.0,
262                        vec2.x / 64.0, vec2.y / 64.0 ));
263            error = func_interface->cubic_to( &vec1, &vec2, &v_start, user );
264            goto Close;
265          }
266        }
267      }
268
269      /* close the contour with a line segment */
270      FT_TRACE5(( "  line to (%.2f, %.2f)\n",
271                  v_start.x / 64.0, v_start.y / 64.0 ));
272      error = func_interface->line_to( &v_start, user );
273
274    Close:
275      if ( error )
276        goto Exit;
277
278      first = last + 1;
279    }
280
281    FT_TRACE5(( "FT_Outline_Decompose: Done\n", n ));
282    return FT_Err_Ok;
283
284  Exit:
285    FT_TRACE5(( "FT_Outline_Decompose: Error %d\n", error ));
286    return error;
287
288  Invalid_Outline:
289    return FT_Err_Invalid_Outline;
290  }
291
292
293  FT_EXPORT_DEF( FT_Error )
294  FT_Outline_New_Internal( FT_Memory    memory,
295                           FT_UInt      numPoints,
296                           FT_Int       numContours,
297                           FT_Outline  *anoutline )
298  {
299    FT_Error  error;
300
301
302    if ( !anoutline || !memory )
303      return FT_Err_Invalid_Argument;
304
305    *anoutline = null_outline;
306
307    if ( FT_NEW_ARRAY( anoutline->points,   numPoints   ) ||
308         FT_NEW_ARRAY( anoutline->tags,     numPoints      ) ||
309         FT_NEW_ARRAY( anoutline->contours, numContours    ) )
310      goto Fail;
311
312    anoutline->n_points    = (FT_UShort)numPoints;
313    anoutline->n_contours  = (FT_Short)numContours;
314    anoutline->flags      |= FT_OUTLINE_OWNER;
315
316    return FT_Err_Ok;
317
318  Fail:
319    anoutline->flags |= FT_OUTLINE_OWNER;
320    FT_Outline_Done_Internal( memory, anoutline );
321
322    return error;
323  }
324
325
326  /* documentation is in ftoutln.h */
327
328  FT_EXPORT_DEF( FT_Error )
329  FT_Outline_New( FT_Library   library,
330                  FT_UInt      numPoints,
331                  FT_Int       numContours,
332                  FT_Outline  *anoutline )
333  {
334    if ( !library )
335      return FT_Err_Invalid_Library_Handle;
336
337    return FT_Outline_New_Internal( library->memory, numPoints,
338                                    numContours, anoutline );
339  }
340
341
342  /* documentation is in ftoutln.h */
343
344  FT_EXPORT_DEF( FT_Error )
345  FT_Outline_Check( FT_Outline*  outline )
346  {
347    if ( outline )
348    {
349      FT_Int  n_points   = outline->n_points;
350      FT_Int  n_contours = outline->n_contours;
351      FT_Int  end0, end;
352      FT_Int  n;
353
354
355      /* empty glyph? */
356      if ( n_points == 0 && n_contours == 0 )
357        return 0;
358
359      /* check point and contour counts */
360      if ( n_points <= 0 || n_contours <= 0 )
361        goto Bad;
362
363      end0 = end = -1;
364      for ( n = 0; n < n_contours; n++ )
365      {
366        end = outline->contours[n];
367
368        /* note that we don't accept empty contours */
369        if ( end <= end0 || end >= n_points )
370          goto Bad;
371
372        end0 = end;
373      }
374
375      if ( end != n_points - 1 )
376        goto Bad;
377
378      /* XXX: check the tags array */
379      return 0;
380    }
381
382  Bad:
383    return FT_Err_Invalid_Argument;
384  }
385
386
387  /* documentation is in ftoutln.h */
388
389  FT_EXPORT_DEF( FT_Error )
390  FT_Outline_Copy( const FT_Outline*  source,
391                   FT_Outline        *target )
392  {
393    FT_Int  is_owner;
394
395
396    if ( !source            || !target            ||
397         source->n_points   != target->n_points   ||
398         source->n_contours != target->n_contours )
399      return FT_Err_Invalid_Argument;
400
401    if ( source == target )
402      return FT_Err_Ok;
403
404    FT_ARRAY_COPY( target->points, source->points, source->n_points );
405
406    FT_ARRAY_COPY( target->tags, source->tags, source->n_points );
407
408    FT_ARRAY_COPY( target->contours, source->contours, source->n_contours );
409
410    /* copy all flags, except the `FT_OUTLINE_OWNER' one */
411    is_owner      = target->flags & FT_OUTLINE_OWNER;
412    target->flags = source->flags;
413
414    target->flags &= ~FT_OUTLINE_OWNER;
415    target->flags |= is_owner;
416
417    return FT_Err_Ok;
418  }
419
420
421  FT_EXPORT_DEF( FT_Error )
422  FT_Outline_Done_Internal( FT_Memory    memory,
423                            FT_Outline*  outline )
424  {
425    if ( memory && outline )
426    {
427      if ( outline->flags & FT_OUTLINE_OWNER )
428      {
429        FT_FREE( outline->points   );
430        FT_FREE( outline->tags     );
431        FT_FREE( outline->contours );
432      }
433      *outline = null_outline;
434
435      return FT_Err_Ok;
436    }
437    else
438      return FT_Err_Invalid_Argument;
439  }
440
441
442  /* documentation is in ftoutln.h */
443
444  FT_EXPORT_DEF( FT_Error )
445  FT_Outline_Done( FT_Library   library,
446                   FT_Outline*  outline )
447  {
448    /* check for valid `outline' in FT_Outline_Done_Internal() */
449
450    if ( !library )
451      return FT_Err_Invalid_Library_Handle;
452
453    return FT_Outline_Done_Internal( library->memory, outline );
454  }
455
456
457  /* documentation is in ftoutln.h */
458
459  FT_EXPORT_DEF( void )
460  FT_Outline_Get_CBox( const FT_Outline*  outline,
461                       FT_BBox           *acbox )
462  {
463    FT_Pos  xMin, yMin, xMax, yMax;
464
465
466    if ( outline && acbox )
467    {
468      if ( outline->n_points == 0 )
469      {
470        xMin = 0;
471        yMin = 0;
472        xMax = 0;
473        yMax = 0;
474      }
475      else
476      {
477        FT_Vector*  vec   = outline->points;
478        FT_Vector*  limit = vec + outline->n_points;
479
480
481        xMin = xMax = vec->x;
482        yMin = yMax = vec->y;
483        vec++;
484
485        for ( ; vec < limit; vec++ )
486        {
487          FT_Pos  x, y;
488
489
490          x = vec->x;
491          if ( x < xMin ) xMin = x;
492          if ( x > xMax ) xMax = x;
493
494          y = vec->y;
495          if ( y < yMin ) yMin = y;
496          if ( y > yMax ) yMax = y;
497        }
498      }
499      acbox->xMin = xMin;
500      acbox->xMax = xMax;
501      acbox->yMin = yMin;
502      acbox->yMax = yMax;
503    }
504  }
505
506
507  /* documentation is in ftoutln.h */
508
509  FT_EXPORT_DEF( void )
510  FT_Outline_Translate( const FT_Outline*  outline,
511                        FT_Pos             xOffset,
512                        FT_Pos             yOffset )
513  {
514    FT_UShort   n;
515    FT_Vector*  vec;
516
517
518    if ( !outline )
519      return;
520
521    vec = outline->points;
522
523    for ( n = 0; n < outline->n_points; n++ )
524    {
525      vec->x += xOffset;
526      vec->y += yOffset;
527      vec++;
528    }
529  }
530
531
532  /* documentation is in ftoutln.h */
533
534  FT_EXPORT_DEF( void )
535  FT_Outline_Reverse( FT_Outline*  outline )
536  {
537    FT_UShort  n;
538    FT_Int     first, last;
539
540
541    if ( !outline )
542      return;
543
544    first = 0;
545
546    for ( n = 0; n < outline->n_contours; n++ )
547    {
548      last  = outline->contours[n];
549
550      /* reverse point table */
551      {
552        FT_Vector*  p = outline->points + first;
553        FT_Vector*  q = outline->points + last;
554        FT_Vector   swap;
555
556
557        while ( p < q )
558        {
559          swap = *p;
560          *p   = *q;
561          *q   = swap;
562          p++;
563          q--;
564        }
565      }
566
567      /* reverse tags table */
568      {
569        char*  p = outline->tags + first;
570        char*  q = outline->tags + last;
571        char   swap;
572
573
574        while ( p < q )
575        {
576          swap = *p;
577          *p   = *q;
578          *q   = swap;
579          p++;
580          q--;
581        }
582      }
583
584      first = last + 1;
585    }
586
587    outline->flags ^= FT_OUTLINE_REVERSE_FILL;
588  }
589
590
591  /* documentation is in ftoutln.h */
592
593  FT_EXPORT_DEF( FT_Error )
594  FT_Outline_Render( FT_Library         library,
595                     FT_Outline*        outline,
596                     FT_Raster_Params*  params )
597  {
598    FT_Error     error;
599    FT_Bool      update = FALSE;
600    FT_Renderer  renderer;
601    FT_ListNode  node;
602
603
604    if ( !library )
605      return FT_Err_Invalid_Library_Handle;
606
607    if ( !outline || !params )
608      return FT_Err_Invalid_Argument;
609
610    renderer = library->cur_renderer;
611    node     = library->renderers.head;
612
613    params->source = (void*)outline;
614
615    error = FT_Err_Cannot_Render_Glyph;
616    while ( renderer )
617    {
618      error = renderer->raster_render( renderer->raster, params );
619      if ( !error || FT_ERROR_BASE( error ) != FT_Err_Cannot_Render_Glyph )
620        break;
621
622      /* FT_Err_Cannot_Render_Glyph is returned if the render mode   */
623      /* is unsupported by the current renderer for this glyph image */
624      /* format                                                      */
625
626      /* now, look for another renderer that supports the same */
627      /* format                                                */
628      renderer = FT_Lookup_Renderer( library, FT_GLYPH_FORMAT_OUTLINE,
629                                     &node );
630      update   = TRUE;
631    }
632
633    /* if we changed the current renderer for the glyph image format */
634    /* we need to select it as the next current one                  */
635    if ( !error && update && renderer )
636      FT_Set_Renderer( library, renderer, 0, 0 );
637
638    return error;
639  }
640
641
642  /* documentation is in ftoutln.h */
643
644  FT_EXPORT_DEF( FT_Error )
645  FT_Outline_Get_Bitmap( FT_Library        library,
646                         FT_Outline*       outline,
647                         const FT_Bitmap  *abitmap )
648  {
649    FT_Raster_Params  params;
650
651
652    if ( !abitmap )
653      return FT_Err_Invalid_Argument;
654
655    /* other checks are delayed to FT_Outline_Render() */
656
657    params.target = abitmap;
658    params.flags  = 0;
659
660    if ( abitmap->pixel_mode == FT_PIXEL_MODE_GRAY  ||
661         abitmap->pixel_mode == FT_PIXEL_MODE_LCD   ||
662         abitmap->pixel_mode == FT_PIXEL_MODE_LCD_V )
663      params.flags |= FT_RASTER_FLAG_AA;
664
665    return FT_Outline_Render( library, outline, &params );
666  }
667
668
669  /* documentation is in freetype.h */
670
671  FT_EXPORT_DEF( void )
672  FT_Vector_Transform( FT_Vector*        vector,
673                       const FT_Matrix*  matrix )
674  {
675    FT_Pos  xz, yz;
676
677
678    if ( !vector || !matrix )
679      return;
680
681    xz = FT_MulFix( vector->x, matrix->xx ) +
682         FT_MulFix( vector->y, matrix->xy );
683
684    yz = FT_MulFix( vector->x, matrix->yx ) +
685         FT_MulFix( vector->y, matrix->yy );
686
687    vector->x = xz;
688    vector->y = yz;
689  }
690
691
692  /* documentation is in ftoutln.h */
693
694  FT_EXPORT_DEF( void )
695  FT_Outline_Transform( const FT_Outline*  outline,
696                        const FT_Matrix*   matrix )
697  {
698    FT_Vector*  vec;
699    FT_Vector*  limit;
700
701
702    if ( !outline || !matrix )
703      return;
704
705    vec   = outline->points;
706    limit = vec + outline->n_points;
707
708    for ( ; vec < limit; vec++ )
709      FT_Vector_Transform( vec, matrix );
710  }
711
712
713#if 0
714
715#define FT_OUTLINE_GET_CONTOUR( outline, c, first, last )  \
716  do {                                                     \
717    (first) = ( c > 0 ) ? (outline)->points +              \
718                            (outline)->contours[c - 1] + 1 \
719                        : (outline)->points;               \
720    (last) = (outline)->points + (outline)->contours[c];   \
721  } while ( 0 )
722
723
724  /* Is a point in some contour?                     */
725  /*                                                 */
726  /* We treat every point of the contour as if it    */
727  /* it were ON.  That is, we allow false positives, */
728  /* but disallow false negatives.  (XXX really?)    */
729  static FT_Bool
730  ft_contour_has( FT_Outline*  outline,
731                  FT_Short     c,
732                  FT_Vector*   point )
733  {
734    FT_Vector*  first;
735    FT_Vector*  last;
736    FT_Vector*  a;
737    FT_Vector*  b;
738    FT_UInt     n = 0;
739
740
741    FT_OUTLINE_GET_CONTOUR( outline, c, first, last );
742
743    for ( a = first; a <= last; a++ )
744    {
745      FT_Pos  x;
746      FT_Int  intersect;
747
748
749      b = ( a == last ) ? first : a + 1;
750
751      intersect = ( a->y - point->y ) ^ ( b->y - point->y );
752
753      /* a and b are on the same side */
754      if ( intersect >= 0 )
755      {
756        if ( intersect == 0 && a->y == point->y )
757        {
758          if ( ( a->x <= point->x && b->x >= point->x ) ||
759               ( a->x >= point->x && b->x <= point->x ) )
760            return 1;
761        }
762
763        continue;
764      }
765
766      x = a->x + ( b->x - a->x ) * (point->y - a->y ) / ( b->y - a->y );
767
768      if ( x < point->x )
769        n++;
770      else if ( x == point->x )
771        return 1;
772    }
773
774    return ( n % 2 );
775  }
776
777
778  static FT_Bool
779  ft_contour_enclosed( FT_Outline*  outline,
780                       FT_UShort    c )
781  {
782    FT_Vector*  first;
783    FT_Vector*  last;
784    FT_Short    i;
785
786
787    FT_OUTLINE_GET_CONTOUR( outline, c, first, last );
788
789    for ( i = 0; i < outline->n_contours; i++ )
790    {
791      if ( i != c && ft_contour_has( outline, i, first ) )
792      {
793        FT_Vector*  pt;
794
795
796        for ( pt = first + 1; pt <= last; pt++ )
797          if ( !ft_contour_has( outline, i, pt ) )
798            return 0;
799
800        return 1;
801      }
802    }
803
804    return 0;
805  }
806
807
808  /* This version differs from the public one in that each */
809  /* part (contour not enclosed in another contour) of the */
810  /* outline is checked for orientation.  This is          */
811  /* necessary for some buggy CJK fonts.                   */
812  static FT_Orientation
813  ft_outline_get_orientation( FT_Outline*  outline )
814  {
815    FT_Short        i;
816    FT_Vector*      first;
817    FT_Vector*      last;
818    FT_Orientation  orient = FT_ORIENTATION_NONE;
819
820
821    first = outline->points;
822    for ( i = 0; i < outline->n_contours; i++, first = last + 1 )
823    {
824      FT_Vector*  point;
825      FT_Vector*  xmin_point;
826      FT_Pos      xmin;
827
828
829      last = outline->points + outline->contours[i];
830
831      /* skip degenerate contours */
832      if ( last < first + 2 )
833        continue;
834
835      if ( ft_contour_enclosed( outline, i ) )
836        continue;
837
838      xmin       = first->x;
839      xmin_point = first;
840
841      for ( point = first + 1; point <= last; point++ )
842      {
843        if ( point->x < xmin )
844        {
845          xmin       = point->x;
846          xmin_point = point;
847        }
848      }
849
850      /* check the orientation of the contour */
851      {
852        FT_Vector*      prev;
853        FT_Vector*      next;
854        FT_Orientation  o;
855
856
857        prev = ( xmin_point == first ) ? last : xmin_point - 1;
858        next = ( xmin_point == last ) ? first : xmin_point + 1;
859
860        if ( FT_Atan2( prev->x - xmin_point->x, prev->y - xmin_point->y ) >
861             FT_Atan2( next->x - xmin_point->x, next->y - xmin_point->y ) )
862          o = FT_ORIENTATION_POSTSCRIPT;
863        else
864          o = FT_ORIENTATION_TRUETYPE;
865
866        if ( orient == FT_ORIENTATION_NONE )
867          orient = o;
868        else if ( orient != o )
869          return FT_ORIENTATION_NONE;
870      }
871    }
872
873    return orient;
874  }
875
876#endif /* 0 */
877
878
879  /* documentation is in ftoutln.h */
880
881  FT_EXPORT_DEF( FT_Error )
882  FT_Outline_Embolden( FT_Outline*  outline,
883                       FT_Pos       strength )
884  {
885    FT_Vector*  points;
886    FT_Vector   v_prev, v_first, v_next, v_cur;
887    FT_Angle    rotate, angle_in, angle_out;
888    FT_Int      c, n, first;
889    FT_Int      orientation;
890
891
892    if ( !outline )
893      return FT_Err_Invalid_Argument;
894
895    strength /= 2;
896    if ( strength == 0 )
897      return FT_Err_Ok;
898
899    orientation = FT_Outline_Get_Orientation( outline );
900    if ( orientation == FT_ORIENTATION_NONE )
901    {
902      if ( outline->n_contours )
903        return FT_Err_Invalid_Argument;
904      else
905        return FT_Err_Ok;
906    }
907
908    if ( orientation == FT_ORIENTATION_TRUETYPE )
909      rotate = -FT_ANGLE_PI2;
910    else
911      rotate = FT_ANGLE_PI2;
912
913    points = outline->points;
914
915    first = 0;
916    for ( c = 0; c < outline->n_contours; c++ )
917    {
918      int  last = outline->contours[c];
919
920
921      v_first = points[first];
922      v_prev  = points[last];
923      v_cur   = v_first;
924
925      for ( n = first; n <= last; n++ )
926      {
927        FT_Vector  in, out;
928        FT_Angle   angle_diff;
929        FT_Pos     d;
930        FT_Fixed   scale;
931
932
933        if ( n < last )
934          v_next = points[n + 1];
935        else
936          v_next = v_first;
937
938        /* compute the in and out vectors */
939        in.x = v_cur.x - v_prev.x;
940        in.y = v_cur.y - v_prev.y;
941
942        out.x = v_next.x - v_cur.x;
943        out.y = v_next.y - v_cur.y;
944
945        angle_in   = FT_Atan2( in.x, in.y );
946        angle_out  = FT_Atan2( out.x, out.y );
947        angle_diff = FT_Angle_Diff( angle_in, angle_out );
948        scale      = FT_Cos( angle_diff / 2 );
949
950        if ( scale < 0x4000L && scale > -0x4000L )
951          in.x = in.y = 0;
952        else
953        {
954          d = FT_DivFix( strength, scale );
955
956          FT_Vector_From_Polar( &in, d, angle_in + angle_diff / 2 - rotate );
957        }
958
959        outline->points[n].x = v_cur.x + strength + in.x;
960        outline->points[n].y = v_cur.y + strength + in.y;
961
962        v_prev = v_cur;
963        v_cur  = v_next;
964      }
965
966      first = last + 1;
967    }
968
969    return FT_Err_Ok;
970  }
971
972
973  /* documentation is in ftoutln.h */
974
975  FT_EXPORT_DEF( FT_Orientation )
976  FT_Outline_Get_Orientation( FT_Outline*  outline )
977  {
978    FT_Pos      xmin       = 32768L;
979    FT_Pos      xmin_ymin  = 32768L;
980    FT_Pos      xmin_ymax  = -32768L;
981    FT_Vector*  xmin_first = NULL;
982    FT_Vector*  xmin_last  = NULL;
983
984    short*      contour;
985
986    FT_Vector*  first;
987    FT_Vector*  last;
988    FT_Vector*  prev;
989    FT_Vector*  point;
990
991    int             i;
992    FT_Pos          ray_y[3];
993    FT_Orientation  result[3];
994
995
996    if ( !outline || outline->n_points <= 0 )
997      return FT_ORIENTATION_TRUETYPE;
998
999    /* We use the nonzero winding rule to find the orientation.       */
1000    /* Since glyph outlines behave much more `regular' than arbitrary */
1001    /* cubic or quadratic curves, this test deals with the polygon    */
1002    /* only which is spanned up by the control points.                */
1003
1004    first = outline->points;
1005    for ( contour = outline->contours;
1006          contour < outline->contours + outline->n_contours;
1007          contour++, first = last + 1 )
1008    {
1009      FT_Pos  contour_xmin = 32768L;
1010      FT_Pos  contour_xmax = -32768L;
1011      FT_Pos  contour_ymin = 32768L;
1012      FT_Pos  contour_ymax = -32768L;
1013
1014
1015      last = outline->points + *contour;
1016
1017      /* skip degenerate contours */
1018      if ( last < first + 2 )
1019        continue;
1020
1021      for ( point = first; point <= last; ++point )
1022      {
1023        if ( point->x < contour_xmin )
1024          contour_xmin = point->x;
1025
1026        if ( point->x > contour_xmax )
1027          contour_xmax = point->x;
1028
1029        if ( point->y < contour_ymin )
1030          contour_ymin = point->y;
1031
1032        if ( point->y > contour_ymax )
1033          contour_ymax = point->y;
1034      }
1035
1036      if ( contour_xmin < xmin          &&
1037           contour_xmin != contour_xmax &&
1038           contour_ymin != contour_ymax )
1039      {
1040        xmin       = contour_xmin;
1041        xmin_ymin  = contour_ymin;
1042        xmin_ymax  = contour_ymax;
1043        xmin_first = first;
1044        xmin_last  = last;
1045      }
1046    }
1047
1048    if ( xmin == 32768L )
1049      return FT_ORIENTATION_TRUETYPE;
1050
1051    ray_y[0] = ( xmin_ymin * 3 + xmin_ymax     ) >> 2;
1052    ray_y[1] = ( xmin_ymin     + xmin_ymax     ) >> 1;
1053    ray_y[2] = ( xmin_ymin     + xmin_ymax * 3 ) >> 2;
1054
1055    for ( i = 0; i < 3; i++ )
1056    {
1057      FT_Pos      left_x;
1058      FT_Pos      right_x;
1059      FT_Vector*  left1;
1060      FT_Vector*  left2;
1061      FT_Vector*  right1;
1062      FT_Vector*  right2;
1063
1064
1065    RedoRay:
1066      left_x  = 32768L;
1067      right_x = -32768L;
1068
1069      left1 = left2 = right1 = right2 = NULL;
1070
1071      prev = xmin_last;
1072      for ( point = xmin_first; point <= xmin_last; prev = point, ++point )
1073      {
1074        FT_Pos  tmp_x;
1075
1076
1077        if ( point->y == ray_y[i] || prev->y == ray_y[i] )
1078        {
1079          ray_y[i]++;
1080          goto RedoRay;
1081        }
1082
1083        if ( ( point->y < ray_y[i] && prev->y < ray_y[i] ) ||
1084             ( point->y > ray_y[i] && prev->y > ray_y[i] ) )
1085          continue;
1086
1087        tmp_x = FT_MulDiv( point->x - prev->x,
1088                           ray_y[i] - prev->y,
1089                           point->y - prev->y ) + prev->x;
1090
1091        if ( tmp_x < left_x )
1092        {
1093          left_x = tmp_x;
1094          left1  = prev;
1095          left2  = point;
1096        }
1097
1098        if ( tmp_x > right_x )
1099        {
1100          right_x = tmp_x;
1101          right1  = prev;
1102          right2  = point;
1103        }
1104      }
1105
1106      if ( left1 && right1 )
1107      {
1108        if ( left1->y < left2->y && right1->y > right2->y )
1109          result[i] = FT_ORIENTATION_TRUETYPE;
1110        else if ( left1->y > left2->y && right1->y < right2->y )
1111          result[i] = FT_ORIENTATION_POSTSCRIPT;
1112        else
1113          result[i] = FT_ORIENTATION_NONE;
1114      }
1115    }
1116
1117    if ( result[0] != FT_ORIENTATION_NONE                     &&
1118         ( result[0] == result[1] || result[0] == result[2] ) )
1119      return result[0];
1120
1121    if ( result[1] != FT_ORIENTATION_NONE && result[1] == result[2] )
1122      return result[1];
1123
1124    return FT_ORIENTATION_TRUETYPE;
1125  }
1126
1127
1128/* END */
1129