ref: 0880ac333a2bde53d6bd090b97bafadc7435ad58
dir: /src/autofit/afangles.c/
/***************************************************************************/
/* */
/* afangles.c */
/* */
/* Routines used to compute vector angles with limited accuracy */
/* and very high speed. It also contains sorting routines (body). */
/* */
/* Copyright 2003, 2004, 2005 by */
/* David Turner, Robert Wilhelm, and Werner Lemberg. */
/* */
/* This file is part of the FreeType project, and may only be used, */
/* modified, and distributed under the terms of the FreeType project */
/* license, LICENSE.TXT. By continuing to use, modify, or distribute */
/* this file you indicate that you have read the license and */
/* understand and accept it fully. */
/* */
/***************************************************************************/
#include "aftypes.h"
#if 1
/* the following table has been automatically generated with */
/* the `mather.py' Python script */
#define AF_ATAN_BITS 8
static const FT_Byte af_arctan[1L << AF_ATAN_BITS] =
{
0, 0, 1, 1, 1, 2, 2, 2,
3, 3, 3, 3, 4, 4, 4, 5,
5, 5, 6, 6, 6, 7, 7, 7,
8, 8, 8, 9, 9, 9, 10, 10,
10, 10, 11, 11, 11, 12, 12, 12,
13, 13, 13, 14, 14, 14, 14, 15,
15, 15, 16, 16, 16, 17, 17, 17,
18, 18, 18, 18, 19, 19, 19, 20,
20, 20, 21, 21, 21, 21, 22, 22,
22, 23, 23, 23, 24, 24, 24, 24,
25, 25, 25, 26, 26, 26, 26, 27,
27, 27, 28, 28, 28, 28, 29, 29,
29, 30, 30, 30, 30, 31, 31, 31,
31, 32, 32, 32, 33, 33, 33, 33,
34, 34, 34, 34, 35, 35, 35, 35,
36, 36, 36, 36, 37, 37, 37, 38,
38, 38, 38, 39, 39, 39, 39, 40,
40, 40, 40, 41, 41, 41, 41, 42,
42, 42, 42, 42, 43, 43, 43, 43,
44, 44, 44, 44, 45, 45, 45, 45,
46, 46, 46, 46, 46, 47, 47, 47,
47, 48, 48, 48, 48, 48, 49, 49,
49, 49, 50, 50, 50, 50, 50, 51,
51, 51, 51, 51, 52, 52, 52, 52,
52, 53, 53, 53, 53, 53, 54, 54,
54, 54, 54, 55, 55, 55, 55, 55,
56, 56, 56, 56, 56, 57, 57, 57,
57, 57, 57, 58, 58, 58, 58, 58,
59, 59, 59, 59, 59, 59, 60, 60,
60, 60, 60, 61, 61, 61, 61, 61,
61, 62, 62, 62, 62, 62, 62, 63,
63, 63, 63, 63, 63, 64, 64, 64
};
FT_LOCAL_DEF( AF_Angle )
af_angle_atan( FT_Fixed dx,
FT_Fixed dy )
{
AF_Angle angle;
/* check trivial cases */
if ( dy == 0 )
{
angle = 0;
if ( dx < 0 )
angle = AF_ANGLE_PI;
return angle;
}
else if ( dx == 0 )
{
angle = AF_ANGLE_PI2;
if ( dy < 0 )
angle = -AF_ANGLE_PI2;
return angle;
}
angle = 0;
if ( dx < 0 )
{
dx = -dx;
dy = -dy;
angle = AF_ANGLE_PI;
}
if ( dy < 0 )
{
FT_Pos tmp;
tmp = dx;
dx = -dy;
dy = tmp;
angle -= AF_ANGLE_PI2;
}
if ( dx == 0 && dy == 0 )
return 0;
if ( dx == dy )
angle += AF_ANGLE_PI4;
else if ( dx > dy )
angle += af_arctan[FT_DivFix( dy, dx ) >> ( 16 - AF_ATAN_BITS )];
else
angle += AF_ANGLE_PI2 -
af_arctan[FT_DivFix( dx, dy ) >> ( 16 - AF_ATAN_BITS )];
if ( angle > AF_ANGLE_PI )
angle -= AF_ANGLE_2PI;
return angle;
}
#else /* 0 */
/*
* a python script used to generate the following table
*
import sys, math
units = 256
scale = units/math.pi
comma = ""
print ""
print "table of arctan( 1/2^n ) for PI = " + repr( units / 65536.0 ) + " units"
r = [-1] + range( 32 )
for n in r:
if n >= 0:
x = 1.0 / ( 2.0 ** n ) # tangent value
else:
x = 2.0 ** ( -n )
angle = math.atan( x ) # arctangent
angle2 = angle * scale # arctangent in FT_Angle units
# determine which integer value for angle gives the best tangent
lo = int( angle2 )
hi = lo + 1
tlo = math.tan( lo / scale )
thi = math.tan( hi / scale )
errlo = abs( tlo - x )
errhi = abs( thi - x )
angle2 = hi
if errlo < errhi:
angle2 = lo
if angle2 <= 0:
break
sys.stdout.write( comma + repr( int( angle2 ) ) )
comma = ", "
*
* end of python script
*/
/* this table was generated for AF_ANGLE_PI = 256 */
#define AF_ANGLE_MAX_ITERS 8
#define AF_TRIG_MAX_ITERS 8
static const FT_Fixed
af_angle_arctan_table[9] =
{
90, 64, 38, 20, 10, 5, 3, 1, 1
};
static FT_Int
af_angle_prenorm( FT_Vector* vec )
{
FT_Fixed x, y, z;
FT_Int shift;
x = vec->x;
y = vec->y;
z = ( ( x >= 0 ) ? x : - x ) | ( (y >= 0) ? y : -y );
shift = 0;
if ( z < ( 1L << 27 ) )
{
do
{
shift++;
z <<= 1;
} while ( z < ( 1L << 27 ) );
vec->x = x << shift;
vec->y = y << shift;
}
else if ( z > ( 1L << 28 ) )
{
do
{
shift++;
z >>= 1;
} while ( z > ( 1L << 28 ) );
vec->x = x >> shift;
vec->y = y >> shift;
shift = -shift;
}
return shift;
}
static void
af_angle_pseudo_polarize( FT_Vector* vec )
{
FT_Fixed theta;
FT_Fixed yi, i;
FT_Fixed x, y;
const FT_Fixed *arctanptr;
x = vec->x;
y = vec->y;
/* Get the vector into the right half plane */
theta = 0;
if ( x < 0 )
{
x = -x;
y = -y;
theta = AF_ANGLE_PI;
}
if ( y > 0 )
theta = -theta;
arctanptr = af_angle_arctan_table;
if ( y < 0 )
{
/* Rotate positive */
yi = y + ( x << 1 );
x = x - ( y << 1 );
y = yi;
theta -= *arctanptr++; /* Subtract angle */
}
else
{
/* Rotate negative */
yi = y - ( x << 1 );
x = x + ( y << 1 );
y = yi;
theta += *arctanptr++; /* Add angle */
}
i = 0;
do
{
if ( y < 0 )
{
/* Rotate positive */
yi = y + ( x >> i );
x = x - ( y >> i );
y = yi;
theta -= *arctanptr++;
}
else
{
/* Rotate negative */
yi = y - ( x >> i );
x = x + ( y >> i );
y = yi;
theta += *arctanptr++;
}
} while ( ++i < AF_TRIG_MAX_ITERS );
#if 0
/* round theta */
if ( theta >= 0 )
theta = FT_PAD_ROUND( theta, 2 );
else
theta = -FT_PAD_ROUND( -theta, 2 );
#endif
vec->x = x;
vec->y = theta;
}
/* cf. documentation in fttrigon.h */
FT_LOCAL_DEF( AF_Angle )
af_angle_atan( FT_Fixed dx,
FT_Fixed dy )
{
FT_Vector v;
if ( dx == 0 && dy == 0 )
return 0;
v.x = dx;
v.y = dy;
af_angle_prenorm( &v );
af_angle_pseudo_polarize( &v );
return v.y;
}
FT_LOCAL_DEF( AF_Angle )
af_angle_diff( AF_Angle angle1,
AF_Angle angle2 )
{
AF_Angle delta = angle2 - angle1;
delta %= AF_ANGLE_2PI;
if ( delta < 0 )
delta += AF_ANGLE_2PI;
if ( delta > AF_ANGLE_PI )
delta -= AF_ANGLE_2PI;
return delta;
}
#endif /* 0 */
FT_LOCAL_DEF( void )
af_sort_pos( FT_UInt count,
FT_Pos* table )
{
FT_UInt i, j;
FT_Pos swap;
for ( i = 1; i < count; i++ )
{
for ( j = i; j > 0; j-- )
{
if ( table[j] > table[j - 1] )
break;
swap = table[j];
table[j] = table[j - 1];
table[j - 1] = swap;
}
}
}
FT_LOCAL_DEF( void )
af_sort_widths( FT_UInt count,
AF_Width table )
{
FT_UInt i, j;
AF_WidthRec swap;
for ( i = 1; i < count; i++ )
{
for ( j = i; j > 0; j-- )
{
if ( table[j].org > table[j - 1].org )
break;
swap = table[j];
table[j] = table[j - 1];
table[j - 1] = swap;
}
}
}
#ifdef TEST
#include <stdio.h>
#include <math.h>
int main( void )
{
int angle;
int dist;
for ( dist = 100; dist < 1000; dist++ )
{
for ( angle = AF_ANGLE_PI; angle < AF_ANGLE_2PI * 4; angle++ )
{
double a = ( angle * 3.1415926535 ) / ( 1.0 * AF_ANGLE_PI );
int dx, dy, angle1, angle2, delta;
dx = dist * cos( a );
dy = dist * sin( a );
angle1 = ( ( atan2( dy, dx ) * AF_ANGLE_PI ) / 3.1415926535 );
angle2 = af_angle_atan( dx, dy );
delta = ( angle2 - angle1 ) % AF_ANGLE_2PI;
if ( delta < 0 )
delta = -delta;
if ( delta >= 2 )
{
printf( "dist:%4d angle:%4d => (%4d,%4d) angle1:%4d angle2:%4d\n",
dist, angle, dx, dy, angle1, angle2 );
}
}
}
return 0;
}
#endif /* TEST */
/* END */