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-2012 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   /*
  24    *  We are not using `af_angle_atan' anymore, but we keep the source
  25    *  code below just in case...
  26    */
  27
  28
  29 #if 0
  30
  31
  32   /*
  33    *  The trick here is to realize that we don't need a very accurate angle
  34    *  approximation.  We are going to use the result of `af_angle_atan' to
  35    *  only compare the sign of angle differences, or check whether its
  36    *  magnitude is very small.
  37    *
  38    *  The approximation
  39    *
  40    *    dy * PI / (|dx|+|dy|)
  41    *
  42    *  should be enough, and much faster to compute.
  43    */
  44   FT_LOCAL_DEF( AF_Angle )
  45   af_angle_atan( FT_Fixed  dx,
  46                  FT_Fixed  dy )
  47   {
  48     AF_Angle  angle;
  49     FT_Fixed  ax = dx;
  50     FT_Fixed  ay = dy;
  51
  52
  53     if ( ax < 0 )
  54       ax = -ax;
  55     if ( ay < 0 )
  56       ay = -ay;
  57
  58     ax += ay;
  59
  60     if ( ax == 0 )
  61       angle = 0;
  62     else
  63     {
  64       angle = ( AF_ANGLE_PI2 * dy ) / ( ax + ay );
  65       if ( dx < 0 )
  66       {
  67         if ( angle >= 0 )
  68           angle = AF_ANGLE_PI - angle;
  69         else
  70           angle = -AF_ANGLE_PI - angle;
  71       }
  72     }
  73
  74     return angle;
  75   }
  76
  77
  78 #elif 0
  79
  80
  81   /* the following table has been automatically generated with */
  82   /* the `mather.py' Python script                             */
  83
  84 #define AF_ATAN_BITS  8
  85
  86   static const FT_Byte  af_arctan[1L << AF_ATAN_BITS] =
  87   {
  88      0,  0,  1,  1,  1,  2,  2,  2,
  89      3,  3,  3,  3,  4,  4,  4,  5,
  90      5,  5,  6,  6,  6,  7,  7,  7,
  91      8,  8,  8,  9,  9,  9, 10, 10,
  92     10, 10, 11, 11, 11, 12, 12, 12,
  93     13, 13, 13, 14, 14, 14, 14, 15,
  94     15, 15, 16, 16, 16, 17, 17, 17,
  95     18, 18, 18, 18, 19, 19, 19, 20,
  96     20, 20, 21, 21, 21, 21, 22, 22,
  97     22, 23, 23, 23, 24, 24, 24, 24,
  98     25, 25, 25, 26, 26, 26, 26, 27,
  99     27, 27, 28, 28, 28, 28, 29, 29,
 100     29, 30, 30, 30, 30, 31, 31, 31,
 101     31, 32, 32, 32, 33, 33, 33, 33,
 102     34, 34, 34, 34, 35, 35, 35, 35,
 103     36, 36, 36, 36, 37, 37, 37, 38,
 104     38, 38, 38, 39, 39, 39, 39, 40,
 105     40, 40, 40, 41, 41, 41, 41, 42,
 106     42, 42, 42, 42, 43, 43, 43, 43,
 107     44, 44, 44, 44, 45, 45, 45, 45,
 108     46, 46, 46, 46, 46, 47, 47, 47,
 109     47, 48, 48, 48, 48, 48, 49, 49,
 110     49, 49, 50, 50, 50, 50, 50, 51,
 111     51, 51, 51, 51, 52, 52, 52, 52,
 112     52, 53, 53, 53, 53, 53, 54, 54,
 113     54, 54, 54, 55, 55, 55, 55, 55,
 114     56, 56, 56, 56, 56, 57, 57, 57,
 115     57, 57, 57, 58, 58, 58, 58, 58,
 116     59, 59, 59, 59, 59, 59, 60, 60,
 117     60, 60, 60, 61, 61, 61, 61, 61,
 118     61, 62, 62, 62, 62, 62, 62, 63,
 119     63, 63, 63, 63, 63, 64, 64, 64
 120   };
 121
 122
 123   FT_LOCAL_DEF( AF_Angle )
 124   af_angle_atan( FT_Fixed  dx,
 125                  FT_Fixed  dy )
 126   {
 127     AF_Angle  angle;
 128
 129
 130     /* check trivial cases */
 131     if ( dy == 0 )
 132     {
 133       angle = 0;
 134       if ( dx < 0 )
 135         angle = AF_ANGLE_PI;
 136       return angle;
 137     }
 138     else if ( dx == 0 )
 139     {
 140       angle = AF_ANGLE_PI2;
 141       if ( dy < 0 )
 142         angle = -AF_ANGLE_PI2;
 143       return angle;
 144     }
 145
 146     angle = 0;
 147     if ( dx < 0 )
 148     {
 149       dx = -dx;
 150       dy = -dy;
 151       angle = AF_ANGLE_PI;
 152     }
 153
 154     if ( dy < 0 )
 155     {
 156       FT_Pos  tmp;
 157
 158
 159       tmp = dx;
 160       dx  = -dy;
 161       dy  = tmp;
 162       angle -= AF_ANGLE_PI2;
 163     }
 164
 165     if ( dx == 0 && dy == 0 )
 166       return 0;
 167
 168     if ( dx == dy )
 169       angle += AF_ANGLE_PI4;
 170     else if ( dx > dy )
 171       angle += af_arctan[FT_DivFix( dy, dx ) >> ( 16 - AF_ATAN_BITS )];
 172     else
 173       angle += AF_ANGLE_PI2 -
 174                af_arctan[FT_DivFix( dx, dy ) >> ( 16 - AF_ATAN_BITS )];
 175
 176     if ( angle > AF_ANGLE_PI )
 177       angle -= AF_ANGLE_2PI;
 178
 179     return angle;
 180   }
 181
 182
 183 #endif /* 0 */
 184
 185
 186   FT_LOCAL_DEF( void )
 187   af_sort_pos( FT_UInt  count,
 188                FT_Pos*  table )
 189   {
 190     FT_UInt  i, j;
 191     FT_Pos   swap;
 192
 193
 194     for ( i = 1; i < count; i++ )
 195     {
 196       for ( j = i; j > 0; j-- )
 197       {
 198         if ( table[j] >= table[j - 1] )
 199           break;
 200
 201         swap         = table[j];
 202         table[j]     = table[j - 1];
 203         table[j - 1] = swap;
 204       }
 205     }
 206   }
 207
 208
 209   FT_LOCAL_DEF( void )
 210   af_sort_and_quantize_widths( FT_UInt*  count,
 211                                AF_Width  table,
 212                                FT_Pos    threshold )
 213   {
 214     FT_UInt      i, j;
 215     FT_UInt      cur_idx;
 216     FT_Pos       cur_val;
 217     FT_Pos       sum;
 218     AF_WidthRec  swap;
 219
 220
 221     if ( *count == 1 )
 222       return;
 223
 224     /* sort */
 225     for ( i = 1; i < *count; i++ )
 226     {
 227       for ( j = i; j > 0; j-- )
 228       {
 229         if ( table[j].org >= table[j - 1].org )
 230           break;
 231
 232         swap         = table[j];
 233         table[j]     = table[j - 1];
 234         table[j - 1] = swap;
 235       }
 236     }
 237
 238     cur_idx = 0;
 239     cur_val = table[cur_idx].org;
 240
 241     /* compute and use mean values for clusters not larger than  */
 242     /* `threshold'; this is very primitive and might not yield   */
 243     /* the best result, but normally, using reference character  */
 244     /* `o', `*count' is 2, so the code below is fully sufficient */
 245     for ( i = 1; i < *count; i++ )
 246     {
 247       if ( table[i].org - cur_val > threshold ||
 248            i == *count - 1                    )
 249       {
 250         sum = 0;
 251
 252         /* fix loop for end of array */
 253         if ( table[i].org - cur_val <= threshold &&
 254              i == *count - 1                     )
 255           i++;
 256
 257         for ( j = cur_idx; j < i; j++ )
 258         {
 259           sum         += table[j].org;
 260           table[j].org = 0;
 261         }
 262         table[cur_idx].org = sum / j;
 263
 264         if ( i < *count - 1 )
 265         {
 266           cur_idx = i + 1;
 267           cur_val = table[cur_idx].org;
 268         }
 269       }
 270     }
 271
 272     cur_idx = 1;
 273
 274     /* compress array to remove zero values */
 275     for ( i = 1; i < *count; i++ )
 276     {
 277       if ( table[i].org )
 278         table[cur_idx++] = table[i];
 279     }
 280
 281     *count = cur_idx;
 282   }
 283
 284
 285 /* END */