# source:trunk/poppler/freetype-2.1.10/src/autofit/afangles.c@2

Last change on this file since 2 was 2, checked in by Eugene Romanenko, 16 years ago

First import

File size: 6.6 KB
RevLine
[2]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, 2004, 2005 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      */
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 * a python script used to generate the following table
25 *
26
27import sys, math
28
29units = 256
30scale = units/math.pi
31comma = ""
32
33print ""
34print "table of arctan( 1/2^n ) for PI = " + repr( units / 65536.0 ) + " units"
35
36r = [-1] + range( 32 )
37
38for n in r:
39    if n >= 0:
40        x = 1.0 / ( 2.0 ** n )   # tangent value
41    else:
42        x = 2.0 ** ( -n )
43
44    angle  = math.atan( x )      # arctangent
45    angle2 = angle * scale       # arctangent in FT_Angle units
46
47    # determine which integer value for angle gives the best tangent
48    lo  = int( angle2 )
49    hi  = lo + 1
50    tlo = math.tan( lo / scale )
51    thi = math.tan( hi / scale )
52
53    errlo = abs( tlo - x )
54    errhi = abs( thi - x )
55
56    angle2 = hi
57    if errlo < errhi:
58        angle2 = lo
59
60    if angle2 <= 0:
61        break
62
63    sys.stdout.write( comma + repr( int( angle2 ) ) )
64    comma = ", "
65
66*
67* end of python script
68*/
69
70
71  /* this table was generated for AF_ANGLE_PI = 256 */
72#define AF_ANGLE_MAX_ITERS  8
73#define AF_TRIG_MAX_ITERS   8
74
75  static const FT_Fixed
76  af_angle_arctan_table[9] =
77  {
78    90, 64, 38, 20, 10, 5, 3, 1, 1
79  };
80
81
82  static FT_Int
83  af_angle_prenorm( FT_Vector*  vec )
84  {
85    FT_Fixed  x, y, z;
86    FT_Int    shift;
87
88
89    x = vec->x;
90    y = vec->y;
91
92    z     = ( ( x >= 0 ) ? x : - x ) | ( (y >= 0) ? y : -y );
93    shift = 0;
94
95    if ( z < ( 1L << 27 ) )
96    {
97      do
98      {
99        shift++;
100        z <<= 1;
101      } while ( z < ( 1L << 27 ) );
102
103      vec->x = x << shift;
104      vec->y = y << shift;
105    }
106    else if ( z > ( 1L << 28 ) )
107    {
108      do
109      {
110        shift++;
111        z >>= 1;
112      } while ( z > ( 1L << 28 ) );
113
114      vec->x = x >> shift;
115      vec->y = y >> shift;
116      shift  = -shift;
117    }
118    return shift;
119  }
120
121
122  static void
123  af_angle_pseudo_polarize( FT_Vector*  vec )
124  {
125    FT_Fixed         theta;
126    FT_Fixed         yi, i;
127    FT_Fixed         x, y;
128    const FT_Fixed  *arctanptr;
129
130
131    x = vec->x;
132    y = vec->y;
133
134    /* Get the vector into the right half plane */
135    theta = 0;
136    if ( x < 0 )
137    {
138      x = -x;
139      y = -y;
140      theta = AF_ANGLE_PI;
141    }
142
143    if ( y > 0 )
144      theta = -theta;
145
146    arctanptr = af_angle_arctan_table;
147
148    if ( y < 0 )
149    {
150      /* Rotate positive */
151      yi     = y + ( x << 1 );
152      x      = x - ( y << 1 );
153      y      = yi;
154      theta -= *arctanptr++;  /* Subtract angle */
155    }
156    else
157    {
158      /* Rotate negative */
159      yi     = y - ( x << 1 );
160      x      = x + ( y << 1 );
161      y      = yi;
162      theta += *arctanptr++;  /* Add angle */
163    }
164
165    i = 0;
166    do
167    {
168      if ( y < 0 )
169      {
170        /* Rotate positive */
171        yi     = y + ( x >> i );
172        x      = x - ( y >> i );
173        y      = yi;
174        theta -= *arctanptr++;
175      }
176      else
177      {
178        /* Rotate negative */
179        yi     = y - ( x >> i );
180        x      = x + ( y >> i );
181        y      = yi;
182        theta += *arctanptr++;
183      }
184    } while ( ++i < AF_TRIG_MAX_ITERS );
185
186#if 0
187    /* round theta */
188    if ( theta >= 0 )
189      theta =  FT_PAD_ROUND( theta, 2 );
190    else
191      theta = -FT_PAD_ROUND( -theta, 2 );
192#endif
193
194    vec->x = x;
195    vec->y = theta;
196  }
197
198
199  /* cf. documentation in fttrigon.h */
200
201  FT_LOCAL_DEF( AF_Angle )
202  af_angle_atan( FT_Fixed  dx,
203                 FT_Fixed  dy )
204  {
205    FT_Vector  v;
206
207
208    if ( dx == 0 && dy == 0 )
209      return 0;
210
211    v.x = dx;
212    v.y = dy;
213    af_angle_prenorm( &v );
214    af_angle_pseudo_polarize( &v );
215
216    return v.y;
217  }
218
219
220  FT_LOCAL_DEF( AF_Angle )
221  af_angle_diff( AF_Angle  angle1,
222                 AF_Angle  angle2 )
223  {
224    AF_Angle  delta = angle2 - angle1;
225
226
227    delta %= AF_ANGLE_2PI;
228    if ( delta < 0 )
229      delta += AF_ANGLE_2PI;
230
231    if ( delta > AF_ANGLE_PI )
232      delta -= AF_ANGLE_2PI;
233
234    return delta;
235  }
236
237
238  FT_LOCAL_DEF( void )
239  af_sort_pos( FT_UInt  count,
240               FT_Pos*  table )
241  {
242    FT_UInt  i, j;
243    FT_Pos   swap;
244
245
246    for ( i = 1; i < count; i++ )
247    {
248      for ( j = i; j > 0; j-- )
249      {
250        if ( table[j] > table[j - 1] )
251          break;
252
253        swap         = table[j];
254        table[j]     = table[j - 1];
255        table[j - 1] = swap;
256      }
257    }
258  }
259
260
261  FT_LOCAL_DEF( void )
262  af_sort_widths( FT_UInt   count,
263                  AF_Width  table )
264  {
265    FT_UInt      i, j;
266    AF_WidthRec  swap;
267
268
269    for ( i = 1; i < count; i++ )
270    {
271      for ( j = i; j > 0; j-- )
272      {
273        if ( table[j].org > table[j - 1].org )
274          break;
275
276        swap         = table[j];
277        table[j]     = table[j - 1];
278        table[j - 1] = swap;
279      }
280    }
281  }
282
283
284#ifdef TEST
285
286#include <stdio.h>
287#include <math.h>
288
289int main( void )
290{
291  int  angle;
292  int  dist;
293
294
295  for ( dist = 100; dist < 1000; dist++ )
296  {
297    for ( angle = AF_ANGLE_PI; angle < AF_ANGLE_2PI * 4; angle++ )
298    {
299      double  a = ( angle * 3.1415926535 ) / ( 1.0 * AF_ANGLE_PI );
300      int     dx, dy, angle1, angle2, delta;
301
302
303      dx = dist * cos( a );
304      dy = dist * sin( a );
305
306      angle1 = ( ( atan2( dy, dx ) * AF_ANGLE_PI ) / 3.1415926535 );
307      angle2 = af_angle_atan( dx, dy );
308      delta  = ( angle2 - angle1 ) % AF_ANGLE_2PI;
309      if ( delta < 0 )
310        delta = -delta;
311
312      if ( delta >= 2 )
313      {
314        printf( "dist:%4d angle:%4d => (%4d,%4d) angle1:%4d angle2:%4d\n",
315                dist, angle, dx, dy, angle1, angle2 );
316      }
317    }
318  }
319  return 0;
320}
321
322#endif /* TEST */
323
324
325/* END */
Note: See TracBrowser for help on using the repository browser.