Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!iuvax!watmath!watcgl!awpaeth
From: awpaeth@watcgl.waterloo.edu (Alan Wm Paeth)
Newsgroups: comp.graphics
Subject: Re: Wanted: Bitmap rotation algorithm
Message-ID: <10455@watcgl.waterloo.edu>
Date: 25 Jun 89 20:33:56 GMT
References: <8.UUL1.2#261@persoft.UUCP>
Reply-To: awpaeth@watcgl.waterloo.edu (Alan Wm Paeth)
Organization: U. of Waterloo, Ontario
Lines: 60

>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
>description would be fine, but any high level language implementation
>would do nicely.  Pointers to books and/or articles on the subject
>are also welcome.
                                
If rotation with scale invariance is required, then three simple image skewing
passes suffice. Each pass shears (like a deck of cards) pixels along a scan
line or column. Unlike the 2-pass approach, no potential degradation through
pixel (re)scaling is occurs, making a fast inner loop, but disallowing general
image warping. Rotations of up to 90-degrees are possible for pixel skews of
up to one unit on consecutive scanlines; in practice one normally limits to
45-degrees and takes advantage of 8-fold pixel symmetry. Anti-alising is done
for fractional pixel skews easily (read the paper).  Here is pseudocode from:

  Paeth, A. W.
  ``A Fast Algorithm for General Raster Rotation''
  PROCEEDINGS, Graphics Interface '86
  Vancouver, B.C. May 26-30, 1986

------------------------------------
IMPLEMENTATION
.PP
Scan line shearing is approximated by a blending of adjacent pixels.
In the following code segment, the ``pixmult'' function returns a pixel scaled
by a value $skewf$, where $0 <= skewf < 1$, is a constant parameter for all
``width'' passes through the inner-most loop:
.sp
.LP
.ft CW
PROCEDURE xshear(shear, width, height)
    FOR y := 0 TO height-1 DO
        skew  := shear * (y+0.5);
        skewi := floor(skew);
        skewf := frac(skew);
        oleft := 0;
        FOR x := 0 TO width-1 DO
            pixel := P(width-x, y);
            left  := pixmult(pixel, skewf);
                  /* pixel - left = right */
            pixel := pixel - left + oleft;
            P(width-x+skewi, y) := pixel;
            oleft := left;
        OD
        P(skewi, y) := oleft;
    OD
.sp

-----

The whole technique phrases the rotation question as a system of 2x2 matrices.
Ironically, the earliest reference I can find for decomposition of rotation
matrices into unit-determinant shear matrices is due C.F. Gauss. Ironically,
he was working on a unified approach to a major problem in Geometric Optics:
better ray tracing!

    /Alan Paeth
    Computer Graphics Laboratory
    University of Waterloo