Rotation using the 3-step shear method
created: 06 Nov 2019

The intuitive approach for rotating points is to use a rotation matrix. This has many computational drawbacks for raster graphics, though. After applying a rotation matrix, pixels fall aperiodically on non-integral coordinates, and up to six input pixels can cover a single output pixel. Because of this, programs must determine areas of overlapping pixels, and sum their intensities. This is unsurprisingly costly.

Alan Paeth tackled this issue in his 1986 paper "A Fast Algorithm for General Raster Rotation," wherein he formulated an attractive alternative that uses three shearing procedures.[1] While simple, this method is widely used, such as in the ImageMagick suite of tools.[2]

Method

Paeth's method uses three shear transformations: Shear horizontally, shear vertically, and then horizontally again. Shearing bitmaps is simple: move each row/column by the shear amount, and sample surrounding pixels for anti-aliasing. This is optimally implemented as a one-pass algorithm, as opposed to three individual shearing calls.

/* Determine shearing amounts */
alpha := -tan(theta / 2);
beta := sin(theta);

/* Perform shears */
shear_x(alpha);
shear_y(beta);
shear_x(alpha);

Note that around 180°, this method will break down (-tan(180° / 2) = ∞?). A simple way to avoid this pitfall can be found in ImageMagick's code, under the "adjust rotation angle" comment.[2]

Footnotes

  1. Paeth, Alan (1986). "A Fast Algorithm for General Raster Rotation".
  2. 3-Step Shear method found in ImageMagick.