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-2012 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 ) af_angle_atan(FT_Fixed dx,FT_Fixed dy)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 ) af_sort_pos(FT_UInt count,FT_Pos * table)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 ) af_sort_and_quantize_widths(FT_UInt * count,AF_Width table,FT_Pos threshold)270 af_sort_and_quantize_widths( FT_UInt* count, 271 AF_Width table, 272 FT_Pos threshold ) 273 { 274 FT_UInt i, j; 275 FT_UInt cur_idx; 276 FT_Pos cur_val; 277 FT_Pos sum; 278 AF_WidthRec swap; 279 280 281 if ( *count == 1 ) 282 return; 283 284 /* sort */ 285 for ( i = 1; i < *count; i++ ) 286 { 287 for ( j = i; j > 0; j-- ) 288 { 289 if ( table[j].org >= table[j - 1].org ) 290 break; 291 292 swap = table[j]; 293 table[j] = table[j - 1]; 294 table[j - 1] = swap; 295 } 296 } 297 298 cur_idx = 0; 299 cur_val = table[cur_idx].org; 300 301 /* compute and use mean values for clusters not larger than */ 302 /* `threshold'; this is very primitive and might not yield */ 303 /* the best result, but normally, using reference character */ 304 /* `o', `*count' is 2, so the code below is fully sufficient */ 305 for ( i = 1; i < *count; i++ ) 306 { 307 if ( table[i].org - cur_val > threshold || 308 i == *count - 1 ) 309 { 310 sum = 0; 311 312 /* fix loop for end of array */ 313 if ( table[i].org - cur_val <= threshold && 314 i == *count - 1 ) 315 i++; 316 317 for ( j = cur_idx; j < i; j++ ) 318 { 319 sum += table[j].org; 320 table[j].org = 0; 321 } 322 table[cur_idx].org = sum / j; 323 324 if ( i < *count - 1 ) 325 { 326 cur_idx = i + 1; 327 cur_val = table[cur_idx].org; 328 } 329 } 330 } 331 332 cur_idx = 1; 333 334 /* compress array to remove zero values */ 335 for ( i = 1; i < *count; i++ ) 336 { 337 if ( table[i].org ) 338 table[cur_idx++] = table[i]; 339 } 340 341 *count = cur_idx; 342 } 343 344 345 /* END */ 346