ReactOS  0.4.14-dev-376-gaedba84
afangles.c
Go to the documentation of this file.
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-2018 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  /*
24  * We are not using `af_angle_atan' anymore, but we keep the source
25  * code below just in case...
26  */
27 
28 
29 #if 0
30 
31 
32  /*
33  * The trick here is to realize that we don't need a very accurate angle
34  * approximation. We are going to use the result of `af_angle_atan' to
35  * only compare the sign of angle differences, or check whether its
36  * magnitude is very small.
37  *
38  * The approximation
39  *
40  * dy * PI / (|dx|+|dy|)
41  *
42  * should be enough, and much faster to compute.
43  */
45  af_angle_atan( FT_Fixed dx,
46  FT_Fixed dy )
47  {
49  FT_Fixed ax = dx;
50  FT_Fixed ay = dy;
51 
52 
53  if ( ax < 0 )
54  ax = -ax;
55  if ( ay < 0 )
56  ay = -ay;
57 
58  ax += ay;
59 
60  if ( ax == 0 )
61  angle = 0;
62  else
63  {
64  angle = ( AF_ANGLE_PI2 * dy ) / ( ax + ay );
65  if ( dx < 0 )
66  {
67  if ( angle >= 0 )
69  else
70  angle = -AF_ANGLE_PI - angle;
71  }
72  }
73 
74  return angle;
75  }
76 
77 
78 #elif 0
79 
80 
81  /* the following table has been automatically generated with */
82  /* the `mather.py' Python script */
83 
84 #define AF_ATAN_BITS 8
85 
86  static const FT_Byte af_arctan[1L << AF_ATAN_BITS] =
87  {
88  0, 0, 1, 1, 1, 2, 2, 2,
89  3, 3, 3, 3, 4, 4, 4, 5,
90  5, 5, 6, 6, 6, 7, 7, 7,
91  8, 8, 8, 9, 9, 9, 10, 10,
92  10, 10, 11, 11, 11, 12, 12, 12,
93  13, 13, 13, 14, 14, 14, 14, 15,
94  15, 15, 16, 16, 16, 17, 17, 17,
95  18, 18, 18, 18, 19, 19, 19, 20,
96  20, 20, 21, 21, 21, 21, 22, 22,
97  22, 23, 23, 23, 24, 24, 24, 24,
98  25, 25, 25, 26, 26, 26, 26, 27,
99  27, 27, 28, 28, 28, 28, 29, 29,
100  29, 30, 30, 30, 30, 31, 31, 31,
101  31, 32, 32, 32, 33, 33, 33, 33,
102  34, 34, 34, 34, 35, 35, 35, 35,
103  36, 36, 36, 36, 37, 37, 37, 38,
104  38, 38, 38, 39, 39, 39, 39, 40,
105  40, 40, 40, 41, 41, 41, 41, 42,
106  42, 42, 42, 42, 43, 43, 43, 43,
107  44, 44, 44, 44, 45, 45, 45, 45,
108  46, 46, 46, 46, 46, 47, 47, 47,
109  47, 48, 48, 48, 48, 48, 49, 49,
110  49, 49, 50, 50, 50, 50, 50, 51,
111  51, 51, 51, 51, 52, 52, 52, 52,
112  52, 53, 53, 53, 53, 53, 54, 54,
113  54, 54, 54, 55, 55, 55, 55, 55,
114  56, 56, 56, 56, 56, 57, 57, 57,
115  57, 57, 57, 58, 58, 58, 58, 58,
116  59, 59, 59, 59, 59, 59, 60, 60,
117  60, 60, 60, 61, 61, 61, 61, 61,
118  61, 62, 62, 62, 62, 62, 62, 63,
119  63, 63, 63, 63, 63, 64, 64, 64
120  };
121 
122 
124  af_angle_atan( FT_Fixed dx,
125  FT_Fixed dy )
126  {
127  AF_Angle angle;
128 
129 
130  /* check trivial cases */
131  if ( dy == 0 )
132  {
133  angle = 0;
134  if ( dx < 0 )
135  angle = AF_ANGLE_PI;
136  return angle;
137  }
138  else if ( dx == 0 )
139  {
141  if ( dy < 0 )
142  angle = -AF_ANGLE_PI2;
143  return angle;
144  }
145 
146  angle = 0;
147  if ( dx < 0 )
148  {
149  dx = -dx;
150  dy = -dy;
151  angle = AF_ANGLE_PI;
152  }
153 
154  if ( dy < 0 )
155  {
156  FT_Pos tmp;
157 
158 
159  tmp = dx;
160  dx = -dy;
161  dy = tmp;
162  angle -= AF_ANGLE_PI2;
163  }
164 
165  if ( dx == 0 && dy == 0 )
166  return 0;
167 
168  if ( dx == dy )
169  angle += AF_ANGLE_PI4;
170  else if ( dx > dy )
171  angle += af_arctan[FT_DivFix( dy, dx ) >> ( 16 - AF_ATAN_BITS )];
172  else
173  angle += AF_ANGLE_PI2 -
174  af_arctan[FT_DivFix( dx, dy ) >> ( 16 - AF_ATAN_BITS )];
175 
176  if ( angle > AF_ANGLE_PI )
177  angle -= AF_ANGLE_2PI;
178 
179  return angle;
180  }
181 
182 
183 #endif /* 0 */
184 
185 
186  FT_LOCAL_DEF( void )
188  FT_Pos* table )
189  {
190  FT_UInt i, j;
191  FT_Pos swap;
192 
193 
194  for ( i = 1; i < count; i++ )
195  {
196  for ( j = i; j > 0; j-- )
197  {
198  if ( table[j] >= table[j - 1] )
199  break;
200 
201  swap = table[j];
202  table[j] = table[j - 1];
203  table[j - 1] = swap;
204  }
205  }
206  }
207 
208 
209  FT_LOCAL_DEF( void )
211  AF_Width table,
212  FT_Pos threshold )
213  {
214  FT_UInt i, j;
215  FT_UInt cur_idx;
216  FT_Pos cur_val;
217  FT_Pos sum;
219 
220 
221  if ( *count == 1 )
222  return;
223 
224  /* sort */
225  for ( i = 1; i < *count; i++ )
226  {
227  for ( j = i; j > 0; j-- )
228  {
229  if ( table[j].org >= table[j - 1].org )
230  break;
231 
232  swap = table[j];
233  table[j] = table[j - 1];
234  table[j - 1] = swap;
235  }
236  }
237 
238  cur_idx = 0;
239  cur_val = table[cur_idx].org;
240 
241  /* compute and use mean values for clusters not larger than */
242  /* `threshold'; this is very primitive and might not yield */
243  /* the best result, but normally, using reference character */
244  /* `o', `*count' is 2, so the code below is fully sufficient */
245  for ( i = 1; i < *count; i++ )
246  {
247  if ( table[i].org - cur_val > threshold ||
248  i == *count - 1 )
249  {
250  sum = 0;
251 
252  /* fix loop for end of array */
253  if ( table[i].org - cur_val <= threshold &&
254  i == *count - 1 )
255  i++;
256 
257  for ( j = cur_idx; j < i; j++ )
258  {
259  sum += table[j].org;
260  table[j].org = 0;
261  }
262  table[cur_idx].org = sum / (FT_Pos)j;
263 
264  if ( i < *count - 1 )
265  {
266  cur_idx = i + 1;
267  cur_val = table[cur_idx].org;
268  }
269  }
270  }
271 
272  cur_idx = 1;
273 
274  /* compress array to remove zero values */
275  for ( i = 1; i < *count; i++ )
276  {
277  if ( table[i].org )
278  table[cur_idx++] = table[i];
279  }
280 
281  *count = cur_idx;
282  }
283 
284 
285 /* END */
FT_DivFix(FT_Long a, FT_Long b)
Definition: ftcalc.c:608
FT_BEGIN_HEADER typedef signed long FT_Pos
Definition: ftimage.h:58
#define swap(a, b)
Definition: qsort.c:63
GLuint GLuint GLsizei count
Definition: gl.h:1545
GLint dy
Definition: linetemp.h:97
GLfloat angle
Definition: glext.h:10853
af_sort_and_quantize_widths(FT_UInt *count, AF_Width table, FT_Pos threshold)
Definition: afangles.c:210
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
unsigned char FT_Byte
Definition: fttypes.h:154
static char org[]
Definition: encode.c:7456
#define AF_ANGLE_PI2
ecx edi ebx edx edi decl ecx esi eax jecxz decl eax andl eax esi movl edx movl TEMP incl eax andl eax ecx incl ebx eax jnz xchgl ecx incl TEMP esp ecx subl ebx pushl ecx ecx edx ecx ecx mm0 mm4 mm0 mm4 mm1 mm5 mm1 mm5 mm2 mm6 mm2 mm6 mm3 mm7 mm3 mm7 paddd mm0 paddd mm4 paddd mm0 paddd mm4 paddd mm0 paddd mm4 movq mm1 movq mm5 mm1 mm5 paddd mm0 paddd mm4 mm0 mm4 packssdw mm0 packssdw mm4 mm1 punpckldq mm0 pand mm1 pand mm0 por mm1 movq edi esi edx edi decl ecx jnz popl ecx ecx jecxz mm0 mm0 mm1 mm1 mm2 mm2 mm3 mm3 paddd mm0 paddd mm0 paddd mm0 movq mm1 mm1 paddd mm0 mm0 packssdw mm0 movd eax movw ax
Definition: synth_sse3d.h:171
#define AF_ANGLE_PI4
#define FT_LOCAL_DEF(x)
Definition: ftconfig.h:388
static int sum(int x_, int y_)
Definition: ptr2_test.cpp:35
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint GLint GLint j
Definition: glfuncs.h:250
FT_Int AF_Angle
Definition: aftypes.h:110
static const WCHAR L[]
Definition: oid.c:1250
signed long FT_Fixed
Definition: fttypes.h:288
FT_BEGIN_HEADER struct AF_WidthRec_ * AF_Width
unsigned int FT_UInt
Definition: fttypes.h:231
FT_BEGIN_HEADER struct AF_WidthRec_ AF_WidthRec
GLint dx
Definition: linetemp.h:97
#define AF_ANGLE_2PI
#define AF_ANGLE_PI
af_sort_pos(FT_UInt count, FT_Pos *table)
Definition: afangles.c:187