mikem@uhccux.uhcc.hawaii.edu (Mike Morton) (11/05/88)
A friend and I are looking for information on how to rotate a bitmapped
image by an arbitrary angle (not something nice like 90 degrees).
Unfortunately, we'd like to find a fast algorithm; is this possible?
A description or reference to something published would be great.
Please email to me, as I don't normally read this group. I'll post a
summary.
-- Mike Morton // P.O. Box 11378, Honolulu, HI 96828, (808) 676-6966 HST
Internet: msm@ceta.ics.hawaii.edu
(anagrams): Mr. Machine Tool; Ethical Mormon; Chosen Immortal; etc.cm26+@andrew.cmu.edu (Curt McDowell) (11/08/88)
/*
* How to Rotate Bitmaps: Example
*
* By Curt McDowell, Carnegie Mellon University
*
* I posted before on how wonderful CORDIC is. But this is a
* very good opportunity to convince the rest of you!!
*
* CORDIC is the only imaginable way to accomplish this
* task. If anyone thinks I'm wrong, please tell me about your
* method! How does PostScript do it?
*
* Do not attempt to compile this right away, since it requires
* my own bitmap graphics package. However the modifications
* for using other bitmap packages are trivial since only
* the ability to set, reset, and test single points is necessary.
*/
#include "gr.h"
#include "ras.h"
/*
* CORDIC works better if everything is done shifted left.
* The scaling provides extra bits of accuracy on the right,
* without affecting the amount of rotation. So it's like
* fixed-point arithmetic. The shifting used for scaling takes
* 1 operation on most computers (or 0 on some like Z-80).
*/
#define SCALE 16
/*
* What I do is first decide what area of the screen I
* want to rotate. In this example it's a large circle
* in the center of the screen. I scan the area and,
* for each pixel that is on, enter its coordinates in a
* large array of pixel (x,y)'s. This is the sole purpose
* of initpoints().
*
* To make it faster I've gone down to the bitmap.
* You could use any method you want. For a square
* area, e.g.:
*
* numpoints = 0;
* for (y = 0; y < MAXY; y++)
* for (x = 0; x < MAXX; x++)
* if (PointSet(x, y)) {
* arrayX[numpoints] = x << SCALE;
* arrayY[numpoints] = y << SCALE;
* numpoints++;
* }
*
* Also notice I'm scaling the points left by 16 bits as
* I read them in. I'll simply scale them right when plotting
* the rotated image. Simple. We're done worrying about
* scaling!
*/
#define MAXPOINTS 150000
long px[MAXPOINTS], py[MAXPOINTS];
int numpoints;
long cx, cy;
struct ras *screen;
#ifdef MSBLEFT
#define LeftBitOn(b) (b & MSBit)
#define ShiftLeft(b) (b <<= 1)
#else
#define LeftBitOn(b) (b & LSBit)
#define ShiftLeft(b) (b >>= 1)
#endif
initpoints(radius)
int radius;
{
register unsigned long *p, b;
int lineCount, colCount;
register int bitCount;
int curx, cury, curySquared;
int radiusSquared = radius * radius;
numpoints = 0;
lineCount = screen->height;
p = gr_framebuf;
cury = -cy;
/* Don't worry about this stuff. It's a faster way of reading */
/* the pixels from a circle. */
while (lineCount--) {
curySquared = cury * cury;
curx = -cx;
colCount = screen->width / 32;
while (colCount--) {
bitCount = 32;
b = *p;
while (bitCount--) {
if (curx * curx + curySquared < radiusSquared &&
LeftBitOn(b)) {
px[numpoints] = curx << SCALE;
py[numpoints] = cury << SCALE;
numpoints++;
}
ShiftLeft(b);
curx++;
}
p++;
}
cury++;
}
}
/*
* This routine right here is the amazing one.
* It erases the previous image and simultaneously
* draws the new rotated one, using XOR plotting mode!
*
* By far the most time being spent in this routine is
* in the plotting, NOT the rotation!
*
* Of course, you could remove plotting from this routine
* altogether. Then this routine reduces to something
* ridiculously small which rotates an array of points by
* some angle. Amazing! You can use any scheme you want
* for erasing the old image and replotting the new one, if
* that's what you need.
*
* Can anyone think of a better way to store the pixels than
* the (x, y) coordinates? Maybe something independent of the
* pixel density?
*/
cycle(xs, ys, count)
register long *xs, *ys;
register int count;
{
while (count--) {
/* Turn off point from old location */
ras_tog(screen, cx + (*xs >> SCALE), cy + (*ys >> SCALE));
/* Simple CORDIC rotation by atn(2 ^ -k). E.g., */
/* k=4 is rotation by ~ 3.57 deg CW */
/* k=5 is rotation by ~ 1.79 deg CW */
/* To rotate CCW, toggle subtraction and addition! */
/* Below is a rotation by 1.79 deg (k=5). */
*xs -= *ys >> 5;
*ys += *xs >> 5;
/* Set point at new location. Wow! */
ras_tog(screen, cx + (*xs >> SCALE), cy + (*ys >> SCALE));
xs++;
ys++;
}
}
/*
* But, you say, you can only rotate by these weird
* arctangent angles. Well, the next obvious thing to do
* is use a few CORDIC rotations in a row to get any
* angle. No problem since each rotation is only two
* shifts, an add, and a subtract! E.g.:
*
* *xs -= *ys >> 5;
* *ys += *xs >> 5;
* *xs -= *ys >> 4;
* *ys += *xs >> 4;
*
* This would rotate atn(2^-4) + atn(2^-5) or about
* 3.57 + 1.79 = 5.36 degrees. Since your scale can get as
* big as you want, you can get any angle to any accuracy
* using rotations of the right sizes.
* You can also mix in CCW rotations if it helps.
*/
main()
{
srand(time(0));
/* Open screen... */
gr_init();
screen =
ras_dpy((u_short *) gr_framebuf,
gr_screenwidth, gr_screenheight);
cx = screen->width / 2;
cy = screen->height / 2;
/* Read in initial points from a big circle on the screen. */
/* It reads what happens to be on the screen when */
/* this program is run. */
initpoints(screen->height * 7 / 16);
/* Now -- repeatedly rotate a little, erasing and */
/* redrawing the image! */
while (1)
cycle(px, py, numpoints);
}
/*
* BUT WAIT, that's not all! CORDIC rotation is stable.
* This means you can sit there rotating the same set of
* points repeatedly forever, and they will NOT diverge or
* converge. Although a few of them may shift a pixel or so.
*
* In the unlikely event that you make a million bucks
* because of seeing this, send money and/or employment
* literature to:
*
* Curt McDowell
* Box 499
* 5115 Margaret Morrison St.
* Pittsburgh, PA 15213
*
* Arpa mail: cm26@andrew.cmu.edu
*/