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#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_and_quantize_widths( FT_UInt*  count,
271                               AF_Width  table,
272                               FT_Pos    threshold )
273  {
274    FT_UInt      i, j;
275    FT_UInt      cur_idx;
276    FT_Pos       cur_val;
277    FT_Pos       sum;
278    AF_WidthRec  swap;
279
280
281    if ( *count == 1 )
282      return;
283
284    /* sort */
285    for ( i = 1; i < *count; i++ )
286    {
287      for ( j = i; j > 0; j-- )
288      {
289        if ( table[j].org >= table[j - 1].org )
290          break;
291
292        swap         = table[j];
293        table[j]     = table[j - 1];
294        table[j - 1] = swap;
295      }
296    }
297
298    cur_idx = 0;
299    cur_val = table[cur_idx].org;
300
301    /* compute and use mean values for clusters not larger than  */
302    /* `threshold'; this is very primitive and might not yield   */
303    /* the best result, but normally, using reference character  */
304    /* `o', `*count' is 2, so the code below is fully sufficient */
305    for ( i = 1; i < *count; i++ )
306    {
307      if ( table[i].org - cur_val > threshold ||
308           i == *count - 1                    )
309      {
310        sum = 0;
311
312        /* fix loop for end of array */
313        if ( table[i].org - cur_val <= threshold &&
314             i == *count - 1                     )
315          i++;
316
317        for ( j = cur_idx; j < i; j++ )
318        {
319          sum         += table[j].org;
320          table[j].org = 0;
321        }
322        table[cur_idx].org = sum / j;
323
324        if ( i < *count - 1 )
325        {
326          cur_idx = i + 1;
327          cur_val = table[cur_idx].org;
328        }
329      }
330    }
331
332    cur_idx = 1;
333
334    /* compress array to remove zero values */
335    for ( i = 1; i < *count; i++ )
336    {
337      if ( table[i].org )
338        table[cur_idx++] = table[i];
339    }
340
341    *count = cur_idx;
342  }
343
344
345/* END */
346