This page contains reasonably short explainations of various techniques that beginning game programmers often need to know about.

Reducing angles in trigonometry calculations to the -45 to +45 degree range.

The trigonometry functions (Sin, Cos and Tan) are repeating wave forms. Thus although it is perfectly sensible to take the sin or cos of any angle, the values returned start repeating fairly soon. By judicious use of compares, mods and subtraction as well as the conversions between sin and cos, we can take any trig erquest and reduce it to a trig call within the -45 to +45 degree range.

Why would we want to do this? There are a few reasons. It used to be that trigonometry functions were always calculated in software, Back then techniques were developed to do fast trigonometric approximations using a look-up table. By reducing the angles to the -45 to +45 degree range that table could be kept small. Although trig lookup tables are no longer necessary on the desktop, they are still useful in many embedded spaces such as set-top boxes and cell-phones.

A second reason for reducing your angles to the -45 to 45 degree range though has to do with a fault in the x86 line of processors. Java makes promises of math accuracy in its specification. Outside of the -45 to 45 degree range, the in-built trig funtions (sometimes called "intrinsics") in the x86 family of processors return incorrect results at the accuracy that Java requires. For this reason Java VMs on the x86 processor avoid the hardware and default over to a software calculation for angles outside of that range. This is much slower then doing it with the hardware. By reducing your angles to the -45 to +45 degree range, you keep it within the spectrum that can be done on the hardware and keep it fast.

The code below will do this conversion for you:

public class FastTrig {
   /**
         * Fast Trig functions for x86.  
         * This forces the trig functiosn to stay within the safe area on the x86 processor (-45 degrees to +45 degrees)
         * The results may be very slightly off from what the Math and StrictMath trig functions give due to
         * rounding in the angle reduction but it will be very very close.
         */
   static double reduceSinAngle(double radians){
      double orig = radians;
      radians %= Math.PI*2.0; // put us in -2PI to +2PI space
      if (Math.abs(radians)>Math.PI){ // put us in -PI to +PI space
         radians = radians-(Math.PI*2.0); 
      }
      if (Math.abs(radians)>Math.PI/2){// put us in -PI/2 to +PI/2 space
         radians = Math.PI - radians;
      }      
      
      return radians;
   }
   
   static double fastSin(double radians){
      radians = reduceSinAngle(radians); // limits angle to between -PI/2 and +PI/2
      if (Math.abs(radians)<=Math.PI/4){
         return Math.sin(radians);
      } else {
         return Math.cos(Math.PI/2-radians);
      }
   }
   
   static double fastCos(double radians){
      return fastSin(radians+Math.PI/2);
   }
   
}

*Note: Some of the guys at JGO have been benchmarking this and found some interesting results. If you compute a whole bunch of Cos in a linear series (looping and adding to the angle for instance) this code comes out about the same speed as just calling Math.cos for everything BUT if you randomly destribute the angles calculated it is indeed significantly faster. This suggests that Math.cos is taking advantage of previous calculations when faced with a series. The nice side benefit of that is if you are going to go all the way to a table-lookup, calculation of your table should be pretty quick. (Special thanks go to DzzD aka Bruno for doing the benchmarking 8) *

Fast-shifter based Integer Abs function

This optimization requries your CPU support a fast multiple-place shift operation. (Most desktops do today).If your processor does not do multiple-place shifts quickly then it might actually be slower. But on systems that do support fast shifting it's dynamite, running at less then a third the speed of Math.abs() on an Intel box under JDK1.6.

public static int abs(int a)
{
    return (a^(a>>31))-(a>>31);
}

-- Main.jeffpk - 04 Dec 2005