|
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-2006, 2011 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 #if 0 |
|
24 |
|
25 FT_LOCAL_DEF( FT_Int ) |
|
26 af_corner_is_flat( FT_Pos x_in, |
|
27 FT_Pos y_in, |
|
28 FT_Pos x_out, |
|
29 FT_Pos y_out ) |
|
30 { |
|
31 FT_Pos ax = x_in; |
|
32 FT_Pos ay = y_in; |
|
33 |
|
34 FT_Pos d_in, d_out, d_corner; |
|
35 |
|
36 |
|
37 if ( ax < 0 ) |
|
38 ax = -ax; |
|
39 if ( ay < 0 ) |
|
40 ay = -ay; |
|
41 d_in = ax + ay; |
|
42 |
|
43 ax = x_out; |
|
44 if ( ax < 0 ) |
|
45 ax = -ax; |
|
46 ay = y_out; |
|
47 if ( ay < 0 ) |
|
48 ay = -ay; |
|
49 d_out = ax + ay; |
|
50 |
|
51 ax = x_out + x_in; |
|
52 if ( ax < 0 ) |
|
53 ax = -ax; |
|
54 ay = y_out + y_in; |
|
55 if ( ay < 0 ) |
|
56 ay = -ay; |
|
57 d_corner = ax + ay; |
|
58 |
|
59 return ( d_in + d_out - d_corner ) < ( d_corner >> 4 ); |
|
60 } |
|
61 |
|
62 |
|
63 FT_LOCAL_DEF( FT_Int ) |
|
64 af_corner_orientation( FT_Pos x_in, |
|
65 FT_Pos y_in, |
|
66 FT_Pos x_out, |
|
67 FT_Pos y_out ) |
|
68 { |
|
69 FT_Pos delta; |
|
70 |
|
71 |
|
72 delta = x_in * y_out - y_in * x_out; |
|
73 |
|
74 if ( delta == 0 ) |
|
75 return 0; |
|
76 else |
|
77 return 1 - 2 * ( delta < 0 ); |
|
78 } |
|
79 |
|
80 #endif /* 0 */ |
|
81 |
|
82 |
|
83 /* |
|
84 * We are not using `af_angle_atan' anymore, but we keep the source |
|
85 * code below just in case... |
|
86 */ |
|
87 |
|
88 |
|
89 #if 0 |
|
90 |
|
91 |
|
92 /* |
|
93 * The trick here is to realize that we don't need a very accurate angle |
|
94 * approximation. We are going to use the result of `af_angle_atan' to |
|
95 * only compare the sign of angle differences, or check whether its |
|
96 * magnitude is very small. |
|
97 * |
|
98 * The approximation |
|
99 * |
|
100 * dy * PI / (|dx|+|dy|) |
|
101 * |
|
102 * should be enough, and much faster to compute. |
|
103 */ |
|
104 FT_LOCAL_DEF( AF_Angle ) |
|
105 af_angle_atan( FT_Fixed dx, |
|
106 FT_Fixed dy ) |
|
107 { |
|
108 AF_Angle angle; |
|
109 FT_Fixed ax = dx; |
|
110 FT_Fixed ay = dy; |
|
111 |
|
112 |
|
113 if ( ax < 0 ) |
|
114 ax = -ax; |
|
115 if ( ay < 0 ) |
|
116 ay = -ay; |
|
117 |
|
118 ax += ay; |
|
119 |
|
120 if ( ax == 0 ) |
|
121 angle = 0; |
|
122 else |
|
123 { |
|
124 angle = ( AF_ANGLE_PI2 * dy ) / ( ax + ay ); |
|
125 if ( dx < 0 ) |
|
126 { |
|
127 if ( angle >= 0 ) |
|
128 angle = AF_ANGLE_PI - angle; |
|
129 else |
|
130 angle = -AF_ANGLE_PI - angle; |
|
131 } |
|
132 } |
|
133 |
|
134 return angle; |
|
135 } |
|
136 |
|
137 |
|
138 #elif 0 |
|
139 |
|
140 |
|
141 /* the following table has been automatically generated with */ |
|
142 /* the `mather.py' Python script */ |
|
143 |
|
144 #define AF_ATAN_BITS 8 |
|
145 |
|
146 static const FT_Byte af_arctan[1L << AF_ATAN_BITS] = |
|
147 { |
|
148 0, 0, 1, 1, 1, 2, 2, 2, |
|
149 3, 3, 3, 3, 4, 4, 4, 5, |
|
150 5, 5, 6, 6, 6, 7, 7, 7, |
|
151 8, 8, 8, 9, 9, 9, 10, 10, |
|
152 10, 10, 11, 11, 11, 12, 12, 12, |
|
153 13, 13, 13, 14, 14, 14, 14, 15, |
|
154 15, 15, 16, 16, 16, 17, 17, 17, |
|
155 18, 18, 18, 18, 19, 19, 19, 20, |
|
156 20, 20, 21, 21, 21, 21, 22, 22, |
|
157 22, 23, 23, 23, 24, 24, 24, 24, |
|
158 25, 25, 25, 26, 26, 26, 26, 27, |
|
159 27, 27, 28, 28, 28, 28, 29, 29, |
|
160 29, 30, 30, 30, 30, 31, 31, 31, |
|
161 31, 32, 32, 32, 33, 33, 33, 33, |
|
162 34, 34, 34, 34, 35, 35, 35, 35, |
|
163 36, 36, 36, 36, 37, 37, 37, 38, |
|
164 38, 38, 38, 39, 39, 39, 39, 40, |
|
165 40, 40, 40, 41, 41, 41, 41, 42, |
|
166 42, 42, 42, 42, 43, 43, 43, 43, |
|
167 44, 44, 44, 44, 45, 45, 45, 45, |
|
168 46, 46, 46, 46, 46, 47, 47, 47, |
|
169 47, 48, 48, 48, 48, 48, 49, 49, |
|
170 49, 49, 50, 50, 50, 50, 50, 51, |
|
171 51, 51, 51, 51, 52, 52, 52, 52, |
|
172 52, 53, 53, 53, 53, 53, 54, 54, |
|
173 54, 54, 54, 55, 55, 55, 55, 55, |
|
174 56, 56, 56, 56, 56, 57, 57, 57, |
|
175 57, 57, 57, 58, 58, 58, 58, 58, |
|
176 59, 59, 59, 59, 59, 59, 60, 60, |
|
177 60, 60, 60, 61, 61, 61, 61, 61, |
|
178 61, 62, 62, 62, 62, 62, 62, 63, |
|
179 63, 63, 63, 63, 63, 64, 64, 64 |
|
180 }; |
|
181 |
|
182 |
|
183 FT_LOCAL_DEF( AF_Angle ) |
|
184 af_angle_atan( FT_Fixed dx, |
|
185 FT_Fixed dy ) |
|
186 { |
|
187 AF_Angle angle; |
|
188 |
|
189 |
|
190 /* check trivial cases */ |
|
191 if ( dy == 0 ) |
|
192 { |
|
193 angle = 0; |
|
194 if ( dx < 0 ) |
|
195 angle = AF_ANGLE_PI; |
|
196 return angle; |
|
197 } |
|
198 else if ( dx == 0 ) |
|
199 { |
|
200 angle = AF_ANGLE_PI2; |
|
201 if ( dy < 0 ) |
|
202 angle = -AF_ANGLE_PI2; |
|
203 return angle; |
|
204 } |
|
205 |
|
206 angle = 0; |
|
207 if ( dx < 0 ) |
|
208 { |
|
209 dx = -dx; |
|
210 dy = -dy; |
|
211 angle = AF_ANGLE_PI; |
|
212 } |
|
213 |
|
214 if ( dy < 0 ) |
|
215 { |
|
216 FT_Pos tmp; |
|
217 |
|
218 |
|
219 tmp = dx; |
|
220 dx = -dy; |
|
221 dy = tmp; |
|
222 angle -= AF_ANGLE_PI2; |
|
223 } |
|
224 |
|
225 if ( dx == 0 && dy == 0 ) |
|
226 return 0; |
|
227 |
|
228 if ( dx == dy ) |
|
229 angle += AF_ANGLE_PI4; |
|
230 else if ( dx > dy ) |
|
231 angle += af_arctan[FT_DivFix( dy, dx ) >> ( 16 - AF_ATAN_BITS )]; |
|
232 else |
|
233 angle += AF_ANGLE_PI2 - |
|
234 af_arctan[FT_DivFix( dx, dy ) >> ( 16 - AF_ATAN_BITS )]; |
|
235 |
|
236 if ( angle > AF_ANGLE_PI ) |
|
237 angle -= AF_ANGLE_2PI; |
|
238 |
|
239 return angle; |
|
240 } |
|
241 |
|
242 |
|
243 #endif /* 0 */ |
|
244 |
|
245 |
|
246 FT_LOCAL_DEF( void ) |
|
247 af_sort_pos( FT_UInt count, |
|
248 FT_Pos* table ) |
|
249 { |
|
250 FT_UInt i, j; |
|
251 FT_Pos swap; |
|
252 |
|
253 |
|
254 for ( i = 1; i < count; i++ ) |
|
255 { |
|
256 for ( j = i; j > 0; j-- ) |
|
257 { |
|
258 if ( table[j] > table[j - 1] ) |
|
259 break; |
|
260 |
|
261 swap = table[j]; |
|
262 table[j] = table[j - 1]; |
|
263 table[j - 1] = swap; |
|
264 } |
|
265 } |
|
266 } |
|
267 |
|
268 |
|
269 FT_LOCAL_DEF( void ) |
|
270 af_sort_widths( FT_UInt count, |
|
271 AF_Width table ) |
|
272 { |
|
273 FT_UInt i, j; |
|
274 AF_WidthRec swap; |
|
275 |
|
276 |
|
277 for ( i = 1; i < count; i++ ) |
|
278 { |
|
279 for ( j = i; j > 0; j-- ) |
|
280 { |
|
281 if ( table[j].org > table[j - 1].org ) |
|
282 break; |
|
283 |
|
284 swap = table[j]; |
|
285 table[j] = table[j - 1]; |
|
286 table[j - 1] = swap; |
|
287 } |
|
288 } |
|
289 } |
|
290 |
|
291 |
|
292 /* END */ |