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 (C) 2003-2019 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 */
44 FT_LOCAL_DEF( AF_Angle )
45 af_angle_atan( FT_Fixed dx,
46 FT_Fixed dy )
47 {
48 AF_Angle angle;
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 )
68 angle = AF_ANGLE_PI - angle;
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
123 FT_LOCAL_DEF( AF_Angle )
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 {
140 angle = AF_ANGLE_PI2;
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 )
187 af_sort_pos( FT_UInt count,
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 )
210 af_sort_and_quantize_widths( FT_UInt* count,
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;
218 AF_WidthRec swap;
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 */