1package jme3tools.android; 2 3import java.util.Random; 4 5/** 6 * Fixed point maths class. This can be tailored for specific needs by 7 * changing the bits allocated to the 'fraction' part (see <code>FIXED_POINT 8 * </code>, which would also require <code>SIN_PRECALC</code> and <code> 9 * COS_PRECALC</code> updating). 10 * 11 * <p><a href="http://blog.numfum.com/2007/09/java-fixed-point-maths.html"> 12 * http://blog.numfum.com/2007/09/java-fixed-point-maths.html</a></p> 13 * 14 * @version 1.0 15 * @author CW 16 * 17 * @deprecated Most devices with OpenGL ES 2.0 have an FPU. Please use 18 * floats instead of this class for decimal math. 19 */ 20@Deprecated 21public final class Fixed { 22 23 /** 24 * Number of bits used for 'fraction'. 25 */ 26 public static final int FIXED_POINT = 16; 27 /** 28 * Decimal one as represented by the Fixed class. 29 */ 30 public static final int ONE = 1 << FIXED_POINT; 31 /** 32 * Half in fixed point. 33 */ 34 public static final int HALF = ONE >> 1; 35 /** 36 * Quarter circle resolution for trig functions (should be a power of 37 * two). This is the number of discrete steps in 90 degrees. 38 */ 39 public static final int QUARTER_CIRCLE = 64; 40 /** 41 * Mask used to limit angles to one revolution. If a quarter circle is 64 42 * (i.e. 90 degrees is broken into 64 steps) then the mask is 255. 43 */ 44 public static final int FULL_CIRCLE_MASK = QUARTER_CIRCLE * 4 - 1; 45 /** 46 * The trig table is generated at a higher precision than the typical 47 * 16.16 format used for the rest of the fixed point maths. The table 48 * values are then shifted to match the actual fixed point used. 49 */ 50 private static final int TABLE_SHIFT = 30; 51 /** 52 * Equivalent to: sin((2 * PI) / (QUARTER_CIRCLE * 4)) 53 * <p> 54 * Note: if either QUARTER_CIRCLE or TABLE_SHIFT is changed this value 55 * will need recalculating (put the above formular into a calculator set 56 * radians, then shift the result by <code>TABLE_SHIFT</code>). 57 */ 58 private static final int SIN_PRECALC = 26350943; 59 /** 60 * Equivalent to: cos((2 * PI) / (QUARTER_CIRCLE * 4)) * 2 61 * 62 * Note: if either QUARTER_CIRCLE or TABLE_SHIFT is changed this value 63 * will need recalculating ((put the above formular into a calculator set 64 * radians, then shift the result by <code>TABLE_SHIFT</code>). 65 */ 66 private static final int COS_PRECALC = 2146836866; 67 /** 68 * One quarter sine wave as fixed point values. 69 */ 70 private static final int[] SINE_TABLE = new int[QUARTER_CIRCLE + 1]; 71 /** 72 * Scale value for indexing ATAN_TABLE[]. 73 */ 74 private static final int ATAN_SHIFT; 75 /** 76 * Reverse atan lookup table. 77 */ 78 private static final byte[] ATAN_TABLE; 79 /** 80 * ATAN_TABLE.length 81 */ 82 private static final int ATAN_TABLE_LEN; 83 84 /* 85 * Generates the tables and fills in any remaining static ints. 86 */ 87 static { 88 // Generate the sine table using recursive synthesis. 89 SINE_TABLE[0] = 0; 90 SINE_TABLE[1] = SIN_PRECALC; 91 for (int n = 2; n < QUARTER_CIRCLE + 1; n++) { 92 SINE_TABLE[n] = (int) (((long) SINE_TABLE[n - 1] * COS_PRECALC) >> TABLE_SHIFT) - SINE_TABLE[n - 2]; 93 } 94 // Scale the values to the fixed point format used. 95 for (int n = 0; n < QUARTER_CIRCLE + 1; n++) { 96 SINE_TABLE[n] = SINE_TABLE[n] + (1 << (TABLE_SHIFT - FIXED_POINT - 1)) >> TABLE_SHIFT - FIXED_POINT; 97 } 98 99 // Calculate a shift used to scale atan lookups 100 int rotl = 0; 101 int tan0 = tan(0); 102 int tan1 = tan(1); 103 while (rotl < 32) { 104 if ((tan1 >>= 1) > (tan0 >>= 1)) { 105 rotl++; 106 } else { 107 break; 108 } 109 } 110 ATAN_SHIFT = rotl; 111 // Create the a table of tan values 112 int[] lut = new int[QUARTER_CIRCLE]; 113 for (int n = 0; n < QUARTER_CIRCLE; n++) { 114 lut[n] = tan(n) >> rotl; 115 } 116 ATAN_TABLE_LEN = lut[QUARTER_CIRCLE - 1]; 117 // Then from the tan values create a reverse lookup 118 ATAN_TABLE = new byte[ATAN_TABLE_LEN]; 119 for (byte n = 0; n < QUARTER_CIRCLE - 1; n++) { 120 int min = lut[n]; 121 int max = lut[n + 1]; 122 for (int i = min; i < max; i++) { 123 ATAN_TABLE[i] = n; 124 } 125 } 126 } 127 /** 128 * How many decimal places to use when converting a fixed point value to 129 * a decimal string. 130 * 131 * @see #toString 132 */ 133 private static final int STRING_DECIMAL_PLACES = 2; 134 /** 135 * Value to add in order to round down a fixed point number when 136 * converting to a string. 137 */ 138 private static final int STRING_DECIMAL_PLACES_ROUND; 139 140 static { 141 int i = 10; 142 for (int n = 1; n < STRING_DECIMAL_PLACES; n++) { 143 i *= i; 144 } 145 if (STRING_DECIMAL_PLACES == 0) { 146 STRING_DECIMAL_PLACES_ROUND = ONE / 2; 147 } else { 148 STRING_DECIMAL_PLACES_ROUND = ONE / (2 * i); 149 } 150 } 151 /** 152 * Random number generator. The standard <code>java.utll.Random</code> is 153 * used since it is available to both J2ME and J2SE. If a guaranteed 154 * sequence is required this would not be adequate. 155 */ 156 private static Random rng = null; 157 158 /** 159 * Fixed can't be instantiated. 160 */ 161 private Fixed() { 162 } 163 164 /** 165 * Returns an integer as a fixed point value. 166 */ 167 public static int intToFixed(int n) { 168 return n << FIXED_POINT; 169 } 170 171 /** 172 * Returns a fixed point value as a float. 173 */ 174 public static float fixedToFloat(int i) { 175 float fp = i; 176 fp = fp / ((float) ONE); 177 return fp; 178 } 179 180 /** 181 * Returns a float as a fixed point value. 182 */ 183 public static int floatToFixed(float fp) { 184 return (int) (fp * ((float) ONE)); 185 } 186 187 /** 188 * Converts a fixed point value into a decimal string. 189 */ 190 public static String toString(int n) { 191 StringBuffer sb = new StringBuffer(16); 192 sb.append((n += STRING_DECIMAL_PLACES_ROUND) >> FIXED_POINT); 193 sb.append('.'); 194 n &= ONE - 1; 195 for (int i = 0; i < STRING_DECIMAL_PLACES; i++) { 196 n *= 10; 197 sb.append((n / ONE) % 10); 198 } 199 return sb.toString(); 200 } 201 202 /** 203 * Multiplies two fixed point values and returns the result. 204 */ 205 public static int mul(int a, int b) { 206 return (int) ((long) a * (long) b >> FIXED_POINT); 207 } 208 209 /** 210 * Divides two fixed point values and returns the result. 211 */ 212 public static int div(int a, int b) { 213 return (int) (((long) a << FIXED_POINT * 2) / (long) b >> FIXED_POINT); 214 } 215 216 /** 217 * Sine of an angle. 218 * 219 * @see #QUARTER_CIRCLE 220 */ 221 public static int sin(int n) { 222 n &= FULL_CIRCLE_MASK; 223 if (n < QUARTER_CIRCLE * 2) { 224 if (n < QUARTER_CIRCLE) { 225 return SINE_TABLE[n]; 226 } else { 227 return SINE_TABLE[QUARTER_CIRCLE * 2 - n]; 228 } 229 } else { 230 if (n < QUARTER_CIRCLE * 3) { 231 return -SINE_TABLE[n - QUARTER_CIRCLE * 2]; 232 } else { 233 return -SINE_TABLE[QUARTER_CIRCLE * 4 - n]; 234 } 235 } 236 } 237 238 /** 239 * Cosine of an angle. 240 * 241 * @see #QUARTER_CIRCLE 242 */ 243 public static int cos(int n) { 244 n &= FULL_CIRCLE_MASK; 245 if (n < QUARTER_CIRCLE * 2) { 246 if (n < QUARTER_CIRCLE) { 247 return SINE_TABLE[QUARTER_CIRCLE - n]; 248 } else { 249 return -SINE_TABLE[n - QUARTER_CIRCLE]; 250 } 251 } else { 252 if (n < QUARTER_CIRCLE * 3) { 253 return -SINE_TABLE[QUARTER_CIRCLE * 3 - n]; 254 } else { 255 return SINE_TABLE[n - QUARTER_CIRCLE * 3]; 256 } 257 } 258 } 259 260 /** 261 * Tangent of an angle. 262 * 263 * @see #QUARTER_CIRCLE 264 */ 265 public static int tan(int n) { 266 return div(sin(n), cos(n)); 267 } 268 269 /** 270 * Returns the arc tangent of an angle. 271 */ 272 public static int atan(int n) { 273 n = n + (1 << (ATAN_SHIFT - 1)) >> ATAN_SHIFT; 274 if (n < 0) { 275 if (n <= -ATAN_TABLE_LEN) { 276 return -(QUARTER_CIRCLE - 1); 277 } 278 return -ATAN_TABLE[-n]; 279 } else { 280 if (n >= ATAN_TABLE_LEN) { 281 return QUARTER_CIRCLE - 1; 282 } 283 return ATAN_TABLE[n]; 284 } 285 } 286 287 /** 288 * Returns the polar angle of a rectangular coordinate. 289 */ 290 public static int atan(int x, int y) { 291 int n = atan(div(x, abs(y) + 1)); // kludge to prevent ArithmeticException 292 if (y > 0) { 293 return n; 294 } 295 if (y < 0) { 296 if (x < 0) { 297 return -QUARTER_CIRCLE * 2 - n; 298 } 299 if (x > 0) { 300 return QUARTER_CIRCLE * 2 - n; 301 } 302 return QUARTER_CIRCLE * 2; 303 } 304 if (x > 0) { 305 return QUARTER_CIRCLE; 306 } 307 return -QUARTER_CIRCLE; 308 } 309 310 /** 311 * Rough calculation of the hypotenuse. Whilst not accurate it is very fast. 312 * <p> 313 * Derived from a piece in Graphics Gems. 314 */ 315 public static int hyp(int x1, int y1, int x2, int y2) { 316 if ((x2 -= x1) < 0) { 317 x2 = -x2; 318 } 319 if ((y2 -= y1) < 0) { 320 y2 = -y2; 321 } 322 return x2 + y2 - (((x2 > y2) ? y2 : x2) >> 1); 323 } 324 325 /** 326 * Fixed point square root. 327 * <p> 328 * Derived from a 1993 Usenet algorithm posted by Christophe Meessen. 329 */ 330 public static int sqrt(int n) { 331 if (n <= 0) { 332 return 0; 333 } 334 long sum = 0; 335 int bit = 0x40000000; 336 while (bit >= 0x100) { // lower values give more accurate results 337 long tmp = sum | bit; 338 if (n >= tmp) { 339 n -= tmp; 340 sum = tmp + bit; 341 } 342 bit >>= 1; 343 n <<= 1; 344 } 345 return (int) (sum >> 16 - (FIXED_POINT / 2)); 346 } 347 348 /** 349 * Returns the absolute value. 350 */ 351 public static int abs(int n) { 352 return (n < 0) ? -n : n; 353 } 354 355 /** 356 * Returns the sign of a value, -1 for negative numbers, otherwise 1. 357 */ 358 public static int sgn(int n) { 359 return (n < 0) ? -1 : 1; 360 } 361 362 /** 363 * Returns the minimum of two values. 364 */ 365 public static int min(int a, int b) { 366 return (a < b) ? a : b; 367 } 368 369 /** 370 * Returns the maximum of two values. 371 */ 372 public static int max(int a, int b) { 373 return (a > b) ? a : b; 374 } 375 376 /** 377 * Clamps the value n between min and max. 378 */ 379 public static int clamp(int n, int min, int max) { 380 return (n < min) ? min : (n > max) ? max : n; 381 } 382 383 /** 384 * Wraps the value n between 0 and the required limit. 385 */ 386 public static int wrap(int n, int limit) { 387 return ((n %= limit) < 0) ? limit + n : n; 388 } 389 390 /** 391 * Returns the nearest int to a fixed point value. Equivalent to <code> 392 * Math.round()</code> in the standard library. 393 */ 394 public static int round(int n) { 395 return n + HALF >> FIXED_POINT; 396 } 397 398 /** 399 * Returns the nearest int rounded down from a fixed point value. 400 * Equivalent to <code>Math.floor()</code> in the standard library. 401 */ 402 public static int floor(int n) { 403 return n >> FIXED_POINT; 404 } 405 406 /** 407 * Returns the nearest int rounded up from a fixed point value. 408 * Equivalent to <code>Math.ceil()</code> in the standard library. 409 */ 410 public static int ceil(int n) { 411 return n + (ONE - 1) >> FIXED_POINT; 412 } 413 414 /** 415 * Returns a fixed point value greater than or equal to decimal 0.0 and 416 * less than 1.0 (in 16.16 format this would be 0 to 65535 inclusive). 417 */ 418 public static int rand() { 419 if (rng == null) { 420 rng = new Random(); 421 } 422 return rng.nextInt() >>> (32 - FIXED_POINT); 423 } 424 425 /** 426 * Returns a random number between 0 and <code>n</code> (exclusive). 427 */ 428 public static int rand(int n) { 429 return (rand() * n) >> FIXED_POINT; 430 } 431}