1 /***************************************************************************/
5 /* Routines used to compute vector angles with limited accuracy */
6 /* and very high speed. It also contains sorting routines (body). */
8 /* Copyright 2003-2018 by */
9 /* David Turner, Robert Wilhelm, and Werner Lemberg. */
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. */
17 /***************************************************************************/
24 * We are not using `af_angle_atan' anymore, but we keep the source
25 * code below just in case...
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.
40 * dy * PI / (|dx|+|dy|)
42 * should be enough, and much faster to compute.
44 FT_LOCAL_DEF( AF_Angle
)
45 af_angle_atan( FT_Fixed dx
,
64 angle
= ( AF_ANGLE_PI2
* dy
) / ( ax
+ ay
);
68 angle
= AF_ANGLE_PI
- angle
;
70 angle
= -AF_ANGLE_PI
- angle
;
81 /* the following table has been automatically generated with */
82 /* the `mather.py' Python script */
84 #define AF_ATAN_BITS 8
86 static const FT_Byte af_arctan
[1L << AF_ATAN_BITS
] =
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
123 FT_LOCAL_DEF( AF_Angle
)
124 af_angle_atan( FT_Fixed dx
,
130 /* check trivial cases */
140 angle
= AF_ANGLE_PI2
;
142 angle
= -AF_ANGLE_PI2
;
162 angle
-= AF_ANGLE_PI2
;
165 if ( dx
== 0 && dy
== 0 )
169 angle
+= AF_ANGLE_PI4
;
171 angle
+= af_arctan
[FT_DivFix( dy
, dx
) >> ( 16 - AF_ATAN_BITS
)];
173 angle
+= AF_ANGLE_PI2
-
174 af_arctan
[FT_DivFix( dx
, dy
) >> ( 16 - AF_ATAN_BITS
)];
176 if ( angle
> AF_ANGLE_PI
)
177 angle
-= AF_ANGLE_2PI
;
187 af_sort_pos( FT_UInt count
,
194 for ( i
= 1; i
< count
; i
++ )
196 for ( j
= i
; j
> 0; j
-- )
198 if ( table
[j
] >= table
[j
- 1] )
202 table
[j
] = table
[j
- 1];
210 af_sort_and_quantize_widths( FT_UInt
* count
,
225 for ( i
= 1; i
< *count
; i
++ )
227 for ( j
= i
; j
> 0; j
-- )
229 if ( table
[j
].org
>= table
[j
- 1].org
)
233 table
[j
] = table
[j
- 1];
239 cur_val
= table
[cur_idx
].org
;
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
++ )
247 if ( table
[i
].org
- cur_val
> threshold
||
252 /* fix loop for end of array */
253 if ( table
[i
].org
- cur_val
<= threshold
&&
257 for ( j
= cur_idx
; j
< i
; j
++ )
262 table
[cur_idx
].org
= sum
/ (FT_Pos
)j
;
264 if ( i
< *count
- 1 )
267 cur_val
= table
[cur_idx
].org
;
274 /* compress array to remove zero values */
275 for ( i
= 1; i
< *count
; i
++ )
278 table
[cur_idx
++] = table
[i
];