Rotation: A programming koan

One of the hardest problems in working with raster graphics is rotation. How do you rotate an array of pixels by an arbitrary angle in such a way that the picture still looks good?

Let's start with nine pixels.

The starting 3-by-3 square of colors. In English reading order: red, orange, yellow, purple, gray, green, violet, blue, light blue.

Now we rotate them 45°.

Same square, rotated 45 degrees counter-clockwise. The square pixels are now diamonds; red is the left corner, and yellow is the top corner.

Simple enough, right?

The problem is, monitors don't adapt so easily to diamond-shaped pixels. We need to convert these diamond-shaped pixels back to square pixels.

Previous diamond arrangement, with the individual pixels rotated back to squares.

This is equivalent to showing the original square arrangement with diamond pixels:

Original (pre-rotation) square arrangement, with diamond-shaped pixels.

But there's a problem: Those gaps between the pixels. They make for a low resolution and will ruin our pretty colors. (Think of viewing the image through one of those roll-up car window shades.)

So we need to take the gaps out. This leaves us with one of two hopscotch-like representations:

The diamond arrangement with square pixels, with the gaps removed. The even rows are offset horizontally by half a pixel.

Hmmm. OK, so we got back to square pixels, but we have a new problem: the aspect ratio of the image has changed. Remember that we had a bisymmetrical diamond: the X diameter was the same as the Y diameter. Now we have a diamond that is squished on one axis or the other. And we still have the previous problem, that this won't fit on a monitor with a plain (non-staggered) grid of pixels.

No problem. Working from the second image, we'll interpolate the even columns from two pixels each into three pixels each.

The even columns are back in alignment with the odd columns. However, the pixels in each even column have faded somewhat as a consequence of interpolation. Also, the middle column is still only three pixels high, though the middle row is five pixels across.

Ack. Not so good. And what do we do about that middle column? Suppose we stretch it out to five pixels: rows (1,2)→1, (1,2,3)→2, (2,3,4)→3, (3,4,5)→4, (4,5)→5.

Same interpolation applied to the middle column. The top and bottom output pixels in that column are blended from white and the top/bottom input pixel; the inner two output pixels are blended from white and two input pixels; the center output pixel is blended from three input pixels.

Interpolation has faded the colors of each pixel in the middle column, and the center pixel is now a faint brown, rather than pure 50% gray. Blurgh. There must be a better way.

Rotation

A programming koan

by Peter Hosey