src/autofit/afangles.c

   1 /***************************************************************************/
   2 /*                                                                         */
   3 /*  afangles.c                                                             */
   4 /*                                                                         */
   5 /*    Routines used to compute vector angles with limited accuracy         */
   6 /*    and very high speed.  It also contains sorting routines (body).      */
   7 /*                                                                         */
   8 /*  Copyright 2003-2006, 2011 by                                           */
   9 /*  David Turner, Robert Wilhelm, and Werner Lemberg.                      */
  10 /*                                                                         */
  11 /*  This file is part of the FreeType project, and may only be used,       */
  12 /*  modified, and distributed under the terms of the FreeType project      */
  13 /*  license, LICENSE.TXT.  By continuing to use, modify, or distribute     */
  14 /*  this file you indicate that you have read the license and              */
  15 /*  understand and accept it fully.                                        */
  16 /*                                                                         */
  17 /***************************************************************************/
  18
  19
  20 #include "aftypes.h"
  21
  22
  23 #if 0
  24
  25   FT_LOCAL_DEF( FT_Int )
  26   af_corner_is_flat( FT_Pos  x_in,
  27                      FT_Pos  y_in,
  28                      FT_Pos  x_out,
  29                      FT_Pos  y_out )
  30   {
  31     FT_Pos  ax = x_in;
  32     FT_Pos  ay = y_in;
  33
  34     FT_Pos  d_in, d_out, d_corner;
  35
  36
  37     if ( ax < 0 )
  38       ax = -ax;
  39     if ( ay < 0 )
  40       ay = -ay;
  41     d_in = ax + ay;
  42
  43     ax = x_out;
  44     if ( ax < 0 )
  45       ax = -ax;
  46     ay = y_out;
  47     if ( ay < 0 )
  48       ay = -ay;
  49     d_out = ax + ay;
  50
  51     ax = x_out + x_in;
  52     if ( ax < 0 )
  53       ax = -ax;
  54     ay = y_out + y_in;
  55     if ( ay < 0 )
  56       ay = -ay;
  57     d_corner = ax + ay;
  58
  59     return ( d_in + d_out - d_corner ) < ( d_corner >> 4 );
  60   }
  61
  62
  63   FT_LOCAL_DEF( FT_Int )
  64   af_corner_orientation( FT_Pos  x_in,
  65                          FT_Pos  y_in,
  66                          FT_Pos  x_out,
  67                          FT_Pos  y_out )
  68   {
  69     FT_Pos  delta;
  70
  71
  72     delta = x_in * y_out - y_in * x_out;
  73
  74     if ( delta == 0 )
  75       return 0;
  76     else
  77       return 1 - 2 * ( delta < 0 );
  78   }
  79
  80 #endif /* 0 */
  81
  82
  83   /*
  84    *  We are not using `af_angle_atan' anymore, but we keep the source
  85    *  code below just in case...
  86    */
  87
  88
  89 #if 0
  90
  91
  92   /*
  93    *  The trick here is to realize that we don't need a very accurate angle
  94    *  approximation.  We are going to use the result of `af_angle_atan' to
  95    *  only compare the sign of angle differences, or check whether its
  96    *  magnitude is very small.
  97    *
  98    *  The approximation
  99    *
 100    *    dy * PI / (|dx|+|dy|)
 101    *
 102    *  should be enough, and much faster to compute.
 103    */
 104   FT_LOCAL_DEF( AF_Angle )
 105   af_angle_atan( FT_Fixed  dx,
 106                  FT_Fixed  dy )
 107   {
 108     AF_Angle  angle;
 109     FT_Fixed  ax = dx;
 110     FT_Fixed  ay = dy;
 111
 112
 113     if ( ax < 0 )
 114       ax = -ax;
 115     if ( ay < 0 )
 116       ay = -ay;
 117
 118     ax += ay;
 119
 120     if ( ax == 0 )
 121       angle = 0;
 122     else
 123     {
 124       angle = ( AF_ANGLE_PI2 * dy ) / ( ax + ay );
 125       if ( dx < 0 )
 126       {
 127         if ( angle >= 0 )
 128           angle = AF_ANGLE_PI - angle;
 129         else
 130           angle = -AF_ANGLE_PI - angle;
 131       }
 132     }
 133
 134     return angle;
 135   }
 136
 137
 138 #elif 0
 139
 140
 141   /* the following table has been automatically generated with */
 142   /* the `mather.py' Python script                             */
 143
 144 #define AF_ATAN_BITS  8
 145
 146   static const FT_Byte  af_arctan[1L << AF_ATAN_BITS] =
 147   {
 148      0,  0,  1,  1,  1,  2,  2,  2,
 149      3,  3,  3,  3,  4,  4,  4,  5,
 150      5,  5,  6,  6,  6,  7,  7,  7,
 151      8,  8,  8,  9,  9,  9, 10, 10,
 152     10, 10, 11, 11, 11, 12, 12, 12,
 153     13, 13, 13, 14, 14, 14, 14, 15,
 154     15, 15, 16, 16, 16, 17, 17, 17,
 155     18, 18, 18, 18, 19, 19, 19, 20,
 156     20, 20, 21, 21, 21, 21, 22, 22,
 157     22, 23, 23, 23, 24, 24, 24, 24,
 158     25, 25, 25, 26, 26, 26, 26, 27,
 159     27, 27, 28, 28, 28, 28, 29, 29,
 160     29, 30, 30, 30, 30, 31, 31, 31,
 161     31, 32, 32, 32, 33, 33, 33, 33,
 162     34, 34, 34, 34, 35, 35, 35, 35,
 163     36, 36, 36, 36, 37, 37, 37, 38,
 164     38, 38, 38, 39, 39, 39, 39, 40,
 165     40, 40, 40, 41, 41, 41, 41, 42,
 166     42, 42, 42, 42, 43, 43, 43, 43,
 167     44, 44, 44, 44, 45, 45, 45, 45,
 168     46, 46, 46, 46, 46, 47, 47, 47,
 169     47, 48, 48, 48, 48, 48, 49, 49,
 170     49, 49, 50, 50, 50, 50, 50, 51,
 171     51, 51, 51, 51, 52, 52, 52, 52,
 172     52, 53, 53, 53, 53, 53, 54, 54,
 173     54, 54, 54, 55, 55, 55, 55, 55,
 174     56, 56, 56, 56, 56, 57, 57, 57,
 175     57, 57, 57, 58, 58, 58, 58, 58,
 176     59, 59, 59, 59, 59, 59, 60, 60,
 177     60, 60, 60, 61, 61, 61, 61, 61,
 178     61, 62, 62, 62, 62, 62, 62, 63,
 179     63, 63, 63, 63, 63, 64, 64, 64
 180   };
 181
 182
 183   FT_LOCAL_DEF( AF_Angle )
 184   af_angle_atan( FT_Fixed  dx,
 185                  FT_Fixed  dy )
 186   {
 187     AF_Angle  angle;
 188
 189
 190     /* check trivial cases */
 191     if ( dy == 0 )
 192     {
 193       angle = 0;
 194       if ( dx < 0 )
 195         angle = AF_ANGLE_PI;
 196       return angle;
 197     }
 198     else if ( dx == 0 )
 199     {
 200       angle = AF_ANGLE_PI2;
 201       if ( dy < 0 )
 202         angle = -AF_ANGLE_PI2;
 203       return angle;
 204     }
 205
 206     angle = 0;
 207     if ( dx < 0 )
 208     {
 209       dx = -dx;
 210       dy = -dy;
 211       angle = AF_ANGLE_PI;
 212     }
 213
 214     if ( dy < 0 )
 215     {
 216       FT_Pos  tmp;
 217
 218
 219       tmp = dx;
 220       dx  = -dy;
 221       dy  = tmp;
 222       angle -= AF_ANGLE_PI2;
 223     }
 224
 225     if ( dx == 0 && dy == 0 )
 226       return 0;
 227
 228     if ( dx == dy )
 229       angle += AF_ANGLE_PI4;
 230     else if ( dx > dy )
 231       angle += af_arctan[FT_DivFix( dy, dx ) >> ( 16 - AF_ATAN_BITS )];
 232     else
 233       angle += AF_ANGLE_PI2 -
 234                af_arctan[FT_DivFix( dx, dy ) >> ( 16 - AF_ATAN_BITS )];
 235
 236     if ( angle > AF_ANGLE_PI )
 237       angle -= AF_ANGLE_2PI;
 238
 239     return angle;
 240   }
 241
 242
 243 #endif /* 0 */
 244
 245
 246   FT_LOCAL_DEF( void )
 247   af_sort_pos( FT_UInt  count,
 248                FT_Pos*  table )
 249   {
 250     FT_UInt  i, j;
 251     FT_Pos   swap;
 252
 253
 254     for ( i = 1; i < count; i++ )
 255     {
 256       for ( j = i; j > 0; j-- )
 257       {
 258         if ( table[j] > table[j - 1] )
 259           break;
 260
 261         swap         = table[j];
 262         table[j]     = table[j - 1];
 263         table[j - 1] = swap;
 264       }
 265     }
 266   }
 267
 268
 269   FT_LOCAL_DEF( void )
 270   af_sort_widths( FT_UInt   count,
 271                   AF_Width  table )
 272   {
 273     FT_UInt      i, j;
 274     AF_WidthRec  swap;
 275
 276
 277     for ( i = 1; i < count; i++ )
 278     {
 279       for ( j = i; j > 0; j-- )
 280       {
 281         if ( table[j].org > table[j - 1].org )
 282           break;
 283
 284         swap         = table[j];
 285         table[j]     = table[j - 1];
 286         table[j - 1] = swap;
 287       }
 288     }
 289   }
 290
 291
 292 /* END */