A Fast Algorithm for Rotating Bitmaps

                                      by
                                  Karl Lager

  According to "Tricks of the Game Programming Gurus", rotating
a bitmap in real time generally isn't done because of the complex
math involved and slow speed. However, with a few optimizations 
it can be done nearly as fast as bitmap scaling.

  To start with, each pixel can be given x,y coordinates.  To rotate 
these by an angle t about the 0 axis , the new coordinates can be 
plotted as (x',y') = (x cos(t) - y sin(t),  y cos(t) + x sin(t)).
( for x = right, y = down, clockwise rotations. )

To convert a pixel on screen to the bitmap, the directions would be 
reversed:
        
        (x',y') = (x cos(t) + y sin(t), y cos(t) - x sin(t);

To rotate a whole bitmap, you can plot
        
        ( for y = min_y to max_y
            for x = min_x to max_x
               x' = (x cos (t) + y sin(t))
               y' = (y cos(t) - x cos(t))
               if (x', y') is in the bounds of the bitmap, 
                 get pixel(x',y') and plot the pixel to (x,y) on screen.
        )

Now, you might want to rotate the bitmap about an arbitrary pixel(x1',y1'), 
and put it to an arbitrary point on screen(x1,y1), and to do this you 
could get pixel(x'+ x1', y'+ y1') and put it to (x + x1, y + y1) on screen.

To speed this procedure up, you can start by taking the trig equations
out of the inner loop.  The angle doesn't change, so these calculations
should only be done once.

        double cosT,sinT;
        cosT = cos(t);
        sinT = sin(t);
        for (y = min_y - y1; y <= max_y - y1; y++)
          for (x = min_x - x1; x <= max_x - x1; x++)
           { x' = (x * cosT + y * sinT);
             y' = (y * cosT - x * sinT);
             if (x'+ x1', y'+ y1') is in the bounds of the bitmap, 
               get pixel(x'+ x1', y'+ y1') and plot the pixel to 
               (x + x1, y + y1) on screen.
           }



Since x and y are incremented by a constant value, the code can be 
streamlined further by removing the multiplications from the inner loop:

        double cosT,sinT;
        cosT = cos(t);
        sinT = sin(t);
        for (y = min_y - y1; y <= max_y - y1; y++)
         { x' = (min_x-x1) * cosT + y * sinT;
           y' = y * cosT - (min_x-x1) * sinT;
           for (x = min_x-x1; x <= max_x - x1; x++)
            { if (x'+ x1', y'+ y1') is in the bounds of the bitmap, 
                 get pixel(x'+ x1',y'+ y1') and plot the pixel to 
                 (x + x1,y + y1) on screen.
              x' += cosT;
              y' -= sinT;
            }
         }

Finally, remove the extra additions from the inner loops:

        double cosT,sinT;
        cosT = cos(t);
        sinT = sin(t);
        for (y = min_y; y <= max_y; y++)
         { x' = (min_x-x1) * cosT + (y-y1) * sinT + x1';
           y' = (y-y1) * cosT - (min_x-x1) * sinT + y1';
           for (x = min_x; x <= max_x; x++)
            { if (x', y') is in the bounds of the bitmap, 
                 get pixel(x', y') and plot the pixel to 
                 (x, y) on screen.
              x' += cosT;
              y' -= sinT;
            }
         }

  Thus you have gone from doing 4 transcendental functions (or 4 lookups
and 4 multiplications if you are using lookup tables) per pixel to
doing 2 additions per pixel. That's going from instructions that take
a couple hundred CPU cycles with a coprocessor or thousands without
one to instructions that take one cycle.

  Further gains can be made by making your max and min values exactly 
fit the bounds of the bitmap and the video screen or window.