Visualization Library 2.0.0-b5

A lightweight C++ OpenGL middleware for 2D/3D graphics

VL     Star     Watch     Fork     Issue

[Download] [Tutorials] [All Classes] [Grouped Classes]
fttrigon.c
Go to the documentation of this file.
1 /***************************************************************************/
2 /* */
3 /* fttrigon.c */
4 /* */
5 /* FreeType trigonometric functions (body). */
6 /* */
7 /* Copyright 2001-2005, 2012-2013 by */
8 /* David Turner, Robert Wilhelm, and Werner Lemberg. */
9 /* */
10 /* This file is part of the FreeType project, and may only be used, */
11 /* modified, and distributed under the terms of the FreeType project */
12 /* license, LICENSE.TXT. By continuing to use, modify, or distribute */
13 /* this file you indicate that you have read the license and */
14 /* understand and accept it fully. */
15 /* */
16 /***************************************************************************/
17 
18  /*************************************************************************/
19  /* */
20  /* This is a fixed-point CORDIC implementation of trigonometric */
21  /* functions as well as transformations between Cartesian and polar */
22  /* coordinates. The angles are represented as 16.16 fixed-point values */
23  /* in degrees, i.e., the angular resolution is 2^-16 degrees. Note that */
24  /* only vectors longer than 2^16*180/pi (or at least 22 bits) on a */
25  /* discrete Cartesian grid can have the same or better angular */
26  /* resolution. Therefore, to maintain this precision, some functions */
27  /* require an interim upscaling of the vectors, whereas others operate */
28  /* with 24-bit long vectors directly. */
29  /* */
30  /*************************************************************************/
31 
32 #include <ft2build.h>
33 #include FT_INTERNAL_OBJECTS_H
34 #include FT_INTERNAL_CALC_H
35 #include FT_TRIGONOMETRY_H
36 
37 
38  /* the Cordic shrink factor 0.858785336480436 * 2^32 */
39 #define FT_TRIG_SCALE 0xDBD95B16UL
40 
41  /* the highest bit in overflow-safe vector components, */
42  /* MSB of 0.858785336480436 * sqrt(0.5) * 2^30 */
43 #define FT_TRIG_SAFE_MSB 29
44 
45  /* this table was generated for FT_PI = 180L << 16, i.e. degrees */
46 #define FT_TRIG_MAX_ITERS 23
47 
48  static const FT_Fixed
49  ft_trig_arctan_table[] =
50  {
51  1740967L, 919879L, 466945L, 234379L, 117304L, 58666L, 29335L,
52  14668L, 7334L, 3667L, 1833L, 917L, 458L, 229L, 115L,
53  57L, 29L, 14L, 7L, 4L, 2L, 1L
54  };
55 
56 
57 #ifdef FT_LONG64
58 
59  /* multiply a given value by the CORDIC shrink factor */
60  static FT_Fixed
61  ft_trig_downscale( FT_Fixed val )
62  {
63  FT_Fixed s;
64  FT_Int64 v;
65 
66 
67  s = val;
68  val = FT_ABS( val );
69 
70  v = ( val * (FT_Int64)FT_TRIG_SCALE ) + 0x100000000UL;
71  val = (FT_Fixed)( v >> 32 );
72 
73  return ( s >= 0 ) ? val : -val;
74  }
75 
76 #else /* !FT_LONG64 */
77 
78  /* multiply a given value by the CORDIC shrink factor */
79  static FT_Fixed
80  ft_trig_downscale( FT_Fixed val )
81  {
82  FT_Fixed s;
83  FT_UInt32 v1, v2, k1, k2, hi, lo1, lo2, lo3;
84 
85 
86  s = val;
87  val = FT_ABS( val );
88 
89  v1 = (FT_UInt32)val >> 16;
90  v2 = (FT_UInt32)( val & 0xFFFFL );
91 
92  k1 = (FT_UInt32)FT_TRIG_SCALE >> 16; /* constant */
93  k2 = (FT_UInt32)( FT_TRIG_SCALE & 0xFFFFL ); /* constant */
94 
95  hi = k1 * v1;
96  lo1 = k1 * v2 + k2 * v1; /* can't overflow */
97 
98  lo2 = ( k2 * v2 ) >> 16;
99  lo3 = FT_MAX( lo1, lo2 );
100  lo1 += lo2;
101 
102  hi += lo1 >> 16;
103  if ( lo1 < lo3 )
104  hi += (FT_UInt32)0x10000UL;
105 
106  val = (FT_Fixed)hi;
107 
108  return ( s >= 0 ) ? val : -val;
109  }
110 
111 #endif /* !FT_LONG64 */
112 
113 
114  static FT_Int
115  ft_trig_prenorm( FT_Vector* vec )
116  {
117  FT_Pos x, y;
118  FT_Int shift;
119 
120 
121  x = vec->x;
122  y = vec->y;
123 
124  shift = FT_MSB( FT_ABS( x ) | FT_ABS( y ) );
125 
126  if ( shift <= FT_TRIG_SAFE_MSB )
127  {
128  shift = FT_TRIG_SAFE_MSB - shift;
129  vec->x = (FT_Pos)( (FT_ULong)x << shift );
130  vec->y = (FT_Pos)( (FT_ULong)y << shift );
131  }
132  else
133  {
134  shift -= FT_TRIG_SAFE_MSB;
135  vec->x = x >> shift;
136  vec->y = y >> shift;
137  shift = -shift;
138  }
139 
140  return shift;
141  }
142 
143 
144  static void
145  ft_trig_pseudo_rotate( FT_Vector* vec,
146  FT_Angle theta )
147  {
148  FT_Int i;
149  FT_Fixed x, y, xtemp, b;
150  const FT_Fixed *arctanptr;
151 
152 
153  x = vec->x;
154  y = vec->y;
155 
156  /* Rotate inside [-PI/4,PI/4] sector */
157  while ( theta < -FT_ANGLE_PI4 )
158  {
159  xtemp = y;
160  y = -x;
161  x = xtemp;
162  theta += FT_ANGLE_PI2;
163  }
164 
165  while ( theta > FT_ANGLE_PI4 )
166  {
167  xtemp = -y;
168  y = x;
169  x = xtemp;
170  theta -= FT_ANGLE_PI2;
171  }
172 
173  arctanptr = ft_trig_arctan_table;
174 
175  /* Pseudorotations, with right shifts */
176  for ( i = 1, b = 1; i < FT_TRIG_MAX_ITERS; b <<= 1, i++ )
177  {
178  if ( theta < 0 )
179  {
180  xtemp = x + ( ( y + b ) >> i );
181  y = y - ( ( x + b ) >> i );
182  x = xtemp;
183  theta += *arctanptr++;
184  }
185  else
186  {
187  xtemp = x - ( ( y + b ) >> i );
188  y = y + ( ( x + b ) >> i );
189  x = xtemp;
190  theta -= *arctanptr++;
191  }
192  }
193 
194  vec->x = x;
195  vec->y = y;
196  }
197 
198 
199  static void
200  ft_trig_pseudo_polarize( FT_Vector* vec )
201  {
202  FT_Angle theta;
203  FT_Int i;
204  FT_Fixed x, y, xtemp, b;
205  const FT_Fixed *arctanptr;
206 
207 
208  x = vec->x;
209  y = vec->y;
210 
211  /* Get the vector into [-PI/4,PI/4] sector */
212  if ( y > x )
213  {
214  if ( y > -x )
215  {
216  theta = FT_ANGLE_PI2;
217  xtemp = y;
218  y = -x;
219  x = xtemp;
220  }
221  else
222  {
223  theta = y > 0 ? FT_ANGLE_PI : -FT_ANGLE_PI;
224  x = -x;
225  y = -y;
226  }
227  }
228  else
229  {
230  if ( y < -x )
231  {
232  theta = -FT_ANGLE_PI2;
233  xtemp = -y;
234  y = x;
235  x = xtemp;
236  }
237  else
238  {
239  theta = 0;
240  }
241  }
242 
243  arctanptr = ft_trig_arctan_table;
244 
245  /* Pseudorotations, with right shifts */
246  for ( i = 1, b = 1; i < FT_TRIG_MAX_ITERS; b <<= 1, i++ )
247  {
248  if ( y > 0 )
249  {
250  xtemp = x + ( ( y + b ) >> i );
251  y = y - ( ( x + b ) >> i );
252  x = xtemp;
253  theta += *arctanptr++;
254  }
255  else
256  {
257  xtemp = x - ( ( y + b ) >> i );
258  y = y + ( ( x + b ) >> i );
259  x = xtemp;
260  theta -= *arctanptr++;
261  }
262  }
263 
264  /* round theta */
265  if ( theta >= 0 )
266  theta = FT_PAD_ROUND( theta, 32 );
267  else
268  theta = -FT_PAD_ROUND( -theta, 32 );
269 
270  vec->x = x;
271  vec->y = theta;
272  }
273 
274 
275  /* documentation is in fttrigon.h */
276 
279  {
280  FT_Vector v;
281 
282 
283  v.x = FT_TRIG_SCALE >> 8;
284  v.y = 0;
285  ft_trig_pseudo_rotate( &v, angle );
286 
287  return ( v.x + 0x80L ) >> 8;
288  }
289 
290 
291  /* documentation is in fttrigon.h */
292 
295  {
296  return FT_Cos( FT_ANGLE_PI2 - angle );
297  }
298 
299 
300  /* documentation is in fttrigon.h */
301 
304  {
305  FT_Vector v;
306 
307 
308  v.x = FT_TRIG_SCALE >> 8;
309  v.y = 0;
310  ft_trig_pseudo_rotate( &v, angle );
311 
312  return FT_DivFix( v.y, v.x );
313  }
314 
315 
316  /* documentation is in fttrigon.h */
317 
320  FT_Fixed dy )
321  {
322  FT_Vector v;
323 
324 
325  if ( dx == 0 && dy == 0 )
326  return 0;
327 
328  v.x = dx;
329  v.y = dy;
330  ft_trig_prenorm( &v );
331  ft_trig_pseudo_polarize( &v );
332 
333  return v.y;
334  }
335 
336 
337  /* documentation is in fttrigon.h */
338 
339  FT_EXPORT_DEF( void )
341  FT_Angle angle )
342  {
343  vec->x = FT_TRIG_SCALE >> 8;
344  vec->y = 0;
345  ft_trig_pseudo_rotate( vec, angle );
346  vec->x = ( vec->x + 0x80L ) >> 8;
347  vec->y = ( vec->y + 0x80L ) >> 8;
348  }
349 
350 
351  /* these macros return 0 for positive numbers,
352  and -1 for negative ones */
353 #define FT_SIGN_LONG( x ) ( (x) >> ( FT_SIZEOF_LONG * 8 - 1 ) )
354 #define FT_SIGN_INT( x ) ( (x) >> ( FT_SIZEOF_INT * 8 - 1 ) )
355 #define FT_SIGN_INT32( x ) ( (x) >> 31 )
356 #define FT_SIGN_INT16( x ) ( (x) >> 15 )
357 
358 
359  /* documentation is in fttrigon.h */
360 
361  FT_EXPORT_DEF( void )
363  FT_Angle angle )
364  {
365  FT_Int shift;
366  FT_Vector v;
367 
368 
369  v.x = vec->x;
370  v.y = vec->y;
371 
372  if ( angle && ( v.x != 0 || v.y != 0 ) )
373  {
374  shift = ft_trig_prenorm( &v );
375  ft_trig_pseudo_rotate( &v, angle );
376  v.x = ft_trig_downscale( v.x );
377  v.y = ft_trig_downscale( v.y );
378 
379  if ( shift > 0 )
380  {
381  FT_Int32 half = (FT_Int32)1L << ( shift - 1 );
382 
383 
384  vec->x = ( v.x + half + FT_SIGN_LONG( v.x ) ) >> shift;
385  vec->y = ( v.y + half + FT_SIGN_LONG( v.y ) ) >> shift;
386  }
387  else
388  {
389  shift = -shift;
390  vec->x = (FT_Pos)( (FT_ULong)v.x << shift );
391  vec->y = (FT_Pos)( (FT_ULong)v.y << shift );
392  }
393  }
394  }
395 
396 
397  /* documentation is in fttrigon.h */
398 
401  {
402  FT_Int shift;
403  FT_Vector v;
404 
405 
406  v = *vec;
407 
408  /* handle trivial cases */
409  if ( v.x == 0 )
410  {
411  return FT_ABS( v.y );
412  }
413  else if ( v.y == 0 )
414  {
415  return FT_ABS( v.x );
416  }
417 
418  /* general case */
419  shift = ft_trig_prenorm( &v );
420  ft_trig_pseudo_polarize( &v );
421 
422  v.x = ft_trig_downscale( v.x );
423 
424  if ( shift > 0 )
425  return ( v.x + ( 1 << ( shift - 1 ) ) ) >> shift;
426 
427  return (FT_Fixed)( (FT_UInt32)v.x << -shift );
428  }
429 
430 
431  /* documentation is in fttrigon.h */
432 
433  FT_EXPORT_DEF( void )
435  FT_Fixed *length,
436  FT_Angle *angle )
437  {
438  FT_Int shift;
439  FT_Vector v;
440 
441 
442  v = *vec;
443 
444  if ( v.x == 0 && v.y == 0 )
445  return;
446 
447  shift = ft_trig_prenorm( &v );
448  ft_trig_pseudo_polarize( &v );
449 
450  v.x = ft_trig_downscale( v.x );
451 
452  *length = ( shift >= 0 ) ? ( v.x >> shift )
453  : (FT_Fixed)( (FT_UInt32)v.x << -shift );
454  *angle = v.y;
455  }
456 
457 
458  /* documentation is in fttrigon.h */
459 
460  FT_EXPORT_DEF( void )
463  FT_Angle angle )
464  {
465  vec->x = length;
466  vec->y = 0;
467 
468  FT_Vector_Rotate( vec, angle );
469  }
470 
471 
472  /* documentation is in fttrigon.h */
473 
476  FT_Angle angle2 )
477  {
478  FT_Angle delta = angle2 - angle1;
479 
480 
481  delta %= FT_ANGLE_2PI;
482  if ( delta < 0 )
483  delta += FT_ANGLE_2PI;
484 
485  if ( delta > FT_ANGLE_PI )
486  delta -= FT_ANGLE_2PI;
487 
488  return delta;
489  }
490 
491 
492 /* END */
GLenum GLuint GLenum GLsizei length
FT_DivFix(FT_Long a, FT_Long b)
Definition: ftcalc.c:586
angle2
Definition: cordic.py:18
unsigned long FT_ULong
Definition: fttypes.h:249
FT_BEGIN_HEADER typedef signed long FT_Pos
Definition: ftimage.h:59
#define FT_ANGLE_PI2
Definition: fttrigon.h:88
GLfloat GLfloat GLfloat v2
GLint GLint GLint GLint GLint GLint y
FT_Cos(FT_Angle angle)
Definition: fttrigon.c:278
signed int FT_Int
Definition: fttypes.h:216
#define FT_ABS(a)
Definition: ftobjs.h:73
#define FT_TRIG_MAX_ITERS
Definition: fttrigon.c:46
unsigned int FT_UInt32
Definition: ftconfig.h:133
#define FT_TRIG_SCALE
Definition: fttrigon.c:39
GLint GLint GLint GLint GLint x
FT_Tan(FT_Angle angle)
Definition: fttrigon.c:303
GLboolean GLboolean GLboolean b
GLfloat GLfloat v1
png_uint_32 i
Definition: png.h:2640
FT_Atan2(FT_Fixed dx, FT_Fixed dy)
Definition: fttrigon.c:319
#define FT_ANGLE_PI4
Definition: fttrigon.h:100
#define FT_EXPORT_DEF(x)
Definition: ftconfig.h:32
FT_Vector_From_Polar(FT_Vector *vec, FT_Fixed length, FT_Angle angle)
Definition: fttrigon.c:461
#define FT_PAD_ROUND(x, n)
Definition: ftobjs.h:77
#define FT_ANGLE_PI
Definition: fttrigon.h:64
const GLdouble * v
FT_Pos x
Definition: ftimage.h:77
FT_Vector_Rotate(FT_Vector *vec, FT_Angle angle)
Definition: fttrigon.c:362
FT_Pos y
Definition: ftimage.h:78
#define FT_TRIG_SAFE_MSB
Definition: fttrigon.c:43
#define FT_MAX(a, b)
Definition: ftobjs.h:71
GLuint GLfloat * val
signed int FT_Int32
Definition: ftconfig.h:132
FT_BEGIN_HEADER typedef FT_Fixed FT_Angle
Definition: fttrigon.h:52
GLfloat angle
FT_Sin(FT_Angle angle)
Definition: fttrigon.c:294
#define FT_ANGLE_2PI
Definition: fttrigon.h:76
FT_Vector * vec
Definition: ftbbox.c:566
FT_MSB(FT_UInt32 z)
Definition: ftcalc.c:104
FT_Vector_Unit(FT_Vector *vec, FT_Angle angle)
Definition: fttrigon.c:340
FT_Angle_Diff(FT_Angle angle1, FT_Angle angle2)
Definition: fttrigon.c:475
signed long FT_Fixed
Definition: fttypes.h:284
FT_Vector_Length(FT_Vector *vec)
Definition: fttrigon.c:400
GLdouble s
#define FT_SIGN_LONG(x)
Definition: fttrigon.c:353
struct FT_Int64_ FT_Int64
FT_Vector_Polarize(FT_Vector *vec, FT_Fixed *length, FT_Angle *angle)
Definition: fttrigon.c:434