Image Rotation

From CGAFaq

The easiest way, according to the comp.graphics faq, is to take the rotation transformation and invert it. Then you just iterate over the destination image, apply this inverse transformation and find which source pixel to copy there.

A much nicer way comes from the observation that the rotation matrix:

R(T) = { { cos(θ), -sin(θ) },
         { sin(θ), cos(θ) } }

is formed by multiplying three matrices, namely:

R(θ) = M₁(θ) * M₂(θ) * M₃(θ)

where

M1(θ) = { { 1, -tan(θ/2) },
	  { 0,      1    } }

M2(θ) = { { 1,      0    },
	  { sin(θ), 1    } }

M3(θ) = { { 1, -tan(θ/2) },
	  { 0,      1    } }

Each transformation can be performed in a separate pass, and because these transformations are either row-preserving or column-preserving, anti-aliasing is quite easy.

Another fast approach is to perform first a column-preserving roation, and then a row-preserving rotation. For an image W pixels wide and H pixels high, this requires W+H BitBlt operations in comparison to the brute-force rotation, which uses W*H SetPixel operations (and a lot of multiplying).

Reference:

• Paeth, A. W., "A Fast Algorithm for General Raster Rotation", Proceedings Graphics Interface ’89, Canadian Information Processing Society, 1986, pp. 77–81 [Note: email copies of this paper are no longer available.]

• [Gems I]