src/base/ftoutln.c

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