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, 2004, 2005, 2006 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 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 */ 293
