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-2018 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 ) af_angle_atan(FT_Fixed dx,FT_Fixed dy)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 ) af_sort_pos(FT_UInt count,FT_Pos * table)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 ) af_sort_and_quantize_widths(FT_UInt * count,AF_Width table,FT_Pos threshold)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 */ 286