Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!ucbvax!agate!shelby!polya!rokicki
From: rokicki@polya.Stanford.EDU (Tomas G. Rokicki)
Newsgroups: comp.graphics
Subject: Re: Wanted: Bitmap rotation algorithm
Message-ID: <9964@polya.Stanford.EDU>
Date: 12 Jun 89 21:11:48 GMT
References: <8.UUL1.2#261@persoft.UUCP> <230@helens.Stanford.EDU>
Sender: Tomas G. Rokicki <rokicki@polya.Stanford.EDU>
Organization: Stanford University
Lines: 51

mike@relgyro.stanford.edu (Mike Macgirvin) writes:
> >I am look for any and all algorithms relating to rotating a bitmap an
> >aribtrary amount.  Efficiency and accuracy (minimal distortion) are,
> >of course, important considerations.  An English or pseudo-code

> ericf@persoft.UUCP (Eric R. Feigenson) writes:
> unsigned char image[WIDTH][HEIGHT];
> rotate(angle)
>      double angle;     /* rotate image 'angle' degrees */
> {
>      int color;
>      int xx,yy;
>      for(y = 0;y < HEIGHT; y ++)
>           for(x = 0;x < WIDTH; x ++) {
> 	       color = image[xx][yy];
>                xx = (x * cos(radians(angle)) - (y * sin(radians(angle));
>                yy = (x * sin(radians(angle)) + (y * cos(radians(angle));
>                setpixel(xx,yy,color);
>           }
> }

This algorithm can be generalized and improved (eliminating the `holes')
quite easily; simply iterate over the output points rather than the
input points.  Thus,

   for (P = each point in the output) {
      P2 = TRANSFORM(P) ; /* can include rotations, scaling, etc */
      setpixel(destination, P, getpixel(source, P2)) ;
   }

TRANSFORM is the usual six-element matrix, that rounds the point after
it's done.

The resulting bitmap won't be beautiful.  Better results can often be
obtained by interpolating between source pixels.  For instance, if
the unrounded transformed result was (2.3, 4.6), then a better looking
image might be obtained by using

   .3[.6[g(2,4),g(2,5)],.6[g(3,4),g(3,5)]]

where n[a,b] means ((1-n) * a + n * b) and g(x,y) means the value of
the source at pixel (x,y).

The image may be more `blurry' this way, though . . .

If you are scaling up (to more bits), this type of interpolation is
probably not a bad idea.  If you are scaling down (to less bits), it
can give odd effects; you might want to high-pass filter the image
before scaling it down.

-tom