|
|
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.
|