ReactOS 0.4.15-dev-8339-g4028de8
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/* */
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 * 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
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 {
128
129
130 /* check trivial cases */
131 if ( dy == 0 )
132 {
133 angle = 0;
134 if ( dx < 0 )
136 return angle;
137 }
138 else if ( dx == 0 )
139 {
141 if ( dy < 0 )
143 return angle;
144 }
145
146 angle = 0;
147 if ( dx < 0 )
148 {
149 dx = -dx;
150 dy = -dy;
152 }
153
154 if ( dy < 0 )
155 {
156 FT_Pos tmp;
157
158
159 tmp = dx;
160 dx = -dy;
161 dy = tmp;
163 }
164
165 if ( dx == 0 && dy == 0 )
166 return 0;
167
168 if ( dx == dy )
170 else if ( dx > dy )
171 angle += af_arctan[FT_DivFix( dy, dx ) >> ( 16 - AF_ATAN_BITS )];
172 else
174 af_arctan[FT_DivFix( dx, dy ) >> ( 16 - AF_ATAN_BITS )];
175
176 if ( angle > AF_ANGLE_PI )
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 )
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 */
af_sort_pos(FT_UInt count, FT_Pos *table)
Definition: afangles.c:187
af_sort_and_quantize_widths(FT_UInt *count, AF_Width table, FT_Pos threshold)
Definition: afangles.c:210
#define AF_ANGLE_PI2
Definition: aftypes.h:115
FT_Int AF_Angle
Definition: aftypes.h:110
#define AF_ANGLE_2PI
Definition: aftypes.h:114
#define AF_ANGLE_PI
Definition: aftypes.h:113
#define AF_ANGLE_PI4
Definition: aftypes.h:116
FT_DivFix(FT_Long a, FT_Long b)
Definition: ftcalc.c:608
#define FT_LOCAL_DEF(x)
Definition: ftconfig.h:388
Definition: ftimage.h:58
unsigned char FT_Byte
Definition: fttypes.h:154
signed long FT_Fixed
Definition: fttypes.h:288
unsigned int FT_UInt
Definition: fttypes.h:231
GLuint GLuint GLsizei count
Definition: gl.h:1545
GLfloat angle
Definition: glext.h:10853
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
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
GLint dy
Definition: linetemp.h:97
GLint dx
Definition: linetemp.h:97
static char org[]
Definition: encode.c:7456
static int sum(int x_, int y_)
Definition: ptr2_test.cpp:35
#define swap(a, b)
Definition: qsort.c:63