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 */
293